Sign in to follow this  

Where does ray within a cube intersect that cube?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm prototyping a voxel, but I've got to resolve something before I can proceed. It was easy to use trig to make a function to determine which face is hit (and where) by a ray projected from a point and given an angle within a 2D square... quite simple... but the routine I made is a hack and uses lots of if's, which aren't going to be easy to upgrade to 3D... So the question is: is there a simpler way to determine which face was hit and where given a point and two angles (yaw/pitch) from within a 3D cube?

Share this post


Link to post
Share on other sites
My typical approach to this is to store all of my rays in point-vector format rather than point-theta-phi format. It is then easy to do a Kajiya-style slab hit test with the ray and the faces of the cube. I believe Jensen has some code in one of his photon mapping articles that is great for converting to and from point-theta-phi and point-vector. Once you have that conversion the slab test is simple and easy to optimize. This is a good description of the Kajiya slab method. If your origin is guaranteed to be inside the original cube, there are some simple and obvious optimizations to the slab approach that should significantly improve performance.

Share this post


Link to post
Share on other sites
i'm finding intersections with cubes in lattice iteratively
edit:i'm calculating some things per ray and then in the raymarching loop i have very little number of calculations per voxel.Alot less than if i would do ray-cube intersection. I'm finding intersection with planes x=0,y=0,z=0,and then i'm selecting closest one. At each step,i'm finding next intersection with plane that are parallel to plane i intersected in previous step , and selecting closest intersection comparing to recent intersections with other planes.... to be more specific,
i have 3 variables ,one stores intersection with X=N planes,other with Y=N, third with Z=N (position and distance).
There,N is a integer.
So my code works like
loop
i'm selecting nearnest,
doing work with it,
then i'm stepping that nearnest point by some value so it's intersects next plane
endloop.

but probably it's too hard for beginner.

[Edited by - Dmytry on August 20, 2004 8:05:58 AM]

Share this post


Link to post
Share on other sites
Thanks, I'll look at some of these and see what I can find.

About the yaw/pitch thing, the way I march thru the world grid (which will ultimately be an octree) is by using an angle and a edge modulous... This reduces my math to two multiplies and a handfull of add/sub's + a few branches for each actual 3D cube step. It's also convenient for constructing the virtual lense, so-to-speak... I know point+vector is probably easier, but it doesn't serve me well here, tho truly, all I need is to seed my main routine with the proper data (two angles and a point on a specific face of a cube).

I like this technique because it doesn't miss corners, etc, but it's a bit slow. I've added some classic optimizations, like when the ray enters one face and exits to the same face of the next cube, it only does addition until it hits a face perpendicular to the one it entered, and in that case, it already knows where it hits in the next cube over, so only one multiply and add, heh. The routine also knows not to test ray/ground intersection if the cube it's in knows that the ray is above it's higest contained point, etc...

The routine itself isn't an iterative process (it doesn't use one loop to march). It actually uses 6 static pieces of code designed to handle a ray originating from any of the 6 sides of the cube. Those pieces jump to one-another, so it's the same as a loop, tho it's path is never so clear heh. It uses boolean flags (set to indicate facts about the input u/v angles -- one reason I use 'em) to determine which face will be hit before computing where.

Still, the routine isn't fast enough... Hopefully, the octree will improve that, and integerization, and I'm also going to add some trace caching stuff so it can skip all the iterative marching steps up until the very last one for known good (but uncomputed) hits, etc.. all very fun stuff..

Anyone with voxel experience have any opinions on what I could do to improve speed? All the tutorials I've run across are either too amateur to be useful for optimizing, or aren't concerned with speed at all... I want this to run in realtime, but at the moment, it struggles for 5 to 10 fps at 160x120! hehe...

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

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