3D well-composed polyhedral complexes

arXiv:1403.2980v1 [cs.CV] 12 Mar 2014 3D Well-composed Polyhedral Complexes Rocio Gonzalez-Diaz1, Maria-Jose Jimenez1, Belen Medrano Applied Math Department, University of Seville, Av. Reina Mercedes, s/n, Seville, Spain e-mails: {rogodi,majiro,belenmg}@us.es March 13, 2014 Abstract A binary three-dimensional (3D) image Iis well-composed if the boundary surface of its continuous analog is a 2D manifold. Since 3D images are not often well-composed, there are several voxel-based methods (“repairing” algorithms) for turning them into well-composed ones but these methods either do not guarantee the topological equivalence between the original image and its corresponding well-composed one or involve sub-sampling the whole image. In this paper, we present a method to locally “repair” the cubical complex Q(I) (embedded in R3) associated to Ito obtain a polyhedral complex P(I) homotopy equivalent to Q(I) such that the boundary of every connected component of P(I) is a 2D manifold. The reparation is performed via a new codification system for P(I) under the form of a 3D grayscale image that allows an efficient access to cells and their faces. Keywords: binary 3D image, well-composedness, cubical complex, polyhedral complex, homotopy equivalence, 2D manifold 1 Introduction 3D well-composed images [14] enjoy important topological and geometrical properties in such a way that several algorithms used in computer vision, computer graphics and image processing are simpler. For example, thinning algorithms can be simplified and naturally made parallel if the input image 1 is well-composed [13, 17]; some algorithms for computing surface curvature or extracting adaptive triangulated surfaces assume that the input image is well-composed [11]. However, our main motivation is that of (co)homology computations on the cell complex representing the 3D image [6, 7]. We could take advantage of a well-composed-like representation since computations could be performed only on the boundary subcomplex. Since 3D images are often not well-composed, there are several methods (repairing algorithms) for turning them into well-composed ones [15, 21], but these methods do not guarantee the topological equivalence between the original and its corresponding well-composed image. In fact, the purpose may even be to simplify as much as possible the topology (in the sense of removing little topological artifacts). However, we are concerned with the fact of preserving the topology of the input image having in mind cases in which subtle details may be important. In [18], the authors provide a solution to the problem of topology preservation during digitization of 3D objects. They use several reconstruction methods that all result in a 3D object with a 2D manifold surface. More specifically, one of the proposed methods is a voxel-based method called Majority Interpolation, by which resolution is doubled in any direction and new sampling voxels are added to the foreground under some constraints. Other method is based on the most common reconstruction methods for 3D digital images is the marching cube (MC) algorithm [16] which analyzes local configurations of eight neighboring sampling points in order to reconstruct a polygonal surface. There even exists a MC variant, called asymmetric marching cubes, which generates the reconstruction of manifold surfaces (see [19, page 101]). A different approach is made in [12], where the authors create a polyhedral complex as the continuous analog of a set of voxels with given digital adjacencies. They also show that such a continuous analog corresponds to the usual definition of iso-surface in the 3Dcase. In our approach, we first consider a a cubical complex Q(I) associated to a voxel-based representation of the given image I. Then, we develop a new scheme of representation, called ExtendedCubeMap (ECM) representation, based on a 3D grayscale image storing the cells and the boundary face relations of cells of Q(I). Working on an ECM representation of Q(I), we design a procedure to obtain a polyhedral complex P(I) homotopy equivalent to Q(I). The importance of our method is that the cells of P(I) are totally encoded in a 3D grayscale image gP, and their boundary face relations in a set of structuring elements BP. It is worth to mention that the set BPremains 2 the same for any polyhedral complex P(I) computed using our method. In our prequel paper [8], the complex P(I) homotopy equivalent to Q(I), was a cell complex constructed with more general building blocks than polyhedra depending on the local configuration of voxels. In this paper, P(I) is always a polyhedral complex, constructed with a general procedure (that is valid for all the local configurations), with the advantage that it can be stored in a matrix form (a 3D grayscale image) in a way that we do not need to build P(I) to obtain face relations between its cells. Section 2 is devoted to clarify, first, the correspondence between 3D binary digital images and cubical complexes; the notion of well-composedness is also introduced as well as its extension to complete polyhedral complexes. Section 3 describes a new codification system called ECM representation of cubical complexes which is also valid for other more general polyhedral complexes as we will see later in this paper. Section 4 describes the repairing algorithm to get a well-composed polyhedral complex, P(I), starting from the cubical complex Q(I) associated to a non-well-composed image I. The repairing process is, in fact, accomplished on the ECM representation EQ of Q(I) to get the ECM representation EPof P(I). Finally, we draw some conclusions and statements for future work in the last section. 2 3D Images, Polyhedral Complexes and Wellcomposedness Consider Z3as the set of points with integer coordinates in 3D space R3. A 3D binary digital image (or 3D image for short) is a set I= (Z3,26,6, B) (or I= (Z3, B), for short), where B⊂Z3is the foreground,Bc=Z3\B the background, and (26,6) is the adjacency relation for the foreground and background, respectively. A point of Z3can be interpreted as a unit closed cube (called voxel) in R3centered at the point and with faces parallel to the coordinate planes. The set of voxels centered at the points of Bin R3is called the continuous analog of Iand it is denoted by C(I). The boundary surface of C(I) is the set of points in R3that are shared by the voxels centered at points of Band those centered at points of Bc(see [1, 5, 20]). Recall that a 3D image I= (Z3, B) is well-composed [14] if the boundary surface of C(I) is a 2D manifold, i.e. each point has a neighborhood homeomorphic to R2(it “looks” locally like a planar open set). The set of 3 voxels of C(I), together with all their faces (squares, edges and vertices) and the coface relationship between them, constitute a combinatorial structure called cubical complex, denoted by Q(I) whose geometric realization is exactly C(I). The topology of Q(I) reflects the topology of Iwhenever (26,6)−adjacency is considered on I. This way, we will say that the cubical complex Q(I) associated to a 3D image Iis well-composed if the corresponding image Iis well-composed. Considering configurations of 8 cubes sharing a vertex, one finds eleven different 8−cube configurations (modulo reflections and 90−degree rotations) around a critical vertex, as showed in Fig. 1, where well-composedness condition is not satisfied. For the eleven 8−cube configurations, the central vertex vis a critical vertex in the sense that it does not have a neighborhood in the boundary surface of Q(I), homeomorphic to R2. These eleven 8−cube configurations come exactly from the (2 ×2×2)−configurations which contain one of the just two configurations being presented in [14, Fig. 3]. A cubical complex is a specific type of polyhedral complex (see [10]). A polyhedral complex Kis a combinatorial structure by which a space is decomposed into vertices, edges, polygons and polyhedra (cells, in general) that are glued together by their boundaries such that the intersection of any two cells of the complex is also a cell of the complex. Notice that the structure of a polyhedral complex Kcan be considered as purely combinatorial (i.e., a set of cells with coface relations between them), but in this work, it is associated to a specific geometric realization of Kin R3. The dimension of an i−cell σ∈Kis dim(σ) = i. A cell µ∈Kis a face of a cell σ∈Kif µlies in the boundary of σand dim(µ)≤dim(σ). The cell σis called a coface of µ. A cell µis maximal if it is not a face of any other cell σ∈Kand free if it is face of exactly one maximal cell of K. The boundary subcomplex ∂K is made up by the free cells of K, together with all their faces. The closure of a subset Sof Kis the smallest subcomplex of Kthat contains each cell in S. It is obtained by repeatedly adding to S each face of every cell in S. The star of S(denoted St S) is the set of all cells in Kthat have any faces in S. Note that the star is generally not a cell complex itself. The link of S(denoted by Lk S) is the closure of the star of Sminus the star of all faces of S.Kis an nD polyhedral complex if for any cell σ∈K,dim(σ)≤nand for some maximal cell µ∈K,dim(µ) = n. An nD polyhedral complex is complete if all its maximal cells have dimension n. Observe that if Kis complete, so it is ∂K. In particular, the cubical complex associated to an image I,Q(I), and its boundary subcomplex, ∂Q(I), 4 Figure 1: The eleven 8−cube configurations around a critical vertex. are, respectively, 3D and 2D complete polyhedral complexes. The following definition extends the notion of well-composedness to 3D complete polyhedral complexes. Definition 1. A 3D complete polyhedral complex Kembedded in R3is wellcomposed if the subcomplex ∂K is a disconnected union of 2D manifolds. Proposition 1. A 3D complete polyhedral complex Kis well-composed if the subcomplex ∂K satisfies that: (E1) any edge has exactly two 2-cofaces in ∂K; (E2) for any vertex v∈∂K,Lk {v}in ∂K has exactly one connected component. Proof. Take a point p∈∂K. Recall that ∂K is made up by a set of 2−cells, together with all their faces. If plies inside a 2−cell in ∂K, obviously the proposition holds; if plies on an edge e∈∂K, condition E1 applies and 5 hence the proposition holds, too; if pis a vertex of ∂K, the star of pin ∂K, is homeomorphic to a disk (thanks to conditions E1 and E2). Notice that conditions E1 and E2 are not satisfied (simultaneously) in the configurations showed in Fig. 1. Definition 2. Given a 3D complete polyhedral complex Kembedded in R3, a vertex vis critical if either E1fails for some 1−coface of vor E2is not satisfied by v. Then, Kis well-composed if there is not any critical vertex in ∂K. An alternative definition of well-composedness has been presented in [19, page 11] based on adjacency of maximal cells. In this paper, we use the one involving the notion of critical vertex given above since the repairing process is done on that vertices and their stars. 3 ExtendedCubeMap Representation In [2], the authors presented a data-structure (called CubeMap representation) designed to compactly store and quickly manipulate cubical complexes. A similar structure was first introduced in CAPD library [3] for computing cubical homology. In that representation, for each cube (voxel), vertices, edges, squares and the cube itself were encoded in a 3 ×3×3 array with values representing the dimension of each cell (see Fig. 2.c). For a set of voxels, the corresponding array is composed by overlapping copies of arrays of size 3×3×3. The CubeMap representation is, in fact, a 3D generalization of the Khalimsky grid, which has already been introduced and extensively used by V. Kovalevsky (e.g. in [9]). Inspired by that representation scheme, we define a new data-structure, called ExtendedCubeMap representation, that allows to store not only 3D cubical complexes but also the new polyhedral complexes that will be constructed. This new codification is still presented under a 3D array form, also encoding the dimension of the cells that are represented (that is, a 3D grayscale image). In such a structure, the information of boundary relations between represented cells will be extracted by searching for certain structuring elements inside the representation. An nD grayscale image is a map g:Zn→Z. Given a point p∈Zn, g(p) is referred to as the color of p. A structuring element is also an nD 6 grayscale image b:Db⊆Zn→Zwhose domain contains the origin o∈Db. A structuring element will be used to perform a given operation around a certain neighborhood of a point. Definition 3. Given an nD complete polyhedral complex K, an Extended- CubeMap (ECM) representation of Kis a triple EK= (hK, gK, BK)where: •hK:DK→Kis a bijective function, for a certain domain DK⊂Zn with as many points as cells in K. For each cell σ, denote by pσthe point h−1 K(σ)representing σ; •gK:Zn→ {−1,0,1,...,n}is an nD grayscale image, such that: –gK(p) = dim(hK(p)), for any p∈DK, . –gK(p) = −1, For any p∈Zn\DK. •BKis a set of structuring elements {b:Db⊂Zn→Z}such that for any i−cell σ∈K, there exists a single structuring element bσ:Dσ→Z in BKsuch that: –bσ(p) = gK(p+pσ), for any p∈Dσ. In particular, bσ(o) = i; –If p∈Dσand p6=othen either bσ(p) = i−1or bσ(p) = −1; –A point p∈Z3satisfies that p−pσ∈Dσand bσ(p−pσ) = i−1 if and only if prepresents a cell µ(that is, p=h−1 K(µ)) which is an (i−1)−face of σ. Remark 1. In order to visualize examples of ECM representations, from now on, a point p∈Z3is colored black if gQ(p) = 3, green if gQ(p) = 2, red if gQ(p) = 1, blue if gQ(p) = 0 and white if gQ(p) = −1. For a better understanding of the pictures, the reader is referred to the web version of this paper. An ECM representation of Kmay not exist and may not be unique (see, for example, Fig. 2.(c,d) which shows two different ECM representations of a single cube together with all its faces). Nevertheless, given a cubical complex Q(I) and the ECM representation EQof Q(I) given in Prop. 2, the procedures described in the next section will provide a unique polyhedral complex P(I) as well as a unique ECM representation EPof P(I). Since the map hKis bijective, each cell σ∈Kis represented by a single point pσ=h−1 K(σ)∈Zn. Moreover, for each p∈DK,gK(p) codifies the 7 Figure 2: a) A single voxel I; b) the cubical complex Q(I) associated to I; c) The color values in the CubeMap representation of Q(I) which is also an ECM representation of Q(I); d) The color values in the ECM representation EQof Q(I). In both c) and d) the central voxel is colored black. dimension of the cell in Kthat prepresents (that is, the cell σ=hK(p)). Finally, observe that the structuring element bσ:Dσ→Zassociated to a cell σ∈Kprovides a codification of the boundary face relations for σ. Therefore, within this codification system, the extraction of boundary faces of any cell σ can be done by checking if any of the structuring elements of BKfits around the point pσ(that is, the point in DKthat represents σ). This last operation could be seen as a morphological erosion of the 3D grayscale image gKby the corresponding structuring element. Definition 4. Given an ECM representation EK= (hK, gK, BK)of a polyhedral complex K, a structuring element b:Db→Zis said to fit around a point p∈DK⊂Znif, for any q∈Db,gK(p+q) = b(q). Fig. 3 shows an example of a polyhedral complex K, the color values in an ECM representation EKof Kand the structuring elements (modulo 90−degree rotations) associated to the cells of K. The following result provides an ECM representation of a cubical complex Q(I) associated to a 3D image I. Let rσbe the barycenter of σ∈Q(I) and DQ={p∈Z3such that p= 4rσfor some σ∈Q(I)}. Proposition 2. Let Q(I)be the cubical complex associated to a 3D image I, the triple EQ= (hQ, gQ, BQ)described below is an ECM representation of Q(I). •hQ:DQ→Q(I), where: –DQ={p∈Z3such that p= 4rσfor some σ∈Q(I)}; 8 Figure 3: Top: A polyhedral complex K(a solid pyramid). Middle: The color values of the voxels in an ECM representation of K. Bottom: Structuring elements (modulo 90−degree rotations) associated to the cells of K. –hQ(4rσ) = σfor σ∈Q(I); •gQ:Z3→ {−1,0,1,2,3}is given by gQ(p) = dim(σ)if p= 4rσ∈DQ, and gQ(p) = −1otherwise. See Fig. 2.d; •BQ={bℓ:Dℓ→Z}ℓ=1,2,3, where bℓ:Dℓ→Z(modulo 90−degree rotations) is given by: –D1={o, (±1,0,0),(±2,0,0)},b1(o) = 1,b1(p) = 0 for p= (±2,0,0) and b1(p) = 0 otherwise. See Fig. 4.x; –D2={o, (±1,0,0),(0,±1,0),(±2,0,0),(0,±2,0)},b2(o) = 2, b2(p) = 1 for p= (±2,0,0),(0,±2,0) and b2(p) = −1otherwise. See Fig. 5.x; –D3={o, (±1,0,0),(0,±1,0),(0,0,±1),(±2,0,0),(0,±2,0), (0,0,±2)},b3(o) = 3,b3(p) = 2 for p= (±2,0,0),(0,±2,0), (0,0,±2) and b3(p) = −1otherwise. See Fig. 6.x. 9 •Nℓ 8(p) are the vertices of the cube Cp. The following remark ensures that given a point p∈Z3such that gQ(p) = 0 (which corresponds to a vertex v=hQ(p)∈Q(I)), the modification of the map gQon the points in N≤2(p) only affects to points that either represent cofaces of vor do not represent any cell in Q(I). Remark 3. Let p∈Z3such that gQ(p) = 0. Let v=hQ(p)be the corresponding vertex in Q(I). •If q∈N≤2(p)\(N2 6(p)∪N2 12(p)∪N2 8(p)) then gQ(q) = −1 •If q∈N2 6(p), then either gQ(q) = 1 (qrepresents a 1−coface of v) or gQ(q) = −1. Analogously, if q∈N2 12(p), then either gQ(q) = 2 (qrepresents a 2−coface of v) or gQ(q) = −1. Finally, if q∈N2 8(p), then either gQ(q) = 3 (qrepresents a 3−coface of v) or gQ(q) = −1. See, for example, Fig. 8, which is an example of the values of gQon the set N≤2(p) where prepresents a vertex shared by eight cubes in Q(I). Now, the following method is performed on the ECM representation EQ to construct a new map gP:Z3→Z. Procedure 1. Start with the ECM representation EQ= (hQ, gQ, BQ)of a given cubical complex Q(I). 0. Initially, gP(p) = gQ(p)for any p∈Z3. 1. Compute the set R⊆Z3where p∈Rif gQ(p) = 0 and one of the structuring elements showed in Fig. 9 fits around p(that is, hQ(p)∈ Q(I)is a critical vertex). 2. For each point p∈R: •Compute the set STp⊆Z3such that q∈STpif one of the structuring elements given in Remark 2 fits around q(that is, hQ(q)is a cell in St{hQ(p)}). •gP(p) = 3; gP(q) = 2 if q∈N1 6(p); gP(q) = 1 if q∈N1 12(p); and gP(q) = 0 if q∈N1 8(p). See Fig. 10.a. 16 •For each point q∈STpsuch that gQ(q) = 1, let q1∈DQrepresent the other endpoint of qdifferent to p. Then: gP(q) = 3; gP(s) = 2 if s∈N1 6(q)\(N1(p)∪N1(q1)); and gP(s) = 1 if s∈N1 12(q)\(N1(p)∪N1(q1)); See Fig. 10.b. •For each point q∈STpsuch that gQ(q) = 2, let q1, q2, q3, q4∈DQ represent the 1-faces of the cell represented by q. Then: gP(q) = 3; and gP(s) = 2 if s∈N1 6(q)\(N1(q1)∪N1(q2)∪N1(q3)∪N1(q4)); See Fig. 10.c. Notice that the points q∈STprepresenting cubes in Q(I) remain with the same color value, that is, gP(q) = 3 = gQ(q). The above procedure could be improved by computing the sets Rand {STp:p∈R}at once, since the coordinates of the different cofaces of a point prepresenting a critical vertex in Q(I) are known. For the sake of clarity we have separated the seeking of critical vertices (the set R) and their cofaces (the set STpfor each p). Proposition 4. The map gP:Z3→Zis well-defined. Proof. Observe that the 3D space Z3can be decomposed into the following non-overlapping subspaces (see Fig. 8): S0={(4i+ 2 ±ℓ1,4j+ 2 ±ℓ2,4k+ 2 ±ℓ3)}i,j,k∈Z, ℓ1,ℓ2,ℓ3∈{0,1} S1={(4i+ 2 ±ℓ1,4j+ 2 ±ℓ2,4k),(4i+ 2 ±ℓ1,4j, 4k+ 2 ±ℓ2), (4i, 4j+ 2 ±ℓ1,4k+ 2 ±ℓ2)}i,j,k∈Z, ℓ1,ℓ2∈{0,1} S2={(4i+ 2 ±ℓ, 4j, 4k),(4i, 4j+ 2 ±ℓ, 4k), (4i, 4j, 4k+ 2 ±ℓ)}i,j,k∈Z, ℓ∈{0,1} S3={(4i,4j,4k)}i,j,k∈Z Then, color-changing process corresponding to a point q∈Z3with gQ(q) = i, for i= 0,1,2,3, is performed on Si∩N≤1(q). In fact, the colors of all the points in Si∩N≤1(q) are modified. Let q1, q2∈Z3be points with i1=gQ(q1)6=−1 and i2=gQ(q2)6=−1. The subsets Si1∩N≤1(q1) and Si2∩N≤1(q2) never intersect since: •N≤1(q1)∩N≤1(q2) = ∅if i1=i2, •Si1∩Si2=∅if i16=i2. 17 Figure 10: a), b) and c) Illustration of the three color-changing operations on gQto obtain gP. Figure 11: Color changing operation around a point representing the critical vertex in the top-left critical configuration of Fig. 1. Fig. 10 illustrates the different color-changing operations described in Proc. 1. In Fig. 11.a, the color values of the ECM representation EQ1of the cubical complex Q1represented on the top-left of Fig. 1, are shown. Fig. 11.b shows the color values obtained after performing Proc. 1 on EQ1. Now, we construct a new polyhedral complex P(I) and a correspondence hPbetween points with color values gP(p)6=−1 and cells of P(I), in a way that gP(p) = dim(hP(p)). Any point p∈Z3with gP(p) = 3 will represent a polyhedron such that its faces will be represented by points in its neighborhood N≤2(p). Later, we will define a set of structuring elements BPfor which (gP, hP, BP) is an ECM representation of P(I). The following polyhedra will be used in the construction of the polyhedral 18 Figure 12: New polyhedra created in P(I) associated with a vertex v∈Q(I), a unit edge e∈Q(I) with endpoints vand wand a unit square s∈Q(I) with 0−faces v,v1,v2and v3. complex P(I), that will be homotopy equivalent to Q(I). (a) The size−1 2cube c(v) centered at point v∈R3, with faces parallel to the coordinate planes. See Fig. 12.a. (b) The pyramid k(v, w) with apex a point wand base the square-face of c(v) whose barycenter lies on the edge e(v, w) with endpoints vand w. See Fig. 12.b. (c) The polyhedra {pi(v, v1, v2, v3)}i=1,2,3,4(where v, v1, v2, v3are four distinct points in R3forming a unit square s) given as follows: –p1(v, v1, v2, v3) is determined by the triangles t(v, v1) and t(v, v2), and the edges e(v1, v3) and e(v2, v3) where t(v, vi), i= 1,2, is the triangle face of k(v, vi) whose barycenter lies on the square s. See Fig. 12.d. 19 Figure 13: List of the hexahedra that can appear in P(I). Each point in bold represents the vertex of c(vi), for some i= 1,...,8, which lies inside the cube c(v). –p2(v, v1, v2, v3) is determined by the triangles t(v, v2) and t(v1, v3), the square s(v, v1) and the edge e(v2, v3), where s(v, v1) is the square face of c(v+v1 2) whose barycenter lies on the square s. See Fig. 12.e. –p3(v, v1, v2, v3) is determined by the four triangles t(v, v1), t(v, v2), t(v3, v1) and t(v3, v2). See Fig. 12.f. –p4(v, v1, v2, v3) is determined by the squares s(v, v1) and s(v, v2) and the triangles t(v1, v3) and t(v2, v3). See Fig. 12.g. •The 22 hexahedra {hi(v1, v2,...v8)}i=1,...,22 (where v1, v2...,v8∈R3 form a unit cube ccentered at a point v∈Z3, with faces parallel to the coordinate planes) showed in Fig. 13. In this picture, each bolded point represents the vertex of c(vi), for some i= 1,...,8, which lies inside the cube c. For example, the hexahedron on the top-left is cand the one on the bottom-right is the size−1 2cube c(v). The sets of data {Eα= (hα, gα, Bα)}α=A,B,D,E,F,G described below are ECM representations of the above polyhedra, whenever the coordinates of the vertices of the polyhedra are multiple of 1 2. 20 (a) DA=N≤1(p) for p= 4v. gA(p) = 3; gA(q) = 2 if q∈N1 6(p); gA(q) = 1 if q∈N1 12(p); gA(q) = 0 if q∈N1 8(p) and gA(q) = −1 if q∈Z3\DA. See Fig. 14.a. hA(p) = c(v); and hA(q) = σif σis a face of c(v) and q= 4rσ. Structuring elements (modulo 90−degree rotations) in BAare showed in Fig. 6.a, Fig. 5.a and Fig. 4.a. (b) DB={q} ∪ N≤1(r)\N1(q) where q= 4wand r∈Z3is the closest point to 4rk(v,w). gB(r) = 3; gB(q) = 0; gB(s) = 2 if s∈N1 6(r)∩DB;gB(s) = 1 if s∈N1 12(r)∩DB;gB(s) = 0 if s∈N1 8(r)∩DB; and gB(s) = −1 if s∈Z3\DB. See Fig. 14.b. hB(r) = k(v, w); hB(q) = w; and hB(s) = σif σis an i-face of k(v, w), and s∈DBis the closest point to 4rσsuch that gB(s) = i. Structuring elements (modulo 90−degree rotations) in BBare showed in Fig. 6.b, Fig. 5.b and Fig. 4.(a,b). (c) The values of gαfor the rest of the ECM representation Eα,α= D, E, F, G, are showed, respectively, in Fig. 14.(d, e, f, g). The values of hαare defined in an analogous way as above. Structuring elements (modulo 90−degree rotations) in Bα,α=D, E, F, G, are showed in Fig. 6.c, Fig. 5.(c,d) and Fig. 4.(a,b). The following procedure constructs the polyhedral complex P(I) and the map hP:DP→P(I). Procedure 2. Let EQbe the ECM representation of Q(I)from Prop. 2. Let gP:Z3→Zthe output of Proc. 1. Let DP={p∈Z3:gP(p)6=−1}. Let R be the set of points in Z3representing the critical vertices in Q(I). Let STp, p∈R, be the set of points in Z3representing the cells in St{hQ(p)}(these sets were computed in Proc. 1). Initially, P(I) = Q(I), and hP(p) = hQ(p)for any p∈Z3. For each p∈R, •Replace v=hQ(p)∈P(I)by the cube c(v)together with all its faces. See Fig. 12.a. Define hP|DA=hAwhere DA=N≤1(p)and hAis described above. 21 Figure 14: The color values in the ECM representations Eα,α= A, B, D, E, F, G, of the polyhedra (and all their faces) described in Fig. 12. •For each r∈STpsuch that gQ(r) = 1, let v, w ∈Q(I)represent the endpoints of e(v, w) = hQ(r). –If wis non-critical: ∗Replace e(v, w)∈P(I)by the pyramid k(v, w)together with its triangular faces. See Fig. 12.b; ∗Define hP|DB=hB. –If wis critical: ∗Replace e(v, w)∈P(I)by the cube c(v+w 2), together with its faces parallel to e(v, w). See Fig. 12.c. ∗Define hP|DA=hAwhere DA=N≤1(r). •For each r∈STpsuch that gQ(r) = 2, let v, v1, v2, v3∈Q(I)represent the 0−faces of σ=hQ(r)∈Q(I)(see Fig. 12.left). Let pi=h−1 Q(vi) for i=,2,3. –If v1, v2, v3are non-critical, ∗Replace σ∈P(I)by the polyhedron p1(v, v1, v2, v3)together with its quadrangular faces. See Fig. 12.d. 22 ∗Define hP|DD=hD. –If v1is critical but v2and v3are not, ∗Replace σ∈P(I)by the polyhedron p2(v, v1, v2, v3)together with its quadrangular faces sharing the edge e(v2, v3). See Fig. 12.e. ∗Define hP|DE=hE. An analogous case is when v2is critical but v1and v3are not. –If v3is critical but v1and v2are not, ∗Replace σ∈P(I)by the polyhedron p3(v, v1, v2, v3)together with its quadrangular faces. See Fig. 12.f. ∗Define hP|DF=hF. –If v1and v2are critical but v3is not, ∗Replace σ∈P(I)by the polyhedron p4(v, v1, v2, v3)together with its quadrangular faces sharing v3. See Fig. 12.g. ∗Define hP|DG=hG. –If v1, v2and v3are critical, ∗Replace σ∈P(I)by the cube c(v+v1+v2+v3 4)together with its square faces parallel to σ(see Fig. 12.h.). ∗Define hP|DA=hAwhere DA=N≤1(r). •For each r∈STpsuch that gQ(r) = 3, the 3-cell σ=hQ(r)is replaced by a 3-cell µwhich is one of the hexahedra showed in Fig. 13 depending on the number and positions of the critical vertices that are faces of σ. Define hP(r) = µ. Theorem 1. P(I)is a well-composed polyhedral complex homotopy equivalent to Q(I). Proof. Let us prove that the polyhedral complex P(I) is well defined: •By construction, all the faces of each cell in P(I) are also in P(I). •The intersection of any two cells of P(I) is also a cell of P(I), since during Proc. 2, each critical vertex vis replaced by c(v) (together with all its faces) in P(I) and each cell in St{v}is replaced by a new polyhedron (together with its faces). Besides, all the faces of the polyhedron 23 added at each step are used in the next steps as faces of the new added polyhedra. Finally, an hexahedron of Fig. 13 substitutes the corresponding cube in Q(I), whose faces are also faces of either previous cubes of Q(I) or new polyhedra in P(I). •P(I) is complete since the new added cells are always polyhedra together with all their faces. Let us prove now that a homotopy equivalence (see [4]) from P(I) to Q(I) can be constructed. The key point is that, for each critical vertex v∈Q(I), the cube c(v)∈P(I) is homotopy equivalent to v. The homotopy equivalence is given by the projection of all the points in c(v) onto v(in fact, it is a deformation retraction). The projection of the vertices of each cube c(v) to vleads, in a natural way, to homotopy equivalences between the rest of the new constructed polyhedra in P(I) and the corresponding cells of Q(I): •The pyramid k(v, w) is homotopy equivalent to the edge e(v, w), by the continuous function that maps the vertices of s(v, w) (where s(v, w) is the square face of c(v) whose barycenter lies on e(v, w)) to v, and wto w; and it is extended continuously to all the points of the polyhedron; •Analogously, the cube c(v+w 2) is homotopy equivalent to the edge e(v, w), by the continuous function that maps s(v, w) to v, and the ones of s(w, v) to w. •Each polyhedron pi(v, v1, v2, v3) (see Fig. 12) is homotopy equivalent to the corresponding square with vertices v, v1, v2, v3by the continuous function that maps the vertices of c(w) to wfor w=v, v1, v2, v3if wis critical, or wto wif not. It is extended continuously to the rest of the points of the polyhedron •Each hexahedron of quadrilateral faces (see Fig. 13) is homotopy equivalent to the corresponding unit cube obtained after mapping each size−1 2cube c(v) corresponding to a critical vertex v∈Q(I), to v. Finally the polyhedral complex P(I) is well-composed. Observe that after performing Proc. 2, we have replaced each critical vertex v∈Q(I) by a cube c(v)⊆P(I), and the set St{v} ⊆ Q(I) by Stc(v)⊆P(I) (see, for example, Fig. 1 and Fig. 15). We have to prove that conditions E1 and E2 of Prop. 1 are satisfied: 24 (E1) Any edge e=e(w1, w2) with endpoints w1and w2in ∂P (I) has exactly two 2-cofaces: –If ewas also an edge in ∂Q(I) satisfying E1, then neither w1nor w2were critical vertices and hence, ewill have as 2-cofaces either square faces (that remain the same from ∂Q(I)) or quadrilateral faces of the polyhedra d) or e) of Fig. 12. –If eis an edge of a cube c(v) for some critical vertex v, then ehas as 2-cofaces a square face of the cube c(v) and either a triangular face of a pyramid k(v, w) for some non critical vertex w, or a square face of a cube c(v+w 2) for some critical vertex w. –If eis an edge of a pyramid k(v, w2) for some critical vertex v, then either eis shared by exactly two triangular faces of the pyramid, or it is shared by a triangular face of the pyramid and a quadrilateral face of a polyhedron pi(v, v1, v2, v3) for some i= 1,2,3,4, and w1=vjfor some j= 1,2,3. See Fig. 12.(d-g). (E2) For any vertex w1∈∂P (I), Lk {w1}in ∂P (I) has exactly one connected component: –If w1was also a vertex in ∂Q(I) (that is, w1was a non-critical vertex and hence, satisfied condition E2), then Lk{w1}was a set of edges and vertices in ∂Q(I), that are faces of 2−cofaces of w1. In the case that any of those 2−cofaces were replaced by a polyhedron pi(v, v1, v2, v3) for some i= 1,2,3,4, some critical vertex vand such that w1=vjfor some j= 1,2,3, only one of the quadrilateral faces fof pi(v, v1, v2, v3) would lie on ∂P (I) and the edges and vertices in Lk{w1}in ∂Q(I) would be replaced by the edges and vertices of c(v) and k(v, w1) shared with f. The way of construction of the new polyhedra guarantees that Lk{w1}in ∂P (I) is still connected. –If w1is a vertex of a cube c(v) for some critical vertex vof Q(I), then, by construction, the 2-cofaces of w1are either square faces of c(v), or triangular faces of a pyramid k(v, w), for some non-critical vertex w, or square faces of an adjacent cube c(v+w 2) for some other critical vertex w, or quadrilateral faces of the polyhedra pi(v, v1, v2, v3) showed in Fig. 12. Then, Lk {w1}in ∂P (I), as one can guess from Fig. 12, has exactly one connected component. 25