mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Intersection with cubic (https://www.mersenneforum.org/showthread.php?t=9908)

kuratkull 2008-01-24 13:26

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);
} [/code]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 [U]very grateful[/U] to anyone who feels like helping me out :)
PS! I have tried using google for this, but failed to get a straightforward answer :(

retina 2008-01-24 13:49

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

kuratkull 2008-01-24 14:01

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.

retina 2008-01-24 14:19

[QUOTE=kuratkull;123791]Umm, if you look at the code in my first post, you see that I'm using doubles.[/QUOTE]:blush: sorry, I didn't think to actually read your code :blush:

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.

kuratkull 2008-01-24 14:26

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.

retina 2008-01-24 14:48

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.

Wacky 2008-01-24 14:54

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.

kuratkull 2008-01-24 15:28

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!


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

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