Research archive · original page Research.Union · last recorded update 2013-12-03
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 +. 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
-
W. Randolph Franklin. Parallel volume computation of massive polyhedron union. In 23rd Fall Workshop on Computational Geometry. City College, New York City, USA, 25–26 Oct 2013. (extended abstract).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.
BibTeX
@InProceedings{fwcg-2013, author = "Franklin, W. Randolph", title = "Parallel Volume Computation of Massive Polyhedron Union", booktitle = "23rd Fall Workshop on Computational Geometry", year = "2013", month = "25--26 Oct", address = "City College, New York City, USA", note = "(extended abstract)", href = "\bibhrefpt{171-fwcg2013-parallel-union}{171-fwcg2013-parallel-union-talk.pdf}", abstract = "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.", fulltext = "https://wrfranklin.org/p/171-fwcg2013-parallel-union.pdf", customlinkslides = "https://wrfranklin.org/p/171-fwcg2013-parallel-union-talk.pdf", mykey = "union3 topology parallel" } -
W. Randolph Franklin. Geometric operations on millions of objects. (talk), 24 July 2013.
BibTeX
@Misc{millions-2013, author = "Franklin, W. Randolph", title = "Geometric Operations on Millions of Objects", howpublished = "(talk)", month = "24 July", year = "2013", fulltext = "https://wrfranklin.org/p/169-millions-talk.pdf", href = "\bibhref{169-millions-talk}" } -
Wm. Randolph Franklin. Mass properties of the union of millions of identical cubes. In Ravi Janardan, Debashish Dutta, and Michiel Smid, editors, Geometric and Algorithmic Aspects of Computer Aided Design and Manufacturing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 67, pages 329–345. American Mathematical Society, 2005.Talk (HTML),
BibTeX
@InCollection{wrf-dimacs2005, author = "Franklin, Wm. Randolph", editor = "Janardan, Ravi and Dutta, Debashish and Smid, Michiel", title = "Mass Properties of the Union of Millions of Identical Cubes", booktitle = "Geometric and Algorithmic Aspects of Computer Aided Design and Manufacturing, {DIMACS} Series in Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "67", year = "2005", pages = "329--345", mykey = "union3 topology", succeeds = "wrf-dimacs2003", fulltext = "https://wrfranklin.org/p/104-dimacs03-union.pdf", customlinkslides = "https://wrfranklin.org/p/104-dimacs03-union-talk.pdf", href = "\bibhrefpt{104-dimacs03-union}{104-dimacs03-union-talk.pdf}" } -
W. Randolph Franklin. Analysis of mass properties of the union of millions of polyhedra. In M. L. Lucian and M. Neamtu, editors, Geometric Modeling and Computing: Seattle 2003, pages 189–202. Nashboro Press, Brentwood TN, 2004.
BibTeX
@InCollection{wrf-union-analysis-2004, author = "Franklin, W. Randolph", editor = "Lucian, M. L. and Neamtu, M.", title = "Analysis of Mass Properties of the Union of Millions of Polyhedra", year = "2004", booktitle = "Geometric Modeling and Computing: Seattle 2003", publisher = "Nashboro Press, Brentwood TN", pages = "189--202", isbn = "0-0-9728482-3-1", mykey = "union3 topology parallel", fulltext = "https://wrfranklin.org/p/101-siam04-union.pdf", href = "\bibhref{101-siam04-union}" } - 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.
-
Mohan Kankanhalli and Wm Randolph Franklin. Area and perimeter computation of the union of a set of iso-rectangles in parallel. J. Parallel Distrib. Comput., 27(2):107–117, June 1995. doi:https://doi.org/10.1006/jpdc.1995.1076.
BibTeX
@article{kf-apcus-92, author = "Kankanhalli, Mohan and Franklin, Wm Randolph", title = "Area and Perimeter Computation of the Union of a Set of Iso-Rectangles in Parallel", year = "1995", pages = "107--117", volume = "27", number = "2", doi = "https://doi.org/10.1006/jpdc.1995.1076", month = "June", journal = "J. Parallel Distrib. Comput.", keywords = "intersection, parallel computation, grids, area", fulltext = "https://wrfranklin.org/p/85-jpdc95-parallel-union-area.pdf", href = "\bibhref{85-jpdc95-parallel-union-area}", abstract = "Finding the area and perimeter of the union/intersection of a set of iso-rectangles is a very important part of circuit extraction in VLSI design. We combine two techniques, the uniform grid and the vertex neighborhoods, to develop a new parallel algorithm for the area and perimeter problems which has an average linear time performance but is not worst-case optimal. The uniform grid technique has been used to generate the candidate vertices of the union or intersection of the rectangles. An efficient point-in-rectangles inclusion test filters the candidate set to obtain the relevant vertices of the union or intersection. Finally, the vertex neighborhood technique is used to compute the mass properties from these vertices. This algorithm has an average time complexity of O(((n + k)/p) + log p) where n is the number of input rectangle edges with k intersections on p processors assuming a PRAM model of computation. The analysis of the algorithm on a SIMD architecture is also presented. This algorithm requires very simple data structures which makes the implementation easy. We have implemented the algorithm on a Sun 4/280 workstation and a Connection Machine. The sequential implementation performs better than the optimal algorithm for large datasets. The parallel implementation on a Connection Machine CM-2 with 32K processors also shows good results.", mykey = "topology kankanhalli parallel" } -
Chandrasekhar Narayanaswami and Wm Randolph Franklin. Boolean combinations of polygons in parallel. In Proceedings of the 1992 International Conference on Parallel Processing, volume. 17–21 Aug 1992.
BibTeX
@inproceedings{nf-bcpp-92, author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph", title = "Boolean Combinations of Polygons in Parallel", booktitle = "Proceedings of the 1992 International Conference on Parallel Processing", month = "17--21 Aug", year = "1992", volume = "", pages = "", fulltext = "https://wrfranklin.org/p/76-icpp92-boolean.pdf", href = "\bibhref{76-icpp92-boolean}", mykey = "chandra", keywords = "parallel computation, grids, intersection, CAD" } -
Chandrasekhar Narayanaswami and Wm Randolph Franklin. Edge intersection on the Hypercube computer. Information Processing Letters, 41(5):257–262, 3 April 1992.
BibTeX
@article{nf-eihc-92, author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph", title = "Edge Intersection on the {H}ypercube Computer", journal = "Information Processing Letters", year = "1992", volume = "41", number = "5", month = "3 April", pages = "257--262", keywords = "parallel algorithms, performance evaluation, intersection, grids", fulltext = "https://wrfranklin.org/p/68-ipl92-hypercube.pdf", mykey = "chandra", href = "\bibhref{68-ipl92-hypercube}" } -
C. Narayanaswami and Wm Randolph Franklin. Determination of mass properties of polygonal CSG objects in parallel. Internat. J. Comput. Geom. Appl., 1(4):381–403, 1991.
BibTeX
@article{nf-dmppcj-91, author = "Narayanaswami, C. and Franklin, Wm Randolph", title = "Determination of mass properties of polygonal {CSG} objects in parallel", journal = "Internat. J. Comput. Geom. Appl.", volume = "1", number = "4", year = "1991", pages = "381--403", fulltext = "https://wrfranklin.org/p/69-ijcga91-determination.pdf", href = "\bibhref{69-ijcga91-determination}", mykey = "chandra", succeeds = "nf-dmppci-91", keywords = "parallel computation, intersection, constructive solid geometry, area, grids" } -
Chandrasekhar Narayanaswami and Wm Randolph Franklin. Determination of mass properties of polygonal CSG objects in parallel. In Joshua Turner, editor, Proc. Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 279–288. ACM/SIGGRAPH, 5–7 June 1991.
BibTeX
@Incollection{nf-dmppci-91, author = "Narayanaswami, Chandrasekhar and Franklin, Wm Randolph", editor = "Turner, Joshua", title = "Determination of Mass Properties of Polygonal {CSG} Objects in Parallel", year = "1991", month = "5--7 June", pages = "279--288", booktitle = "Proc. Symposium on Solid Modeling Foundations and CAD/CAM Applications", publisher = "ACM/SIGGRAPH", fulltext = "https://wrfranklin.org/p/69a-turner91-determination.pdf", href = "\bibhref{69a-turner91-determination}", mykey = "chandra", precedes = "nf-dmppcj-91", keywords = "parallel computation, intersection, grids, constructive solid geometry, area" } -
Wm Randolph Franklin, Narayanaswami Chandrasekhar, Mohan Kankanhalli, Varol Akman, and Peter YF Wu. Efficient geometric operations for CAD. In Michael J. Wozny, Joshua U. Turner, and K. Preiss, editors, Geometric Modeling for Product Engineering, pages 485–498. Elsevier Science Publishers B.V. (North-Holland), 1990.
BibTeX
@incollection{fckaw-egoc-90, author = "Franklin, Wm Randolph and Chandrasekhar, Narayanaswami and Kankanhalli, Mohan and Akman, Varol and Wu, Peter YF", editor = "Wozny, Michael J. and Turner, Joshua U. and Preiss, K.", title = "Efficient Geometric Operations for {CAD}", booktitle = "Geometric Modeling for Product Engineering", publisher = "Elsevier Science Publishers B.V. (North-Holland)", year = "1990", note = "Selected and expanded papers from the IFIP WG 5.2/NSF Working Conference on Geometric Modeling, Rensselaerville, USA, 18-22 September 1988", pages = "485--498", fulltext = "https://wrfranklin.org/p/58-wozny90-efficient.pdf", href = "\bibhref{58-wozny90-efficient}", mykey = "topology chandra akman kankanhalli", keywords = "intersection, CAD, grids" } -
W. Randolph Franklin, Narayanaswami Chandrasekhar, and Mohan Kankanhalli. Parallel algorithms for geometric computing. In Final Program, SIAM Conference on Geometric Design, A17. 6–10 Nov 1989. (abstract only).
BibTeX
@InProceedings{fck-pagc-siam-89, author = "Franklin, W. Randolph and Chandrasekhar, Narayanaswami and Kankanhalli, Mohan", title = "Parallel Algorithms for Geometric Computing", pages = "A17", booktitle = "Final Program, {SIAM} Conference on Geometric Design", year = "1989", month = "6--10 Nov", mykey = "chandra kankanhalli", note = "(abstract only)" } -
Wm Randolph Franklin, Mohan Kankanhalli, Chandrasekhar Narayanaswami, and Varol Akman. Efficient intersection calculations in large databases. In International Cartographic Association 14th World Conference, A–62 – A–63. Budapest, August 1989.Unpublished full paper.
BibTeX
@inproceedings{f-eiclb-89, author = "Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar and Akman, Varol", title = "Efficient Intersection Calculations in Large Databases", booktitle = "International Cartographic Association 14th World Conference", address = "Budapest", month = "August", year = "1989", pages = "A-62 -- A-63", fulltext = "https://wrfranklin.org/p/60-budapest89-efficient.pdf", href = "\bibhref{60-budapest89-efficient}", mykey = "akman chandra kankanhalli", keywords = "intersection, grids" } -
Wm Randolph Franklin, Mohan Kankanhalli, and Chandrasekhar Narayanaswami. Efficient primitive geometric operations on large databases. In Proceedings National Conference Challenge for the 1990s GIS Geographic Information Systems, 1247–1256. Ottawa, 27 February - 3 Mar 1989. Canadian Institute of Surveying and Mapping.
BibTeX
@inproceedings{fkn-epgol-89, author = "Franklin, Wm Randolph and Kankanhalli, Mohan and Narayanaswami, Chandrasekhar", title = "Efficient Primitive Geometric Operations on Large Databases", booktitle = "Proceedings National Conference Challenge for the 1990s {GIS} Geographic Information Systems", address = "Ottawa", organization = "Canadian Institute of Surveying and Mapping", month = "27 February - 3 Mar", year = "1989", pages = "1247--1256", mykey = "geometry kankanhalli chandra", fulltext = "https://wrfranklin.org/p/59-ottawa89-efficient.pdf", href = "\bibhref{59-ottawa89-efficient}", keywords = "intersection, CAD, grids" } -
Wm Randolph Franklin. Efficient polyhedron intersection and union. In Proc. Graphics Interface, 73–80. Toronto, 1982.
BibTeX
@inproceedings{f-epiu-82, author = "Franklin, Wm Randolph", title = "Efficient polyhedron intersection and union", booktitle = "Proc. Graphics Interface", pages = "73-80", address = "Toronto", year = "1982", fulltext = "https://wrfranklin.org/p/15-gi82-xsect.pdf", href = "\bibhref{15-gi82-xsect}", mykey = "topology", keywords = "intersection, CAD" }
No publications match your search. Try another word or clear the search.