Я пытаюсь понять, как реализовать дерево KD.
На странице 322 «Обнаружение столкновений в реальном времени» Эриксона
Текстовый раздел включен ниже на случай, если предварительный просмотр книги Google не позволяет увидеть его во время нажатия на ссылку.
Соответствующий раздел:
Основная идея пересечения луча или направленного отрезка линии с деревом kd проста. Линия пересекается с плоскостью разбиения узла, и вычисляется значение t пересечения. Если t находится в интервале линии, 0 <= t <= tmax, линия пересекает плоскость, и оба потомка дерева рекурсивно спускаются. Если нет, рекурсивно посещается только сторона, содержащая начало сегмента.
Итак, вот что у меня есть: ( откройте изображение в новой вкладке, если вы не видите надписи)
Логическое дерево
Здесь оранжевый луч проходит через трехмерную сцену. Х представляют пересечение с плоскостью. Слева луч попадает:
- Передняя грань окружающего куба сцены,
- (1) плоскость расщепления
- (2.2) плоскость расщепления
- Правая сторона вмещающего куба сцены
Но вот что произойдет, наивно следуя базовому описанию Эриксона выше:
- Испытание на расщепление плоскости (1). Луч попадает в плоскость расщепления (1), поэтому левый и правый дочерние элементы плоскости расщепления (1) включаются в следующий тест.
- Испытание на плоскость расщепления (2.1). Рэй на самом деле попадает в этот самолет (далеко направо), поэтому оба ребенка включаются в следующий уровень тестов. (Это нелогично - в последующие тесты следует включать не только нижний узел)
Кто-нибудь может описать, что происходит, когда оранжевый луч проходит через сцену правильно?
источник