Defining a convex hull

Post Reply
PORRAS
Posts: 15
Joined: Tue Oct 13, 2009 2:49 pm

Defining a convex hull

Post by PORRAS » Sun Dec 27, 2009 7:57 pm

Hi, all.

I'm a new Bullet user. I'd like to know how to build a convex hull from a set of vertices that form a concave shape.

I mean, I already know all the vertices that form the initial concave shape, and I want to remove from it the inner ones (those not belonging to the convex hull) in order to use the resulting shape (and only its vertices) in the collision calculations.

Do I have to do it my myself?, or is it already implemented in Bullet?

Concave Shape.jpg
Concave Shape.jpg (335.83 KiB) Viewed 15277 times

More questions:

- would you use btConvexHullShape to define shapes and detect collisions with a shape like this?

- when I specify the vertices to define a convex hull using btConvexHullShape, do I have to put them in a certain order or it's the same?

btConvexHullShape (const btScalar *points, int numPoints, int stride)

Thank you very much,
Francisco

spy32
Posts: 19
Joined: Fri Aug 01, 2008 1:12 pm

Re: Defining a convex hull

Post by spy32 » Sun Dec 27, 2009 11:10 pm

Hi,
- when I specify the vertices to define a convex hull using btConvexHullShape, do I have to put them in a certain order or it's the same?
I guess you read the concave model out of a model file like .3ds or .obj. These file formats don't just store the "points", they're saving vertices and indices. This might sound pretty strange, but this article explains what you've to know about that topic.
Here this code might help you, too:

Code: Select all

[...]
	bool Trimesh::init(TrimeshData data, float mass)
	{
		trimesh = new btTriangleMesh();
		for (int i = 0; i < data.getIndexCount() * 3; i++)
		{
			int index0 = data.getIndices()[i * 3];
			int index1 = data.getIndices()[i * 3 + 1];
			int index2 = data.getIndices()[i * 3 + 2];

			btVector3 vertex0(data.getVertices()[index0].x, data.getVertices()[index0].y, data.getVertices()[index0].z);
			btVector3 vertex1(data.getVertices()[index1].x, data.getVertices()[index1].y, data.getVertices()[index1].z);
			btVector3 vertex2(data.getVertices()[index2].x, data.getVertices()[index2].y, data.getVertices()[index2].z);

			trimesh->addTriangle(vertex0, vertex1, vertex2);
		}
		btConvexShape *tmpshape = new btConvexTriangleMeshShape(trimesh);
		btShapeHull *hull = new btShapeHull(tmpshape);
		btScalar margin = tmpshape->getMargin();
		hull->buildHull(margin);
		tmpshape->setUserPointer(hull);
[...]
It's used to extract the triangles out of vertex and index data (in the right order), pretty much the same what you want to do.

PORRAS
Posts: 15
Joined: Tue Oct 13, 2009 2:49 pm

Re: Defining a convex hull

Post by PORRAS » Mon Dec 28, 2009 5:13 am

Hi, spy32, and thanks for your fast reply!

Yes, I know what you mean with that vertices and indices definition. It's like OpenGL and VRML files, you have to specify how the points are linked to each other in order to make triangles, and create a triangle mesh. I didn't know if that was also applicable in Bullet.

I obtain the data via VRML models. First, I create the models in Solid Edge, save them as VRML files, and copy their vertices and indices vectors.

Well, I have used your code in an example. I create a triangle mesh and then, pass it to a btConvexShape using:

btConvexShape *tmpshape = new btConvexTriangleMeshShape(trimesh);

Before applying the ShapeHull simplification:

- Suppose that the previous triangle mesh is a convex shape. Then, is this btConvexShape EXACTLY the triangle mesh I previously introduced or an approximation?

- If the triangle mesh is a concave shape, what is the btConvexShape defined here?, is the corresponding EXACT convex hull related to the triangle mesh?

Thank you very much,
Francisco

spy32
Posts: 19
Joined: Fri Aug 01, 2008 1:12 pm

Re: Defining a convex hull

Post by spy32 » Sun Jan 03, 2010 2:56 pm

- Suppose that the previous triangle mesh is a convex shape. Then, is this btConvexShape EXACTLY the triangle mesh I previously introduced or an approximation?
Ehm, I am not really sure, but I think the convex hull of a convex mesh is EXACTLY the same as the convex mesh itself. Otherwise this wouldn't make sense.
- If the triangle mesh is a concave shape, what is the btConvexShape defined here?, is the corresponding EXACT convex hull related to the triangle mesh?
I think that's the way bullet is generating convex mesh hulls out of concave meshs.. but I am not sure here, too.
Image

PORRAS
Posts: 15
Joined: Tue Oct 13, 2009 2:49 pm

Re: Defining a convex hull

Post by PORRAS » Tue Jan 05, 2010 2:25 am

Thank you very much, spy32.

Well, I want to check that.

I also need some debugging in my application, so I'll need to debug (draw) any btConvexHullShape object I create. For each one, in order to achieve this in OpenGL, I need the mesh (set of points and indices to build triangles). BtConvexHullShape doesn't provide any mesh.

Does btShapeHull do that?, without any simplifications? I don't want a convex simplified mesh of the original concave object, I want its exact (or at least, very similar) convex hull.
I already tried using btShapeHull and debugDrawObject (from btCollisionWorld) but the resulting shape was considerably different from the original (original rounded edges, for example, were very polygonal).

If not, is possible to use directly CreateConvexHull from HullLibrary to get the triangles?

Please, help, I'm really lost.

Thanks,
Francisco.

User avatar
Erwin Coumans
Site Admin
Posts: 4183
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Defining a convex hull

Post by Erwin Coumans » Tue Jan 05, 2010 4:39 am

The best way to visualize Bullet collision shapes is using a software renderer and ray casting. See Bullet/Demos/RaycastDemo for an example. It might be slow, but it is the most accurate way.

The btShapeHull utility indeed simplifies the convex shape. There are two things you could modify to avoid simplification. First, you need to skip the simplification, by using the HullLibrary directly, in LinearMath/btConvexHull.h/cpp.

Secondly, you need to make sure to set the epsilon to zero, to avoid removal of duplicate vertices. Can you try this? Otherwise, please file an issue in the google issue tracker.

Cheers,
Erwin

User avatar
dphil
Posts: 237
Joined: Tue Jun 29, 2010 10:27 pm
Contact:

Re: Defining a convex hull

Post by dphil » Sat Jul 03, 2010 11:13 pm

After reading this and other threads, I am still a bit confused (though I am starting to get an idea) about the uses and differences between btConvexHullShape, btConvexTriangleMeshShape and btShapeHull. This is what I currently understand or am unsure about:

btConvexHullShape - ideal for complex convex shapes. It takes a list of vertices (or one at a time via addPoint) and uses these as an implicit representation of a convex hull (but the exact shape of this hull is not explicitly stored; so can not directly access the faces of the hull, for example). The implicit shape may not be exactly the same as the original mesh the vertices were taken from, even if that mesh happened to be concave?

btShapeHull - A utility class for producing triangle data (via the buildHull function) from a btConvexShape, so that the shape becomes explicit. However, it appears that the hull built with this utility is a "simplified" version of the provided btConvexShape. Is it not possible just to build the *actual*, non-simplified shape that is implicit within the btConvexShape provided? I want to know if a shape I am visualizing (using btShapeHull mesh data) is the exact same as the collision shape implicitly used by a btConvexHullShape that I provide, for example.

btConvexTriangleMeshShape - This is one I am a bit more intrigued/curious about. I know its use seems to be discouraged in favour of btConvexHullShape, but it still seems like something I may want to use. How does it work, exactly? It can take in a triangle mesh. Great. Then what? Does it disregard the provided trimesh and use its vertices to compute a convex hull just like btConvexHullShape? Or does it directly use the provided mesh, similar to how btGImpactMeshShape does for concave shapes? And if so, how does it use the mesh for collision detection (since it's a convex shape, does it determine an "inside" vs "outside" for the provided mesh, meaning this type of shape can not be "hollow"?)? And what if the provided mesh is, in fact, concave?
On a side note, I have also heard people mention the drawback of trimesh duplication with the btConvexTriangleMeshShape. What is this referring to?

Clearing up these questions would help me know when and how to use these, particularly btConvexTriangleMeshShape. If the mesh I have is already convex, the only reason I figure I might want to use btConvexTriangleMeshShape over btConvexHullShape is if the latter does not necessarily preserve the original shape (triangles) of the mesh whereas the former does (ie so I can be sure of the collision shape I am getting). As a simple example, say I have a complex mesh that I produce using some graphics software, and I know the shape is convex, and I want that exact mesh shape to be used as a convex collision shape, including being a typical "filled" convex shape ("collides" with objects even if they are fully inside the mesh's contained volume).

Sorry about all the questions, but insight into all or any of these will help me (and probably others) a lot. Thanks.

sarbartha
Posts: 5
Joined: Fri Apr 19, 2013 5:18 am

Re: Defining a convex hull

Post by sarbartha » Fri Jun 28, 2013 9:29 pm

I have defined a btConvexTriangleMeshShape as you have shown above. And I got the shape also. Now I am trying to find the distance of a point from that shape. Its giving a distance from the Hull surrounding the mesh but not exactly from the surface.

Can you tell me how do I get that?

Or atleast get the closest triangle from that point in the mesh.

Post Reply