Polyhedron convex hull generation

[pHySiQuE]

Fast generation of low-poly convex hulls.

Exact convex hull:

hull.jpg (54.35 KiB) Viewed 4914 times

Polyhedron method:

wrap.jpg (52.52 KiB) Viewed 4914 times

Code: Select all

   Leadwerks::Shape* ShapeShrinkWrap(Leadwerks::Model* model,float* matf)
      {
         Leadwerks::Mat4 mat = Leadwerks::Mat4(matf);
         Leadwerks::Vec3 p;
         Leadwerks::PhysicsDriver* driver = Leadwerks::PhysicsDriver::GetCurrent();
         Leadwerks::Shape* shape = NULL;
         std::vector<Leadwerks::Vec3> points;
         float mindist,d;
         Leadwerks::Surface* hulldata = Leadwerks::Surface::Create();

         //Collect vertices
         for (int i = 0; i < model->CountSurfaces(); i++)
         {
            model->surfaces[i]->Transform(mat);
            for (int v = 0; v < model->surfaces[i]->CountVertices(); v++)
            {
               p = model->surfaces[i]->GetVertexPosition(v);
               points.push_back(p);
            }
         }

         //Create planes
         std::vector < Leadwerks::Plane > planes;

         //Top
         planes.push_back(Leadwerks::Plane(0, 1, 0, 0));

         //Top ring
         planes.push_back(Leadwerks::Plane(-1, 1, 0, 0));
         planes.push_back(Leadwerks::Plane(1, 1, 0, 0));
         planes.push_back(Leadwerks::Plane(0, 1, -1, 0));
         planes.push_back(Leadwerks::Plane(0, 1, 1, 0));
         planes.push_back(Leadwerks::Plane(-1, 1, -1, 0));
         planes.push_back(Leadwerks::Plane(-1, 1, 1, 0));
         planes.push_back(Leadwerks::Plane(1, 1, -1, 0));
         planes.push_back(Leadwerks::Plane(1, 1, 1, 0));

         //Middle ring
         planes.push_back(Leadwerks::Plane(-1, 0, 0, 0));
         planes.push_back(Leadwerks::Plane(1, 0, 0, 0));
         planes.push_back(Leadwerks::Plane(0, 0, -1, 0));
         planes.push_back(Leadwerks::Plane(0, 0, 1, 0));
         planes.push_back(Leadwerks::Plane(-1, 0, -1, 0));
         planes.push_back(Leadwerks::Plane(-1, 0, 1, 0));
         planes.push_back(Leadwerks::Plane(1, 0, -1, 0));
         planes.push_back(Leadwerks::Plane(1, 0, 1, 0));

         //Bottom ring
         planes.push_back(Leadwerks::Plane(-1, -1, 0, 0));
         planes.push_back(Leadwerks::Plane(1, -1, 0, 0));
         planes.push_back(Leadwerks::Plane(0, -1, -1, 0));
         planes.push_back(Leadwerks::Plane(0, -1, 1, 0));
         planes.push_back(Leadwerks::Plane(-1, -1, -1, 0));
         planes.push_back(Leadwerks::Plane(-1, -1, 1, 0));
         planes.push_back(Leadwerks::Plane(1, -1, -1, 0));
         planes.push_back(Leadwerks::Plane(1, -1, 1, 0));

         //Bottom
         planes.push_back(Leadwerks::Plane(0, -1, 0, 0));

         //Adjust planes
         for (int i = 0; i < planes.size(); i++)
         {
            planes[i].Normalize();
            for (int v = 0; v < points.size(); v++)
            {
               d = planes[i].DistanceToPoint(points[v]);
               if (v == 0)
               {
                  mindist = d;
               }
               else
               {
                  mindist = min(mindist, d);
               }               
            }
            planes[i].d = mindist;
         }
         
         //Build shape
         Leadwerks::Vec3 na, nb, nc;
         for (int a = 0; a < planes.size(); a++)
         {
            na = planes[a].GetNormal();
            for (int b = 0; b < planes.size(); b++)
            {
               if (b != a)
               {
                  nb = planes[b].GetNormal();
                  for (int c = 0; c < planes.size(); c++)
                  {
                     if (c != a && c != b)
                     {
                        nc = planes[c].GetNormal();
                        if( planes[a].IntersectsPlanes(planes[b], planes[c],p))
                        {
                           bool ok = true;
                           for (int n = 0; n < planes.size(); n++)
                           {
                              if (n != a && n != b && n != c)
                              {
                                 if (planes[n].DistanceToPoint(p) > 0.0)
                                 {
                                    ok = false;
                                    exit;
                                 }
                              }
                           }
                           if (ok) hulldata->AddVertex(-p);
                        }
                     }
                  }
               }
            }
         }   
         if (hulldata->CountVertices() < 4)
         {
            hulldata->Release();
            return NULL;
         }
         shape = Leadwerks::Shape::ConvexHull(hulldata);
         hulldata->Release();
         return shape;
      }


[Julio Jerez]

Is that a question?

Yes that method of building convex hull for a set of plane equations is one of the older algorithm.
I think is was the algothithm uses by engine like quake and unreal for building brushes.

The problem is that is it no good a t all, it is actually one of eth worse method because it realize of the accuracy of the calculation of the intersection [point of thread or more plane equations, which very numerically unstable.

You image show a useful conversion, but that because ether planes happen to intersect and very well defined point, the moment the intersection point start to be close three result in far form a convex mesh.

the second problem is that it is no fast at all, I tis in fact the slowest known method,
the outer loop are three nested iterations over set of planes, that's cubic time complexity, which is probably the worse thong you want in an algorithm.
You test is fast because the number of plane is small, if you double the input planes it will take 8 time more time.
This is like saying a bubble sort is faster that a quick sort because the inner loop is faster, which is true as long as you data set is small.

The third problems is that, the method build the convex hull of a set of a set of planes, not the best fitting convex hull.

if you want a robust convex hull generation for you Tool you can use
http://code.google.com/p/juliohull/

This is my won version of the Best know algorithm for generation convex hull on any dimensions.
It is the same used in Newton, but this one was made standalone by the people at Nvidia.

That algothim has the property that if you pass the Max point count for you hull the construction time is constant. and it will always build the best fitting Hull.

[JoeJ]

One Idea for a more precise automatic physics remeshing tool would be:
Partition the mesh in groups using it's uv maps. Mostly that should separate things nicely like 4 wheels, chassis, spoiler.
Then for each group make a sparate convex hull and finally a compound.

[pHySiQuE]

I just posted it for other people to use. It's a good algorithm for some objects.

[Julio Jerez]

yes is good for simple object like making convex brushes. that's why game like quake and Unreal were using it. but the algorithm extremely error prompt, all you need is more the three plane coinciding in one corner and it goes banana.

[pHySiQuE]

My code does not go bananas!

[Julio Jerez]

Hey, I was browsing the net in search of people dissatisfactions with the engine, because there has engine a new development.
You are one of the end users that uses the Newton despite the strong pressure you get form you customers. These show up high in Google,

http://www.leadwerks.com/werkspace/topi ... entry61832
http://www.leadwerks.com/werkspace/topi ... entry28453

I see that there is a strong feeling that the Grass is greener of the other side of fence all based on propaganda, myth and false advertisement, and fan boys sheer leading.

Here is a tool NVidia released that the uses to compare Physx to other engines. They did their own interpretation of how Newton should work trying to perpetuate the myth.
So this weekend I did mine. I hope they have the decency to integrate that.

viewtopic.php?f=9&t=8836

Maybe you should show this to your users, so that the can see that Newton is not that much slower that Phsyx, and in fact is the thing that really count Newton outperform Physx while doing with more accuracy and stability.
Newton is faster, more accurate and more stable than Bullet in all counts.