Structured Volume Decomposition via Generalized Sweeping

 IEEE Transactions on Visualization and Computer Graphics ( Volume: 22, Issue: 7, July 1 2016)

​

黃慧光

introduction

• In a variety of computer graphics and engineering applications such as physically based deformation or free-form deformation, volumetric representations are often required
• better convergence properties and more space efficiency
• However, to date none of the existing techniques in the literature allows practitioners to efficiently generate a hex-mesh with controllable orientation（2015）
• In this paper, we introduce a new volumetric decomposition technique for the generation of a simple and predictable structured hex-mesh.

overview

​

​

​

​

​

​

​

• Computing 3D Harmonic Function
• Decomposition of H (H is the set of tetrahedra）
• 2D SKELETAL STRUCTURE
• 3D SKELETAL SURFACE
• PARAMETERIZATION AND HEX-MESHING

3D Harmonic Function

Decomposition of H

2D SKELETAL STRUCTURE

1. Corner Point Extraction

• Figure 4a shows a slice of a twisted U-shape model and its simplified medial axis.
• For each branch of the medial axis, if the area (for example, the dotted area in Figure 4a) bounded by its branch point, corresponding foot points and the boundary between foot points is smaller than 1/10 of the area of the slice, then we remove this branch.
• At this moment, if the simplified medial axis has only two end points, then we trace from the end points to the internal points, until the separation angle between the foot points of the current medial axis point is larger than a predefined value (we use 120◦ in this work).

​

• Otherwise there are more than two end points in the medial axis, and in this case we compute a principal component analysis (PCA) of the medial axis curves, to obtain the dominant direction from which to extract the bounding box.
• Once the bounding box is computed and the corners are mapped onto the flattened slices, the corner points are inversely mapped onto the original (non-planar) slices.
• Note that the bounding box of the medial axis may not produce desirable corners. In addition, for more symmetrical slices (e.g. circular shape), the orientation given by the PCA is less reliable. The corners of both situations will be adjusted by a smoothing process discussed next.

​

2. Computing the Corners of the Interior Structure

Corner Point Matching Over Level Sets

• After the corner points at individual level sets are extracted, they are matched between adjacent 3D level sets for the construction of a 3D inner skeletal surface (Section 5).

To determine the correspondence between corners at adjacent level sets, we employ a distance based greedy algorithm, modified by using the ratio of the eigenvalues of the PCA on the medial axis

• When a bifurcation occurs, emphasis is placed on the continuity of the adjacent chains from the previous levels wherever possible to maintain good spacing of the corners.
• For example, in Figure 4b, the invalid match (shown by the red dash line segment) loses the continuity. The adjacent chain in the previous slice becomes non-adjacent after bifurcation. The correct matching is shown by the cyan line segments. However, forcing continuity of chains can lead to distortion.
• As shown in Figure 4b, the matching line segments in the right are almost tangent to Li+1. Thus, the quad-region (shaded) formed by these four corners is skewed, leading to distortion in the subsequent hex-mesh.
• This is due to the independent nature of the extraction of the corners at their individual level sets and the rapid change of the surface features along the gradient of the harmonic function. We introduce a smoothing process to remove this noise and reduce distortion.

​

3D SKELETAL SURFACE

Bifurcation improvement

• The above basic bifurcation handling introduces a valence-6 extraordinary node at each side of the bifurcation on the boundary quad mesh (orange dot in the left figure of Figure 8b). This may lead to large distortion in elements at bifurcations whose neighborhood is relatively flat.

• To lessen the distortion, instead of associating the two unmatched components to a section across the saddle point as shown in Figure 6c, we map them to two sections as shown in Figure 8a. This splits the valence-6 (the number of neighboring hexahedral elements) extraordinary point into two valence-5 nodes (Figure 8b). This adds an additional component at the bifurcation (e.g., the purple region in Figure 8a).
• Note that this improvement is not required and can be selected by the user according to the surface characteristics around the bifurcations. We have applied this improvement to the kitten, fertility, blade, and rocker arm models in our experiments.

​

PARAMETERIZATION AND HEX-MESHING

• This section describes how to compute a seamless 3D parameterization and induce hex-meshes with large hexahedral components, after constructing S.

​

​

RESULTS AND DISCUSSION

• For all the models shown in this paper, at most 600 slices are used for the cutting, which takes up to 2 minutes to compute. The corner extraction (including medial axis computation) takes one min per slice. The time spent on the generation of hex-meshes ranges from 5 seconds to 2 minutes, depending on the mesh resolution
• All timings are obtained on a PC with Intel i7 2670QM 2.2GHz CPU and 8GB RAM

​

• In Figure 11, the kitten model is meshed from two different choices of harmonic functions, one with bifurcation and one without bifurcation.

​

• Compared to existing methods, the hex-meshes generated by our method typically have simpler structure, which is helpful in applications in graphics and engineering