Mass properties of the union of millions of identical cubes. (English) Zbl 1272.65028

Franklin, W. Randolph

Janardan, Ravi (ed.) et al., Geometric and algorithmic aspects of computer-aided design and manufacturing. DIMACS workshop computer aided design and manufacturing, October 7–9, 2003, Piscataway, New Jersey. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3628-5/hbk). DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 67, 329-345 (2005).

Summary: We present an algorithm and implementation, UNION3, for computing mass properties of the union of many identical axis-aligned cubes. This implementation has processed 20,000,000 cubes on a dual processor Pentium Xeon workstation in about one elapsed hour. The ideas would extend to the union of general polyhedra.
UNION3 works by combining three techniques. The first is a set of local topological formulae for computing polyhedral mass properties. No global topology is used, such as complete face or edge information, or edge loops and face shells. For example, the volume of a multiple component, concave, rectilinear object is \(\sum s_ix_iy_iz_i\) summed over the vertices \((x_i,y_i,z_i)\), where each \(s_i\) is a function of the directions of the incident edges. The second technique is a 3-D grid of uniform cells, which is overlaid on the data. Each cell has a list of edges, faces, and cubes that overlap it. Only pairs of objects in the same cell are tested for intersection. Experimentally, the uniform grid is quite tolerant of varying densities in the input. The third technique, building on the second, is the covered-cell concept. When a cell is completely contained within a cube, its overlap list is cleared, and objects in it are not intersected against each other (unless they both also overlap the same other, noncovered, cell). These techniques combine to reduce the expected computation time to linear in the number of cubes, regardless of the number of intersections.
In the slowest step of UNION3, which is testing pairs of objects in each cell for intersection, no inter-cell communication is required. Therefore UNION3 parallelizes quite well.
For the entire collection see [Zbl 1077.68111].

MSC:

65D32	Numerical quadrature and cubature formulas
65D18	Numerical aspects of computer graphics, image analysis, and computational geometry
65Y05	Parallel numerical computation

Keywords:

Boolean operation; polyhedron; volume; mass property; uniform grid; parallel geometry computation; numerical examples; parallel computation; algorithm; UNION3

Software:

UNION3