CGAL users discussion list

[Cheng Zhao <>]

Thank you very much Sebastien.

I tried already constructing the net using boundary facets with Polyhedron_incremental_builder_3.

However, the problem is that it cannot handle the case shown in the attached picture, where the edge indicated by the red arrow is shared by 4 faces. Hence there is the orientation problem:
lookup_halfedge(): input error: facet 39 shares a halfedge from vertex 6 to vertex 4 with facet 19.

I do not know how the union handles this case, but it seems that it works (but unacceptably slow)...

2015-08-28 13:33 GMT+08:00 Sebastien Loriot (GeometryFactory) <>:

On 08/16/2015 12:16 PM, QYInst wrote:

I performed 3D Delaunay Triangulation on a point set.
Then I would like to select some of the joint cells (the overall shape is
not a convex hull) and then decompose this set of cells to convex hulls.
I successfully achieved it by constructing nef polyhedron from the cells
(tetrahedrons) and then applying convex decomposition of polyhedra.
The problem is that the procedure of constructing polyhedron from cells is
extremely slow given several hundred cells.

Basically below is my implementation:
1. For each of the cell in the joint cell set (vector<Cell_handle> cell),
get the 4 vertices (vector<Point> P) and create a nef polyhedron with them.
2. Get the union of the nef polyhedrons.
3. Decompose this nef polyhedron.

Below is the code for step 1 and 2.

for(size_t i = 0; i < cell.size(); ++i) {
   for(int j = 0; j < 4; ++j)
     P.push_back(cell[i]->vertex(j)->point();
   Nef_polyhedron_3 NPtmp(P.begin(),P.end());
   NP+=NPtmp;
   P.clear();
}

This loop is very slow when cell.size() is about 200.
Is there any better way to achieve my goal, i.e. decompose a set of cells to
convex hulls?
Any comments or suggestions will be highly appreciated.

I can see some speed up to avoid the union of nef polyhedra, by directly constructing the final nef using the boundary facets of
selected cell.

Sebastien.

--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/construct-polyhedron-from-tetrahedrons-tp4661074.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

Attachment: polyhedron.png
Description: PNG image