From BlenderWiki
Outline
My immediate goal is to implement the uniform grid cut algorithm with trimming. I have three reasons to do this before implementing the more advanced recursive subdivision algorithm:
- UGC is relatively easy and can serve as a "known good" reference while coding the RSD implementation.
- I want to post images of imported 3dm files for my midterm. The adaptive subdivision algorithm will probably not be done before the midterm, but the uniform subdivision algorithm will be.
- Trimming code should port well between UGC and RSD, so if it is bugfixed for UGC then it should create less of a complexity burden when transitioning to RSD. Bugfixing often isn't a linear process: bugfixing(A+B) is harder than bugfixing(A)+bugfixing(B), so I hope to simplify the process by separating the steps.
Code
The code is not ready for inclusion into blender yet, but I have put it in a github repository so that you can play with it if you want. It is split into two pieces, poly.cpp and poly_demo.cpp. Only compile poly_demo.cpp if you want the GLUT visualization; it #includes poly.cpp but doesn't link to it. Later on poly_demo.cpp will be detached and the code in poly.cpp will find its way into blender's shiny new UGC tessellator.
Trimming in Nurbana, then on my own
One thing that all major NURBS tessellation algorithms have in common is that trimming is performed in 2-dimensional UV parameter space, typically after the UGC or RSD algorithms split UV space into quads. Since my immediate goal is to implement the UGC algorithm and the subdivision step of UGC is trivial (a uniform grid), the natural next step is to implement trimming for UGC. Trimming involves tessellating the trim curves (NURBS curves in UV space) into polygons and then cutting the polygons out of the untrimmed UV mesh. Edge cases such as nested inner and outer trim curves, trim curves small enough to entirely fit inside a single subdivision cell, and self-intersecting trim curves are common, so the trim algorithm must be fairly robust. A cursory read of Nurbana's UGC trim code convinced me that it did not live up to these high expectations in its present form and that it would be difficult to adapt it in order to live up to these expectations. Therefore, I set out to learn enough 2D computational geometry to implement trimming on my own.
Taking a hint from the BRL_CAD 2012 implementer I wrote a GLUT visualizer so that I could implement the computational geometry code
- with a fast turn-around time (instantaneous compile and run)
- with a visualization of the internal state
- with the ability to rapidly challenge the code against interactively defined test geometry
This approach turned out to be wise, since the visualization allowed me to rapidly catch and squash several bugs that would have otherwise been inordinately difficult to locate.
The Chalk-Cart Algorithm
[2] details a robust algorithm for performing booleans on concave and self-intersecting polygons (the name "chalk-cart" comes from an analogy employed by the paper which is probably more amusing than helpful). The fundamental observation behind the paper is that winding number changes by 1 every time you cross an edge (minus a few edge cases, of course). Therefore, if you add vertices at all the intersection points of two polygons and record which vertices are "entering" and "exiting" the polygon according to a standard traversal order, you can then find unions/intersections/differences simply by traversing through edges from a vertex of known winding number and changing directions (hopping between polygons) in a certain manner at every intersection. The simplicity and elegance of this approach is remarkable, but the individual steps in the algorithm aren't entirely trivial to implement. I took them one at a time and visualized each component in order minimize the potential for bugs that were difficult to track down.
Line-Segment to Line-Segment Intersection
This was one of the fundamental building blocks of the other algorithms. I implemented the quick-rejection test from [4] and the actual intersection-finding code by writing each segment in parametric form, noticing that a 2x2 matrix equation resulted, and using the explicit formula for the inverse to solve for the affine interpolation parameters. This approach seemed to work reasonably well:
| 
| 
| 
|
Vertex Insertion
Once line segments can be intersected, it is conceptually trivial to add vertices at the intersections. This is the first stage in the chalk-cart algorithm. By the time I was done debugging this stage of the algorithm, the GLUT visualization code had already payed off. The subtle bug captured below (which only appears sporadically on edges that are intersected twice or more) could have lived a very long time had I not started playing with the vertices and noticed that they didn't flex where I expected.
| 
|
| Buggy | Fixed |
Point-in-Polygon Test
One last ingredient for the chalk-cart algorithm is a robust test to determine whether a point is in a polygon. This is used to determine the initial winding number (increments of +-1 happen when crossing an edge). I found a fast algorithm in [3] that did the trick even for concave, self-intersecting polygons:
Putting it All Together
Once the pieces were assembled, implementing the chalk-cart algorithm was relatively simple. The image below demonstrates the process of finding the intersection (formed by the union of lighter line segments). A trivial alteration changes this behavior to find the difference.
Next Steps
- Get the code to output multiple traversed polygons (this is a limitation primarily due to the viewer at present)
- Generalize to multiple subject polygons and then implement an optimization so that the code does not have to test every line segment against every other line segment while performing intersections. Since the locations of line segments in a grid are very predictable, this should amount to something resembling a raster algorithm.
- Integrate the UGC code into Blender!
References
[1] Weiler, K., & Atherton, P. (1977). Hidden surface removal using polygon area sorting. In ACM SIGGRAPH Computer Graphics (Vol. 11, pp. 214–222). ACM. Retrieved from http://dl.acm.org/citation.cfm?id=563896
[2] Greiner, G., & Hormann, K. (1998). Efficient clipping of arbitrary polygons. ACM Transactions on Graphics (TOG), 17(2), 71–83. Retrieved from http://www.inf.usi.ch/hormann/papers/Greiner.1998.ECO.pdf
[3] Hormann, K., & Agathos, A. (2001). The point in polygon problem for arbitrary polygons. Computational Geometry, 20, 131–144. Retrieved from http://www.inf.usi.ch/hormann/papers/Hormann.2001.TPI.pdf
[4] http://www.mochima.com/articles/cuj_geometry_article/cuj_geometry_article.html
