java - 创建一个函数来查找任意线段和正方形的交集

Question

我正在用 Java 开发游戏引擎，但遇到了问题。

我正在尝试将我的世界空间对象投影到 View 空间中。我有一个定义了假想顶点的视锥体(我们称之为视锥体的“眼睛”。如果它的顶部没有被“切断”，它只是视锥体的边缘会相遇的地方。我的对象的所有顶点都将通过线段连接到眼睛。这条线与视锥体小端相交的地方是屏幕上显示的对象的 x 和 y 坐标。

我的问题是确定它们与平截头体小端相交的位置。我已经考虑过这个问题并进行了大量研究，但我找不到任何关于我应该如何做的资源。

我现在的类(class)如下:

class Point--a simple class which basically contains x-y-z variables.I also use the Point class to represent vectors.

class Frustum, which is basically eight points to make a shape like a squashed square.

class Triangle, which is basically three Points. It has several methods to do things with those points.

我还有几个经过彻底测试的功能:

double Distance_Between(Point p1, Point p2)--Calculates the distance between two 3d points

Point GetNormalVector(Point p1, Point p2, Point p3)--Gets the normal vector of three coplanar points.

void NormalizeVector(Point p)--Normalizes a vector

double GetDotProduct(Point p1, Point p2)--Gets the Dot Product of two points.

int[] GetSharedSide(Triangle t1, Triangle t2)--Gets the shared side of two Triangles.

void MovePointAlongVector(Point point, Point direction, float distance)--Moves a given Point along a given vector a given amount.

如果您能通过现有功能找到答案，那就太好了，但我可以添加更多实用功能。

这对于游戏引擎来说非常重要——可以说这个功能是最重要的。我想这将需要一些几何学和三角学。这将是完美的，因为我最近在高中就读过这两门课!

Answer 1

您确实正在考虑投影变换。

考虑当眼睛位于原点并且平截头体的方形末端位于 x=1 时的情况飞机。如果我们采取这一点(x, y, z)从眼睛到该点的线上的点将具有 (a x, a y, a z) 的形式。现在如果a = 1/x这给出了点(1, y/x, z/x) .

解决这个问题最简单的方法是建立一个转换库。因此，您可以应用旋转和其他变换(以矩阵表示)。使用 4 x 4 矩阵是最简单的，因为这允许将翻译表示为矩阵。使用此库，您可以变换场景，使眼睛位于原点，并且平截头体末端的法线沿着基轴之一。

更复杂的方法是一般的线段平面相交。要执行此操作，请计算平面的法线 n，并找到平面到原点的距离，取 d = P . n使用点积。使用从 A 点到 B 点的线段计算两个点积 d1 = A . n和d2= B . n 。对于与 d1 和 d2 相交的线段，其中一个应大于 d，另一个应小于 d。您现在可以使用线性插值来查找两者之间的点。线段上的点由

给出

m A + (1 - m) B

我们希望它与法线的点积为 d .

(m A + (1 - m) B) . n = d
m A . n + (1 - m) B . n = d
m d1 + (1 - m) d2 = d
m (d1 - d2) + d2 = d
m = (d - d2) / (d1 - d2)

这给出了参数，然后可以使用该参数来查找线段上的交点。

许多库都有 lerp 函数，可以进行线性插值。