Computing geodesic distances on 3D surfaces is fundamental to many tasks in 3D vision and geometry processing, with deep connections to tasks such as shape correspondence. Recent learning-based methods achieve strong performance but rely on large 3D backbones, leading to high memory usage and latency, which limit their use in interactive or resource-constrained settings. We introduce LiteGE, a lightweight approach that constructs compact, category-aware shape descriptors by applying PCA to unsigned distance field (UDFs) samples at informative voxels. This descriptor is efficient to compute and removes the need for high-capacity networks. LiteGE remains robust on sparse point clouds, supporting inputs with as few as 300 points, where prior methods fail. Extensive experiments show that LiteGE reduces memory usage and inference time by up to 300x compared to existing neural approaches. In addition, by exploiting the intrinsic relationship between geodesic distance and shape correspondence, LiteGE enables fast and accurate shape matching. Our method achieves up to 1000x speedup over state-of-the-art mesh-based approaches while maintaining comparable accuracy on non-isometric shape pairs, including evaluations on point-cloud inputs.

Recovering precise surface geometry from corrupted point clouds remains a core challenge in 3D vision. Although existing denoising techniques achieve remarkable success, balancing noise removal with preserving intricate geometric details continues to pose difficulties. A critical limitation of current methods is that their adaptive feature aggregation mechanisms rely heavily on intermediate network features that have not been explicitly regularized, resulting in unstable guidance signals. This instability restricts the capability of the network to optimally differentiate true geometric details from noise. To overcome this limitation, we propose a novel deep learning framework that explicitly learns structured representations as robust priors to guide feature refinement. Our approach first derives a set of representative local structural primitives from input features by means of a learned codebook. This learned structured representation then serves as a robust conditional signal, directing a subsequent feature fusion mechanism to dynamically aggregate information in a structure-aware manner, thereby more effectively discerning noise and meticulously reconstructing geometric details. Extensive experiments on several benchmarks have demonstrated the superiority of our framework over existing advanced techniques in terms of detail preservation and noise suppression.

While 3D Gaussian Splatting (3DGS) excels at real-time rendering of standard scenes, it struggles to reconstruct underwater environments due to severe challenges such as light scattering, color attenuation, and sparse coverage of Gaussian kernels in far-field aqueous regions. To address this, we introduce AquaSplatting, a hybrid framework that combines explicit and implicit modeling methods for robust underwater scene reconstruction. Our dual-branch architecture employs 3DGS in a geometry-guided branch to model solid surfaces like the seabed, while a medium-aware branch uses a compact, view-dependent MLP to represent volumetric water effects. Furthermore, a neural underwater hybrid rendering mechanism adaptively fuses these two representations based on accumulated opacity. Thanks to this dual-branch framework, our method can also synthesize restored images without water medium. To enhance efficiency, our proposed engagement-based pruning (EBP) strategy quantifies each Gaussian's contribution by accumulating its image-space gradients over multiple frames, enabling the principled removal of primitives with negligible impact. The entire framework is optimized using a comprehensive loss function that integrates photometric, exposure, semantic, and depth priors to maximize visual fidelity. Experiments on challenging underwater datasets demonstrate that AquaSplatting achieves the state-of-the-art in reconstruction quality surpassing prior methods while maintaining real-time performance.

Reconstructing realistic 3D human avatars from monocular videos is a challenging task due to the limited geometric information and complex non-rigid motion involved. We present MonoCloth, a new method for reconstructing and animating clothed human avatars from monocular videos. To overcome the limitations of monocular input, we introduce a part-based decomposition strategy that separates the avatar into body, face, hands, and clothing. This design reflects the varying levels of reconstruction difficulty and deformation complexity across these components. Specifically, we focus on detailed geometry recovery for the face and hands. For clothing, we propose a dedicated cloth simulation module that captures garment deformation using temporal motion cues and geometric constraints. Experimental results demonstrate that MonoCloth improves both visual reconstruction quality and animation realism compared to existing methods. Furthermore, thanks to its part-based design, MonoCloth also supports additional tasks such as clothing transfer, underscoring its versatility and practical utility.

Point cloud data have been extensively studied due to their compact form and flexibility in representing complex 3D geometries and structures. The ability of point cloud data to accurately capture and represent intricate 3D geometry makes it an ideal choice for a wide range of applications, including 3D computer graphics, autonomous driving, robotics, and augmented reality, all of which require an understanding of the underlying geometry and spatial structures. Given the challenges associated with annotating large-scale point clouds, self-supervised point cloud representation learning has attracted increasing attention in recent years. It aims to learn generic and useful point cloud representations from unlabeled data, circumventing the need for extensive manual annotation. In this paper, we present a comprehensive survey of self-supervised point cloud representation learning using DNNs. We begin by presenting the motivation and general trends in recent research, then briefly introduce commonly used datasets and evaluation metrics. Next, we extensively explore self supervised point cloud representation learning methods. Finally, we share our thoughts on some of the challenges and potential issues that future research into self supervised learning for pre-training 3D point clouds may encounter. Our curated bibliography can be found at https://github.com/EtronTech/Awesome_3DSSL.

Abstract Existing image restoration methods primarily rely on the posterior distribution of natural images but are often limited by their dependence on known degradations and supervised training. To this end, we propose Generative Diffusion Prior (GDP), an unsupervised sampling-based framework that effectively models posterior distributions for image and video restoration. GDP utilizes a single pre-trained denoising diffusion probabilistic model (DDPM) to solve a wide range of linear, non-linear, and blind inverse problems without explicit degradation assumptions. Specifically, GDP systematically explores a conditional guidance protocol, which proves more practical and effective than conventional methods of adding guidance. Furthermore, GDP incorporates a degradation model optimization mechanism during the denoising process, enabling blind image restoration. Besides, we introduce a patch-based strategy, allowing GDP to handle images of arbitrary resolution. We extensively evaluate GDP on multiple image and video restoration tasks, including super-resolution, deblurring, inpainting, and colorization, as well as more challenging applications such as low-light enhancement, HDR recovery, and LDR video enhancement. Experimental results demonstrate that GDP outperforms leading unsupervised methods across diverse benchmarks in both reconstruction accuracy and perceptual quality, while demonstrating robust generalization to images and videos of any size. Our project page at https://generativediffusionprior.github.io/.

Surface parameterization is a fundamental geometry processing task, laying the foundations for the visual presentation of 3D assets and numerous downstream shape analysis scenarios. Conventional parameterization approaches demand high-quality mesh triangulation and are restricted to certain simple topologies unless additional surface cutting and decomposition are provided. In practice, the optimal configurations (e.g., type of parameterization domains, distribution of cutting seams, number of mapping charts) may vary drastically with different surface structures and task characteristics, thus requiring more flexible and controllable processing pipelines. To this end, this paper introduces FlexPara, an unsupervised neural optimization framework to achieve both global and multi-chart surface parameterizations by establishing point-wise mappings between 3D surface points and adaptively-deformed 2D UV coordinates. We ingeniously design and combine a series of geometrically-interpretable sub-networks, with specific functionalities of cutting, deforming, unwrapping, and wrapping, to construct a bi-directional cycle mapping framework for global parameterization without the need for manually specified cutting seams. Furthermore, we construct a multi-chart parameterization framework with adaptively-learned chart assignment. Extensive experiments demonstrate the universality, superiority, and inspiring potential of our neural surface parameterization paradigm.

Giving machines the ability to infer the complete 3D geometry and semantics of complex scenes is crucial for many downstream tasks, such as decision-making and planning. Vision-centric Semantic Scene Completion (SSC) has emerged as a trendy 3D perception paradigm due to its compatibility with task properties, low cost, and rich visual cues. Despite impressive results, current approaches inevitably suffer from problems such as depth errors or depth ambiguities during the 2D-to-3D transformation process. To overcome these limitations, in this paper, we first introduce an Optical Flow-Guided (OFG) DepthNet that leverages the strengths of pretrained depth estimation models, while incorporating optical flow images to improve depth prediction accuracy in regions with significant depth changes. Then, we propose a depth ambiguity-mitigated feature lifting strategy that implements deformable cross-attention in 3D pixel space to avoid depth ambiguities caused by the projection process from 3D to 2D and further enhances the effectiveness of feature updating through the utilization of prior mask indices. Moreover, we customize two subnetworks: a residual voxel network and a sparse UNet, to enhance the network's geometric prediction capabilities and ensure consistent semantic reasoning across varying scales. By doing so, our method achieves performance improvements over state-of-the-art methods on the SemanticKITTI, SSCBench-KITTI-360 and Occ3D-nuScene benchmarks.

Recent work in 3D deep learning has demonstrated that unsigned distance functions (UDFs) are a useful representation for 3D reconstruction and shape generation because they can represent surfaces with arbitrary topology. However, extracting meshes that preserve the intended topology, especially in the presence of non-manifold structures, remains challenging. We present DCx , an extension of the standard Dual Contouring (DC) method which was originally proposed for isosurface extraction from signed distance functions (SDFs). Standard DC operates on individual voxels and inserts one vertex per active cube, where activation is determined by detecting sign changes. To address the lack of sign information in UDFs, DCx adopts an optimization-based strategy for determining active cubes. It operates on each 2 × 2 × 2 voxel block, referred to as an expanded cube, and introduces a voxel-to-mesh lookup table that stores connectivity patterns based on local voxel configurations. This enables efficient triangle extraction using predefined templates. These changes improve upon DC by avoiding failure cases caused by unreliable active-cube detection in UDFs and by correcting mesh connections in non-manifold regions. As a result, DCx supports the extraction of both manifold and non-manifold surfaces from neural UDFs. DCx is conceptually simple and easy to implement. Experimental results show that DCx produces meshes with higher accuracy in a more robust way than existing methods, particularly on shapes with complex geometry or non-manifold structures. The source code is available at http://github.com/jjjkkyz/DCx.

The medial axis, a lower-dimensional descriptor that captures the extrinsic structure of a shape, plays an important role in digital geometry processing. Despite its importance, computing the medial axis transform robustly from diverse inputs, especially point clouds with defects, remains a challenging problem. In this article, we propose a new implicit method that deviates from traditional explicit medial axis computation. Our key technical insight is that the difference between the signed distance field (SDF) and the medial field (MF) of a solid shape relates to the unsigned distance field (UDF) of the shape’s medial axis. This observation allows us to formulate medial axis extraction as an implicit reconstruction problem. By employing a modified double covering strategy, we recover the medial axis as the zero level-set of the UDF. Extensive experiments demonstrate that our method achieves higher accuracy and robustness in learning compact medial axis transforms from challenging meshes and point clouds, outperforming existing approaches.

Multi-layer perceptrons (MLPs) are a standard tool for learning and function approximation, but they inherently produce globally smooth outputs. Consequently, they struggle to represent functions that are continuous yet intentionally non-differentiable (i.e., functions with prescribed C 0 sharp features) without ad hoc post-processing. We present SharpNet , a modified MLP architecture that encodes user-specified sharp features by augmenting the network with an auxiliary feature function defined as the solution to Poisson's equation with jump Neumann boundary conditions. This feature function is evaluated via an efficient local integral and is fully differentiable with respect to the feature locations, allowing us to jointly optimize both the feature locations and the MLP parameters to recover the target function or geometry. This construction provides precise control over where non-differentiability occurs, enforcing the desired C 0 behavior at feature locations while preserving smoothness elsewhere. We validate SharpNet on 2D problems and 3D CAD reconstruction, and compare it with several state-of-the-art baselines. In both settings, SharpNet accurately recovers sharp edges and corners while remaining smooth away from them, whereas existing methods tend to blur gradient discontinuities. Qualitative and quantitative results demonstrate the effectiveness of our approach. Our project page, code and models are publicly available at https://sharpnettech.github.io.

The Medial Axis Transform (MAT) is a complete shape descriptor capable of reconstructing the geometry of the original domain. A high-quality MAT should not only facilitate high-fidelity reconstruction but also capture structural features—for instance, by aligning the MAT boundary with the locus of rolling ball centers within fillet regions. However, computing such an ideal MAT remains a significant challenge, particularly when the input is a discrete triangle mesh. In this paper, we follow the established technical pipeline of initializing the MAT via a 3D Voronoi diagram of surface samples and subsequently simplifying the Voronoi structure through a QEM-like scheme. Our key insight is to explicitly track the correspondence between MAT vertices and surface regions throughout the progressive simplification process, ensuring that the resulting MAT triangles accurately reflect the intrinsic symmetries between surface patches. We translate these geometric requirements into a suite of priority control strategies that govern the sequencing of edge collapses. Through extensive evaluation against state-of-the-art MAT algorithms, we validate the strong performance of our approach regarding runtime efficiency, structural alignment, boundary regularity, triangle quality, and robustness to noise. Our resulting MATs remain highly expressive for both articulated shapes and CAD models, even under extreme simplification—effectively capturing the global structure of complex geometries with only a few hundred vertices. Finally, we showcase the utility of our approach through two potential applications: capturing the locus of rolling ball centers within fillet regions, a structural capability not previously demonstrated in the existing literature, and surface extraction from unsigned distance fields, where the medial axis of the є -isosurface naturally yields a clean single-layer result. Source code is available at https://github.com/sssomeone/structural-mat.

Point cloud denoising is a fundamental yet challenging task in computer graphics. Existing solutions typically rely on supervised training on synthesized noise. However, real-world noise often exhibits greater complexity, causing learning-based methods trained on synthetic noise to struggle when encountering unseen noise-a phenomenon we refer to as noise misalignment. To address this challenge, we propose LaPDA (Latent-space Point cloud Denoising with Adaptivity), a neural network explicitly designed to mitigate noise misalignment and enhance denoising robustness. LaPDA consists of two key stages. First, we adaptively model noise in the latent space, aligning unseen noise distributions with the known training distributions or adjusting them toward distributions with lower noise scales. Training objectives at this stage are formulated based on controlled synthetic noise with varying intensity levels. Second, we introduce a gradual noise removal module that optimizes the spatial distribution of the adaptively adjusted noisy points. Extensive experiments conducted on both synthetic and scanned datasets demonstrate that LaPDA achieves enhanced accuracy and robustness compared to state-of-the-art methods.

With the growing demand for real-world 3-D understanding, learning effective representations of 3-D data has become increasingly important for tasks such as shape classification, model retrieval, scene reconstruction, and point cloud completion. Although previous work has explored self-supervised learning within individual modalities (e.g., point clouds or images), the potential of multi-modal supervision remains largely underexplored due to the lack of aligned and scalable training signals. In this work, we present DR-Point, a tri-modal pre-training framework that jointly learns from RGB images, depth maps, and 3-D point clouds to build a unified embedding space across modalities. By enforcing cross-modal consistency among RGB-depth-point triplets, DR-Point achieves effective 2-D-3-D feature alignment without manual annotations. A differentiable rendering module further enhances geometric fidelity by synthesizing depth cues and refining structural details in reconstructed point clouds. Extensive experiments on benchmarks demonstrate that DR-Point consistently outperforms state-of-the-art self-supervised methods on 3-D classification, segmentation, and completion. These results highlight the advantages of multi-modal pre-training for unified 3-D understanding and its potential to benefit a wide range of vision and graphics applications.

Diffusion-based generative models have achieved remarkable success in image restoration by learning to iteratively refine noisy data toward clean signals. Inspired by this progress, recent efforts have begun exploring their potential in 3D domains. However, applying diffusion models to point cloud denoising introduces several challenges. Unlike images, clean and noisy point clouds are characterized by structured displacements. As a result, it is unsuitable to establish a transform mapping in the forward phase by diffusing Gaussian noise, as this approach disregards the inherent geometric relationship between the point sets. Furthermore, the stochastic nature of Gaussian noise introduces additional complexity, complicating geometric reasoning and hindering surface recovery during the reverse denoising process. In this paper, we introduce a deterministic noise-free diffusion framework that formulates point cloud denoising as a two-phase residual diffusion process. In the forward phase, directional residuals are injected into clean surfaces to construct a degradation trajectory that encodes both local displacements and their global evolution. In the reverse phase, a U-Net-based network iteratively estimates and removes these residuals, effectively retracing the degradation path backward to recover the underlying surface. By decomposing the denoising task into directional residual computation and sequential refinement, our method enables faithful surface recovery while mitigating common artifacts such as over-smoothing and under-smoothing. Extensive experiments on synthetic and real-world datasets demonstrate that our method achieves state-of-the-art performance in both quantitative metrics and visual quality.

While 3D head reconstruction is widely used for modeling, existing neural reconstruction approaches rely on high-resolution multi-view images, posing notable privacy issues. Individuals are particularly sensitive to facial features, and facial image leakage can lead to many malicious activities, such as unauthorized tracking and deepfake. In contrast, geometric data is less susceptible to misuse due to its complex processing requirements, and absence of facial texture features. In this paper, we propose a novel two-stage 3D facial reconstruction method aimed at avoiding exposure to sensitive facial information while preserving detailed geometric accuracy. Our approach first uses non-sensitive rear-head images for initial geometry and then refines this geometry using processed privacy-removed gradient images. Extensive experiments show that the resulting geometry is comparable to methods using full images, while the process is resistant to DeepFake applications and facial recognition (FR) systems, thereby proving its effectiveness in privacy protection.

Point clouds have become the preferred data format for a variety of tasks in 3D vision and graphics. However, raw point clouds often contain significant noise. This paper introduces the Adaptive Stop Denoising Network (ASDN), a novel approach aimed at restoring high-quality point clouds from noisy data. Our method is built upon a pivotal observation: during the denoising phase, high-noise points draw more focus from the network, which may suppress the points that have already been effectively denoised. This observation has led us to develop an adaptive strategy that ceases denoising already cleaned points to prevent over-denoising, while continuing to refine points that remain noisy. We employ a U-Net architecture complemented by an adaptive classifier, which utilizes a recoverability factor to assess the completion of denoising and make dynamic decisions about when to halt the process. Our method not only demonstrates superior noise removal efficiency but also preserves geometric details more effectively, reducing over- or under-denoising artifacts. Extensive experiments and evaluations demonstrate that our method outperforms the state-of-the-art both qualitatively and quantitatively.

In this paper we study the task of a single-view image-guided point cloud completion. Existing methods have got promising results by fusing the information of image into point cloud explicitly or implicitly. However, given that the image has global shape information and the partial point cloud has rich local details, We believe that both modalities need to be given equal attention when performing modality fusion. To this end, we propose a novel dual-channel modality fusion network for image-guided point cloud completion(named DMF-Net), in a coarse-to-fine manner. In the first stage, DMF-Net takes a partial point cloud and corresponding image as input to recover a coarse point cloud. In the second stage, the coarse point cloud will be upsampled twice with shape-aware upsampling transformer to get the dense and complete point cloud. Extensive quantitative and qualitative experimental results show that DMF-Net outperforms the state-of-the-art unimodal and multimodal point cloud completion works on ShapeNet-ViPC dataset.

While Signed Distance Fields (SDF) are well-established for modeling watertight surfaces, Unsigned Distance Fields (UDF) broaden the scope to include open surfaces and models with complex inner structures. Despite their flexibility, UDFs encounter significant challenges in high-fidelity 3D reconstruction, such as non-differentiability at the zero level set, difficulty in achieving the exact zero value, numerous local minima, vanishing gradients, and oscillating gradient directions near the zero level set. To address these challenges, we propose Details Enhanced UDF (DEUDF) learning that integrates normal alignment and the SIREN network for capturing fine geometric details, adaptively weighted Eikonal constraints to address vanishing gradients near the target surface, unconditioned MLP-based UDF representation to relax non-negativity constraints, and DCUDF for extracting the local minimal average distance surface. These strategies collectively stabilize the learning process from unoriented point clouds and enhance the accuracy of UDFs. Our computational results demonstrate that DEUDF outperforms existing UDF learning methods in both accuracy and the quality of reconstructed surfaces.

Noise is an inevitable aspect of point cloud acquisition, necessitating filtering as a fundamental task within the realm of 3D vision. Existing learning-based filtering methods have shown promising capabilities on commonly used datasets. Nonetheless, the effectiveness of these methods is constrained when dealing with a substantial quantity of point clouds. This limitation primarily stems from their limited denoising capabilities for dense and large-scale point clouds and their inclination to generate noisy outliers after denoising. To deal with this challenge, we introduce 3DMambaIPF, for the first time, exploiting Selective State Space Models (SSMs) architecture to handle highly-dense and large-scale point clouds, capitalizing on its strengths in selective input processing and large context modeling capabilities. Additionally, we present a robust and fast differentiable rendering loss to constrain the noisy points around the surface. In contrast to previous methodologies, this differentiable rendering loss enhances the visual realism of denoised geometric structures and aligns point cloud boundaries more closely with those observed in real-world objects. Extensive evaluations on commonly used datasets (typically with up to 50K points) demonstrate that 3DMambaIPF achieves state-of-the-art results. Moreover, we showcase the superior scalability and efficiency of 3DMambaIPF on highly dense and large-scale point clouds with up to 500K points compared to off-the-shelf methods.

Unsigned distance fields (UDFs) provide a versatile framework for representing a diverse array of 3D shapes, encompassing both watertight and non-watertight geometries. Traditional UDF learning methods typically require extensive training on large 3D shape datasets, which is costly and necessitates re-training for new datasets. This paper presents a novel neural framework, LoSF-UDF, for reconstructing surfaces from 3D point clouds by leveraging local shape functions to learn UDFs. We observe that 3D shapes manifest simple patterns in localized regions, prompting us to develop a training dataset of point cloud patches characterized by mathematical functions that represent a continuum from smooth surfaces to sharp edges and corners. Our approach learns features within a specific radius around each query point and utilizes an attention mechanism to focus on the crucial features for UDF estimation. Despite being highly lightweight, with only 653 KB of trainable parameters and a modest-sized training dataset with 0.5 GB storage, our method enables efficient and robust surface reconstruction from point clouds without requiring for shape-specific training. Furthermore, our method exhibits enhanced resilience to noise and outliers in point clouds compared to existing methods. We conduct comprehensive experiments and comparisons across various datasets, including synthetic and real-scanned point clouds, to validate our method’s efficacy. Notably, our lightweight framework offers rapid and reliable initialization for other unsupervised iterative approaches, improving both the efficiency and accuracy of their reconstructions. Our project and code are available at https://jbhu67.github.io/LoSF-UDF.github.io/.

In this study, we introduce a novel two-stage technique for decomposing and reconstructing facial features from sparse-view images, a task made challenging by the unique geometry and complex skin reflectance of each individual. To synthesize 3D facial models more realistically, we endeavor to decouple key facial attributes from the RGB color, including geometry, diffuse reflectance, and specular reflectance. Specifically, we design a Sparse-view Face Decomposition Model (SFDM): 1) In the first stage, we create a general facial template from a wide array of individual faces, encapsulating essential geometric and reflectance characteristics. 2) Guided by this template, we refine a specific facial model for each individual in the second stage, considering the interaction between geometry and reflectance, as well as the effects of subsurface scattering on the skin. With these advances, our method can reconstruct high-quality facial representations from as few as three images. The comprehensive evaluation and comparison reveal that our approach outperforms existing methods by effectively disentangling geometric and reflectance components, significantly enhancing the quality of synthesized novel views, and paving the way for applications in facial relighting and reflectance editing. Visit our project page for more details https://kingjg.github.io/SFDM.github.io/.

Novel view synthesis (NVS) and surface reconstruction (SR) are essential tasks in 3D Gaussian Splatting (3D-GS). Despite recent progress, these tasks are often addressed independently, with GS-based rendering methods struggling under diverse light conditions and failing to produce accurate surfaces, while GS-based reconstruction methods frequently compromise rendering quality. This raises a central question: must rendering and reconstruction always involve a trade-off? To address this, we propose MGSR, a 2D/3D Mutual-boosted Gaussian splatting for Surface Reconstruction that enhances both rendering quality and 3D reconstruction accuracy. MGSR introduces two branches--one based on 2D-GS and the other on 3D-GS. The 2D-GS branch excels in surface reconstruction, providing precise geometry information to the 3D-GS branch. Leveraging this geometry, the 3D-GS branch employs a geometry-guided illumination decomposition module that captures reflected and transmitted components, enabling realistic rendering under varied light conditions. Using the transmitted component as supervision, the 2D-GS branch also achieves high-fidelity surface reconstruction. Throughout the optimization process, the 2D-GS and 3D-GS branches undergo alternating optimization, providing mutual supervision. Prior to this, each branch completes an independent warm-up phase, with an early stopping strategy implemented to reduce computational costs. We evaluate MGSR on a diverse set of synthetic and real-world datasets, at both object and scene levels, demonstrating strong performance in rendering and surface reconstruction. Code is available at https://github.com/TsingyuanChou/MGSR.

We introduce MIRReS, a novel two-stage inverse rendering framework that jointly reconstructs and optimizes explicit geometry, materials, and lighting from multi-view images. Unlike previous methods that rely on implicit irradiance fields or oversimplified ray tracing, our method begins with an initial stage that extracts an explicit triangular mesh. In the second stage, we refine this representation using a physically-based inverse rendering model with multi-bounce path tracing and Monte Carlo integration. This enables our method to accurately estimate indirect illumination effects, including self-shadowing and internal reflections, leading to a more precise intrinsic decomposition of shape, material, and lighting. To address the noise issue in Monte Carlo integration, we incorporate reservoir sampling, improving convergence and enabling efficient gradient-based optimization with low sample counts. Through both qualitative and quantitative assessments across various scenarios, especially those with complex shadows, we demonstrate that our method achieves state-of-the-art decomposition performance. Furthermore, our optimized explicit geometry seamlessly integrates with modern graphics engines supporting downstream applications such as scene editing, relighting, and material editing.

Unsigned distance fields (UDFs) are widely used in 3D deep learning due to their ability to represent shapes with arbitrary topology. While prior work has largely focused on learning UDFs from point clouds or multi-view images, extracting meshes from UDFs remains challenging, as the learned fields rarely attain exact zero distances. A common workaround is to reconstruct signed distance fields (SDFs) locally from UDFs to enable surface extraction via Marching Cubes. However, this often introduces topological artifacts such as holes or spurious components. Moreover, local SDFs are inherently incapable of representing non-manifold geometry, leading to complete failure in such cases. To address this gap, we propose MIND ($\mathrm{\underline{M}aterial}$ $\mathrm{\underline{I}nterface}$ $\mathrm{from}$ $\mathrm{\underline{N}on}$-$\mathrm{manifold}$ $\mathrm{\underline{D}istance}$ $\mathrm{fields}$), a novel algorithm for generating material interfaces directly from UDFs, enabling non-manifold mesh extraction from a global perspective. The core of our method lies in deriving a meaningful spatial partitioning from the UDF, where the target surface emerges as the interface between distinct regions. We begin by computing a two-signed local field to distinguish the two sides of manifold patches, and then extend this to a multi-labeled global field capable of separating all sides of a non-manifold structure. By combining this multi-labeled field with the input UDF, we construct material interfaces that support non-manifold mesh extraction via a multi-labeled Marching Cubes algorithm. Extensive experiments on UDFs generated from diverse data sources, including point cloud reconstruction, multi-view reconstruction, and medial axis transforms, demonstrate that our approach robustly handles complex non-manifold surfaces and significantly outperforms existing methods. The source code is available at https://github.com/jjjkkyz/MIND.

This paper tackles the challenges of physics-based simulation of rigid bodies in neural rendering, with a focus on 3D model representation and collision handling. We propose Physics and Geometry-Augmented Neural Implicit Surfaces (PGA-NeuS), a novel approach that combines neural implicit surfaces with a differentiable physics solver. In the pre-processing stage, PGA-NeuS reconstructs static scene and object geometry from multi-view images using signed distance fields (SDFs). For dynamic scenes captured in monocular videos, these SDFs, along with the initial position and orientation of moving rigid bodies, are fed into a differentiable rigid body solver to optimize physical parameters, such as initial velocity and friction coefficients. Subsequently, PGA-NeuS leverages color loss, physics loss, and object mask supervision to iteratively refine the neural implicit surface, ensuring the target object's alignment with the predicted motion sequence. We evaluate PGA-NeuS on five real-world scenes, demonstrating its ability to accurately reconstruct realistic motion sequences and estimate physical parameters such as position and velocity. Dataset and source code are available at https://github.com/Raining00/PGA-NeuS . • PGA-NeuS reconstructs moving rigid objects from monocular videos using physics-aware neural surfaces. • Joint optimization of color, physics, and mask losses enables dynamic scene reconstruction from monocular videos. • We introduce a dataset with synthetic and real scenes featuring sliding, rolling, and collision motions.

Abstract Topological properties play a crucial role in the analysis, reconstruction, and generation of 3D shapes. Yet, most existing research focuses primarily on geometric features, due to the lack of effective representations for topology. In this paper, we introduce TopoGen , a method that extracts both discrete and continuous topological descriptors–Betti numbers and persistence points–using persistent homology. These features provide robust characterizations of 3D shapes in terms of their topology. We incorporate them as conditional guidance in generative models for 3D shape synthesis, enabling topology‐aware generation from diverse inputs such as sparse and partial point clouds, as well as sketches. Furthermore, by modifying persistence points, we can explicitly control and alter the topology of generated shapes. Experimental results demonstrate that TopoGen enhances both diversity and controllability in 3D generation by embedding global topological structure into the synthesis process.

We propose PortraitACG, a novel framework for user-guided portrait image editing that leverages an asymmetric conditional generative adversarial network (GAN), which supports the fine-grained editing of geometries, colors, lights, and shadows using a single neural network model. Existing conditional GAN-based approaches usually feed the same conditional information into generators and discriminators, which is sub-optimal because these two modules are designed for different purposes. To facilitate flexible user-guided editing, we propose a novel asymmetric conditional GAN, where the generators take the transformed conditional inputs, such as edge maps, color palettes, sliders, and masks, that can be directly edited by the user, and the discriminators take the conditional inputs in a way that can guide controllable image generation more effectively. This allows image editing operations to be performed in a simpler and more intuitive manner. For example, the user can directly use a color palette to specify the desired colors of hair, skin, eyes, lips, and background and use a slider to blend colors. Moreover, users can edit the lights and shadows by modifying their corresponding masks.

Predicting per-voxel occupancy status and corresponding semantic labels in 3D scenes is pivotal to 3D intelligent perception in autonomous driving. In this paper, we propose a novel semantic scene completion framework that can generate complete 3D volumetric semantics from a single image at a low cost. To the best of our knowledge, this is the first endeavor specifically aimed at mitigating the negative impacts of incorrect voxel query proposals caused by erroneous depth estimates and enhancing interactions for positive ones in camera-based semantic scene completion tasks. Specifically, we present a straightforward yet effective Semantic-aware Guided (SAG) module, which seamlessly integrates with task-related semantic priors to facilitate effective interactions between image features and voxel query proposals in a plug-and-play manner. Furthermore, we introduce a set of learnable object queries to better perceive objects within the scene. Building on this, we propose an Interactive Refinement Transformer (IRT) block, which iteratively updates voxel query proposals to enhance the perception of semantics and objects within the scene by leveraging the interaction between object queries and voxel queries through query-to-query cross-attention. Extensive experiments demonstrate that our method outperforms existing state-of-the-art approaches, achieving overall improvements of 0.30 and 2.74 in mIoU metric on the SemanticKITTI and SSCBench-KITTI-360 validation datasets, respectively, while also showing superior performance in the aspect of small object generation.

Learning universal representations of 3-D point clouds is essential for reducing the need for manual annotation of large-scale and irregular point cloud datasets. The current modus operandi for representative learning is self-supervised learning, which has shown great potential for improving point cloud understanding. Nevertheless, it remains an open problem how to employ auto-encoding for learning universal 3-D representations of irregularly structured point clouds, as previous methods focus on either global shapes or local geometries. To this end, we present a cascaded self-supervised point cloud representation learning framework, dubbed Curriculumformer, aiming to tame curriculum pre-training for enhanced point cloud understanding. Our main idea lies in devising a progressive pre-training strategy, which trains the Transformer in an easy-to-hard manner. Specifically, we first pre-train the Transformer using an upsampling strategy, which allows it to learn global information. Then, we follow up with a completion strategy, which enables the Transformer to gain insight into local geometries. Finally, we propose a Multi-Modal Multi-Modality Contrastive Learning (M4CL) strategy to enhance the ability of representation learning by enriching the Transformer with semantic information. In this way, the pre-trained Transformer can be easily transferred to a wide range of downstream applications. We demonstrate the superior performance of Curriculumformer on various discriminant and generative tasks, outperforming state-of-the-art methods. Moreover, Curriculumformer can also be integrated into other off-the-shelf methods to promote their performance. Our code is available at https://github.com/Fayeben/Curriculumformer.

Orienting point clouds is a fundamental problem in computer graphics and 3D vision, with applications in reconstruction, segmentation, and analysis. While significant progress has been made, existing approaches mainly focus on watertight, object-level 3D models. The orientation of large-scale, non-watertight 3D scenes remains an underexplored challenge. To address this gap, we propose DACPO (Divide-And-Conquer Point Orientation), a novel framework that leverages a divide-and-conquer strategy for scalable and robust point cloud orientation. Rather than attempting to orient an unbounded scene at once, DACPO segments the input point cloud into smaller, manageable blocks, processes each block independently, and integrates the results through a global optimization stage. For each block, we introduce a two-step process: estimating initial normal orientations by a randomized greedy method and refining them by an adapted iterative Poisson surface reconstruction. To achieve consistency across blocks, we model inter-block relationships using an an undirected graph, where nodes represent blocks and edges connect spatially adjacent blocks. To reliably evaluate orientation consistency between adjacent blocks, we introduce the concept of the visible connected region , which defines the region over which visibility-based assessments are performed. The global integration is then formulated as a 0-1 integer-constrained optimization problem, with block flip states as binary variables. Despite the combinatorial nature of the problem, DACPO remains scalable by limiting the number of blocks (typically a few hundred for 3D scenes) involved in the optimization. Experiments on benchmark datasets demonstrate DACPO's strong performance, particularly in challenging large-scale, non-watertight scenarios where existing methods often fail. The source code is available at https://github.com/zd-lee/DACPO.

This article presents Diffusing Winding Gradients (DWG) for reconstructing watertight surfaces from unoriented point clouds. Our method exploits the alignment between the gradients of the screened generalized winding number (GWN) field—a robust variant of the standard GWN field—and globally consistent normals to orient points. Starting with an unoriented point cloud, DWG initially assigns a random normal to each point. It computes the corresponding screened GWN field and extracts a level set whose iso-value is the average of GWN values across all input points. The gradients of this level set are then utilized to update the point normals. This cycle of recomputing the screened GWN field and updating point normals is repeated until the screened GWN level sets stabilize and their gradients cease to change. Unlike conventional methods, DWG does not rely on solving linear systems or optimizing objective functions, which simplifies its implementation and enhances its suitability for efficient parallel execution. Experimental results demonstrate that DWG significantly outperforms existing methods in terms of runtime performance. For large-scale models with 10 to 20 million points, our CUDA implementation on an NVIDIA GTX 4090 GPU achieves speeds 30 to 120 times faster than iPSR, the leading sequential method, tested on a high-end PC with an Intel i9 CPU. Furthermore, by employing a screened variant of GWN, DWG demonstrates enhanced robustness against noise and outliers and proves effective for models with thin structures and real-world inputs with overlapping and misaligned scans. For source code and additional results, visit our project webpage: https://dwgtech.github.io/ .

Unsigned distance fields (UDFs) provide a flexible representation for models with complex topologies, but accurately extracting their zero level sets remains challenging, particularly in preserving topological correctness and fine geometric details. We present DCUDF2, an enhanced method that builds upon DCUDF to address these limitations. Our approach introduces an accuracy-aware loss function with self-adaptive weights, enabling precise geometric fitting while avoiding over-smoothing. To improve robustness, we propose a topology correction strategy that reduces the sensitivity to hyper-parameter settings. Furthermore, we develop new operations leveraging self-adaptive weights to accelerate convergence and improve runtime efficiency. Extensive experiments on diverse datasets demonstrate that DCUDF2 consistently outperforms DCUDF and existing methods in both geometric fidelity and topological accuracy.

3D Gaussian Splatting (3D-GS) has emerged as a significant advancement in the field of computer graphics and 3D vision, offering explicit scene representation and novel view synthesis without the reliance on neural networks. This technique has found diverse applications in areas such as robotics, urban mapping, autonomous navigation, and virtual reality/augmented reality, just name a few. Given the growing popularity and expanding research in 3D-GS, this paper presents a comprehensive survey of relevant papers from the past year. We organize the survey into taxonomies based on characteristics and applications, providing an introduction to the theoretical underpinnings of 3D-GS. The survey aims to introduce the theoretical foundations of 3D Gaussian Splatting and provide a reference for new researchers while inspiring future research directions.

Extracting wireframes from CAD models represented by point cloud remains a significant challenge in computer graphics. This difficulty arises from two main factors: first, imperfections in the point cloud data, such as lack of orientation, noise, and sparsity; and second, the inherent complexity of geometric shapes, which often feature a high density of sharp edges in close proximity. In this paper, we propose D-FRAME, a multi-stage wireframe extraction framework that incorporates a novel direction field to improve edge detection quality and connectivity, a refinement strategy to address sparse or noisy edge points, and a final coarse-to-fine connection module to extract a robust wireframe. The direction field not only facilitates connectivity but also enhances the precision of extracted edges by mitigating the impact of misclassified points. By combining the Restricted Voronoi Diagram (RVD) with the extracted wireframes and the original point cloud, our approach also achieves highly faithful reconstruction of CAD model. Experiments conducted on synthetic and real-world scanned CAD datasets demonstrate that D-FRAME effectively manages noise, sparsity, and complex geometries, yielding high-fidelity wireframes.

We propose a new method for computing smooth and integrable cross fields on 2D and 3D surfaces. our approach first computes smooth cross fields by minimizing the Dirichlet energy. Unlike existing optimization-based methods, our technique determines the singularity configuration-i.e., the number, locations, and indices of singularities-by iteratively adjusting them. Singularities can move, merge and split, akin to the behavior of like charges repelling and unlike charges attracting. Once all singularities stop moving, we obtain a cross field with (locally) the lowest Dirichlet energy. In simply connected domains, this cross field is guaranteed to be integrable. However, this property does not hold in multiply connected domains. To make a smooth cross field integrable, we construct a vector field $\bf c$c that characterizes the deviation of the cross field from a curl-free field. We then optimize the locations of singularities by moving them along the field lines of $\bf c$c. Our method is fundamentally different from existing integer programming-based approaches, as it avoids combinatorial optimization. It is fully automatic and includes a parameter to control the number of singularities. Our method is well suited for smooth models where exact boundary alignment and sparse hard directional constraints are desired, and can guide seamless conformal parameterization and T-junction-free quadrangulation.

We study a problem of modeling wireframe meshes where the vertices and edges fall into a set of discrete equivalence classes, respectively. This problem is motivated by the need of fabricating large wireframe structures at lower cost and faster speed since both nodes (thickened vertices) and rods (thickened edges) can be mass-produced. Given a 3D shape represented as a wireframe mesh, our goal is to compute a set of template vertices and a set of template edges, whose instances can be used to produce a fabricable wireframe mesh that approximates the input shape. To achieve this goal, we propose a computational approach that generates the template vertices and template edges by iteratively clustering and optimizing the mesh vertices and edges. At the clustering stage, we cluster mesh vertices and edges according to their shape and length, respectively. At the optimization stage, we first locally optimize the mesh to reduce the number of clusters of vertices and/or edges, and then globally optimize the mesh to reduce the intra-cluster variance for vertices and edges, while facilitating fabricability of the wireframe mesh. We demonstrate that our approach is able to model wireframe meshes with various shapes and topologies, compare it with three state-of-the-art approaches to show its superiority, and validate fabricability of our results by making three physical prototypes.

The task of reconstructing indoor floorplans has become an increasingly popular subject, offering substantial benefits across various applications such as interior design, virtual reality, and robotics. Despite the growing interest, existing approaches frequently encounter challenges due to high computational costs and sensitivity to errors in primitive detection. In this article, we introduce PolyGraph, a new computational framework that combines a deep-learning based primitive detection network with an optimization-based reconstruction algorithm to facilitate high-quality reconstruction results. Specifically, we develop a novel guided wall point primitive estimation network capable of generating dense samples along wall boundaries. This network not only retains structural detail but also shows improved robustness in the detection phase. Then, PolyGraph utilizes wall points to establish a graph-based representation, formulating indoor floorplan reconstruction as a subgraph optimization problem. This approach significantly reduces the search space comparing to existing pixel-level optimization approaches. By utilizing "structural weight", we seamlessly integrate the structural information of walls and rooms into graph representations, ensuring high-quality reconstruction results. Experimental results demonstrate PolyGraph's effectiveness and its advantages compared to other optimization-based approaches, showcasing its computational efficiency, and its ability to preserve structural integrity and capture fine details, as quantified by the structure metrics.

Since point clouds acquired by scanners inevitably contain noise, recovering a clean version from a noisy point cloud is essential for further 3D geometry processing applications. Several data-driven approaches have been recently introduced to overcome the drawbacks of traditional filtering algorithms, such as less robust preservation of sharp features and tedious tuning for multiple parameters. Most of these methods achieve filtering by directly regressing the position/displacement of each point, which may blur detailed features and is prone to uneven distribution. In this article, we propose a novel data-driven method that explores the implicit fields. Our assumption is that the given noisy points implicitly define a surface, and we attempt to obtain a point's movement direction and distance separately based on the predicted signed distance fields (SDFs). Taking a noisy point cloud as input, we first obtain a consistent alignment by incorporating the global points into local patches. We then feed them into an encoder-decoder structure and predict a 7D vector consisting of SDFs. Subsequently, the distance can be obtained directly from the first element in the vector, and the movement direction can be obtained by computing the gradient descent from the last six elements (i.e., six surrounding SDFs). We finally obtain the filtered results by moving each point with its predicted distance along its movement direction. Our method can produce feature-preserving results without requiring explicit normals. Experiments demonstrate that our method visually outperforms state-of-the-art methods and generally produces better quantitative results than position-based methods (both learning and non-learning).

The article presents a new method for constructing self-supporting surfaces using arch beams that are designed to convert their thrust into supporting force, thereby eliminating shear stress and bending moments. Our method allows for the placement of the arch beams on the boundary or within a surface and partitions the surface into multiple self-supporting parts. The use of arch beams enhances stability and durability, adds aesthetic appeal, and allows for greater flexibility in the design process. We develop an iterative algorithm for designing self-supporting surfaces with arch beams that enables the user to control the shape of the beams and surface through intuitive parameters and specify the desired location of the arch beams. We verify the physical stability of the structure using finite element analysis. Experimental results show that our method can produce visually pleasing self-supporting surfaces that satisfy the equilibrium equation with high accuracy.

This paper presents a new algorithm, Weighted Squared Volume Minimization (WSVM), for generating high-quality tetrahedral meshes from closed triangle meshes. Drawing inspiration from the principle of minimal surfaces that minimize squared surface area, WSVM employs a new energy function integrating weighted squared volumes for tetrahedral elements. When minimized with constant weights, this energy promotes uniform volumes among the tetrahedra. Adjusting the weights to account for local geometry further achieves uniform dihedral angles within the mesh. The algorithm begins with an initial tetrahedral mesh generated via Delaunay tetrahedralization and proceeds by sequentially minimizing volume-oriented and then dihedral angle-oriented energies. At each stage, it alternates between optimizing vertex positions and refining mesh connectivity through the iterative process. The algorithm operates fully automatically and requires no parameter tuning. Evaluations on a variety of 3D models demonstrate that WSVM consistently produces tetrahedral meshes of higher quality, with fewer slivers and enhanced uniformity compared to existing methods.

Occlusion is a common issue in 3D reconstruction from RGB-D videos, often blocking the complete reconstruction of objects and presenting an ongoing problem. In this paper, we propose a novel framework, empowered by a 2D diffusion-based in-painting model, to reconstruct complete surfaces for the hidden parts of objects. Specifically, we utilize a pre-trained diffusion model to fill in the hidden areas of 2D images. Then we use these in-painted images to optimize a neural implicit surface representation for each instance for 3D reconstruction. Since creating the in-painting masks needed for this process is tricky, we adopt a human-in-the-loop strategy that involves very little human engagement to generate high-quality masks. Moreover, some parts of objects can be totally hidden because the videos are usually shot from limited perspectives. To ensure recovering these invisible areas, we develop a cascaded network architecture for predicting signed distance field, making use of different frequency bands of positional encoding and maintaining overall smoothness. Besides the commonly used rendering loss, Eikonal loss, and silhouette loss, we adopt a CLIP-based semantic consistency loss to guide the surface from unseen camera angles. Experiments on ScanNet scenes show that our proposed framework achieves state-of-the-art accuracy and completeness in object-level reconstruction from scene-level RGB-D videos. Code: https://github.com/THU-LYJ-Lab/O2-Recon.

Recently, building on the foundation of neural radiance field, various techniques have emerged to learn unsigned distance fields (UDF) to reconstruct 3D non-watertight models from multi-view images. Yet, a central challenge in UDF-based volume rendering is formulating a proper way to convert unsigned distance values into volume density, ensuring that the resulting weight function remains unbiased and sensitive to occlusions. Falling short on these requirements often results in incorrect topology or large reconstruction errors in resulting models. This paper addresses this challenge by presenting a novel two-stage algorithm, 2S-UDF, for learning a high-quality UDF from multi-view images. Initially, the method applies an easily trainable density function that, while slightly biased and transparent, aids in coarse reconstruction. The subsequent stage then refines the geometry and appearance of the object to achieve a high-quality reconstruction by directly adjusting the weight function used in volume rendering to ensure that it is unbiased and occlusion-aware. Decoupling density and weight in two stages makes our training stable and robust, distinguishing our technique from existing UDF learning approaches. Evaluations on the DeepFashion3D, DTU, and BlendedMVS datasets validate the robustness and effectiveness of our proposed approach. In both quantitative metrics and visual quality, the results indicate our superior performance over other UDF learning techniques in reconstructing 3D non-watertight models from multi-view images. Our code is available at https://bitbucket.org/jkdeng/2sudf/.

Point clouds frequently contain noise and outliers, presenting obstacles for downstream applications. In this work, we introduce a novel denoising method for point clouds. By leveraging the latent space, we explicitly un-cover noise components, allowing for the extraction of a clean latent code. This, in turn, facilitates the restoration of clean points via inverse transformation. A key component in our network is a new multi-level graph convolution network for capturing rich geometric structural features at various scales from local to global. These features are then integrated into the invertible neural network which bijectively maps the latent space, to guide the noise disentanglement process. Additionally, we employ an invertible mono-tone operator to model the transformation process, effectively enhancing the representation of integrated geometric features. This enhancement allows our network to pre-cisely differentiate between noise factors and the intrinsic clean points in the latent code by projecting them onto separate channels. Both qualitative and quantitative evaluations demonstrate that our method outperforms state-of-the-art methods at various noise levels. The source code is available at https://github.com/yanbiaol/PD-LTS.

Traditional 3D shape reconstruction techniques from multi-view images, such as structure from motion and multi-view stereo, face challenges in reconstructing transparent objects. Recent advances in neural radiance fields and its variants primarily address opaque or transparent objects, encountering difficulties to reconstruct both transparent and opaque objects simultaneously. This paper introduces $\alpha$-NeuS$\textemdash$an extension of NeuS$\textemdash$that proves NeuS is unbiased for materials from fully transparent to fully opaque. We find that transparent and opaque surfaces align with the non-negative local minima and the zero iso-surface, respectively, in the learned distance field of NeuS. Traditional iso-surfacing extraction algorithms, such as marching cubes, which rely on fixed iso-values, are ill-suited for such data. We develop a method to extract the transparent and opaque surface simultaneously based on DCUDF. To validate our approach, we construct a benchmark that includes both real-world and synthetic scenes, demonstrating its practical utility and effectiveness. Our data and code are publicly available at https://github.com/728388808/alpha-NeuS.

Surface parameterization plays an essential role in numerous computer graphics and geometry processing applications. Traditional parameterization approaches are designed for high-quality meshes laboriously created by specialized 3D modelers, thus unable to meet the processing demand for the current explosion of ordinary 3D data. Moreover, their working mechanisms are typically restricted to certain simple topologies, thus relying on cumbersome manual efforts (e.g., surface cutting, part segmentation) for pre-processing. In this paper, we introduce the Flatten Anything Model (FAM), an unsupervised neural architecture to achieve global free-boundary surface parameterization via learning point-wise mappings between 3D points on the target geometric surface and adaptively-deformed UV coordinates within the 2D parameter domain. To mimic the actual physical procedures, we ingeniously construct geometrically-interpretable sub-networks with specific functionalities of surface cutting, UV deforming, unwrapping, and wrapping, which are assembled into a bi-directional cycle mapping framework. Compared with previous methods, our FAM directly operates on discrete surface points without utilizing connectivity information, thus significantly reducing the strict requirements for mesh quality and even applicable to unstructured point cloud data. More importantly, our FAM is fully-automated without the need for pre-cutting and can deal with highly-complex topologies, since its learning process adaptively finds reasonable cutting seams and UV boundaries. Extensive experiments demonstrate the universality, superiority, and inspiring potential of our proposed neural surface parameterization paradigm. Our code is available at https://github.com/keeganhk/FlattenAnything.

Abstract We propose a novel method for generating symmetric piecewise developable approximations for shapes in approximately global reflectional or rotational symmetry. Given a shape and its symmetry constraint, the algorithm contains two crucial steps: (i) a symmetric deformation to achieve a nearly developable model and (ii) a symmetric segmentation aided by the deformed shape. The key to the deformation step is the use of the symmetric implicit neural representations of the shape and the deformation field. A new mesh extraction from the implicit function is introduced to construct a strictly symmetric mesh for the subsequent segmentation. The symmetry constraint is carefully integrated into the partition to achieve the symmetric piecewise developable approximation. We demonstrate the effectiveness of our algorithm over various meshes.

Abstract The 3D Gaussian Splatting technique has significantly advanced the construction of radiance fields from multi‐view images, enabling real‐time rendering. While point‐based rasterization effectively reduces computational demands for rendering, it often struggles to accurately reconstruct the geometry of the target object, especially under strong lighting conditions. Strong lighting can cause significant color variations on the object's surface when viewed from different directions, complicating the reconstruction process. To address this challenge, we introduce an approach that combines octree‐based implicit surface representations with Gaussian Splatting. Initially, it reconstructs a signed distance field (SDF) and a radiance field through volume rendering, encoding them in a low‐resolution octree. This initial SDF represents the coarse geometry of the target object. Subsequently, it introduces 3D Gaussians as additional degrees of freedom, which are guided by the initial SDF. In the third stage, the optimized Gaussians enhance the accuracy of the SDF, enabling the recovery of finer geometric details compared to the initial SDF. Finally, the refined SDF is used to further optimize the 3D Gaussians via splatting, eliminating those that contribute little to the visual appearance. Experimental results show that our method, which leverages the distribution of 3D Gaussians with SDFs, reconstructs more accurate geometry, particularly in images with specular highlights caused by strong lighting. The source code can be downloaded from https://github.com/LaoChui999/GS-Octree .

the Best Paper Award Committee to select the Best Paper.After careful deliberation, the following paper was chosen with the unanimous consensus as the winner, on the basis of its intellectual merit and potential impact:Visual attention network [1] Two other papers were awarded an

Recent advances in point cloud completion make it possible to simultaneously recover complete shapes and fine details from partial point clouds captured by professional 3D devices, such as Lidar, or consumer cameras, such as iPhones. Despite significant progress, the potential utilization of self-projected views from partial inputs and the effective reduction of noise in generated point clouds remain under-explored. In this paper, we propose a novel point cloud completion method that leverages self-projected view augmentation and implicit field constraints. Specifically, we introduce a cross-view augmentation (CVA) module and a cross-modal fusion (CMF) module to enhance information interaction and integration at the image and modality levels, respectively. We also propose a bidirection-aware refinement block to improve detail and completeness by considering both complete-to-partial detail perception and partial-to-complete structure perception paths. Additionally, we address the issue of noise reduction from the perspective of implicit field constraints. We evaluate our method on several baseline datasets, including PCN, ShapeNet55/34 and KITTI (car). Extensive experiments demonstrate that our method outperforms state-of-the-art methods, achieving improvements of 0.11 CD-$\ell _{1}$, 0.015 DCD and 0.009 F-score on the standard PCN test set. Furthermore, our approach effectively reduces noise in the generated point clouds, showcasing its promising potential for practical applications.

Designing thin-shell structures that are diverse, lightweight, and physically viable is a challenging task for traditional heuristic methods. To address this challenge, we present a novel parametric design framework for engraving regular, irregular, and customized patterns on thin-shell structures. Our method optimizes pattern parameters such as size and orientation, to ensure structural stiffness while minimizing material consumption. Our method is unique in that it works directly with shapes and patterns represented by functions, and can engrave patterns through simple function operations. By eliminating the need for remeshing in traditional FEM methods, our method is more computationally efficient in optimizing mechanical properties and can significantly increase the diversity of shell structure design. Quantitative evaluation confirms the convergence of the proposed method. We conduct experiments on regular, irregular, and customized patterns and present 3D printed results to demonstrate the effectiveness of our approach.

Point cloud denoising is a fundamental and challenging problem in geometry processing. Existing methods typically involve direct denoising of noisy input or filtering raw normals followed by point position updates. Recognizing the crucial relationship between point cloud denoising and normal filtering, we re-examine this problem from a multitask perspective and propose an end-to-end network called PCDNF for joint normal filtering-based point cloud denoising. We introduce an auxiliary normal filtering task to enhance the network's ability to remove noise while preserving geometric features more accurately. Our network incorporates two novel modules. First, we design a shape-aware selector to improve noise removal performance by constructing latent tangent space representations for specific points, taking into account learned point and normal features as well as geometric priors. Second, we develop a feature refinement module to fuse point and normal features, capitalizing on the strengths of point features in describing geometric details and normal features in representing geometric structures, such as sharp edges and corners. This combination overcomes the limitations of each feature type and better recovers geometric information. Extensive evaluations, comparisons, and ablation studies demonstrate that the proposed method outperforms state-of-the-art approaches in both point cloud denoising and normal filtering.

The quality of point clouds is often limited by noise introduced during their capture process. Consequently, a fundamental 3D vision task is the removal of noise, known as point cloud filtering or denoising. State-of-the-art learning based methods focus on training neural networks to infer filtered displacements and directly shift noisy points onto the underlying clean surfaces. In high noise conditions, they iterate the filtering process. However, this iterative filtering is only done at test time and is less effective at ensuring points converge quickly onto the clean surfaces. We propose IterativePFN (iterative point cloud filtering network), which consists of multiple IterationModules that model the true iterative filtering process internally, within a single network. We train our IterativePFn network using a novel loss function that utilizes an adaptive ground truth target at each iteration to capture the relationship between intermediate filtering results during training. This ensures that the filtered results converge faster to the clean surfaces. Our method is able to obtain better performance compared to state-of-the-art methods. The source code can be found at: https://github.com/ddsediri/IterativePFN

Arbitrary-scale image super-resolution (SR) is often tackled using the implicit neural representation (INR) approach, which relies on a position encoding scheme to im-prove its representation ability. In this paper, we introduce orthogonal position encoding (OPE), an extension of po-sition encoding, and an OPE-Upscale module to replace the INR-based upsampling module for arbitrary-scale im-age super-resolution. Our OPE-Upscale module takes 2D coordinates and latent code as inputs, just like INR, but does not require any training parameters. This parameter-free feature allows the OPE-Upscale module to directly perform linear combination operations, resulting in con-tinuous image reconstruction and achieving arbitrary-scale image reconstruction. As a concise SR framework, our method is computationally efficient and consumes less mem-ory than state-of-the-art methods, as confirmed by exten-sive experiments and evaluations. In addition, our method achieves comparable results with state-of-the-art methods in arbitrary-scale image super-resolution. Lastly, we show that OPE corresponds to a set of orthogonal basis, validating our design principle.11Project page: https://github.com/gaochao-s/ope-sr

We present a learning-based method, namely GeoUDF, to tackle the long-standing and challenging problem of reconstructing a discrete surface from a sparse point cloud. To be specific, we propose a geometry-guided learning method for UDF and its gradient estimation that explicitly formulates the unsigned distance of a query point as the learnable affine averaging of its distances to the tangent planes of neighboring points on the surface. Besides, we model the local geometric structure of the input point clouds by explicitly learning a quadratic polynomial for each point. This not only facilitates upsampling the input sparse point cloud but also naturally induces unoriented normal, which further augments UDF estimation. Finally, to extract triangle meshes from the predicted UDF we propose a customized edge-based marching cube module. We conduct extensive experiments and ablation studies to demonstrate the significant advantages of our method over state-of-the-art methods in terms of reconstruction accuracy, efficiency, and generality. The source code is publicly available at https://github.com/rsy6318/GeoUDF.

Reconstructing 3D human heads in low-view settings presents technical challenges, mainly due to the pronounced risk of overfitting with limited views and high-frequency signals. To address this, we propose geometry decomposition and adopt a two-stage, coarse-to-fine training strategy, allowing for progressively capturing high-frequency geometric details. We represent 3D human heads using the zero level-set of a combined signed distance field, comprising a smooth template, a non-rigid deformation, and a high-frequency displacement field. The template captures features that are independent of both identity and expression and is co-trained with the deformation network across multiple individuals with sparse and randomly selected views. The displacement field, capturing individual-specific details, undergoes separate training for each person. Our network training does not require 3D supervision or object masks. Experimental results demonstrate the effectiveness and robustness of our geometry decomposition and two-stage training strategy. Our method outperforms existing neural rendering approaches in terms of reconstruction accuracy and novel view synthesis under low-view settings. Moreover, the pre-trained template serves a good initialization for our model when encountering unseen individuals.

Geodesics play a critical role in many geometry processing applications. Traditional algorithms for computing geodesics on 3D mesh models are often inefficient and slow, which make them impractical for scenarios requiring extensive querying of arbitrary point-to-point geodesics. Recently, deep implicit functions have gained popularity for 3D geometry representation, yet there is still no research on neural implicit representation of geodesics. To bridge this gap, we make the first attempt to represent geodesics using implicit learning frameworks. Specifically, we propose neural geodesic field (NeuroGF), which can be learned to encode all-pairs geodesics of a given 3D mesh model, enabling to efficiently and accurately answer queries of arbitrary point-to-point geodesic distances and paths. Evaluations on common 3D object models and real-captured scene-level meshes demonstrate our exceptional performances in terms of representation accuracy and querying efficiency. Besides, NeuroGF also provides a convenient way of jointly encoding both 3D geometry and geodesics in a unified representation. Moreover, the working mode of per-model overfitting is further extended to generalizable learning frameworks that can work on various input formats such as unstructured point clouds, which also show satisfactory performances for unseen shapes and categories. Our code and data are available at https://github.com/keeganhk/NeuroGF.

Given a set of generators, the geodesic Voronoi diagram (GVD) defines how the base surface is decomposed into separate regions such that each generator dominates a region in terms of geodesic distance to the generators. Generally speaking, each ordinary bisector point of the GVD is determined by two adjacent generators while each branching point of the GVD is given by at least three generators. When there are sufficiently many generators, straight-line distance serves as an effective alternative of geodesic distance for computing GVDs. However, for a set of sparse generators, one has to use exact or approximate geodesic distance instead, which requires a high computational cost to trace the bisectors and the branching points. We observe that it is easier to infer the branching points by stretching the ordinary segments than competing between wavefronts from different directions. Based on the observation, we develop an unfolding technique to compute the ordinary points of the GVD, as well as a growth-based technique to stretch the traced bisector segments such that they finally grow into a complete GVD. Experimental results show that our algorithm runs 3 times as fast as the state-of-the-art method at the same accuracy level.

The explosive growth of social media means portrait editing and retouching are in high demand. While portraits are commonly captured and stored as raster images, editing raster images is non-trivial and requires the user to be highly skilled. Aiming at developing intuitive and easy-to-use portrait editing tools, we propose a novel vectorization method that can automatically convert raster images into a 3-tier hierarchical representation. The base layer consists of a set of sparse diffusion curves (DCs) which characterize salient geometric features and low-frequency colors, providing a means for semantic color transfer and facial expression editing. The middle level encodes specular highlights and shadows as large, editable Poisson regions (PRs) and allows the user to directly adjust illumination by tuning the strength and changing the shapes of PRs. The top level contains two types of pixel-sized PRs for high-frequency residuals and fine details such as pimples and pigmentation. We train a deep generative model that can produce high-frequency residuals automatically. Thanks to the inherent meaning in vector primitives, editing portraits becomes easy and intuitive. In particular, our method supports color transfer, facial expression editing, highlight and shadow editing, and automatic retouching. To quantitatively evaluate the results, we extend the commonly used FLIP metric (which measures color and feature differences between two images) to consider illumination. The new metric, illumination-sensitive FLIP, can effectively capture salient changes in color transfer results, and is more consistent with human perception than FLIP and other quality measures for portrait images. We evaluate our method on the FFHQR dataset and show it to be effective for common portrait editing tasks, such as retouching, light editing, color transfer, and expression editing.

Point clouds are characterized by irregularity and unstructuredness, which pose challenges in efficient data exploitation and discriminative feature extraction. In this paper, we present an unsupervised deep neural architecture called Flattening-Net to represent irregular 3D point clouds of arbitrary geometry and topology as a completely regular 2D point geometry image (PGI) structure, in which coordinates of spatial points are captured in colors of image pixels. Intuitively, Flattening-Net implicitly approximates a locally smooth 3D-to-2D surface flattening process while effectively preserving neighborhood consistency. As a generic representation modality, PGI inherently encodes the intrinsic property of the underlying manifold structure and facilitates surface-style point feature aggregation. To demonstrate its potential, we construct a unified learning framework directly operating on PGIs to achieve diverse types of high-level and low-level downstream applications driven by specific task networks, including classification, segmentation, reconstruction, and upsampling. Extensive experiments demonstrate that our methods perform favorably against the current state-of-the-art competitors.

This paper explores the task-oriented compact representation of 3D point clouds, which should maintain the performance of subsequent applications applied to such compact point clouds as much as possible. Designing from the perspective of matrix optimization, we propose MOPS-Net, a novel deep learning-based method that is distinguishable from existing approaches due to its interpretability and flexibility. The matrix optimization problem is challenging due to the discrete and combinatorial nature of the sampling matrix. Therefore, we tackle the challenges by relaxing the binary constraint of the sampling matrix and formulating a constrained and differentiable optimization problem. We then design a deep neural network to mimic the matrix optimization by exploring both the local and global structures of the input data. MOPS-Net can be end-to-end trained with a task network and is permutation-invariant, making it robust to the input. We also extend MOPS-Net such that a single network after one-time training is capable of handling arbitrary downsampling ratios. Extensive experimental results show that MOPS-Net can achieve favorable performance against state-of-the-art deep learning-based methods over various tasks, including classification, reconstruction, and registration. Besides, we validate the robustness of MOPS-Net on noisy data.

This paper proposes a method to model masonry shell structures where the shell elements fall into a set of discrete equivalence classes. Such shell structure can reduce the fabrication cost and simplify the physical construction due to reuse of a few template shell elements. Given a freeform surface, our goal is to generate a small set of template shell elements that can be reused to produce a seamless and buildable structure that closely resembles the surface. The major technical challenge in this process is balancing the desire for high reusability of template elements with the need for a seamless and buildable final structure. To address the challenge, we define three error metrics to measure the seamlessness and buildability of shell structures made from discrete equivalence classes and develop a hierarchical cluster-and-optimize approach to generate a small set of template elements that produce a structure closely approximating the surface with low error metrics. We demonstrate the feasibility of our approach on various freeform surfaces and geometric patterns, and validate buildability of our results with four physical prototypes. Code and data of this paper are at https://github.com/Linsanity81/TileableShell.

In this paper, we propose a new method, called DoubleCoverUDF, for extracting the zero level-set from unsigned distance fields (UDFs). DoubleCoverUDF takes a learned UDF and a user-specified parameter r (a small positive real number) as input and extracts an iso-surface with an iso-value r using the conventional marching cubes algorithm. We show that the computed iso-surface is the boundary of the r -offset volume of the target zero level-set S , which is an orientable manifold, regardless of the topology of S. Next, the algorithm computes a covering map to project the boundary mesh onto S , preserving the mesh's topology and avoiding folding. If S is an orientable manifold surface, our algorithm separates the double-layered mesh into a single layer using a robust minimum-cut post-processing step. Otherwise, it keeps the double-layered mesh as the output. We validate our algorithm by reconstructing 3D surfaces of open models and demonstrate its efficacy and effectiveness on synthetic models and benchmark datasets. Our experimental results confirm that our method is robust and produces meshes with better quality in terms of both visual evaluation and quantitative measures than existing UDF-based methods. The source code is available at https://github.com/jjjkkyz/DCUDF.

Point cloud upsampling aims to generate dense point clouds from given sparse ones, which is a challenging task due to the irregular and unordered nature of point sets. To address this issue, we present a novel deep learning-based model, called PU-Flow, which incorporates normalizing flows and weight prediction techniques to produce dense points uniformly distributed on the underlying surface. Specifically, we exploit the invertible characteristics of normalizing flows to transform points between euclidean and latent spaces and formulate the upsampling process as ensemble of neighbouring points in a latent space, where the ensemble weights are adaptively learned from local geometric context. Extensive experiments show that our method is competitive and, in most test cases, it outperforms state-of-the-art methods in terms of reconstruction quality, proximity-to-surface accuracy, and computation efficiency. The source code will be publicly available at https://github.com/unknownue/puflow.

3D reconstruction from single-view images is a long-standing research problem. There have been various methods based on point clouds and volumetric representations. In spite of success in 3D models generation, it is quite challenging for these approaches to deal with models with complex topology and fine geometric details. Thanks to the recent advance of deep shape representations, learning the structure and detail representation using deep neural networks is a promising direction. In this article, we propose a novel approach named STD-Net to reconstruct 3D models utilizing mesh representation that is well suited for characterizing complex structures and geometry details. Our method consists of (1) an auto-encoder network for recovering the structure of an object with bounding box representation from a single-view image; (2) a topology-adaptive GCN for updating vertex position for meshes of complex topology; and (3) a unified mesh deformation block that deforms the structural boxes into structure-aware meshes. Evaluation on ShapeNet and PartNet shows that STD-Net has better performance than state-of-the-art methods in reconstructing complex structures and fine geometric details.

Simulating liquid-textile interaction has received great attention in computer graphics recently. Most existing methods take textiles as particles or parameterized meshes. Although these methods can generate visually pleasing results, they cannot simulate water content at a microscopic level due to the lack of geometrically modeling of textile's anisotropic structure. In this paper, we develop a method for yarn-level simulation of hygroscopicity of textiles and evaluate it using various quantitative metrics. We model textiles in a fiber-yarn-fabric multi-scale manner and consider the dynamic coupled physical mechanisms of liquid spreading, including wetting, wicking, moisture sorption/desorption, and transient moisture-heat transfer in textiles. Our method can accurately simulate liquid spreading on textiles with different fiber materials and geometrical structures with consideration of air temperatures and humidity conditions. It visualizes the hygroscopicity of textiles to demonstrate their moisture management ability. We conduct qualitative and quantitative experiments to validate our method and explore various factors to analyze their influence on liquid spreading and hygroscopicity of textiles.

Geodesics measure the shortest distance (either locally or globally) between two points on a curved surface and serve as a fundamental tool in digital geometry processing. Suppose that we have a parameterized path$\gamma (t)=\mathbf {x}(u(t),v(t))$on a surface$\mathbf {x}=\mathbf {x}(u,v)$with$\gamma (0)=p$and$\gamma (1)=q$. We formulate the two-point geodesic problem into a minimization problem$\int _0^1 H(\Vert \mathbf {x}_uu^{\prime }(t)+\mathbf {x}_vv^{\prime }(t)\Vert)\text{d}t$, where$H(s)$satisfies$H(0)=0,H^{\prime }(s)>0$and$H^{\prime \prime }(s)\geq 0$for$s>0$. In our implementation, we choose$H(s)=e^{s^2}-1$and show that it has several unique advantages over other choices such as$H(s)=s^2$and$H(s)=s$. It is also a minimizer of the traditional geodesic length variational and able to guarantee the uniqueness and regularity in terms of curve parameterization. In the discrete setting, we construct the initial path by a sequence of moveable points$\lbrace x_i\rbrace _{i=1}^n$and minimize$\sum _{i=1}^{n} H(\Vert x_i - x_{i+1}\Vert)$. The resulting points are evenly spaced along the path. It’s obvious that our algorithm can deal with parametric surfaces. Considering that meshes, point clouds and implicit surfaces can be transformed into a signed distance function (SDF), we also discuss its implementation on a general SDF. Finally, we show that our method can be extended to solve a general least-cost path problem. We validate the proposed algorithm in terms of accuracy, performance and scalability, and demonstrate the advantages by extensive comparisons.

This paper investigates the problem of temporally interpolating dynamic 3D point clouds with large non-rigid deformation. We formulate the problem as estimation of point-wise trajectories (i.e., smooth curves) and further reason that temporal irregularity and under-sampling are two major challenges. To tackle the challenges, we propose IDEA-Net, an end-to-end deep learning framework, which disentangles the problem under the assistance of the explicitly learned temporal consistency. Specifically, we propose a temporal consistency learning module to align two consecutive point cloud frames point-wisely, based on which we can employ linear interpolation to obtain coarse trajectories/in-between frames. To compensate the high-order nonlinear components of trajectories, we apply aligned feature embeddings that encode local geometry properties to regress point-wise increments, which are combined with the coarse estimations. We demonstrate the effectiveness of our method on various point cloud sequences and observe large improvement over state-of-the-art methods both quantitatively and visually. Our framework can bring benefits to 3D motion data acquisition. The source code is publicly available at https://github.com/ZENGYIMING-EAMON/IDEANet.git.

We present a simple yet effective method for constructing 3D self-supporting surfaces with planar quadrilateral (PQ) elements. Starting with a triangular discretization of a self-supporting surface, we first compute the principal curvatures and directions of each triangular face using a new discrete differential geometry approach, yielding more accurate results than existing methods. Then, we smooth the principal direction field to reduce the number of singularities. Next, we partition all faces into two groups in terms of principal curvature difference. For each face with small curvature difference, we compute a stretch matrix that turns the principal directions into a pair of conjugate directions. For the remaining triangular faces, we simply keep their smoothed principal directions. Finally, applying a mixed-integer programming solver to the mixed principal and conjugate direction field, we obtain a planar quadrilateral mesh. Experimental results show that our method is computationally efficient and can yield high-quality PQ meshes that well approximate the geometry of the input surfaces and maintain their self-supporting properties.

Poisson surface reconstruction (PSR) remains a popular technique for reconstructing watertight surfaces from 3D point samples thanks to its efficiency, simplicity, and robustness. Yet, the existing PSR method and subsequent variants work only for oriented points. This paper intends to validate that an improved PSR, called iPSR, can completely eliminate the requirement of point normals and proceed in an iterative manner. In each iteration, iPSR takes as input point samples with normals directly computed from the surface obtained in the preceding iteration, and then generates a new surface with better quality. Extensive quantitative evaluation confirms that the new iPSR algorithm converges in 5--30 iterations even with randomly initialized normals. If initialized with a simple visibility based heuristic, iPSR can further reduce the number of iterations. We conduct comprehensive comparisons with PSR and other powerful implicit-function based methods. Finally, we confirm iPSR's effectiveness and scalability on the AIM@SHAPE dataset and challenging (indoor and outdoor) scenes. Code and data for this paper are at https://github.com/houfei0801/ipsr.

Color design for 3D indoor scenes is a challenging problem due to many factors that need to be balanced. Although learning from images is a commonly adopted strategy, this strategy may be more suitable for natural scenes in which objects tend to have relatively fixed colors. For interior scenes consisting mostly of man-made objects, creative yet reasonable color assignments are expected. We propose$C^{3}$C3Assignment, a system providing diverse suggestions for interior color design while satisfying general global and local rules including color compatibility, color mood, contrast, and user preference. We extend these constraints from the image domain to$\mathbb {R}^3$, and formulate 3D interior color design as an optimization problem. The design is accomplished in an omnidirectional manner to ensure a comfortable experience when the inhabitant observes the interior scene from possible positions and directions. We design a surrogate-assisted evolutionary algorithm to efficiently solve the highly nonlinear optimization problem for interactive applications, and investigate the system performance concerning problem complexity, solver convergence, and suggestion diversity. Preliminary user studies have been conducted to validate the rule extension from 2D to 3D and to verify system usability.

We propose a robust normal estimation method for both point clouds and meshes using a low rank matrix approximation algorithm. First, we compute a local isotropic structure for each point and find its similar, non-local structures that we organize into a matrix. We then show that a low rank matrix approximation algorithm can robustly estimate normals for both point clouds and meshes. Furthermore, we provide a new filtering method for point cloud data to smooth the position data to fit the estimated normals. We show the applications of our method to point cloud filtering, point set upsampling, surface reconstruction, mesh denoising, and geometric texture removal. Our experiments show that our method generally achieves better results than existing methods.

This article presents a simple yet effective method for computing geodesic distances on triangle meshes. Unlike the popular window propagation methods that partition mesh edges into intervals of varying lengths, our method places evenly-spaced, source-independent Steiner points on edges. Given a source vertex, our method constructs a Steiner-point graph that partitions the surface into mutually exclusive tracks, called geodesic tracks. Inside each triangle, the tracks form sub-regions in which the change of distance field is approximately linear. Our method does not require any pre-computation, and can effectively balance speed and accuracy. Experimental results show that with 5 Steiner points on each edge, the mean relative error is less than 0.3 % for common 3D models used in the graphics community. We propose a set of effective filtering rules to eliminate a large amount of useless broadcast events. For a 1000K-face model, our method runs 10 times faster than the conventional Steiner point method that examines a complete graph of Steiner points in each triangle. We also observe that using more Steiner points increases the accuracy at only a small extra computational cost. Our method works well for meshes with poor triangulation and non-manifold configuration, which often poses challenges to the existing PDE methods. We show that geodesic tracks, as a new data structure that encodes rich information of discrete geodesics, support accurate geodesic path and isoline tracing, and efficient distance query. Our method can be easily extended to meshes with non-constant density functions and/or anisotropic metrics.

In this article, we develop a novel method for fast geodesic distance queries. The key idea is to embed the mesh into a high-dimensional space, such that the euclidean distance in the high-dimensional space can induce the geodesic distance in the original manifold surface. However, directly solving the high-dimensional embedding problem is not feasible due to the large number of variables and the fact that the embedding problem is highly nonlinear. We overcome the challenges with two novel ideas. First, instead of taking all vertices as variables, we embed only the saddle vertices, which greatly reduces the problem complexity. We then compute a local embedding for each non-saddle vertex. Second, to reduce the large approximation error resulting from the purely euclidean embedding, we propose a cascaded optimization approach that repeatedly introduces additional embedding coordinates with a non-euclidean function to reduce the approximation residual. Using the precomputation data, our approach can determine the geodesic distance between any two vertices in near-constant time. Computational testing results show that our method is more desirable than previous geodesic distance queries methods.

Motivated by the intuition that one can transform two aligned point clouds to each other more easily and meaningfully than a misaligned pair, we propose CorrNet3D – the first unsupervised and end-to-end deep learning-based framework – to drive the learning of dense correspondence between 3D shapes by means of deformation-like reconstruction to overcome the need for annotated data. Specifically, CorrNet3D consists of a deep feature embedding module and two novel modules called correspondence indicator and symmetric deformer. Feeding a pair of raw point clouds, our model first learns the pointwise features and passes them into the indicator to generate a learnable correspondence matrix used to permute the input pair. The symmetric deformer, with an additional regularized loss, transforms the two permuted point clouds to each other to drive the unsupervised learning of the correspondence. The extensive experiments on both synthetic and real-world datasets of rigid and non-rigid 3D shapes show our CorrNet3D outperforms state-of-the-art methods to a large extent, including those taking meshes as input. CorrNet3D is a flexible framework in that it can be easily adapted to supervised learning if annotated data are available. The source code and pre-trained model will be available at https://github.com/ZENGYIMINGEAMON/CorrNet3D.git.

In this paper, we propose a parallel and scalable approach for geodesic distance computation on triangle meshes. Our key observation is that the recovery of geodesic distance with the heat method [1] can be reformulated as optimization of its gradients subject to integrability, which can be solved using an efficient first-order method that requires no linear system solving and converges quickly. Afterward, the geodesic distance is efficiently recovered by parallel integration of the optimized gradients in breadth-first order. Moreover, we employ a similar breadth-first strategy to derive a parallel Gauss-Seidel solver for the diffusion step in the heat method. To further lower the memory consumption from gradient optimization on faces, we also propose a formulation that optimizes the projected gradients on edges, which reduces the memory footprint by about 50 percent. Our approach is trivially parallelizable, with a low memory footprint that grows linearly with respect to the model size. This makes it particularly suitable for handling large models. Experimental results show that it can efficiently compute geodesic distance on meshes with more than 200 million vertices on a desktop PC with 128 GB RAM, outperforming the original heat method and other state-of-the-art geodesic distance solvers.

Complex blur such as the mixup of space-variant and space-invariant blur, which is hard to model mathematically, widely exists in real images. In this article, we propose a novel image deblurring method that does not need to estimate blur kernels. We utilize a pair of images that can be easily acquired in low-light situations: (1) a blurred image taken with low shutter speed and low ISO noise; and (2) a noisy image captured with high shutter speed and high ISO noise. Slicing the blurred image into patches, we extend the Gaussian mixture model (GMM) to model the underlying intensity distribution of each patch using the corresponding patches in the noisy image. We compute patch correspondences by analyzing the optical flow between the two images. The Expectation Maximization (EM) algorithm is utilized to estimate the parameters of GMM. To preserve sharp features, we add an additional bilateral term to the objective function in the M-step. We eventually add a detail layer to the deblurred image for refinement. Extensive experiments on both synthetic and real-world data demonstrate that our method outperforms state-of-the-art techniques, in terms of robustness, visual quality, and quantitative metrics.

This paper addresses the problem of generating dense point clouds from given sparse point clouds to model the underlying geometric structures of objects/scenes. To tackle this challenging issue, we propose a novel end-to-end learning-based framework. Specifically, by taking advantage of the linear approximation theorem, we first formulate the problem explicitly, which boils down to determining the interpolation weights and high-order approximation errors. Then, we design a lightweight neural network to adaptively learn unified and sorted interpolation weights as well as the high-order refinements, by analyzing the local geometry of the input point cloud. The proposed method can be interpreted by the explicit formulation, and thus is more memory-efficient than existing ones. In sharp contrast to the existing methods that work only for a pre-defined and fixed upsampling factor, the proposed framework only requires a single neural network with one-time training to handle various upsampling factors within a typical range, which is highly desired in real-world applications. In addition, we propose a simple yet effective training strategy to drive such a flexible ability. In addition, our method can handle non-uniformly distributed and noisy data well. Extensive experiments on both synthetic and real-world data demonstrate the superiority of the proposed method over state-of-the-art methods both quantitatively and qualitatively. The code will be publicly available at https://github.com/ninaqy/Flexible-PU.

Human poses play a critical role in human-centric product design. Despite considerable researches on pose synthesis and pose-driven product design, most of them adopt the simple stick figure model that captures only skeletons rather than real body geometries and do not link human poses to the environment (e.g., chairs for sitting). This paper focuses on user-tailored ergonomic design and rating of chairs using scanned human geometries. Fully utilizing the anthropometric information of the human models, our method considers more ergonomic guidelines of chair design (such as pressure distribution and support intensity) and links the geometry of 3D chair models and human-to-chair interactions into the pose deformation constraints of the human avatars. The core of our method is a pose generation algorithm which rigs the user's successive poses through coarse- and fine-level pose deformations. We define a non-linear energy function with contact, collision, and joint limit terms, and solve it using a hill-climbing algorithm. The fitting results allow us to quantitatively evaluate the chair model in terms of various ergonomic criteria. Our method is flexible and effective and can be applied to users with varying body shapes and a wide range of chairs. Moreover, the proposed technique can be easily extended to other furniture, such as desk, bed, and cabinet. Extensive evaluations and a user study demonstrate the efficiency and advantages of the proposed virtual fitting method. Given that our method avoids tedious on-site trying, facilitates the exploration/evaluation of various chair products, and provides valuable feedback for the designers and manufacturers to deliver customized products, it is ideal for online shopping of chairs.

Point cloud filtering is a fundamental problem in geometry modeling and processing. Despite of significant advancement in recent years, the existing methods still suffer from two issues: 1) they are either designed without preserving sharp features or less robust in feature preservation; and 2) they usually have many parameters and require tedious parameter tuning. In this article, we propose a novel deep learning approach that automatically and robustly filters point clouds by removing noise and preserving their sharp features. Our point-wise learning architecture consists of an encoder and a decoder. The encoder directly takes points (a point and its neighbors) as input, and learns a latent representation vector which goes through the decoder to relate the ground-truth position with a displacement vector. The trained neural network can automatically generate a set of clean points from a noisy input. Extensive experiments show that our approach outperforms the state-of-the-art deep learning techniques in terms of both visual quality and quantitative error metrics. The source code and dataset can be found at https://github.com/dongbo-BUAA-VR/Pointfilter.

We present an automated treadmill featuring physiological-data-driven feedback-PhysioTreadmill, which allows its user to easily control running settings based on their physical condition and can also motivate them through real-time physiological computing. We developed a robust exercise intensity self-adaptive adjustment algorithm using physiological data processing to adjust the user's physiological state accurately. We also designed exergames with physiological-data-driven visual/audio feedback in PhysioTreadmill. With PhysioTreadmill, we can ideally increase exercise duration, and enhance exercise performance and safety. Two user studies involving 42 participants showed that PhysioTreadmill is user-friendly and can effectively extend users' training duration.

Abstract Apollonius diagrams, also known as additively weighted Voronoi diagrams, are an extension of Voronoi diagrams, where the weighted distance is defined by the Euclidean distance minus the weight. The bisectors of Apollonius diagrams have a hyperbolic form, which is fundamentally different from traditional Voronoi diagrams and power diagrams. Though robust solvers are available for computing 2D Apollonius diagrams, there is no practical approach for the 3D counterpart. In this paper, we systematically analyze the structural features of 3D Apollonius diagrams, and then develop a fast algorithm for robustly computing Apollonius diagrams in 3D. Our algorithm consists of vertex location, edge tracing and face extraction, among which the key step is to adaptively subdivide the initial large box into a set of sufficiently small boxes such that each box contains at most one Apollonius vertex. Finally, we use centroidal Voronoi tessellation (CVT) to discretize the curved bisectors with well‐tessellated triangle meshes. We validate the effectiveness and robustness of our algorithm through extensive evaluation and experiments. We also demonstrate an application on computing centroidal Apollonius diagram.

This paper develops a new method for constructing Discrete Geodesic Graph (DGG)—an undirected, sparse graph for computing discrete geodesic distances and paths on triangle meshes. Based on a novel accuracy aware window propagation scheme, our method is able to compute the graph edges in a direct and efficient manner. Given a triangle mesh with n vertices and a user-specified accuracy parameter ɛ, our method produces a DGG with O ( n \√ɛ) edges in empirical O ( n \ɛ 0.75 log 1\ɛ) time, which greatly improves the time complexity O ( n \ɛ log 1\ɛ) of the existing method. Extensive evaluation on a large-scale 3D shape repository shows that our method is efficient and can produce high-quality geodesic distances with predictable accuracy and guaranteed true distance metric. In particular, our method has a great advantage over the existing approximate methods on meshes with high degree of anisotropy. The source code is available at https://github.com/GeodesicGraph.

This paper presents Poisson vector graphics (PVG), an extension of the popular diffusion curves (DC), for generating smooth-shaded images. Armed with two new types of primitives, called Poisson curves and Poisson regions, PVG can easily produce photorealistic effects such as specular highlights, core shadows, translucency and halos. Within the PVG framework, the users specify color as the Dirichlet boundary condition of diffusion curves and control tone by offsetting the Laplacian of colors, where both controls are simply done by mouse click and slider dragging. PVG distinguishes itself from other diffusion based vector graphics for 3 unique features: 1) explicit separation of colors and tones, which follows the basic drawing principle and eases editing; 2) native support of seamless cloning in the sense that PCs and PRs can automatically fit into the target background; and 3) allowed intersecting primitives (except for DC-DC intersection) so that users can create layers. Through extensive experiments and a preliminary user study, we demonstrate that PVG is a simple yet powerful authoring tool that can produce photo-realistic vector graphics from scratch.

State-of-the-art researches model the data of images and videos as low-dimensional manifolds and generate superpixels/supervoxels in a content-sensitive way, which is achieved by computing geodesic centroidal Voronoi tessellation (GCVT) on manifolds. However, computing exact GCVTs is slow due to computationally expensive geodesic distances. In this paper, we propose a much faster queue-based graph distance (called q-distance). Our key idea is that for manifold regions in which q-distances are different from geodesic distances, GCVT is prone to placing more generators in them, and therefore after few iterations, the q-distance-induced tessellation is an exact GCVT. This idea works well in practice and we also prove it theoretically under moderate assumption. Our method is simple and easy to implement. It runs 6-8 times faster than state-of-the-art GCVT computation, and has an optimal approximation ratio O(1) and a linear time complexity O(N) for N-pixel images or N-voxel videos. A thorough evaluation of 31 superpixel methods on five image datasets and 8 supervoxel methods on four video datasets shows that our method consistently achieves the best over-segmentation accuracy. We also demonstrate the advantage of our method on one image and two video applications.

Abstract Image vectorization is an important yet challenging problem, especially when the input image has rich content. In this paper, we develop a novel method for automatically vectorizing natural images with feature‐aligned quad‐dominant meshes. Inspired by the quadrangulation methods in 3D geometry processing, we propose a new directional field optimization technique by encoding the color gradients, sidestepping the explicit computing of salient image features. We further compute the anisotropic scales of the directional field by accommodating the distance among image features. Our method is fully automatic and efficient, which takes only a few seconds for a 400×400 image on a normal laptop. We demonstrate the effectiveness of the proposed method on various image editing applications.

Most existing proposals for indoor localization are “unnatural,” as they rely on sensing abilities not available to human beings. While such a mismatch causes complications in human-computer interactions and thus potentially reduces the usability and friendliness of a localization service, it is partially entailed by the need for low-cost/effort sensing with resource-limited mobile devices. Fortunately, recent developments in smart glasses (e.g., Google Glasses) signal a trend toward realistic visual sensing and hence make the sensing ability of mobile devices more compatible to that of human users. Leveraging such front-end developments, we propose VisioMap as a natural indoor localization system that intentionally mimics the human skills in visual localization. VisioMap uses very sparse photograph samples to reconstruct 3-D indoor scenes; this is facilitated by the facts that photographs are taken at the eye-level with high stability and regularity, and that the reconstruction is lightweight as it exploits geometric features rather than image pixels. Localization is in turn performed by matching the geometric features extracted online to the reconstructed 3-D scene, making VisioMap: 1) natural to users as they can see the matched 3-D scene and 2) dispensed with the need for dense fingerprints/POIs toward accurate localization.

This article presents a new computational framework for constructing 3D self-supporting surfaces with isotropic stress. Inspired by the self-supporting property of catenary and the fact that catenoid (the surface of revolution of the catenary curve) is a minimal surface, we discover the relation between 3D self-supporting surfaces and 4D minimal hypersurfaces (which are 3-manifolds). Lifting the problem into 4D allows us to convert gravitational forces into tensions and reformulate the equilibrium problem to total potential energy minimization, which can be solved using a variational method. We prove that the hyper-generatrix of a 4D minimal hyper-surface of revolution is a 3D self-supporting surface, implying that constructing a 3D self-supporting surface is equivalent to volume minimization. We show that the energy functional is simply the surface’s gravitational potential energy, which in turn can be converted into a surface reconstruction problem with mean curvature constraint. Armed with our theoretical findings, we develop an iterative algorithm to construct 3D self-supporting surfaces from triangle meshes. Our method guarantees convergence and can produce near-regular triangle meshes, thanks to a local mesh refinement strategy similar to centroidal Voronoi tessellation. It also allows users to tune the geometry via specifying either the zero potential surface or its desired volume. We also develop a finite element method to verify the equilibrium condition on 3D triangle meshes. The existing thrust network analysis methods discretize both geometry and material by approximating the continuous stress field through uniaxial singular stresses, making them an ideal tool for analysis and design of beam structures. In contrast, our method works on piecewise linear surfaces with continuous material. Moreover, our method does not require the 3D-to-2D projection, therefore it also works for both height and non-height fields.

In this article, we introduce a novel method that can generate a sequence of physical transformations between 3D models with different shape and topology. Feasible transformations are realized on a chain structure with connected components that are 3D printed. Collision-free motions are computed to transform between different configurations of the 3D printed chain structure. To realize the transformation between different 3D models, we first voxelize these input models into a similar number of voxels. The challenging part of our approach is to generate a simple path—as a chain configuration to connect most voxels. A layer-based algorithm is developed with theoretical guarantee of the existence and the path length. We find that collision-free motion sequence can always be generated when using a straight line as the intermediate configuration of transformation. The effectiveness of our method is demonstrated by both the simulation and the experimental tests taken on 3D printed chains.

This paper proposes a novel method for decorating 3D surfaces using a new type of vector graphics, called Poisson Vector Graphics (PVG). Unlike other existing techniques that frequently require local/global parameterization, our approach advocates a parameterization-free paradigm, affording decoration of geometric models with any topological type while minimizing the overall computational expenses. Since PVG supports a set of simple discrete curves, it is straightforward for users to edit colors and synthesize geometry details. Meanwhile, the details could be organized by Poisson Region (PR), leading to much smoother decoration than those of Diffusion Curve (DC). Consequently, it is an ideal tool to create smooth relief. It may be noted that, DC is adequate to create sharp or discontinuous results. But PR is superior to DC, supporting level-of-details editing on meshes thanks to its smoothness. To render PVG on meshes efficiently, we develop a Poisson solver based on harmonic B-splines, which could be constructed using geodesic Voronoi diagram . Our Poisson solver is a local solver for rendering with more flexibility and versatility. We demonstrate the efficacy of our approach on synthetic and real-world 3D models.

Superpixels are perceptually meaningful atomic regions that can effectively capture image features. Among various methods for computing uniform superpixels, simple linear iterative clustering (SLIC) is popular due to its simplicity and high performance. In this paper, we extend SLIC to compute content-sensitive superpixels, i.e., small superpixels in content-dense regions with high intensity or colour variation and large superpixels in content-sparse regions. Rather than using the conventional SLIC method that clusters pixels in , we map the input image to a 2-dimensional manifold , whose area elements are a good measure of the content density in . We propose a simple method, called intrinsic manifold SLIC (IMSLIC), for computing a geodesic centroidal Voronoi tessellation (GCVT)-a uniform tessellation-on , which induces the content-sensitive superpixels in . In contrast to the existing algorithms, IMSLIC characterizes the content sensitivity by measuring areas of Voronoi cells on . Using a simple and fast approximation to a closed-form solution, the method can compute the GCVT at a very low cost and guarantees that all Voronoi cells are simply connected. We thoroughly evaluate IMSLIC and compare it with eleven representative methods on the BSDS500 dataset and seven representative methods on the NYUV2 dataset. Computational results show that IMSLIC outperforms existing methods in terms of commonly used quality measures pertaining to superpixels such as compactness, adherence to boundaries, and achievable segmentation accuracy. We also evaluate IMSLIC and seven representative methods in an image contour closure application, and the results on two datasets, WHD and WSD, show that IMSLIC achieves the best foreground segmentation performance.

This paper presents a 3-D printing system that uses a low-cost off-the-shelf consumer projector to fabricate large models. Compared with traditional digital light processing (DLP) 3-D printers using a single vertical carriage, the platform of our DLP 3-D printer using delta mechanism can also move horizontally in the plane. We show that this system can print 3-D models much larger than traditional DLP 3-D printers. The major challenge to realize 3-D printing of large models in our system comes from how to cover a planar polygonal domain by a minimum number of rectangles with fixed size, which is NP-hard. We propose a simple yet efficient approximation algorithm to solve this problem. The key idea is to segment a polygonal domain using its medial axis and afterward merge small parts in the segmentation. Given an arbitrary polygon Q with n generators (i.e., line segments and reflex vertices in Q), we show that the time complexity of our algorithm is O(n2log2n) and the number of output rectangles covering Q is O(Kn), where K is an input-polygon-dependent constant. A physical prototype system is built and several large 3-D models with complex geometric structures have been printed as examples to demonstrate the effectiveness of our approach.

Delaunay meshes (DM) are a special type of manifold triangle meshes --- where the local Delaunay condition holds everywhere --- and find important applications in digital geometry processing. This paper addresses the general DM simplification problem: given an arbitrary manifold triangle mesh M with n vertices and the user-specified resolution m (< n ), compute a Delaunay mesh M * with m vertices that has the least Hausdorffdistance to M. To solve the problem, we abstract the simplification process using a 2D Cartesian grid model, in which each grid point corresponds to triangle meshes with a certain number of vertices and a simplification process is a monotonic path on the grid. We develop a novel differential-evolution-based method to compute a low-cost path, which leads to a high quality Delaunay mesh. Extensive evaluation shows that our method consistently outperforms the existing methods in terms of approximation error. In particular, our method is highly effective for small-scale CAD models and man-made objects with sharp features but less details. Moreover, our method is fully automatic and can preserve sharp features well and deal with models with multiple components, whereas the existing methods often fail.

Sparse signal representation has proven to be an extremely powerful tool in a wide range of engineering applications. However, most of the existing techniques are designed for regular data (such as audio signals and images/videos) that uniformly lies in regular Euclidian spaces. This paper aims at extending sparse representation for irregular data (such as colors of 3D point clouds) that is defined on irregular domains embedded in Euclidean spaces. Dealing with the irregular structure of such data via a virtual adaptive sampling process, we formulate sparse representation as an ℓ0-norm regularized optimization problem. Experimental results show that the proposed algorithm outperforms the state-of-the-art algorithm to a large extent: with the same number of nonzero coefficients, we improve the reconstruction quality up to 5 dB; conversely, fixing the reconstruction quality, our method uses only 55% coefficients. Using compressive sensing theory, we provide an intuitive explanation on how and why our algorithm works well in practice.

Learning “motion” online or from video tutorials is usually inefficient since it is difficult to deliver “motion” information in traditional ways and in the ordinary PC platform. This paper presents ImmerTai, a system that can efficiently teach motion, in particular Chinese Taichi motion, in various immersive environments. ImmerTai captures the Taichi expert's motion and delivers to students the captured motion in multi-modal forms in immersive CAVE, HMD as well as ordinary PC environments. The students' motions are captured too for quality assessment and utilized to form a virtual collaborative learning atmosphere. We built up a Taichi motion dataset with 150 fundamental Taichi motions captured from 30 students, on which we evaluated the learning effectiveness and user experience of ImmerTai. The results show that ImmerTai can enhance the learning efficiency by up to 17.4% and the learning quality by up to 32.3%.

We present a new graph-based method, called discrete geodesic graph (DGG), to compute discrete geodesics in a divide-and-conquer manner. Let M be a manifold triangle mesh with n vertices and 𝜀 > 0 the given accuracy parameter. Assume the vertices are uniformly distributed on the input mesh. We show that the DGG associated to M has 𝑂 ⁡ ( 𝑛 √ 𝜀 ) edges and the shortest path distances on the graph approximate geodesic distances on M with relative error 𝑂 ⁡ ( 𝜀 ) . Computational results show that the actual error is less than 0.6 ε on common models. Taking advantage of DGG's unique features, we develop a DGG-tailored label-correcting algorithm that computes geodesic distances in empirically linear time. With DGG, we can guarantee the computed distances are true distance metrics, which is highly desired in many applications. We observe that DGG significantly outperforms saddle vertex graph (SVG) – another graph based method for discrete geodesics – in terms of graph size, accuracy control and runtime performance.

Low-rank matrix approximation (LRMA) is a powerful technique for signal processing and pattern analysis. However, its potential for data compression has not yet been fully investigated. In this paper, we propose sparse LRMA (SLRMA), an effective computational tool for data compression. SLRMA extends conventional LRMA by exploring both the intra and inter coherence of data samples simultaneously. With the aid of prescribed orthogonal transforms (e.g., discrete cosine/wavelet transform and graph transform), SLRMA decomposes a matrix into a product of two smaller matrices, where one matrix is made up of extremely sparse and orthogonal column vectors and the other consists of the transform coefficients. Technically, we formulate SLRMA as a constrained optimization problem, i.e., minimizing the approximation error in the least-squares sense regularized by the $\ell _{0}$ -norm and orthogonality, and solve it using the inexact augmented Lagrangian multiplier method. Through extensive tests on real-world data, such as 2D image sets and 3D dynamic meshes, we observe that: 1) SLRMA empirically converges well; 2) SLRMA can produce approximation error comparable to LRMA but in a much sparse form; and 3) SLRMA-based compression schemes significantly outperform the state of the art in terms of rate-distortion performance.

Recent large-scale deployments of wireless sensor networks have posed a high demand on network throughput, forcing all (discrete) orthogonal ZigBee channels to be exploited to enhance transmission parallelism. However, the interference from widely deployed WiFi networks has severely jeopardized the usability of these discrete ZigBee channels, while the existing CSMA-based ZigBee MAC is too conservative to utilize each channel temporally. In this paper, we propose ART (Adaptive fRequency-Temporal co-existing) as a framework consisting of two components: FAVOR (FrequencyAllocation for Versatile Occupancy of spectRum) and P-CSMA (Probabilistic CSMA), to improve the co-existence between ZigBee and WiFi in both frequency and temporal perspectives. On one hand, FAVOR allocates continuous (center) frequencies to nodes/links in a near-optimal manner, by innovatively converting the problem into a spatial tessellation problem in a unified frequency-spatial space. This allows ART to fully exploit the “frequency white space” left out by WiFi. On the other hand, ART employs P-CSMA to opportunistically tune the use of CSMA for leveraging the “temporal white space” of WiFi interference, according to real-time assessment of transmission quality. We implement ART in MicaZ platforms, and our extensive experiments strongly demonstrate the efficacy of ART in enhancing both throughput and transmission quality.

Intrinsic Delaunay triangulation (IDT) naturally generalizes Delaunay triangulation from R 2 to curved surfaces. Due to many favorable properties, the IDT whose vertex set includes all mesh vertices is of particular interest in polygonal mesh processing. To date, the only way for constructing such IDT is the edge-flipping algorithm, which iteratively flips non-Delaunay edges to become locally Delaunay. Although this algorithm is conceptually simple and guarantees to terminate in finite steps, it has no known time complexity and may also produce triangulations containing faces with only two edges. This article develops a new method to obtain proper IDTs on manifold triangle meshes. We first compute a geodesic Voronoi diagram (GVD) by taking all mesh vertices as generators and then find its dual graph. The sufficient condition for the dual graph to be a proper triangulation is that all Voronoi cells satisfy the so-called closed ball property. To guarantee the closed ball property everywhere, a certain sampling criterion is required. For Voronoi cells that violate the closed ball property, we fix them by computing topologically safe regions, in which auxiliary sites can be added without changing the topology of the Voronoi diagram beyond them. Given a mesh with n vertices, we prove that by adding at most O ( n ) auxiliary sites, the computed GVD satisfies the closed ball property, and hence its dual graph is a proper IDT. Our method has a theoretical worst-case time complexity O ( n 2 + tn log n ), where t is the number of obtuse angles in the mesh. Computational results show that it empirically runs in linear time on real-world models.

Biharmonic B-splines, proposed by Feng and Warren, are an elegant generalization of univariate B-splines to planar and curved domains with fully irregular knot configuration. Despite the theoretic breakthrough, certain technical difficulties are imperative, including the necessity of Voronoi tessellation, the lack of analytical formulation of bases on general manifolds, expensive basis re-computation during knot refinement/removal, being applicable for simple domains only (e.g., such as euclidean planes, spherical and cylindrical domains, and tori). To ameliorate, this paper articulates a new biharmonic B-spline computing paradigm with a simple formulation. We prove that biharmonic B-splines have an equivalent representation, which is solely based on a linear combination of Green's functions of the bi-Laplacian operator. Consequently, without explicitly computing their bases, biharmonic B-splines can bypass the Voronoi partitioning and the discretization of bi-Laplacian, enable the computational utilities on any compact 2-manifold. The new representation also facilitates optimization-driven knot selection for constructing biharmonic B-splines on manifold triangle meshes. We develop algorithms for spline evaluation, data interpolation and hierarchical data decomposition. Our results demonstrate that biharmonic B-splines, as a new type of spline functions with theoretic and application appeal, afford progressive update of fully irregular knots, free of singularity, without the need of explicit parameterization, making it ideal for a host of graphics tasks on manifolds.

Superpixels are perceptually meaningful atomic regions that can effectively capture image features. Among various methods for computing uniform superpixels, simple linear iterative clustering (SLIC) is popular due to its simplicity and high performance. In this paper, we extend SLIC to compute content-sensitive superpixels, i.e., small superpixels in content-dense regions (e.g., with high intensity or color variation) and large superpixels in content-sparse regions. Rather than the conventional SLIC method that clusters pixels in ℝ5, we map the image I to a 2-dimensional manifold M ⊂ ℝ5, whose area elements are a good measure of the content density in I. We propose an efficient method to compute restricted centroidal Voronoi tessellation (RCVT) - a uniform tessellation - on M, which induces the content-sensitive superpixels in I. Unlike other algorithms that characterize content-sensitivity by geodesic distances, manifold SLIC tackles the problem by measuring areas of Voronoi cells on M, which can be computed at a very low cost. As a result, it runs 10 times faster than the state-of-the-art content-sensitive superpixels algorithm. We evaluate manifold SLIC and seven representative methods on the BSDS500 benchmark and observe that our method outperforms the existing methods.

We propose a new method for robust learning Laplacian matrices from observed smooth graph signals in the presence of both Gaussian noise and random-valued impulse noise (i.e., outliers). Using the recently developed factor analysis model for representing smooth graph signals in [1], we formulate our learning process as a constrained optimization problem, and adopt the £i-norm for measuring the data fidelity in order to improve robustness. Computational results on three types of synthetic graphs demonstrate that the proposed method outperforms the state-of-the-art methods in terms of commonly used information retrieval metrics, such as F-measure, precision, recall and normalized mutual information. In particular, we observed that F-measure is improved by up to 16%.

In this paper, we propose a new data-driven transform, called sparse two-dimensional singular value decomposition (S2DSVD). By leveraging the advantages of discrete cosine transform and the conventional 2D SVD, we decompose a set of matrices into transform coefficient matrices with sparse and orthogonal basis functions. Such sparsity characteristic can significantly reduce their overhead, hence being beneficial to data compression. We formulate S2DSVD as a constrained optimization problem and solve it via alternative iteration. We demonstrate the efficacy of S2DSVD on image and video datasets, and observe that it can produce results with error comparable to 2D SVD whereas its space complexity is significantly smaller than 2D SVD.

We present a delta DLP 3D printer with large size in this paper. Compared with traditional DLP 3D printers that use a low-cost off-the-shelf consumer projector and a single vertical carriage, the platform of our delta DLP 3D printer can also move horizontally in the plane. We show that this structure allows the printer to have a larger printing area than the projection area of a projector. Our system can print 3D models much larger than traditional DLP 3D printers. The major challenge to realize delta 3D printing with large size comes from how to partition an arbitrary planar polygonal shape (possibly with holes or multiple disjoint polygons) into a minimum number of rectangles with fixed size, which is NP-hard. We propose a simple yet efficient approximation algorithm to solve this problem. The time complexity of our algorithm is O(n3log n), where n is the number of edges in the polygonal shape. A physical prototype system is built and several large 3D models with complex geometric structures have been printed as examples to demonstrate the effectiveness of our approach.

This paper presents an efficient data-driven approach to track fingertip and detect finger tapping for virtual piano using an RGB-D camera. We collect 7200 depth images covering the most common finger articulation for playing piano, and train a random regression forest using depth context features of randomly sampled pixels in training images. In the online tracking stage, we firstly segment the hand from the plane in contact by fusing the information from both color and depth images. Then we use the trained random forest to estimate the 3D position of fingertips and wrist in each frame, and predict finger tapping based on the estimated fingertip motion. Finally, we build a kinematic chain and recover the articulation parameters for each finger. In contrast to the existing hand tracking algorithms that often require hands are in the air and cannot interact with physical objects, our method is designed for hand interaction with planar objects, which is desired for the virtual piano application. Using our prototype system, users can put their hands on a desk, move them sideways and then tap fingers on the desk, like playing a real piano. Preliminary results show that our method can recognize most of the beginner's piano-playing gestures in realtime for soothing rhythms.

Due to the growing needs of motion capture (mocap) in movie, video games , sports, etc., it is highly desired to compress mocap data for efficient storage and transmission. Unfortunately, the existing compression methods have either high latency or poor compression performance , making them less appealing for time-critical applications and/or network with limited bandwidth . This paper presents two efficient methods to compress mocap data with low latency. The first method processes the data in a frame-by-frame manner so that it is ideal for mocap data streaming. The second one is clip-oriented and provides a flexible trade-off between latency and compression performance . It can achieve higher compression performance while keeping the latency fairly low and controllable. Observing that mocap data exhibits some unique spatial characteristics , we learn an orthogonal transform to reduce the spatial redundancy . We formulate the learning problem as the least square of reconstruction error regularized by orthogonality and sparsity , and solve it via alternating iteration. We also adopt a predictive coding and temporal DCT for temporal decorrelation in the frame- and clip-oriented methods, respectively. Experimental results show that the proposed methods can produce higher compression performance at lower computational cost and latency than the state-of-the-art methods. Moreover, our methods are general and applicable to various types of mocap data.

This paper presents an automatic method for computing an anisotropic 2D shape distribution on an arbitrary 2-manifold mesh. Our method allows the user to specify the direction as well as the density of the distribution. Using a pre-computed lookup table, our method can efficiently detect collision among the shapes to be distributed on the 3D mesh. In contrast to existing approaches, which usually assume the 2D objects are isotropic and have simple geometry, our method works for complex 2D objects and can guarantee the distribution is conflict-free, which is a critical constraint in many applications. It is able to compute multi-class shape distributions in parallel. Our method does not require global parameterization of the input 3D mesh. Instead, it computes local parameterizations on the fly using geodesic polar coordinates. Thanks to a recent breakthrough in geodesic computation, the local parameterization can be computed at low cost. As a result, our method can be applied to models with complicated geometry and topology. Experimental results on a wide range of 3D models and 2D anisotropic shapes demonstrate the good performance and effectiveness of our method.

Computing centroidal Voronoi tessellations (CVT) has many applications in computer graphics. The existing methods, such as the Lloyd algorithm and the quasi-Newton solver, are efficient and easy to implement; however, they compute only the local optimal solutions due to the highly non-linear nature of the CVT energy. This paper presents a novel method, called manifold differential evolution (MDE), for computing globally optimal geodesic CVT energy on triangle meshes. Formulating the mutation operator using discrete geodesics, MDE naturally extends the powerful differential evolution framework from Euclidean spaces to manifold domains. Under mild assumptions, we show that MDE has a provable probabilistic convergence to the global optimum. Experiments on a wide range of 3D models show that MDE consistently out-performs the existing methods by producing results with lower energy. Thanks to its intrinsic and global nature, MDE is insensitive to initialization and mesh tessellation. Moreover, it is able to handle multiply-connected Voronoi cells, which are challenging to the existing geodesic CVT methods.

This paper presents a simple yet effective algorithm for compressing human motion capture (mocap) data. With a reordering-based discrete wavelet transform and the standard discrete cosine transform, our method can effectively reduce the spatial and temporal correlation in mocap data. Our method is conceptually simple and easy to implement. Experimental results show that our method can achieve better compression performance with lower latency, compared to the state-of-the-art methods.

In this paper, we propose a simple-yet-effective method for isotropic meshing relying on Euclidean distance transformation based centroidal Voronoi tessellation (CVT). Our approach improves the performance and robustness of computing CVT on curved domains while simultaneously providing high-quality output meshes. While conventional extrinsic methods compute CVTs in the entire volume bounded by the input model, we restrict the computation to a 3D shell of user-controlled thickness. Taking voxels which contain surface samples as sites, we compute the exact Euclidean distance transform on the GPU. Our algorithm is parallel and memory-efficient, and can construct the shell space for resolutions up to 2048 3 at interactive speed. The 3D centroidal Voronoi tessellation and restricted Voronoi diagrams are also computed efficiently on the GPU. Since the shell space can bridge holes and gaps smaller than a certain tolerance, and tolerate non-manifold edges and degenerate triangles, our algorithm can handle models with such defects, which typically cause conventional remeshing methods to fail. Our method can process implicit surfaces, polyhedral surfaces, and point clouds in a unified framework. Computational results show that our GPU-based isotropic meshing algorithm produces results comparable to state-of- the-art techniques, but is significantly faster than conventional CPU-based implementations.

Protein-protein interfaces defined through atomic contact or solvent accessibility change are widely adopted in structural biology studies. But, these definitions cannot precisely capture energetically important regions at protein interfaces. The burial depth of an atom in a protein is related to the atom's energy. This work investigates how closely the change in burial level of an atom/residue upon complexation is related to the binding. Burial level change is different from burial level itself. An atom deeply buried in a monomer with a high burial level may not change its burial level after an interaction and it may have little burial level change. We hypothesize that an interface is a region of residues all undergoing burial level changes after interaction. By this definition, an interface can be decomposed into an onion-like structure according to the burial level change extent. We found that our defined interfaces cover energetically important residues more precisely, and that the binding free energy of an interface is distributed progressively from the outermost layer to the core. These observations are used to predict binding hot spots. Our approach's F-measure performance on a benchmark dataset of alanine mutagenesis residues is much superior or similar to those by complicated energy modeling or machine learning approaches.

This paper presents keyframe-based geometry video (KGV), a novel framework for compressing 3-D human motion data by using geometry videos. Given a motion data encoded in a geometry video (GV) format, our method extracts the keyframes and produces a reconstruction matrix. Then it applies the video compression technique (e.g., H.264/Advanced Video Coding) to the reordered keyframes, which can significantly reduce the spatial and temporal redundancy in the KGV. We develop a rate distortion-based optimization algorithm to determine the parameters (i.e., the number of keyframes and quantization parameter) leading to optimal performance. Experimental results show that the proposed KGV framework significantly outperforms the existing GV techniques in terms of both the rate distortion performance and visual quality. Besides, the computational cost of the KGV is rather low at the decoder, making it highly desirable for power-constrained devices. Last but not least, our method can be easily extended to progressive compression with heterogeneous communication network.

Delaunay meshes (DM) are a special type of triangle mesh where the local Delaunay condition holds everywhere. We present an efficient algorithm to convert an arbitrary manifold triangle mesh M into a Delaunay mesh. We show that the constructed DM has O ( Kn ) vertices, where n is the number of vertices in M and K is a model-dependent constant. We also develop a novel algorithm to simplify Delaunay meshes, allowing a smooth choice of detail levels. Our methods are conceptually simple, theoretically sound and easy to implement. The DM construction algorithm also scales well due to its O ( nK log K ) time complexity. Delaunay meshes have many favorable geometric and numerical properties. For example, a DM has exactly the same geometry as the input mesh, and it can be encoded by any mesh data structure. Moreover, the empty geodesic circumcircle property implies that the commonly used cotangent Laplace-Beltrami operator has non-negative weights. Therefore, the existing digital geometry processing algorithms can benefit the numerical stability of DM without changing any codes. We observe that DMs can improve the accuracy of the heat method for computing geodesic distances. Also, popular parameterization techniques, such as discrete harmonic mapping, produce more stable results on the DMs than on the input meshes.

Human motion capture (mocap) is a widely used technique for digitalizing human movements. With growing usage, compressing mocap data has received increasing attention, since compact data size enables efficient storage and transmission. Our analysis shows that mocap data have some unique characteristics that distinguish themselves from images and videos. Therefore, directly borrowing image or video compression techniques, such as discrete cosine transform, does not work well. In this paper, we propose a novel mocap-tailored transform coding algorithm that takes advantage of these features. Our algorithm segments the input mocap sequences into clips, which are represented in 2D matrices. Then it computes a set of data-dependent orthogonal bases to transform the matrices to frequency domain, in which the transform coefficients have significantly less dependency. Finally, the compression is obtained by entropy coding of the quantized coefficients and the bases. Our method has low computational cost and can be easily extended to compress mocap databases. It also requires neither training nor complicated parameter setting. Experimental results demonstrate that the proposed scheme significantly outperforms state-of-the-art algorithms in terms of compression performance and speed.

Computing geodesic distances on triangle meshes is a fundamental problem in computational geometry and computer graphics. To date, two notable classes of algorithms, the Mitchell-Mount-Papadimitriou (MMP) algorithm and the Chen-Han (CH) algorithm, have been proposed. Although these algorithms can compute exact geodesic distances if numerical computation is exact, they are computationally expensive, which diminishes their usefulness for large-scale models and/or time-critical applications. In this paper, we propose the fast wavefront propagation (FWP) framework for improving the performance of both the MMP and CH algorithms. Unlike the original algorithms that propagate only a single window (a data structure locally encodes geodesic information) at each iteration, our method organizes windows with a bucket data structure so that it can process a large number of windows simultaneously without compromising wavefront quality. Thanks to its macro nature, the FWP method is less sensitive to mesh triangulation than the MMP and CH algorithms. We evaluate our FWP-based MMP and CH algorithms on a wide range of large-scale real-world models. Computational results show that our method can improve the speed by a factor of 3-10.

Although the problem of k-area coverage has been intensively investigated for dense wireless sensor networks (WSNs), how to arrive at a k-coverage sensor deployment that optimizes certain objectives in relatively sparse WSNs still faces both theoretical and practical difficulties. Moreover, only a handful of centralized algorithms have been proposed to elevate 2-D area coverage to 3-D surface coverage. In this paper, we present a practical algorithm, i.e., the Autonomous dePlOyment for Load baLancing k-surface cOverage (APOLLO), to move sensor nodes toward k-surface coverage, aiming at minimizing the maximum sensing range required by the nodes. APOLLO enables purely autonomous node deployment as it only entails localized computations. We prove the termination of the algorithm and the (local) optimality of the output. We also show that our optimization objective is closely related to other frequently considered objectives for 2-D area coverage. Therefore, our practical algorithm design also contributes to the theoretical understanding of the 2-D k-area coverage problem. Finally, we use extensive simulation results to both confirm our theoretical claims and demonstrate the efficacy of APOLLO.

In this paper, we propose a practical, elegant and effective scheme for compact mocap data representation. Guided by our analysis of the unique properties of mocap data, the input mocap sequence is optimally segmented into a set of subsequences. Then, we project the subsequences onto a pair of computational orthogonal matrices to explore strong low-rank characteristic within and among the subsequences. The experimental results show that the proposed scheme is much more effective for reducing the data size, compared with the existing techniques.

Motion capture (mocap) technology is widely used in various applications. The acquired mocap data usually has missing data due to occlusions or ambiguities. Therefore, restoring the missing entries of the mocap data is a fundamental issue in mocap data analysis. Based on jointly low-rank matrix completion, this paper presents a practical and highly efficient algorithm for restoring the missing mocap data. Taking advantage of the unique properties of mocap data (i.e, strong correlation among the data), we represent the corrupted data as two types of matrices, where both the local and global characteristics are taken into consideration. Then we formulate the problem as a convex optimization problem, where the missing data is recovered by solving the two matrices using the alternating direction method of multipliers algorithm. Experimental results demonstrate that the proposed scheme significantly outperforms the state-of-the-art algorithms in terms of both the quality and computational cost.

Compression of 3D time-varying meshes (TVMs) plays a critical role in the storage and transmission of 3D contents. In this paper, we propose a novel framework for compressing 3D TVMs. In our framework, 3D TVMs are parameterized and represented by the geometry videos (GVs) through polycube parameterization. By considering the low-rank characteristic of dynamic meshes, we decompose GVs into a sequence with small frames namely EigenGV and the computed reconstruction matrix. We further apply 2D video encoder to eliminate spatial and temporal redundancy among the EigenGV. Experimental results demonstrate that the proposed method significantly outperforms the existing compression schemes in terms of both the rate distortion performance and visual quality. Besides, the proposed method naturally achieves progressive form, which is very suitable for error prone channel transmission.

Whereas a few physical layer techniques have been proposed to locate a signal source indoors, they all deem multipath a "curse" and hence take great efforts to cope with it. Consequently, each sensor only obtains the information about the direct path; this necessitates a networked sensing system (hence higher system complexity and deployment cost) with at least three sensors to actually locate a source.

While 3D line drawing techniques have become well established in the past decade, most are only suitable for polygonal meshes. This paper presents splatting lines, a unified framework for generating line drawings from various types of 3D models, including point clouds, volumes, and polygonal meshes. In contrast to the existing mesh-based approaches, our method takes a densely sampled point cloud as input. It renders two diffuse shading images using splatting with different parameters and then generates line drawings by subtracting these images. Our point-based approach can be easily extended to polygonal meshes and volumes by an efficient (iso-)surface sampling method. Our method is highly efficient and it does not require any pre-computation. It is also more robust to the mesh tessellation than existing mesh-based techniques. Experimental results indicate the advantages of our method in terms of both performance and quality.

Abstract This paper studies the Voronoi diagrams on 2‐manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point‐source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line‐segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n‐face mesh with m generators, where N = max{m, n}. Computational results on real‐world models demonstrate the efficiency of our algorithm.

Auto face annotation, which aims to detect human faces from a facial image and assign them proper human names, is a fundamental research problem and beneficial to many real-world applications. In this work, we address this problem by investigating a retrieval-based annotation scheme of mining massive web facial images that are freely available over the Internet. In particular, given a facial image, we first retrieve the top $(n)$ similar instances from a large-scale web facial image database using content-based image retrieval techniques, and then use their labels for auto annotation. Such a scheme has two major challenges: 1) how to retrieve the similar facial images that truly match the query, and 2) how to exploit the noisy labels of the top similar facial images, which may be incorrect or incomplete due to the nature of web images. In this paper, we propose an effective Weak Label Regularized Local Coordinate Coding (WLRLCC) technique, which exploits the principle of local coordinate coding by learning sparse features, and employs the idea of graph-based weak label regularization to enhance the weak labels of the similar facial images. An efficient optimization algorithm is proposed to solve the WLRLCC problem. Moreover, an effective sparse reconstruction scheme is developed to perform the face annotation task. We conduct extensive empirical studies on several web facial image databases to evaluate the proposed WLRLCC algorithm from different aspects. The experimental results validate its efficacy. We share the two constructed databases "WDB" (714,454 images of 6,025 people) and "ADB" (126,070 images of 1,200 people) with the public. To further improve the efficiency and scalability, we also propose an offline approximation scheme (AWLRLCC) which generally maintains comparable results but significantly reduces the annotation time.

Motion capture (mocap) technology is widely used in movie and game industries. Compact representation of the mocap data is critical to efficient storage and transmission. In this letter, we propose a novel tensor decomposition based scheme for compact and progressive representation of the mocap data. Our method segments and stacks the mocap sequence locally, and generates a 3rd-order tensor, which has strong correlation within and across slices of the tensor. Then, our method iteratively applies tensor decomposition in a multi-layer structure to explore the correlation characteristic. Experimental results demonstrate that the proposed scheme significantly outperforms existing algorithms in terms of scalability and storage requirement.

The rapid recent development of 3-DTV technology has led to an increase in studies on mesh-based 3-D scene representation. Compressing 3-D time-varying meshes is critical for the storage and transmission of 3-D contents. This paper proposes a highly efficient framework for compressing time-varying 3-D facial expressions. We use the near-isometric property of human facial expressions to parameterize the 3-D dynamic faces into an expression-invariant 2-D canonical domain that will naturally generate 2-D geometry videos (GVs). Considering the intrinsic properties of GVs, we apply low-rank and sparse matrix decomposition (LRSMD) separately to three dimensions of GVs (namely, \(X, Y,\) and \(Z\) ). Based on our high precision rate and distortion models for GVs, we further compress the components from LRSMD using a video encoder in which bitrates of all components are assigned optimally according to the target bitrate. Experimental results show that the proposed scheme can significantly improve compression performance in terms of rate-distortion performance and visual quality compared with the state-of-the-art algorithms.

This paper investigates a framework of search-based face annotation (SBFA) by mining weakly labeled facial images that are freely available on the World Wide Web (WWW). One challenging problem for search-based face annotation scheme is how to effectively perform annotation by exploiting the list of most similar facial images and their weak labels that are often noisy and incomplete. To tackle this problem, we propose an effective unsupervised label refinement (ULR) approach for refining the labels of web facial images using machine learning techniques. We formulate the learning problem as a convex optimization and develop effective optimization algorithms to solve the large-scale learning task efficiently. To further speed up the proposed scheme, we also propose a clustering-based approximation algorithm which can improve the scalability considerably. We have conducted an extensive set of empirical studies on a large-scale web facial image testbed, in which encouraging results showed that the proposed ULR algorithms can significantly boost the performance of the promising SBFA scheme.

In many graphics applications, the computation of exact geodesic distance is very important. However, the high computational cost of existing geodesic algorithms means that they are not practical for large-scale models or time-critical applications. To tackle this challenge, we propose the Parallel Chen-Han (or PCH) algorithm, which extends the classic Chen-Han (CH) discrete geodesic algorithm to the parallel setting. The original CH algorithm and its variant both lack a parallel solution because the windows (a key data structure that carries the shortest distance in the wavefront propagation) are maintained in a strict order or a tightly coupled manner, which means that only one window is processed at a time. We propose dividing the CH's sequential algorithm into four phases, window selection, window propagation, data organization, and events processing so that there is no data dependence or conflicts in each phase and the operations within each phase can be carried out in parallel. The proposed PCH algorithm is able to propagate a large number of windows simultaneously and independently. We also adopt a simple yet effective strategy to control the total number of windows. We implement the PCH algorithm on modern GPUs (such as Nvidia GTX 580) and analyze the performance in detail. The performance improvement (compared to the sequential algorithms) is highly consistent with GPU double-precision performance (GFLOPS). Extensive experiments on real-world models demonstrate an order of magnitude improvement in execution time compared to the state-of-the-art.

Many applications of wireless sensor networks involve monitoring a time-variant event (e.g., radiation pollution in the air). In such applications, fast boundary detection is a crucial function, as it allows us to track the event variation in a timely fashion. However, the problem becomes very challenging as it demands a highly efficient algorithm to cope with the dynamics introduced by the evolving event. Moreover, as many physical events occupy volumes rather than surfaces (e.g., pollution again), the algorithm has to work for 3-D cases. Finally, as boundaries of a 3-D network can be complicated 2-manifolds, many network functionalities (e.g., routing) may fail in the face of such boundaries. To this end, we propose Localized Boundary Detection and Parametrization (LBDP) to tackle these challenges. The first component of LBDP is UNiform Fast On-Line boundary Detection (UNFOLD). It applies an inversion to node coordinates such that a “notched” surface is “unfolded” into a convex one, which in turn reduces boundary detection to a localized convexity test. We prove the correctness and efficiency of UNFOLD; we also use simulations and implementations to evaluate its performance, which demonstrates that UNFOLD is two orders of magnitude more time- and energy-efficient than the most up-to-date proposal. Another component of LBDP is Localized Boundary Sphericalization (LBS). Through purely localized operations, LBS maps an arbitrary genus-0 boundary to a unit sphere, which in turn supports functionalities such as distinguishing interboundaries from external ones and distributed coordinations on a boundary. We implement LBS in TOSSIM and use simulations to show its effectiveness.

Architectural sketching and massing are used by designers to analyze and explore the design space of buildings. This paper describes a novel multi-touch interface for fast architectural sketching and massing of tall buildings. It incorporates a family of multi-touch gestures, enabling one to quickly sketch the 2D contour of a base floor plan and extrude it to model a building with multi-floor structures. Further, it provides a set of gestures to users: select and edit a range of floors; scale contours of a building; copy, paste, and rotate a building, i.e., create a twisted structure; edit profile curves of a building's profile; and collapse and remove a selected range of floors. The multi-touch system also allows users to apply textures or geometric facades to the building, and to compare different designs side-by-side. To guide the design process, we describe interactions with a domain expert, a practicing architect. The final interface is evaluated by architects and students in an architecture Dept., which demonstrates that the system allows rapid conceptual design and massing of novel multi-story building structures.

Motion capture is widely used in sports, entertainment and medical applications. An important issue is to recover motion capture data that has been corrupted by noise and missing data entries during acquisition. In this paper, we propose a new method to recover corrupted motion capture data through trajectory-based sparse representation. The data is firstly represented as trajectories with fixed length and high correlation. Then, based on the sparse representation theory, the original trajectories can be recovered by solving the sparse representation of the incomplete trajectories through the OMP algorithm using a dictionary learned by K-SVD. Experimental results show that the proposed algorithm achieves much better performance, especially when significant portions of data is missing, than the existing algorithms.

While the increasing scales of the recent WSN deployments keep pushing a higher demand on the network throughput, the 16 orthogonal channels of the ZigBee radios are intensively explored to improve the parallelism of the transmissions. However, the interferences generated by other ISM band wireless devices (e.g., WiFi) have severely limited the usable channels for WSNs. Such a situation raises a need for a spectrum utilizing method more efficient than the conventional multi-channel access. To this end, we propose to shift the paradigm from discrete channel allocation to continuous frequency allocation in this paper. Motivated by our experiments showing the flexible and efficient use of spectrum through continuously tuning channel center frequencies with respect to link distances, we present FAVOR (Frequency Allocation for Versatile Occupancy of spectRum) to allocate proper center frequencies in a continuous spectrum (hence potentially overlapped channels, rather than discrete orthogonal channels) to nodes or links. To find an optimal frequency allocation, FAVOR creatively combines location and frequency into one space and thus transforms the frequency allocation problem into a spatial tessellation problem. This allows FAVOR to innovatively extend a spatial tessellation technique for the purpose of frequency allocation. We implement FAVOR in MicaZ platforms, and our extensive experiments with different network settings strongly demonstrate the superiority of FAVOR over existing approaches.

Line drawings are a popular shape depiction technique due to its capability to express meaningful information by ignoring less important or distracting details. Many computer generated line drawing algorithms have been proposed in the past decade, such as suggestive contours, ridge-valley lines, apparent ridges, photic extremum lines, demarcating curves, Laplacian lines, just name a few.

This paper presents Texture Brush, an interactive interface for texturing 3D surfaces. We extend the conventional exponential map to a more general setting, in which the generator can be an arbitrary curve. Based on our extended exponential map, we develop a local parameterization method which naturally supports anisotropic texture mapping. With Texture Brush, the user can easily specify such local parameterization with a free-form stroke on the surface. We also propose a set of intuitive operations which are mainly based on 3D painting metaphor, including texture painting, texture cloning, texture animation design, and texture editing. Compared to the existing surface texturing techniques, our method enables a smoother and more natural work flow so that the user can focus on the design task itself without switching back and forth among different tools or stages. The encouraging experimental results and positive evaluation by artists demonstrate the efficacy of our Texture Brush for interactive texture mapping.

This paper presents a simple yet effective algorithm to improve an arbitrary Poisson disk sampling in R2 and R3 to reach the maximal property, i.e., no more Poisson disk can be inserted. Taking a non-maximal Poisson disk sampling as input, our algorithm efficiently detects the regions allowing additional samples and then generates Poisson disks in these regions. The key idea is to convert the complicated plane or space searching problem into a simple searching on circles or spheres, which is one dimensional lower than the original sampling domain. Our algorithm is memory efficient, fully parallel and highly fast by using modern graphics card.

Automated face annotation aims to automatically detect human faces from a photo and further name the faces with the corresponding human names. In this paper, we tackle this open problem by investigating a search-based face annotation (SBFA) paradigm for mining large amounts of web facial images freely available on the WWW. Given a query facial image for annotation, the idea of SBFA is to first search for top-n similar facial images from a web facial image database and then exploit these top-ranked similar facial images and their weak labels for naming the query facial image. To fully mine those information, this paper proposes a novel framework of Learning to Name Faces (L2NF) -- a unified multimodal learning approach for search-based face annotation, which consists of the following major components: (i) we enhance the weak labels of top-ranked similar images by exploiting the "label smoothness" assumption; (ii) we construct the multimodal representations of a facial image by extracting different types of features; (iii) we optimize the distance measure for each type of features using distance metric learning techniques; and finally (iv) we learn the optimal combination of multiple modalities for annotation through a learning to rank scheme. We conduct a set of extensive empirical studies on two real-world facial image databases, in which encouraging results show that the proposed algorithms significantly boost the naming accuracy of search-based face annotation task.

Compression of mesh-based 3-D models has been an important issue, which ensures efficient storage and transmission. In this paper, we present a very effective compression scheme specifically for expression variation 3-D face models. Firstly, 3-D models are mapped into 2-D parametric domain and corresponded by expression-invariant parameterizaton, leading to 2-D image format representation namely geometry images, which simplifies the 3-D model compression into 2-D image compression. Then, sparse representation with learned dictionaries via K-SVD is applied to each patch from sliced GI so that only few coefficients and their indices are needed to be encoded, leading to low datasize. Experimental results demonstrate that the proposed scheme provides significant improvement in terms of compression performance, especially at low bitrate, compared with existing algorithms.

BACKGROUND: Human triosephosphate isomerase (HsTIM) deficiency is a genetic disease caused often by the pathogenic mutation E104D. This mutation, located at the side of an abnormally large cluster of water in the inter-subunit interface, reduces the thermostability of the enzyme. Why and how these water molecules are directly related to the excessive thermolability of the mutant have not been investigated in structural biology. RESULTS: This work compares the structure of the E104D mutant with its wild type counterparts. It is found that the water topology in the dimer interface of HsTIM is atypical, having a "wet-core-dry-rim" distribution with 16 water molecules tightly packed in a small deep region surrounded by 22 residues including GLU104. These water molecules are co-conserved with their surrounding residues in non-archaeal TIMs (dimers) but not conserved across archaeal TIMs (tetramers), indicating their importance in preserving the overall quaternary structure. As the structural permutation induced by the mutation is not significant, we hypothesize that the excessive thermolability of the E104D mutant is attributed to the easy propagation of atoms' flexibility from the surface into the core via the large cluster of water. It is indeed found that the B factor increment in the wet region is higher than other regions, and, more importantly, the B factor increment in the wet region is maintained in the deeply buried core. Molecular dynamics simulations revealed that for the mutant structure at normal temperature, a clear increase of the root-mean-square deviation is observed for the wet region contacting with the large cluster of interfacial water. Such increase is not observed for other interfacial regions or the whole protein. This clearly suggests that, in the E104D mutant, the large water cluster is responsible for the subunit interface flexibility and overall thermolability, and it ultimately leads to the deficiency of this enzyme. CONCLUSIONS: Our study reveals that a large cluster of water buried in protein interfaces is fragile and high-maintenance, closely related to the structure, function and evolution of the whole protein.

With the extensive applications of 3-D multimedia technology, 3-D content compression has been an important issue, which ensures its smooth transmission on the network with constrained bandwidth. In this letter, we propose a new compression framework for dynamic 3-D facial expressions. Taking advantage of the near-isometric property of human facial expressions, we parameterize the dynamic 3-D faces into an expression-invariant canonical domain, which naturally generates 2-D geometry videos and allows us to apply the well-studied video compression techniques. Due to the difference from natural videos, each dimension (i.e., X, Y and Z, respectively) of the geometry video is regarded as a video sequence and encoded separately. Meanwhile, a model-based joint bit allocation scheme is designed to allocate reasonable bitrate to each dimension by detailed analysis of rate-distortion model for geometry videos, to obtain optimal results under given target bitrate. Experimental results show that up to 25% improvement in terms of bitrate reduction can be achieved, compared to existing algorithms.

This paper presents the Saddle Vertex Graph (SVG), a novel solution to the discrete geodesic problem. The SVG is a sparse undirected graph that encodes complete geodesic distance information: a geodesic path on the mesh is equivalent to a shortest path on the SVG, which can be solved efficiently using the shortest path algorithm (e.g., Dijkstra algorithm). The SVG method solves the discrete geodesic problem from a local perspective. We have observed that the polyhedral surface has some interesting and unique properties, such as the fact that the discrete geodesic exhibits a strong local structure, which is not available on the smooth surfaces. The richer the details and complicated geometry of the mesh, the stronger such local structure will be. Taking advantage of the local nature, the SVG algorithm breaks down the discrete geodesic problem into significantly smaller sub-problems, and elegantly enables information reuse. It does not require any numerical solver, and is numerically stable and insensitive to the mesh resolution and tessellation. Users can intuitively specify a model-independent parameter K , which effectively balances the SVG complexity and the accuracy of the computed geodesic distance. More importantly, the computed distance is guaranteed to be a metric. The experimental results on real-world models demonstrate significant improvement to the existing approximate geodesic methods in terms of both performance and accuracy.

In this paper, we propose a sketch-based editable polycube mapping method that, given a general mesh and a simple polycube that coarsely resembles the shape of the object, plus sketched features indicating relevant correspondences between the two, provides a uniform, regular, and user-controllable quads-only mesh that can be used as a basis structure for subdivision. Large scale models with complex geometry and topology can be processed efficiently with simple, intuitive operations. We show that the simple, intuitive nature of the polycube map is a substantial advantage from the point of view of the interface by demonstrating a series of applications, including kit-basing, shape morphing, painting over the parameterization domain, and GPU-friendly tessellated subdivision displacement, where the user is also able to control the number of patches in the base mesh by the construction of the base polycube.

Poisson disk sampling has excellent spatial and spectral properties, and plays an important role in a variety of visual computing. Although many promising algorithms have been proposed for multidimensional sampling in euclidean space, very few studies have been reported with regard to the problem of generating Poisson disks on surfaces due to the complicated nature of the surface. This paper presents an intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces. In sharp contrast to the conventional parallel approaches, our method neither partitions the given surface into small patches nor uses any spatial data structure to maintain the voids in the sampling domain. Instead, our approach assigns each sample candidate a random and unique priority that is unbiased with regard to the distribution. Hence, multiple threads can process the candidates simultaneously and resolve conflicts by checking the given priority values. Our algorithm guarantees that the generated Poisson disks are uniformly and randomly distributed without bias. It is worth noting that our method is intrinsic and independent of the embedding space. This intrinsic feature allows us to generate Poisson disk patterns on arbitrary surfaces in IR(n). To our knowledge, this is the first intrinsic, parallel, and accurate algorithm for surface Poisson disk sampling. Furthermore, by manipulating the spatially varying density function, we can obtain adaptive sampling easily.

Auto face annotation plays an important role in many real-world multimedia information and knowledge management systems. Recently there is a surge of research interests in mining weakly-labeled facial images on the internet to tackle this long-standing research challenge in computer vision and image understanding. In this paper, we present a novel unified learning framework for face annotation by mining weakly labeled web facial images through interdisciplinary efforts of combining sparse feature representation, content-based image retrieval, transductive learning and inductive learning techniques. In particular, we first introduce a new search-based face annotation paradigm using transductive learning, and then propose an effective inductive learning scheme for training classification-based annotators from weakly labeled facial images, and finally unify both transductive and inductive learning approaches to maximize the learning efficacy. We conduct extensive experiments on a real-world web facial image database, in which encouraging results show that the proposed unified learning scheme outperforms the state-of-the-art approaches.

Although the problem of k-area coverage has been intensively investigated for dense wireless sensor networks (WSNs), how to arrive at a k-coverage sensor deployment that optimizes certain objectives in relatively sparse WSNs still faces both theoretical and practical difficulties. In this paper, we present a practical algorithm LAACAD (Load balancing k-Area Coverage through Autonomous Deployment) to move sensor nodes toward k-area coverage, aiming at minimizing the maximum sensing range required by the nodes. LAACAD enables purely autonomous node deployment as it only entails localized computations. We prove the convergence of the algorithm, as well as the (local) optimality of the output. We also show that our optimization objective is closely related to other frequently considered objectives. Therefore, our practical algorithm design also contributes to the theoretical understanding of the k-area coverage problem. Finally, we use extensive simulation results both to confirm our theoretical claims and to demonstrate the efficacy of LAACAD.

With the development of ever-expanding wireless sensor networks (WSNs) that are meant to connect physical worlds with human societies, gathering sensory data at a single point is becoming less and less practical. Unfortunately, the alternative in-network data management schemes may fail to operate in the face of communication voids (or holes) in WSNs (especially 3D WSNs). In response to this challenge, we propose harmonic quorum systems (HQSs) as a lightweight data management system for 2D/3D WSNs. HQSs innovate in exploiting a few scalar fields (constructed using pure localized algorithms) to guide data accesses. This liberates HQSs from depending on any routing mechanisms or location services, hence making HQSs efficient and robust against anomalies in WSN topologies. We implement HQSs in TinyOS, and we perform intensive simulations using TOSSIM to validate the performance of HQSs.

Computing discrete geodesics on polyhedral surfaces plays an important role in computer graphics. In contrast to the well-studied "single-source, all-destination" discrete geodesic problem, little progress has been reported to the all-pairs geodesic, i.e., computing the geodesic distance between arbitrary two points on the surface. To our knowledge, the existing all-pairs geodesic algorithms have very high computational cost, thus, can not be applied to real-world models, which usually contain thousands of vertices. In this paper, we propose an efficient algorithm to approximate the all-pairs geodesic on triangular meshes. The pre-processing step takes O(mn2 log n) time for the input mesh with n vertices and m samples, where m (≪ n) is specified by the user, usually between a few hundred and several thousand. In the query step, our algorithm can compute the approximate geodesic distance between arbitrary pair of points (not necessarily mesh vertices) in O(1) time. Furthermore, the geodesic path and the geodesic distance field can be approximated in linear time. Both theoretical analysis and experimental results on real-world models demonstrate that our algorithm is efficient and accurate. We demonstrate the efficacy of our algorithm on the interactive texture mapping by using discrete exponential map.

BACKGROUND: Water is an integral part of protein complexes. It shapes protein binding sites by filling cavities and it bridges local contacts by hydrogen bonds. However, water molecules are usually not included in protein interface models in the past, and few distribution profiles of water molecules in protein binding interfaces are known. RESULTS: In this work, we use a tripartite protein-water-protein interface model and a nested-ring atom re-organization method to detect hydration trends and patterns from an interface data set which involves immobilized interfacial water molecules. This data set consists of 206 obligate interfaces, 160 non-obligate interfaces, and 522 crystal packing contacts. The two types of biological interfaces are found to be drier than the crystal packing interfaces in our data, agreeable to a hydration pattern reported earlier although the previous definition of immobilized water is pure distance-based. The biological interfaces in our data set are also found to be subject to stronger water exclusion in their formation. To study the overall hydration trend in protein binding interfaces, atoms at the same burial level in each tripartite protein-water-protein interface are organized into a ring. The rings of an interface are then ordered with the core atoms placed at the middle of the structure to form a nested-ring topology. We find that water molecules on the rings of an interface are generally configured in a dry-core-wet-rim pattern with a progressive level-wise solvation towards to the rim of the interface. This solvation trend becomes even sharper when counterexamples are separated. CONCLUSIONS: Immobilized water molecules are regularly organized in protein binding interfaces and they should be carefully considered in the studies of protein hydration mechanisms.

In this paper, we present a novel geometry video (GV) framework to model and compress 3-D facial expressions. GV bridges the gap of 3-D motion data and 2-D video, and provides a natural way to apply the well-studied video processing techniques to motion data processing. Our framework includes a set of algorithms to construct GVs, such as hole filling, geodesic-based face segmentation, expression-invariant parameterization (EIP), and GV compression. Our EIP algorithm can guarantee the exact correspondence of the salient features (eyes, mouth, and nose) in different frames, which leads to GVs with better spatial and temporal coherence than that of the conventional parameterization methods. By taking advantage of this feature, we also propose a new H.264/AVC-based progressive directional prediction scheme, which can provide further 10%-16% bitrate reductions compared to the original H.264/AVC applied for GV compression while maintaining good video quality. Our experimental results on real-world datasets demonstrate that GV is very effective for modeling the high-resolution 3-D expression data, thus providing an attractive way in expression information processing for gaming and movie industry.

Character pose design is one of the most fundamental processes in computer graphics authoring. Although there are many research efforts in this field, most existing design tools consider only character body structure, rather than its interaction with the environment. This paper presents an intuitive sketching interface that allows the user to interactively place a 3D human character in a sitting position on a chair. Within our framework, the user sketches the target pose as a 2D stick figure and attaches the selected joints to the environment (e.g., the feet on the ground) with a pin tool. As reconstructing the 3D pose from a 2D stick figure is an ill-posed problem due to many possible solutions, the key idea in our paper is to reduce solution space by considering the interaction between the character and environment and adding physics constraints, such as balance and collision. Further, we formulated this reconstruction into a nonlinear optimization problem and solved it via the genetic algorithm (GA) and the quasi-Newton solver. With the GPU implementation, our system is able to generate the physically correct and visually pleasing pose at an interactive speed. The promising experimental results and user study demonstrates the efficacy of our method.

Closed geodesics, or geodesic loops, are crucial to the study of differential topology and differential geometry. Although the existence and properties of closed geodesics on smooth surfaces have been widely studied in mathematics community, relatively little progress has been made on how to compute them on polygonal surfaces. Most existing algorithms simply consider the mesh as a graph and so the resultant loops are restricted only on mesh edges, which are far from the actual geodesics. This paper is the first to prove the existence and uniqueness of geodesic loop restricted on a closed face sequence; it contributes also with an efficient algorithm to iteratively evolve an initial closed path on a given mesh into an exact geodesic loop within finite steps. Our proposed algorithm takes only an O(k) space complexity and an O(mk) time complexity (experimentally), where m is the number of vertices in the region bounded by the initial loop and the resultant geodesic loop, and k is the average number of edges in the edge sequences that the evolving loop passes through. In contrast to the existing geodesic curvature flow methods which compute an approximate geodesic loop within a predefined threshold, our method is exact and can apply directly to triangular meshes without needing to solve any differential equation with a numerical solver; it can run at interactive speed, e.g., in the order of milliseconds, for a mesh with around 50K vertices, and hence, significantly outperforms existing algorithms. Actually, our algorithm could run at interactive speed even for larger meshes. Besides the complexity of the input mesh, the geometric shape could also affect the number of evolving steps, i.e., the performance. We motivate our algorithm with an interactive shape segmentation example shown later in the paper.

Diffusion curves are effective 2D vector-graphics primitives, for creating smoothly-shaded drawings with rich colors and unique styles. Conventional drawing systems for diffusion curves often require users to successively layout curve geometry and then specify colors, which is rather tedious for complex drawings. This paper proposes a novel multi-touch sketching interface for efficient design of 2D vector graphics with diffusion curves. In sharp contrast to previous interfaces, we develop a family of multi-touch gestures, allowing users to simultaneously sketch multiple diffusion curves and also to interactively edit and tune curve geometry and colors. Our experiments show that this not only brings novel painting experience to users but also provides a practical and effective tool for vector graphics design, useful for styles like silk painting, Disney cartoon, art poster, and photo-realistic effects. Lastly, we conduct a user study to explore the interface's intuitive and efficient drawing capability with both professional 2D artists and novice users.

This paper proposes novel mechanisms to access sensory data in a distributed fashion in 3D wireless sensor networks. As these networks have their nodes deployed in 3D volumes, we first propose a volume parametrization algorithm to transform irregular volumes into a regular one; it also allows us to extend network protocols from 2D to 3D (which would otherwise be highly non-trivial). Based on this transformation, we propose a new quorum system, 3DQS, to handle distributed data access. The tunability of 3DQS enables it to adapt to different application requirements. We demonstrate the efficacy and efficiency of 3DQS through both analysis and simulations.

When data productions and consumptions are heavily unbalanced and when the origins of data queries are spatially and temporally distributed, the so called in-network data storage paradigm supersedes the conventional data collection paradigm in wireless sensor networks (WSNs). In this paper, we first introduce geometric quorum systems (along with their metrics) to incarnate the idea of in-network data storage. These quorum systems are “geometric” because curves (rather than discrete node sets) are used to form quorums. We then propose GeoQuorum as a new quorum system, for which the quorum forming curves are parameterized. Our proposal significantly expands the quorum design methodology, by endowing a system with a great flexibility to fine-tune itself towards different application requirements. In particular, the tunability allows GeoQuorum to substantially improve the load balancing performance and to remain competitive in energy efficiency. Our simulation results confirm the performance enhancement brought by GeoQuorum.

3D articulated motions are widely used in entertainment, sports, military, and medical applications. Among various techniques for modeling 3D motions, geometry videos (GVs) are a compact representation in that each frame is parameterized to a 2D domain, which captures the 3D geometry (x, y, z) to a pixel (r, g, b) in the image domain. As a result, the widely studied image/video processing techniques can be directly borrowed for 3D motion. This paper presents conformal geometry videos (CGVs), a novel extension of the traditional geometry videos by taking into the consideration of the isometric nature of 3D articulated motions. We prove that the 3D articulated motion can be uniquely (up to rigid motion) represented by (»,H), where » is the conformal factor characterizing the intrinsic property of the 3D motion, and H the mean curvature characterizing the extrinsic feature (i.e., embedding or appearance). Furthermore, the conformal factor » is pose-invariant. Thus, in sharp contrast to the GVs which capture 3D motion by three channels, CGVs take only one channel of mean curvature H and the first frame of the conformal factor », i.e., approximately 1/3 the storage of the GVs. In addition, CGVs have strong spatial and temporal coherence, which favors various well studied video compression techniques. Thus, CGVs can be highly compressed by using the state-of the-art video compression techniques, such as H.264/AVC. Our experimental results on real-world 3D motions show that CGVs are a highly compact representation for 3D articulated motions, i.e., given CGVs and GVs of the same file size, CGVs show much better visual quality than GVs.

This paper investigates a retrieval-based annotation paradigm of mining web facial images for automated face annotation. In general, there are two key challenges for such an annotation paradigm. The first challenge is how to efficiently retrieve a short list of most similar facial images from facial image databases, and the second challenge is how to effectively perform annotation by exploiting these similar facial images and their weak labels which are often noisy and incomplete. In this paper, we mainly focus on tackling the second challenge of the retrieval-based face annotation paradigm. In particular, we propose an effective Weak Label Regularized Local Coordinate Coding (WLRLCC) technique, which exploits the local coordinate coding principle in learning sparse features, and at the same time employs the graph-based weak label regularization principle to enhance the weak labels of the short list of similar facial images. We present an efficient optimization algorithm to solve the WLRLCC task, and develop an effective sparse reconstruction scheme to perform the final face name annotation. We conduct a set of extensive empirical studies on a large-scale facial image database withatotal of 6,000 persons and over 600,000 web facial images, in which encouraging results show that the proposed WLRLCC algorithm significantly boosts the performance of the regular retrieval-based face annotation approaches.

A wireless sensor network becomes dynamic if it is monitoring a time-variant event (e.g., expansion of oil spill in ocean). In such applications, on-line boundary detection is a crucial function, as it allows us to track the event variation in a timely fashion. However, the problem becomes very challenging as it demands a highly efficient algorithm to cope with the dynamics introduced by the evolving event. Moreover, as many physical events occupy volumes rather than surfaces (e.g., oil spill again), the algorithm has to work for 3D cases. To this end, we propose UNiform Fast On-Line boundary Detection (UNFOLD) to tackle the challenge. The essence of UNFOLD is to inverse node coordinates such that a "notched" surface is "unfolded" into a convex one, which in turn reduces boundary detection to simple convexity test. UNFOLD is uniform as every node behaves the same (performing coordinate inversion and convexity test), and it is super fast as both computation and communication involve only one-hop neighbors. We prove the correctness and efficiency of UNFOLD; we also use simulations and implementations to evaluate its performance, which demonstrates that UNFOLD is 100 times more time and energy efficient than the most up-to-date proposal.

In this paper we propose an editable polycube mapping method that, given an arbitrary high-resolution polygonal mesh and a simple polycube representation plus optional sketched features indicating relevant correspondences between the two, provides a uniform, regular and artist-controllable quads-only mesh with a parameterized subdivision scheme. The method introduces a global parameterization, based on a divide and conquer strategy, which allows to create polycube-maps with a much smaller number of patches, and gives much more control over the quality of the induced subdivision surface. All this makes it practical for real-time rendering on modern hardware (e.g. OGL 4.1 and D3D11 tessellation hardware). By sketching these correspondence features, processing large-scale models with complex geometry and topology is now feasible. This is crucial for obtaining watertight displaced Catmull-Clark subdivision surfaces and high-quality texturing on real-time applications.

Line drawings are an effective way to convey shapes in a relatively succinct manner by ignoring the less important or distracting details. In the past decade, many promising computer-generated line drawing algorithms have been proposed, which can be roughly classified into two categories: object-space and image-space.

Sampling plays an important role in a variety of graphics applications. Among existing sampling methods, Poisson disk sampling is popular thanks to its useful statistical property in distribution and the absence of aliasing artifacts. Although many promising algorithms have been proposed for multi-dimensional sampling in Euclidean space, very few research studies have been reported with regard to the problem of generating Poisson disks on surfaces due to the complicated nature of the surface. This still remains a challenge due to the following reasons: first, a surface is a two-dimensional manifold that has arbitrary topology and complicated geometry, and is embedded in R3 or even higher dimensional space. Second, the exact geodesic distance should be used to enforce the minimum distance constraint between any pair of samples. Third, the algorithm should be parallelized such that it can make full use of all available threads. Last but not least, the generated samples should be randomly and uniformly distributed on surfaces, and exhibit the blue noise pattern without bias. Wei [2008] pioneered a parallel Poisson disk sampling algorithm by subdividing the sample domain into grid cells and drawing samples concurrently from multiple cells that are sufficiently far apart to avoid conflicts. Bowers et al. [2010] extended Wei's algorithm to 3D surfaces. Their method is highly efficient, allowing sampling on large-scale models at interactive speed. However, the generated distribution is not fully random since the sequence of processing the phase groups follows a predefined order. Moreover, the approximate geodesic computation in their approach results in large errors in models with rich features and thus compromises the sampling quality.

Geodesic plays an important role in geometric computation and analysis. Rather than the widely studied single source all destination discrete geodesic problem, very little work has been reported on the all pairs geodesic distance query So far, the best known result is due to Cook IV and Wenk [2009], who pre-computed the pairwise geodesic between any two mesh vertices in O(n52α(n) logn) time complexity and O(n4) space complexity, where n is the number of mesh vertices and α(n) the inverse Ackermann function. Then the geodesic distance between any pair of points on the mesh edges can be computed in O(m + logn) time, where m is the number of edges crossed by the geodesic path. Although Cook IV and Wenk's algorithm is able to compute the exact geodesic the high computational cost limits its applications to real-world models which usually contain thousands of vertices.

In this paper, we investigate a search-based face annotation framework by mining weakly labeled facial images that are freely available on the internet. A key component of such a search-based annotation paradigm is to build a database of facial images with accurate labels. This is however challenging since facial images on the WWW are often noisy and incomplete. To improve the label quality of raw web facial images, we propose an effective Unsupervised Label Refinement (ULR) approach for refining the labels of web facial images by exploring machine learning techniques. We develop effective optimization algorithms to solve the large-scale learning tasks efficiently, and conduct an extensive empirical study on a web facial image database with 400 persons and 40,000 web facial images. Encouraging results showed that the proposed ULR technique can significantly boost the performance of the promising search-based face annotation scheme.

With the popularity of various social media applications, massive social images associated with high quality tags have been made available in many social media web sites nowadays. Mining social images on the web has become an emerging important research topic in web search and data mining. In this paper, we propose a machine learning framework for mining social images and investigate its application to automated image tagging. To effectively discover knowledge from social images that are often associated with multimodal contents (including visual images and textual tags), we propose a novel Unified Distance Metric Learning (UDML) scheme, which not only exploits both visual and textual contents of social images, but also effectively unifies both inductive and transductive metric learning techniques in a systematic learning framework. We further develop an efficient stochastic gradient descent algorithm for solving the UDML optimization task and prove the convergence of the algorithm. By applying the proposed technique to the automated image tagging task in our experiments, we demonstrate that our technique is empirically effective and promising for mining social images towards some real applications.

A 3D burr puzzle is a 3D model that consists of interlocking pieces with a single-key property. That is, when the puzzle is assembled, all the pieces are notched except one single key component which remains mobile. The intriguing property of the assembled burr puzzle is that it is stable, perfectly interlocked, without glue or screws, etc. Moreover, a burr puzzle consisting of a small number of pieces is still rather difficult to solve since the assembly must follow certain orders while the combinatorial complexity of the puzzle's piece arrangements is extremely high. In this paper, we generalize the 6-piece orthogonal burr puzzle (a knot) to design and model burr puzzles from 3D models. Given a 3D input model, we first interactively embed a network of knots into the 3D shape. Our method automatically optimizes and arranges the orientation of each knot, and modifies pieces of adjacent knots with an appropriate connection type. Then, following the geometry of the embedded pieces, the entire 3D model is partitioned by splitting the solid while respecting the assembly motion of embedded pieces. The main technical challenge is to enforce the single-key property and ensure the assembly/disassembly remains feasible, as the puzzle pieces in a network of knots are highly interlocked. Lastly, we also present an automated approach to generate the visualizations of the puzzle assembly process.

This paper presents a novel object-space line drawing algorithm that can depict shapes with view-dependent feature lines in real time. Strongly inspired by the Laplacian-of-Gaussian (LoG) edge detector in image processing, we define Laplacian lines as the zero-crossing points of the Laplacian of the surface illumination. Compared to other view-dependent feature lines, Laplacian lines are computationally efficient because most expensive computations can be preprocessed. We further extend Laplacian lines to volumetric data and develop the algorithm to compute volumetric Laplacian lines without isosurface extraction. We apply the proposed Laplacian lines to a wide range of real-world models and demonstrate that Laplacian lines are more efficient than the existing computer generated feature lines, and can be used in interactive graphics applications.

Painting on 3D surfaces is an important operation in computer graphics, virtual reality, and computer aided design. The painting styles in existing WYSIWYG systems can be awkward, due to the difficulty in rotating or aligning an object for proper viewing during the painting. This paper proposes a multi-layer approach to building a practical, robust, and novel WYSIWYG interface for efficient painting on 3D models. The paintable area is not limited to the front-most visible surface on the screen as in conventional WYSIWYG interfaces. We can efficiently and interactively draw long strokes across different depth layers, and unveil occluded regions that one would like to see or paint on. In addition, since the painting is now depth-sensitive, we can avoid various potential painting artifacts and limitations in the conventional painting interfaces. This multi-layer approach brings in several novel painting operations that contribute to a more compelling WYSIWYG 3D painting interface; this is particular useful when dealing with complicated objects with occluded parts and objects that cannot be easily parameterized. We evaluated our system with 23 users, including both artists and novice painters, and obtained positive experimental results and feedback from them. The user study results demonstrate the efficacy of our novel interface over conventional painting interfaces.

Current trends in digital display technology show a marked interest towards 3D displays, which allow three dimensional images to be conveyed to viewers. Among various 3D display techniques, auto stereoscopic display appears to be promising due to the use of optical trickery at the display, allowing glass-free viewing. However, the cost of generating and transmitting the auto stereoscopic images is usually quite high due to the huge amount of data. Hence, it is challenging to acquire artifact-free 3D images in real-time. This paper presents a system to generate and display high-resolution auto stereoscopic images at full HD resolution, i.e., 1920*1080*24. We show that the video-plus-depth data representation enables a scalable system architecture and efficient data transition. The proposed GPU accelerated depth image-based rendering (DIBR) algorithm and multiplexing algorithm are able to synthesize auto stereoscopic images in real-time. The synthesized images are then displayed on the auto stereoscopic screen that is mounted on a conventional LCD monitor. We demonstrate our system to both indoor activities and natural scenes.

The significant advances in developing high-speed shape acquisition devices make it possible to capture the moving and deforming objects at video speeds. However, due to its complicated nature, it is technically challenging to effectively model and store the captured motion data. In this paper, we present a set of algorithms to construct geometry videos for 3D facial expressions, including hole filling, geodesic-based face segmentation, and expression-invariant parametrization. Our algorithms are efficient and robust, and can guarantee the exact correspondence of the salient features (eyes, mouth and nose). Geometry video naturally bridges the 3D motion data and 2D video, and provides a way to borrow the well-studied video processing techniques to motion data processing. With our proposed intra-frame prediction scheme based on H.264/AVC, we are able to compress the geometry videos into a very compact size while maintaining the video quality. Our experimental results on real-world datasets demonstrate that geometry video is effective for modeling the high-resolution 3D expression data.

Shells are three-dimensional structures. One dimension, the thickness, is much smaller than the other two dimensions. Shell structures can be widely found in many real-world objects. This paper presents a method to construct a layered hexahedral mesh for shell objects. Given a closed 2-manifold and the user-specified thickness, we construct the shell space using the distance field and then parameterize the shell space to a polycube domain. The volume parameterization induces the hexahedral tessellation in the object shell space. As a result, the constructed mesh is an all-hexahedral mesh in which most of the vertices are regular, i.e., the valence is 6 for interior vertices and 5 for boundary vertices. The mesh also has a layered structure that all layers have exactly the same tessellation. We prove our parameterization is guaranteed to be bijective. As a result, the constructed hexahedral mesh is free of degeneracy, such as self-intersection, flip-over, etc. We also show that the iso-parametric line (in the thickness dimension) is orthogonal to the other two isoparametric lines. We demonstrate the efficacy of our method upon models of various topology.

Volumetric parameterization plays an important role for geometric modeling. Due to the complicated topological nature of volumes, it is much more challenging than the surface case. This work focuses on the parameterization of volumes with a boundary surface embedded in 3D space. The intuition is to decompose the volume as the direct product of a two dimensional surface and a one dimensional curve. We first partition the boundary surface into ceiling, floor and walls. Then we compute the harmonic field in the volume with a Dirichlet boundary condition. By tracing the integral curve along the gradient of the harmonic function, we can parameterize the volume to the parametric domain. The method is guaranteed to produce bijection for handle bodies with complex topology, including topological balls as a degenerate case. Furthermore, the parameterization is regular everywhere. We apply the proposed parameterization method to construct hexahedral mesh.

This paper introduces a method for optimizing the tiles of a quad-mesh. Given a quad-based surface, the goal is to generate a set of K quads whose instances can produce a tiled surface that approximates the input surface. A solution to the problem is a K-set tilable surface, which can lead to an effective cost reduction in the physical construction of the given surface. Rather than molding lots of different building blocks, a K-set tilable surface requires the construction of K prefabricated components only. To realize the K-set tilable surface, we use a cluster-optimize approach. First, we iteratively cluster and analyze: clusters of similar shapes are merged, while edge connections between the K quads on the target surface are analyzed to learn the induced flexibility of the K-set tilable surface. Then, we apply a non-linear optimization model with constraints that maintain the K quads connections and shapes, and show how quad-based surfaces are optimized into K-set tilable surfaces. Our algorithm is demonstrated on various surfaces, including some that mimic the exteriors of certain renowned building landmarks.

Designing rotational symmetry fields on surfaces is an important task for a wide range of graphics applications. This work introduces a rigorous and practical approach for automatic N-RoSy field design on arbitrary surfaces with user-defined field topologies. The user has full control of the number, positions, and indexes of the singularities (as long as they are compatible with necessary global constraints), the turning numbers of the loops, and is able to edit the field interactively. We formulate N-RoSy field construction as designing a Riemannian metric such that the holonomy along any loop is compatible with the local symmetry of N-RoSy fields. We prove the compatibility condition using discrete parallel transport. The complexity of N-RoSy field design is caused by curvatures. In our work, we propose to simplify the Riemannian metric to make it flat almost everywhere. This approach greatly simplifies the process and improves the flexibility such that it can design N-RoSy fields with single singularity and mixed-RoSy fields. This approach can also be generalized to construct regular remeshing on surfaces. To demonstrate the effectiveness of our approach, we apply our design system to pen-and-ink sketching and geometry remeshing. Furthermore, based on our remeshing results with high global symmetry, we generate Celtic knots on surfaces directly.

The transmission of 3D models in the form of Geometry Images (GI) is an emerging and appealing concept due to the reduction in complexity from R3 to image space and wide availability of mature image processing tools and standards. However, geometry images often suffer from the artifacts and error during compression and transmission. Thus, there is a need to address the artifact reduction, error resilience and protection of such data information during the transmission across an error prone network. In this paper, we introduce a new concept, called Spectral Geometry Images (SGI), which naturally combines the powerful spectral analysis with geometry images. We show that SGI is more effective than GI to generate visually pleasing shapes at high compression rates. Furthermore, by coupling SGI to the proposed error protection scheme, we are able to ensure the smooth delivery of 3D model across error networks for different packet loss rate simulated using the two-state Markov model.

This paper presents a novel object-space line drawing algorithm that can depict shape with view dependent feature lines in real-time. Strongly inspired by the Laplacian-of-Gaussian (LoG) edge detector in image processing, we define Laplacian Lines as the zero-crossing points of the Laplacian of the surface illumination. Compared to other view dependent features, Laplacian lines are computationally efficient because most expensive computations can be pre-processed. Thus, Laplacian lines are very promising for interactively illustrating large-scale models.

Constructing smooth freeform surfaces of arbitrary topology with higher order continuity is one of the most fundamental problems in shape and solid modeling. This paper articulates a novel method to construct C∞ smooth surfaces with negative Euler numbers based on hyperbolic geometry and discrete curvature flow. According to Riemann uniformization theorem, every surface with negative Euler number has a unique conformal Riemannian metric, which induces Gaussian curvature of --1 everywhere. Hence, the surface admits hyperbolic geometry. Such uniformization metric can be computed using the discrete curvature flow method: hyperbolic Ricci flow. Consequently, the basis function for each control point can be naturally defined over a hyperbolic disk, and through the use of partition-of-unity, we build a freeform surface directly over hyperbolic domains while having C∞ property. The use of radial, exponential basis functions gives rise to a true meshless method for modeling freeform surfaces with greatest flexibilities, without worrying about control point connectivity. Our algorithm is general for arbitrary surfaces with negative Euler characteristic. Furthermore, it is C∞ continuous everywhere across the entire hyperbolic domain without singularities. Our experimental results demonstrate the efficiency and efficacy of the proposed new approach for shape and solid modeling.

Harmonic volumetric mapping aims to establish a smooth bijective correspondence between two solid shapes with the same topology. In this paper, we develop an automatic meshless method for creating such a mapping between two given objects. With the shell surface mapping as the boundary condition, we first solve a linear system constructed by a boundary method called themethodoffundamentalsolution, and then represent the mapping using a set of points with different weights in the vicinity of the shell of the given model. Our algorithm is a true meshless method (without the need of any specific meshing structure within the solid interior) and the behavior of the interior region is directly determined by the boundary, which can improve the computational efficiency and robustness significantly. Therefore, our algorithm can be applied to massive volume data sets with various geometric primitives and topological types. We demonstrate the utility and efficacy of our algorithm in information transfer, shape registration, deformation sequence analysis, tetrahedral remeshing, and solid texture synthesis.

Polycube T-spline has been formulated elegantly that can unify T-splines and manifold splines to define a new class of shape representations for surfaces of arbitrary topology by using polycube map as its parametric domain. In essense, The data fitting quality using polycube T-splines hinges upon the construction of underlying polycube maps. Yet, existing methods for polycube map construction exhibit some disadvantages. For example, existing approaches for polycube map construction either require projection of points from a 3D surface to its polycube approximation, which is therefore very difficult to handle the cases when two shapes differ significantly; or compute the map by conformally deforming the surfaces and polycubes to the common canonical domain and then construct the map using function composition, which is challenging to control the location of singularities and makes it hard for the data-fitting and hole-filling processes later on.

This paper presents a method to extract skeletons using examples. Our method is based on the observation that many deformations in real world applications are isometric or near isometric. By taking advantage of the intrinsic property of harmonic 1-form, i.e., it is determined by the metric and independent of the resolution and embedding, our method can easily find a consistent mapping between the reference and example poses which can be in different resolutions and triangulations. We first construct the skeleton-like Reeb graph of a harmonic function defined on the given poses. Then by examining the changes of mean curvatures, we identify the initial locations of joints. Finally we refine the joint locations by solving a constrained optimization problem. To demonstrate the efficacy of our method, we apply the extracted skeletons to pose space deformation and skeleton transfer.

This paper develops a novel computational technique to define and construct powerful manifold splines with only one singular point by employing the rigorous mathematical theory of Ricci flow. The central idea and new computational paradigm of manifold splines are to systematically extend the algorithmic pipeline of spline surface construction from any planar domain to arbitrary topology. As a result, manifold splines can unify planar spline representations as their special cases. Despite their earlier success, the existing manifold spline framework is plagued by the topology-dependent, large number of singular points (i.e., |2g -- 2| for any genus-g surface), where the analysis of surface behaviors such as continuity remains extremely difficult. The unique theoretical contribution of this paper is that we devise new mathematical tools so that manifold splines can now be constructed with only one singular point, reaching their theoretic lower bound of singularity for real-world applications. Our new algorithm is founded upon the concept of discrete Ricci flow and associated techniques. First, Ricci flow is employed to compute a special metric of any manifold domain (serving as a parametric domain for manifold splines), such that the metric becomes flat everywhere except at one point. Then, the metric naturally induces an affine atlas covering the entire manifold except this singular point. Finally, manifold splines are defined over this affine atlas. The Ricci flow method is theoretically sound, and practically simple and efficient. We conduct various shape experiments and our new theoretical and algorithmic results alleviate the modeling difficulty of manifold splines, and hence, promising to promote the widespread use of manifold splines in surface and solid modeling, geometric design, and reverse engineering.

Harmonic volumetric mapping for two solid objects establishes a one-to-one smooth correspondence between them. It finds its applications in shape registration and analysis, shape retrieval, information reuse, and material/texture transplant. In sharp contrast to harmonic surface mapping techniques, little research has been conducted for designing volumetric mapping algorithms due to its technical challenges. In this paper, we develop an automatic and effective algorithm for computing harmonic volumetric mapping between two models of the same topology. Given a boundary mapping between two models, the volumetric (interior) mapping is derived by solving a linear system constructed from a boundary method called the fundamental solution method. The mapping is represented as a set of points with different weights in the vicinity of the solid boundary. In a nutshell, our algorithm is a true meshless method (with no need of specific connectivity) and the behavior of the interior region is directly determined by the boundary. These two properties help improve the computational efficiency and robustness. Therefore, our algorithm can be applied to massive volume data sets with various geometric primitives and topological types. We demonstrate the utility and efficacy of our algorithm in shape registration, information reuse, deformation sequence analysis, tetrahedral remeshing and solid texture synthesis.

This paper proposes a new concept of polycube splines and develops novel modeling techniques for using the polycube splines in solid modeling and shape computing. Polycube splines are essentially a novel variant of manifold splines which are built upon the polycube map, serving as its parametric domain. Our rationale for defining spline surfaces over polycubes is that polycubes have rectangular structures everywhere over their domains except a very small number of corner points. The boundary of polycubes can be naturally decomposed into a set of regular structures, which facilitate tensor-product surface definition, GPU-centric geometric computing, and image-based geometric processing. We develop algorithms to construct polycube maps, and show that the introduced polycube map naturally induces the affine structure with a finite number of extraordinary points. Besides its intrinsic rectangular structure, the polycube map may approximate any original scanned data-set with a very low geometric distortion, so our method for building polycube splines is both natural and necessary, as its parametric domain can mimic the geometry of modeled objects in a topologically correct and geometrically meaningful manner. We design a new data structure that facilitates the intuitive and rapid construction of polycube splines in this paper. We demonstrate the polycube splines with applications in surface reconstruction and shape computing.

Conveying shape using feature lines is an important visualization tool in visual computing. The existing feature lines (e.g., ridges, valleys, silhouettes, suggestive contours, etc.) are solely determined by local geometry properties (e.g., normals and curvatures) as well as the view position. This paper is strongly inspired by the observation in human vision and perception that a sudden change in the luminance plays a critical role to faithfully represent and recover the 3D information. In particular, we adopt the edge detection techniques in image processing for 3D shape visualization and present Photic Extremum Lines (PELs) which emphasize significant variations of illumination over 3D surfaces. Comparing with the existing feature lines, PELs are more flexible and offer users more freedom to achieve desirable visualization effects. In addition, the user can easily control the shape visualization by changing the light position, the number of light sources, and choosing various light models. We compare PELs with the existing approaches and demonstrate that PEL is a flexible and effective tool to illustrate 3D surface and volume for visual computing.

We develop a new surface matching framework to handle surface comparisons based on the mathematical analysis of curves on surfaces, and propose a unique signature for any closed curve on a surface. The signature describes not only the shape of the curve, but also the intrinsic relationship between the curve and its embedding surface; and furthermore, the signature metric is stable across surfaces sharing similar Riemannian geometry metrics. Based on this theoretical advance, we analyze and align features defined as closed curves on surfaces using their signatures. These curves segment a surface into different regions which are mapped onto canonical domains for the matching purpose. The experimental results are very promising, demonstrating that the curve signatures and the comparison framework are robust and discriminative for the effective shape comparison. Besides its utility in our current framework, we believe the curve signature will also serve as a powerful shape segmentation/mapping tool and can be used to aid in many existing techniques towards effective shape analysis

Constructing splines whose parametric domain is an arbitrary manifold and effectively computing such splines in real-world applications are of fundamental importance in solid and shape modeling, geometric design, graphics, etc. This paper presents a general theoretical and computational framework, in which spline surfaces defined over planar domains can be systematically extended to manifold domains with arbitrary topology with or without boundaries. We study the affine structure of domain manifolds in depth and prove that the existence of manifold splines is equivalent to the existence of a manifold's affine atlas. Based on our theoretical breakthrough, we also develop a set of practical algorithms to generalize triangular B-spline surfaces from planar domains to manifold domains. We choose triangular B-splines mainly because of its generality and many of its attractive properties. As a result, our new spline surface defined over any manifold is a piecewise polynomial surface with high parametric continuity without the need for any patching and/or trimming operations. Through our experiments, we hope to demonstrate that our novel manifold splines are both powerful and efficient in modeling arbitrarily complicated geometry and representing continuously-varying physical quantities defined over shapes of arbitrary topology.

Traditional approaches for modeling a closed manifold surface with either regular tensor-product or triangular splines (defined over an open planar domain) require decomposing the acquired geometric data into a group of charts, mapping each chart to a planar parametric domain, fitting an open surface patch of certain degree to each chart, and finally, trimming the patches (if necessary) and stitching all of them together to form a closed manifold. In this paper, we develop a novel modeling method which does not need any cutting or patching operations for genus zero surfaces. Our new approach is founded upon the concept of spherical splines proposed by Pfeifle and Seidel. Our work is strongly inspired by the fact that, for genus zero surfaces, it is both intuitive and necessary to employ spheres as their natural domains. Using this framework, we can convert genus zero mesh to a single rational spherical spline whose maximal error deviated from the original data is less than a user-specified tolerance. With the rational spherical splines, we can model sharp features and edit both the global shape and the local details with ease. Furthermore, we can accurately compute the differential quantities without resorting to any numerical approximations. We conduct several experiments in order to demonstrate the efficacy of our approach for reverse engineering, shape modeling, and interactive graphics.

This paper presents a modeling technique for reconstructing a triangular B-spline surface from a set of scanned 3D points. Unlike existing surface reconstruction methods based on tensor-product B-splines which primarily generate a network of patches and then enforce certain continuity (usually, G/sup 1/ or C/sup 1/) between adjacent patches, our algorithm can avoid the complicated procedures of surface trimming and patching. In our framework, the user simply specifies the degree n of the triangular B-spline surface and fitting error tolerance /spl epsi/. The surface reconstruction procedure generates a single triangular B-spline patch that has C/sup n-1/ continuity over smooth regions and C/sup 0/ on sharp features. More importantly, all the knots and control points are determined by minimizing a linear combination of interpolation and fairness functionals. Examples are presented which demonstrate the effectiveness of the technique for real data sets.