btShapeHull::buildHull

[S.Lundmark]

Hi,

I'm passing the following data into the btShapeHull::buildHull:

Code: Select all

-		(pointCloud).m_data,8	0x0ac52150 {mVec128={...} m_floats=0x0ac52150 }	btVector3 *
-		[0]	{mVec128={...} m_floats=0x0ac52150 }	btVector3
+		mVec128	{0, -0,360922, -1, 4,29651}	__m128
-		m_floats	0x0ac52150	float [4]
		[0]	4.2965055	float
		[1]	-1.0000000	float
		[2]	-0.36092195	float
		[3]	0.00000000	float
-		[1]	{mVec128={...} m_floats=0x0ac52160 }	btVector3
+		mVec128	{0, 2,79581, -1, -2,51747}	__m128
-		m_floats	0x0ac52160	float [4]
		[0]	-2.5174723	float
		[1]	-1.0000000	float
		[2]	2.7958112	float
		[3]	0.00000000	float
-		[2]	{mVec128={...} m_floats=0x0ac52170 }	btVector3
+		mVec128	{0, 0,269299, 1, -4,38952}	__m128
-		m_floats	0x0ac52170	float [4]
		[0]	-4.3895168	float
		[1]	1.0000000	float
		[2]	0.26929939	float
		[3]	0.00000000	float
-		[3]	{mVec128={...} m_floats=0x0ac52180 }	btVector3
+		mVec128	{0, -2,70419, 1, 2,61048}	__m128
-		m_floats	0x0ac52180	float [4]
		[0]	2.6104834	float
		[1]	1.0000000	float
		[2]	-2.7041886	float
		[3]	0.00000000	float
-		[4]	{mVec128={...} m_floats=0x0ac52190 }	btVector3
+		mVec128	{0, -2,70419, -1, 2,61048}	__m128
-		m_floats	0x0ac52190	float [4]
		[0]	2.6104834	float
		[1]	-1.0000000	float
		[2]	-2.7041886	float
		[3]	0.00000000	float
-		[5]	{mVec128={...} m_floats=0x0ac521a0 }	btVector3
+		mVec128	{0, 2,79581, 1, -2,51747}	__m128
-		m_floats	0x0ac521a0	float [4]
		[0]	-2.5174723	float
		[1]	1.0000000	float
		[2]	2.7958112	float
		[3]	0.00000000	float
-		[6]	{mVec128={...} m_floats=0x0ac521b0 }	btVector3
+		mVec128	{0, -0,360922, 1, 4,29651}	__m128
-		m_floats	0x0ac521b0	float [4]
		[0]	4.2965055	float
		[1]	1.0000000	float
		[2]	-0.36092195	float
		[3]	0.00000000	float
-		[7]	{mVec128={...} m_floats=0x0ac521c0 }	btVector3
+		mVec128	{0, 0,269299, -1, -4,38952}	__m128
-		m_floats	0x0ac521c0	float [4]
		[0]	-4.3895168	float
		[1]	-1.0000000	float
		[2]	0.26929939	float
		[3]	0.00000000	float

Which is just 8 vertices. They already form a convex hull, although the are not guaranteed to be in any certain order.

Passing these vertices by the following code:

btConvexPointCloudShape cloud(&pointCloud[0], 8, btVector3(1.f, 1.f, 1.f), true);
btShapeHull hull(&cloud);
hull.buildHull(0.04f);
cloud.setUserPointer(&hull);
shape = new btConvexHullShape(&(hull.getVertexPointer()->m_floats[0]), hull.numVertices(), sizeof(btVector3));

Results in a shape with 144 indices and 26 vertices. I think that equals to 48 triangles. The vertices that are supplied are created from 8 triangles.

I'm not sure if this is intended, but it surely isn't very optimal. Is there anyway to fine-tune the hull-generation to generate less triangles?

P.S.
I'm sorry I haven't submitted my changes regarding the btCollider refactoring into the cd-pipeline. I'll see if I can get the time to do it during my christmas holidays.

/Simon

[Dirk Gregorius]

I noticed this as well. If I remember correctly Bullet does not send the vertices directly to StanHull, but creates vertices sampling support points itself. Maybe you can skip that step. On the other hand there might have been a motivation for this. It has been a while I looked into this, so I might be wrong.

[Erwin Coumans]

Hi,

I'm passing the following data into the btShapeHull::buildHull:
[...]
Results in a shape with 144 indices and 26 vertices. I think that equals to 48 triangles. The vertices that are supplied are created from 8 triangles.
I'm not sure if this is intended, but it surely isn't very optimal. Is there anyway to fine-tune the hull-generation to generate less triangles?

The sampling uses the support mapping and there might be two issues that cause extra vertices to be created:

• the collision margin might inflate the object so it becomes rounded
• there is no check for duplicate vertices in the sampling

You could try setting the margin to zero during the sampling, and see if there is a duplicate vertices check?

P.S.
I'm sorry I haven't submitted my changes regarding the btCollider refactoring into the cd-pipeline. I'll see if I can get the time to do it during my christmas holidays.

It would be nice to have a look at your work, it could help the Bullet 3.x design.

I'm concerned about your approach bypassing the broadphase collision detection for static artwork, creating extra overlapping pairs etc. It would be good to try to keep the number of children in static btCompoundShapes low, if possible. You mentioned that memory overhead is an issue. Instead of using a btRigidBody for the static btCompoundShape's, you could use a btCollisionShape (which is around 350 bytes or so). When using static btCompoundShape's of say 24 children, the overhead per shape is just 16 bytes or so.

What are your thoughts about this, and how do you optimize for SPUs with huge compounds on PS3?
Thanks,
Erwin

[S.Lundmark]

Hey Erwin,

It looks like the collision-margin that I can pass in gets ignored (btShapeHull.cpp - line 85 (btShapeHull::buildHull)). It doesn't use the margin passed in. I haven't looked into the implementation very much but it looks like the HullDesc has a default of 0.001f as their normal-epsilon, but nothing associated with collision-margins. I will try to increase the normal-epsilon and see how it behaves.

I'm not sure that the cost in overlapping pairs would be much different than if I had split up the btCompounds into several pieces. The dynamic rigidbodies will collide with something static anyway, so each dynamic rb would still create (atleast) one overlapping pair. I've unsuccessfully tried to eliminate the allocations of collisionAlgorithms in the compound-shape in order to decrease (some of) the overhead that the large compound creates. What's unfortunate is that I'm using the cost of both the broadphase and the bvh with only gaining the benefits from the bvh-lookup.

I assume you meant btCollisionObject instead of btCollisionShape, which sounds like a really good solution. The memory overhead is much less for such an object. My greatest concern is that I'm using a buffer of 1024 persistent manifolds which I gladely would decrease if possible. 16 bytes overhead per shape is definetly good enough. In a "worst case" scenario, that would lead to 160k memory overhead - which is good.

I'll see what I can do about this and if I can get a good test-implementation. I might not have time for it until the holidays though.

The huge compounds are sent as their bvh-tree's. The first thing I do is to query the tree to find the keys which are overlapping with the collided shape. I then dma the needed shapes for the compound. I then cache the key from the last frame and send that shape over together with the bvh-tree the next time that pair is resolved, since it's most likely that it'll reuse the old shape. It's not optimal but it's good enough. Something that would be more optimal would be by sending the shapes in the near vicinity over. The implementation is not fully done yet.

When would you need my refactoring at latest in order to aid you in designing bullet 3.x? (I'll really try to get it in around christmas).

Cheers
Simon

[S.Lundmark]

Hey!

Increasing the mNormalEpsilon of the HullDesc solved my problem of too many vertices being generated in the convexHull! Many thanks.

Cheers,
Simon