# Ray tracer and collision detection

Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last
• 12-30-2005
hdragon
Ray tracer and collision detection
Ray tracing and collision detection are...well, kinda messy. I've read some of the tutorials online and always asked myself: where and when the heck ray tracing is going to start? and how do they know which direction it will go. After a little digging and sticking my brain into the computer's monitor, i've finally understand something.

This is basically what i understand. If it is not a good way to do it, please give advice.

So the ray will have a start point and end point. The start point will be the position of the tangible object, and the end point will be where it goes to. To determine the direction of the ray, the object's velocity will be add to the object's position:
Code:

```Vector3d startPoint, endPoint, velocity(1, 1, 1); endPoint = startPoint + velocity;```
With this kind of calculation, every step (or frame) the object moves, it will calculates if the end point will hit anything when the velocity added to the object's position. (i don't know if this is a good idea to do it, but it is pretty simple).

Well, ray tracing will be useful for collision detection in 3d space. My problem is (i forgot some of the stuff from geometry) determine the plane in 3d space. I've been looking all over the place and found out: the plane's equation is
Code:

`Ax + By + Cz + D = 0`
It looks simple but what the heck is it mean. I know the x, y, z stands for the coordinate but what is 'D' stand for? Can anyone please tell me how does the plane works in 3d space? Thanks
• 12-31-2005
VirtualAce
But for computer graphics you will want this:

Ax + By + Cz=D

So that D's sign is not flipped.

Ray tracing is a bit more than that. It basically traces a ray of light that goes through pixel x,y at a set angle. It then calculates what, if anything, the ray hits and how much it's light properties are affected. By knowing the materials of the objects it hits, you can gradually change the light properties of the ray using color equations.

There are several types of intersections to test for but the basics will give you a complex scene since most scenes are just large collections of simple objects
• 01-01-2006
VirtualAce
I think someone here has coded a raytracer program. They traced a cool looking pic of a teddy bear or something. I'm not sure if was Perspective or not.

You might want to do a search.
• 01-05-2006
Shamino
hdragon is working on raytracing for a collision method in our engine.
• 01-05-2006
BobMcGee123
>>stands for the coordinate but what is 'D' stand for?

The closest distance from the origin to the plane.

The dotproduct between a point and a plane normal, minus 'D' gives the distance from the point in question to the plane.

If this value is > 0, the point is in front of the plane, if this value is < 0 the point is behind the plane.

If this value for the start point is > 0, and the value for the end point is < 0, then the ray intersects the plane.

You can find the point of intersection by using the ratio of the start distance to the total distance (absolute values) as a linear interpolation factor to determine the XYZ of where the ray hits the plane.

Code:

```Vector3d startPoint, endPoint, velocity(1, 1, 1); endPoint = startPoint + velocity; float startdist = dotproduct(plane.normal,startPoint) - plane.D; float enddist = dotproduct(plane.normal,endPoint) - plane.D; if(startdist > 0 && enddist < 0) {   vector hitpoint;   startdist = fabs(startdist);   enddist = fabs(enddist);   float iTotalDist  =  1 / (startdist + enddist); //inverse total distance   float InterpValue = startdist * iTotalDist; //otherwise we'd just divide here, startdist / TotalDist   hitpoint = startPoint + (endPoint - StartPoint) * InterpValue; } else {  ;//doesn't cross plane }```
• 01-05-2006
Sang-drax
Quote:

Originally Posted by BobMcGee123
>>stands for the coordinate but what is 'D' stand for?

The closest distance from the origin to the plane.

No. Consider the plane

2x + y + 2 = 0

What is its closest distance to the origin? It's not 2. The point (-1,0,0) is on the plane and its distance to the origin is 1. The smallest distance is less than that (draw a figure).

EDIT: perhaps I should add that the closest distance to the origin is

D / sqrt(A^2 + B^2 +C^2)

so for normalized (A,B,C) your statement is true.
• 01-05-2006
BobMcGee123
>>so for normalized (A,B,C) your statement is true.

And, plane normals are always normalized in the paradigm of game programming, that's a safe assumption you can always make...therefore in this context what I said is correct. Whatever source he referenced from is describing what I said, and you are crossing some useless crap from a university text book with game programming.

The equation he described is the dotproduct between the normalized plane normal and some point on that plane, which will *always* give the closest distance from the origin to the plane. Always.

And the next time you suggest I draw a diagram I am going to kill you.
• 01-05-2006
hdragon
Ok, i think i'm being dumb here. What i don't understand is the Plane normal. So if i say like this:
Code:

`plane.normal(-1, 0, 0);`
What does it mean?

So the plane normal only contain 1, 0, and -1. This is the plane normal code i found on nehe.gamedev.net about the plane's normal and its position:
Code:

```struct Plane {                 TVector _Position;               TVector _Normal; }; Plane pl1,pl2,pl3,pl4,pl5; void InitVars() {         //create palnes         pl1._Position=TVector(0,-300,0);         pl1._Normal=TVector(0,1,0);         pl2._Position=TVector(300,0,0);         pl2._Normal=TVector(-1,0,0);         pl3._Position=TVector(-300,0,0);         pl3._Normal=TVector(1,0,0);         pl4._Position=TVector(0,0,300);         pl4._Normal=TVector(0,0,-1);         pl5._Position=TVector(0,0,-300);         pl5._Normal=TVector(0,0,1); }```
could you explaine for me more about the plane normal?
• 01-05-2006
Shamino
University? We're still in high school! :D
• 01-05-2006
Junior89
Lol, i hate Geometry :( Bad Teacher. Good luck with your project! I have a quick question perhaps someone could PM me or just make a quick post, i dont want to interrupt :) How do you go about using 3D objects in programming code? You make them in 3D programs im sure but how do you go about bringing them into the code? I have done a few little 3D things in Blender 3D, with the Yafray Raytracer. Perhaps if you could find the source code fo the raytracer implemented in that program it could help? I dont know, just offering a possibility, and a question. Good luck and thanks!
• 01-05-2006
Shamino
Well to bring 3d models into your code you simply have to set up all the data structures that the model file (.3ds) has in it already, and basically you copy all information from the file into memory (your new storage structures..)

We're using MS3D Models in our project...
• 01-05-2006
Junior89
Thanks, and good luck!
• 01-05-2006
VirtualAce
In Bob's defense there is nothing wrong with what he said as it relates to game programming. It may not be accurate for classroom math, but plane normals are ALWAYS normalized in 3D graphics. Storing them any other way would bring the system to a crawl as it attempted to re-normalize every frame. D3D does do a re-normalization but I think somehow the hardware plays a role in it and I'm sure it does not re-normalize every normal in the game per frame.

Sometimes the normals do get out of wack and end up pointing the wrong direction, thus making then abnormal (no pun intended). So re-normalizing them fixes this. There are a lot of calculations and transformations going on and sometimes the underlying data gets hosed to the point it's not useable after a few hundred or a few thousand iterations. Floating point creep and the like all contribute to the problem.

But what Bob said is completely accurate. The statement about the dot product is the exact same process that Direct3D uses to determine camera-facing triangles as opposed to those not facing the camera.

And notice this:
Quote:

hitpoint = startPoint + (endPoint - StartPoint) * InterpValue
Is what I've been talking about in a great many threads here.

LIvalue=value1+value_interp*(value2-value1)

or

hitpoint=startPoint+InterpValue*(endPoint-startPoint);

They yield the same result.

Code:

```fld [endPoint] fsub [startPoint] fmul [InterpValue] fadd [startPoint]```
This is a fast linear interpolation in assembly using only the FPU.
This can also be done in modern pixel shaders although I would probably only do it in a vertex shader.
• 01-08-2006
BobMcGee123
>> What does it mean?

Normalis, latin, literally means perpendicular...a plane normal is the vector that is perpendicular to the plane.

>>So the plane normal only contain 1, 0, and -1

Except that the vector <1, 0, -1> doesn't have a length of 1...the unit vector in that direction would be <.7071, 0, -.7071>

>>could you explaine for me more about the plane normal?

I think you need to access more resources about basic 3D math. Why not start here:

http://chortle.ccsu.ctstateu.edu/Vec...ctorIndex.html

You can do a google or amazon search and quickly find an assload of material on the subject. I suggest reading some rudimentary sources but then come back to our explanations as they relate to game programming (eventually the light will turn on, I promise).

>>University? We're still in high school!

The school of high people.

Quote:

How do you go about using 3D objects in programming code? You make them in 3D programs im sure but how do you go about bringing them into the code? I have done a few little 3D things in Blender 3D, with the Yafray Raytracer. Perhaps if you could find the source code fo the raytracer implemented in that program it could help? I dont know, just offering a possibility, and a question. Good luck and thanks!
I have written code for just a couple of formats: MS3D models and quake3 BSPs. You need to write code that loads a model from a file (or just use loading code from one of the many tutorials online). You need to know how to use the data.

Quote:

Well to bring 3d models into your code you simply have to set up all the data structures that the model file (.3ds) has in it already, and basically you copy all information from the file into memory (your new storage structures..)

We're using MS3D Models in our project...
Yeah

Quote:

It may not be accurate for classroom math, but plane normals are ALWAYS normalized in 3D graphics
Yeah

Quote:

D3D does do a re-normalization but I think somehow the hardware plays a role in it and I'm sure it does not re-normalize every normal in the game per frame.
Yeah, I'm pretty sure you can turn this on and off, at least you can in OpenGL. You only really need forced renormalization in some pretty arcane scenarios, i.e using a scalaing matrix to modify a mesh before sending it to the rendering API. Incidentally this is the first thing described in OpenGL.org's 16 common pitfalls to OpenGL programming.
http://opengl.org/resources/features...es/oglpitfall/

You really do like assembly don't you bubba? I wish I had gotten more masterful with it. Have you used any old/arcane instruction sets (something other than x86 or the x87 FPU inst. set?)
• 01-10-2006
hdragon
Ok, after a while, i figured out the theory about collision detection/ray tracing.

For each triangle, i set a plane normal for it and declared 3 vector points.
Then i create an object vector3d point, as well as velocity.

so this is how it goes:
Code:

``` struct Plane {       vect3 Normal; } Plane pl; vect3 Pos, velocity;  //position and velocity of player object vect3 IP; //intersection point; vect3 p1, p2, p3;  //3 points for the triangle double Dplane;```
Then I calculate the distance of the vector to the plane (which will be the triangle i created using p1, p2, p3)

Code:

```double DistRayPlane(vect3& Origin, vect3& velocity, vect3& PlaneNormal, double& D) {   double Delta;   double cosAlpha = dot(velocity, PlaneNormal);   if(cosAlpha == 0) return -1.0;  //when it is parallel, do nothing     Delta = D - (dot(Origin, PlaneNormal)); return (Delta/cosAlpha); }```

After that, here will be another function to determine if the Pos vector will be inside the triangle (p1, p2, p3) at the IP point.

Code:

```bool PointInTriangle(vect3& Point, vect3& v1, vect3& v2, vect3& v3) { double Angle; vect3 vt1 = NormalizeVect(Point - v1); vect3 vt2 = NormalizeVect(Point - v2); vect3 vt3 = NormalizeVect(Point - v3); Angle = (acos(dot(vt1, vt2))+ acos(dot(vt2, vt3)) + acos(dot(vt3, vt1))); if(fabs(Angle - 2*PI) < EPSILON)     return true; else     return false; }```
So this is all set...I think. All i have to do is calculate the direction of the object, then check to see if it is inside the triangle or not when the IP hit the plane.

in the InitGL i set the value for the vectors
Code:

``` pl.Normal = vect3(-1, 0, 0); Pos = vect3(0, 0, -50); velocity = vect3(1, 0, 0); p1 = vect3(0, 10, -45); p2 = vect3(0, -10, -40); p3 = vect3(0, -10, -50); Dplane = 1;```

Then, in the draw function i set up the triangle and set normal for everything i needed to.

Code:

```                glLoadIdentity();         glTranslatef(10, 0, 0);         glBegin(GL_TRIANGLES);                 glColor3f(1, 1, 1);                 glNormal3f(-1, 0, 0);                 glVertex3d(p1.x, p1.y, p1.z);                 glVertex3d(p2.x, p2.y, p2.z);                 glVertex3d(p3.x, p3.y, p3.z);         glEnd(); //then draw the rectangle         glLoadIdentity();         glTranslated(Pos.x, Pos.y, Pos.z);         glBegin(GL_QUADS);                 glColor3f(1, 0, 0);                 glVertex3f(1, 1, 0);                 glVertex3f(-1, 1, 0);                 glVertex3f(-1, -1, 0);                 glVertex3f(1, -1, 0);         glEnd(); double dist = distRayPlane(Pos, velocity, pl.Normal, Dplane);       if(dist > 0)       {         if(dist < distRayPlane(Pos, velocity, pl.Normal, Dplane))         {         IP = Pos + velocity*dist;                 if(VertexTriangle(IP, p1, p2, p3))                         {                       //collision                         }           }       }```
So when the distance is bigger than 0 and the distance is still smaller than the distance the object has to travel, the Intersection point will be add in. And when the IP point is inside the triangle, collision will occurs.

Well, the problem is it did not work. The object goes right through the triangle. Did i do something wrong or my calculation is wrong?
Show 80 post(s) from this thread on one page
Page 1 of 3 123 Last