Inverted tetrahedron correction

Depending on the shape of the polyhedron of the vertex, the vertex movement in step V2 and V6 may lead to the self-intersections of the vSDM. In this case, the model obtained after step V2 and V6 sometimes contains inverted tetrahedra. The inverted tetrahedra provide the wrong description of the spatial relationship among the vertices in the mapped model. In order to obtain a reliable correspondence of volume models by using only their mapped models on the target volume, the volumetric mapping method must guarantee a one-to-one mapping with no inverted tetrahedra between the volume model and the target volume.

After step V2, the OMS vertices are fixed on the OTS. However, almost all inverted tetrahedra can be corrected by moving freely all vertices except the OMS vertices inside the OMS. After step V6, both the OMS and IMS vertices are moved on only the OTS and ITS, respectively. Because of the limitation of moving the OMS and IMS vertices, inverted tetrahedra around the OMS or IMSs may not be corrected by moving only inner vertices. Here, MS is the set of the OMS and IMSs while TS is the set of the OTS and ITSs. When the inverted tetrahedron includes only one MS vertex or three MS vertices forming a patch on the MS, the inverted tetrahedron is almost always corrected by moving the inner vertices and the MS vertices on the TS.

On the other hand, when the inverted tetrahedron has one of six structures as shown in Figure 3.4, the inverted tetrahedron cannot be corrected by only moving the MS vertices and inner vertices. In Figure 3.4, red points represent the MS vertices while blue points represent the inner vertices. Similarly, red patches represent the patches on the MS while blue patches represent the patches nonadjacent to the MS. The six structures tend to cause the limited movement of each vertex in the inverted tetrahedra.

In this case, the inverted tetrahedron is divided into multi sub-tetrahedra in order to make a wider range of the vertex movement. After the division, each vertex is moved to correct the inverted tetrahedra.

3.2 Method 54

To sum up, I propose the following three methods for correcting the inverted tetra-hedra in step V3, V7 and V8.

[Correction method 1]

It is considered that a tetrahedron is inverted when at least one vertex of the hedron exists outside the polyhedron of the vertex (Figure 3.2 (b)). The inverted tetra-hedron is found by the visibility condition of the vertex from its neighbor vertices. The visibility condition is that the vertex v is visible from all vertices of the polyhedron of v. If the vertex v meets the visibility condition, there are no inverted tetrahedra including a vertex v. Otherwise, the tetrahedra including the vertices are regarded as to be inverted. The inverted tetrahedra are corrected by moving the vertices toward the suitable positions where the vertices meet the condition. The suitable position of the vertexv is determined depending on whether the polyhedron of the vertexv is a star-shaped polyhedron or not. If the polyhedron is star-shaped, the polyhedron con-tains the kernel region in which all points are always visible from the vertices of the polyhedron [9]. Then, the vertex v is moved to the kernel region. Otherwise, when the polyhedron of v is not star-shaped, the vertices forming the polyhedron ofv are moved to their kernel region without movingv.

The algorithm of Correction method 1 is described as follows. For each vertex v except the OMS vertices, support planes are calculated (the dotted lines in Figure 3.2 (c)) by extending the faces of the polyhedron of the vertexv. If the support planes form an enclosed region (the red region in Figure 3.2(c)), the enclosed region is regarded as the kernel region of the polyhedron. Then, v is moved toward the centroid of the kernel region. Otherwise, the inverted tetrahedra includingv are corrected by moving the vertices composing the polyhedron of v to the centroids of their kernel regions.

These processes are repeated until all inverted tetrahedra are corrected.

[Correction method 2]

In the step V3, Correction method 1 is applied to all vertices to correct all the inverted tetrahedra. On the contrary, in the step V7, Correction method 1 is applied to only the inner vertices to correct the inverted tetrahedra. Because of the vertex limitation for applying Correction method 1, there reminds inverted tetrahedra in the vSDM. The remained tetrahedra are corrected by moving the IMS verticesv_lalong the ITS. To achieve this, by the same way as Correction method 1, it is checked whether the kernel region of v_l exists or not. If the kernel region exists, intersection points between the kernel region and the ITS are calculated by using a collision detection for

3.2 Method 55

ϰD^ǀĞƌƚŝĐĞƐ

ϭƉĂƚĐŚŽŶD^

ϯD^ǀĞƌƚŝĐĞƐ

ϮD^ǀĞƌƚŝĐĞƐ

ϮƉĂƚĐŚĞƐŽŶD^ ϯƉĂƚĐŚĞƐŽŶD^

EŽƉĂƚĐŚŽŶD^

䐟 䐠 䐡 䐢

䐣

䐤

Figure 3.4: Six types of tetrahedral structures which need to be divided into multi sub-tetrahedra. The red points represent the MS vertices while blue points represent the inner vertices. Similarly, the red patches represent the patches on the MS while the blue patches represent the patches nonadjacent to the MS.

two triangular patches. Here, there are two kinds of the intersection points. One is the cross point between each edge of the kernel region and a patch of the ITS, and the other is that between each patch of the kernel region and an edge of the ITS. When there are the intersection points between the kernel region and the ITS, v_l is moved toward the centroid of the intersection points. Otherwise, if there is neither the kernel region nor the intersection points, Correction method 1 is applied to only the vertices constituting the inverted tetrahedra. Correction method 2 repeats these processes until all inverted tetrahedra are corrected or the number of inverted tetrahedra is not changed.

[Correction method 3]

After step V7, if there remains inverted tetrahedra and these have the structures shown in Figure 3.4, each inverted tetrahedron is divided into multi sub-tetrahedra by one of three division methods or combining three division methods shown in Figure 3.5. In Figure 3.5, a point with star shape represents a new vertex added to the tetrahe-dron of vSDM. The first division method divides a tetrahetetrahe-dron into four sub-tetrahedra by using as a new vertex the centroid of the four MS vertices, and connecting the new vertex with the four MS vertices. The second division method divides a tetrahedron into three sub-tetrahedra by using as a new vertex the centroid of the three MS

ver-3.2 Method 56

ŝǀŝĚĞŝŶƚŽϰ ŝǀŝĚĞŝŶƚŽϯ ŝǀŝĚĞŝŶƚŽϮ

㽢

ϰ

ϯ

Ϯ

ŝǀŝƐŝŽŶŵĞƚŚŽĚϭ ŝǀŝƐŝŽŶŵĞƚŚŽĚϮ ŝǀŝƐŝŽŶŵĞƚŚŽĚϯ

Figure 3.5: Three division methods. The point with star shape represents a new vertex added to the tetrahedron. The red points represent the MS vertices while blue points represent the inner vertices.

tices, and connecting the new vertex with the all vertices of the tetrahedron. The third division method divides a tetrahedron into two sub-tetrahedra by using as a new vertex the middle of the two MS vertices, and connecting the new vertex with the two inner vertices of the tetrahedron. The division steps for the six structures in Figure 3.4 are shown in Table 3.1. These division steps are determined so that each tetrahedron ob-tained after the division has only one MS vertex or three MS vertices constituting a patch on the MS. After the division steps, Correction method 2 is applied to the vol-ume model. The tetrahedral division and Correction method 2 are repeated until all inverted tetrahedra are corrected or all inverted tetrahedra have only one MS vertex or three MS vertices constituting a patch on the MS.