• Create Account

Calling all IT Pros from Canada and Australia.. we need your help! Support our site by taking a quick sponsored surveyand win a chance at a \$50 Amazon gift card. Click here to get started!

# Voxel traversal problem

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.

3 replies to this topic

### #1thecheeselover  Members   -  Reputation: 420

Like
0Likes
Like

Posted 29 April 2012 - 10:56 AM

Hi,

I have a little issue with a voxel traversal algorithm that I can't fix. I put more than two weeks fixing it without any results and I even made my own voxel traversal that has the same problem but bigger. My problem appears only when one axis of my camera's position is negative. It also only appears when I look at a voxel that has the same position as my camera on the same axis of my camera that is negative. For exemple, if my camera's position is (-2, 3, 5) and if I look at a voxel that its position is (-2, -5, -2), then the problem will appear because my camera's X position is negative (-2) and because I look at a voxel that has the same X value as my camera (-2). But if I looked at the voxel (-1, -5, -2), the problem wouldn't have happened because the X value of that voxel isn't equal to my camera's X value. When all those conditions occur, then if my camera's facing normal is not negative on the same axis of my camera that is negative, it will select the closer voxel to zero (always on the same negative axis of my camera) next to the one that is supposed to be selected. Now if you could look at the picture that I attached to this post, you would maybe understand more. Here's the source code in C#:

public struct GetSolidVoxelOnRayResult
{
public Vector3i pos;
public bool hitVoxel; // Si un voxel solide a été touché
public GetSolidVoxelOnRayResult(Vector3i _pos, bool _hitVoxel)
{
pos = _pos;
hitVoxel = _hitVoxel;
}
}

/// <summary>
/// Est comme GetVoxelsOnRay, sauf qu'il retourne un seul voxel. C'est le premier voxel
/// que le ray a touché et qui est solide.
/// </summary>
/// <param name="ray"></param>
/// <param name="maxDepth"></param>
/// <returns></returns>
public static GetSolidVoxelOnRayResult GetSolidVoxelOnRay(Ray ray, int maxDepth, World world, WorldSettings worldSettings)
{
// Implementation is based on:
// "A Fast Voxel Traversal Algorithm for Ray Tracing"
// John Amanatides, Andrew Woo
// http://www.cse.yorku.ca/~amana/research/grid.pdf
// http://www.devmaster.net/articles/raytracing_series/A%20faster%20voxel%20traversal%20algorithm%20for%20ray%20tracing.pdf
// NOTES:
// * This code assumes that the ray's position and direction are in 'cell coordinates', which means
//   that one unit equals one cell in all directions.
// * When the ray doesn't start within the voxel grid, calculate the first position at which the
//   ray could enter the grid. If it never enters the grid, there is nothing more to do here.
// * Also, it is important to test when the ray exits the voxel grid when the grid isn't infinite.
// * The Point3D structure is a simple structure having three integer fields (X, Y and Z).
// The cell in which the ray starts.
// Rounds the position's X, Y and Z down to the nearest integer values.
// There's no problem here!
ray.Position.X += 0.5f;
ray.Position.Y += 0.5f;
ray.Position.Z += 0.5f;
int x = (int)ray.Position.X;
int y = (int)ray.Position.Y;
int z = (int)ray.Position.Z;
// Ce qui est retourné.
Vector3i returnVector = new Vector3i(x, y, z);
// Determine which way we go.
int stepX = Math.Sign(ray.Direction.X);
int stepY = Math.Sign(ray.Direction.Y);
int stepZ = Math.Sign(ray.Direction.Z);
// Calculate cell boundaries. When the step (i.e. direction sign) is positive,
// the next boundary is AFTER our current position, meaning that we have to add 1.
// Otherwise, it is BEFORE our current position, in which case we add nothing.
Vector3i cellBoundary = new Vector3i(
x + (stepX > 0 ? 1 : 0),
y + (stepY > 0 ? 1 : 0),
z + (stepZ > 0 ? 1 : 0));
// NOTE: For the following calculations, the result will be Single.PositiveInfinity
// when ray.Direction.X, Y or Z equals zero, which is OK. However, when the left-hand
// value of the division also equals zero, the result is Single.NaN, which is not OK.
// Determine how far we can travel along the ray before we hit a voxel boundary.
Vector3 tMax = new Vector3(
(cellBoundary.X - ray.Position.X) / ray.Direction.X,	// Boundary is a plane on the YZ axis.
(cellBoundary.Y - ray.Position.Y) / ray.Direction.Y,	// Boundary is a plane on the XZ axis.
(cellBoundary.Z - ray.Position.Z) / ray.Direction.Z);	// Boundary is a plane on the XY axis.
if (Single.IsNaN(tMax.X)) tMax.X = Single.PositiveInfinity;
if (Single.IsNaN(tMax.Y)) tMax.Y = Single.PositiveInfinity;
if (Single.IsNaN(tMax.Z)) tMax.Z = Single.PositiveInfinity;
// Determine how far we must travel along the ray before we have crossed a gridcell.
Vector3 tDelta = new Vector3(
stepX / ray.Direction.X,					// Crossing the width of a cell.
stepY / ray.Direction.Y,					// Crossing the height of a cell.
stepZ / ray.Direction.Z);					// Crossing the depth of a cell.
if (Single.IsNaN(tDelta.X)) tDelta.X = Single.PositiveInfinity;
if (Single.IsNaN(tDelta.Y)) tDelta.Y = Single.PositiveInfinity;
if (Single.IsNaN(tDelta.Z)) tDelta.Z = Single.PositiveInfinity;
// Return it.
returnVector = new Vector3i(x, y, z);
if (Octree.GetBlockTypeParent(world, worldSettings, returnVector).physicalPhase == BlockTypeParent.PhysicalPhase.Solid)
return new GetSolidVoxelOnRayResult(returnVector, true);
// For each step, determine which distance to the next voxel boundary is lowest (i.e.
// which voxel boundary is nearest) and walk that way.
for (int i = 0; i < maxDepth; i++)
{
// Do the next step.
if (tMax.X < tMax.Y && tMax.X < tMax.Z)
{
// tMax.X is the lowest, an YZ cell boundary plane is nearest.
x += stepX;
tMax.X += tDelta.X;
}
else if (tMax.Y < tMax.Z)
{
// tMax.Y is the lowest, an XZ cell boundary plane is nearest.
y += stepY;
tMax.Y += tDelta.Y;
}
else
{
// tMax.Z is the lowest, an XY cell boundary plane is nearest.
z += stepZ;
tMax.Z += tDelta.Z;
}
// Return it.
returnVector = new Vector3i(x, y, z);
if (Octree.GetBlockTypeParent(world, worldSettings, returnVector).physicalPhase == BlockTypeParent.PhysicalPhase.Solid)
return new GetSolidVoxelOnRayResult(returnVector, true);
}
return new GetSolidVoxelOnRayResult(returnVector, false);
}


Do you have any idea how I could fix this or where's the problem in my code?

Thank you,
Thecheeselover

#### Attached Thumbnails

Hide yo cheese! Hide yo wife!

### #2mgoss  Members   -  Reputation: 225

Like
1Likes
Like

Posted 13 May 2012 - 12:17 AM

There a much easier way of finding blocks. If you have an 3 dimensional array. For instance, a Blocks[16, 128, 16] for a chunk.

float x = position.X;
float y = position.Y;
float z = position.Z;
int x = ((int)x / SCALE) % 16;
int y = ((int)y / SCALE) % 128;
int z = ((int)z / SCALE) % 16;


scale is how big your blocks are. Then you can say Block b = Blocks[x, y, z];

If you want to pick what blocks you clicked on. Then do this

const int range = SCALE * 10; //10 = Distance in radius
for(int x = playerX - range; x <= playerX + range; x += SCALE)
{
for(int z = playerZ - range; z <= playerZ + range; z += SCALE)
{
for(int y = playerY - range; y <= playerY + range; y += SCALE)
{
SignedVector3i xyz = GetBlockIndex(new Vector3(x, y, z));
Block b = Block[xyz.x, xyz.y, xyz.z];
//Create a bounding box around that block and it's 6 bounding boxes for each face. Then use a ray to see which side it intersected at.
}
}
}


Edited by mgoss, 13 May 2012 - 01:53 PM.

### #3Elchi  Members   -  Reputation: 780

Like
1Likes
Like

Posted 14 May 2012 - 05:46 PM

// There's no problem here!
ray.Position.X += 0.5f;
ray.Position.Y += 0.5f;
ray.Position.Z += 0.5f;
int x = (int)ray.Position.X;
int y = (int)ray.Position.Y;
int z = (int)ray.Position.Z;

Actually...there is a problem there.

Try this: don't modify the ray position and use floor instead of casting to an int.

### #4thecheeselover  Members   -  Reputation: 420

Like
0Likes
Like

Posted 21 May 2012 - 04:26 PM

Thank you both!

Elchi, you almost had the good answer. I needed to add floor but keep the += 0.5f! Thank you a lot. Mgoss, sorry but your way is really too slow and creates a lot of garbages.
Hide yo cheese! Hide yo wife!

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.

PARTNERS