八叉树光线投射/光线追踪 - 无需递归的最佳光线/叶子相交

Question

谁能提供一个简短的&关于如何在不递归的情况下向体素八叉树投射光线的甜蜜解释（或建议一个好教程）？

我有一个复杂的模型烘焙成八叉树，我需要找到与射线相交的最佳/最近的叶子。标准的向下钻取迭代树遍历：

1. 抓住根节点
2. 检查交集
3. 否？退出
4. 是吗？找到与射线相交最接近射线原点的子级
5. 循环直到到达叶子或退出树

始终返回叶子，但在树存储地形的情况下，距离射线原点最近的节点不会必然包含最匹配的叶子。这并不奇怪——使用这种方法不会测试较远节点中较高的对象。

我可以通过找到树中所有相交的叶子、按距离排序并选择最接近光线位置的叶子来递归地完成此操作。然而，这很慢并且需要递归。

我读过一些关于使用 Bresenham 线算法来遍历树的内容，这似乎要求每个节点包含指向相邻邻居的指针，但我不清楚如何以有用的方式实现这一点。

有什么建议吗？我可以在 HLSL 中使用固定长度数组或每个潜在堆栈条目都有一个元素的结构来伪造堆栈，但对于足够大的树来说，其内存需求可能会变得严重。

帮助。

Answer 1

我已经设法使用 3D DDA 算法和邻居节点指针来实现此功能。

我仍在解决一些错误，但这里有一个似乎可以工作的 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