Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] How to understand the implementation of 3D boolean operation?

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





Archive powered by MHonArc 2.6.16.

Top of Page