Approximate Convex Decomposition

by **jay3d** » Thu Jul 31, 2008 10:44 am

Hi,

Something interesting in here: http://cs.gmu.edu/~jmlien/research/app-cd/
and here: http://codesuppository.blogspot.com/2006/08/approximate-convexdecomposition.html

Check'em out :mrgreen:

by **Julio Jerez** » Thu Jul 31, 2008 10:54 am

jay3d wrote:Something interesting in here: http://cs.gmu.edu/~jmlien/research/app-cd/

I was looking at that paper to get some ideas how to implement in newton, I did some work but I have not finished yet, the idea for measuring concavity is brialliant but it had some flaws on it.
We will have a solution close to the one in the paper.

the secund link is maybe good for comercial and open source engines, but too naive for Newton as is produces a decompositions of such pour quality
that is unaceptable even for the lowest standards of aceptance of a production pipe line.

by **JernejL** » Thu Jul 31, 2008 12:56 pm

I used the second john ratcliff's algorythm, and i have to say it works awfully slow for anything above 1000 polygons, it is unacceptable for run-time use and creates a lot of redundant shapes that could be unified for less shapes, so my physics editor had a manual-fix step to get these shapes glued together, also the algorythm has too many variables that have to be set up properly for every different model, and it tends to break on concave parts of the shape that approach each other.

by **khaled** » Sat May 07, 2011 9:04 am

by **Julio Jerez** » Sat May 07, 2011 9:52 am

khaled wrote:Dear all,
You can find an implementation of the Hierarchical Approximate Convex Decomposition (HACD) here http://sourceforge.net/projects/hacd
--Khaled

Are you the author of the paper?

I read it, and I tryed an implementation, however I found some problems with it, maybe you can explain how to go about.
or Maybe if I am correct and the algorithm as stated in your paper, does fail with some particular configuration of concave face arrangents. Perhaps we can work together to find a work around.
I have some ideas how to improve the algorithm, and also how to make a little faster. I have not oppnned my version the end users because of that problem.
in all you sample the meshs are kind of organic and continue, but of you try a typical low to medium game mesh you will see the problem immidially
In fournd that the algorithm will fail on geometries with deep concave dents.
for example say you have something like a Boul, it can separate the borders into nice convex pieces, but as it sepate the pieces,
it leaves the inside of teh center and the outside as two seperate sheets whic do no make a nice convex part.

Or maybe I made a mistake, and you can tell me what I did wrong, or even better if you want if you give me permision, I can integrated into Netwon as a Contribution, "Giving all yours credict of course"

by **khaled** » Sat May 07, 2011 1:09 pm

Hi Julio,
Yes, I am the author of the paper. Yes you can integrate the library into Newton.
As I mentioned it in my last post, this is still a first version which needs a lot of optimizations and probably it does not handle all the cases...
Please, could you send me the models that the algorithm failed to deal with?

--Khaled

by **Julio Jerez** » Sat May 07, 2011 1:19 pm

Excenllent, I will start righ away to integrate your lib with Newton, :mrgreen:

This actually helps me a great deal, because I do not have to focus any more on writing the convex partition tool.

The aproach I was taking now was using a Dealnay decompoisition adn mesh recovery using Boollean, tehn afte that a hierchocal recontrution
But mans It pleage of round errors. Anyway that is anther story.

the meshes that can make fail is actually very simple, again IT may be that I jsut got teh algorith wrong, but I will deach my version fo your algorith and use you library as it.
In the mean time, what mesh format mesh woud you like to to run test?

by **khaled** » Sat May 07, 2011 1:20 pm

OFF or VRML is ok.
--Khaled

by **Julio Jerez** » Sat May 07, 2011 1:30 pm

Ok here is a test mesh that can remproduce the problem I mentioned

Code: Select all: #VRML V2.0 utf8 # Produced by 3D Studio MAX VRML97 exporter, Version 12, Revision 1.06 # Date: Sat May 07 10:28:14 2011 DEF Cylinder01 Transform { translation -16.86 0 45.85 children [ DEF Cylinder01-TIMER TimeSensor { loop TRUE cycleInterval 3.333 }, Shape { appearance Appearance { material Material { diffuseColor 0.3412 0.8784 0.7765 } } geometry DEF Cylinder01-FACES IndexedFaceSet { ccw TRUE solid TRUE coord DEF Cylinder01-COORD Coordinate { point [ 63.47 0 0, 31.73 0 -54.96, -31.73 0 -54.96, -63.47 0 0, -31.73 0 54.96, 31.73 0 54.96, 63.47 139.5 0, 31.73 139.5 -54.96, -31.73 139.5 -54.96, -63.47 139.5 0, -31.73 139.5 54.96, 31.73 139.5 54.96, 23.52 139.5 -39.15, 46.12 139.5 0, -21.68 139.5 -39.15, -44.29 139.5 0, -21.68 139.5 39.15, 23.52 139.5 39.15, 46.12 13.55 0, 23.52 13.55 -39.15, -21.68 13.55 -39.15, -44.29 13.55 0, -21.68 13.55 39.15, 23.52 13.55 39.15] } coordIndex [ 0, 1, 7, -1, 7, 6, 0, -1, 1, 2, 8, -1, 8, 7, 1, -1, 2, 3, 9, -1, 9, 8, 2, -1, 3, 4, 10, -1, 10, 9, 3, -1, 4, 5, 11, -1, 11, 10, 4, -1, 5, 0, 6, -1, 6, 11, 5, -1, 4, 3, 2, -1, 2, 1, 0, -1, 4, 2, 0, -1, 5, 4, 0, -1, 13, 17, 11, -1, 13, 11, 6, -1, 12, 13, 6, -1, 12, 6, 7, -1, 12, 7, 8, -1, 14, 12, 8, -1, 14, 8, 9, -1, 15, 14, 9, -1, 15, 9, 10, -1, 16, 15, 10, -1, 16, 10, 11, -1, 16, 11, 17, -1, 18, 19, 20, -1, 20, 21, 22, -1, 18, 20, 22, -1, 23, 18, 22, -1, 19, 12, 14, -1, 14, 20, 19, -1, 18, 13, 12, -1, 12, 19, 18, -1, 21, 15, 16, -1, 16, 22, 21, -1, 20, 14, 15, -1, 15, 21, 20, -1, 23, 17, 13, -1, 13, 18, 23, -1, 22, 16, 17, -1, 17, 23, 22, -1] } } ] }

by **Julio Jerez** » Sat May 07, 2011 2:06 pm

I just syc to you svn adress and go tteh code https://hacd.svn.sourceforge.net/svnroot/hacd

I am adding a contribution sub forde to teh Netwon core source forder, and I am placing your library there.
I will leave out the test file because there are too many of them.

what I will do is that I well export some of the representative one to the NGN format (that is the Newton format)
and the next estable update will have a new demo using aproximate convex decompostion using your library.

In fact the demo is made already, and the has and interface function for that already.
So let us see how fat I go this wekend.

by **Julio Jerez** » Sat May 07, 2011 2:29 pm

I integrated the library already, now I need to write the glue code to Newton. I leke a lot that is is very small.

by **khaled** » Sun May 08, 2011 12:11 pm

Thanks for the example.
You can find the associated decomposition here http://sourceforge.net/projects/hacd/fi ... s/bowl.jpg
It is true that I have not detailed how to deal with this kind of meshes in the article. To handle concave meshes you need to activate the option AddExtraDistPoints (i.e. SetAddExtraDistPoints(true)). What is done is that the algorithm will associate with each face a set of extra points that will be used only to compute the concavity but not the convex-hull.

The points are chosen as follows (cf. Figure http://sourceforge.net/projects/hacd/fi ... Points.jpg ). Let's consider the red face as being the face to be processed and let the yellow arrow be its normal. We will look for all the faces that have an opposite normal and that intersect with the ray starting at the barycenter of the red face and with direction the opposite of the yellow arrow. From all the found faces we will choose the nearest face, which is the blue one in the figure. The 3 vertices of the blue face are then associated with the yellow face as distance points.

The goal behind adding those extra points is to make the algorithm take into account the concave points when dealing with the convex parts.

You can find the code in the function HACD::InitializeGraph(). This part of the code is slow and should be optimized by using a kd-tree structure for instance.

Code: Select all: for(unsigned long f = 0; f < m_nTriangles; f++) { i = m_triangles[f].X(); j = m_triangles[f].Y(); k = m_triangles[f].Z(); m_graph.m_vertices[f].m_distPoints[i].m_distOnly = false; m_graph.m_vertices[f].m_distPoints[j].m_distOnly = false; m_graph.m_vertices[f].m_distPoints[k].m_distOnly = false; u = m_points[j] - m_points[i]; v = m_points[k] - m_points[i]; normal = u ^ v; if (m_addExteraDistPoints) {// we need a kd-tree structure to accelerate this part! Vec3<double> seedPoint((m_points[i] + m_points[i] + m_points[k]) / 3.0); long nhit = 0; for(size_t f1 = 0; f1 < m_nTriangles; f1++) { i1 = m_triangles[f1].X(); j1 = m_triangles[f1].Y(); k1 = m_triangles[f1].Z(); u1 = m_points[j1] - m_points[i1]; v1 = m_points[k1] - m_points[i1]; normal1 = (u1 ^ v1); if (normal * normal1 < 0.0) { nhit = IntersectRayTriangle(seedPoint, -normal, m_points[i1], m_points[j1], m_points[k1], distance); if ((nhit==1) && (distance >0.0) && ((distMin > distance) || (faceIndex == m_nTriangles))) { distMin = distance; faceIndex = f1; } } } if (faceIndex < m_nTriangles ) { i1 = m_triangles[faceIndex].X(); j1 = m_triangles[faceIndex].Y(); k1 = m_triangles[faceIndex].Z(); m_graph.m_vertices[f].m_distPoints[i1].m_distOnly = true; m_graph.m_vertices[f].m_distPoints[j1].m_distOnly = true; m_graph.m_vertices[f].m_distPoints[k1].m_distOnly = true; } } }

by **Julio Jerez** » Sun May 08, 2011 12:33 pm

This is execelent. I beleieve that that cover all cases them.
One last question, why AddExtraDistPoints is optional and is not applyed unconditonally on each mesh?

I added your library the engine already, and now I am writting the demo, I will post later to let you know, and I will make the annnoucement that now Newton supports
Advance approximated Convex Decomposition using your library.

Your algorithm to track concavity by the use the faces is very clever. I was very impresse with it.

by **khaled** » Sun May 08, 2011 1:10 pm

The algorithm is far from being perfect and I hope that people would be interested in improving it...

AddExtraDistPoints is too slow because of the brute force approach to find the associated faces. If not needed, probably you should not use it.

I have fixed some bugs lately. Please, try to have the last version integrated.

--Khaled

by **khaled** » Sun Jul 24, 2011 12:29 am

Dear all,
A new version of the HACD library is available. I added support for meshes with multiple connected components and fixed some bugs...
Enjoy!

--Khaled

Approximate Convex Decomposition

Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Re: Approximate Convex Decomposition

Who is online