The formulae in this section display best in Firefox. When using Chrome, some math chars appear blank at some zoom levels. Some versions of Explorer really mess things up.

Here are new local topological formulae for the center of gravity of a polygon and polyhedron.

For a polygon:

Let {$\vec{M} $} be the 1st order moment. Then

{$$ \vec{M} = \sum_{\{(\vec{P},\hat{T}, \hat{N}) \} } \left\{ \right. $$}

{$$ \left. \frac{1}{6} \left( \vec{P} \cdot \hat{T}\right) \ \left(\vec{P} \cdot \hat{N}\right) \ \left( \vec{P} + \left( \vec{P}\cdot \hat{N}\right) \ \hat{N} \right) \right\} $$}

Let {$ \vec{C} $} be the center of gravity, and {$A$} be the area. Then

{$$ \vec{C} = \vec{M} \ / \ A $$}

For a polyhedron:

Let {$\vec{M} $} be the 1st order moment. Then {$ \vec{M} = $}

{$$ - \frac{1}{24} \sum_{\{(\vec{P},\hat{T}, \hat{N}, \hat{B}) \} } \left\{ \left( \vec{P} \cdot \hat{T}\right) \ \left(\vec{P} \cdot \hat{N}\right) \left( \vec{P} \cdot \hat{B} \right)

 \right. $$}

{$$ \left. \left( \vec{P} + \left( \vec{P}\cdot \hat{N}\right) \ \hat{N}

 + 2 \left(  \vec{P}\cdot \hat{B}\right) \  \hat{B}
 \right) \right\} $$}

Let {$ \vec{C} $} be the center of gravity, and {$V$} be the volume. Then

{$$ \vec{C} = \vec{M} \ / \ V $$}

These formulae are preliminary are may have errors.

This is part of a research theme of using the least amount of explicit information when processing polygons or polyhedra. A little more information is at Local Topology, which also references Union, although I need to expand them.

104-dimacs03-union.pdf and other papers and talks lists there describe the formulae for edge length, area, and volume.

However, in brief, a polygon is represented as a set of occurrences of incidences of vertices and edges, {$ \{(\vec{P},\hat{T}, \hat{N}) \} $}, where {$ \vec{P} $} is a vertex, {$\hat{T} $} is a unit tangent vector pointing from the vertex along an adjacent edge, and {$\hat{N} $} is a unit normal vector pointing from the edge towards the inside of the polygon. There is one triple for each case of an adjacent vertex and edge. For an N-gon, there are 2N triples.

For a polyhedron, we have {$ \{(\vec{P},\hat{T}, \hat{N}, \hat{B}) \} $}, which also has {$ \hat{B} $}, the binormal vector. A cube has 48 quadruples, one for each incidence of a vertex, edge, and face.

Note that the complete edges are not stored, although they are implicit. The polygon may have multiple nested or separate components and even non-manifold vertices.

(12/3/13)

UNION3 computes the volume and area of the union of many cubes: Processing {$10^8$} cubes of edge size 1/400 (of the universe size) took 5000 CPU seconds on a 3.4GHz Xeon.

Details: The data structure was an {$800^3$} uniform grid. The program used 100GB 57GB of main memory. The output volume was 0.765 (where the universe's volume is 1). If the cubes had not intersected at all, the output volume would have been 1.56 (meaning that the average point was inside 2 cubes). The output surface area was 831 (compared to 3750 if the cubes did not intersect at all). Of the 800,000,000 input vertices, 186,366,729 were visible, that is, not inside any cube, and so were output vertices. There were another 395,497,686 output vertices that were the intersection of 3 of the 600,000,000 input faces, and 811,328,383 output vertices that were the intersection of one of the 600,000,000 input faces with one of the 1,200,000,000 input edges. (Note: only those intersection that were not inside any input cube formed an output vertex.)

I listed the various comparisons to show that the sample dataset had many overlaps, and so was nontrivial and would exercise any boolean combination program.

UNION3 parallelizes very well. Using OpenMP with 2 processors containing 16 cores and 32 threads on the above 100M cubes example cut the elapsed time by over a factor of 10, down to 1740 473 elapsed seconds. The parallel version is probably correct because it computes same numbers as the serial version.

UNION3's execution time depends on the number of intersections. For {$10^8$} smaller cubes of size {$1/500$}, the parallel elapsed clock time was reduced to 1237 396 seconds (using a {$1000^3$} grid and 50GB of memory), because there were fewer intersections.

UNION3 scales down. Processing {$1,000$} cubes of size {$1/10$}, to compute a union volume of 0.573 and area of 19, took 0.04 0.02 seconds. Therefore it could be used to efficiently test for collisions among moving rigid objects, each approximated as a union of cubes, as follows. Compute the volume of the union of the set of possibly colliding objects. If it changes, the objects have started to overlap.

The talk mentioned in the previous announcement is a good intro to the principles. More details are here: Union, though that page has not been updated with the most recent results.

The significance of this result is as follows.

1. This implementation is a merely proof of principle. This is necessary because it is not obvious a priori that the ideas really work. Cubes were chosen because there is no round-off error when they intersect.
2. The concepts extend to the union of any set of polyhedra, with general topology (multiple nested shells of faces containing multiple nested loops of edges).
3. Since a general Boolean operation can be expressed in terms of unions and intersections, and since intersections are easier than unions, this can be extended to compute any mass property of any Boolean operation of a set of polyhedra.
4. As shown, and in contrast to most geometric algorithms, the algorithm is quite parallelizable.
5. This would appear to compare favorably with existing methods.
6. UNION3 does use a lot of memory to process large examples, but we believe any other method would use considerably more.

Next step: Try CUDA.

(updated 9/14/13 and 9/29/30 with newer results).