(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. . C. Narayanaswami and Wm Randolph Franklin. Internat. J. Comput. Geom. Appl., 1(4):381-403, 1991. (paper).
  2. . W. Randolph Franklin. In Geometric Modeling and Computing: Seattle 2003, pages 189-202.Nashboro Press, Brentwood TN, , 2004. (paper).
  3. . Wm. Randolph Franklin. In Geometric and Algorithmic Aspects of Computer Aided Design and Manufacturing, {DIMACS} Series in Discrete Mathematics and Theoretical Computer Science, pages 329-345.American Mathematical Society, , 2005. (paper, talk).
    Talk (HTML),
  4. 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.
  5. . Mohan Kankanhalli and Wm Randolph Franklin. J. Parallel Distrib. Comput., 27:107-117, 1995.
  6. . Chandrasekhar Narayanaswami and Wm Randolph Franklin. In Proceedings of the 1992 International Conference on Parallel Processing, Aug 1992. (paper).
  7. . Chandrasekhar Narayanaswami and Wm Randolph Franklin. Information Processing Letters, 41(5):257-262, 3 April 1992. (paper).
  8. . Chandrasekhar Narayanaswami and Wm Randolph Franklin. In Proc. Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 279-288.ACM/SIGGRAPH, , 5--7 June 1991. (paper).
  9. . Wm Randolph Franklin, Narayanaswami Chandrasekhar, Mohan Kankanhalli, Varol Akman and Peter YF Wu. In Geometric Modeling for Product Engineering, pages 485-498.Elsevier Science Publishers B.V. (North-Holland), , 1990. (paper).
  10. . W. Randolph Franklin, Narayanaswami Chandrasekhar and Mohan Kankanhalli. In Final Program, SIAM Conference on Geometric Design, page A17, 6--10 Nov 1989. (abstract only).
  11. . Wm Randolph Franklin, Mohan Kankanhalli, Chandrasekhar Narayanaswami and Varol Akman. In International Cartographic Association 14th World Conference, pages A-62 - A-63, Budapest, Aug 1989. (paper).
    Unpublished full paper.
  12. . Wm Randolph Franklin, Mohan Kankanhalli and Chandrasekhar Narayanaswami. In Proceedings National Conference Challenge for the 1990s GIS Geographic Information Systems, pages 1247-1256, Ottawa. Canadian Institute of Surveying and Mapping, 27 February - 3 March 1989. (paper).
  13. . Wm Randolph Franklin. In Proc. Graphics Interface, pages 73-80, Toronto, 1982. (paper).


<< Overlaying 3D Triangulations | Research Page List | Octrees >>