iDevGames Forums
Collision Detection using four dimensions (time) - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: Collision Detection using four dimensions (time) (/thread-2840.html)



Collision Detection using four dimensions (time) - wyrmmage - Jan 10, 2008 06:43 PM

I've been reading about collision detection for my physics engine and one article I ran across mentioned doing collision detection using four dimensions (x,y,z and time t).
Does anyone have any experience with this or thoughts on if it would work efficiently or not?
I just found this link while googling around: ftp://ftp.cs.brown.edu/pub/techreports/93/cs93-04.pdf
I'm going to have a look at it, but it's quite a long read XD

Anyone else have links on the subject? I've only taken math through Math-Analysis (the class after Algebra II, before calculus) in high-school, but I could always try to learn some new math if needed Smile

Thanks,
-wyrmmage


Collision Detection using four dimensions (time) - TomorrowPlusX - Jan 11, 2008 08:05 AM

I think Bullet uses this kind of approach ( they call it "continuous" collision ).

http://www.bulletphysics.com/Bullet/

They might have papers on the topic. Failing that, they have a forum. The lead developer ( I can't recall his name ) is working on integrating it to ODE and is very approachable.


Collision Detection using four dimensions (time) - scgames - Jan 11, 2008 03:05 PM

Just a couple more comments on the topic of continuous collision detection...

These days, I think there's a lot to be said for using third-party physics solutions, simply because of the amount of work involved in implementing such a system oneself.

If you do want to do it yourself though, the optimal approach for the collision detection narrow phase will be determined largely by:

1. Dimension (2-d or 3-d?)

2. What shapes you want to support (convex polytopes, curved shapes such as spheres and capsules, polygon soups, non-convex or arbitrary meshes, etc.)

Common solutions are the SAT (separating axis test), special-case CSO raytracing (for e.g. sphere vs. box intersection testing), and GJK (which can be generalized to work with just about any convex shape).

I believe Bullet uses GJK for its collision detection, but be aware that GJK is fairly difficult to implement (or at least to implement robustly).

As far as efficiency goes, continuous collision detection is pretty standard these days, and under normal circumstances shouldn't be that much more costly than the discrete test.

If you can describe more about your physics engine (dimension, supported shapes, etc.), it might be possible to make more specific suggestions about what algorithms would be worth pursuing.


Collision Detection using four dimensions (time) - wyrmmage - Jan 11, 2008 05:17 PM

The game is 3D. Currently the engine supports rigid body objects that are triangle meshes. Objects are kept in a hierarchy for animation, so I started my physics engine by calculating bounding rectangular prisms for each object and then its sub-objects in the hierarchy. I'm also using a radius for each object as the initial test, and working on using a sort of spacial partitioning using binary trees Smile

Advice is welcome! Smile

So far I've mostly been reading through the articles on gamedev.net to get an idea of various physic engine types.

-wyrmmage