0

I'm trying to implement this algorithm in C#, but I have very inconsistent results at the moment, and I can't figure out why.

Here is my current implementation :

public static IEnumerable<Point> FastVoxelTraversal(Point a, Point b)
    {
        var ret = new List<Point>();

        Vector direction = ((Vector)b - (Vector)a);

        int stepX = direction.x >= 0 ? 1 : -1;
        int stepY = direction.y >= 0 ? 1 : -1;
        int stepZ = direction.z >= 0 ? 1 : -1;

        var iterator = a;

        float nextVoxelBoundaryX = (iterator.x + stepX);
        float nextVoxelBoundaryY = (iterator.y + stepY);
        float nextVoxelBoundaryZ = (iterator.z + stepZ);

        float tMaxX = (direction.x != 0) ? (nextVoxelBoundaryX - a.x) / direction.x : float.MaxValue;
        float tMaxY = (direction.y != 0) ? (nextVoxelBoundaryY - a.y) / direction.y : float.MaxValue;
        float tMaxZ = (direction.z != 0) ? (nextVoxelBoundaryZ - a.z) / direction.z : float.MaxValue;

        float tDeltaX = (direction.x != 0) ? 1f / direction.x * stepX : float.MaxValue;
        float tDeltaY = (direction.y != 0) ? 1f / direction.y * stepY : float.MaxValue;
        float tDeltaZ = (direction.z != 0) ? 1f / direction.z * stepZ : float.MaxValue;

        while (iterator != b)
        {
            if (tMaxX < tMaxY)
            {
                if (tMaxX < tMaxZ)
                {
                    iterator.x += stepX;
                    tMaxX += tDeltaX;
                }
                else
                {
                    iterator.z += stepZ;
                    tMaxZ += tDeltaZ;
                }
            }
            else
            {
                if (tMaxY < tMaxZ)
                {
                    iterator.y += stepY;
                    tMaxY += tDeltaY;
                }
                else
                {
                    iterator.z += stepZ;
                    tMaxZ += tDeltaZ;
                }
            }

            ret.Add(iterator);
        }

        return ret;
    }

The cell size is 1.

This is the type of result I get. As you can see, sometimes the results are as expected, and sometimes not.

This does not seem to be related to the coordinates being positive or negative (I have strange results in striclty positive spaces, and good results in negative spaces, and vice versa). enter image description here enter image description here

I struggled to find more documentation on this algorithm, so I'm thinking that my variables could not be initialized correctly? What should I correct?

Thank you very much.

EDIT : Thank you for your answers. I painted the results I'm expecting : enter image description here

This algorithm should perform a "supercover", meaning that it should include all cells it traverses. This is different from Bresenham, which is supposed to give an approximative rasterization.

6
  • 1
    Could you draw an image of what you expect the result to be? Also, depending on your need, there may be a better way to do this, but it'd help to know a bit more why you need this algorithm (or a similar algorithm). Commented Apr 10 at 20:41
  • Is your point a always exactly at grid point? If not, nextVoxelBoundaryX = (iterator.x + stepX); looks strange. Initial point may be inside cell, example of initialization Commented Apr 11 at 3:58
  • It is not at all clear to me what results are as expected or not. The code look kind of Bresenham's line algorithm extended to 3D, but there might be some detail I'm missing. Commented Apr 11 at 7:36
  • Hello, thank you for your answers! I edited my answer with the expected results. I need this algorithm because I'm working on a XCom2-like game, and I would like to evaluate which tiles a shot would go through. I would basically like to implement it for voxel-based LOS. @MBo the point will indeed always be on the grid, as the game is grid-based. Commented Apr 11 at 8:09
  • @LaGrange I know this algo, used it for 2D case. AFAIR, article does not explain initialization step well. Note that you have to make initial cordinates relative to cell (like 0.5; 0.5 for cell center). That is why I asked. Commented Apr 11 at 8:18

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.