| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Программирование игр, графики и искусственного интеллекта > принадлежность точки невыпуклому многограннику |
| Автор: tulebaev 28.2.2012, 17:57 |
| Прошу подсказать верное направление в решении следующей проблемы: Имеется оболочка в виде трехмерного невыпуклого многогранника, заданного плоскими многоугольными гранями. Требуется определить принадлежность некоторой произвольной точки внутренней области этой оболочки. В учебниках этот вопрос упомянут -- нужно выпустить произвольный луч из проверяемой точки и подсчитать четность/нечетность количества пересечений этого луча с оболочкой. Проблема в деталях -- как учитывать случай пересечения лучом ребра многоугольной грани или прохождение через вершину? Заранее спасибо. |
| Автор: Bitter 28.2.2012, 19:16 |
| В теории всегда все просто, да? А на деле начинаются проблемы. Честно говоря, по теме не отвечу, но если у вас задача проверки столкновения в игре, то чаще всего делают по другому - Ваш многогранник описывается кубом или сферой и после этого ищем столкновение с этим примитивом, что гораздо проще. Если же все таки нужна именно точная проверка пересечения многогранника, то могу посоветовать (опять же в теории просто...) разбить многогранник на выпуклые подобъекты, а затем проверить пересечение с одним из них (проверка с выпуклым довольно простая задача, но вот само разбиение - нет) |
| Автор: maxim1000 28.2.2012, 20:14 | ||
пустить луч в другом направлении  конечно, он опять может попасть на ребро, но можно реализовать алгоритм, который выберет "безопасное" направление (можно доказать, что оно всегда есть) |
| Автор: tulebaev 28.2.2012, 22:48 |
| Это не задача проверки на столкновения -- многогранник есть модель мишени, поэтому аппроксимировать неким примитивом не получится. В качестве "безопасного" направления годится среднее геометрическое всех лучей, соединящих проверяемую точку и вершины многогранника? Может кто-нибудь придумать контрпример? |
| Автор: maxim1000 29.2.2012, 09:39 | ||
куб и точка в центре даже если не в центре, её можно так сместить (например, по диагонали), что луч пройдёт через ребро |
| Автор: Bitter 1.3.2012, 12:24 |
| Зачем все это выдумывать? В чем собственно проблема с гранями и вершинами? Проверка на пересечение луча с плоскостью (а потом проверка на попадание в треугольник) это чистая математика. То есть я хочу сказать что математике все равно грань у вас или точка, если математически луч пересекает треугольник, то не важно проходит он через вершину или грань. Например если проверить сумму углов от точки к вершинам треугольника, то в случае если сумма равна 360, то точка внутри треугольника, если нет - то вне его. Тут все однозначно даже если точка совпадает с одной из вершин. Ну и все остальные алгоритмы работают так же. |
| Автор: tulebaev 1.3.2012, 12:40 |
| Проверка на пересечение луча с плоской гранью уже реализована -- действительно, сначала проверяем на предмет пересечения с плоскостью, содержащую грань, а потом идет проверка попадания точки пересечения внутрь многоугольника грани. Проблема в том, что прохождение луча через ребро или вершину формально учитывается как пересечение нескольких граней. |
