Subject: CGAL users discussion list
List archive
Re: [cgal-discuss] How to understand the implementation of 3D boolean operation?
Chronological Thread
- From: "Sebastien Loriot (GeometryFactory)" <>
- To:
- Subject: Re: [cgal-discuss] How to understand the implementation of 3D boolean operation?
- Date: Thu, 12 May 2011 17:28:40 +0200
If you are looking for a paper, I'll recommend this one:
@article{granados2003boolean,
title={Boolean operations on 3D selective Nef complexes: Data structure, algorithms, and implementation},
author={Granados, M. and Hachenberger, P. and Hert, S. and Kettner, L. and Mehlhorn, K. and Seel, M.},
journal={Algorithms-ESA 2003},
pages={654--666},
year={2003},
publisher={Springer}
}
file available here:
www.mpi-inf.mpg.de/~kettner/pub/nef_3d_esa_03.pdf
S.
ZHAO Junqiao (John) wrote:
Hi all,
I have been tried to implement Boolean operators on B-rep based models. In my implementation, two BSP trees are constructed using the facets of each model to partition the space into interior and exterior. Then, all the facets of the models are split and triangulated. At the end, the two BSP trees are traversed to mark the belonging of facets.
However, comparing with the 3D Boolean operation provided by CGAL, the performance of my algorithm is similar but the fatal problem is that sometimes the prediction gives wrong results, such as the facet is wrongly marked.
To solve this problem, I learnt that CGAL deploys exact kernel to solve the problem of rounding-off error and regularized set operations to prevent producing non-manifold facets. Although I have carefully read the definition of concepts in the manual(section 27), it’s still very hard for me to understand the code that implement the algorithm.
Are there any introductions of the ideas for implementation? To my understanding, CGAL marks the facets using explicit recorded topology information in Nef_polyhedron_3. But, it’s not clear to me that 1) how does CGAL calculate the intersection of facets and marked them correctly? 2) how to implement regularized set operations? 3) Does regularization() actually do triangulation?
It would be greatly appreciated that someone could give me some guidelines.
Best Wishes,
John
- [cgal-discuss] How to understand the implementation of 3D boolean operation?, ZHAO Junqiao \(John\), 05/11/2011
- Re: [cgal-discuss] How to understand the implementation of 3D boolean operation?, Sebastien Loriot (GeometryFactory), 05/12/2011
- RE: [cgal-discuss] How to understand the implementation of 3D boolean operation?, ZHAO Junqiao \(John\), 05/13/2011
- Re: [cgal-discuss] How to understand the implementation of 3D boolean operation?, Sebastien Loriot (GeometryFactory), 05/12/2011
Archive powered by MHonArc 2.6.16.