This approach to computation of space arrangements may be used in disparate subdomains of geometric and visual computing, including geo-mapping, computer vision, computer graphics, medical imaging, geometric and solid modeling, and finite elements. In all such domains one must compute incidences, adjacencies and ordering of cells, generally using disparate and often incompatible data structures and algorithms. E.g., most of earlier algorithms for space decomposition and Boolean operations work with data structures optimized for selected classes of geometric objects.
Conversely, we introduce a computational architecture based only on linear algebra with sparse arrays and basic matrix operations. Therefore our formulation, cast in terms of (co)chain complexes of (co)boundary maps, may be applied to very different geometric objects, ranging from solid models to engineering meshes, geographical systems, and biomedical images. In particular, we use rather general cellular complexes, with cells homeomorphic to polyhedra, i.e., to triangulable spaces, and hence possibly non convex and with holes.
The main stage of our computational pipeline operates independently on each 2-cell of the input data sets, according to an embarrassingly parallel data-driven approach. It is remarkable that the approach works with collections of 2-manifolds with- or without-boundary, sets of non-manifolds, sets of 3-manifolds, etc., and not only with triangle meshes.
Extending this approach to Boolean solid operations is straightforward. Among other strong points we cite: the compact representation of cellular complexes; the combinable nature of maps, allowing for multiple queries about the local topology, by a single matrix multiplication; the parallel fragmentation of input cells empowered by cell congruence; and what we call "topological gift wrapping" algorithm.