正如 @jdub1581 所建议的,射线只是一个几何向量,因此为了找到与该向量相交的三角形列表,我们需要解决“线与平面相交”和“线在三角形边界内与平面相交”等问题。
假设我们有一个TriangleMesh
,我们有一个顶点列表和一个面列表。每个顶点有 3 个坐标,每个面有 3 个顶点(不考虑纹理、法线……)。为了简单起见,我们使用两个列表Point3D
来存储它们。
In this link有多种 3D 形状可供使用。让我们抢一个CuboidMesh
.
CuboidMesh cuboid = new CuboidMesh(10f,12f,4f,4);
这将为我们提供以下 3D 形状:
现在,如果我们查看网格,我们可以创建两个包含顶点和面的列表:
List<Point3D> vertices=Arrays.asList(new Point3D(5.0, 6.0, 2.0),
new Point3D(5.0, 6.0, 2.0), new Point3D(5.0, -6.0, 2.0), ...,
new Point3D(-1.875, -2.25, -2.0), new Point3D(-1.875, -1.5, -2.0));
List<Point3D> faces=Arrays.asList(new Point3D(0, 386, 388),
new Point3D(98, 387, 386.0), new Point3D(100, 388, 387), ...,
new Point3D(383, 1535, 1537), new Point3D(1536, 1537, 1535));
让我们在场景中添加一些 3D 点,一个原点和一个目标,两者都在全局坐标中,并定义向量的方向(标准化):
Point3D gloOrigin=new Point3D(4,-7,-4);
Point3D gloTarget=new Point3D(2,3,2);
Point3D direction=gloTarget.subtract(gloOrigin).normalize(); // -0.154,0.771,0.617
那么射线方程将是这样的:
r(t) = (4,-7,-4)+t*(-0.154,0.771,0.617)
如果我们在这两点之间添加一个细长的圆柱体,我们将得到射线的视觉表示:
边界框交点
第一步将检查光线是否与形状的边界框相交。在形状的局部坐标中,我们有 6 个面,由它们的法线给出,有 6 个中心:
Bounds locBounds = cuboid.getBoundsInLocal();
List<Point3D> normals=Arrays.asList(new Point3D(-1,0,0),new Point3D(1,0,0),
new Point3D(0,-1,0), new Point3D(0,1,0), new Point3D(0,0,-1), new Point3D(0,0,1));
List<Point3D> positions=Arrays.asList(new Point3D(locBounds.getMinX(),0,0),
new Point3D(locBounds.getMaxX(),0,0), new Point3D(0,locBounds.getMinY(),0),
new Point3D(0,locBounds.getMaxY(),0), new Point3D(0,0,locBounds.getMinZ()),
new Point3D(0,0,locBounds.getMaxZ()));
由于我们将在本地系统上工作,因此我们需要以下坐标中的原点:
Point3D gloOriginInLoc = cuboid.sceneToLocal(gloOrigin); // 4,-7,-4 since the box is centered in 0,0,0
现在,对于六个面中的任何一个,我们得到距离t
到随后的飞机link。然后我们可以检查该点是否属于盒子。
AtomicInteger counter = new AtomicInteger();
IntStream.range(0, 6).forEach(i->{
double d=-normals.get(i).dotProduct(positions.get(i));
double t=-(gloOriginInLoc.dotProduct(normals.get(i))+d)/
(gloDirection.dotProduct(normals.get(i)));
Point3D locInter=gloOriginInLoc.add(gloDirection.multiply(t));
if(locBounds.contains(locInter)){
counter.getAndIncrement();
}
});
If counter.get()>0
然后我们在射线和形状之间有一些交点,我们可以继续处理三角形。在此示例中,这些将是交点:(3.5,-4.5,-2) 和 (2.5,0.5,2)。
三角形相交
有多种算法可用于查找射线是否与网格的任何三角形相交,因此我们不需要重新发明轮子。
我用过的那个是来自托马斯·穆勒和本·特朗博尔。它将提供距离t
从原点到平面的坐标u,v
在给定交点的三角形内部。
一旦我们有了形状的局部坐标原点,并且知道了射线的方向,该算法的实现如下:
private final float EPS = 0.000001f;
public List<Point3D> getIntersections(Point3D origin, Point3D direction,
List<Point3D> points, List<Point3D> faces){
return faces.parallelStream().filter(f->{
// vertices indices
int p0=(int)f.getX();
int p1=(int)f.getY();
int p2=(int)f.getZ();
// vertices 3D coordinates
Point3D a = points.get(p0);
Point3D b = points.get(p1);
Point3D c = points.get(p2);
Point3D edge1 = b.substract(a);
Point3D edge2 = c.substract(a);
Point3D pvec=direction.crossProduct(edge2);
float det=edge1.dotProduct(pvec);
if(det<=-EPS || det>=EPS){
float inv_det=1f/det;
Point3D tvec=origin.substract(a);
float u = tvec.dotProduct(pvec)*inv_det;
if(u>=0f && u<=1f){
Point3D qvec=tvec.crossProduct(edge1);
float v = direction.dotProduct(qvec)*inv_det;
if(v>=0 && u+v<=1f){
float t = c.dotProduct(qvec)*inv_det;
System.out.println("t: "+t+", u: "+u+", v: "+v);
return true;
}
}
}
return false;
}).collect(Collectors.toList());
}
在此示例中,我们找到由以下顶点给出的三个面:(85, 1245, 1274)、(85, 1274, 1266) 和 (351, 1476, 1479)。
如果我们绘制这些面将会看到交集:
请注意,通过在形状的局部坐标系中执行所有操作,我们节省了将每个三角形转换到全局坐标系的操作。
这个算法确实很快。我在不到 40 毫秒的时间内测试了多达 300 万个三角形。
本次测试的所有代码均可用here.