• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

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

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

7 replies to this topic

### #1Erika32  Members

Posted 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?

### #2slicer4ever  GDNet+

Posted 09 October 2012 - 11:56 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?

there are probably faster method's, but if we make a few assumptions about the ray being inside the voxel grid, then some pseudo-code would look like this:

CurrentCell = GetCell(Ray.Start); //we start in the current cell
EndCell = GetCell(Ray.End); //we mark the last cell so we know where to stop.
while(CurrentCell!=EndCell){
//we only need to check at most 3 faces depending on the direction of the ray(since we obviously can't hit faces we're not heading towards)
Vector3 Result; //Store ray point.
int Faces[3];
Faces[0] = Ray.Direction.x<0.0f?LEFT:(Ray.Direction.x>0.0f?Right:-1); //if direction.x == 0 then no need to test the face;
Faces[1] = Ray.Direction.y<0.0f?BOTTOM:(Ray.Direction.y>0.0f?TOP:-1); //" "
Faces[2] = Ray.Direction.z<0.0f?BACK:(Ray.Drection.z>0.0f?FRONT:-1); //" "
for(int i=0;i<3;i++){
if(Faces[i]==-1) continue;
if(CheckPlanexRay(CurrentCell.VoxelPlane[Faces[i]], Ray, &Result)){ //we need the point that intersects this cell.
if(CurrentCell.CheckPointInVoxel(Result)){
CurrentCell = CurrentCell.GetNeighbor(Faces[i]);
if(CurrentCell.isClosed()) return Result, CurrentCell;.
break;
}
}
}
return null;
}



anywho, i'm sure someone else has a better solution, much luck mate=-)

Edited by slicer4ever, 09 October 2012 - 11:59 PM.

Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

### #3Sirisian  Members

Posted 10 October 2012 - 12:35 AM

You want the 3DDDA algorithm. If you google you can find 2D versions easily. It expands to 3D intuitively.

### #4Erika32  Members

Posted 10 October 2012 - 01:59 AM

For simplicity, since my voxels are 1x1x1 in size, I decided I could just move the ray by 1 unit, then get the cell that the ray is in, then check collision within that cell. Then I just keep incrementing it until I either reach my max length, or I find collision. Now I just need to remember how to collide a 3D ray with a 3D quad.

### #5slicer4ever  GDNet+

Posted 10 October 2012 - 05:39 AM

For simplicity, since my voxels are 1x1x1 in size, I decided I could just move the ray by 1 unit, then get the cell that the ray is in, then check collision within that cell. Then I just keep incrementing it until I either reach my max length, or I find collision. Now I just need to remember how to collide a 3D ray with a 3D quad.

while a valid approach, this can potentially skip some voxels if the ray is too close to an edge, but if it meets you needs, then by all means=-)
Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

### #6Erika32  Members

Posted 11 October 2012 - 12:56 AM

I decided to just go ahead and write the hard, complicated code to find the next cell from the camera, and it works, but I'm having trouble tracing through the cells. My problem is a little simple. All I need to do is figure out how to properly get the position that the ray touched the next cell. I don't need the complicated math to do this, it's something I THOUGHT I would be able to do. The ray is positioned inside a cell, then I find the face that's closest, and I move into that cell, and move the ray along itself until it is against the edge of that cell. I figured that I could do this:

ray.Position = ray.Position + ray.Direction * distanceNeeded, but I now realize why that won't work.

if the ray is a simple ray with a position of (0.5,0.5,0.5) and a direction of (1.0,0.0,0.0), then the next position should be (1.0,0.5,0.5). The distance between the X component of the wall and the X component of the ray's position is 0.5f, it works just fine when you have those values, but when the direction has values for all three components, and it's normalized, you won't be able to get the same value by multiplication.

So, really, what my new question is: How can I find the position that a ray collides with a plane? I just want to move the ray along itself until it is inside the next cell, but that's not working for some reason.

### #7luca-deltodesco  Members

Posted 11 October 2012 - 01:09 AM

You should really just look up the DDA algorithm as previously suggested, it is 'far' simpler implementation than what you have described.

Edited by luca-deltodesco, 11 October 2012 - 01:10 AM.

### #8Erika32  Members

Posted 11 October 2012 - 01:26 AM

You should really just look up the DDA algorithm as previously suggested, it is 'far' simpler implementation than what you have described.

My description was very poor. The algorithm I wrote is really simple, but it requires that your ray is inside the cell that you're finding the neighbor of.

Here's a simple version with a single value:

int sign = Math.Sign(direction)
float distance;

if(sign == 1)
{
distance = 1 - value;
}
else if(sign == -1)
{
distance = -value;
}
else
{
distance = infinity;
}



After you get the distance to the next face for each component (X, Y, and Z), you figure out which face you will get to first by dividing the distance by the direction.

Once you know which face you will encounter first, you know which cell is the next cell. The problem I'm having is that I rely on the position of the ray to trace through the cells.

Sorry that I'm being very vague, I have ADHD, and it's really hard for me to articulate what's going through my mind. All I see is a visualization of my algorithm, and I could give you the code, but it wouldn't make sense since there are a few things that you'll likely not know what's happening.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.