• Create Account

# Erika32

Member Since 31 Aug 2012
Offline Last Active Oct 24 2012 06:34 AM

### Trace a ray through a 3D grid of cells?

09 October 2012 - 11:12 PM

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?

### 3D line drawing algorithm?

31 August 2012 - 06:09 PM

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)
{
accum += dx;
startY += sy;
}
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);
}
}
}

PARTNERS