xna - 八叉树光线转换/光线跟踪 - 无递归的最佳光线/叶子交叉点

Question

任何人都可以提供关于如何在没有递归的情况下对体素八叉树转换光线的简短而甜蜜的解释(或建议一个好的教程)？

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

抓取根节点

检查交叉点

不？退出

是的？找到与最接近射线原点的射线相交的子元素

循环直到我到达一片叶子或离开树

总是返回一个叶子，但在树存储的情况下，比如地形，离射线原点最近的节点不一定包含最匹配的叶子。这并不奇怪 - 使用这种方法不会测试更远节点中更高的对象。

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

我已经阅读了一些关于使用 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