UNION3 swMATH ID: 7532 Software Authors: Franklin, W.Randolph Description: Mass properties of the union of millions of identical cubes 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. par 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.par 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. Homepage: http://www.ecse.rpi.edu/~wrf/Research/union3/union3-DIMACS.pdf Keywords: Boolean operation; polyhedron; volume; mass property; uniform grid; parallel geometry computation; numerical examples; parallel computation; algorithm; UNION3 Related Software: Cited in: 1 Document Cited by 1 Author 1 Franklin, William Randolph Cited in 0 Serials Cited in 1 Field 1 Numerical analysis (65-XX) Citations by Year