Thread: 3D maze

I rarely post full code algos or even full algos on the board. It doesn't help for me to spoon feed information. Concepts are far more important than the code that implements them.

I've posted a ray to triangle intersection snippet here before as well as several other algos relating to graphics. I couldn't tell you which of my 2069 posts involve graphic algos, but I'm sure it's quite a bit of them.

Okay, just remember that's only an early rejection test not a complete collision detection method.

You want to be using your start point and endpoint, then, you send your final calculated collision position to gluLookAt (the point where you ended up actually colliding).

edit:
I'm cleaning my room to pack up for thanksgiving, but I'll gladly go on AIM and walk you through this.

Any three points in 3D space are guaranteed to be coplanar. But it's even easier than that. Since your walls are already flat then you know all points on the wall are coplanar.

Also we know that the dot product of two perpendicular vectors is always 0. Since this is true and since all your walls are planes themselves you can test whether or not any point is in the plane by a simple dot product. If the result is 0 then you know the point is on the plane. However, in 3D games this is RARELY EVER going to work out perfect since you will probably interpenetrate the plane or the wall.

The equation for a plane is A+B+C+D=0 or A+B+C=D.

It can be expressed in vector form as:

N dot P=0

Where N is the normal to the plane and P is a point on the plane.

The graph of a plane is:


N dot (P-P0)=0


Essentially if PO lies on the plane then the point P also lies on the plane if the vector formed from P-P0 is orthogonal to the plane's normal vector.

This results in the popular form: N dot P + d =0

d=-N dot P0

If the normal is of unit length then the above equation gives the shortest signed distance from the origin to the plane.

Ok now a,b,c form the component's of the plane's normal vector and d is the is the value we just derived from above.

From this proof we can see that:

if (n dot p)+d=0 then p is coplanar with the plane
if (n dot p)+d>0 then p is in front of the plane and in the plane's positive half space.
if (n dot p)+d<0 then p is in back of the plane and in the plane's negative half space.

The D3DX library provides functions to compute all of this but since you are not using Direct3D I will write the C function here.

Code:

typedef struct Plane
{
  float a,b,c,d;
}
 
void VectorDotPlane(Plane P,Vector3 V)
{
  return ((P.a*V.x)+(P.b*V.y)+(P.c*V.z)+(P.d))
}

Not if you use the A+B+C=D.

That doesn't negate D.

So:

Code:

....
 
  return ((P.a*V.x)+(P.b*V.y)+(P.c*V.z)-(P.d));
}

A+B+C+D=0

D must be negative in this case, because:

d=-N dot P0

If the normal is of unit length then the above equation gives the shortest signed distance from the origin to the plane.

That's actually the distance from the point to the origin, and there's a crucial distinction, because if you started at the origin, then traveled d units in the Normal direction, you dont' end up at P, you end up on the other side of the origin, and that's why it was so hard for me to visualize starting off. The only reason they do this is so that they can add in the plane equation, instead of subtract (add a negative instead of subtract a positive).

It doesn't really matter, he'll get used to both, but we might have to start drawing pictures.