Forum archive
Tutorial for accurate Cube intersections
- Hi everybody,
I just finished a little tutorial showing howto compute accurate cube intersections as in Ken's method.
It is similar to blockscan of evaldraw, but in 3D and more easy to understand.
I think its a great help for the ones of you wanting to start your own voxel engine.
http://www.xinix.org/sven/main/publications.htm
best regards,
Sven Forstmann
http://www.p0werup.de/
--
here the main part of the Code
// draw elements from p1 to p2
vec3f p1 = vec3f(0.5,0.3,0.7);
vec3f p2 = p1+vec3f(10,8,15);
BoxFrame( vec3f(0,0,0) , vec3f(0,0,0) , 1 );
GFX::Line( p1, p2 ,vec3f(0,0,0) );
vec3f delta = p2-p1;
vec3f frac = p1.frac();
vec3f frac1 = vec3f(1,1,1) - frac;
// Gradients
vec3f gradx ( 1 , delta.y / delta.x , delta.z / delta.x );
vec3f grady ( delta.x / delta.y , 1 , delta.z / delta.y );
vec3f gradz ( delta.x / delta.z , delta.y / delta.z , 1 );
// Fix Div 0
if ( delta.x < 0.001f ) gradx = vec3f ( 1 , 10000 , 10000 );
if ( delta.y < 0.001f ) grady = vec3f ( 10000 , 1 , 10000 );
if ( delta.z < 0.001f ) gradz = vec3f ( 10000 , 10000 , 1 );
// Intersections in x-,y- and z-plane
vec3f ix = p1 + gradx * frac1.x;
vec3f iy = p1 + grady * frac1.y;
vec3f iz = p1 + gradz * frac1.z;
vec3f isect[3]; // intersection in x,y,z
vec3f grad[3]; // gradient in x,y,z
vec3f col[3]; // color for x,y,z
isect [0] = ix; grad[0] = gradx; col[0] = vec3f(0.5,0,0); // X
isect [1] = iy; grad[1] = grady; col[1] = vec3f(0,0.5,0); // Y
isect [2] = iz; grad[2] = gradz; col[2] = vec3f(0,0,0.5); // Z
// algorithm : choose closest of the next 3 intersections in z direction
int index ; vec3f pos,posi;
do {
// sort by z
index = 0; // x smallest -> next intersection in x
if (isect[1].z < isect[0].z) index = 1; // y smallest -> next intersection in y
if (isect[2].z < isect[1].z) index = 2; // z smallest -> next intersection in z
pos = isect[ index ];
posi = isect[ index ].integer();
BoxFrame( pos , col[index] , 0.1f ); // intersection point
BoxFrame( posi , vec3f(0,0,0) , 1 ); // voxel
isect[ index ] = isect[ index ] + grad [index];
} while ( pos.z < p2.z ); Re: Tutorial for accurate Cube intersections
First of all, I appreciate you giving me some credit : )
If you only care about boxes visited and not the intersection points, then you can eliminate the divides in your setup code altogether. Start by multiplying gradx, grady, gradz all by the product: delta.x*delta.y*delta.z. Make sure to scale p1 by the same amount when calculating isect.
There is a bug in your code:index = 0; // x smallest -> next intersection in x
It would claim 2 as the minimum index if you plugged in the following values:
if (isect[1].z < isect[0].z) index = 1; // y smallest -> next intersection in y
if (isect[2].z < isect[1].z) index = 2; // z smallest -> next intersection in z
isect[0].z = 1; isect[1].z = 3; isect[2].z = 2;
In your paper, you say:Then, in a second step, gaps are filled that occur due to the non-orthogonal drawing direction.
This sounds like how Peter Houska's voxel engine works. Voxlap, however, does not fill gaps like you suggest. Instead, it raycasts columns to the temporary buffer, such that it always writes color and depth information to consecutive memory addresses. This makes the temporary buffer more like a linear list than a screen. In the second stage, I use reverse texture mapping to avoid issues with gaps or overdraw - like a standard polygon renderer.. just with unusual perspective.
Rendering to a cube map might be a simpler solution, but I would expect it to be less efficient as far as raycast density is concerned. Maybe it's easier for hardware, I don't know. Also, I'm curious how you plan to render the top and bottom faces of the cube.- >First of all, I appreciate you giving me some credit : )
Sure - as far as I know, you're the inventor of this method :-)
>.. Instead, it raycasts columns to the temporary buffer, such that it always writes color and depth information to consecutive memory addresses.
Ah - then I guess the columns in the temporary buffer does not have linear y while the final perspective skewing is done by the inverse texture mapping - right ? But I wonder what happens by looking straight down - will the temporary buffer be transformed to radial rays starting from the center ? How can you avoid a lot of overdraw in this case?
Do you exactly determine the visible columns and the range ?
>Rendering to a cube map might be a simpler solution, but I would expect it to be less efficient as far as raycast density is concerned. Maybe it's easier for hardware, I don't know.
I didnt have my implementation that far to tell, but as the hardware is optimized for texture-maps it might be ok..
I will have to test it.
> Also, I'm curious how you plan to render the top and bottom faces of the cube.
Hm.. yes, thats a difficulty indeed. An idea could be to precompute an offset map, storing the visible columns with range. Each column will turn into a radial line. The advantage would be that there is no overdraw by creating the texture - screenwise it might not be best though..
>If you only care about boxes visited and not the intersection points, then you can eliminate the divides in your setup code altogether.
Hm.. I think the divides are not such a big issue - but I am still wondering if there is a way to remove some of the "if" 's ..
they might be a bit slow on the graphicscard. I think its possible if the screen is divided into 4 segments (+-x,+-y) - then each screen-partition can be treated with a fixed setting for the sign.
>There is a bug in your code
Thats true - I also just found and fixed it.. the new version is below - I will upload the complete source later.
This time, also sign for delta is taken into consideration. The only restriction left is p1.z<p2.z
void Raycast(vec3f p1,vec3f p2)
{
BoxFrame( vec3f(0,0,0) , vec3f(0,0,0) , 1 );
GFX::Line( p1, p2 ,vec3f(0,0,0) );
vec3f delta = p2-p1; // delta vector
vec3f frac = p1.frac(); // fraction
vec3f fix = vec3f(-1,-1,-1); // Fix for negative numbers
// Signs & direction for frac
if (delta.x >= 0){ fix.x = 0; frac.x = 1-frac.x; }
if (delta.y >= 0){ fix.y = 0; frac.y = 1-frac.y; }
if (delta.z >= 0){ fix.z = 0; frac.z = 1-frac.z; }
// Gradients
vec3f grad[3];
grad[0] = delta * (1/fabs(delta.x)); // x
grad[1] = delta * (1/fabs(delta.y)); // y
grad[2] = delta * (1/fabs(delta.z)); // z
// Intersections in x-,y- and z-plane
vec3f isect[3];
isect[0] = p1 + grad[0] * frac.x; // x
isect[1] = p1 + grad[1] * frac.y; // y
isect[2] = p1 + grad[2] * frac.z; // z
// Colors
vec3f color[3] = {vec3f(0.5,0,0),vec3f(0,0.5,0),vec3f(0,0,0.5)};
// Main loop
vec3f pos,posi;
do {// algorithm : choose closest of the next 3 intersections in z direction
int index = 0; // x smallest -> next intersection in x
if ( isect[1].z < isect[0].z ) index = 1; // y smallest -> next intersection in y
if ( isect[2].z < isect[index].z ) index = 2; // z smallest -> next intersection in z
pos = isect[ index ];
posi = (isect[ index ]+fix).integer();
BoxFrame( pos , color[index] , 0.1f ); // intersection (little box)
BoxFrame( posi , vec3f(0,0,0) , 1 ); // large black box
isect[ index ] = isect[ index ] + grad [index];
} while ( pos.z < p2.z );
}Edited by Spacerat at - Hello,
I just "scrolled" through your paper and it looks very interesting! I already liked HVox although it seems that the textures only work on ATI-cards...Then, in a second step, gaps are filled that occur due to the non-orthogonal drawing direction.
As Ken already said, that's really how my engine works. It is one of the greatest weaknesses of my engine because you can't rely on having all pixels on screen covered correctly... this makes it really hard to allow screen-resizes and/or casting less rays because the gaps then become too large. It's also rather slow to "search" for the gaps (at least the way I do in my engine...).
p.s.:
I noticed that the link to ken's page is wrong - it doesn't end in ".html" but rather ".htm"...
p.p.s.:
cool turrican model!Edited by husky at Do you exactly determine the visible columns and the range ?
Yes. When looking towards the horizon, the column planes project to parallel lines on the screen (vertical lines if your head is not tilted). When looking down at the ground, the column planes project to radial rays on the screen, and the rays all start from the center of the screen. In fact, no matter what orientation you look at, the rays emanate from single point. The trick is how to calculate this point. It's the "zenith" point - the point straight down (or straight up) from your location. A problem occurs when you try to project this point onto the screen. In the case of looking towards the horizon, the rays all "intersect" at screen coordinate (0,+/-infinity), which is caused by a divide by 0. A simple fix is to nudge the denominator before the divide, resulting in not exactly parallel lines, but if done right, it can be made unnoticable.
If you would like to see how I deal with ray projection, run voxed.exe, press '.' a few times to lower the ray density, and then look straight down. You should see the directions in which I cast rays. You may also be interested in checking out GROURAY2.KC, included with Evaldraw. This shows a side view of how the raycasting works. The white dots represent a linearly spaced screen. For each raycast, I align this "dot" screen so that it's linear to the pixels on the screen.
BTW, please fix the spelling of my name at the bottom of this page: http://www.p0werup.de/- I think I understood the functioning of the line-mapping. I added a little test (with source),
showing it roughly - its not yet complete (no inverse mapping) and its not 100% equal to
the one in voxlap, but its similar.
http://www.xinix.org/sven/main/publications/Simple_Raycast.zip
However, the ray-distribution is only optimal by looking straight forward - looking downwards leads to a too high
resolution in the center while the border has a very low resolution. Maybe this could be improved by not letting all
lines end up in the center point - I will do some testing.
>BTW, please fix the spelling of my name
done. Sorry for the typo - Raymapping.exe looks good. In Voxlap, I did not worry about the higher ray density at the poles. The voxels in those areas are usually big and close, so raycasting is a lot faster there.
One thing that would help is to not limit your quadrants to always start and end at the corners of the screen. If you look at the border of 2 neighboring quadrants, often there's a large mismatch in the ray density (I'm talking about angle, not slope). What I do is extend the quadrant with the lower ray density until it matches the density with its neighbor. This reduces the number of rays in areas where it is not important. I call it the "opticast" algorithm. : ) - I would be interested in reading this tutorial but it appears that Sven's site is gone. Has anyone got an archived copy?
- My server is currently beeing shifted.
I therefore added the attachment below.
Due to the size limit you have to download glut and libglee separately
Sven - Thanks, this looks interesting and helpful. You wouldn't happen to have the paper you wrote with it would you?
- Can you send me an email ? My server is still down but I can send you the paper. My email is svenforstmann * yahoo.co.jp
- The page is partially online again now:
http://www.gpstraces.com/sven/main/publications.htm
and
www.p0werup.de
Here a paper descibing a method similar to voxlap - very interesting to read.
http://www-dial.jpl.nasa.gov/~john/papers/realscene/realscene.pdf
Actually it seems to be patented
http://www.patentstorm.us/patents/5684935/description.htmlEdited by Spacerat at