Плоскость для пересечения с алгоритмом местности

Question

У меня есть ландшафт, который представлен элементами и координатами (это просто список сетки), и у меня есть плоскость.

Как найти пересечение между самолетом и местностью? Должен ли я просто разбить плоскость на список линий, а затем использовать технику приведения лучей или другую технику, чтобы вычислить список пересечений и соединить их вместе? Или есть другие способы сделать?

Этот вопрос является частным случаем моего вопроса здесь, в котором я фактически дискретизировал плоскость, разбив ее на множество линий, и нашел точки пересечения, чтобы получить линии, где плоскость пересекаются с местностью, но мне действительно интересно, есть ли лучший способ.

Answer 1

1. определить плоскость, используя ее неявное уравнение. Найдите a, b, c и d так, чтобы ax + by + cz + d = 0 для всех (x, y, z) на плоскости
2. Пройдите через каждый квадрат, который определяет сегмент вашей местности. Интерпретировать квадрат как два отдельных треугольника
3. Для каждой вершины v1 = (x1, y1, z1), v2 = (x2, y2, z2), v3 = (x3, y3, z3) треугольника определите, на какой стороне плоскости он лежит:
   • l1 = a x1 + b y1 + c * z1 + d
   • l2 = a x2 + b y2 + c * z2 + d
   • l3 = a x3 + b y3 + c * z3 + d
4. Теперь есть два варианта.
   • либо l1, l2, l3 все> 0, либо l1, l2, l3 все <0 - в этом случае плоскость не пересекает треугольник, и вам нечего делать. </li>
   • или два значения l положительные / отрицательные, а третье противоположное, например, l1> 0, l2> 0 и l3 <0 - тогда ребра треугольника v1-v3 и v2-v3 пересекаются </li>
5. пересечение кромки и плоскости легко рассчитать. Предполагая, что ребро v1-v2 пересекается:
   • xi = (x1 * l1 - x2 * l2) / (l1 - l2)
   • yi = (y1 * l1 - y2 * l2) / (l1 - l2)
   • zi = (z1 * l1 - z2 * l2) / (l1 - l2)

Таким образом, вы получите список ребер, которые соответствуют пересечению плоскости с вашей местностью. Это медленный метод, но его легко объяснить ... если вы хотите ускорить его, вам нужно будет использовать октреи или аналогичную структуру данных, чтобы ограничить количество точечных / плоскостных тестов, которые вам нужно выполнить.