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:

STEP 1:
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
}

STEP 2:
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.

CONCLUSION:
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 ?

20 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!

    ResponderEliminar
  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

    ResponderEliminar
  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

    ResponderEliminar
  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
    good.

    ResponderEliminar
  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

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

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

    Also visit my homepage ... air conditioner parts Hartland

    ResponderEliminar
  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

    ResponderEliminar
  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

    ResponderEliminar
  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

    ResponderEliminar
  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
    before.

    Feel free to surf to my site: simpoints code generator

    ResponderEliminar
  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

    ResponderEliminar
  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

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

    my homepage ... lake boat rental

    ResponderEliminar
  15. 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

    ResponderEliminar
  16. 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

    ResponderEliminar
  17. 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

    ResponderEliminar
  18. 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

    ResponderEliminar
  19. 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

    ResponderEliminar
  20. 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

    ResponderEliminar

Put a message :)