Voronoi Fracture Demo Error

[StabInTheDark]

In the "Voronoi Fracture Demo" if you make "bbmax" larger than "10.0" there are errors when creating the shattered pieces.
There are missing pieces of the geometry.
The larger sizes increases the amount and frequency of the missing bits of geometry.
For example if you set the "VORONOIPOINTS" to 8 you will get 8 shards but there is missing geometry.
If you set "VORONOIPOINTS" to 2, most of the time you will get two
shards with some missing geometry but sometimes you will get only one shard.
Is there a way to eliminate these errors for larger sizes?
Is there a way to scale the algorithm?

P.S.
I am using Bullet version 2.81-rev2613.
I am wrapping Bullet for use in the Dark Basic Programming language.

[RBD]

Yes, simply using doubles instead of floats for the voronoi fracture code will fix this problem... as a quick test try adding BT_USE_DOUBLE_PRECISION to the preprocessor definitions.

[StabInTheDark]

RDB,

Thanks for taking the time to read my post.
I added BT_USE_DOUBLE_PRECISION to the preprocessor definitions in the libs and demos.
It has solved the issue in the demos.
Unfortunately it has introduced a bug into my dll project for use with Dark Basic Professional.
Back to debugging.

[StabInTheDark]

Using double precision in the demos helped but there are still errors.
Double precision has reduced the errors but not eliminated them.
Is this the best that can be excepted from this algorithm?
I have examined the code but can not seem to find any errors.
I really wanted to use voronoi shatter in the wrapper for DBpro.

[RBD]

Make sure you are working in local space (origin near center of object you want to fracture).
It simply becomes a math precision issue the further you get from origin (0,0,0); not really an algorithm problem.
Otherwise you can easily scale / translate your objects to and from around unit scale / origin, before and after fracture, that will work fine.

Edit: also, just to make sure... the actual mesh produced by the algorithm is the one that comes out of the convex hull computer (convexHC). That is the mesh you should be using in your own application and looking at, because as explained in the Note: in the middle of the demo, Bullet's demo convex hull approximation visuals may show cracks that don't exist in the actual mesh.

[StabInTheDark]

This is definitely starting to look like a real bug.
I have already extensively tested your suggestion unfortunately it has not solved the issue.
I would really like to solve this bug so I can contribute to this project.
In the demo the remark "// Use the mesh in convexHC for visual display or to perform boolean operations with."
had lead me to believe that "convexHC" contained all the data to create my visual geometry.
It seems that it is actually missing faces, so I create my geometry from this code.

Code: Select all

		
btCollisionShape* shardShape = new btConvexHullShape(&(convexHC->vertices[0].getX()), convexHC->vertices.size());
btShapeHull shapeHull((btConvexShape*)shardShape);
shapeHull.buildHull(shardShape->getMargin());
		
const btVector3* vertexBuffer = shapeHull.getVertexPointer();
const unsigned int* indexBuffer = shapeHull.getIndexPointer();

Is it possible that the missing faces in "convexHC" are related to the error?

EDIT: I posted this before I saw your edit. In the demo none of the visual geometry is made from "convexHC".

[RBD]

Not much I can add to what I wrote, sorry if it's not clear for you… best of luck.
Keep in mind the demo is just that, a basic example, it's not a complete application.

[StabInTheDark]

Would somebody else being willing to confirm this is a bug?
It is very clear to me that so far I'm the only one who has tested this demo.
If this demo is limited by a bug we need to consider fixing the bug or removing it from
Bullet's core. I suggest we fix it since I think bullet should have a working voronoi fracture.
I never implied I was looking for a complete application.
I assumed being open source posting a possible bug would be helping contribute.
I am going to research another method and will post here with my findings.

[Flix]

Would somebody else being willing to confirm this is a bug?

I think you should be more precise. I have not tested the voronoi shatter demo deeply, but from your posts it's not clear if it's a bug in the btConvexHullComputer (that is missing faces) or in some other parts of the voronoi shatter algorithm.

For sure btShapeHull reduces the number of convex hull vertices to a maximum of 42, and btShapeHull is used to display the collision shapes in libBulletOpenGLSupport: so you should NOT using it, and not relying on the shape displayed by the Bullet "demo engine".
You can try visualizing the shapes with a raycast technique to be sure, or just draw the faces returned from btConvexHullComputer (however from your posts it seems that you're using btShapeHull right because btConvexHullComputer is "eating" some faces... if so it can really be an issue related to the convex hull computer).

PS. I've posted this just to be sure it's not just a "visualization" problem: although if it depends on the scaling of the mesh it should be something different.

[RBD]

Strange last post SITD. Whether this is a troll thread or not, I suggest you look at the actual code, it's in fact very simple, and the algorithm implementation is less than a page. You'll see that it's an as straightforward brute force implementation of Voronoi as you can get, using plane half-spaces to cut out Voronoi shards given a set of cell points. It uses very simple math with plane normal equations, if there was a bug there, you'd find it in no time. No sense pretending the algorithm/code is a faulty black box... seriously, it's silly.

Now, the getVerticesInsidePlanes function does rely on cross and dot products, which are susceptible to floating point precision errors when using very large scales (or far away from origin). As I already explained to you, using double precision will help a lot, or simply working near unit scale will always work reliably. If you need to work at very large scale, scaling up shards post Voronoi operation takes simple multiplication operations.

[StabInTheDark]

Using double precision reduced the amount of errors.
I have posted two screen shots at two different scales.
The boxes were positioned at 0,0,0 and had no rotations applied.
Both errors appeared at the 3rd creation of the voronoi shatter object.
"Voronoi1.jpg" is at size "btVector3 bbmax(42.0,23.0,85.0);"
"Voronoi2.jpg" is at size "btVector3 bbmax(5.0,2.5,10.0);"

[RBD]

STID you're showing a screenshot of the Bullet demo approximation visuals, not the actual mesh produced by the voronoi fracture...

It's clearly explained in the code, it has also been explained to you in this thread already, and I'll repeat it here again: use the mesh found in the convex hull computer (convexHC) in your own application, that's where you'll find the accurate mesh produced by the Voronoi fracture; do not rely on the Bullet demo visuals, they are not accurate!!

[Flix]

Strange last post SITD. Whether this is a troll thread or not

If you're referring to my post I'm sorry, that was unintentional I simply forgot about the double-precision issues and I had the impression that SITD was relying on the btShapeHull's visuals.

@SITD: you can use my extension of libBulletOpenGLSupport if you need btConvexHullComputer's visuals (and raytrace support too). It's in the OpenGLEx subfolder of the demo I posted here: http://www.bulletphysics.org/Bullet/php ... =17&t=7159 (it requires STL). Whether you use it or not, its source code can be useful if you need to implement such features in your tests.

Both errors appeared at the 3rd creation of the voronoi shatter object.

This is strange; I'm not sure this is related to btShapeHull. Maybe I'll try to reproduce it myself: can you post the modified VoronoiFractureDemo.cpp file?

[Edit:]I think I've reproduced the issue and I can confirm that it is NOT related to the btShapeHull/btConvexHullComputer visualization method. Anyway it can be related to the fact that I didn't use BT_USE_DOUBLE_PRECISION when compiling.
Visualization problems produce cracks in geometry, usually like in this picture:

Bullet Physics Demo 010.png

However here some whole shards seem to be missing (does this happen with BT_USE_DOUBLE_PRECISION too?).

[RBD]

No Flix, my post was entirely directed at SITD's post.

But just to clarify, shapeHull.buildHull does not simply reduce vertices to 42, it actually approximates hulls by sampling them from only 42 directions for all of 3D space, so inevitably it misses edges, but most often it misses sharp protruding edges. Voronoi shards can have sharp protruding edges, especially the lower the cell point count, so this is why we get these kinds of results from the Bullet demo approximation visuals.

Obviously, you will have gaps between shards if you use a margin shrink. If you use a large scale, then indeed shards might be missing or gaps may also occur due to floating point precision, but using double precision should remedy that (up to a point, of course, best to fracture near normal scale and scale up results if need be).

[Flix]

Thanks, RBD

Anyway I was able to solve SITD's issue in the easiest possible way:
without using BT_USE_DOUBLE_PRECISION, I simply changed one single threshold value in your getVerticesInsidePlanes(...) method and the holes magically disappeared.
Here is the full method (for completeness):

Code: Select all

const btScalar value1 = btScalar(0.0001);
const btScalar value2 = btScalar(0.000005);//originally btScalar(0.000001); // Guess this value depends on the aabb size...
void VoronoiFractureDemo::getVerticesInsidePlanes(const btAlignedObjectArray<btVector3>& planes, btAlignedObjectArray<btVector3>& verticesOut, std::set<int>& planeIndicesOut)
{
	// Based on btGeometryUtil.cpp (Gino van den Bergen / Erwin Coumans)
	verticesOut.resize(0);
	planeIndicesOut.clear();
	const int numPlanes = planes.size();
	int i, j, k, l;
	for (i=0;i<numPlanes;i++)
	{
		const btVector3& N1 = planes[i];
		for (j=i+1;j<numPlanes;j++)
		{
			const btVector3& N2 = planes[j];
			btVector3 n1n2 = N1.cross(N2);
            if (n1n2.length2() > value1)
			{
				for (k=j+1;k<numPlanes;k++)
				{
					const btVector3& N3 = planes[k];
					btVector3 n2n3 = N2.cross(N3);
					btVector3 n3n1 = N3.cross(N1);
                    if ((n2n3.length2() > value1) && (n3n1.length2() > value1 ))
					{
						btScalar quotient = (N1.dot(n2n3));
                        if (btFabs(quotient) > value1)
						{
							btVector3 potentialVertex = (n2n3 * N1[3] + n3n1 * N2[3] + n1n2 * N3[3]) * (btScalar(-1.) / quotient);
							for (l=0; l<numPlanes; l++)
							{
								const btVector3& NP = planes[l];
                                if (btScalar(NP.dot(potentialVertex))+btScalar(NP[3]) > value2)
									break;
							}
							if (l == numPlanes)
							{
								// vertex (three plane intersection) inside all planes
								verticesOut.push_back(potentialVertex);
								planeIndicesOut.insert(i);
								planeIndicesOut.insert(j);
								planeIndicesOut.insert(k);
							}
						}
					}
				}
			}
		}
	}
}

P.S. I remember that when you first posted the Voronoi Shatter code, by playing with these two values, I was able to produce an "explosion effect". Now I've lost the code, but it was a funny effect to see (although it should not be used in production code, due to the huge overlap of all shards: it's probably better to apply some kind of radial impulse to all the bodies). This is just for fun