Как найти кубики прошли через треугольником

Question

Учитывая треугольник с Vertice A, B и C в 3D мире, и ось выровненных ограничивающая кубовидной с длина * ширина * высота = й * мкр * LD (n, m, l - целые числа, а d - float), содержащие его, разбивают кубик на n * m * l кубики и как найти кубы, проходящие через треугольник?

Существует множество алгоритмов для определения пересечения треугольника и куба. Петля по всем кубам проблема может быть решена. Однако сложность этого подхода O (n * m * l) или O (n^3). Существует ли подход со сложностью O (n^2) или даже O (nlogn)?

Answer 1

Вы не можете улучшить O (n m l) по следующей причине: выберите m = 1 и l = 1. Тогда у вас есть планарное расположение n кубов, и ваш треугольник может пересекать все. Если вам нужно сообщить о каждом пересечении куба, вам нужно будет сообщить все n кубов.

Но, очевидно, это всего лишь недостаток вашего заявления о проблеме. То, что вы должны спросить, это ситуация, когда n = m = l. Итак, теперь у вас есть n x n x n множество кубов, и один треугольник может пересекать их только O (n^2).

В этом случае, конечно, треугольник может пересекать Ω (n^2) кубики, поэтому нельзя улучшить квадратичную сложность. Это исключает O (n log n).

Итак, возникает вопрос: существует ли подкубический алгоритм для определения кубов O (n^2), пересекаемых треугольником? (И можно заменить «треугольник» на «плоскость».)

Я считаю, что ответ Да. Один из способов состоит в том, чтобы построить окт., представляющий кубы. Поиски «вокселов» и «пересечений октетов» могут привести вас к к явным алгоритмам.