Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] construct polyhedron from tetrahedrons.

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] construct polyhedron from tetrahedrons.


Chronological Thread 
  • From: "Sebastien Loriot (GeometryFactory)" <>
  • To:
  • Subject: Re: [cgal-discuss] construct polyhedron from tetrahedrons.
  • Date: Fri, 28 Aug 2015 07:33:48 +0200
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-phdr: 9a23:XehhYRID22fxUadilNmcpTZWNBhigK39O0sv0rFitYgULPrxwZ3uMQTl6Ol3ixeRBMOAu6kC1bed6vi8EUU7or+/81k6OKRWUBEEjchE1ycBO+WiTXPBEfjxciYhF95DXlI2t1uyMExSBdqsLwaK+i760zceF13FOBZvIaytQ8iJ35/xib35osWPKyxzxxODIppKZC2sqgvQssREyaBDEY0WjiXzn31TZu5NznlpL1/A1zz158O34YIxu38I46FppIZ8VvDxcK08CLBZFz87KHsd5cvxtBCFQxHcyGEbVzBcqRdCChPZ7Rz8FrP2qCr9qqI99ySdOMDqV6EaUD++6L16CVWg3DwDMCQ4932Rj8hYg6dSoRbnrBt6ld2HKLqJPeZzK/uONegRQnBMC55c
  • Organization: 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.





Archive powered by MHonArc 2.6.18.

Top of Page