CGAL users discussion list

["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.