mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2008-01-24, 13:26   #1
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

23·17 Posts
Default Intersection with cubic

Hey, this topic could have been made under Programming, but I decided that this is more math centered.

Ok, I'm writing my own raytracer and it's basically finished. It's ~300 lines of C code. As you may guess/know, the most important step is to calculate the intersections with the ray and object(in this situation, cube).
The way I solved this now, is the most robust way:
1. I have calculated the vector(vec.x, vec.y, vec.z), I have the starting point(ray.x, ray.y, ray.z).
2. Add unit vector to current location and loop through every object to see if it is currently in the boundries of any cube(repeat #2 for x times):

SIZE is handeled by the C preprocessor and is replaced by an integer, let's say '40' in my case. This is in units.
It checks if all three coordinates are currently all within a single object and then returns the number of the object it hit, else it returns '-1'. This is rather impractical, but that's why I'm here, asking for your help :)

Code:
int collide(double ray.x, double ray.y, double ray.z)
{
    int i;
    for (i = 0; i < num_of_obj; i++)
    {
        if (ray.x >= objects[i][0] && ray.x <= objects[i][0]+SIZE)
        {
            if (ray.y >= objects[i][1] && ray.y <= objects[i][1]+SIZE)
            {
                if (ray.z >= objects[i][2] && ray.z <= objects[i][2]+SIZE)
                {
                    return (i);
                }
            }
        }
    }
    return(-1);
}
I read from an online tutorial, that the best way would be to use polynomial functions to detect the intersection.
The biggest negative side of my current solution is the inaccuracy: let's say the ray is very near to a corner of a cube, the ray might "jump" through the corner, if the vector is a bit too large.

Can anyone help me to figure out a (polynomial)function to get an intersection point? I guess the needed inputs would be:
*(vec.x, vec.y, vec.z) - current (unit)vector
*(ray.x, ray.y, ray.z) - current location of ray
and
*the locations of cubes are global variables, so they don't need to be an input, they could be accessed from objects[o][0..3].
*Size is also available as global.

I would be very grateful to anyone who feels like helping me out :)
PS! I have tried using google for this, but failed to get a straightforward answer :(
kuratkull is offline   Reply With Quote
Old 2008-01-24, 13:49   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22×1,471 Posts
Default

This post makes no sense anymore 'cause I didn't read the original question properly.

Last fiddled with by retina on 2008-01-24 at 14:20
retina is online now   Reply With Quote
Old 2008-01-24, 14:01   #3
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

23×17 Posts
Default

Umm, if you look at the code in my first post, you see that I'm using doubles.(i removed casts from the code, but they still exist in the arguments for the function).
It's just, that I calculate my vectors so, that the largest vector is always '1', and others are 0<=x<=1, since the cubes sides are all presented by decimal numbers, so a vector in decimal is a logical method(for example, it wouldn't be optimal to use 0.1 as the largest, because then the program would run 10x longer :/)
But still, a mathematical function would be the best solution.

PS! I am willing to change other parts(returns, arguments, etc.) of my code to implement this.

Last fiddled with by kuratkull on 2008-01-24 at 14:08
kuratkull is offline   Reply With Quote
Old 2008-01-24, 14:19   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

16FC16 Posts
Default

Quote:
Originally Posted by kuratkull View Post
Umm, if you look at the code in my first post, you see that I'm using doubles.
sorry, I didn't think to actually read your code

Now that I see what you are doing, I can see why you have such a problem. You are iterating through your ray at small increments! Wow, I have never seen that approach before. In that case I strongly suggest you find the line/plane intersection formula. Google for it or even better, write down the two equations for a line and a plane an equate the two together. Then solve for x and y and that is you intersection point. With suitable bounds checking of x and y you can detect arbitrary collision of any shape you chose to define that lies on the plane.
retina is online now   Reply With Quote
Old 2008-01-24, 14:26   #5
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

23×17 Posts
Default

Thanks!
Anyway, I tend to use the "code now, think later" moto, when coding...yes, i know it's not good.
I wasn't actually able to see all the problems that might arise when planning this, and because of that, I just went with the more robust solution, to learn as I go. And now when it's finished, I want to replace the weakest links and bottlenecks.
->
Now is the time I learn about the plane/line intersection formula :)
I will post here about my progress.
I still welcome other tips on how to accomplish this.
kuratkull is offline   Reply With Quote
Old 2008-01-24, 14:48   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

16FC16 Posts
Default

Of course in your case you will need 6 planes at right angles to each other each with a square defined as the intersection region. You will also need to solve for the ray intersection point so that you can detect if it intersects the plane behind your eye and is thus unseen. Later you can give the plane reflective properties and bounce the ray around the scene and/or map a picture into the seen region and give it some nice texture. Don't forget about specular highlights at reflective angles that pass close to to a light source since in the real world nothing can completely absorb light.
retina is online now   Reply With Quote
Old 2008-01-24, 14:54   #7
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

First, a "cubic", normally refers to "a cubic equation" (one of the third degree).
You are looking for intersections with a "cube" (a right- rectilinear solid whose faces are squares).

The traditional approach is to determine which, if any, face the ray first intersects.

But notice that each face is just a portion of a plane. Therefore, we can determine at what point the ray intersects the plane and then whether or not that point is a part of the face.

Start by describing the ray in parametric form (which it appears you have already done). R(t) = { Rx(t), Ry(t), Rz(t) } where Rx(t) = Rx0 + Vx * t, etc.

Now, if you have the luxury of selecting the cubes, you choose one oriented in an alignment parallel to the axes. There, one of the faces is described by the equation x=X, where X is a constant.

Now, our parametric ray intersects this plane at Rx(t) = X.
Solve for t. Substitute and determine Ry and Rz. If both of these are within the bounds of the face, there is an intersection.

Repeat as necessary for all other faces in the view.

Note that there are a number of ways to shortcut the testing in order to speed up the overall process. But here we are just discussing the underlying math.
Wacky is offline   Reply With Quote
Old 2008-01-24, 15:28   #8
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

23·17 Posts
Default

Wacky, yes I think I will use your suggested method, since It's easier to implement and is very suitable too.
I had thought about it, but in a slightly different manner, so It didn't seem to work :)
Thanks!
kuratkull is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Finding line intersection values? jvang Homework Help 5 2015-11-29 10:03
Efficient computation of cubic residue axn Computer Science & Computational Number Theory 2 2015-01-04 03:49
Circle intersection points Mini-Geek Puzzles 1 2006-11-27 03:20

All times are UTC. The time now is 07:08.

Wed Dec 2 07:08:53 UTC 2020 up 83 days, 4:19, 1 user, load averages: 1.76, 1.71, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.