User:Jdoliner
Abstract: Constructive Solid Geometry(CSG) is a procedural modeling technique that represents solids as Boolean combinations of more primitive solids. Boundary Representation (B-REP) represents solids by their limits. Both of these systems have their own merits. My project will bring these two systems together by implementing methods for evaluating Boolean operations on B-REP. The algorithm to be implemented hinges upon calculating the intersection curves between Bezier patches.
Proposal: I propose to forward the goal of hybrid model support in BRL-CAD by implementing BREP on BREP CSG evaluation. To this end I propose an implementation of the BOOLE system detailed in Shankar Krishnan, Atul Narkhede, Dinesh Manocha (1996) (see link). The Boole system has a number of merits:
Firstly BOOLE is very robust. It is capable of performing operations on curved surfaces (such as NURBS and Bezier patches) and outputting trimmed Bezier patches without approximating using polyhedra. This prevents data proliferation and yields more useful results as the new surfaces can still be modified using control points. Note: although the algorithm is meant for curved surfaces, it is very easily applied to polyhedral surfaces. The system also uses floating points for arbitrary precision.
Secondly BOOLE is a realistically implementable solution, as is clear from the fact that Krishnan et al. details an implementation of the system. This was done in FORTRAN but will still be an invaluable reference for me throughout the implementation process. This implementation is open too.
Finally the BOOLE systems is concerned with efficiency. Not only is the algorithm already streamlined; the paper also details how to parallelize the system, which will make for a more lasting solution with today’s computers.
The BOOLE system's algorithm is as follows:
Data Structures The algorithm requires data stored as trimmed Bezier patches which are simply Bezier patches together with a closed sequence of curves defined in the domain of the patch. Note, Bezier patches are a subset of trimmed Bezier patches. And the paper notes that this algorithm is easily applied to algebraically defined surfaces. The structure also maintains adjacency information about the surfaces. It maintains which patches share a curve, the two patches to which a curve is attached, and the edges (in counter-clockwise order) to which each vertex is attached (winged edge storage structure). This adjacency storage method is easy enough to adapt to whatever fits best with the current BRL-CAD structures.
Assumptions The algorithm assumes that the surfaces form a manifold; mathematically this means they are locally homeomorphic to a euclidean space, which implies that they have a well-defined inside and outside, so boolean operations are well defined. The algorithm also assumes that the boolean operations on the these manifolds yield manifolds. To this end the system uses regularized boolean operations (see algorithm notes). The paper mentions that it is still possible to generate non-manifolds from manifolds even with regularized boolean operations; this is something I will have to look into as a possible bug. The paper states that given these assumptions it has been shown that there exists an unambiguous topological representation of the solid.
Step 1 The main part of the algorithm is computing the intersection curves between the two solids. It is also the most computationally expensive, and each patch of one solid must be checked with every patch from the other. However, a lot of pairs have no intersection, so the algorithm uses two techniques to prune the mn patches. The first uses bounding boxes (really fast) to eliminate pairs (Bezier patches possess the convex hull property); the second is more costly (which is why it's second) and uses linear programming (still polynomial) to find planes between the patches, which also eliminates the pair.
Step 2 The intersection between the remaining pairs of patches is computed next. This computation is by far the most difficult (but interesting) part. It relies on the fact that any space curve can be projected onto a plane curve with the correct linear transformation (a result from algebraic geometry). The algorithm first finds a suitable transformation to obtain the curve in a plane. This makes the computation of the intersection more manageable, although there are still some interesting twists. The paper goes into some detail on the mathematics required for this calculation and cites a number of other papers that contain more information. This section is a bit lengthy for inclusion in this proposal.
Step 3 The intersection curves become the trimming curves of our resultant Bezier patches. The curves partition each of the patches into pieces that are inside the other manifold and pieces that are outside the other manifold. We then have all the information needed to reconstruct the solid.
Algorithm Notes Regularized booleans avoid the problem of manifolds intersecting in lower-dimensional surfaces, for example unit spheres at (0,0,0) and (2,0,0) intersect in a point (1,1,1). Regularized booleans avoid this basically by using the interior of sets instead of the entire set and then taking the closure.
Production Notes The final product of my proposal will be a library to be added into the BRL-CAD codebase implementing the BOOLE system as described above. I am fairly certain that I will be able to use the B-REP structures as they are in the BRL-CAD codebase. Although as I understand these are presently undergoing rewriting, my project may involve some work on these if it makes sense with the project goals. Also should my project finish ahead of schedule, I intend to begin implementing the CSG primitives in BRL-CAD as B-REP objects. The most challenging part of this project is computing the intersection curve between two patches. Thus I intend to code this part first, and anticipate that it will take 4 weeks. After this I anticipate spending the next 4 weeks developing the remainder of the system, that is, making it compatible with all of the BRL-CAD structuresand setting up the other parts of the algorithm. These include the pruning methods to optimize the patch intersection computations and the methods needed to reassemble the B-REP from intersection curves. The final task is making sure that the outputs are all compatible with BRL-CAD. I anticipate about 1 week for each task. This leaves me with about 4 weeks at the end to debug everything and possibly if everything is running fine work on some related tasks.
About Myself: I am presently a third year math and computer science major at The University of Chicago. I have taken numererous classes on C/C++ programming and consider myself very comfortable with the two languages. I am also very comfortable with funtional programming languages, particularly Scheme and Lisp. Although these will be less handy for the BRL-CAD project. This project has very interesting mathematical underpinnings and as such piques my mathematical curiosity. There are also a number of interesting challanges to be overcome in implementing such a system. This project is one of the few in the GSoC pool that really interests both the Mathematician and the Programmer in me. Over the past 2 summers I have worked at Fermi National Laborartory writing a simulation of a liquid argon neutrino detector that was being built there. And as a researcher at The University of Chicago doing research on genetic programming. My experience in the later involved writing a working implementation of my research topic using Lisp and Python.
Patch (from last year) : http://sourceforge.net/tracker/index.php?func=detail&aid=1944674&group_id=105292&atid=640804
