How to fix my 3D Ray-Casting Algorithm for getting the Block the player is looking at

Question

My algorithm for calculating which block a player is looking at (voxel based world) is not working correctly. I have adapted it from this tutorial from 2D to 3D. At times it shows the correct block but other times it either returns nothing when it should or something in a completely different direction, why is this happening?

public (Block, Box?) GetLookAtBlock(Vector3 pos, Vector3 look) {
    try {
        look = look.Normalized() * 4;

        float deltaX = Math.Abs(look.Normalized().X);
        float deltaY = Math.Abs(look.Normalized().Y);
        float deltaZ = Math.Abs(look.Normalized().Z);

        int stepX, stepY, stepZ;
        float distX, distY, distZ;

        if (look.X < 0) {
            distX = (pos.X - SandboxMath.RoundDown(pos.X)) * deltaX;
            stepX = -1;
        } else {
            distX = (SandboxMath.RoundDown(pos.X) + 1 - pos.X) * deltaX;
            stepX = 1;
        }

        if (look.Y < 0) {
            distY = (pos.Y - SandboxMath.RoundDown(pos.Y)) * deltaY;
            stepY = -1;
        } else {
            distY = (SandboxMath.RoundDown(pos.Y) + 1 - pos.Y) * deltaY;
            stepY = 1;
        }

        if (look.Z < 0) {
            distZ = (pos.Z - SandboxMath.RoundDown(pos.Z)) * deltaZ;
            stepZ = -1;
        } else {
            distZ = (SandboxMath.RoundDown(pos.Z) + 1 - pos.Z) * deltaZ;
            stepZ = 1;
        }

        int endX = SandboxMath.RoundDown(pos.X + look.X);
        int endY = SandboxMath.RoundDown(pos.Y + look.Y);
        int endZ = SandboxMath.RoundDown(pos.Z + look.Z);

        int x = (int)pos.X;
        int y = (int)pos.Y;
        int z = (int)pos.Z;

        Block start = GetBlock(x, y, z);

        if (start != 0) {
            return (start, new Box(new Vector3(x, y, z), new Vector3(x + 1, y + 1, z + 1)));
        }

        while (x != endX && y != endY && z != endZ) {
            if (distX < distY) {
                if (distX < distZ) {
                    distX += deltaX;
                    x += stepX;
                } else {
                    distZ += deltaZ;
                    z += stepZ;
                }
            } else {
                if (distY < distZ) {
                    distY += deltaY;
                    y += stepY;
                } else {
                    distZ += deltaZ;
                    z += stepZ;
                }
            }

            Block b = GetBlock(x, y, z);
            if (b != 0) {
                return (b, new Box(new Vector3(x, y, z), new Vector3(x + 1, y + 1, z + 1)));
            }
        }

        return (0, null);
    } catch (IndexOutOfRangeException) {
        return (0, null);
    }
}

Answer 1

your DDA have two issues I can see from the first look:

1. work only if Z is the major axis

   so only if you are in camera space or have fixed camera looking in Z direction

2. your deltas are weird

   why:

   delta? = abs(1 / look.Normalized().?);
   

   I would expect:

   delta? = abs(look.Normalized().?);
   

I do not code in C# so I am not confident to repair your code however here is my C++ template for n-dimensional DDA so just compare and repair yours according it ...

template<const int n>class DDA
    {
public:
    int p0[n],p1[n],p[n];
    int d[n],s[n],c[n],ix;

    DDA(){};
    DDA(DDA& a) { *this=a; }
    ~DDA(){};
    DDA* operator = (const DDA *a) { *this=*a; return this; }
    //DDA* operator = (const DDA &a) { ..copy... return this; }

    void start()
        {
        int i;
        for (ix=0,i=0;i<n;i++)
            {
            p[i]=p0[i];  s[i]= 0; d[i]=p1[i]-p0[i];
            if (d[i]>0)  s[i]=+1;
            if (d[i]<0){ s[i]=-1; d[i]=-d[i]; }
            if (d[ix]<d[i]) ix=i;
            }
        for (i=0;i<n;i++) c[i]=d[ix];
        }
    void start(double *fp0) // this will add the subpixel offset according to first point as double
        {
        int i; start();
        for (i=0;i<n;i++)
            {
            if (s[i]<0) c[i]=double(double(d[ix])*(    fp0[i]-floor(fp0[i])));
            if (s[i]>0) c[i]=double(double(d[ix])*(1.0-fp0[i]+floor(fp0[i])));
            }
        }

    bool update()
        {
        int i;
        for (i=0;i<n;i++){ c[i]-=d[i]; if (c[i]<=0){ c[i]+=d[ix]; p[i]+=s[i]; }}
        return (p[ix]!=p1[ix]+s[ix]);
        }
    };

start() init the variables and position for the DDA (from p0,p1 control points) and the update() is just single step of the DDA ... Resulting iterated point is in p

s is the step, d is delta, c is counter and ix is major axis index.

The usage is like this:

DDA<3> A; // 3D
A.p0[...]=...; // set start point
A.p1[...]=...; // set end point

for (A.start();A.update();)
 {
 A.p[...]; // here use the iterated point
 }

DDA go through

well DDA is just interpolation (rasterization) of integer positions on some line between two endpoints (p0,p1). The line equation is like this:

p(t) = p0 + t*(p1-p0);
t = <0.0,1.0>

however that involves floating math and we want integer so we can rewrite to something like this:

dp = p1-p0
D  = max (|dp.x|,|dp.y|,|dp.z|,...)
p.x(i) = p0.x + (dp.x*i)/D
p.y(i) = p0.y + (dp.y*i)/D
p.z(i) = p0.z + (dp.z*i)/D
...
i = { 0,1,...D }

where i,D is matching the major axis (the one with biggest change). If you look closer we are using *i/D Which is slow operation and we usually want speed so we can rewrite the therm (exploiting the fact that i goes from 0 to D in order) into something like this (for x axis only the others will be the same with different indexes ...):

p.x=p0.x;                          // start position
s.x=0; d.x=p1.x-p0.x;              // step and abs delta
if (d.x>0) s.x=+1;
if (d.x<0){ s.x=-1; d.x=-d.x; }
D = max(d.x,d.y,d.z,...);          // major axis abs delta
c.x=D;                             // counter for the iteration
for (i=0;i<D;i++)
 {
 c.x-=d.x;                         // update counter with axis abs delta
 if (c.x<=0)                       // counter overflowed?
  {
  c.x+=D;                          // update counter with major axis abs delta
  p.x+=s.x;                        // update axis by step
  }
 }

Now take a closer look at the counter c which we are adding the D and substracting d.x which is the i/D rewrited into D iterations. All the other axises are computed in the same manner you just need to add counter c step s and abs delta d for each axis ...

btw if it helps look at this:

• volumetric GLSL back ray tracer

  which is (I assume) what you are doing but implemented in GLSL shader (see the fragment code) however it does not use DDA instead it is adding unit direction vector to initial position until hit something or end of voxel space ...

btw its based on:

• Ray Casting with different height size

just like the link of yours.

[Edit] wrong hits (guessed from your comments)

That has most likely nothing to do with DDA. Its more like edge case when you are standing directly on cell crossing or have wrongly truncated position or have wrongly z-sorted the hits. I remember I was having trouble with it. I ended up with very weird solution in GLSL see the Link above and see the fragment code. Look for

// YZ plane voxels hits

its directly after the non "DDA" ray casting code. It detects which plane of the voxel will be hit I think you should do something similar. It was weird as in 2D DOOM (also in links above) I had no such problems... but that was due to fact they were solved by different math used (suitable only for 2D).

The GLSL code just before the casting of ray changes a position a bit to avoid edge cases. pay attention to the floor and ceil but mine works on floats so it would need some tweaking for int math. Luckily I was repairing my other ray casting engine based on this:

• Comanche Voxel space ray casting

And the solution is to offset the DDA by subpixel start position of the ray. I updated the DDA code above the new usage is:

DDA<3> A; // 3D
A.p0[...]=...; // set start point
A.p1[...]=...; // set end point

for (A.start(start_point_as_double[3]);A.update();)
 {
 A.p[...]; // here use the iterated point
 }

Also on second taught make sure that in your DDA the c,d,s are integers if they are floating instead then it might cause the problems you are describing too...