Не могли бы помочь Барицентрические координаты?
Это может быть. Это немного зависит от того, насколько сильно оптимизирован ваш не-барицентрический код, но я бы сказал, что с использованием барицентрических координат, по крайней мере, проще писать код, который является как поддерживаемым, так и работоспособным.
Насколько я могу судить, вся ваша установка по существу 2d, с точкой E и направлением d, содержащимся в плоскости, охватываемой A,B,C. Таким образом, у вас есть
E = aE*A + bE*B + cE*C with aE+bE+cE=1
d = ad*A + bd*B + cd*C with ad+bd+cd=0
Теперь у вас есть две подзадачи:
- Как получить барицентрические координаты эффективно
- Как найти точку пересечения
Давайте начнем с последнего , Вы просто добавляете к E столько кратных d, пока координата c не станет равной нулю.
P = E - (cE/cd)*d
В зависимости от настроек, вы также может быть штраф с использованием однородных координат, в этом случае вы могли бы написать это как P = cd*E - cE*d.
Каким образом вы поворачиваете x,y,z Координаты d и E в барицентрический a,b,c? Ну, это всего лишь система линейных уравнений. Вы можете использовать обратную матрицу, образованную векторами A,B,C. Опять же, если вы имеете дело с однородными координатами, вы можете использовать вспомогательный элемент вместо обратного.
Вот однородный подход прописано:
aE = (By*Cz-Bz*Cy)*Ex + (Bz*Cx-Bx*Cz)*Ey + (Bx*Cy-By*Cx)*Ez
bE = (Cy*Az-Cz*Ay)*Ex + (Cz*Ax-Cx*Az)*Ey + (Cx*Ay-Cy*Ax)*Ez
cE = (Ay*Bz-Az*By)*Ex + (Az*Bx-Ax*Bz)*Ey + (Ax*By-Ay*Bx)*Ez
ad = (By*Cz-Bz*Cy)*dx + (Bz*Cx-Bx*Cz)*dy + (Bx*Cy-By*Cx)*dz
bd = (Cy*Az-Cz*Ay)*dx + (Cz*Ax-Cx*Az)*dy + (Cx*Ay-Cy*Ax)*dz
cd = (Ay*Bz-Az*By)*dx + (Az*Bx-Ax*Bz)*dy + (Ax*By-Ay*Bx)*dz
aP = cd*aE - cE*ad
bP = cd*bE - cE*bd
Px = aP/(aP+bP)*Ax + bP/(aP+bP)*Bx
Py = aP/(aP+bP)*Ay + bP/(aP+bP)*By
Pz = aP/(aP+bP)*Az + bP/(aP+bP)*Bz
Первые три строки преобразуют E в барицентрических координаты, следующие три строки d. Затем мы вычисляем барицентрические координаты P и возвращаем их обратно в декартовы координаты. На этом этапе мы также дегомогенизируем их, т. Е. Делим на сумму барицентрических координат.
В целом, здесь имеется большое количество кода. Вы можете уменьшить количество операций, перемещая общие выражения в выделенные переменные, особенно если ваш компилятор не делает этого для вас. Одно из преимуществ заключается в том, что вам не нужны никакие дивизии, кроме последней дегомогенизации, т. Е. Деление на (a+b). Если вы вычислите 1/(a+b) один раз, вы можете сделать это, но только одно подразделение, что хорошо для производительности.
Однако реальная выгода от приведенного выше кода, скорее всего, позволяет сделать много приятных вещей с помощью барицентрических координат, которые вы не могли бы легко сделать с другими системами координат. Например, если вы хотите проверить, попадает ли луч в строку AB на сегмент линии или где-то вне треугольника, просто проверьте, aP*bP > 0.
Как и в [math-stackexchange] [1], сложность вычисления этих трех тестов пересечения в O (1). Я сомневаюсь, что (2) изменение системы координат вам очень поможет. (1) Более интересно то, что вы подразумеваете под: «Я должен сделать это для большого количества треугольников». Возможно, вы можете добавить остальную проблему, с которой имеете дело, чтобы упростить предоставление рекомендаций. [1]: http://math.stackexchange.com/questions/2139740/fast-3d-algorithm-to-find-a-ray-triangle-edge-intersection/2140591#2140591 – gue
Вы должны сгруппировать свои треугольники пространственно и проверять только группы рядом с вашим лучом ... в направлении камеры Z-порядок – Spektre
Как я его читал, вы, по сути, в настройке 2d: все ваши точки, кажется, находятся в одной плоскости. Это правильно? – MvG