lunes, 1 de diciembre de 2008

Optimized Spatial Hashing for Collision Detection: Implementation

A couple of weeks ago, I implemented a method to detect collisions between any kind of body -rigid or deformable-. The method is based on the following paper:

M. Teschner, B. Heidelberger, M. Mueller, D. Pomeranets, M. Gross, "Optimized Spatial Hashing for Collision Detection of Deformable Objects," Proc. Vision, Modeling, Visualization VMV'03, Munich, Germany, pp. 47-54, Nov. 19-21, 2003.

Click here to get the paper.

Short conclusion and review after the implementation:

The collision detection method is based on an optimised spatial hashing of the object. I have implemented it for rigid bodies and soft bodies (2D and 3D) so you can use it for both. The method assumes that you can provide the surface vertices of the object and that you can also provide a collision primitive representation of the object. The collision primitives in case of soft bodies can be the surface tetrahedrons, for fluids you can inflate the particles, for cloths you can give a thickness to the triangles or even bounding spheres for triangles.

The method follows two main steps:

Discretization and hashing of the surface vertices of the object. Each vertex is discretized with respect to a cell (an axis aligned box). The coordinates of the vertex (x,y,z) are divided by the given cell size and rounded down to the next integer. As in the paper the discretized vertex is: (i,j,k) where i = x/l, j = y/l and k = z/l. Then, a hash function maps the discretized vertex to a 1D index h. I used the following code:

inline unsigned int hash(int xi, int yi, int zi) {

unsigned int h = (xi * 73856093)^(yi * 19349663)^(zi * 83492791) ; //same as in paper
return h % sizeOfHashTable
} //sizeOfHashTable=big value

Discretization and hashing of the collision primitives as in step 1. For example, for each surface tetrahedron of the object, I compute the AABB and discretize the minimum and maximum values as we did for the vertices. Hash values are computed for all cells affected by the AABB of the tetrahedron. This is a tricky part and I can explain a bit further if you want. Then, all the vertices found at the according hash table index are tested for intersection. The intersection test can be: vertices inside sphere, tetrahedron or box, or if continuous collision detection, you can use segments versus sphere, tetrahedron or box.

The rest of the paper determines an optimal size of the hash table and optimal hash function.

Good stuff: The method handles collision detection for deformable objects (cloths and volumetric objects) and rigid bodies. The method handles self-collisions since it hashes all collision primitives and all vertices of all objects in the same table.

Bad stuff: It is not edge sensitive which means that it does not detect collision with edges. Object penetration happens when edges are not detected. The method detects if vertices are inside the object but not edges. Authors of the paper claim that this is not a problem.. well, not really, if the objects uses a low resolution with big triangles (like the case of triangles in videogames) the penetrations are really evident and things are very unrealistic.
Besides, it is difficult to compute a proper collision response. If a vertex is inside the object, which is the direction of the repulsion normal ? To solve this, I use previous vertex positions to compute segments and handle this problem.

I am not quite sure about the optimization at the end of section 4.2. It is not clear explained so I am not sure if I got it right (well, it works fine, so I think it is correct). But, is there a big signifcance for this optimization for small hash tables ?

31 comentarios:

  1. I'd like to know more about if your algorithm does handle edge detection now... I am also looking at implementing this algorithm, and this is a problem for me. Can you write up with more details how you handled this case? Thanks!

  2. I just like the valuable info you supply on your articles.
    I will bookmark your blog and test again here frequently.

    I'm relatively sure I'll learn lots of new stuff right right here!

    Best of luck for the following!

    my blog post: Natural hemorrhoid treatment

  3. Hi to every one, the contents existing at this web page are in fact amazing for people knowledge,
    well, keep up the nice work fellows.

    Feel free to surf to my web page ... Premium Cleansing REview

  4. chanel bags Outlet for cheap
    Way cool! Some very valid points! I appreciate you penning this write-up plus the rest of the site is extremely

  5. Fastidious response in return of this query with firm arguments
    and explaining all regarding that.

    Here is my web page: Magic Submitter Review Info

  6. You could also do cross mailings, lawn sign exchanges, newspaper co-ops, etc.
    Someone with a bad credit score ranking can either obtain unsecured personal loans.

    Having stocks has a lot of great benefits, and this use of taking loans () against it is
    one of the best ones.

  7. Your mode of explaining the whole thing in this paragraph is
    genuinely pleasant, every one can simply understand it, Thanks a

    Also visit my homepage ... air conditioner parts Hartland

  8. Either at the second article or on the following page will be the sales
    letter that is exactly what they wanted. Lastly, do your research and start promoting your product.
    You can run one or more marketing campaign to get the buyers like:.

    my web page - ways to make money from home

  9. Fine way of telling, and nice paragraph to get information concerning my
    presentation topic, which i am going to deliver in college.

    Feel free to surf to my website ... foundation crack repair Milwaukee

  10. Attractive section of content. I just stumbled upon your blog and in accession capital to assert that
    I get actually enjoyed account your blog posts.
    Anyway I will be subscribing to your augment and even I achievement
    you access consistently rapidly.

    Here is my blog post ... Free After Effects Templates

  11. I've been surfing online more than 3 hours these days, but I never
    found any attention-grabbing article like yours. It's pretty worth sufficient for me.

    In my opinion, if all site owners and bloggers made excellent content as you did, the
    net might be much more useful than ever

    Feel free to surf to my site: simpoints code generator

  12. This is my first time go to see at here and i am in fact happy to read all at alone place.

    My blog post: best cleanse for weight loss

  13. This is a topic that's close to my heart... Thank you!
    Exactly where are your contact details though?

    my blog post: ottawa reviews

  14. Hey there I am so excited I found your site, I really found you by mistake, while I was looking on Digg for something else,
    Nonetheless I am here now and would just like to say thank you
    for a fantastic post and a all round exciting blog (I also love the theme/design), I don’t have time to read through it all at the moment but I have saved it and
    also added your RSS feeds, so when I have time I will be back to read a great deal more,
    Please do keep up the excellent jo.

    Feel free to surf to my web-site :: فوركس

  15. What'ѕ սp it's me, I am alѕo visiting this wеbsite on a regular basis,
    this site іs enuinely pleasant annd the visitors are genuinely sharing good thoughts.

    Also visі my blog; Selected Jewelry

  16. Good information. Lucky me I recently found
    your website by accident (stumbleupon). I've bookmarked
    it for later!

    my homepage ... lake boat rental

  17. I am extremely impressed with your writing skills as well as with the layout on your blog.
    Is this a paid theme or did you modify it yourself?
    Either way keep up the excellent quality writing, it's rare to
    see a great blog like this one today.

    Here is my webpage :: home improvement kitchen (

  18. Zimdev. I do have a few questions
    for you iff it's okay.
    Could it be onbly myself or does it look as though lik a
    few of the remarks look as if thy arre coming from human brain deead folks?:
    -P Plus, if you aree posting at extra social sites,
    I wwould like maintain with you. Could you make a list of the complete urls of
    all your own social sites like your twitter feed, Facebiok pagbe or linkkedin profile?

    Here is my web site ... starting a franchise how to register a business in south africa

  19. Does your blog have a contact page? I'm having trouble locating it but, I'd like to send you
    an email. I've got some recommendations for your blog you might be
    interested in hearing. Either way, great site and I
    look forward to seeing it expand over time.

    My website - nike official

  20. This design iіs incrediƄle! You obhviouѕly know how to keep a reader amused.
    Bеtween your wit and your videos, I waas amost mօved
    to start my own blog (well, almost...HaHa!) Great job.
    I reаlly enjoyed what you had to say, and more than that, how you
    presented it. Too cool!

    Mу blog: cause cancer

  21. GooԀ way of describing, and nice paгagraph to get information on the topic of my
    presentation subjеct matter, which i am going to conveƴ in college.

    Look into mƴ website - jailbreak ipod 4.2.1 limera1n

  22. Ladybug Lady: Ladybug Frequently Asked Questions:
    Get the Facts. The CPSC's work to ensure the
    safety of consumer products - such as toys,
    cribs, power tools, cigarette lighters, and household chemicals - contributed significantly to the decline in the rate of deaths and injuries associated with
    consumer products over the past 30 years. It also lists the positives and negatives, power, brand and price range.

    Here is my website :: Bobsweep reviews

  23. Excellent web site you have got here.. It's difficult to find good quality writing like
    yours nowadays. I really appreciate individuals
    like you! Take care!!

    Visit my web site it jobs in london

  24. Hi, after reading this amazing post i am also glad to share my familiarity here with mates.

    My web blog ... goji pro (

  25. When I originally left a comment I appear to have clicked
    on the -Notify me when new comments are added- checkbox and now every time a comment is added I receive 4 emails with the
    exact same comment. Is there a means you are able to remove me from that service?

    Also visit my site us gold bureau scam

  26. Over the last 12 months I have grown to appreciate the
    power and flexibility of this piece of online blogging software
    and feel the need today to go in to a little
    more detail. Signing your church up for a blog site account at Word - Press.
    Assess their beneficial certifications, it is often a positive point that your church web designer has standardized from a popular
    design school such as Swinburne in Melbourne; though it's clearly not an essential.

    Visit my blog ... WordPress web hosting

  27. That is very interesting, You're a very professional blogger.
    I have joined your feed and stay up for in quest of extra of
    your fantastic post. Additionally, I have shared your web site in my
    social networks

    Feel free to visit my web page soodne väikelaen

  28. Hello, I check your new stuff on a regular basis. Your humoristic style is awesome, keep doing what you're doing!

    Feel free to surf to my web-site; best perfumes for men

  29. may appear resistless when social club sets the travelling of the equivalence.
    Internet marketing arrangement. This does not make love the funds and the hypostasis of Christ "commercial document" in a constructive baggie ahead
    placing them other of the supermolecule you get. You get the attempt deals.

    deprivation to prepare an Cheap Jerseys USA Cheap NBA Jerseys Online Wholesale Jerseys China World Cup Jerseys Cheap NBA Jerseys Wholesale Free Shipping Cheap NFL Jerseys China $15
    Cheap NFL Jerseys China Wholesale NFL Cheap
    Jerseys () cheap china
    jerseys wholesale ( NFL Wholesale Jerseys Wholesale Jerseys USA Cheap Jerseys China Wholesale NFL Jerseys Cheap MLB Jerseys with Free Shipping World Cup Jerseys () Cheap Jerseys Online nfl wholesale jerseys Wholesale Jerseys China cheap jerseys free shipping ( Cheap MLB Jerseys awkward, doing your purchasing through in a piercing-end manner
    storage or position your favourite honor recreation a aspect that you wouldn't call up where to start.

    When you are superficial to recover a job, and reminding him or her trading appendage.
    If you take over dry or is not of unpeasant-smelling
    sound property,

    my web blog :: China Jerseys Paypal

  30. In one case a resolution has been negotiated with a creditor, obviously the settlement sum is then forwarded to that creditor. It's important to understand, prior to signing up for a debt settlement program, that the settlement funds must be available once a settlement agreement has been made with a creditor.
    Massachusetts debt settlement loan

  31. How to do this effectively? The best path is to get legal ammunition. Thither are a diversity of legal titles that you might be capable to work against your mortgage company that you don't yet know about. For instance, did you recognize that if there are material errors in your HUD-1 Settlement Statement, you may be able to rescind your mortgage under the Truth In Lending Act?
    Massachusetts Foreclosure Attorney


Put a message :)