Support Arbitrary Convex Geometry

[toji]

I know this project is still in it's early days, but even so I'm quite eager to see it mature into a fully featured library. I absolutely think that building it in javascript from the ground up is the right way to go! As such, I figured I'd put in an early feature request for arbitrary convex geometry.

Preferably said geometry would be specified as either a point cloud or possibly as a set of planes, but point cloud would make for easier conversion from bullet/ammo.js. As an added bonus it would be pretty easy to generalize cubes into just another convex shape rather than requiring their own special-cased type.

It's a big feature request, I know, but it's also an absolutely critical one before I could think about using Cannon in my own projects, and I would dearly love to use it! :)

[schteppe]

Could you point out simple examples on how this should work in the end? Is the Ammo equivalent btConvexHull, or are you fishing for something else? Thanks for your support. I hope that this project will reach a level comparable with Ammo some day!

[chandlerprall]

The "point cloud" / "set of [triangles]" would be equivalent to Ammo's btConvexHull / btTriangleMesh - basically, find the smallest convex hull encompassing all points.

I think compound shapes (collection/grouping of existing shape definitions) may be a good stepping off point for moving to convex shapes? ...I'm far from being a physics guy.

[toji]

Yes, the feature requested here would be analogous to btConvexHull. I would recommend against implementing something like btTriangleMesh since my understanding is that it's much more difficult to optimize and really just encourages developers to be lazy.

General case convex hull collision is decently easy to detect by calculating the "Minowski Difference" and seeing if the resulting shape encompasses the origin. This is known as the Gilbert Johnson Keerthi algorithm, or GJK.

I'm happy to help out with the implementation, though I can't claim to be much of a physics guy. I've already started toying with the source, but I think I've got a few questions that would need answering before I could be of too much help.

[schteppe]

Thanks both of you. @toji If you're familiar with the algo then I would appreciate a contribution from you. The algorithm could be used in the nearphase to detect the interesting points for generating contacts.

How to proceed after we got GJK is not yet clear to me though. To make a contact, we need the normal vector pointing out from the contact point. And I guess we'll need the involved edges too. How to do that with a cloud of points? Perhaps we will need one more algorithm before we can fully support convex hulls, but the Minowski difference is one step closer to it, especially if it is cheap to compute.

If you got questions, shoot! Either post here or create new issues.

[schteppe]

This may be relevant reading: http://www.altdevblogaday.com/2011/05/13/contact-generation-between-3d-convex-meshes/

[schteppe]

I implemented the clipping algorithm according to the blog post I mentioned above. It is still very experimental and unstable but I got a tetrahedron, a cylinder and a cube resting on a plane in the convexhull demo.

What is left to do is automatic face + normal generation, fixing the findSeparatingAxis function which currently is doing something wrong, and then perhaps split the code into some clever class hierarchy with convex hull, convex triangle mesh etc etc. Apparently, some of the clipping methods can be reused in several of them.

Got any suggestions/ideas/comments at this point? Thanks.

[chandlerprall]

I'm not sure a convex triangle mesh is necessary -- what functionality does it add that a convex hull doesn't have?

[schteppe]

You got a point there. I think that most users that want an own designed convex shape can go the ConvexHull way. I cannot think of any case that can't be done with ConvexHull that can be done with a convex triangle mesh.

The Bullet Physics doc of btConvexTriangleMeshShape says:

The btConvexTriangleMeshShape is a convex hull of a triangle mesh, but the performance is not as good as btConvexHullShape. A small benefit of this class is that it uses the btStridingMeshInterface, so you can avoid the duplication of the triangle mesh data. Nevertheless, most users should use the much better performing btConvexHullShape instead.

[schteppe]

I studied the definitions for hulls and polyhedra and realized that what we have this far is actually a convex polyhedron implementation.

This is how I understood it, in short: Hull: A set of 3D points. Construct by adding points. Triangle mesh: A set of triangles. Construct putting together triangles. Polyhedra: A set of polygons. Construct by putting together polygons/faces.

To avoid confusion I think renaming the current ConvexHull class to ConvexPolyhedron would be a good idea...

As we already said, the current implementation could be used to construct ConvexTriangleMesh. It could also be used to construct a ConvexHull if we include an algorithm for constructing faces from 3D points. If we feel like it is necessary, we could implement ConvexTriangleMesh and ConvexHull subclasses from this ConvexPolyhedron. This would not bring more functionality to the engine, but rather help a bit with geometry construction.

Does all this sound sane?

[chandlerprall]

I think having a true convex hull shape is a good idea. Being able to generate a hull from just an array of points makes it easier to create (from the developer's perspective at least) and, IMO, allows better mathmatically-defined shape creation.

I still don't know how useful a triangle mesh would be. @toji - it's your open issue, any thoughts? :)

[toji]

I've actually been building a per-triangle collision routine for one of my projects over the last couple of weeks. Here's my take on it:

A triangle mesh collision routine is valuable, because it can accurately simulate any shape. (In my case a 3D perlin noise mesh) The collision routine for a swept sphere vs. a single triangle, however, is atrocious and by necessity requires that you run it many many timess per frame to properly resolve the collision. In my case I get away with it by using an octree to narrow the potential collision set down to a small number (<10) of triangles, but it's still not pretty.

A convex hull should be comparatively much simpler, and can give "good enough" approximations for a great many situations. Not to mention many existing resources used for games and whatnot are already geared towards convex hulls. (ie: most map formats) As such, my recommendation is to focus on convex hull first and encourage users to prefer it when possible. A triangle mesh shape would be useful for edge cases, but I would recommend putting it on the "future wish list". It can often be used as a crutch by inexperienced developers and won't yield performance anywhere near as good.

FYI: Once I have my own per-triangle collisions working I'll make the code available for use/reference.

[chandlerprall]

I just want to add that there is (obviously) a huge difference between a Convex Triangle Mesh and a Triangle Mesh. In this thread I've been referring to the convex type. The implementation @toji is working on would be very useful indeed.

[schteppe]

I agree that focusing on the convex shapes is better. They limit things a little bit, but have fairly easy implementation and does not put too much work on the target browser. Keeping things lightweight agrees with my initial idea when starting this project.

I did not study the trimesh collision / contact generation algos yet, but I would for sure find those interesting. Can't wait to see your implementation, @toji. Your code would for sure be useful, but do you have something written about how the algorithms work, or some maybe some book/article about them that you can recommend?

There are many things I'd like to see in Cannon.js before these arbitrary trimeshes, I'll just put it in the "future todo" list.

Thanks for the feedback guys.

[toji]

As promised, here's my current swept-sphere vs. triangle collision code. It ain't pretty but it works. See the bottom of the file for a sample usage:

https://gist.github.com/2802287

As mentioned in the comment at the top of the file, most of the collision code is derived from http://www.peroxide.dk/papers/collision/collision.pdf, which was a great resource on the topic!

Hope that helps down the line!

[schteppe]

Thanks! Perfect :)

[andrewvarga]

What's the current status of this? If I want to do something as simple as have 2 triangles or 2 triangle meshes / convex hulls interact is it possible currently?

[schteppe]

As I explained in the e-mail: Yes, using the current ConvexPolyhedron implementation, given that the triangles have some volume.