[Из песочницы] Алгоритм «пересекается ли отрезок с треугольником в 3D: да/нет»
Предыстория
В 3D имеется объемная фигура с триангулированной поверхностью и требуется выяснить: находится ли некоторая данная точка внутри объема или снаружи… Вот если бы речь шла об аналитически заданной поверхности или об объединении и пересечении таких поверхностей, то всё просто — втыкаем нашу точку в аналитическую функцию поверхности f (x,y,z) = 0 и смотрим: ноль или не ноль? Если больше нуля, то точка снаружи (куда градиент показывает), а если меньше нуля, то внутри. Да и с триангулированной поверхностью тоже особой возни нет, просто чуть дольше:
— выбираем тестовую точку, которая заведомо лежит например снаружи,
— соединяем ее отрезком с некоторой данной точкой (про которую мы хотим узнать, внутри она или снаружи)
— и перебираем все треугольники, считаем пересечения: пересечений четное число — значит точка снаружи (как и тестовая, выбранная нами), нечетное — внутри.
Осталось только сообразить, как пересечения c треугольниками фиксировать. И давайте немного договоримся с терминологией: пересечением будем называть наше рабоче-крестьянское пересечение, когда отрезок уверенно пронзает треугольник, а не трусливо по-интеллигентски его всего лишь касается).
Читать дальше →
