Computing the directed Hausdorff distance between two triangle meshes is a fundamental operation in geometry processing and simulation. While existing certified branch-and-bound (B&B) methods are efficient for well-separated geometry, they can become prohibitively expensive on large models under tight tolerances and near-zero distance configurations where pruning is limited. We present a GPU-accelerated certified B&B algorithm that explicitly maintains enclosing lower and upper bounds on the directed Hausdorff distance and terminates once their normalized gap, measured with respect to the bounding-box diagonal of the source mesh, meets a user-prescribed tolerance. To map the inherently prioritized search to SIMT (single-instruction, multiple-thread) hardware, we replace priority queues and recursion with a sorted, double-buffered wavefront pipeline built from bulk-parallel worklists for bound evaluation, culling, subdivision, and compaction. To mitigate loose bounds on thin primitives while preserving predictable stream behavior, we introduce a fixed-cardinality adaptive subdivision scheme that selectively applies double longest-edge bisection. To remain robust in deep-refinement regimes, we add a resource-aware deferral mechanism that enforces a device-capacity invariant by prioritizing candidates likely to be culled while postponing expensive ones. Finally, we improve numerical robustness under FP32 (single precision) via triangle-local coordinate transforms and other conservative numerical safeguards, and enhance coherence by spatially ordering the active set and traversing the BVH (bounding volume hierarchy) in triangle packets. Under the same stopping tolerance, experiments on an NVIDIA RTX 5090 show that our GPU solver remains numerically consistent with the FP64 CPU baseline, with normalized cross-platform deviation below 0.01% in over 99.9% of cases. Our method achieves millisecond-scale runtimes capable of supporting interactive frame rates, even on models with millions of triangles. Across the comparison set, it delivers throughput speedups of 836× on the Thingi10K/TetWild benchmark ( A → B ) and 709× on the Thingi10K/Decimation benchmark. Code and data for this paper are available at https://github.com/fhp-transient/gpu-hausdorff.

We present a novel learning method using a two-stream network to predict cloth deformation for skeleton-based characters. The characters processed in our approach are not limited to humans, and can be other targets with skeleton-based representations such as fish or pets. We use a novel network architecture which consists of skeleton-based and mesh-based residual networks to learn the coarse features and wrinkle features forming the overall residual from the template cloth mesh. Our network may be used to predict the deformation for loose or tight-fitting clothing. The memory footprint of our network is low, thereby resulting in reduced computational requirements. In practice, a prediction for a single cloth mesh for a skeleton-based character takes about 7 ms on an nVidia GeForce RTX 3090 GPU. Compared to prior methods, our network can generate finer deformation results with details and wrinkles.

Recent researches reveal that StyleGAN can generate highly realistic images, inspiring researchers to use pretrained StyleGAN to generate high-fidelity swapped faces. However, existing methods fail to meet the expectations in two essential aspects of high-fidelity face swapping. Their results are blurry without pore-level details and fail to preserve identity for challenging cases. To overcome the above artifacts, we innovatively construct a series of identity-preserving semantic bases of StyleGAN (called StyleIPSB) in respect of pose, expression, and illumination. Each basis of StyleIPSB controls one specific semantic attribute and disentangles with the others. The StyleIPSB constrains style code in the subspace of W+ space to preserve pore-level details and gives us a novel tool for high-fidelity face swapping, and we propose a three-stage framework for face swapping with StyleIPSB. Firstly, we transform the target facial images' attributes to the source image. We learn the mapping from 3D Morphable Model (3DMM) parameters, which capture the prominent semantic variance, to the coordinates of StyleIPSB that show higher identity-preserving and fidelity. Secondly, to transform detailed attributes which 3DMM does not capture, we learn the residual attribute between the reenacted face and the target face. Finally, the face is blended into the background of the target image. Extensive results and comparisons demonstrate that StyleIPSB can effectively preserve identity and pore-level details. The results of face swapping can achieve state-of-the-art performance. We will release our code at https://github.com/a686432/StyleIPSB

Abstract We propose a three‐stage network that utilizes a skinning‐based model to accurately predict dynamic cloth deformation. Our approach decomposes cloth deformation into three distinct components: static, coarse dynamic, and wrinkle dynamic components. To capture these components, we train our three‐stage network accordingly. In the first stage, the static component is predicted by constructing a static skinning model that incorporates learned joint increments and skinning weight increments. Then, in the second stage, the coarse dynamic component is added to the static skinning model by incorporating serialized skeleton information. Finally, in the third stage, the mesh sequence stage refines the prediction by incorporating the wrinkle dynamic component using serialized mesh information. We have implemented our network and used it in a Unity game scene, enabling real‐time prediction of cloth dynamics. Our implementation achieves impressive prediction speeds of approximately 3.65ms using an NVIDIA GeForce RTX 3090 GPU and 9.66ms on an Intel i7‐7700 CPU. Compared to SOTA methods, our network excels in accurately capturing fine dynamic cloth deformations.

3D morphable models (3DMMs) are generative models for face shape and appearance. Recent works impose face recognition constraints on 3DMM shape parameters so that the face shapes of the same person remain consistent. However, the shape parameters of traditional 3DMMs satisfy the multivariate Gaussian distribution. In contrast, the identity embeddings meet the hypersphere distribution, and this conflict makes it challenging for face reconstruction models to preserve the faithfulness and the shape consistency simultaneously. In other words, recognition loss and reconstruction loss can not decrease jointly due to their conflict distribution. To address this issue, we propose the Sphere Face Model (SFM), a novel 3DMM for monocular face reconstruction, preserving both shape fidelity and identity consistency. The core of our SFM is the basis matrix which can be used to reconstruct 3D face shapes, and the basic matrix is learned by adopting a two-stage training approach where 3D and 2D training data are used in the first and second stages, respectively. We design a novel loss to resolve the distribution mismatch, enforcing that the shape parameters have the hyperspherical distribution. Our model accepts 2D and 3D data for constructing the sphere face models. Extensive experiments show that SFM has high representation ability and clustering performance in its shape parameter space. Moreover, it produces high-fidelity face shapes consistently in challenging conditions in monocular face reconstruction. The code will be released at https://github.com/a686432/SIR

Abstract Many recent works have reconstructed distinctive 3D face shapes by aggregating shape parameters of the same identity and separating those of different people based on parametric models (e.g. 3D morphable models (3DMMs)). However, despite the high accuracy in the face recognition task using these shape parameters, the visual discrimination of face shapes reconstructed from those parameters remains unsatisfactory. Previous works have not answered the following research question: Do discriminative shape parameters guarantee visual discrimination in represented 3D face shapes? This paper analyses the relationship between shape parameters and reconstructed shape geometry, and proposes a novel shape identity‐aware regularization (SIR) loss for shape parameters, aiming at increasing discriminability in both the shape parameter and shape geometry domains. Moreover, to cope with the lack of training data containing both landmark and identity annotations, we propose a network structure and an associated training strategy to leverage mixed data containing either identity or landmark labels. In addition, since face recognition accuracy does not mean the recognizability of reconstructed face shapes from the shape parameters, we propose the SIR metric to measure the discriminability of face shapes. We compare our method with existing methods in terms of the reconstruction error, visual discriminability, and face recognition accuracy of the shape parameters and SIR metric. Experimental results show that our method outperforms the state‐of‐the‐art methods. The code will be released at https://github.com/a686432/SIR .

Abstract We present a novel mesh‐based learning approach (N‐Cloth) for plausible 3D cloth deformation prediction. Our approach is general and can handle cloth or obstacles represented by triangle meshes with arbitrary topologies. We use graph convolution to transform the cloth and object meshes into a latent space to reduce the non‐linearity in the mesh space. Our network can predict the target 3D cloth mesh deformation based on the initial state of the cloth mesh template and the target obstacle mesh. Our approach can handle complex cloth meshes with up to 100 K triangles and scenes with various objects corresponding to SMPL humans, non‐SMPL humans or rigid bodies. In practice, our approach can be used to generate plausible cloth simulation at 30 – 45 fps on an NVIDIA GeForce RTX 3090 GPU. We highlight its benefits over prior learning‐based methods and physically‐based cloth simulators.

Image-based virtual try-on aims to synthesize the customer image with an in-shop clothes image to acquire seamless and natural try-on results, which have attracted increasing attentions. The main procedures of image-based virtual try-on usually consist of clothes image generation and try-on image synthesis, whereas prior arts cannot guarantee satisfying clothes results when facing large geometric changes and complex clothes patterns, which further deteriorates the afterwards try-on results. To address this issue, we propose a novel virtual try-on network based on landmark-guided shape matching (LM-VTON). Specifically, the clothes image generation progressively learns the warped clothes and refined clothes in an end-to-end manner, where we introduce a landmark-based constraint in Thin-Plate Spline (TPS) warping to inject finer deformation constraints around the clothes. The try-on process synthesizes the warped clothes with personal characteristics via a semantic indicator. Qualitative and quantitative experiments on two public datasets validate the superiority of the proposed method, especially for challenging cases such as large geometric changes and complex clothes patterns. Code will be available at https://github.com/lgqfhwy/LM-VTON.

We present a novel parallel algorithm for cloth simulation that exploits multiple GPUs for fast computation and the handling of very high resolution meshes. To accelerate implicit integration, we describe new parallel algorithms for sparse matrix-vector multiplication (SpMV) and for dynamic matrix assembly on a multi-GPU workstation. Our algorithms use a novel work queue generation scheme for a fat-tree GPU interconnect topology. Furthermore, we present a novel collision handling scheme that uses spatial hashing for discrete and continuous collision detection along with a non-linear impact zone solver. Our parallel schemes can distribute the computation and storage overhead among multiple GPUs and enable us to perform almost interactive simulation on complex cloth meshes, which can hardly be handled on a single GPU due to memory limitations. We have evaluated the performance with two multi-GPU workstations (with 4 and 8 GPUs, respectively) on cloth meshes with 0.5 -- 1.65 M triangles. Our approach can reliably handle the collisions and generate vivid wrinkles and folds at 2 -- 5 fps, which is significantly faster than prior cloth simulation systems. We observe almost linear speedups with respect to the number of GPUs.

We propose Hierarchical Optimization Time Integration (HOT) for efficient implicit timestepping of the material point method (MPM) irrespective of simulated materials and conditions. HOT is an MPM-specialized hierarchical optimization algorithm that solves nonlinear timestep problems for large-scale MPM systems near the CFL limit. HOT provides convergent simulations out of the box across widely varying materials and computational resolutions without parameter tuning. As an implicit MPM timestepper accelerated by a custom-designed Galerkin multigrid wrapped in a quasi-Newton solver, HOT is both highly parallelizable and robustly convergent. As we show in our analysis, HOT maintains consistent and efficient performance even as we grow stiffness, increase deformation, and vary materials over a wide range of finite strain, elastodynamic, and plastic examples. Through careful benchmark ablation studies, we compare the effectiveness of HOT against seemingly plausible alternative combinations of MPM with standard multigrid and other Newton-Krylov models. We show how these alternative designs result in severe issues and poor performance. In contrast, HOT outperforms existing state-of-the-art, heavily optimized implicit MPM codes with an up to 10× performance speedup across a wide range of challenging benchmark test simulations.

Harnessing the power of modern multi-GPU architectures, we present a massively parallel simulation system based on the Material Point Method (MPM) for simulating physical behaviors of materials undergoing complex topological changes, self-collision, and large deformations. Our system makes three critical contributions. First, we introduce a new particle data structure that promotes coalesced memory access patterns on the GPU and eliminates the need for complex atomic operations on the memory hierarchy when writing particle data to the grid. Second, we propose a kernel fusion approach using a new Grid-to-Particles-to-Grid ( G2P2G ) scheme, which efficiently reduces GPU kernel launches, improves latency, and significantly reduces the amount of global memory needed to store particle data. Finally, we introduce optimized algorithmic designs that allow for efficient sparse grids in a shared memory context, enabling us to best utilize modern multi-GPU computational platforms for hybrid Lagrangian-Eulerian computational patterns. We demonstrate the effectiveness of our method with extensive benchmarks, evaluations, and dynamic simulations with elastoplasticity, granular media, and fluid dynamics. In comparisons against an open-source and heavily optimized CPU-based MPM codebase [Fang et al. 2019] on an elastic sphere colliding scene with particle counts ranging from 5 to 40 million, our GPU MPM achieves over 100x per-time-step speedup on a workstation with an Intel 8086K CPU and a single Quadro P6000 GPU, exposing exciting possibilities for future MPM simulations in computer graphics and computational science. Moreover, compared to the state-of-the-art GPU MPM method [Hu et al. 2019a], we not only achieve 2x acceleration on a single GPU but our kernel fusion strategy and Array-of-Structs-of-Array ( AoSoA ) data structure design also generalizes to multi-GPU systems. Our multi-GPU MPM exhibits near-perfect weak and strong scaling with 4 GPUs, enabling performant and large-scale simulations on a 1024 3 grid with close to 100 million particles with less than 4 minutes per frame on a single 4-GPU workstation and 134 million particles with less than 1 minute per frame on an 8-GPU workstation.

Abstract Bounding volume hierarchy (BVH) has been widely adopted as the acceleration structure in broad‐phase collision detection. Previous state‐of‐the‐art BVH‐based collision detection approaches exploited the spatio‐temporal coherence of simulations by maintaining a bounding volume test tree (BVTT) front. A major drawback of these algorithms is that large deformations in the scenes decrease culling efficiency and slow down collision queries. Moreover, for front‐based methods, the inefficient caching on GPU caused by the arbitrary layout of BVH and BVTT front nodes becomes a critical performance issue. We present a fast and robust BVH‐based collision detection scheme on GPU that addresses the above problems by ordering and restructuring BVHs and BVTT fronts. Our techniques are based on the use of histogram sort and an auxiliary structure BVTT front log, through which we analyze the dynamic status of BVTT front and BVH quality. Our approach efficiently handles inter‐ and intra‐object collisions and performs especially well in simulations where there is considerable spatio‐temporal coherence. The benchmark results demonstrate that our approach is significantly faster than the previous BVH‐based method, and also outperforms other state‐of‐the‐art spatial subdivision schemes in terms of speed.

Abstract Accurate high‐resolution simulation of cloth is a highly desired computational tool in graphics applications. As single‐resolution simulation starts to reach the limit of computational power, we believe the future of cloth simulation is in multi‐resolution simulation. In this paper, we explore nonlinearity, adaptive smoothing, and parallelization under a full multigrid (FMG) framework. The foundation of this research is a novel nonlinear FMG method for unstructured meshes. To introduce nonlinearity into FMG, we propose to formulate the smoothing process at each resolution level as the computation of a search direction for the original high‐resolution nonlinear optimization problem. We prove that our nonlinear FMG is guaranteed to converge under various conditions and we investigate the improvements to its performance. We present an adaptive smoother which is used to reduce the computational cost in the regions with low residuals already. Compared to normal iterative solvers, our nonlinear FMG method provides faster convergence and better performance for both Newton's method and Projective Dynamics. Our experiment shows our method is efficient, accurate, stable against large time steps, and friendly with GPU parallelization. The performance of the method has a good scalability to the mesh resolution, and the method has good potential to be combined with multi‐resolution collision handling for real‐time simulation in the future.

We present an incremental collision handling algorithm for GPU-based interactive cloth simulation. Our approach exploits the spatial and temporal coherence between successive iterations of an optimization-based solver for collision response computation. We present an incremental continuous collision detection algorithm that keeps track of deforming vertices and combine it with spatial hashing. We use a non-linear GPU-based impact zone solver to resolve the penetrations. We combine our collision handling algorithm with implicit integration to use large time steps. Our overall algorithm, I-Cloth, can simulate complex cloth deformation with a few hundred thousand vertices at 2 - 8 frames per second on a commodity GPU. We highlight its performance on different benchmarks and observe up to 7 - 10X speedup over prior algorithms.

Abstract We present an efficient and accurate algorithm for self‐collision detection in deformable models. Our approach can perform discrete and continuous collision queries on triangulated meshes. We present a simple and linear time algorithm to perform the normal cone test using the unprojected 3D vertices, which reduces to a sequence point‐plane classification tests. Moreover, we present a hierarchical traversal scheme that can significantly reduce the number of normal cone tests and the memory overhead using front‐based normal cone culling. The overall algorithm can reliably detect all (self) collisions in models composed of hundreds of thousands of triangles. We observe considerable performance improvement over prior continuous collision detection algorithms.

Abstract Estimation of 3D body shapes from dressed‐human photos is an important but challenging problem in virtual fitting. We propose a novel automatic framework to efficiently estimate 3D body shapes under clothes. We construct a database of 3D naked and dressed body pairs, based on which we learn how to predict 3D positions of body landmarks (which further constrain a parametric human body model) automatically according to dressed‐human silhouettes. Critical vertices are selected on 3D registered human bodies as landmarks to represent body shapes, so as to avoid the time‐consuming vertices correspondences finding process for parametric body reconstruction. Our method can estimate 3D body shapes from dressed‐human silhouettes within 4 seconds, while the fastest method reported previously need 1 minute. In addition, our estimation error is within the size tolerance for clothing industry. We dress 6042 naked bodies with 3 sets of common clothes by physically based cloth simulation technique. To the best of our knowledge, We are the first to construct such a database containing 3D naked and dressed body pairs and our database may contribute to the areas of human body shapes estimation and cloth simulation.

Abstract We present a novel GPU‐based approach to robustly and efficiently simulate high‐resolution and complexly layered cloth. The key component of our formulation is a parallelized matrix assembly algorithm that can quickly build a large and sparse matrix in a compressed format and accurately solve linear systems on GPUs. We also present a fast and integrated solution for parallel collision handling, including collision detection and response computations, which utilizes spatio‐temporal coherence. We combine these algorithms as part of a new cloth simulation pipeline that incorporates contact forces into implicit time integration for collision avoidance. The entire pipeline is implemented on GPUs, and we evaluate its performance on complex benchmarks consisting of 100 – 300K triangles. In practice, our system takes a few seconds to simulate one frame of a complex cloth scene, which represents significant speedups over prior CPU and GPU‐based cloth simulation systems.

We present an efficient and robust method which performs well for both strain limiting and treatment of simultaneous collisions. Our method formulates strain constraints and collision constraints as a serial of linear matrix inequalities (LMIs) and linear polynomial inequalities (LPIs), and solves an optimization problem with standard convex semidefinite programming solvers. When performing strain limiting, our method acts on strain tensors to constrain the singular values of the deformation gradient matrix in a specified interval. Our method can be applied to both triangular surface meshes and tetrahedral volume meshes. Compared with prior strain limiting methods, our method converges much faster and guarantees triangle flipping does not occur when applied to a triangular mesh. When performing treatment of simultaneous collisions, our method eliminates all detected collisions during each iteration, leading to higher efficiency and faster convergence than prior collision treatment methods.

We propose an automatic parametric human body reconstruction algorithm which can efficiently construct a model using a single Kinect sensor. A user needs to stand still in front of the sensor for a couple of seconds to measure the range data. The user's body shape and pose will then be automatically constructed in several seconds. Traditional methods optimize dense correspondences between range data and meshes. In contrast, our proposed scheme relies on sparse key points for the reconstruction. It employs regression to find the corresponding key points between the scanned range data and some annotated training data. We design two kinds of feature descriptors as well as corresponding regression stages to make the regression robust and accurate. Our scheme follows with dense refinement where a pre-factorization method is applied to improve the computational efficiency. Compared with other methods, our scheme achieves similar reconstruction accuracy but significantly reduces runtime.

http://gamma.cs.unc.edu/BSC/ We present a realtime and reliable continuous collision detection (CCD) algorithm between triangulated models that exploits the floating point hardware capability of current CPUs and GPUs. Our formulation is based on Bernstein Sign Classification that takes advantage of the geometry properties of Bernstein basis and Bézier curves to perform Boolean collision queries. We derive tight numerical error bounds on the computations and employ those bounds to design an accurate algorithm using finite-precision arithmetic. Compared with prior floatingpoint CCD algorithms, our approach eliminates all the false negatives and 90–95% of the false positives. We integrated our algorithm (TightCCD) with physically-based simulation system and observe speedups in collision queries of 5–15X compared with prior reliable CCD algorithms. Furthermore, we demonstrate its benefits in terms of improving the performance or robustness of cloth simulation systems.

Abstract We present a GPU‐based streaming algorithm to perform high‐resolution and accurate cloth simulation. We map all the components of cloth simulation pipeline, including time integration, collision detection, collision response, and velocity updating to GPU‐based kernels and data structures. Our algorithm perform intra‐object and inter‐object collisions, handles contacts and friction, and is able to accurately simulate folds and wrinkles. We describe the streaming pipeline and address many issues in terms of obtaining high throughput on many‐core GPUs. In practice, our algorithm can perform high‐fidelity simulation on a cloth mesh with 2M triangles using 3GB of GPU memory. We highlight the parallel performance of our algorithm on three different generations of GPUs. On a high‐end NVIDIA Tesla K20c, we observe up to two orders of magnitude performance improvement as compared to a single‐threaded CPU‐based algorithm, and about one order of magnitude improvement over a 16‐core CPU‐based parallel implementation.

In the application of extracting human regions from videos, many existing methods may lose their efficacy when illumination varies or the human remains still. To address this problem, we propose a method in this paper for human region detection and segmentation by constructing a generalized human upper body model. The method mainly consists of two main procedures. First, foreground connected regions are extracted by background subtraction from the current frame and classified through a human upper body model pretrained with a support vector machine to determine whether they are human regions. Second, we assign an energy function to the region contour and apply an energy minimization procedure to evolve the contour when human regions are polluted by background; for example, a change in lighting conditions. After finding the optimal contour, we update the background and repeat the procedures in next frame. This feedback strategy rectifies the mistaken background regions promptly and extracts human regions correctly. Our experimental results demonstrate that the proposed method is robust enough to handle videos of low contrast as well as normal conditions.

ABSTRACT We present a novel culling algorithm that uses deforming noncollinear filters to improve the performance of continuous collision detection (CCD) algorithms. The underlying idea is to use simple and effective filters, deforming noncollinear filters (NCFs), that reduce the number of false positives between the primitives. These filters are derived from the collinear conditions and can be easily combined with other culling methods. We have tested its performance on several benchmarks. Comparing with previous methods, we can reduce the number of false positives significantly and improve the overall performance of CCD algorithms, especially for simulations with large time steps. Copyright © 2012 John Wiley & Sons, Ltd.

We present a simple algorithm to compute continuous penalty forces to determine collision response between rigid and deformable models bounded by triangle meshes. Our algorithm computes a well-behaved solution in contrast to the traditional stability and robustness problems of penalty methods, induced by force discontinuities. We trace contact features along their deforming trajectories and accumulate penalty forces along the penetration time intervals between the overlapping feature pairs. Moreover, we present a closed-form expression to compute the continuous and smooth collision response. Our method has very small additional overhead compared to previous penalty methods, and can significantly improve the stability and robustness. We highlight its benefits on several benchmarks.

We present a fast GPU-based streaming algorithm to perform collision queries between deformable models. Our approach is based on hierarchical culling and reduces the computation to generating different streams. We present a novel stream registration method to compact the streams and efficiently compute the potentially colliding pairs of primitives. We also use a deferred front tracking method to lower the memory overhead. The overall algorithm has been implemented on different GPUs and we have evaluated its performance on non-rigid and deformable simulations. We highlight our speedups over prior CPU-based and GPU-based algorithms. In practice, our algorithm can perform inter-object and intra-object computations on models composed of hundreds of thousands of triangles in tens of milliseconds.

We present a novel culling algorithm to perform fast and robust continuous collision detection between deforming volume meshes. This includes a continuous separating axis test that can conservatively check whether two volume meshes overlap during a given time interval. In addition, we present efficient methods to eliminate redundant elementary tests between the features (e.g., vertices, edges, and faces) of volume elements (e.g., tetrahedra, hexahedra, triangular prisms, etc.). Our approach is applicable to various deforming meshes, including those with changing topologies, and efficiently computes the first time of contact. We are able to perform inter-object and intra-object collision queries in models represented with tens of thousands of volume elements at interactive rates on a single CPU core. Moreover, we observe more than an order of magnitude performance improvement over prior methods.

We present a novel culling algorithm that uses deforming non-penetration filters to improve the performance of continuous collision detection (CCD) algorithms. The underlying idea is to use a simple and effective filter that reduces both the number of false positives and the elementary tests between the primitives. This filter is derived from the coplanarity condition and can be easily combined with other methods used to accelerate CCD. We have implemented the algorithm and tested its performance on many non-rigid simulations. In practice, we can reduce the number of false positives significantly and improve the overall performance of CCD algorithms by 1.5--8.2x.

Abstract This paper presents an intuitive rhinoplasty planning and simulation system, to provide high quality prediction of postoperative appearance, and design patient specific nose prosthesis automatically. The key component is a novel volumetric Laplacian deformation tool inspired by the state‐of‐the‐art differential surface deformation techniques. Working on the volumetric domain and incorporating inhomogeneous material from CT data make the new approach suitable for soft tissue simulation. In particular, the system employs a special sketch contour driving deformation interface, which can provide realistic 3D rhinoplasty simulation with intuitive and straightforward 2D manipulation. When satisfied with the appearance, the change of soft tissue before and after simulation is utilized to generate the individual prosthesis model automatically. Clinical validation using post‐operative CT data demonstrated that the system can provide prediction results of high quality. And the surgeons who used the system confirmed that this planning system is attractive and has potential for daily clinical practice. Copyright © 2010 John Wiley & Sons, Ltd.

This paper presented a special computer aided procedure to design a new sacroliliac anatomic bar-plate internal fixation system, and evaluated its biomechanical properties on an accurate patient-specific finite element model of entire pelvis, compared with two conventional internal fixation methods. Based on virtual anatomical measure of 30 digital pelvic models reconstructed from CT, an anatomic plate was designed according to the complicated structure of the outer table of the posterior ilium, and was integrated into the complete fixation system. Then, an ad hoc semi-automatic mesh generator was employed to construct a patient-specific finite element model of whole pelvis, including elaborate sacroiliac joints, important pelvic ligaments, and interpubic disc, as well as position-dependent cortical thickness and trabecular bone elastic modulus. Following, one side of sacroiliac joint related ligaments were deleted to simulate a complete unilateral sacroiliac joint disruption. Then the new anatomic fixation system was integrated to fix the fracture, and two comparing models including iliosacral screw fixation and front reconstruction plate fixation were also generated. Finally, all models were simulated under same loading conditions. The results demonstrated that the mechanical stability of the new anatomic fixation system was superior, with obviously improved stress distribution and little displacement, which implied an effective internal fixation method for potential clinical application.

We present a new parallel algorithm for interactive and continuous collision detection between deformable models. Our algorithm performs incremental hierarchical computations between successive frames and parallelizes the computation among multiple cores on current CPUs. The main computations include front building and updating and performing the elementary tests between the triangle primitives. The overall algorithm can perform inter- and intra-object collisions at interactive rates on current commodity processors on models with many tens of thousands of triangles. In practice, the performance of our algorithm almost scales linearly with the number of cores.

We present an interactive algorithm for continuous collision detection between deformable models. We introduce multiple techniques to improve the culling efficiency and the overall performance of continuous collision detection. First, we present a novel formulation for continuous normal cones and use these normal cones to efficiently cull large regions of the mesh as part of self-collision tests. Second, we introduce the concept of "procedural representative triangles" to remove all redundant elementary tests between nonadjacent triangles. Finally, we exploit the mesh connectivity and introduce the concept of "orphan sets" to eliminate redundant elementary tests between adjacent triangle primitives. In practice, we can reduce the number of elementary tests by two orders of magnitude. These culling techniques have been combined with bounding volume hierarchies and can result in one order of magnitude performance improvement as compared to prior collision detection algorithms for deformable models. We highlight the performance of our algorithm on several benchmarks, including cloth simulations, N-body simulations, and breaking objects.

We present an interactive algorithm for continuous collision detection between deformable models. We introduce two techniques to improve the culling efficiency and reduce the number of potentially colliding triangle candidate pairs. First, we present a novel formulation for continuous normal cones and use these normal cones to efficiently cull large regions of the mesh from self-collision tests. Second, we exploit the mesh connectivity and introduce the concept of orphan sets to eliminate almost all redundant elementary tests between adjacent triangles. In particular, we can reduce the number of elementary tests by many orders of magnitude. These culling techniques have been combined with bounding volume hierarchies and can result in one order of magnitude performance improvement as compared to prior algorithms for deformable models. We highlight the performance of our algorithm on several benchmarks, including cloth simulations, N-body simulations and breaking objects.

Mobile devices quickly become popular tools in collaborative design for their portability and supporting of graphics user interface. However, their limited resources may result in the complexity of rendering 3D products. Non-photorealistic rendering is extremely suitable for mobile devices since they efficiently save computational power and convey visual information. In this paper, a new approach is proposed to deal with mobile collaboration based on non-photorealistic rendering. In contrast to traditional methods, our method describes the user's design intent in an XML-based model, which is customizable and improves the collaboration between mobile users.

An efficient method for simulating cartoon style rain in 3D environment is proposed here. By taking advantage of the parallelism and programmability of GPUs (graphic processing units), real-time interaction can be achieved. Splashing of raindrop is simulated using collision detection, series of stylized textures and rotations of point sprites. To simulate wind-driven raining effect, the motion of particles can be freely controlled based on Newtonian dynamics. We can also control the size of raindrops dynamically by using different textures or changing the size of point sprites. Many experiments have been done in 3D scenes with different complexity and GPU-based stylized rendering. The experimental results demonstrated the efficiency of our method for real-time rain simulation in cartoon style with complex geometries of 3D scenes.

CAD systems increasingly require distributed collaborative design capabilities to meet the designers at different geographical locations to co-develop parts. It involves transmitting the CAD models back and forth among the systems in a distributed design environment. However, it is very difficult to apply because the CAD models are always very complex and the current network bandwidth is limited. In this paper, some important work about the compression and transmission of CAD models through the network is elaborated. Meanwhile, because a feature-based model always contains many extruded and revolved features, then we propose a new approach to transmission of feature-based models to deal with these extruded and revolved features. This approach can effectively cut down the transmission delay of the feature-based models, especially when the model contains many extruded and revolved features.

We present an efficient method for simulation of raining phenomenon in real time by taking advantage of the parallelism and programmability of GPU (graphic processing unit). Our implementation of the method is based on particle systems and collision detection. Splashing of raindrop is simulated using a series of stylized textures and rotations of point sprites. Taking into account human perception in raining phenomenon of real world, the effects such as light influence, depth of field, motion blur, have been applied. The test results show that our method is efficient and is feasible to solve the problem of 3D raining simulation in real time for more general environment with complex geometry.

This paper presents a novel algorithm for optimal packing problem by combining ant colony algorithm with BLF (bottom-left-fill) heuristic approach. The proposed algorithm not only automatically looks for the best sequence of the polygons and each polygon's optimum rotation by ant colony algorithm but also implements the exact layout with the BLF heuristic algorithm. Moreover, the algorithm supports the parallel computation and facilitates quick convergence to the optimal solution. The experimental results show the effectiveness of our algorithm comparing with the other methods.

Most of current collaborative feature modeling systems use the token-passing method as its collaborative strategy that makes the collaborative design between multi-clients inflexible and inefficient. Based on the analysis of feature operation in collaborative environment, we propose a new method to solve the concurrency conflicts, an enhanced naming mechanism for collaborative feature modeling to preserve the design intensions, and a process for non-locked multi-client collaborative design. The algorithms have been implemented in a prototype system integrating C++, Java3D and VML, CORBA technologies. Flexibility and efficiency in collaborative feature modeling environment have been achieved in our system.

Silhouettes play a critical role in non-photorealistic rendering. The effect of the NPR greatly depends on the silhouette performance. And it is also a key technology for real-time NPR applications. This paper introduces the most popular and latest techniques in silhouette detection. We classify and analyze them, and discuss them with the problem of visibility determination. After analyze the advantage and disadvantage of them, the working context of them is also concluded.

Geometric constraint solving is a rapidly developing field, with applications in areas such as kinematics, molecular modeling, surveying, and geometric theorem proving. This paper has incorporated conic arcs into a geometric constraint solver and describes how to construct conic blending arcs from constraints using a rational parametric representation - rational quadratic Bezier which combines the separate cases of blending edges. There are some possible constraints: traverse a fixed point, or tangency to or distance from a line. Here a uniform rational Bezier representation has been developed first, then the paper presents two methods to solve tangency to or distance from a line.

In this paper, a model and algorithm of optimum layout is proposed for blank layout of single pattern on single rectangular sheet. The approach arranges the cutting patterns on rectangular sheet in the typical style of Double Opposite Layout (DOL). The remains of the sheet, which has been left in one direction after arranging patterns, called as "Step Leavings" (SL) is considered while the optimum layout is discussed We make full use of material of the sheet, including the A in x-direction and y-direction, and set up a reasonable mathematical model for the two-dimensional optimum layout. A corresponding algorithm is also provided to work out the optimum layout quickly and automatically. In this way, we can get the best layout scheme to arrange the maximum shapes on the sheet.

Three-dimensional geometric constraint solving is a rapidly developing field, with applications in areas such as kinematics, molecular, modeling, surveying, and geometric theorem proving. While two-dimensional constraint solving has been studied extensively, there still remain many open questions in the arena of three-dimensional problems. We first introduce some techniques presented by (Hoffmann and Vermeer, 1995). The constraint system Hoffmann has studied consists of six geometric elements and pairwise constraints between triples of the elements. The core idea is to solve the geometric constraint template problems. Based on this, we continue to demonstrate how to solve a special template system composed of three points and three planes. This constraint system includes the angle constraints between two planes that are not discussed before.

Feature is the fundamental design unit in modern solid modeling systems, and this makes a well defined feature interface a matter of concernment in the component based distributed modeling environment. This paper introduces a feature based modeling service framework and proposes an interface model of feature based modeling service toward such a modeling environment, including support of remote feature attachment and semantic maintenance. A prototype based feature interface definition strategy using procedural attaching and declarative validation mechanism is discussed and how the interface model tackles with the problems in distributed environment, such as locality transparently model reusing, is also explained.

With the intensification of the competition in manufacture, the distributed technology, whose aim is to promote product design process, has changed the traditional CAD serial design approach. But the distributed design systems also bring some new problems such as design conflict. To avoid this inconsistent situation, there must be some coordination mechanisms. At the same time, these mechanisms must not constrain the freedom of the designers too much to take their creativity away. This paper introduces a feature-based distributed CAD system to support this collaborative work. We analyze the reason of the design conflict. For addressing this conflict, we present feature-based concurrency operation model. In such model, the feature is the basic atom that can be locked and excluded from other designers using. Comparing with part level concurrency system, this mechanism doesn't limit the design flexibility too much.

Shadow mapping has been a popular way of generating shadows in real-time applications, but it is still incapable of generating realistic real time soft shadows for area light. There is an algorithm for generating soft shadows for linear light with few samples, but the algorithm is not suitable for area light. The author presents a modified method to the shadow mapping algorithm for linear light. The new method can produce convincing soft shadows for area light in real time applications.

This paper proposes a virtual brush model based on droplet operation and its application on retrieving character outlines and character modeling in Chinese calligraphy style. In the proposed approach, a virtual brush model based on droplet operation is applied to produce vivid character outlines. The droplet model helps to compute stroke area with well-defined geometry information and leads to the feasibility to retrieve the outlines of characters with well-defined geometry representation. Further more, the variations of the model can express various Chinese brush styles, so by using the droplet model, we successfully overcome the poor expressive ability of the previous curve-offset method The complex evaluation of stroke area based on physical solid-model brush is also eliminated since the simplicity of the model.

We present the detailed modeling of the hairy brush used typically in Chinese calligraphy. The complex model, which includes also a model for the ink and the paper, covers the various stages of the brush going through a calligraphy process. The model relies on the concept of writing primitives, which are the smallest units of hair clusters, to reduce the load on the simulation. Each such primitive is constructed through the general sweeping operation in CAD and described by a NURBS surface. The writing primitives dynamically adjust themselves during the virtual writing process, leaving an imprint on the virtual paper as they move. The behavior of the brush is an aggregation of the behavior of all the writing primitives. A software system based on the model has been built and tested. Samples of imitation artwork from using the system were obtained and found to be nearly indistinguishable from the real artwork. Categories and Subject Descriptors (according to ACM CCS): I.3.6 [Methodology and Techniques]: Interaction techniques I.3.5 [Computational Geometry and Object Modeling]: Physically based modeling I.3.4 [Graphics Utilities]: Paint systems

In the field of computer graphics there is an increasing demand for non-photorealistic effects. We add the idea of pattern recognition guided by theoretical rules into a traditional NPR system and create non-photorealistic drawings intelligently. The Style Sample Library functions as an expert library and makes it easier to render a picture with nonphotorealistic effects even by an amateur user.

With the demand of distributed designers to cooperatively design a single product, these designers need to simultaneously access a common database, which holds the geometric model and other information of the product. But frequently, their design will lead to invalid results. Therefore, it is very important to build a distributed model to coordinate these designers to ensure the consistency of the product. The paper introduces a collaborative model to support this concurrent work. First, the architecture of this system is presented. Then a collaborative design model is described in detail. We analyze two reasons for the conflict and give two collaborative modes to coordinate the design process. These two modes can be used in different environments and can be used in a mixed way. So we can keep the consistency of the common solid model and maintain the maximal freedom of the designers at the same time. Finally, we give some design examples to further illustrate our model.

It is necessary to use libraries of parts when using CAD software. But, deficiencies and problems exist in most libraries, so we developed a part management system called GS-PM. Based on features, but not geometric information, it not only improves efficiency but also enables some applications of higher levels, for instance, the parts can be used in different CAD software. This part library can work in client/server mode to share information. It can also be applied to establish a customized visual part library (a Web part library), which can build parts dynamically according to the user's needs.

Feature based design is the main characteristic of current prevailing parametric solid modeling systems. By means of enabling users to build their own feature libraries, user defined features (UDF) provided as an extensional design method can overcome the shortcoming of inconvenience that exists in the traditional feature based modeling system. Traditional UDF representation is implemented either by procedural definition, which represents the features implicitly (J.J. Shah, 1991), or by an explicit representation or enumerative way (M.J. Pratt, 1989; M. Ranta and M. Mantyla, 1993). The paper proposes an innovative approach to the representation of UDFs by extending the common procedural UDFs' data structure with boundary features. Then a unified feature attachment interface is described. Thus, a unified representation of UDFs is introduced.

In this article we propose a hybrid modeling system based on B-rep model and volume model to overcome the inability of representing volume information of modeling object in conversional feature based modeling systems. Using this hybrid representation, we can easily solve the visualization and mass property computation for designing objects with specified volume attribute. In this article we propose a new method of converting B-rep models into volume models. This converting method is based on marching cube algorithm, and is optimized by octree algorithm. Using this converting method, we can efficiently convert the B-rep models into volume models. We also discuss the antialiasing technical on those volume models, we analyze different filters used for the voxelization of analytically described objects. To solve the visualization product problems in modeling systems, such as dynamic simulation, we present the methods of how to add Boolean operations on the hybrid modeling system to solve these problems. Voxelization enables uniform representation of all objects by a single primitive. Thus, instead of dealing with a number of different objects with specific features, dynamic simulation and dynamic interference on volume models only need simple calculations and is more efficient. We show that, using volume modeling, difficult problems in old modeling systems can be easily solved. The details of our algorithm are discussed in this article. We have implemented a volume modeling system based on our old feature based modeling system-GSCAD.