20080124, 13:26  #1 
Mar 2007
Estonia
2^{3}·17 Posts 
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); } 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 :( 
20080124, 13:49  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{2}×1,471 Posts 
This post makes no sense anymore 'cause I didn't read the original question properly.
Last fiddled with by retina on 20080124 at 14:20 
20080124, 14:01  #3 
Mar 2007
Estonia
2^{3}×17 Posts 
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 20080124 at 14:08 
20080124, 14:19  #4  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
16FC_{16} Posts 
Quote:
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. 

20080124, 14:26  #5 
Mar 2007
Estonia
2^{3}×17 Posts 
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. 
20080124, 14:48  #6 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
16FC_{16} Posts 
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.

20080124, 14:54  #7 
Jun 2003
The Texas Hill Country
3^{2}·11^{2} Posts 
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. 
20080124, 15:28  #8 
Mar 2007
Estonia
2^{3}·17 Posts 
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! 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Finding line intersection values?  jvang  Homework Help  5  20151129 10:03 
Efficient computation of cubic residue  axn  Computer Science & Computational Number Theory  2  20150104 03:49 
Circle intersection points  MiniGeek  Puzzles  1  20061127 03:20 