BREPLIBRARY IS NO LONGER MAINTAINED

Have a look at the more mature GTS library

The only documentation and test files available are the ones delivered with the source package. There are only two objects for testing union, intersection and difference. Note that some of the resulting files miss some faces. Nobody's working on the project (for more than a year now); it's been left in a development state we usually call 'alpha stage'. It isn't ready for practical use though it outputs meaningful shapes. It particularly doesn't handle coplanar faces, which is a huge flaw for engineers.

The library is supposed to handle holes: the face structure in BREP includes them, but it is untested. From the developer's point of view, the BREP data structure is difficult to understand. A better approach would not break up the split-edge abstract structure into so many C or C++ classes (depends on the version you downloaded). Moreover, there are techniques that garantee stable ouput (such as Simulation of Simplicity) which are not used within BREPLIBRARY.

If you still want to play with the code, note that you won't be able to build sub-library BREP as stand-alone since it defines functions that are implemented in sub-library CSG (CreateContour, CreateEdge, VertexCompare and VertexCompareLocation). BREP needs to interact with CSG structures and it was solved by this turn-around.

There are other libraries available that are still maintained and more robust:

GTS (LGPL license)

Open Cascade, Boolean operations component (LGPL-like, have to acknowledge use and send back modifications)

SvLis (not free)

News (June 2003)

C++ version 1.2 with minimal CSG code

News (May 2003)

C++ version with alternate input/output format (in CVS only)

Summary

Implementation of a topological data structure similar to the WINGED EDGE data structure, representing the boundary of a polyhedral solid. A core layer on top of which e.g. CSG operations or 3D model topology fixers can be implemented. Comes with a sample application for CSG.

BREP: Boundary Representation Library

The boundary (surface) of a solid is represented by means of a set of topological entities. These entities are:

solids: consist of one or more shells
shells: collections of connected faces, e.g. made of the same material
faces: bounded open subsets of a plane or a curved surface in 3D, delimited by an outer contour and zero, one or more inner contours describing holes. Holes may contain new outer contours with possible holes in turn etc...
contours: single closed piecewise smooth curve (a loop). Consists of directed edges called wings
wings: connection from a first vertex to a next vertex (directed edge)
edges: undirected connection between two vertices. Populated by one or two wings.
vertices: the "corners" of a solid.

The BREP library maintains adjacency and containement relations between these topological entities. It provides:

constructors and destructors to create/dispose of solids, shells in a solid, etc...
modifiers to split or join edges or contours, to create notches and slits, etc...
selectors and iterators, implementing queries such as "what are the contours in this face", "what face is sharing this edge on the other side", "what contours pass through this vertex", ...
for convenience, the library also allows to maintain a sorted octree of vertices in a solid, for fast vertex searching etc...

The BREP library does not maintain geometric or other information associated with topological entities. For instance: it does not maintain (and does not need to maintain) the coordinates of a vertex, the line equation of an edge, the plane equation of a (planar) face or the color of a shell. The library does not even assume that vertices are 3D points. It could as well be used to represent the topology of a (restricted kind of) computer network, in which e.g. an IP adres would be associated with each vertex and where wings correspond to physical wires between computers. Neither is planarity assumed: any topological structure consisting of pieces that could be laid down in a plane can be represented.

In the current C version of the library, additional information can be associated with topological entities by means of client data. A predefined set of callback functions to be implemented and registered by a user of the library will take care of allocating/disposing of storage for such client data and manipulating it. With the upcoming C++ version of the library, inheritance will be used for this purpose.

CSG: Sample application program

Command-line application computing the CSG union/difference/intersection of two solid objects in MGF files. Illustrates how to use the BREP library. Some results are shown below.

GDT: Generic Data Types Library (needed by BREP & CSG)

Something like the C++ Standard Template Library but much less ambitious and for C programs. Relict of the past.

POOLS: Memory Management routines on top of the C runtime library storage allocator (needed by BREP & CSG)

Contains malloc() and free() replacements useful in case you have large collections of small, but equally sized, memory objects. This library groups such objects in "pools". Each pool consist of a set of "pages" allocated using standard malloc() and disposed using free(). Unlike other libraries of this kind, you can freely interleave usage of this library with malloc() and free(), for other objects not maintained by the POOLS library. Storage and computation time overhead are much lower than with the standard malloc() and free(), which do not exploit knowledge that your objects are small and of equal size. The POOLS library once made my radiosity program (which evolved into RenderPark later on) faster by a factor of two.

MGF: Greg W. Larson and co's Material and Geometry Format library (needed by CSG)

3D model input file format used by the CSG application. See the MGF web site.

CSG Example

Solid A	Solid B
Union of A and B	Intersection of A and B
Difference A minus B	Difference B minus A

Status

Initial version, build on material dating back to the summer of 1996 - April, 12 2000
New version, C++ conversion of initial version, without POOLS nor GDT - February 2002 (only in CVS)
New version, replaced MGF I/O with a much simpler one - May 2003 (only in CVS)

To do:

CSG application does not yet correctly handle coplanar faces.
Implement Euler operations, for the construction and manipulation of solids with guaranteed consistent topology.

License

GNU Library Public License.

Projects using the BREP library

3dom: Solid Modeller
MeshItUp: 3D model topology fixer. Contact Philippe Bekaert.

Download

The project is hosted at sourceforge. CVS repository, Mailing lists, Bug Tracker are available at the project
administrative page on sourceforge.

Authors

Philippe Bekaert, Olivier Ceulemans.

If you want to contribute, drop some code/documentation and an e-mail to the project admins.

References

Kevin Weiler, "Edge-based Data Structures for Solid Modeling in Curved-Surface Environments", IEEE Computer Graphics and Applications, January, 1985.
Martti Mantyla and Reijo Sulonen, "GWB: A Solid Modeler with Euler Operators", IEEE Computer Graphics and Applications, September 1982.
Tony C. Woo, "A Combinatorial Analysis of Boundary Data Structure Schemata", IEEE Computer Graphics and Applications, March 1985.
Andrew S. Glassner, "Maintaining Winged-Edge Models", Graphics Gems II, James Arvo (editor), Academic Press, 1991.
Mark Segal and Carlo H. Sequin, "Partitioning Polyhedral Objects into Nonintersecting Parts", IEEE Computer Graphics and Applications, January, 1988.
Marc Segal, "Using Tolerances to Guarantee Valid Polyhedral Modeling Results", Proceedings of ACM SIGGRAPH 1990.

Page maintained by the BREP Library Team.
Last update: April, 12, 2000