ConvexHull and multithreading

[carli2]

Hello,

I'm generating the physics representation of the landscape as a compound collision of convex hulls.
When I try to call NewtonCreateConvexHull in more than one thread at the same time, Newton crashes.
The non-parallel case is very slow. The profiler tells me that ConvexHull::faceNormals and dgGoogol::operator* consume the most computation time.

Can you fix thread safety for hulls please?
Or should I use some other method to generate the physics representation of the terrain? (Voxels; I can triangulate them or hullify them; lots of them change each frame)

[Julio Jerez]

oh yes the funtion will crash,
the problem is that the pool allocator memory manager is no thread safe.

I can fix that, however how many hulld are you creation and hpow many vertices they have?
I did not think people will try to build convex hull at real time.


I will make the memory manager renetrant an thread safe aft I check in the kinamatic body

[Julio Jerez]

as a quick test for speeding up the hull you can try this locally
in this function: file ..\coreLibrary_300\source\core\dgConvexHull3d.cpp

Code: Select all

dgFloat64 dgConvexHull3DFace::Evalue (const dgBigVector* const pointArray, const dgBigVector& point) const
{
   const dgBigVector& p0 = pointArray[m_index[0]];
   const dgBigVector& p1 = pointArray[m_index[1]];
   const dgBigVector& p2 = pointArray[m_index[2]];

   dgFloat64 matrix[3][3];
   for (dgInt32 i = 0; i < 3; i ++) {
      matrix[0][i] = p2[i] - p0[i];
      matrix[1][i] = p1[i] - p0[i];
      matrix[2][i] = point[i] - p0[i];
   }

   dgFloat64 error;
   dgFloat64 det = Determinant3x3 (matrix, &error);

                 // the code use double however the threshold for accuracy test is the machine precision of a float.
   // by changing this to a smaller number the code should run faster since many small test will be considered valid
   // the precision must be a power of tow and no small then the machine precision of a double, float64(1<<30) can be a good value
   //dgFloat64 precision  = dgFloat64 (1.0f) / dgFloat64 (1<<24);
   dgFloat64 precision  = dgFloat64 (1.0f) / dgFloat64 (1<<30);
   dgFloat64 errbound = error * precision;
   if (fabs(det) > errbound) {
      return det;
   }

   dgGoogol exactMatrix[3][3];
   for (dgInt32 i = 0; i < 3; i ++) {
      exactMatrix[0][i] = dgGoogol(p2[i]) - dgGoogol(p0[i]);
      exactMatrix[1][i] = dgGoogol(p1[i]) - dgGoogol(p0[i]);
      exactMatrix[2][i] = dgGoogol(point[i]) - dgGoogol(p0[i]);
   }
   return Determinant3x3(exactMatrix);
}

try what the commnet says, use 1<<30 instead of 1<<24
it will do much fewer extended presion arithmetic which arebut very acurate, but expensive,

[carli2]

The hulls are at a maximum of 8 vertices, but they are much.

Sorry, I cannot test your ideas because there is no newton 2.xx source any more and the newton3 migration was not able until now.

[Julio Jerez]

If the point count is so small, then not optimization will help. The conve hull routine is very, very efficent.
I can say it is teh faster and more robust convex hull routine even made. In fact when it run in constant time for a convex hull of maximun points copunt regales of how menay point are passed in.
for example a 20 vetex conves hull will take teh same ampunt of tiem to calculate wher you pass 20 point, 2000 point or 2000000 million points. that's how good it is.
Hoewver this do not comes for free, the routine has a large overhead that can only be neglible for large point set.
your problem is that you are making too many small hulls all at once so the are paying the cost of the overhead too many time.
if you mesh is static there is another way. you can make a User mesh collision, and bascially build the polygon in teh call back at run time.
basically you will be making all of teh hull that are inside the colliding volume.
Another posibility is to make all teh convex and serialize then, teh you can simple fetch the one you need.
you can do that in core 200, but it will work best in core 300.


also I do not understand why you say that thre is no source code for core 200, all teh source is in the archive, I just remove for svn core 300.
It is very hard for me to maintain two versions of the engine. what it is that you see in core 200 that it is not in core 300?

[carli2]

also I do not understand why you say that thre is no source code for core 200, all teh source is in the archive, I just remove for svn core 300.
It is very hard for me to maintain two versions of the engine. what it is that you see in core 200 that it is not in core 300?

That's basically true, but I want to move to core300, so I don't invest much energy into maintaining a buggy version of a piece of software that is not maintained.
The latest version of core200 is not working any more. I'm relying on the binaries you published on the web page.

[carli2]

I tried to TreeCollision and it is much faster.

But there's a problem:

Code: Select all

#0 dgAABBTree::ImproveTotalFitness(0x7fffd08d2e40, 0x2725980, <optimised out>, <optimised out>) at ../../source/core/dgAABBPolygonSoup.cpp:437
#1 BuildTopDown at ../../source/core/dgAABBPolygonSoup.cpp:741
#2 dgAABBPolygonSoup::Create(<optimised out>, @0x1cbc580: {m_faceCount = 1, m_indexCount = 4, m_vertexCount = 3, m_normalCount = 1, m_faceVertexCount = {<dgArray<int>> = {m_granulatity = 262144, m_maxSize = 262144, m_array = 0x7fffd040d380, m_allocator = 0xde8bc0}, }, m_vertexIndex = {<dgArray<int>> = {m_granulatity = 262144, m_maxSize = 262144, m_array = 0x7fffd030d300, m_allocator = 0xde8bc0}, }, m_normalIndex = {<dgArray<int>> = {m_granulatity = 262144, m_maxSize = 262144, m_array = 0x7fffd0b41880, m_allocator = 0xde8bc0}, }, m_vertexPoints = {<dgArray<dgTriplex>> = {m_granulatity = 262144, m_maxSize = 262144, m_array = 0x7fffd000d280, m_allocator = 0xde8bc0}, }, m_normalPoints = {<dgArray<dgTriplex>> = {m_granulatity = 262144, m_maxSize = 262144, m_array = 0x7fffd050d400, m_allocator = 0xde8bc0}, }, m_allocator = 0xde8bc0}, <optimised out>) at ../../source/core/dgAABBPolygonSoup.cpp:1740
#3 dgCollisionBVH::EndBuild(0x2720280, <optimised out>) at ../../source/physics/dgCollisionBVH.cpp:95
#4 RUN(0x7fffcff35bc0) at voxelscripts.pas:240
#5 EXECUTE(0x0) at threadmanager.pas:86
#6 ?? at :0
#7 ?? at :0
#8 ?? at :0
#9 CLASSES_THREADFUNC$POINTER$$INT64 at :0
#10 CTHREADS_THREADMAIN$POINTER$$POINTER at :0
#11 ?? at :0
#12 ?? at :0
#13 ?? at :0
#14 ?? at :0
#15 ?? at :0


The mesh is not closed because I split the geometry into chunks. What exactly led to this crash?

[Julio Jerez]

I do not know, I never seen it crashing on that funtion, are you doing than form mutiplethread as well?

[carli2]

I do not know, I never seen it crashing on that funtion, are you doing than form mutiplethread as well?

No. I lock everything to call that function.

[Julio Jerez]

That can not be possible because that function is call for every single collision tree that is constructed, and I have never seen it fail.
In fact it is impossble for the function to fail. It will not fail under any circustance.