

Advanced 3D Collision Detection

Hi all,
I've been working on my own 3D game engine with XNA, but I haven't gotten too far because of collision detection. I'm at the point where I need to take a box that represents the player as well as the player's movement, and use it to find the furthest it can travel before intersecting with the world, composed of triangles. Basically, it's a sweptbox/triangle collision that returns the time [0,1] until it hits something (1 if it made it to the target). I've searched all over the internet, but all the methods that I've used either result in false positives or false negatives.
I'd really like to figure this out, because I have a pretty interesting idea for a futuristic multiplayer deathmatch.




Re: Advanced 3D Collision Detection

Looks like you are stuck where most people get stuck in 3d games. Collision is not easy. First of all you need a triangle intersection method that will tell you when you have intersected with a triangle. You can download some really eligant code from zippys, just google xna triangle intersection and click on the zippy link. Next you have to create a vector/ray and calculate if it intersected with a triangle. Sounds easy? Not! This requires running this method on every triangle in your world. If your world is tiny and I mean TINY, then you wont need a quadtree or octree, but more than likely you will. 3d worlds really need an octree. The octree will break your world into 8 cubes, there for only calculating triangle intersection on 1/8th of your world at a time and increasing your performance. Most octrees dont stop at the first branch, many will break 1 cube into 8, then 1 of those 8 into another 8 and so on until they have as little triangles as possible to calculate intersection on. I have found that 3000ish triangles per cube is nice on performance. So there you go, once you have a working octree, you can calculate your intersection on your triangle, which will give you an x,y,z cordinate of intersection, subtract that from your player position x,y,z to get distance. Then its up to you to decide how long you think it took to get there, because in the game world its instant (one frame) and your done. I failed to mention you can create bounding spheres, bounding boxes, and shoot a ray/vector into them to dectect collision as well, although this wont help you with triangle collision.




Re: Advanced 3D Collision Detection

Well, I found a really fast ray/triangle intersection, and I'm not worrying about octrees right now (my world is a box with a pillar in it). However, the way you mention doesn't take into consideration the fact that the player in my case is represented as a box. A simple example where ray/triangle would fail for this would be a wall with a narrow slit in it. The ray that represents your movement will go through, but the box shouldn't. Also, it isn't as easy as placing rays on the corners of the box, because there are many cases where this would return false positives.
I've been thinking of a sweptbox/triangle collision that sweeps the box over the triangle, then testing a ray against that, but I don't know how to form the swept box over the triangle. Another idea that I've investigated is figuring a point on the triangle to place the box at, then tracing a ray against the box, however it is incomplete.




Re: Advanced 3D Collision Detection

I would recommend forgoing triangle accuracy and instead concentrate on basic primitives. Break your world into boxes, spheres, cylinders, and other basic shapes. These won't necessarily be drawn, but will be used by the collision detection engine in your game. Performing box/box, box/sphere, etc. collision detection robustly is a lot easier than box/triangle intersections robustly, and it is also much easier on the CPU! In most cases, you won't even notice the accuracy difference.
Look into the Separating Axes Theorem for box/box detection, there is a code sample somewhere on Ziggyware. Or if you're really feeling adventurous, implement a GJK algorithm, which detects collisions between any arbitrary convex shapes, given a mapping function for each shape. Both of these can be combined with techniques to give you the point, line, or plane of intersection between the objects.
Once that is working, then you can implement spatial partitioning algorithms like an octree to speed it up even more.




Re: Advanced 3D Collision Detection

Well the easiest solution is definately the bounding box. Put a bounding box around your box, and if your triangles are a lot smaller than your box you can just say does bounding box contain vertices1, 2, or 3 of the triangle. If your triangles are a lot bigger than your box then you run into the problem of the box not hitting a vertice even though its colliding with the triangle. In this case you are kinda screwed lol, you will have to alter the fast ray/triangle intesection method to take in a bounding box parameter instead of a ray parameter. I dont see how putting 4 rays on the corners of your cube would cause a false positive, those rays are straight lines, so if they intersect with something, the boxes corners would have also been intersecting, which would be a true.




 (0)

MVP
Moderator

Posts
1,305

Re: Advanced 3D Collision Detection

If you want to do collision detection for a bounding box with a triangle mesh, you might want to consider fabio policarpo's BoxCollider library.




Re: Advanced 3D Collision Detection

@MJP: The collider library you suggested looks useful, I will look into it later (I'm at work now).
@cpyburn: Sorry, but I meant to say false negative (not positive). Anyway, here's a crude image with the ray corners idea (+'s are box, x's are triangle). As you can see, if the box is moved straight into the triangle, none of the corners hit, but the box and triangle do.
xxxxxxxx
xxxxxxx
++++++++++
+ xxxxx +
+ xxxx +
++++++++++
xx
x
@ShawMishrak: I might look into basic box/box collision for now, but since this will be my 3D game engine, I'll ultimately want to support box/triangle tracing. As far as the separating axis theorem, I've already done work with that, but it's not easy to add support 3D movement (much easier for 2D movement). So I may wind up with a 2.5D engine  3D graphics, 2D collision and movement  for now.




Re: Advanced 3D Collision Detection

I'm using JigLibX. It has some warts, but all in all, it's a lot faster to use that than to write your own from scratch.




Re: Advanced 3D Collision Detection

MJP, the library you suggested is EXACTLY what I was looking for  thanks!
My current code does most of that, but there's a walkingintocorner issue that seems impossible for me to figure out.
Thanks again  I didn't think I'd be as lucky as to get it figured out in just 2 days!




Re: Advanced 3D Collision Detection

Could you link this library to me? It seems his website has been updated and i cant find the lib in there.
Im writing a flight game that travels through human viens to fight virus's etc. So i need to check for collisions with the walls and im assuming that only triangle intersection is gonna work here. I wont be checking each triangle in the ship model as il just have one bounding sphere around that and then smaller ones inside that are checked only when the big one has collided, this should help with performance. Anywhos, if you or someone else could help me with this i would be very grateful.
Thanks
Kev




Re: Advanced 3D Collision Detection


