Surface-based computation of the Euler characteristic in the BCC grid (Q6186789)

In this paper, the authors propose three algorithms for computing the Euler characteristic in a body-centered cubic grid. In the algorithms, the authors use a surface-based approach and propose two frameworks. The first framework is the piecewise linear critical point Morse theory. For this framework, the authors introduce an algorithm that computes the Euler characteristic of the boundary by recording the changes in the lower level sets with a suitable elevation function \(f\), defined in such a way that no two vertices have the same function value. This is done by considering the lexicographic order of the \((x, y, z)\) triplets obtained from the coordinates of all the vertices, and function \(f\) maps each vertex onto its elevation defined as its position in the sorted list of all vertices. The complexity of the algorithm is \(\mathcal{O}(n_{\partial O} \log n_{\partial O})\), where \(n_{\partial O}\) is the number of faces in the boundary \(\partial O\). The second framework is the discrete version of the Gauss-Bonnet theorem, which states that the sum of angular vertex deficits in a polyhedron is equal to \(2 \pi\) times its Euler characteristic. For this framework, the authors introduce two algorithms. In the first algorithm, they visit all vertices of the boundary, classify them to one of four classes based on the local configuration of the incident voxels, and iteratively add the corresponding contribution of the vertex to the Euler characteristics. In the second algorithm, they visit all faces of the boundary and count the number of quad faces, the number of hex faces, and the number of vertices in the boundary. Then, they compute the Euler characteristic. The complexity of both algorithms is \(\mathcal{O}(n_{\partial O})\), where \(n_{\partial O}\) is the number of faces in the boundary \(\partial O\). The authors also compare their algorithms with algorithms based on counting the number of cells, either of the 3D object or of its 2D boundary surface. The experiments show that the author's, boundary-based approach is faster than the approach based on cell counting when the number of boundary cells is less than \(66\%\) of the number of interior cells.