Как проверить попадает точка в сложную трехмерную фигуру? Интересует сам алгоритм

Принятый ответ

darkowlom, хм, действительно, есть такое. Но тут надо действительно разбивать на баунд боксы
и это поможет, а потом уже уточнять
2
29
9 лет назад
Отредактирован alexprey
2
1 вариант:
Разбиение сложной фигуры на простые примитивы (кубы и сферы) проверять по простым формулам.
2 вариант.
Брать полигоны, вычислять вектор направления. Проецировать этот вектор на нормаль полгона и если получается отрицательная проекция, значит точка лежит под этим полигоном. Точка будет находится внутри сложной фигуры, если она будет размещаться под всеми пролигонами одновременно
0
24
9 лет назад
Отредактирован prog
0
Если обобщить, то выглядит так
  • перебираем все фигуры, в которые может попасть точка
  • отсекаем по баундинг боксам и другим простым критериям столько фигур, сколько получится
  • для оставшихся фигур прогоняем более дорогие детальные проверки, зависящие от того, что именно подразумевается под "попаданием точки в фигуру"
если задача определить, например, клик мышкой по объекту это одно, а если есть координаты точки в трехмерном пространстве и надо понять находится ли она внутри объекта это совсем другое
2
34
9 лет назад
2
Можно рендернуть 3d объект в 2d текстуру (текстура глубины), где белым цветом будет отображена модель, а черным прозрачность. Затем просто проверить цвет пикселя в нужной точке. Это конечно если тебе нужно проверить попадание 2D точки в 3D модель (например выбор юнита в стратегии).
Подсветка объектов под курсором реализуется путем рендеринга выделяемого объекта в отдельную текстуру. Шейдер при этом используется простейший – вывод единицы в альфа канал рендер таргета, и цвета выделения в rgb каналы.
--
Если нужно проверить попадание 3D точки в 3D модель, то тогда стоит использовать raytrace (raycast). Большинство движков умеют это делать.
Загруженные файлы
0
24
9 лет назад
0
Я не точно описал задание, это нужно реализовать в спартанских условиях, то есть, у меня есть голый язык программирования, набор полигонов и библиотека математических функций, на этом доступный инструментарий ограничен. Потому рейтрейс не подходит
Брать полигоны, вычислять вектор направления
Можно подробней как вычисляется этот вектор? Или подскажи литературу где об этом можно почитать
2
29
9 лет назад
2
// V1, V2, V3 - точки полигона
// vN - нормаль полигона
var vEnd = new Vector3(...); // точка проверки
var vStart = (V1 + V2 + V3) / 3.0f; // центральная точка
var vDir = vEnd - vStart
var result = Vector3.Dot(vDir, vN);
if (result < 0.0f) {
	// Внутри
}
0
24
9 лет назад
0
darkowlom, можешь немного уточнить задачу? тебе мауспик нужен (точка на экране монитора) или точка в трехмерном пространстве? в зависимости от этого нужны различные алгоритмы.
0
24
9 лет назад
Отредактирован darkowlom
0
тебе мауспик нужен
Трехмерное пространство, у меня даже визуализации нету.
Метод предложенный алекспреем я пока не опробовал,но не будет ли такого бага, когда у сложной фигуры, напрмер человека прикрывшего лицо рукой, точка находится как раз внутри руки, и получается относительно лица и тела она вне фигуры, а результатом проверки должно быть попадание в фигуру, может я ошибаюсь, но по моему точка не будет сразу под всеми полигонами. Интересует проверка цельного объекта не деленного на баунд боксы. Или без деления на них не обойтись? делается для интереса, так что оптимизация нагрузки на систему не важна
0
29
9 лет назад
0
darkowlom, хм, действительно, есть такое. Но тут надо действительно разбивать на баунд боксы
и это поможет, а потом уже уточнять
Принятый ответ
0
34
9 лет назад
0
если тебе нужно попадание только в грудь, но не учитывая руки или лицо то делить нужно на баунд боксы. С другой стороны если нужно учитывать точку внутри руки когда она находится "по швам", и на уровне торса, но при этом не учиывать её когда она напротив лица, то стоит проверить модель на bbox и попадание этой точки просто в квадрат модели, а потом уже проверять по полигонам.
0
28
9 лет назад
0
точка неподвижна?
или она движется по прямой
или она движется по кривой?
допустима ли погрешность?
0
24
9 лет назад
0
H, я не это имел ввиду, просто по формуле алекса выходит что точка внутри руки у лица не будут учитываться , так они не внутри фигуры. Буду пользоваться баундбоксами значит. Спасибо
2
9
9 лет назад
2
Оптимизация не важна? ок, есть один драконовский способ )
Строим паралелипипед , чтобы он полностью вмещал модель(можно по самым далеким от центра фигуры точкам).
Затем "пускаем луч" от нашей точки(которая внутри или снаружи) , скажем, в направлении Ох и каждую точку луча(кроме первой) проверяем на нахождение в составе поверхности хотя-бы одного полигона, увелечиваем переменную кол-ва пересечений луча с фигурой . Перебираем точки, пока очередная не окажется вне параллелипипеда .
Если число пересечений четно - снаружи , нечетно - внутри.
Проблема может быть, когда луч скрещивается с поверхностью, а не пронзает её, тогда надо проверять очередную точку и если она не принадлежит той же поверхности, то луч скрещивается и увеличивать переменную не надо.
Совершенно неоптимизированный , но 100% работающий метод.
0
29
9 лет назад
0
GeneralElConsul, это RayTracing - очень годный вариант, так-то)
0
9
9 лет назад
0
Его можно оптимизировать - вначале сопоставить каждому полигону его самую большую по координате Х точку(из точек, которыми он задается).
А затем при проверке вхождения очередной точки в поверхность полигона перед этим
проверить, меньше ли Х крайней точки дальнего полигона координаты Х точки луча.
Если так, то полигон остался сзади точки по оси Ох и нет нужды вызывать функцию для проверки вхождения в поверхность данного полигона. А лучше вообще его вышвырнуть из коллекции.
0
26
9 лет назад
0
Можно выпускать с точки луч в сторону центра фигуры. Если количество пересечений будет четное - точка вне фигуры, если нечетное - внутри.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.