[Smtk-developers] Evaluating boost.polygon for 2D modeling

[David Thompson]

Hi all,

I've been looking at whether we might use boost.polygon to get faster, more robust 2D modeling. My first experiments have been aimed at exercising and benchmarking it, not integrating it into SMTK. A progress report is below.

	David

## Simple exercises

Starting with Boost 1.52, the polygon package comes with a "segment" concept and a function for finding self-intersecting segments (used to precondition data for Voronoi diagram generation). It has an interesting quirk, but should be useful for breaking ill-conditioned model edges into multiple, proper model edges.

The quirk is that entirely coincident line segments are not eliminated or marked as redundant, so testing 2 copies of the segment (0,0)->(10,10) results in 2 identical output segments. However, testing (0,0)->(10,10) and (4,4)->(8,8) yields 4 output segments: (0,0)->(4,4); (4,4)->(8,8); (8,8)->(10,10); and (4,4)->(8,8).

Another quirk is the way boost.polygon reports "tessellations." Instead of providing triangles or quadrilaterals that compose a polygon, it generates trapezoids. The trapezoids always have 2 edges are aligned with either the horizontal or vertical axis. However, they may also have more than 4 points... I've seen some with more than 2 collinear points along the axis-aligned segments. So, what boost appears to actually report are convex polygons which are easy to triangulate. Not a deal-killer, but a definite quirk.

## Boolean exercises

After getting boolean operations working with simple rectangles, I did some timings on a more complex shape; I took the Chesapeake bay contour (7664 points in 1 very crinkly polygon) we've used for testing CMB and imported it into a boost.polygon model. It takes about 0.1 sec per boolean when I start subtracting random(-ish) rectangles but the cost decreases as more crinkly stuff gets removed, so that when punching 500 random rectangular holes, the amortized cost is 0.069 seconds per rectangle. Uniting all the holes and subtracting that is much faster.

You can see some attached pictures of the trapezoids reported for as part of the benchmark. Overall, it seems decently fast and also gets us Voronoi functionality as well.

## Using Boost.Polygon for an SMTK session

To expose boost as a 2D modeling kernel in SMTK will take some work. Boost does not distinguish between model vertices and mid-edge vertices, mainly because Boost does not model polygons with edges at all. The "segment" concept above is used only for Voronoi diagram computation; when you create a polygon, you provide an ordered set of points (and optionally a set of polygonal holes). So, the SMTK session bridging the boost polygon would have to track edges and their model-face adjacencies as well as map UUIDs to vertices, edges, faces and (perhaps) uses.

We would also have to provide an algorithm to discern which edges form closed polygons, but (1) we already have an implementation of this (vtkDiscoverRegions) that could be adapted and (2) we probably also want to keep a data structure identifying vertex-edge adjacencies anyway, since Boost doesn't provide it; boost's polygon sets are just bags of polygons with no relationship to each other.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Bay-NoHoles.pdf
Type: application/pdf
Size: 102991 bytes
Desc: not available
URL: <http://public.kitware.com/pipermail/smtk-developers/attachments/20150908/8e6c447f/attachment-0004.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BayStar.pdf
Type: application/pdf
Size: 37297 bytes
Desc: not available
URL: <http://public.kitware.com/pipermail/smtk-developers/attachments/20150908/8e6c447f/attachment-0005.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BayWith50Holes.pdf
Type: application/pdf
Size: 97341 bytes
Desc: not available
URL: <http://public.kitware.com/pipermail/smtk-developers/attachments/20150908/8e6c447f/attachment-0006.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: BayWith500Holes.pdf
Type: application/pdf
Size: 51692 bytes
Desc: not available
URL: <http://public.kitware.com/pipermail/smtk-developers/attachments/20150908/8e6c447f/attachment-0007.pdf>