CGAL users discussion list

["ZHAO Junqiao \(John\)" <>]

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