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.

My dedication: If selected to join the brlcad team over the second as part of google summer of code, I would treat that as a full time job and feel obligated to work at least 40 hours a week on it. I have select brlcad because it's a project I feel I could be very passionate about working on, therefore I'm certain I will wind up spending more than those 40 hours a week at times when my project has particularly interesting hurdles for me to overcome.

Timeline and deliverables: Step 1, Leveraging ON_Nurb: .5-1 weeks My planned solution will use the openNurbs solution the first step will be to make sure that these are all setup in the most logical way to be used in the intersection algorithms. This will include writing a few helper functions. I don't expect this to be a long step at all, it just has the potential to save me a lot of headaches down the road. Deliverables: Helper functions for ON_Nurb objects.

Step 2, Intersection (CPU solution): ~3 weeks With a bit of setup I'll be ready to get right into the meat of the task, intersecting two ON_Nurb objects together. It will take 2 ON_Nurbs, and return the path along which they intersect. This will allow us to easily form intersections and unions. The main worry with this algorithm is that the error will get out of hand. Prior solutions have either lacked the accuracy that is required for our solution, or used calculations that are far too expensive for our purposes. This will be the main hurdle of the project. Deliverables: Intersection Algorithm for ON_Nurb objects.

Step 3, restitching ~2 weeks After we can take two ON_Nurbs objects and intersect them succesfully to get the paths, we need to able to take these and restitch them properly into the resultant ON_Nurbs. This doesn't have the same algorithmic challenges that the previous step has but will really be a matter of bookkeeping. Delivarables: Restitching algorithm, leaving us with a functional intersection algorithm.

Step 4. testing, tweaking 1 week This isn't so much a step with set deliverables as a time that I'm sure I'll need just to tweek everything with the algorithm and make sure it's all running well and working together.

Step 5 GPU solution ~3 weeks: In http://www.uni-weimar.de/cms/fileadmin/medien/vr/documents/publications/Ray_Casting_of_Trimmed_NURBS_Surfaces_on_the_GPU.pdf a speed up in this algorithm was acheived by leveraging GPUs. This would be an ambitious thing to implement. Furthermore I don't have any experience programming GPUs. However this would be a very nice feature to have since this task parallellizes so well we would get a substantial speed boost. Deliverables: A functional GPU version of the above algorithm which would be much faster.

This leaves me with 4 weeks of unallocated time which I'm told is a good amount of time to leave in the GSoC period for random things that might arise and for integration of my implementation into the trunk.

Patch (from last year) : http://sourceforge.net/tracker/index.php?func=detail&aid=1944674&group_id=105292&atid=640804

Progress: Initial Commit: https://sourceforge.net/tracker/?func=detail&aid=2805742&group_id=105292&atid=640804

June 13th - June 15th -Implemented:

   -PointInTriangle
   -SegmentSegmentIntersect
   -SegmentTriangleIntersect
   -TriangleTriangleIntersect

June 15th - June 16th: Worked on making my code conform to all HACKING guidelines

June 16th: Wrote tests and fixed bugs in PointInTriangle Wrote tests for SegmentSegmentIntersect (thus far there don't seem to be any bugs) Question to look into: Cross products are creating a great deal of floating point inaccuracy is this to be expected or can I mitigate it in some way?

June 18th: Fixed numerous bugs both in my code and in test code. Tests are now very rigorous using rotations to generate large numbers of tests (these are nice becuase intersection is invariant under rotation so I still know the answer) At this point it seems that all of the low level functions are very robust.

June 19th,22nd: Implemented the function MeshMeshIntersect. The final goal of all of these functions, it doesn't handle degenerate cases yet. Next Steps: test the function very rigorously, since this function uses all of the lower level stuff it serves as a very good integrative test. Also these tests are closer to the sort of thing that it will actually be called on.

The only thing left that's need to actually perform CSG on meshes is implementing accounting systems to keep track of the curves and insert them as trimming curves.