Medial Elastics: Efficient and Collision-ready Deformation via Medial Axis Transform
Abstract: We propose a framework for the interactive simulation of nonlinear deformable objects. The primary feature of our system is the seamless integration of deformable simulation and collision culling, which are often independently handled in existing animation systems. The bridge connecting them is the medial axis transform or MAT, a high-fidelity volumetric approximation of complex 3D shapes. From the physics simulation perspective, MAT leads to an expressive and compact reduced nonlinear model. We employ a semi-reduced projective dynamics formulation, which well captures high-frequency local deformations of high-resolution models while retaining a low computation cost. Our key observation is that the most compelling (nonlinear) deformable effects are enabled by the local constraints projection, which should not be aggressively reduced, and only apply model reduction at the global stage. From the collision detection/culling perspective, MAT is geometrically versatile using linear-interpolated spheres (i.e. the so-called medial primitives) to approximate the boundary of the input model. The intersection test between two medial primitives is formulated as a quadratically constrained quadratic program problem. We give an algorithm to solve this problem exactly, which returns the deepest penetration between a pair of intersecting medial primitives. When coupled with spatial hashing, collision (including self-collision) can be efficiently identified on the GPU within few milliseconds even for massive simulations. We have tested our system on a variety of geometrically complex and high-resolution deformable objects, and our system produces convincing animations with all the collisions/self-collisions well handled at an interactive rate.
[Paper Download] Lei Lan, Ran Luo, Marco Fratarcangeli, Weiwei Xu, Huamin Wang, Xiaohu Guo, Junfeng Yao, Yin Yang. (2020) "Medial Elastics: Efficient and Collision-ready Deformation via Medial Axis Transform." ACM Transactions on Graphics 39(3): Article No.20. doi: 10.1145/3384515
Plane-Based Optimization of Geometry and Texture for RGB-D Reconstruction of Indoor Scenes
Abstract: We present a novel approach to reconstruct RGB-D indoor scene with plane primitives. Our approach takes as input a RGB-D sequence and a dense coarse mesh reconstructed by some 3D reconstruction method on the sequence, and generate a lightweight, low-polygonal mesh with clear face textures and sharp features without losing geometry details from the original scene. To achieve this, we firstly partition the input mesh with plane primitives, simplify it into a lightweight mesh next, then optimize plane parameters, camera poses and texture colors to maximize the photometric consistency across frames, and finally optimize mesh geometry to maximize consistency between geometry and planes. Compared to existing planar reconstruction methods which only cover large planar regions in the scene, our method builds the entire scene by adaptive planes without losing geometry details and preserves sharp features in the final mesh. We demonstrate the effectiveness of our approach by applying it onto several RGB-D scans and comparing it to other state-of-the-art reconstruction methods.
[Paper Download] Chao Wang, Xiaohu Guo. (2018) "Plane-Based Optimization of Geometry and Texture for RGB-D Reconstruction of Indoor Scenes." Proceedings of 2018 International Conference on 3D Vision (3DV 2018) pp. 533-541. doi: 10.1109/3DV.2018.00067
Superpixel Generation by Agglomerative Clustering with Quadratic Error Minimization
Abstract: Superpixel segmentation is a popular image preprocessing technique in many computer vision applications. In this paper we
present a novel superpixel generation algorithm by agglomerative clustering with quadratic error minimization. We use a
quadratic error metric (QEM) to measure the difference of spatial compactness and color homogeneity between superpixels.
Based on the quadratic function, we propose a bottom-up greedy clustering algorithm to obtain higher quality superpixel segmentation.
There are two steps in our algorithm: merging and swapping. First, we calculate the merging cost of two superpixels
and iteratively merge the pair with the minimum cost until the termination condition is satisfied. Then, we optimize the boundary
of superpixels by swapping pixels according to their swapping cost to improve the compactness. Due to the quadratic nature
of the energy function, each of these atomic operations has only O(1) time complexity. We compare the new method with other
state-of-the-art superpixel generation algorithms on two datasets, and our algorithm demonstrates superior performance.
[Paper Download] Xiao Dong, Zhonggui Chen, Junfeng Yao, Xiaohu Guo. (2019) "Superpixel Generation by Agglomerative Clustering with Quadratic Error Minimization." Computer Graphics Forum 38(1): 405-416. doi: 10.1111/cgf.13538
Surface Approximation via Asymptotic Optimal Geometric Partition
Abstract: In this paper, we present a novel method on surface partition from the perspective of approximation theory. Different from previous shape proxies, the ellipsoidal variance proxy is proposed to penalize the partition results falling into disconnected parts. On its support, the Principle Component Analysis (PCA) based energy is developed for asymptotic cluster aspect ratio and size control. We provide the theoretical explanation on how the minimization of the PCA-based energy leads to the optimal asymptotic behavior for approximation. Moreover, we show the partitions on densely sampled triangular meshes converge to the theoretic expectations. To evaluate the effectiveness of surface approximation, polygonal/triangular surface remeshing results are generated. The experimental results demonstrate the high approximation quality of our method.
[Paper Download] [Supplement] Yiqi Cai, Xiaohu Guo, Yang Liu, Wenping Wang, Weihua Mao, Zichun Zhong. (2017) "Surface Approximation via Asymptotic Optimal Geometric Partition." IEEE Transactions on Visualization and Computer Graphics 23(12): 2613-2626. doi: 10.1109/TVCG.2016.2623779
Anisotropic Superpixel Generation Based on Mahalanobis Distance
Abstract: Superpixels have been widely used as a preprocessing step in various computer vision tasks. Spatial compactness and color homogeneity are the two key factors determining the quality of the superpixel representation. In this paper, these two objectives are considered separately and anisotropic superpixels are generated to better adapt to local image content. We develop a unimodular Gaussian generative model to guide the color homogeneity within a superpixel by learning local pixel color variations. It turns out maximizing the log-likelihood of our generative model is equivalent to solving a Centroidal Voronoi Tessellation (CVT) problem. Moreover, we provide the theoretical guarantee that the CVT result is invariant to affine illumination change, which makes our anisotropic superpixel generation algorithm well suited for image/video analysis in varying illumination environment. The effectiveness of our method in image/video superpixel generation is demonstrated through the comparison with other state-of-the-art methods.
[Paper Download] [Supplement] Yiqi Cai, Xiaohu Guo. (2016) "Anisotropic Superpixel Generation Based on Mahalanobis Distance." Computer Graphics Forum 35(7): 199-207. doi: 10.1111/cgf.13017
Q-MAT: Computing Medial Axis Transform Using Quadratic Error Minimization
Abstract: The medial axis transform (MAT) is an important shape representation for shape approximation, shape recognition, and shape retrieval. Despite years of research, there is still a lack of effective methods for efficient, robust and accurate computation of the MAT. We present an efficient method, called Q-MAT, that uses quadratic error minimization to compute a structurally simple, geometrically accurate, and compact representation of the MAT. We introduce a new error metric for approximation and a new quantitative characterization of unstable branches of the MAT, and integrate them in an extension of the well-known quadric error metric (QEM) framework for mesh decimation. Q-MAT is fast, removes insignificant unstable branches effectively, and produces a simple and accurate piecewise linear approximation of the MAT. The method is thoroughly validated and compared with existing methods for MAT computation.
[Paper Download] Pan Li, Bin Wang, Feng Sun, Xiaohu Guo, Caiming Zhang, Wenping Wang. (2015) "Q-MAT: Computing Medial Axis Transform Using Quadratic Error Minimization." ACM Transactions on Graphics 35(1): Article No.8. doi: 10.1145/2753755
Abstract: This paper proposes an algorithm to build a set of orthogonal Point-Based Manifold Harmonic Bases (PB-MHB) for spectral analysis over point-sampled manifold surfaces. To ensure that PB-MHB are orthogonal to each other, it is necessary to have symmetrizable discrete Laplace-Beltrami Operator (LBO) over the surfaces. Existing converging discrete LBO for point clouds, as proposed by Belkin et al , is not guaranteed to be symmetrizable. We build a new point-wisely discrete LBO over the point-sampled surface that is guaranteed to be symmetrizable, and prove its convergence. By solving the eigen problem related to the new operator, we define a set of orthogonal bases over the point cloud. Experiments show that the new operator is converging better than other symmetrizable discrete Laplacian operators (such as graph Laplacian) defined on point-sampled surfaces, and can provide orthogonal bases for further spectral geometric analysis and processing tasks.
[Paper Download] Yang Liu, Balakrishnan Prabhakaran, and Xiaohu Guo. (2012) "Point-Based Manifold Harmonics." IEEE Transactions on Visualization and Computer Graphics 18(10): 1693-1703. doi: 10.1109/TVCG.2011.152
GPU-Assisted Computation of Centroidal Voronoi Tessellation
Abstract: Centroidal Voronoi tessellations (CVT) are widely used in computational science and engineering. The most commonly used method is Lloyd’s method, and recently the L-BFGS method is shown to be faster than Lloyd’s method for computing the CVT. However, these methods run on the CPU and are still too slow for many practical applications. We present techniques to implement these methods on the GPU for computing the CVT on 2D planes and on surfaces, and demonstrate significant speedup of these GPU-based methods over their CPU counterparts. For CVT computation on a surface, we use a geometry image stored in the GPU to represent the surface for computing the Voronoi diagram on it. In our implementation a new technique is proposed for parallel regional reduction on the GPU for evaluating integrals over Voronoi cells.
[Paper Download] Guodong Rong, Yang Liu, Wenping Wang, Xiaotian Yin, Xianfeng Gu, and Xiaohu Guo. (2010) "GPU-Assisted Computation of Centroidal Voronoi Tessellation." IEEE Transactions on Visualization and Computer Graphics 17(3): 345-356. doi: 10.1109/TVCG.2010.53