这是我在stackoverflow上的第一个问题，所以我希望我做对了。对于 java 项目，我需要使用八叉树进行光线跟踪。我已经创建了一个简单的八叉树（没有邻居信息或其他东西）并将对象网格的三角形分类到八叉树的 AABB 中。现在我想为每条光线轻松遍历树。（这应该很容易，因为完成这个项目的时间很短）。基本算法如下：
- 从第一个节点开始
- 如果这个节点被命中，记住交点在排序列表中的位置
- 如果此节点有子节点，检查子框是否被击中并将每个交点写入排序列表
- 从最近的交点的子框开始
- 如果这个盒子也有孩子，请参阅 4)
- 如果一个节点没有任何子节点，请检查此框中的每个三角形与射线
- 如果击中三角形，则获取三角形的颜色（带有阴影和所有内容）并将其绘制在屏幕上
不幸的是，我当前的实现似乎在交集计算（ray vs ABBB）中有一个“错误”。我检查是否击中了 AABB 的任何一侧并记住最近的 ip（距射线原点的最小距离）。
这是我的 BoundingBox 类中此函数的代码：
public HitResult intersects6(Ray ray) {
double t;
Vec3d ip = new Vec3d();
HitResult finalHitResult = null;
// front xy
if (Math.abs(ray.direction.z) > Helper.EPSYLON) {
t = (vmax.z - ray.origin.z) / ray.direction.z;
ip.x = ray.origin.x + t * ray.direction.x;
ip.y = ray.origin.y + t * ray.direction.y;
ip.z = vmax.z;
if ((ip.x >= vmin.x) && (ip.x <= vmax.x) && (ip.y >= vmin.y) && (ip.y <= vmax.y)) {
// here is an intersection
double distance = Vec3d.distance(ray.origin, ip);
finalHitResult = new HitResult(ip, distance);
}
}
// back xy
if (Math.abs(ray.direction.z) > Helper.EPSYLON) {
t = (vmin.z + ray.origin.z) / -ray.direction.z;
ip.x = ray.origin.x + t * ray.direction.x;
ip.y = ray.origin.y + t * ray.direction.y;
ip.z = vmin.z;
if ((ip.x >= vmin.x) && (ip.x <= vmax.x) && (ip.y >= vmin.y) && (ip.y <= vmax.y)) {
double distance = Vec3d.distance(ray.origin, ip);
if (finalHitResult!= null) {
if(distance < finalHitResult.distance)
finalHitResult.distance = distance;
finalHitResult.point = ip;
}
else
finalHitResult = new HitResult(ip, distance);
}
}
// Side Right
if (Math.abs(ray.direction.x) > Helper.EPSYLON) {
t = (vmax.x - ray.origin.x) / ray.direction.x;
ip.y = ray.origin.y + t * ray.direction.y;
ip.z = ray.origin.z + t * ray.direction.z;
ip.x = vmax.x;
if ((ip.y >= vmin.y) && (ip.y <= vmax.y) && (ip.z >= vmin.z) && (ip.z <= vmax.z)) {
double distance = Vec3d.distance(ray.origin, ip);
if (finalHitResult!= null) {
if(distance < finalHitResult.distance)
finalHitResult.distance = distance;
finalHitResult.point = ip;
}
else
finalHitResult = new HitResult(ip, distance);
}
}
// Side Left
if (Math.abs(ray.direction.x) > Helper.EPSYLON) {
t = (vmin.x + ray.origin.x) / -ray.direction.x;
ip.y = ray.origin.y + t * ray.direction.y;
ip.z = ray.origin.z + t * ray.direction.z;
ip.x = vmin.x;
if ((ip.y >= vmin.y) && (ip.y <= vmax.y) && (ip.z >= vmin.z) && (ip.z <= vmax.z)) {
double distance = Vec3d.distance(ray.origin, ip);
if (finalHitResult!= null) {
if(distance < finalHitResult.distance)
finalHitResult.distance = distance;
finalHitResult.point = ip;
}
else
finalHitResult = new HitResult(ip, distance);
}
}
// Top
if (Math.abs(ray.direction.y) > Helper.EPSYLON) {
t = (vmax.y - ray.origin.y) / ray.direction.y;
ip.x = ray.origin.x + t * ray.direction.x;
ip.z = ray.origin.z + t * ray.direction.z;
ip.y = vmax.y;
if ((ip.x >= vmin.x) && (ip.x <= vmax.x) && (ip.z >= vmin.z) && (ip.z <= vmax.z)) {
double distance = Vec3d.distance(ray.origin, ip);
if (finalHitResult!= null) {
if(distance < finalHitResult.distance)
finalHitResult.distance = distance;
finalHitResult.point = ip;
}
else
finalHitResult = new HitResult(ip, distance);
}
}
// Bottom
if (Math.abs(ray.direction.y) > Helper.EPSYLON) {
t = (vmin.y + ray.origin.y) / -ray.direction.y;
ip.x = ray.origin.x + t * ray.direction.x;
ip.z = ray.origin.z + t * ray.direction.z;
ip.y = vmin.y;
if ((ip.x >= vmin.x) && (ip.x <= vmax.x) && (ip.z >= vmin.z) && (ip.z <= vmax.z)) {
double distance = Vec3d.distance(ray.origin, ip);
if (finalHitResult!= null) {
if(distance < finalHitResult.distance)
finalHitResult.distance = distance;
finalHitResult.point = ip;
}
else
finalHitResult = new HitResult(ip, distance);
}
}
return finalHitResult;
我想这不是最好的方法。在我的第一个实现中，我只使用了 t 值并比较了它们（以找到我接下来要访问的框）。但问题是一样的。找不到某些交叉点。
我还在这里检查了交集方法： https ://code.google.com/p/3d-workspace/source/browse/trunk/MathLibrary/Bounding/BoundingBox.cpp?r=17 但我看不到如何获取与此代码（甚至任何 t 值）的交点。此外，我测试了此处描述的平板方法：http: //tavianator.com/2011/05/fast-branchless-raybounding-box-intersections/ 但这似乎也错过了一些交叉点，我不知道为什么：
public double[] intersects3(Ray ray) {
double Tnear = -1e30;
double Tfar = 1e30;
// First, check slab in X.
if (Math.abs(ray.direction.x) < 0.0) {
// Ray is parallel to X, but starts outside. Fail.
if (ray.origin.x < vmin.x || ray.origin.x > vmax.x) {
return null;
}
} else {
double Ta = ((vmin.x - ray.origin.x) / ray.direction.x), Tb = (vmax.x - ray.origin.x) / ray.direction.x;
double T1 = Math.min(Ta, Tb);
double T2 = Math.max(Ta, Tb);
if (T1 > Tnear)
Tnear = T1;
if (T2 < Tfar)
Tfar = T2;
if (Tnear > Tfar)
return null;
if (Tfar < 0)
return null;
}
// Then check slab in Y.
if (Math.abs(ray.direction.y) < 0.0) {
// Ray is parallel to X, but starts outside. Fail.
if (ray.origin.y < vmin.y || ray.origin.y > vmax.y) {
return null;
}
} else {
double Ta = (vmin.y - ray.origin.y) / ray.direction.y, Tb = (vmax.y - ray.origin.y) / ray.direction.y;
double T1 = Math.min(Ta, Tb);
double T2 = Math.max(Ta, Tb);
if (T1 > Tnear)
Tnear = T1;
if (T2 < Tfar)
Tfar = T2;
if (Tnear > Tfar)
return null;
if (Tfar < 0)
return null;
}
// Then check slab in Z.
if (Math.abs(ray.direction.z) < 0.0) {
// Ray is parallel to X, but starts outside. Fail.
if (ray.origin.z < vmin.z || ray.origin.z > vmax.z) {
return null;
}
} else {
double Ta = (vmin.z - ray.origin.z) / ray.direction.z, Tb = (vmax.z - ray.origin.z) / ray.direction.z;
double T1 = Math.min(Ta, Tb);
double T2 = Math.max(Ta, Tb);
if (T1 > Tnear)
Tnear = T1;
if (T2 < Tfar)
Tfar = T2;
if (Tnear > Tfar)
return null;
if (Tfar < 0)
return null;
}
// If we have survived this far, the test passed.
return new double[] { Tnear, Tfar };
}
也许我对光线追踪太愚蠢了。
但我的实际问题是：
是否可以使用 t 值来比较哪个框的交点最近？如果是，我怎样才能得到这个 t 值？或者我该怎么做才能使第一个代码被剪断？（到目前为止，我对任何可行的解决方案都很满意，即使这个解决方案很慢）
提前致谢。