Erika32

I could write the algorithm to do this myself if I took the time to work it out, but I wanted to see if someone else has done it first.

I'm working on a voxel engine for a game that I'm working on, and I need to trace a ray from the camera's position out a certain distance to try to find the nearest intersection. I was thinking of just taking the cell that the camera is in, then taking the direction, figuring out at what point the ray leaves the cell, then figure out what the next cell is that it will enter. I would keep doing this until I find an intersection.

Does anyone have experience with this? Maybe you have an algorithm that can do just that?

I have some modified Bresenham line code, but I can't seem to wrap my head around the concept of taking it into the third dimension.

typedef void (*pointCallback)(int x, int y);
void DoLine(int startX, int startY, int endX, int endY, pointCallback callback)
{
int dx, dy;
int sx, sy;
int accum;//accumilator
dx = endX - startX;//Start X subtracted from End X
dy = endY - startY;
sx = ((dx) < 0 ? -1 : ((dx) > 0 ? 1 : 0));//if dx is less than 0, sx = -1; otherwise if dx is greater than 0, sx = 1; otherwise sx = 0
sy = ((dy) < 0 ? -1 : ((dy) > 0 ? 1 : 0));
//dx = (dx < 0 ? -dx : dx);//if dx is less than 0, dx = -dx (becomes positive), otherwise nothing changes
dx = abs(dx);//Absolute value
//dy = (dy < 0 ? -dy : dy);
dy = abs(dy);
endX += sx;//Add sx to End X
endY += sy;
//x = 6
//y = 5
//accum = 3
//accum - 5 = 1
//startx + 1 = 1
//accum - 5 = -4
//accum + 6 = 2
//startY + 1 = 1
if (dx > dy)//if dx is greater than dy
{
  accum = dx >> 1;//Accumilator = dx / 2
  do
  {
   //Plot point
   callback(startX, startY);
   //Subtract dy from accumilator
   accum -= dy;
   //if accumilator is less than 0
   if (accum < 0)
   {
	//Add dx to accumilator
	accum += dx;
	//Add sy to Start Y
	startY += sy;
   }
   //Add sx to Start X
   startX += sx;
  } while (startX != endX);
}
else
{
  accum = dy >> 1;
  do
  {
   callback(startX, startY);
   accum -= dx;
   if (accum < 0)
   {
	accum += dy;
	startX += sx;
   }
   startY += sy;
  } while (startY != endY);
}
}

All I can think of to do is parallel draw the line between the XY and YZ planes, but I'm not sure of how do go about doing that.

Edit: I think I figured it out. I always figure out my problem right after I resort to asking for help >.<

public static void DoLine(int startX, int startY, int startZ, int endX, int endY, int endZ, Action<int, int, int> callback)
	    {
		    int dx, dy, dz;
		    int sx, sy, sz;
		    int accum, accum2;//accumilator
		    dx = endX - startX;//Start X subtracted from End X
		    dy = endY - startY;
		    dz = endZ - startZ;
		    sx = ((dx) < 0 ? -1 : ((dx) > 0 ? 1 : 0));//if dx is less than 0, sx = -1; otherwise if dx is greater than 0, sx = 1; otherwise sx = 0
		    sy = ((dy) < 0 ? -1 : ((dy) > 0 ? 1 : 0));
		    sz = ((dz) < 0 ? -1 : ((dz) > 0 ? 1 : 0));
		    //dx = (dx < 0 ? -dx : dx);//if dx is less than 0, dx = -dx (becomes positive), otherwise nothing changes
		    dx = Math.Abs(dx);//Absolute value
		    //dy = (dy < 0 ? -dy : dy);
		    dy = Math.Abs(dy);
		    dz = Math.Abs(dz);
		    endX += sx;//Add sx to End X
		    endY += sy;
		    endZ += sz;
		    if (dx > dy)//if dx is greater than dy
		    {
			    if (dx > dz)
			    {
				    accum = dx >> 1;
				    accum2 = accum;
				    do
				    {
					    callback(startX, startY, startZ);
					    accum -= dy;
					    accum2 -= dz;
					    if (accum < 0)
					    {
						    accum += dx;
						    startY += sy;
					    }
					    if (accum2 < 0)
					    {
						    accum2 += dx;
						    startZ += sz;
					    }
					    startX += sx;
				    }
				    while (startX != endX);
			    }
			    else
			    {
				    accum = dz >> 1;
				    accum2 = accum;
				    do
				    {
					    callback(startX, startY, startZ);
					    accum -= dy;
					    accum2 -= dx;
					    if (accum < 0)
					    {
						    accum += dz;
						    startY += sy;
					    }
					    if (accum2 < 0)
					    {
						    accum2 += dz;
						    startX += sx;
					    }
					    startZ += sz;
				    }
				    while (startZ != endZ);
			    }
		    }
		    else
		    {
			    if (dy > dz)
			    {
				    accum = dy >> 1;
				    accum2 = accum;
				    do
				    {
					    callback(startX, startY, startZ);
					    accum -= dx;
					    accum2 -= dz;
					    if (accum < 0)
					    {
						    accum += dx;
						    startX += sx;
					    }
					    if (accum2 < 0)
					    {
						    accum2 += dx;
						    startZ += sz;
					    }
					    startY += sy;
				    }
				    while (startY != endY);
			    }
			    else
			    {
				    accum = dz >> 1;
				    accum2 = accum;
				    do
				    {
					    callback(startX, startY, startZ);
					    accum -= dx;
					    accum2 -= dy;
					    if (accum < 0)
					    {
						    accum += dx;
						    startX += sx;
					    }
					    if (accum2 < 0)
					    {
						    accum2 += dx;
						    startY += sy;
					    }
					    startZ += sz;
				    }
				    while (startZ != endZ);
			    }
		    }
	    }