Пересечение треугольник-куб / воксель
Каков наилучший алгоритм для определения того, пересекается ли треугольник с вокселем / кубом в трехмерном пространстве? У меня есть этот источник, написанный на C: http://tog.acm.org/resources/GraphicsGems/gemsiii/triangleCube.c . Я пытался реорганизовать и преобразовать этот код в C ++, но я понял, что действительно не знаю, что происходит. Кроме того, в комментариях говорится, что пересечение треугольника сравнивается с единичным кубом, однако я не могу найти способ расширить алгоритм для работы с любым произвольным кубом / вокселем.
Существует ли более четкая реализация (предпочтительно в C ++) обнаружения пересечения треугольник-куб? Если нет, то каков будет лучший способ расширить код C для работы с любым произвольным кубом?
заранее спасибо
Решение
Простой алгоритм будет:
- Рассчитайте плоскость, на которой лежит треугольник.
- Найдите пересечение между этой плоскостью и кубом (если есть).
- Если пересечения нет, то проблема решена.
- В противном случае найдите прямую линию, которая проходит через все ребра треугольников.
- Для каждой линии: если пересечение находится «снаружи», то пересечение отсутствует.
- В противном случае есть пересечение.
Если ваши критерии для «лучшего» алгоритма просты, то это будет хорошим. Если вы ищете производительность, возможно, есть и более быстрые.
Вы также можете попробовать посмотреть код, размещенный на:
http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/
Другие решения
Других решений пока нет …