Добрый день

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

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

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

Спасибо

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

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

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

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

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

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

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

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

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

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

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

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

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

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