Voxel Engine - Function to DrawLine in 3D space

This topic is 1021 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hey guys,

Random question, I am storing my voxel world in chunks (3d byte arrays). I am creating some helper functions and there is one particular function that I can't seem to figure out. How to draw a line from a Vector3 Origin Point to a Vector3 Destination Point. The points would be cells in my array based on World Coordinates.

For example I want to draw a line from 0,0,0 to 0,10,5

Based on that it would turn all the cells in the array between 0,0,0 and 0,10,5 that form a line from 0 to 1.

It's a bit hard to explain but I hope it makes sense.

Cheers,

NGD

Share on other sites

/*
* C code from the article
* "Voxel Traversal along a 3D Line"
* by Daniel Cohen, danny@bengus.bgu.ac.il
* in "Graphics Gems IV", Academic Press, 1994
*/

/* The following C subroutine visits all voxels along the line
segment from (x, y, z) and (x + dx, y + dy, z + dz) */

Line ( x, y, z, dx, dy, dz )
int x, y, z, dx, dy, dz;
{
int n, sx, sy, sz, exy, exz, ezy, ax, ay, az, bx, by, bz;

sx = sgn(dx);  sy = sgn(dy);  sz = sgn(dz);
ax = abs(dx);  ay = abs(dy);  az = abs(dz);
bx = 2*ax;	   by = 2*ay;	  bz = 2*az;
exy = ay-ax;   exz = az-ax;	  ezy = ay-az;
n = ax+ay+az;
while ( n-- ) {
VisitVoxel ( x, y, z );
if ( exy < 0 ) {
if ( exz < 0 ) {
x += sx;
exy += by; exz += bz;
}
else  {
z += sz;
exz -= bx; ezy += by;
}
}
else {
if ( ezy < 0 ) {
z += sz;
exz -= bx; ezy += by;
}
else  {
y += sy;
exy -= bx; ezy -= bz;
}
}
}
}

From the book "Graphics Gems IV", "Voxel Traversal along a 3D Line, p. 366-369". The books and source are available here: http://tog.acm.org/resources/GraphicsGems/ (So there is not confusion over copyrights and stuff...)

Share on other sites

The problem is a fairly straightforward generalisation of line rasterisation, for example, using the classical Bresenham's algorthm.