Мне удалось заставить в основном работать с использованием алгоритма 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