• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
thecheeselover

Voxel traversal problem

3 posts in this topic

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#:

[CODE]
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);
}
[/CODE]

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

Thank you,
Thecheeselover
0

Share this post


Link to post
Share on other sites
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.


[CODE]
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;
[/CODE]

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


[CODE]
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.
}
}
}
[/CODE] Edited by mgoss
1

Share this post


Link to post
Share on other sites
[quote name='thecheeselover' timestamp='1335718616' post='4935843']
// 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;
[/quote]

Actually...there is a problem there.

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

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0