Генерация минимального набора вершин из сплайна/кривой

В моем проекте я представляю геометрию с помощью сплайнов. Для физики и рендеринга я предварительно обрабатываю сплайны и преобразовываю их в линии, а затем в полигоны, сэмплируя сплайны через равные промежутки времени. Однако я хочу уменьшить количество вершин/линий, игнорируя образцы, которые уже достаточно хорошо представлены линией.

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

РЕДАКТИРОВАТЬ: Чтобы уточнить, результат, который я хочу получить, - это количество вершин/линейных сегментов, которые лучше всего представляют сплайн с наименьшим количеством вершин/линейных сегментов. Я не уверен, как определить, что на самом деле означает «наилучшее представление сплайна», но цель состоит в том, чтобы максимально усложнить различие между сплайном и приближением.


algorithm computational-geometry spline polygon
person Jens Andersson    schedule 23.04.2014    source источник
comment
Традиционная техника, которую я знал, заключалась в оптимизации максимального расстояния.   -  person Denys Séguret    schedule 23.04.2014
comment
Существуют ли какие-либо ограничения или дополнительные полезные свойства, которые могут помочь? Например: если точки могут быть определены некоторыми функциями x(t) и y(t), где t — индекс вершины (так что 1-я вершина будет (x(0), y(0))), это даст нам еще немного для работы.   -  person Conduit    schedule 23.04.2014
comment
@Nate, мои постыдно низкие математические способности заставляют меня избегать попыток объяснить проблему в этих терминах, поскольку я ожидаю, что это больше запутает, чем поможет. Однако, если сплайн s(0 -> 1) и я выбираю s(0,01), s(0,02), s(0,03),..., s(1), чтобы получить xy[0], xy[1] , ху[2], ..., ху[100]. (В этом случае xy является 2d-вершиной, но я не ожидаю, что проблема будет отличаться в 3d). Затем я хочу найти набор s(t0), s(t1), s(t2),..., s(tn), откуда линейная интерполяция будет соответствовать s(0 -> 1) до указанной суммы ошибки.   -  person Jens Andersson    schedule 23.04.2014

Ответы (2)


arrow_upward
4
arrow_downward

Это можно сделать путем рекурсивного уточнения части, которая не находится рядом с сегментом между концами части.

Если у нас есть кривая (сплайн) C:[0,1]->R^n. Первым приближением является отрезок S между конечными точками кривой [C(0), C(1)]. Возьмите точку C(0.5) и проверьте, насколько далеко она от сегмента S. Если это далеко, то мы должны принять это в дискретизации, если нет, то S является хорошим приближением. Если C(0.5) далеко, то следующим приближением будет ломаная [C(0), C(0.5), C(1)], и такую ​​же процедуру проделываем с частями [C(0), C(0.5)] и [C(0.5), C(1)].

Если вы используете полиномиальный сплайн порядка >= 3 (например, кубический сплайн), он может иметь точку (точки) перегиба. В этом случае возможно, что точка кривой на половине может «упасть» точно на отрезок, но огибать его будет далеко от отрезка. В этом случае хорошо проверить еще один уровень подразделов.

person Ante    schedule 23.04.2014
comment
Хм, это действительно умно. Это особенно приятно, так как мне не нужно сэмплировать массу точек на кривой, которые все равно будут отброшены. - person Jens Andersson; 24.04.2014
comment
Это просто и приятно. Алгоритм стандартный, но описания не нашел. Я знаю, что читал об этом в Википедии. - person Ante; 24.04.2014
comment
Если вы можете представить свой сплайн с помощью кривых Безье (это возможно из кубического сплайна), то свойство корпуса позволяет вам использовать подход рекурсивного подразделения с абсолютной гарантией аппроксимации, даже при наличии точек перегиба. - person Yves Daoust; 25.04.2014

arrow_upward
0
arrow_downward

Это полностью основано на моей собственной интуиции, поэтому я не уверен, совпадает ли это вообще с лучшими практиками. У меня есть степень по математике, так что, надеюсь, это не за горами. Замечу, что задействованные вычисления могут превзойти прирост производительности, обеспечиваемый меньшим количеством вершин, если сплайн необходимо часто пересчитывать.

Допустим, вершины находятся в массиве вроде [v(0), v(1), v(2),..., v(n)], где каждая v(i) является чем-то вроде (x, y). Перебирая вершины, начиная с v(1) и заканчивая v(n-1), мы можем сравнить точку с ее соседями, чтобы определить, отбрасывать ее или нет. Обратите внимание, что мы игнорируем v(0) и v(n) по двум причинам: (я предполагаю) мы не хотим удалять наши конечные точки, а также v(0) и v(n) не хватает соседа, который нам нужен для настройки нашего расчета. Я могу придумать здесь пару возможностей, которые могут потребовать изучения, но один, в частности, кажется (в моей голове) лучшим ответом...

Рассмотрим случай, когда мы решаем, удалять ли v(i) из массива вершин. Мы могли бы проверить декартово расстояние между v(i) и его соседями и удалить точку, если оба ниже некоторого порогового значения T. Например, если v(i-1) = (x1, y1) и v(i) = ( x2, y2) и v(i+1) = (x3, y3), то мы оцениваем sqrt((x2-x1)^2 + (y2-y1)^2))<T && sqrt((x3-x2)^2 + (y3-y2)^2))<T, удаляя v(i), если оценка возвращает true.

В 3+ измерениях это усложнилось бы - расчет был бы аналогичным, но вам потребовался бы метод определения соседей точки, поскольку они могут не лежать непосредственно рядом с исследуемой точкой в ​​массиве вершин.

person Conduit    schedule 23.04.2014
comment
Спасибо за ответ Нейт. Хотя это уменьшит количество вершин, это не будет делаться чаще, когда кривая хорошо представлена ​​сегментами линии — не будут сохраняться вершины в более изогнутых частях сплайна, чтобы сохранить там визуальную точность. - person Jens Andersson; 24.04.2014