 |
|
Модераторы: Rickert |
 
|
|
принадлежность точки невыпуклому многограннику 
| tulebaev |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 17.2.2012 Репутация: нет Всего: нет |
Прошу подсказать верное направление в решении следующей проблемы:
Имеется оболочка в виде трехмерного невыпуклого многогранника, заданного плоскими многоугольными гранями. Требуется определить принадлежность некоторой произвольной точки внутренней области этой оболочки. В учебниках этот вопрос упомянут -- нужно выпустить произвольный луч из проверяемой точки и подсчитать четность/нечетность количества пересечений этого луча с оболочкой. Проблема в деталях -- как учитывать случай пересечения лучом ребра многоугольной грани или прохождение через вершину? Заранее спасибо. |
|||
|
||||
Загрузка ...
| Bitter |
|
|||
 Опытный лентяй  Профиль Группа: Завсегдатай Сообщений: 1209 Регистрация: 15.8.2004 Где: Харьков, Ukraine Репутация: 5 Всего: 27 |
В теории всегда все просто, да? А на деле начинаются проблемы.
Честно говоря, по теме не отвечу, но если у вас задача проверки столкновения в игре, то чаще всего делают по другому - Ваш многогранник описывается кубом или сферой и после этого ищем столкновение с этим примитивом, что гораздо проще. Если же все таки нужна именно точная проверка пересечения многогранника, то могу посоветовать (опять же в теории просто...) разбить многогранник на выпуклые подобъекты, а затем проверить пересечение с одним из них (проверка с выпуклым довольно простая задача, но вот само разбиение - нет) |
|||
|
||||
| maxim1000 |
|
|||
 Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 2 Всего: 110 |
пустить луч в другом направлении  конечно, он опять может попасть на ребро, но можно реализовать алгоритм, который выберет "безопасное" направление (можно доказать, что оно всегда есть) -------------------- qqq |
|||
|
||||
| tulebaev |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 17.2.2012 Репутация: нет Всего: нет |
Это не задача проверки на столкновения -- многогранник есть модель мишени, поэтому аппроксимировать неким примитивом не получится.
В качестве "безопасного" направления годится среднее геометрическое всех лучей, соединящих проверяемую точку и вершины многогранника? Может кто-нибудь придумать контрпример? |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 2 Всего: 110 |
куб и точка в центре даже если не в центре, её можно так сместить (например, по диагонали), что луч пройдёт через ребро Это сообщение отредактировал(а) maxim1000 - 29.2.2012, 09:40 -------------------- qqq |
|||
|
||||
| Bitter |
|
|||
|
Опытный лентяй Профиль Группа: Завсегдатай Сообщений: 1209 Регистрация: 15.8.2004 Где: Харьков, Ukraine Репутация: 5 Всего: 27 |
Зачем все это выдумывать? В чем собственно проблема с гранями и вершинами? Проверка на пересечение луча с плоскостью (а потом проверка на попадание в треугольник) это чистая математика. То есть я хочу сказать что математике все равно грань у вас или точка, если математически луч пересекает треугольник, то не важно проходит он через вершину или грань.
Например если проверить сумму углов от точки к вершинам треугольника, то в случае если сумма равна 360, то точка внутри треугольника, если нет - то вне его. Тут все однозначно даже если точка совпадает с одной из вершин. Ну и все остальные алгоритмы работают так же. |
|||
|
||||
| tulebaev |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 17.2.2012 Репутация: нет Всего: нет |
Проверка на пересечение луча с плоской гранью уже реализована -- действительно, сначала проверяем на предмет пересечения с плоскостью, содержащую грань, а потом идет проверка попадания точки пересечения внутрь многоугольника грани.
Проблема в том, что прохождение луча через ребро или вершину формально учитывается как пересечение нескольких граней. |
|||
|
||||
|
|
| Правила форума "Программирование игр, графики и искуственного интеллекта" | |
|
|
НА ЗЛОБУ ДНЯ: Дорогие посетители, прошу обратить внимание что новые темы касающиеся новых вопросов создаются кнопкой "Новая тема" а не "Ответить"! Любые оффтопиковые вопросы, заданные в текущих тематических темах будут удалены а их авторы, при рецедиве, забанены.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Rickert. |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Программирование игр, графики и искусственного интеллекта | Следующая тема » |
[ Время генерации скрипта: 0.1091 ] [ Использовано запросов: 20 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |