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.
Contents
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
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