3D maze

Hi,

I want to try and create a 3d maze, with walls, and a floor, but with an open ceiling. If I have an object (a sphere) how is the easiest way to go about testing if the object hits a wall, so it doesnt go through it?

Thanks

;) Hmm, there are several methods of doing this. 3D collision detection is not an easy subject. What data does your program have access to? I.e, are your mazes simply comprised of triangles? Is your maze going to be axially aligned, or can the orientation of the walls and floor be completely arbitrary?

here is a tutorial which essentially implements what you want, but the mathematics behind it isn't exactly easy (I don't know what your math background is). I suggest trying to read and understand the equations and algorithm, and if you don't understand it I can try to explain it to you. Note that this tutorial talks about a sphere intersecting triangles, and something called the "2PI summation method" to determine if a ray strikes a triangle.


The one I am referring to is at the bottom of this page:
http://www.gametutorials.com/Tutoria...OpenGL_Pg3.htm

Try to read it before asking questions, but I'll gladly explain if you need it.

Also note that relatively speaking, this algorithm is expensive because it requires many calls to the trigonometric functions, and square root functions (they are typically the slowest math functions that exist, and if you call it too much you may get a speed slowdown).

well are you using raycasting or not? that could help out if you are

Just reasearch collision detection, theres a topic all the way at the top of this forum thats loaded with awsome links.

Would you mind posting the link to that thread for him/her? I looked but I'm not sure which you are referring to.

Thanks.

http://cboard.cprogramming.com/showthread.php?t=33318

Ohh, I thought you said the bottom for some reason, didn't realize you meant the sticky... :D

no big

If all you need is to test against a plane then create a plane from your wall and do a ray to plane intersection test. A very simple test is a dot product test. If the result of the dot product is >0, or the vectors are pointing in somewhat the same direction, then you know you are on the near side of the wall. If its <0, or the vectors are nearly pointing in the opposite directions then you are on the far side of the wall. Your normal setup though can differ so it must be so that the normals point towards the camera if the quad or tri in question is facing the camera. If your setup is reversed then simply alter the two tests - <0 and >0 take on the opposite meanings.

D3DXVECTOR3 WallNormal;
D3DXVECTOR3 Camera;

D3DXVec3Normalize(&Camera,&Camera);

float dot=D3DXVec3Dot(&WallNormal,&Camera);

if (dot<0)
{
//camera is on far side of wall
} else //camera is on near side of wall

Note that this does not guarantee pixel perfect collisions. But it does test whether or not you have penetrated the wall in question in the previous frame. To test for pixel perfect, you must find the point at which your camera ray intersected the plane in question. Back the camera up to that point, compute the collision response, and move on.

Here is the equation for intersection of ray and plane. This is easier to do in a maze because we know that all walls will form a plane so there is no need to do an expensive ray to triangle test.

Ray: p(t)=p0+td
Plane: p dot n=d

Equation: t=(d-p0 dot n)/(d dot n)

If ray is parallel to plane or (d dot n)=0 then there is no intersection.
If (d dot n)<0 then intersection during interval.

You can solve for p0 which is actuall p0.x and p0.y in this equation as well. This has been solved for t to test for intersection in this time interval. The nice thing about this is the dot product test and point test are rolled up in one algo. If the first time interval test passes, you can then solve for p0.

I am a little bit confused with what you are saying Bubba. Planes are infinitely large, and just because you've collided with a plane doesn't mean you've collided with the geometry you've setup.

On the same site I posted above, there's an algorithm for testing for collision against sets of planes. You can't trust on colliding against just one plane, because while you may be colliding with the plane, you might not be colliding with, say, the actual wall, because the plane extends to infinity.

In the picture I've posted, you want to move from the green sphere to the pink sphere. The red thing is the plane that represents one of the sides of a wall. The wall is the black thing, and it's just one wall that you might find in a maze.

The movement from the green point to the pink point clearly intersects the plane, and the intersection point is marked as the blue line. However, you clearly don't intersect the wall. To see if you intersected the wall, you use the algorithm posted on the main page of gametutorials, the actual link is here:

http://www.gametutorials.com/Tutoria...OpenGL_Pg5.htm

note that it is for the computer game quake3, but as long as you have sets of planes that represent the geometry (in this case, 6 planes for the wall in 3D), and as long as the planes point out from the geometry, the algorithm will work.

True, but if you are on the front side of the plane in question then you still have not collided with or penetrated the wall even if the plane extends to infinity. I would say my post was more towards trivial rejection than the actual expensive test. Either way once you know where you have intersected the plane, then you can test those coords against the extents of your actual wall. But again you must eliminate geometry if you have a lot of it in your maze. You wouldn't want to test every wall in the maze on every frame or even every wall in the frustrum in every frame. As well you don't need to test against portions of the wall you cannot see. Testing against 6 planes, when only a fraction of those will be visible at any one point in time is overkill. Only test planes that first are facing the camera - if they are not then don't test them. This is a simple dot product. Then only test the plane the wall lies on if and only if the wall in question is close enough to the camera or the player to be intersected in the current frame. If it is, then plane test it and check the coords where you would intersect the plane against the extents of the wall that lies on the plane. There are several ways to do this.

But whatever approach you take, elimination of unnecessary geometric tests is vital to maintaining an interactive framerate.

Quote:

---

True, but if you are on the front side of the plane in question then you still have not collided with or penetrated the wall even if the plane extends to infinity. I would say my post was more towards trivial rejection than the actual expensive test.

---

Okay, I guess that aspect of it makes sense...but trivial rejection is included in that algo I posted anyway. That algo I posted for the quake3 collision detection only needs dotproducts, and then multiplications, in order to do its business. Plus, you don't need to overlap the plane in order to collide with it: that algo computes where you would hit the plane anyway (otherwise, with overlap tests, you can get inter-object pass-through). Also, there's no such thing as an inexpensive collision detection system that actually works. I suggest you read it if you haven't.

Quote:

---

You wouldn't want to test every wall in the maze on every frame or even every wall in the frustrum in every frame

---

You only use the frustum for rendering culling anyway, not collision culling. I highly doubt this is a problem for a simple 3D maze, but most computer games use spatial partitioning, i.e quake3 either uses bsp or octree or something like that, don't remember which.

Since you insist on arguing with me:

Quote:

---

You only use the frustum for rendering culling anyway, not collision culling.

---

This is true in certain cases, not all. And my point was that the more expensive collision test should be done after you have narrowed down the geometry to those triangles, quads, etc, that could in fact collide in the next frame. Because per pixel and per unit testing is so expensive elimination of the geometry is vital - which is what I said earlier. Also the algo we are discussing is not special by any means and there are about a thousand ways to accomplish what it does.

Quote:

---

Also, there's no such thing as an inexpensive collision detection system that actually works.

---

Quote:

---

But whatever approach you take, elimination of unnecessary geometric tests is vital to
maintaining an interactive framerate.

---

Quote:

---

I would say my post was more towards trivial rejection than the actual expensive test.

---

Is this not what I said? But you must do the expensive test last after you have eliminated unnecessary geometry. Whatever your issue is with my posting I suggest we discuss it elsewhere as continually arguing over the same principles, albeit approached from different frames of reference, is not going to help anyone.

Quote:

---

Since you insist on arguing with me:

---

I'm not arguing with you in the way that you think. You are posting things that I find are inaccurate or incomplete. This is a learning environment, so I suggest you get used to constructive criticism. You are a good programmer, but also the most touchy, just relax and look into what I am saying, because I also know a thing or two as well.

Quote:

---

This is true in certain cases, not all

---

Again, frustum culling has nothing to do with collision culling that I can see...what if you want to move backwards? Does that mean you dont' test against the geometry behind you, because it's not in the frustum? If there IS a special case where I'm wrong, you should have posted it.

Quote:

---

And my point was that the more expensive collision test should be done after you have narrowed down the geometry to those triangles, quads, etc, that could in fact collide in the next frame

---

This algorithm is faster because you don't ever actually test against triangles. Read the algorithm, you don't test against 'non visible' faces, there's trivial rejection built in, I'll expand on this at the bottom.

Quote:

---

Also the algo we are discussing is not special by any means and there are about a thousand ways to accomplish what it does.

---

I disagree, I think it's a very clever algorithm, it's computationally very fast, and it's accurate. It encapsulates trivial rejection, it works against arbitrarily complex geometry, and it only really uses dotproducts and multiplication. The only catches is that you must have a hull that is convex and that it only works against static geometry.

This is where I said I would expand
I don't think I addressed the speed issue enough. For every plane in the geometry using the algo I posted, you need to compute dotproducts for the startpoint and endpoint of the move. Then you need to do a reciprocal calculation, then some multiplications to get some fractions, and you toss these fractions around to determine whether or not you hit the geometry. During the algorithm, if the start point's distance and the end point's distance to a given plane is positive, you exit the testing because you are in front of a side and could not have collided. If they are both BEHIND a given plane, you continue onto the next plane as you dont' need to worry about the 'non visible faces' :) This is actually what you've suggested about 'skipping the non visible faces' and what not, but you didn't read the algo.

What you suggest is that you try to find which planes you are in front of (which ones are 'visible'), as you correctly stated that these are the only actual sides you would collide with. This means that you have to either

A) take the dotproduct for every plane with the startposition

B) only take dotproducts until you've got the maximum number possible visible faces given the number of sides (which involves lots of if testing during a for loop)

Then, once you've got this data you then have to do the actual per-polygon testing. But, even the relatively fast version of the per-polygon checking that you posted (which I've never actually seen work and I believe you have said you haven't actually implemented it yet) seems very expensive compared to the algo I posted.

The algo I posted some time back was from Graphics gems and developed by a programmer who used it inside of a game. So I'm sure it's fast enough. Basically that algo does a ray to triangle test and then computes the barycentric coords of the ray inside of the triangle. It will also bail on NAN's which can cause problems. It only uses dot products as well. But as I said there are a lot of algos out there which is why there have been several books written on just graphics algos, and now on pixel-shader algos. There's always something faster or more exact.

Now that you have explained yourself I understand what you are talking about. But again this comes down to a question of the best way to do it and this poster simply wants to know one way to do it. I don't always post the fastest methods here simply because optimizations often obfuscate the actual algo behind the code which is not my goal. And it's very hard to explain these algos on a text message board and even reading back through some of my posts I can see areas I've skipped.

But c'mon man you could write an entire book on some of these questions and I really don't want to do that here. I'm really not a touchy programmer but I dislike being questioned mid-post when the only reason behind it is simply because you have a faster algo. Perhaps if your approach were different I would respond differently. I would love to talk with you about code and graphics algos as you have a lot to offer and even though I do know a lot about it, there is always more to learn. PM me and we can hook up either MSN messenger or teamspeak which would allow us to talk instead of type.

I think we've covered the issue quite well though in this post.

Quote:

---

I'm really not a touchy programmer but I dislike being questioned mid-post when the only reason behind it is simply because you have a faster algo

---

The reason I questioned you was because you never actually posted a full algorithm for doing a collision test, only a trivial rejection.

Quote:

---

Perhaps if your approach were different I would respond differently

---

I'm doing an exceptionally good job as far as I'm concerned, but thanks

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.

To the original poster: have you made any progress? Are you still even following the thread? :(

>>To the original poster: have you made any progress? Are you still even following the thread?

I had no time to start, but have read some of the post and have looked at some tutorials.

My walls in the maze are constructed of polygons, so 1 polygon for each wall.

I will try to attempt Bubba's idea, with a ray intersecting a plane.

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

I was reading on nehe

You test whethere the ray intersects a plane, and then you know that point, and then you can check if that point is on the polygon of the wall.

Just wanted to clarify.

I have a lot of polygons, one for each wall in the maze, each with a normal.

My camera is on the player, kind of like a first person view. I need to create a ray to see if it intersects the plane (wall). Would I be using values from the gluLookat in order to test whether the ray intersects the plane?

Edit:

I found this site:

http://www.cs.montana.edu/~charon/th.../collision.php

Using what they suggest, you will find out the distance to the intersection point. I would then have to test to see if the point is acutally on the plane of the polygon.

Im a bit confused.

How do I get any information as to which plane/polygon I will be testing on. Im not really afraid of losing some speed by testing every wall, since there wont be that many.

Im not sure how you create a plain on the polygon to test it against.

Thanks again

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

---

arg, I was really, really, really hoping you wouldn't post that form of the plane equation, it accomplishes the same thing but only confuses someone starting out. The d is computed with a normal vector which is anti parallel (the negative of) the actual normal, which is why I hate that form of the plane equation.

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

---

Quote:

---

A+B+C+D=0

---

D must be negative in this case, because:

Quote:

---

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.