3D maze

[MethodMan]

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

[Darkness]

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

[linuxdude]

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

[RoD]

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

[Darkness]

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.

[RoD]

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

[Darkness]

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

[RoD]

no big

[VirtualAce]

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.

[Darkness]

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.

[VirtualAce]

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.

[Darkness]

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.

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.

[VirtualAce]

Since you insist on arguing with me:

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.

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

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

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.

[Darkness]

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.

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.

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.

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.

[VirtualAce]

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.