八叉树光线投射/光线跟踪 - 没有递归的最佳光线/叶子交叉点
3Da*_*ave 5 xna hlsl octree raycasting
任何人都可以提供一个简短而甜蜜的解释(或建议一个很好的教程),如何在没有递归的情况下对一个体素八叉树投射光线？
我有一个复杂的模型烤成八叉树,我需要找到与光线相交的最佳/最接近的叶子.标准的向下钻取迭代树步骤:
- 抓住根节点
- 检查交叉点
- 没有？出口
- 是？找到与最接近光线原点的光线相交的子项
- 循环直到我到达树叶或退出树
始终返回叶子,但在树存储地形的实例中,与光线原点最接近的节点不一定包含最匹配的叶子.这并不令人惊讶 - 使用这种方法不会对更远节点中的较高对象进行测试.
我可以通过查找树中所有相交的叶子,按距离排序并选择最接近光线的位置来递归地执行此操作.但是,这很慢并且需要递归.
我已经阅读了一些关于使用Bresenham线算法来遍历树的一些内容,这似乎要求每个节点都包含指向相邻邻居的指针,但我不清楚如何以有用的方式实现它.
有什么建议？我可以使用固定长度的数组或带有每个潜在堆栈条目的元素的结构来伪造HLSL中的堆栈,但是对于它的内存要求可能会变得非常大.
救命.
我已经成功地得到这个主要是使用3D DDA算法和邻居节点的指针工作.
我还在制作一些bug,但是这里的C#版似乎有效.当它到达第一片叶子时会停止,但这并不是完全必要的.
/// <param name="ray"></param>
public OctreeNode DDATraverse(Ray ray)
{
float tmin;
float tmax;
/// make sure the ray hits the bounding box of the root octree node
if (!RayCasting.HitsBox(ray, root.BoundingBox.Min, root.BoundingBox.Max, out tmin, out tmax))
return null;
/// move the ray position to the point of intersection with the bounding volume.
ray.Position += ray.Direction * MathHelper.Min(tmin, tmax);// intersectionDistance.Value;
/// get integer cell coordinates for the given position
/// leafSize is a Vector3 containing the dimensions of a leaf node in world-space coordinates
/// cellCount is a Vector3 containng the number of cells in each direction, or the size of the tree root divided by leafSize.
var cell = Vector3.Min(((ray.Position - boundingBox.Min) / leafSize).Truncate(), cellCount - Vector3.One);
/// get the Vector3 where of the intersection point relative to the tree root.
var pos = ray.Position - boundingBox.Min;
/// get the bounds of the starting cell - leaf size offset by "pos"
var cellBounds = GetCellBounds(cell);
/// calculate initial t values for each axis based on the sign of the ray.
/// See any good 3D DDA tutorial for an explanation of t, but it basically tells us the
/// distance we have to move from ray.Position along ray.Direction to reach the next cell boundary
/// This calculates t values for both positive and negative ray directions.
var tMaxNeg = (cellBounds.Min - ray.Position) / ray.Direction;
var tMaxPos = (cellBounds.Max - ray.Position) / ray.Direction;
/// calculate t values within the cell along the ray direction.
/// This may be buggy as it seems odd to mix and match ray directions
var tMax = new Vector3(
ray.Direction.X < 0 ? tMaxNeg.X : tMaxPos.X
,
ray.Direction.Y < 0 ? tMaxNeg.Y : tMaxPos.Y
,
ray.Direction.Z < 0 ? tMaxNeg.Z : tMaxPos.Z
);
/// get cell coordinate step directions
/// .Sign() is an extension method that returns a Vector3 with each component set to +/- 1
var step = ray.Direction.Sign();
/// calculate distance along the ray direction to move to advance from one cell boundary
/// to the next on each axis. Assumes ray.Direction is normalized.
/// Takes the absolute value of each ray component since this value is in units along the
/// ray direction, which makes sure the sign is correct.
var tDelta = (leafSize / ray.Direction).Abs();
/// neighbor node indices to use when exiting cells
/// GridDirection.East = Vector3.Right
/// GridDirection.West = Vector3.Left
/// GridDirection.North = Vector3.Forward
/// GridDirection.South = Vector4.Back
/// GridDirection.Up = Vector3.Up
/// GridDirection.Down = Vector3.Down
var neighborDirections = new[] {
(step.X < 0) ? GridDirection.West : GridDirection.East
,
(step.Y < 0) ? GridDirection.Down : GridDirection.Up
,
(step.Z < 0) ? GridDirection.North : GridDirection.South
};
OctreeNode node=root;
/// step across the bounding volume, generating a marker entity at each
/// cell that we touch. Extension methods GreaterThanOrEEqual and LessThan
/// ensure that we stay within the bounding volume.
while (node!=null)
{
/// if the current node isn't a leaf, find one.
/// this version exits when it encounters the first leaf.
if (!node.Leaf)
for (var i = 0; i < OctreeNode.ChildCount; i++)
{
var child = node.Children[i];
if (child != null && child.Contains(cell))
{
//SetNode(ref node, child, visitedNodes);
node = child;
i = -1;
if (node.Leaf)
return node;
}
}
/// index into the node's Neighbor[] array to move
int dir = 0;
/// This is off-the-shelf DDA.
if (tMax.X < tMax.Y)
{
if (tMax.X < tMax.Z)
{
tMax.X += tDelta.X;
cell.X += step.X;
dir = 0;
}
else
{
tMax.Z += tDelta.Z;
cell.Z += step.Z;
dir = 2;
}
}
else
{
if (tMax.Y < tMax.Z)
{
tMax.Y += tDelta.Y;
cell.Y += step.Y;
dir = 1;
}
else
{
tMax.Z += tDelta.Z;
cell.Z += step.Z;
dir = 2;
}
}
/// see if the new cell coordinates fall within the current node.
/// this is important when moving from a leaf into empty space within
/// the tree.
if (!node.Contains(cell))
{
/// if we stepped out of this node, grab the appropriate neighbor.
var neighborDir = neighborDirections[dir];
node = node.GetNeighbor(neighborDir);
}
else if (node.Leaf && stopAtFirstLeaf)
return node;
}
return null;
}
随意指出任何错误.如果有任何需求,我会发布HLSL版本.
这是另一个版本,它只是在没有交叉检查的情况下以叶子大小的步骤遍历树.这在3D DDA演示中非常有用:
/// <summary>
/// draw a 3D DDA "line" in units of leaf size where the ray intersects the
/// tree's bounding volume/
/// </summary>
/// <param name="ray"></param>
public IEnumerable<Vector3> DDA(Ray ray)
{
float tmin;
float tmax;
if (!RayCasting.HitsBox(ray, root.BoundingBox.Min, root.BoundingBox.Max, out tmin, out tmax))
yield break;
/// move the ray position to the point of intersection with the bounding volume.
ray.Position += ray.Direction * tmin;
/// get integer cell coordinates for the given position
var cell = Vector3.Min(((ray.Position - boundingBox.Min) / leafSize).Truncate(), cellCount - Vector3.One);
/// get the bounds of the starting cell.
var cellBounds = GetCellBounds(cell);
/// calculate initial t values for each axis based on the sign of the ray.
var tMaxNeg = (cellBounds.Min - ray.Position) / ray.Direction;
var tMaxPos = (cellBounds.Max - ray.Position) / ray.Direction;
/// calculate t values within the cell along the ray direction.
var tMax = new Vector3(
ray.Direction.X < 0 ? tMaxNeg.X : tMaxPos.X
,
ray.Direction.Y < 0 ? tMaxNeg.Y : tMaxPos.Y
,
ray.Direction.Z < 0 ? tMaxNeg.Z : tMaxPos.Z
);
/// get cell coordinate step directions
var step = ray.Direction.Sign();
/// calculate distance along the ray direction to move to advance from one cell boundary
/// to the next on each axis. Assumes ray.Direction is normalized.
var tDelta = (leafSize / ray.Direction).Abs();
/// step across the bounding volume, generating a marker entity at each
/// cell that we touch. Extension methods GreaterThanOrEEqual and LessThan
/// ensure that we stay within the bounding volume.
while (cell.GreaterThanOrEqual(Vector3.Zero) && cell.LessThan(cellCount))
{
yield return boundingBox.Min + cell * leafSize;
///create a cube at the given cell coordinates, and add it to the draw list.
if (tMax.X < tMax.Y)
{
if (tMax.X < tMax.Z)
{
tMax.X += tDelta.X;
cell.X += step.X;
}
else
{
tMax.Z += tDelta.Z;
cell.Z += step.Z;
}
}
else
{
if (tMax.Y < tMax.Z)
{
tMax.Y += tDelta.Y;
cell.Y += step.Y;
}
else
{
tMax.Z += tDelta.Z;
cell.Z += step.Z;
}
}
}
}
还有一个HLSL版本,只将树存储在Texture3D中,没有邻居或树的任何"稀疏性".
这仍然是错误的.第一次测试hitbox()工作正常,但光线在树中折射.这看起来很酷,但不正确.
这是我停在根边界时的样子,而不使用DDA遍历树:
/*
find which leaf, if any, the ray intersects.
Returns transparency (Color(0,0,0,0)) if no intersection was found.
TestValue is a shader constant parameter passed from the caller which is used to dynamically adjust the number of loops the shader code will execute. Useful for debugging.
intrinsics:
step(y,x) : (x >= y) ? 1 : 0
*/
float4 DDATraverse(Ray ray)
{
float3 bounds_min = OctreeCenter-OctreeObjectSize/2;
float3 bounds_max = OctreeCenter+OctreeObjectSize/2;
float4 cellsPerSide = float4(trunc((bounds_max-bounds_min)/CellSize),1);
float3 vector3_one = float3(1,1,1);
float tmin;
float tmax;
if(hitbox(ray,bounds_min,bounds_max,tmin,tmax))
{
ray.Position+=ray.Direction*tmin;
float4 cell = float4((ray.Position-bounds_min)/CellSize,1);
float3 tMaxNeg = (bounds_min-ray.Position)/ray.Direction;
float3 tMaxPos = (bounds_max-ray.Position)/ray.Direction;
float3 tmax = float3(
ray.Direction.x < 0 ? tMaxNeg.x : tMaxPos.x
,
ray.Direction.y < 0 ? tMaxNeg.y : tMaxPos.y
,
ray.Direction.z < 0 ? tMaxNeg.z : tMaxPos.z
);
float3 tstep = sign(ray.Direction);
float3 dt = abs(CellSize/ray.Direction);
float4 texel;
float4 color;
for(int i=0;i<TestValue;i++)
{
texel=smoothstep(float4(0,0,0,0),cellsPerSide,cell);
if (color.a < 0.9)
color = tex3Dlod(octreeSampler,texel);
if (tmax.x < tmax.y)
{
if (tmax.x < tmax.z)
{
tmax.x+=dt.x;
cell.x+=tstep.x;
}
else
{
tmax.z+=dt.z;
cell.z+=tstep.z;
}
}
else
{
if (tmax.y < tmax.z)
{
tmax.y+=dt.y;
cell.y+=tstep.y;
}
else
{
tmax.z+=dt.z;
cell.z+=tstep.z;
}
}
}
return color;
}
else
return float4(1,0,0,1);
}
更新
找到了一个非常好的体积渲染教程!
http://graphicsrunner.blogspot.com/search?updated-max=2009-08-27T02%3A45%3A00-04%3A00&max-results=10