Application: Cutting Tool Path

• Represent path of a tool as piecewise line.
• Each piece sweeps a polyhedron.
• Volume of material removed is (approx) volume of union of those polyhedra.
• Image is from Surfware Inc's Surfcam website.

Traditional N-Polygon Union

• Construct pairwise unions of primitives.     Iterate.
• Time depends on assumed size of intermediates, and assumed elementary intersection time.
• P = size of union of an M-gon and an N-gon =(min(M,N)). P=O(MN).
• Time for union perhaps T=(P lg P) .
• Total T = (N lg N), T=O(N²lg N).
• Hard to parallelize upper levels of computation tree.

Problems With Traditional Method

• lg N levels in computation tree cause lg N factor in execution time. If N>20, that's significant.
• Intermediate swell: gets worse as overlap is worse.

• 

  The explicit volume has a complicated topology:
  • loops of edges,
  • shells of faces,
  • nonmanifold adjacancies.
    
• This is tricky to get right.
• The explicit volume is not needed for computing mass properties.
• The set of the vertices with their neighborhoods suffices.

Volume Determination

• Box:
  • V = _i s_i x_i y_i z_i
  • s_i: +1 or -1
  
  
• General rectilinear polygons:
  • 8 types of vertices, based on neighborhood
  • 4 are type "+", 4 "-"
  • Area = (s_ix_iy_i)
  • Perimeter = (+x_i+y_i)

Rectilinear Polyhedron Volume

• V = _i s_i x_i y_i z_i
• 2 classes of vertices: s _i = +1 , or -1.
• Extends to lower dimensional properties, like area and edge length.
• Extends to general polyhedra.

Vertex Classes

• Each vertex has 8 adjacent octants.
• Each octant is either interior or exterior to the polyhedron.
• Which octants are interior determines the vertex's sign.
• Debugging this was tricky.

Properties

The output union polyhedron will be represented as a set of vertices with their neighborhoods.

• no explicit edges; no edge loops
• no explicit faces; no face shells
• no component containment info
• represents general polygons: multiple nested or separate comps
• any mass property determinable in one pass thru the set
• parallelizable
• amenable to external storage implementation, if necessary.

Volume Computation Overview

• Find all the vertices of the output object.
• For each vertex, find its location and local geometry.
• Sum over the vertices, applying the formula.

Finding the Vertices

3 types of output vertex:

• vertex of input cube
• intersection of edge of one cube with face of another,
• intersection of three faces of different cubes.

Find possible output vertices, and filter them

• An output vertex must not be contained in any input cube.

Isn't intersecting all triples of faces, then testing each candidate output vertex against every input cube too slow? No, if we do it right.

Face-Face Intersection Details

• Iterate over the grid cells.
• In each cell, test all triples of faces, where each face must be from a different cube, for intersection.
• Three faces intersect if their planes intersect, and the intersection is inside each face (2D point containment).
• If the 3 faces intersect, look up s_i in a table and add a term to the accumulating volume.
• The implementation is easier for cubes.

Point Containment Testing

P is a possible vertex of the output union polyhedron.

Q: Is point P contained in any input cube?

A:

• Find which cell, C, contains P.
• If C is completely covered by some cube then P is inside the covering cube.
• Otherwise, test P against all the cubes that overlap C.

The expected number of such cubes is constant, under broad conditions.

Execution Time

• N: number of cubes
• L: edge length, in a 1x1x1 universe.
• Expected number of 3-face intersections = (N³ L⁶)

Effect of Grid

• Good choice of cell size: half the cube size.
• G: number of grid cells on a side = 2/L.
• Number of face triples: N³
• Prob. of a 3-face test succeeding = N^-2L⁶.
• Depending on asymptotic behavior of L(N), this tends to 0.
• With the grid, prob. of 3 tested faces actually intersecting = c, independent of N and L(N) .
• Big improvement!

Parallel Implementation

• Pentium-class processors allow only 3GiB memory per user process.
• Machine may have 12GiB real memory, so real memory > virtual memory!
• Solution: decompose problem into pieces and process in parallel.
• Cannot just slice up the input: this increases the area and edge length.
• Observation: inserting objects into cells is quicker than testing the cells for intersections.
• Solution:
  • Insert the {cubes, faces, edges} into the cells.
  • Dustribute the cells among the processors, and test for intersections in parallel.
  • Each process reads several GiB of data, but writes only 3 words: its part of the volume, area, length.

Implementation

• Very compact data structures.
• Random (Tausworth generator) uniform i.i.d. cubes.
• 1000 executable lines of C++.
• dual 2.4GHz Xeon with 4GiB memory, Linux.

Small Datasets are Fast

• 10,000 cubes
• 0.03 edge length
• 60x60x60 grid
• Not using parallelism
• Execution time: 2.5 CPU secs
• Memory: 15 MB.

Large Datasets are Feasible

• 20,000,000 cubes
• 0.009 edge length (quite small, few intersections).
• 500x500x500 grid
• Using 4 parallel processes.
• Execution time: 2000 to 2200 CPU secs per process. I.e., the work was evenly divided.
• Memory per process: 2.6 GB

Why not larger datasets? Address space limitations. Creating more parallel processes thrashes the memory. We're creating separate sequential processes, but still working on the interfacing.

Implementation Validation

1.  
   • The terms summed for the volume range up to 10¹⁵.
   • Errors would be unlikely to total to a number in [0,1].
2.  
   • The expected volume is 1-(1-L³)^N.
   • Compare to computed volume.
   • Assume that coincidental equivalence is unlikely.
3.  
   • Construct specific, maybe degenerate, examples with known volume.

Extension to General Polygons

The only data type is the incidence of an edge and a vertex, and its neighborhood. For each such:

• V = coord of vertex
• T = unit tangent vector along the edge
• N = unit vector normal to T pointing into the polygon.

Polygon: {(V, T, N)} (2 tuples per vertex)

Perimeter = -(V.T).            
Area = 1/2 ( V.T V.N )

Multiple nested components ok.

Extension to 3D

The only data type is the incidence of a face, an edge and a vertex, and its neighborhood. For each such:

• V = coord of vertex
• T = unit tangent vector along the edge
• N = unit vector normal to T in the plane of the face, pointing into the face.
• B = unit vector normal to T and N, pointing into the polyhedron.

Polyhedron: {(V, T, N, B)}

Perimeter = -1/2 (V.T)          
Area = 1/2 ( V.T V.N )

Volume = -1/6 ( V.T V.N V.B )

Intersection Volumes from Overlaying 3-D Triangulations

Existing 2-D implementation: overlay two planar graphs; find areas of all intersection regions.

E.g. overlay counties of the coterminous US against hydrography polygons. Map stats:

Map #0: 55068 vertices, 46116 edges, 2985 polygons
Map #1: 76215 vertices, 69835 edges, 2075 polygons

Total time (excluding I/O): 1.58 CPU seconds.

Future: Extend to 3-D.

Application: Interpolate some property from one triangulation to the other.

Extension: More Complicated Boolean Operations

Given a red object defined as the union of many overlapping cubes, and a similar blue one.

• Do they intersect?
• Simplified to 2-D: N red edge segments, and N blue ones.
• There may be O(N²) red-red and blue-blue intersections.
• You don't know them.
• There are O(1) red-blue intersections.
• Find them.
• No subquadratic worst-case algorithm (SFAIK).

Moral: sometimes heuristics are necessary.

Other Possible Extensions

• Online algorithm, with incremental input insertions, would be easy.
• Online deletion of cubes should be only a little harder, if covered cells not used.
• This could be fast enough to be process hundreds of cubes at video update rates (1/30 sec).

Summary

Guiding principles:

• Use minimal possible topology, and compact data structures.
• Short circuit the evaluation of volume(union(cubes)).
• Design for expected, not worst, case input.
• External data structures unnecessary, tho possible.

Allows very large datasets to be processed quickly in 3-D with algorithms where sweep lines might have problems.

A paper on this subject is at http://wrfranklin.org/research/union3/union3.pdf.

The html version of this talk is at http://wrfranklin.org/research/union3/index.html.