Thread: Ray tracer and collision detection

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:

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.

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.

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

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

Yeah

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?