Алгоритм 2D уровня детализации (LOD)

Я искал в сети алгоритм, который позволяет вам создавать представления уровня детализации (LOD) 2D-полигонов, но не может найти ЛЮБУЮ достойную ссылку. Возможно, я использую неправильные условия поиска, но все результаты поиска относятся к алгоритмам 3D LOD, которые, я думаю, не могут (?) Действительно применяться в 2D.

Я уверен, что до наступления трехмерной графики многие люди работали бы над алгоритмами 2D LOD. Любые подсказки или указатели, где я могу получить больше информации? Спасибо!

Источник

2 ответа

Решение

Помимо очевидного глупого алгоритма, который должен был бы брать каждую N-ую вершину из многоугольника (уменьшая число вершин на N), здесь есть идея, вдохновленная некоторыми 3D-алгоритмами.

Обычно в 3D требуется удалить грани, которые вносят меньший вклад в общий объем. Для этого мы постараемся упростить "самые плоские" участки модели.

Теперь в 2D вы можете перевести это, чтобы "упростить сегменты, которые имеют наименьший угол между ними. Первой наивной реализацией может быть:

  1. Вычислить все углы между отрезками Si и Si+1 многоугольника
  2. Возьмите все углы ниже заданного порога (или возьмите М наименьших углов)
  3. Упростим сегменты, которые мы определили в 2. (замените [Pi, Pi+1] и [Pi+1, Pi+2] на [Pi, Pi+2])
  4. Повторяйте от 1. до тех пор, пока мы не уменьшим наш полигон

Конечно, это не оптимально, но это должна быть хорошая сделка между качеством и скоростью. Вместо угла можно взять минимальное расстояние между средней точкой двух сегментов (Pi+1) и потенциально упрощенным сегментом ([Pi, Pi+2])

Редактировать:

Я бы попробовал другой алгоритм, если бы мне не нужно было слишком много производительности:

  1. Рассмотрим исходные вершины многоугольника как контрольные точки сплайна Кэтмалла-Рома.
  2. Тесселяйте этот сплайн в нужном количестве точек

Наконец, я нашел для вас исходный код по этой ссылке: http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html, а также соответствующие алгоритмы: http://www.geom.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm

Источник

Найдите алгоритм Дугласа-Пекера, который используется для упрощения полилиний, но может быть расширен для поддержки многоугольников. Это то, что я использовал. Существуют также топологически стабильные расширения, если вам это нужно.

Источник
Другие вопросы по тегам