Implementing boundary representation modeling

Question

Does anyone have any good implementation strategies or resources for putting together a b-rep modeling system?

OpenCascade is an apparently good library for b-rep modeling (used by FreeCad and PythonOCC are both very cool) but the library is huge, complicated and may not be a good starting point to learn about b-rep modeling 'engines'.

I've done quite a bit of research paper reading, and while the fundamental math is useful for understanding why everything works, its left me with some implementation questions.

The halfedge data-structure seems to be the preferred way to store information about a body in b-rep implementations.

So a handful of questions in no particular order:

1. Using the halfedge data-structure how is rendering typically implemented? Triangulation based on the solid's boundaries?

2. How are circular faces/curved surfaces typically implemented? For instance a cylinder in one basic introduction to b-rep's I read, was internally stored as a prism. IE an extruded triangle and meta-data was stored about the cap faces denoting that they were indeed circular.

3. How are boolean operations typically implemented? I've read about generating BSP-Tree's along the intersection curves then combining those tree's to generate the new geometry. Are there other ways to implement boolean operations and what sort of pro's/con's do they have?

Thanks!

If you'd like to provide a code example don't worry about the language -- the questions are more about algorithmic/data-structure implementation details

Answer 1

I'm working on a B-Rep modeler in C# (I'm in a very early stage: it's an huge project) so I ask myself the same questions as you. Here is my answers:

1. Triangulation: I've not done this step, but the strategy I'm thinking about is as follow: project the face boundaries in parameter space to obtain 2D polygons (with holes), triangulate that with the ear clipping algorithm and then reproject triangle vertices in 3D space. For curved surfaces, I need to split the polygons with a grid in order to follow the surface;
2. For a cylinder, there is 3 edges : two circulars and one line segment. I have classes for each type of curves (Segment3d, Circle3d...) and each half-edge hold an instance of one of theses classes. Each face hold an instance of a surface object (plane, cylinder, sphere...);
3. There is an interesting project here based on BSP-Tree, but it uses CSG method, not B-rep. I'm still researching how to do this, but I don't think I will need a BSP tree. The difficulty is in computing intersections and topology.

The best books I've found on this subject:

• 3D CAD - Principles and Applications (old but still relevant)
• Geometric Modeling: The mathematics of shapes (more recent than the previous one, but less clear)