(in WR Franklin → Research)

This theme computes mass properties of boolean operations on large sets of polyhedra, typically in linear time. Besides algorithms, it includes demo implementations such as computing the volume and area of the union of up to 20,000,000 cubes. That took one hour on a dual xeon workstation.

My technique is to combine several other themes. The first is to optimizes the composition of volume and union operators; finding the volume of the union of two polyhedra does not require finding their explicit union with global topology etc. That also uses my local topological formulae; see Mass Properties of Polyhedra from their Vertices' Local Topology. Finally, the linear execution time is effected with a uniform grid.

UNION2 is a demo program that finds the area and perimeter of the union of many random equal-sized squares. For example, for 100,000,000 squares with edge length 0.0006, the cpu execution time on a 1600 mhz pentium was only 11 minutes.

UNION3 is a fast algorithm for computing the volume, area, and other mass properties, of the union of many polyhedra. UNION3 is well suited for parallel machines. A prototype implementation for identical random cubes has processed 20,000,000 polyhedra, containing half a billion subfacets, on a dual processor Pentium Xeon workstation in about one hour.

UNION3 processes all the polyhedra in one pass instead of repeatedly combining them pair by pair. The first step finds the candidate output vertices. These are the 3-face intersections, edge-face intersections, and input vertices. Next, the candidates are culled by deleting those inside any polyhedron. The volume is the sum of a function of each survivor. There is no statistical sampling. Input degeneracies are processed with Simulation Of Simplicity. Since UNION3 never explicitly determines the output polyhedron, messy non-manifold cases become irrelevant. No complicated topological structures are computed. UNION3's simple flat data structures permit it to fork copies of itself to utilize multi-processor machines. The expected time is linear in the number of input, even when the number of intersections is superlinear.

The principal data structure is a 3-D grid of uniform cells. Each cell records overlaps of itself with any edge, face, or polyhedron. Intersection tests are performed only between objects overlapping the same cell. However, if a cell is completely contained in some polyhedron, i.e., (covered), then no intersection tests are performed in it, since none of those intersections would be visible. Indeed, altho there may be a cubic number of intersections, all but a linear number occur in these covered cells, and are never computed. Therefore the final time is linear.

Papers and Talks

1. bibtexsummary:[/wrf.bib,fwcg-2013]
   We present a parallel implementation of UNION3, an algorithm for computing the volume, surface area, center of mass, or similar properties of a boolean combination of many polyhedra. UNION3 has been implemented on the special case of the union of congruent isothetic cubes, and tested on $100,000,000$ cubes. The algorithm uses a volume formula that does not require first computing the explicit union. All that is needed is the set of output vertices, including each vertex's position and neighborhood. UNION3's computation does not use randomization or sampling, and its output is exact. The implementation is parallel, using OpenMP. When using 32 threads, UNION3's elapsed time is only a few minutes, and the speedup, compared to using one thread, is a factor of ten. When executed on uniform random i.i.d input, UNION3's execution time is linear in the number of output vertices. UNION3 is intended as an example of a parallel geometry algorithm whose techniques should be broadly applicable.
2. bibtexsummary:[/wrf.bib,millions-2013]
3. bibtexsummary:[/wrf.bib,wrf-dimacs2005]
   Talk (HTML),
4. bibtexsummary:[/wrf.bib,wrf-union-analysis-2004]
5. Mass Properties of the Union of Many Squares (Geometric Operations on Hundreds of Millions of Objects), DIMACS Workshop on Implementation of Geometric Algorithms, 4-6 Dec 2003, Rutgers University.
   Talk (HTML),
   Abstract: Local topological data structures, uniform grids, KISS lead to fast implementations on large datasets. This talk describes our algorithm and implementation to find the area and perimeter of the union of many squares. For 100,000,000 squares with edge length 0.0006, the CPU execution time on a 1600 MHz Pentium was only 11 minutes. Similar principles have led to other fast implementations. For example, finding the connected components in a 1024x1088x1088 universe of bits took 96 seconds, and connecting the components in a 2D example of 18573x19110 bits took 25 seconds. Another program finds the areas of all the nonempty intersections of two planar graphs. One example overlaid coterminous US counties on hydrography polygons. The two maps totalled 130K vertices and 5000 polygons. The execution time, excluding I/O, was 1.58 CPU seconds.
   Code.
6. bibtexsummary:[/wrf.bib,kf-apcus-92]
7. bibtexsummary:[/wrf.bib,nf-bcpp-92]
8. bibtexsummary:[/wrf.bib,nf-eihc-92]
9. bibtexsummary:[/wrf.bib,nf-dmppcj-91]
10. bibtexsummary:[/wrf.bib,nf-dmppci-91]
11. bibtexsummary:[/wrf.bib,fckaw-egoc-90]
12. bibtexsummary:[/wrf.bib,fck-pagc-siam-89]
13. bibtexsummary:[/wrf.bib,f-eiclb-89]
    Unpublished full paper.
14. bibtexsummary:[/wrf.bib,fkn-epgol-89]
15. bibtexsummary:[/wrf.bib,f-epiu-82]