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

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

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.

hdragon is working on raytracing for a collision method in our engine.

>>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 }

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.

>>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.

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?

University? We're still in high school! :D

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!

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...

Thanks, and good luck!

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.

>> 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?)

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?

>double dist = distRayPlane(Pos, velocity, pl.Normal, Dplane);
>if(dist < distRayPlane(Pos, velocity, pl.Normal, Dplane))

dist is never going to be less than itself

score 1 for perspective :D

I was thinking about telling him that in class today.... but... I decided it was best he find out his silly mistake for himself :D

No, I'm just kidding, I was just as oblivious as he was :D.

Quote:

Originally Posted by Perspective

>double dist = distRayPlane(Pos, velocity, pl.Normal, Dplane);
>if(dist < distRayPlane(Pos, velocity, pl.Normal, Dplane))

dist is never going to be less than itself

I kinda figured out. So all i have to do is determine the distance from the Original position till the plane's normal. Also, i have to check to see if the Origin position is inside the triangle or not (it is easier checking a rectangle than a triangle). Do you think you can help me figure out what the problem is?

There is a ray-to-triangle intersection algo somewhere on this board. Bob and I talked about it extensively in several posts. I would recommend searching for posts either started by Bubba or by Bob.

Yes, finally i've made it work. This is how it goes:

Code:

bool checkPointTriangle(vect3 Point, vect3 Pa, vect3 Pb, vect3 Pc) { double totalAngle = 0.0f; vect3 v1 = Point - Pa; vect3 v2 = Point - Pb; vect3 v3 = Point - Pc; NormalizeVect(v1); NormalizeVect(v2); NormalizeVect(v3); totalAngle += acos(dot(v1, v2)); totalAngle += acos(dot(v2, v3)); totalAngle += acos(dot(v3, v1)); if(fabs(totalAngle - 2*PI) < 0.005) return true; else return false; }

So, the Position of the object (a vector) will be check if it is going to be inside a triangle or not, then with a distance calculation from the position to the triangle's normal, collision will occur.

Is there anything else i should add into my collision code to make it faster?

EDIT:
If i have a model with multiple triangles, what vector on the model should i check for the collide triangles? A point in a model's triangle or a point on its face?

That acos() looks quite nasty. Anything you can do to get rid of it?

Quote:

If i have a model with multiple triangles, what vector on the model should i check for the collide triangles? A point in a model's triangle or a point on its face?

Could you please explain what you mean by this question?

I wrote this for determining if a point resides in a triangle...but this is also pretty nasty, and might actually be more expensive, but it works.

Code:

#include "CollisionDetectionPrimitives.h" extern std::ofstream trace; #define CCWPITDEBUG(x) x //Fixme: investigate to see how vector length plays into uncertainty here //Normal x DiffVector = InwardVector //InwardVector Dot Point >= 0 or >= -.0001 BOOL CCWPointInTri(float P1X,float P1Y,float P1Z, float P2X,float P2Y,float P2Z, float P3X,float P3Y,float P3Z, float NormalX,float NormalY,float NormalZ, float PointX,float PointY,float PointZ) { Vector3 Point1(P1X,P1Y,P1Z); Vector3 Point2(P2X,P2Y,P2Z); Vector3 Point3(P3X,P3Y,P3Z); Vector3 Normal(NormalX,NormalY,NormalZ); Vector3 Point(PointX,PointY,PointZ); Vector3 LocalPoint = Point - Point1; //The point in local coordintes with respect to a vertex Vector3 DiffVector = Point2 - Point1; Vector3 InwardVector(0,0,0); InwardVector = CrossProduct(&Normal,&DiffVector); if(DotProduct(&InwardVector,&LocalPoint) < -.0001f) { CCWPITDEBUG( trace << "Returning on first point" << "\n"; ) return FALSE; } LocalPoint = Point - Point2; DiffVector = Point3 - Point2; InwardVector = CrossProduct(&Normal,&DiffVector); if(DotProduct(&InwardVector,&LocalPoint) < -.0001f) { CCWPITDEBUG( trace << "Returning on seconed point" << "\n"; ) return FALSE; } LocalPoint = Point - Point3; DiffVector = Point1 - Point3; InwardVector = CrossProduct(&Normal,&DiffVector); if(DotProduct(&InwardVector,&LocalPoint)<-.0001f) { CCWPITDEBUG( trace << "Returning on third point" << "\n"; ) return FALSE; } return TRUE; }

That doesn't look so nasty. It's only subtraction's and cross product's. Shouldn't hit too hard.

while we're all in the mood for posting ray-triangle intersection algo's, here's mine. (I was forced to use this prototype, thats why i set the u, v, t params by reference). Also, this scence always had one object, that's why i just grab objects[0]. A better implimentation would pass the triangle as a paramater.

edit: oh btw: u and v are the "UV Coordinates" of the intersected triangle and t is the magnitude along the direction of the ray that the intersection takes place. So this algo doesn't just tell you if there is an intersection, it tells you the point on the triangle that the intersection takes place by setting the u,v, and t params (handy for phong shading or other types of lighting). Returns 0 if there is no intersection and 1 if there is.

Code:

// calculate ray - triangle intersection with backface culling int RayTracer::calcTriangleIntersection(const Ray& ray, const VertexList* face, float *t, float *u, float *v) { Point3f vert1 = scene->objects[0].vertices[(face->vertex)-1]; Point3f vert0 = scene->objects[0].vertices[(face->next->vertex)-1]; Point3f vert2 = scene->objects[0].vertices[(face->next->next->vertex)-1]; Vector3f edge1, edge2, tvec, pvec, qvec; float det, inv_det; // find vectors for two edges sharing vert0 edge1 = vert1 - vert0; edge2 = vert2 - vert0; // begin calculating determinant - also used to calculate U parameter pvec = ray.dir.cross(edge2); // if determinant is near zero, ray lies in plane of triangle det = edge1.dot(pvec); if (det < EPSILON) return 0; // calculate distance from vert0 to ray origin tvec = ray.start - vert0; // calculate U parameter and test bounds *u = tvec.dot(pvec); if (*u < -EPSILON || *u > det) return 0; // prepare to test V parameter qvec = tvec.cross(edge1); // calculate V parameter and test bounds *v = ray.dir.dot(qvec); if (*v < -EPSILON || (*u + *v) > det) return 0; // calculate t, scale parameters, ray intersects triangle *t = -edge2.dot(qvec); inv_det = 1.0f / det; *t *= inv_det; *u *= inv_det; *v *= inv_det; return 1; }

Quote:

Originally Posted by Bubba

That acos() looks quite nasty. Anything you can do to get rid of it?

Well, i can put it like this:

Code:

totalAngle += (acos(dot(v1, v2)) + acos(dot(v2, v3)) + acos(dot(v3, v1)));

Anyway, i have to convert the decimal to degree to make a full 360* circle. Then minus 2 PI. I don't know how can you clean it up if you need the function.

Quote:

Originally Posted by BobMcGee123

Could you please explain what you mean by this question?

I meant like this, I use a vector Pos, which i put in the glTranslatef() for testing. So all it does is check the Pos coordinate (x, y, z). Then i draw a triangle moved by the Pos coordinates. So, when i have more than one triangle, what point should i check so that all the triangle of the model can determine if it is inside/hit another objects.

>>
I meant like this, I use a vector Pos, which i put in the glTranslatef() for testing. So all it does is check the Pos coordinate (x, y, z). Then i draw a triangle moved by the Pos coordinates. So, when i have more than one triangle, what point should i check so that all the triangle of the model can determine if it is inside/hit another objects.
<<

Well, I didn't post the question but anywho...

You can ray trace against every triangle in the model, you can ray trace against a bounding volume of the model, or you can use a space partitioning algorithm to determine which triangles are in the same volume of space as your ray and test the triangles in that volume.

Those 3 options range from easy to difficult while simultaniously ranging from innefficient to efficient :)

That was suppose to be Bob, i messed up.

Anyway, if i ray trace every triangle of a model, it would be slow right?

About the bounding volume, if my model is really complex (curve, rectangles, all kind of stuff that make it look complex), do i have to find the center of the model? If the model is an aircraft with 2 wings on the side, would the bounding volume will make it look realistic.

The partitioning algorithm is something i have no idea, could you talk about it more.

I think he means something along the lines of checking whether or not two objects are even close to each other whatsoever...

If not they don't need to check collision between each other, saving valuable computation time :).

How to do it? You could just as well ask a monkey for the answer :d.

Quote:

Originally Posted by Shamino

I think he means something along the lines of checking whether or not two objects are even close to each other whatsoever...

If not they don't need to check collision between each other, saving valuable computation time :).

How to do it? You could just as well ask a monkey for the answer :d.

So by that, we can use the ray to determine if the object parallel to the others. Find the ray direction of the first object, and calculate. If it perpendicular to the other objects' normal, we have a parallel line and we don't have to run the calculation.

Well you could probably use an octree. Each leaf in the tree holds the vertices for that volume and each leaf is responsible for drawing itself. I'm not sure how to do this in a raytracer except that you wouldn't ray-intersect test any of the tri's in a leaf unless it passed certain tests.

I have very little experience with pure ray-tracing but I'm very experienced with ray-casting and vertical ray coherence. However ray-tracing is a whole nuther ball game since you basically are tracing a ray of light through pixel at x,y to completion.

I hope you get it working because I'm looking forward to seeing the final result.

Also a curve is simply a ray-to-sphere intersection test and you would want to break down the geometry into vertices if the sphere passed the test. Again I'm pretty much in the dark here with little experience in ray-tracing.

I was thinking like this:
The model contains certain number of triangles. Each triangle has 3 vertices, which will be vector3d. Then to move the whole model, i will add the velocity into each vector, so no matter what i do, the model will always be one part. Then i use those vector direction to check if it is intersect with anything in front in a certain distance. If there is nothing, the PointIntriangle checking will not be execute.

Now, i have to figure out how to pass the collision onto the object that had been collided. So it goes like this: a ship hits a meteoroid (the meteoroid's direction is same as the ship but slower. So basically the ship hits the meteoroid behind). The ship will change direction/ slow down, but how can i change the meteoroid's direction/ speed up because of the hit.

Object.Vector*=-HitPlane.Normal;

For physics you would need much more code to include weight, mass moment of inertia, etc,.