martes, 16 de diciembre de 2008

Time Critical Collision Detection

One of the bottlenecks to obtain real-time physical based simulations is the collision detection process and much research has been done on this. In the past, I proposed a method to fit the collision process to any given budget of time. See the paper here. This method works for rigid and deformable bodies.

The idea is to interrupt the collision process when our budget of time has expired and use the available information to compute the collision response (it this happened). The computed response is an approximation of the real one: Yes, we trade time for accuracy, but in general the results are quite satisfactory.

The method is based on sphere representations of the object. Each of these representations goes from a coarse representation (a) to a high quality representation (d). If we have little time, we compute the collision detection process using (a) or (b) representations as in the figure above. If we have lots of time, we use more detailed representations (c) or (d). The coarser the representation the less accurate is the response (or even the detection).

The complexity of the problem comes to compute good responses even with little information.

The question is: do you prefer high accurate responses even if your application goes slow or do you prefer to keep your simulation rates and obtaining some non-accurate responses ??

Well, here at Atari we have decided to go for high accurate responses... so, that means that I will have to find other ways to keep good simulation rates... good challenge !

So, if anybody have some good ideas, please let me know.

7 comentarios:

  1. Well, the most popular sentence these days is: "go parallel!". Take the most advantage of multiple processing units... instead of using the processing power to increase the performance, use it to improve the accuracy!
    good luck :)

  2. Hi Cris,

    Thanks for the advise. We have started in some little things like parallelizing the broadphase but for the rest, it is still under work.

    Anyway, it is dark enough for me how to distribute the collision detection for the narrow phase of pairs... I need to re-think more on that.

    Thanks anyway.

  3. I see! But I can also tell you that nowadays is a pretty standard solution distributing the narrow phase on several threads/cores. It's what the major engines do (physx, havok, bullet). Once you collected the overlapping pairs (in the broadphase, through sweep and prune or some other way), the computation of every single "accurate" intersection is completely independent. You can setup a "task queue". Each task computes the narrow phase for a set of pairs (from 1 to N pairs, to be tuned), and at when all tasks complete, the contact solver can start. I did the same for my little 2d engine and it works very well... actually it gets better when the number of contacts grows!

  4. First of all I would like to say superb blоg! I hаd a quісk question that Ι'd like to ask if you do not mind. I was interested to know how you center yourself and clear your mind prior to writing. I have had a tough time clearing my mind in getting my ideas out. I do enjoy writing however it just seems like the first 10 to 15 minutes are usually wasted just trying to figure out how to begin. Any ideas or tips? Cheers!

    my web blog ... Big Green Egg Pizza Stone

  5. Hellο to all, it's in fact a fastidious for me to go to see this website, it consists of helpful Information.

    My website; irving tx cab

  6. Wonderful blog! I found it while surfing around on Yahoo
    News. Dо you have any tips on how to get listed in Yahoo News?
    I've been trying for a while but I never seem to get there! Many thanks

    my web-site :: taxi service irving

  7. Thanks foг the аuѕріcious writeup.
    Ιt in fact uѕed to be a enјoyment аcсount it.

    Looκ compliсated to mοre brought agreeаble frοm уou!
    However, how cаn we κeеρ up a сorrespondеnce?

    Αlѕo visit mу web pаge okc roofer


Put a message :)