Расстояние до поверхности

[Igors]

Добрый день

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

Нужно: для заданной внутренней точки p уметь находить кратчайшее расстояние до поверхности модели с заданной точностью.

Погуглив "деньков несколько" я ничего выдающегося не нашел. Конечно "плохо искал" - всегда возможно, но не видно чего-то "авторитетного" чтобы это было признанным и вошло в MatLab и др. обиход. Вообще на форуме преобладают темы в которых есть "правильный ответ" - но в жизни все намного сложнее, часто неизвестно есть ли такой вообще и хз кто назначил его правильным. Поэтому прошу не стесняться "велосипедить"

Спасибо

[Dancing_on_water]

Невыпуклость модели суровое условие.

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

[Igors]

Невыпуклость модели суровое условие.

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

Я велосипедю "примерно в том же направлении" Однако "заданные гранями" явно не годится, модель может иметь приличное число полигонов, нужно как-то использовать быстрый спуск по дереву (пока не знаю как). Плюс еще одна противная проблема

------
       |
       |
       |
       ------------
   *(p)             |
                      |

Здесь проекции дадут гораздо бОльшее расстояние

[Dancing_on_water]

Указанный случай это уже не выпуклый многогранник. Посему и сказал, что это суровое условие.

Стоп. У меня была подобная задача, по идее должно пойти многомерное R-дерево!

[Igors]

Стоп. У меня была подобная задача, по идее должно пойти многомерное R-дерево!

Оказывается достаточно знать "волшебное слово" (напр R-tree) - и все, задача решена! Хорошо бы если так, но у меня что-то не получается Что хранить в таком дереве? Вертексы явно не то, значит полигоны. Хорошо, разбили пр-во на иерархию кубов, каждый знает какие полигоны пересекает. Ну и дальше что?

Я склоняюсь к мысли "попробывать" незатейливый  регулярный буфер (точнее 3 буфера по каждой из осей). Каждый просто 2-мерный массив, элемент - пара(ы) float - расстояния по оси где луч протыкает поверхность 

[Dancing_on_water]

Хорошо бы если так, но у меня что-то не получается

Помниться кто-то жаловался на разжеванность доки Qt

Разжевываю. В довольно экзотических условиях ближайший вертекс не принадлежит ближайшей грани. Поэтому на первом этапе ищется ближайшая вершина. Задаем какой-то радиус D, с помощью R-дерева выбираем все вершины в кубе с центром в заданной точке и шириной грани D, если вершин много, сокращаем раза в два радиус, и так до тех пор, пока прямой перебор не станет эффективным. После того как нашли ближайший вертекс, проверяем грани, к которым он принадлежит.

[Igors]

В довольно экзотических условиях ближайший вертекс не принадлежит ближайшей грани.

Это ситуация самая рядовая. Пример: размер полигона напр 100x100. Точка находится на расстоянии 50 от одного вертекса и еще большем от других. Однако расстояние до полигона (поверхности) может быть сколь угодно малым, напр 0.1.

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

Продолжая пример выше - мы должны искать с D = 50. Возможно сотни и более др вертексов попадут в этот радиус захвата. Что-то Ваш поиск сильно похож на прямой перебор

[Dancing_on_water]

Форум по-ходу подглюкивает, в новых сообщениях он мне не тему не показал.

Это ситуация самая рядовая. Пример: размер полигона напр 100x100. Точка находится на расстоянии 50 от одного вертекса и еще большем от других. Однако расстояние до полигона (поверхности) может быть сколь угодно малым, напр 0.1.

Еще раз, я не говорю о том, что расстояние до  ближайшего вертекса = расстоянию до поверхности. Ближайшая вершина не принадлежит ближайшей грани только в случае близкому к самопересечению

Продолжая пример выше - мы должны искать с D = 50. Возможно сотни и более др вертексов попадут в этот радиус захвата. Что-то Ваш поиск сильно похож на прямой перебор

Если до ближайшего вертекса 50 попугаев, то в радиусе 50 попугаев не может быть сотни вертексов, если это не круг и не шар! (Да, срочно вышлите меня косяк употребляемой травы),

[Igors]

я не говорю о том, что расстояние до  ближайшего вертекса = расстоянию до поверхности. Ближайшая вершина не принадлежит ближайшей грани только в случае близкому к самопересечению

См аттач. Красный шарик ближе всего к левой стенке, однако ближайший вертекс принадлежит нижней.

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

Также не следует питать иллюзий что если мы уж нашли ближайший, то перебрать все его полигоны = достаточно быстро, ведь их немного. К сожалению это не всегда так, см. второй аттач. Эта проблема возникает и в др случаях (напр при построении дерева)

(Да, срочно вышлите меня косяк употребляемой травы),

Я ценю что Вы предложили свое решение (очень немногие способны на это). Но вот зазнайство лучше все-таки выключить 

[ssoft]

Есть библиотеки, специализирующиеся на геометрических вычислениях или ядра CAD систем.
Например, http://www.cgal.org или http://www.opencascade.org/.
Может там что-то есть полезное.

[xop]

А много поликов? А то может тупо перебором можно, тем более он хорошо параллелится?

[Dancing_on_water]

См аттач. Красный шарик ближе всего к левой стенке, однако ближайший вертекс принадлежит нижней.

По-моему он принадлежит как левой, нижней и задней стенке, не? (если конечно понимаем одно и тоже под вертексом)

Также не следует питать иллюзий что если мы уж нашли ближайший, то перебрать все его полигоны = достаточно быстро, ведь их немного. К сожалению это не всегда так, см. второй аттач. Эта проблема возникает и в др случаях (напр при построении дерева)

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

[Igors]

А много поликов? А то может тупо перебором можно, тем более он хорошо параллелится?

"поликов" - ну что за босяцкий жаргон?   Ну как пользователь сделает, он задает модель. Ожидается немного, обычно 2-5K, однако кратность вызова очень велика, трассируется по глубине (объему) и для каждой точки сначала надо найти расстояние до края. Конечно есть упрощенные режимы (spherpoid, box) но их возможности ограничены. Аттач показывает что будет без учета расстояния (слева)

Есть библиотеки, специализирующиеся на геометрических вычислениях или ядра CAD систем.
Например, http://www.cgal.org или http://www.opencascade.org/.
Может там что-то есть полезное.

Да, есть. Ведь знал же про CGAL но не догадался там посмотреть, спасибо! Есть там такое, откомпилировал пример и прошел по шагам. Дерево (ноды содержат полигоны), начинаем с первого попавшегося, потом подсекаем. К сожалению, это не та скорость что хотелось бы. Ну тоже результат, значит лучшего видимо нет. Придется удовлетвориться проекциями, хотя они и дают значительную ошибку.