Convex decomposition, is this a wrong way of thinking?

[dneckels]

I would like to decompose some static meshes into a series of convex pieces and use my convex collision code on the pieces.
For a non-intersecting polygon soup, what if I:
1) start a convex obj with a single triangle.
2) Look at edge-adjacent triangles. Add triangle to convex obj is angle between tris < 180 (assume I have a well defined inside/outside. If triangle intersects any other triangles in obj, make sure those other edges are also convex.
3) When not possible to add any more tris, pick an unused tri, repeat....

Does this work? If not, what is the condition on the object when it fails? Will it work for terrain?

In the long run would it be more advisable to just use a BVH?

thoughts?

[dneckels]

Oh, never mind. I think I see; the convex hull of a few triangles could over-estimate possible indentations in the object..... ??

I might still work for terrain, though, if, say there was a rule that triangles never go past vertical??

[aokman]

I think you should refer to a text book on computational geometry.

[ola]

There is a convex decomposition library provided with Bullet, you can find it in the Extras/ConvexDecomposition directory. It is not depending on Bullet. I've used it some times and it's OK for my needs. At least you won't have to implement it all from scratch if you just want to do some testing.

Cheers,
Ola

[dneckels]

I think you should refer to a text book on computational geometry.

hmmmm

why do i post here?

[dneckels]

There is a convex decomposition library provided with Bullet, you can find it in the Extras/ConvexDecomposition directory. It is not depending on Bullet. I've used it some times and it's OK for my needs. At least you won't have to implement it all from scratch if you just want to do some testing.

Cheers,
Ola

Oh yeah, thats why. Thanks.

Is this the 'approximate convex decomposition' library J. Ratcliff, or an exact library?

I'm thinking RCB may be what I'm looking for. Trying to rig up collision detection (and portals) for a level....

[ola]

It is the one one from John Ratcliff. I just found this: http://codesuppository.blogspot.com/200 ... y-now.html
Maybe that version is a bit more recent than the one provided with Bullet, I haven't compared them.

[dneckels]

Ok, yeah, I downloaded John's code. Very impressive (he has an example with a deer).

I guess in general what I am struggling to do is move from collision between a bunch of convex or 'union of convex' objects and start to understand how to put together a level (like for a first person shooter).
The bullet bspdemo seems to build a bunch of convex solid rigid bodies from the bsp decomposition. I'm not sure if this type of approach scales?

I have a kd-tree wrapping my collision world, so the broadphase collision is only done between objects within a leaf, and leaves that are totally asleep can be skipped altogether, so I am thinking that maybe partitioning the world up into convex solid rigid bodies would work...??

Not sure....

Thanks again.

[dneckels]

Answer = Download Quake III and Q3Radiant code. Read.
Big project, but started it!!