Research Projects

  • Intelligent processing of visual media, National Basic Research Program (973 program) of China, Project Number: 2006CB303100, 2006-2011.
  • Feature sensitive geometry processing, National Natural Science Foundation, Project number: 60673004, 2007-2009.
  • Geometric representation and rapair of scaned point clouds, National Natural Science Foundation, Project number: 60603085, 2007-2009.
  • Video procesing based on structure analysis, the Specialized Research Fund for the Doctoral Program of Higher Education, Project Number: 20060003057, 2007-2009.

    • Publications

    Technical Reports


    Online Video Stream Stylization
    Technical Report TR-090801. Tsinghua University, Beijing, China  
    Song-Hai Zhang, Xian-Ying Li, Shi-Min Hu, Ralph R. Martin

    This paper gives an automatic method for online video stream stylization, producing a temporally coherent output video stream. Our system transforms video into an abstract style with large regions of constant color and highlighted bold edges. Our system includes two novel components. Firstly, to provide coherent and simplified output, we segment frames, and use optical flow to propagate segmen tation information from frame to frame; an error control strategy is used to help ensure that the propagated information is reliable. Secondly, to achieve coherent and attractive coloring of the output, we use a color scheme replacement algorithm specifically designed for an online video stream. We demonstrate real-time performance, allowing our approach to be used for live communication, video games, and related applications.


    Video Presentation Board : A Semantic Visualization of Video Sequence
    Technical Report TR-081202. Tsinghua University, Beijing, China  
    Tao Chen, Ai-Dong Lu, Shi-Min Hu

    This paper presents a video summarization method to visualizing video sequences in a static image for the purposes of efficient representation and quick overview. It can assist viewers to understand important video contents by revealing essential information of video story units and their relations. We have designed a new method called Video Presentation Board to extract, organize, and synthesize important video information in a succinct and meaningful visual format, which also preserves the elegance of original videos.

    2009



    Sketch2Photo: Internet Image Montage
    ACM SIGGRAPH ASIA 2009, ACM Transactions on Graphics, Vol. 28, No. 5, Article No. 124   
    Tao Chen, Ming-Ming Cheng, Ping Tan, Ariel Shamir, Shi-Min Hu

    We present a system that composes a realistic picture from a user provided sketch with text labels. The composed picture is generated by seamlessly stitching several photographs automatically searched from internet according to the sketch and its text labels. While on line image search generates noisy results, our system can automat ically select suitable photographs to generate a high quality com position. To achieve this, we first design a filtering scheme to exclude undesirable images from searched results. Then we propose a novel image blending algorithm for seamless image composition. Our blending algorithm returns a numeric score for each blending, which is used to optimize the combination of searched images. Several vivid results are generated in the experiments. We also perform a user study to demonstrate the advantages of our system.


    Efficient Affinity-based Edit Propagation using K-D Tree
    ACM SIGGRAPH ASIA 2009, ACM Transactions on Graphics, Vol. 28, No. 5, Article No. 118    
    Kun Xu, Yong Li, Tao Ju, Shi-Min Hu, Tian-Qiang Liu

    Image/video editing by strokes has become increasingly popular due to the ease of interaction. Propagating the user inputs to the rest of the image/video, however, is often time and memory consuming especially for large data. We propose here an efficient scheme that allows affinity-based edit propagation to be computed on data containing tens of millions of pixels at interactive rate (in matter of seconds). The key in our scheme is a novel means for approximately solving the optimization problem involved in edit propagation, using adaptive clustering in a high-dimensional, affinity space. Our approximation significantly reduces the cost of existing affinitybased propagation methods while maintaining visual fidelity, and enables interactive stroke-based editing even on high resolution images and long video sequences using commodity computers.


    Simulating Gaseous Fluids with Low and High Speeds
    Computer Graphics Forum, Special issue of Pacific Graphics 2009, Vol. 28, No. 7, 1845-1852    
    Yue Gao, Chen-Feng Li, Shi-Min Hu, Brian A. Barsky

    Gaseous fluids may move slowly, as smoke does, or at high speed, such as occurs with explosions. High-speed gas flow is always accompanied by low-speed gas flow, which produces rich visual details in the fluid motion. Realistic visualization involves a complex dynamic flow field with both low and high speed fluid behavior. In computer graphics, algorithms to simulate gaseous fluids address either the low speed case or the high speed case, but no algorithm handles both efficiently. With the aim of providing visually pleasing results, we present a hybrid algorithm that efficiently captures the essential physics of both low- and high-speed gaseous fluids. We model the low speed gaseous fluids by a grid approach and use a particle approach for the high speed gaseous fluids. In addition, we propose a physically sound method to connect the particle model to the grid model. By exploiting complementary strengths and avoiding weaknesses of the grid and particle approaches, we produce some animation examples and analyze their computational performance to demonstrate the effectiveness of the new hybrid method.


    Edit Propagation on Bidirectional Texture Functions
    Computer Graphics Forum, Special issue of Pacific Graphics 2009, Vol. 28, No. 7, 1871-1877    
    Kun Xu, Jiaping Wang, Xin Tong, Shi-Min Hu, Baining Guo

    We propose an efficient method for editing bidirectional texture functions (BTFs) based on edit propagation scheme. In our approach, users specify sparse edits on a certain slice of BTF. An edit propagation scheme is then applied to propagate edits to the whole BTF data. The consistency of the BTF data is maintained by propagating similar edits to points with similar underlying geometry/reflectance. For this purpose, we propose to use view independent features including normals and reflectance features reconstructed from each view to guide the propagation process. We also propose an adaptive sampling scheme for speeding up the propagation process. Since our method needn’t any accurate geometry and reflectance information, it allows users to edit complex BTFs with interactive feedback.


    A Shape-Preserving Approach to Image Resizing
    Computer Graphics Forum, Special issue of Pacific Graphics 2009, Vol. 28, No. 7, 1897-1906  
    Guo-Xin Zhang, Ming-Ming Cheng, Shi-Min Hu, Ralph R. Martin

    We present a novel image resizing method which attempts to ensure that important local regions undergo a geometric similarity transformation, and at the same time, to preserve image edge structure. To accomplish this, we define handles to describe both local regions and image edges, and assign a weight for each handle based on an importance map for the source image. Inspired by conformal energy, which is widely used in geometry processing, we construct a novel quadratic distortion energy to measure the shape distortion for each handle. The resizing result is obtained by minimizing the weighted sum of the quadratic distortion energies of all handles. Compared to previous methods, our method allows distortion to be diffused better in all directions, and important image edges are well-preserved. The method is efficient, and offers a closed form solution.


    Generalized Discrete Ricci Flow
    Computer Graphics Forum, Special issue of Pacific Graphics 2009, Vol. 28, No. 7, 2005-2014    
    Yong-Liang Yang, Ren Guo, Feng Luo, Shi-Min Hu, Xianfeng Gu

    Surface Ricci flow is a powerful tool to design Riemannian metrics by user defined curvatures. Discrete surface Ricci flow has been broadly applied for surface parameterization, shape analysis, and computational topology. Conventional discrete Ricci flow has limitations. For meshes with low quality triangulations, if high conformality is required, the flow may get stuck at the local optimum of the Ricci energy. If convergence to the global optimum is enforced, the conformality may be sacrificed. This work introduces a novel method to generalize the traditional discrete Ricci flow. The generalized Ricci flow is more flexible, more robust and conformal for meshes with low quality triangulations. Conventional method is based on circle packing, which requires two circles on an edge intersect each other at an acute angle. Generalized method allows the two circles either intersect or separate from each other. This greatly improves the flexibility and robustness of the method. Furthermore, the generalized Ricci flow preserves the convexity of the Ricci energy, this ensures the uniqueness of the global optimum. Therefore the algorithm won’t get stuck at the local optimum. Generalized discrete Ricci flow algorithms are explained in details for triangle meshes with both Euclidean and hyperbolic background geometries. Its advantages are demonstrated by theoretic proofs and practical applications in graphics, especially surface parameterization.


    Automatic and Topology-Preserving Gradient Mesh Generation for Image Vectorization
    ACM SIGGRAPH 2009, ACM Transactions on Graphics, Vol. 28, No. 3, article 85    
    Yu-Kun Lai, Shi-Min Hu, Ralph R. Martin

    Gradient mesh vector graphics representation, used in commercial software, is a regular grid with specified position and color, and their gradients, at each grid point. Gradient meshes can compactly represent smoothly changing data, and are typically used for single objects. This paper advances the state of the art for gradient meshes in several significant ways. Firstly, we introduce a topology-preserving gradient mesh representation which allows an arbitrary number of holes. This is important, as objects in images often have holes, either due to occlusion, or their 3D structure. Secondly, our algorithm uses the concept of image manifolds, adapting surface parameterization and fitting techniques to generate the gradient mesh in a fully automatic manner. Existing gradient-mesh algorithms require manual interaction to guide grid construction, and to cut objects with holes into disk-like regions. Our new algorithm is empirically at least 10 times faster than previous approaches. Furthermore, image segmentation can be used with our new algorithm to provide automatic gradient mesh generation for a whole image. Finally, fitting errors can be simply controlled to balance quality with storage.


    Metric-Driven RoSy Fields Design
    IEEE Transaction on Visualization and Computer Graphics, 2009, to appear  
    Yu-Kun Lai, Miao Jin, Xuexiang Xie, Ying He, Jonathan Palacios, Eugene Zhang, Shi-Min Hu and Xianfeng David Gu

    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 indices of the singularities, 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. To demonstrate the effectiveness of our approach, we apply our design system to pen-and-ink sketching and geometry remeshing.


    Rapid and Effective Segmentation of 3D Models using Random Walks
    Computer Aided Geometric Design, 2008, Vol. 26, No. 6, 665-679.
    (An earlier version has been presented in ACM Symosium on Solid and Physical Modeling, June 2-4, 2008)
    Yu-Kun Lai, Shi-Min Hu, Ralph R. Martin and Paul L. Rosin

    3D mesh models are now widely available for use in various applications. The demand for automatic model analysis and understanding is ever increasing. Mesh segmentation is an important step towards model understanding, and acts as a useful tool for different mesh processing applications, e.g. reverse engineering and modeling by example. We extend a random walk method used previously for image segmentation to give algorithms for both interactive and automatic mesh segmentation. This method is extremely efficient, and scales almost linearly with increasing number of faces. For models of moderate size, interactive performance is achieved with commodity PCs. It is easy-to-implement, robust to noise in the mesh, and yields results suitable for downstream applications for both graphical and engineering models.


    Vectorizing Cartoon Animations
    IEEE Transaction on Visualization and Computer Graphics, 2009, Vol. 15, No. 4, May/June, 618-629  
    Song-hai Zhang, Tao Chen, Yi-Fei Zhang, Shi-Min Hu, Ralph R. Martin

    We present a system for vectorizing 2D raster format carton animations. The output animations are visually flicker free, smaller in file size, and easy to edit. We identify decorative lines separately from coloured regions. We use an accurate and semantically meaningful image decomposition algorithm which supports an arbitrary color model for each region. To ensure temporal coherence in the output cartoon, we reconstruct a universal background for all frames, and separately extract foreground regions. Simple user-assistance is required to complete the background. Each region and decorative line is vectorized and stored together with their motions from frame to frame.


    Video-Based Running Water Animation in Chinese Painting Style
    Science in China Series F: Information Sciences, 2009, Vol. 52, No. 2, 162-171   
    Song-hai Zhang, Tao Chen, Yi-Fei Zhang, Shi-Min Hu, Ralph R. Martin

    This paper presents a novel algorithm for synthesizing animations of running water, such as waterfalls and rivers, in the style of Chinese paintings, for applications such as cartoon making. All video frames are first registered in a common coordinate system, simultaneously segmenting the water from background and computing optical flow of the water. Taking artists’ advice into account, we produce a painting structure to guide painting of brush strokes. Flow lines are placed in the water following an analysis of variance of optical flow, to cause strokes to be drawn where the water is flowing smoothly, rather than in turbulent areas: this allows a few moving strokes to depict the trends of the water flows. A variety of brush strokes is then drawn using a template determined from real Chinese paintings. The novel contributions of this paper are: a method for painting structure generation for flows in videos, and a method for stroke placement, with the necessary temporal coherence.


    A new watermarking method for 3D model based on integral invariant
    IEEE Transaction on Visualization and Computer Graphics, 2009, Vol. 15, No. 2, March/April, 285-294   
    Yu-Ping Wang and Shi-Min Hu

    In this report, we propose a new semi-fragile watermarking algorithm for the authentication of 3D models based on integral invariants. To do so, we embed a watermark image by modifying the integral invariants of some of the vertices. Basically, we shift a vertex and its neighbors in order to change the integral invariants. To extract the watermark, test all the vertices for the embedded information, and combine them to recover the watermark image. How many parts can
    the watermark image be recovered would help us to make the authentication decision. Experimental test shows that this method is robust against rigid transform and noise attack, and useful to test purposely attack besides transferring noise and geometrical transforming noise. An additional contribution of this paper is a new algorithm for computing two kinds of integral invariants.


    Evaluation for Small Visual Difference Between Conforming Meshes on Strain Field
    Journal of Computer Science and Technology, 2009, Vol. 24, No. 1, 65-75   
    Zhe Bian, Shi-Min Hu and Ralph R Martin
    The preliminary version of this work has been presented on GMP2008.

    This paper gives a method of quantifying small visual differences between 3D mesh models with conforming topology, based on the theory of strain fields. Strain field is a geometric quantity in elasticity which is used to describe the deformation of elastomer. In this paper we consider the 3D models as objects with elasticity The further demonstrations are provided: the first is intended to give the reader a visual impression of how our measure works in practice; and the second is to give readers a visual impression of how our measure works in evaluating filter algorithms. Our experiments show that our difference estimates are well correlated with human perception of differences. This work has applications in the evaluation of 3D mesh watermarking, 3D mesh compression reconstruction, and 3D mesh filtering.

    2008



    Optimal Surface Parameterization Using Inverse Curvature Map
    IEEE Transaction on Visualization and Computer Graphics, 2008, Vol. 14, No. 5, Septmber/Octber, 1054-1066.   
    Yong-Liang Yang, Junho Kim, Feng Luo, Shi-Min Hu, and Xianfeng Gu

    Mesh parameterization is a fundamental technique in computer graphics. The major goals during mesh parameterization are to minimize both the angle distortion and the area distortion. Angle distortion can be eliminated by use of conformal mapping, in principle. Our paper focuses on solving the problem of nding the best discrete conformal mapping that also minimizes area distortion. Major theoretical results and practical algorithms are presented for optimal parameterization based on the inverse curvature map. Comparisons are conducted with existing methods and using different energies. Novel parameterization applications are also introduced. The theoretical framework of the inverse curvature map can be applied to further study discrete conformal mappings.


    Shrinkability Maps for Content-Aware Video Resizing
    Computer Graphics Forum, Special issue of Pacific Graphics 2008 , Vol. 27, No. 7, 1797-1804 .
    Yi-Fei Zhang,Shi-Min Hu, Ralph R. Martin

    A novel method is given for content-aware video resizing, i.e. targeting video to a new resolution (which may involve aspect ratio change) from the original. We precompute a per-pixel cumulative shrinkability map which takes into account both the importance of each pixel and the need for continuity in the resized result. (If both x and y resizing are required, two separate shrinkability maps are used, otherwise one suffices). A random walk model is used for efficient offline computation of the shrinkability maps. The latter are stored with the video to create a multi-sized video, which permits arbitrarysized new versions of the video to be later very efficiently created in real-time, e.g. by a video-on-demand server supplying video streams to multiple devices with different resolutions. These shrinkability maps are highly compressible, so the resulting multi-sized videos are typically less than three times the size of the original compressed video. A scaling function operates on the multi-sized video, to give the new pixel locations in the result, giving a high-quality content-aware resized video.

    An Incremental Approach to Feature Aligned Quad Dominant Remeshing
    ACM Symosium on Solid and Physical Modeling, June 2-4, 2008, 137-145.
    Yu-Kun Lai, Leif Kobbelt and Shi-Min Hu

    In this paper we present a new algorithm which turns an unstructured triangle mesh into a quad-dominant mesh with edges aligned to the principal directions of the underlying geometry. Instead of computing a globally smooth parameterization or integrating curvature lines along a tangent vector field, we simply apply an iterative relaxation scheme which incrementally aligns the mesh edges to the principal directions. The quad-dominant mesh is eventually obtained by dropping the not-aligned diagonals from the triangle mesh. A post-processing stage is introduced to further improve the results. The major advantage of our algorithm is its conceptual simplicity since it is merely based on elementary mesh operations such as edge collapse, flip, and split. The resulting meshes exhibit a very good alignment to surface features and rather uniform distribution of mesh vertices. This makes them very well-suited, e.g., as Catmull-Clark Subdivision control meshes.


    Fairing Wireframes in Industrial Design
    IEEE International Conference on Shape Modeling and Applications, June 4-6, 2008, 29-35.
    Yu-Kun Lai, Yong-Jin Liu, Yu Zang and Shi-Min Hu

    Wireframe is a modeling tool widely used in industrial geometric design. The term wireframe refers to two sets of curves, with the property that each curve from one set intersects with each curve from the other set. Akin to the u-, v-isocurves in a tensor-product surface, the two sets of curves in a wireframe span an underlying surface. In many industrial design activities, wireframes are usually set up and adjusted by the designers before the whole surfaces are reconstructed. For adjustment, the fairness of wireframe has a direct influence on the quality of the underlying surface. Wireframe fairing is significantly different from fairing individual curves in that intersections should be preserved and kept in the same order. In this paper, we first present a technique for wireframe fairing by fixing the parameters during fairing. The limitation of fixed parameters is further released by an iterative gradient descent optimization method with step-size control. Experimental results show that our solution is efficient, and produces reasonably fairing results of the wireframes.

    Shape Deformation using a Skeleton to Drive Simplex Transformations
    IEEE Transaction on Visualization and Computer Graphics, 2008, Vol. 14, No. 3, May/June, 693-706  
    Han-Bing Yan, Shi-Min Hu, Ralph R Martin, and Yong-Liang Yang
    The preliminary version of this work has been presented on CGI 2006

    This paper presents a skeleton-based method for deforming meshes (the skeleton need not be the medial axis). The significant difference from previous skeleton-based methods is that the latter use the skeleton to control movement of vertices whereas we use it to control the simplices defining the model. By doing so, errors that occur near joints in other methods can be spread over the whole mesh, via an optimization process, resulting in smooth transitions near joints of the skeleton. By controlling simplices, our method has the additional advantage that no vertex weights need be defined on the bones, which is a tedious requirement in previous skeleton-based methods. Furthermore, by incorporating the translation vector in our optimisation, unlike other methods, we do not need to fix an arbitrary vertex, and the deformed mesh moves with the deformed skeleton. Our method can also easily be used to control deformation by moving a few chosen line segments, rather than a skeleton.


    Spherical Piecewise Constant Basis Functions for All-Frequency Precomputed Radiance Transfer
    IEEE Transaction on Visualization and Computer Graphics, 2008, Vol. 14, No. 2, March/April, 454-467  
    Kun Xu, Yun-Tao Jia, Hongbo Fu, Shi-Min Hu and Chiew-Lan Tai

    This paper presents a novel basis function, called spherical piecewise constant basis function (SPCBF), for precomputed radiance transfer. SPCBFs have several desirable properties: rotatability, ability to represent all-frequency signals, and support for efficient multiple product. By partitioning the illumination sphere into a set of subregions, and associating each subregion with an SPCBF valued 1 inside the region and 0 elsewhere, we precompute the light coefficients using the resulting SPCBFs. We run-time approximate BRDF and visibility coefficients with the same set of SPCBFs through fast lookup of summed-area-table (SAT) and visibility distance table (VDT), respectively. SPCBFs enable new effects such as object rotation in all-frequency rendering of dynamic scenes and onthe-fly BRDF editing under rotating environment lighting. With graphics hardware acceleration, our method achieves real-time frame rates.

    Video: Download video here (13.0MB).

    2007



    Editing The Topology of 3D Models by Sketching
    ACM SIGGRAPH 2007, ACM Transactions on Graphics, Vol. 26, No. 3, Article 42, Publication date: July 2007.
    Tao Ju, Qian-Yi Zhou and Shi-Min Hu

    We present a method for modifying the topology of a 3D model with user control. The heart of our method is a guided topology editing algorithm. Given a source model and a user-provided target shape, the algorithm modifies the source so that the resulting model is topologically consistent with the target. Our algorithm permits removing or adding various topological features (e.g., handles, cavities and islands) in a common framework and ensures that each topological change is made by minimal modification to the source model. To create the target shape, we have also designed a convenient 2D sketching interface for drawing 3D line skeletons. As demonstrated in a suite of examples, the use of sketching allows more accurate removal of topological artifacts than previous methods, and enables creative designs with specific topological goals.

    Video: Download video here (31.8MB). (Cannot open the video? Cannot hear the audio? Get latest QuickTime player.)

    Software: A software MendIT based on this paper will come soon, please refer to webpage: http://graphics.usc.edu/~qianyizh/software.html


    Real-time homogeneous translucent material editing
    EuroGraphics 2007, Computer Graphics Forum, Vol. 26, No. 3, 545–552.
    Kun Xu, Yue Gao, Yong Li, Tao Ju and Shi-Min Hu

    This paper presents a novel method for real-time homogeneous translucent material editing under fixed illumination. We consider the complete analytic BSSRDF model proposed by Jensen et al.[JMLH01], including both multiple scattering and single scattering. Our method allows the user to adjust the analytic parameters of BSSRDF and provides high-quality, real-time rendering feedback. Inspired by recently developed Precomputed Radiance Transfer (PRT) techniques, we approximate both the multiple scattering diffuse reflectance function and the single scattering exponential attenuation function in the analytic model using basis functions, so that re-computing the outgoing radiance at each vertex as parameters change reduces to simple dot products. In addition, using a non-uniform piecewise polynomial basis, we are able to achieve smaller approximation error than using bases adopted in previous PRT-based works, such as spherical harmonics and wavelets. Using hardware acceleration, we demonstrate that our system generates images comparable to [JMLH01] at real-time frame-rates.

    Video: Download video here (17.3MB).


    Dynamic Delaunay tetrahedralisation of a deforming surface
    The Visual Computers, 2007, Vol. 23, No. 12, 975 - 986
    Jean-Baptiste Debard, Romain Balp, Raphaelle Chaine

    Reconstruction algorithms make it possible to retrieve a surface from the Delaunay tetrahedralisation (DT) of a point sampling, whose density reflects the surface local geometry and thickness. Most of these algorithms are static and some work remains to be done to handle deforming surfaces. In such case, we defend the idea that each point of the sampling should move with the surface using the information given by the motion to allow fast reconstruction. In this article, we tackle the problem of producing a good evolving sampling of a deforming surface S, and maintaining its DT along the motion. The surface is known only through a projection operator (O1) : R3 -> S, and a normal operator (O2) that returns the oriented normal at a point on the surface. On that basis, we offer some perspectives on how reconstruction algorithms can be extended to the tracking of deforming surfaces.

    Video: Download video here (16.2MB).


    Topology Repair of Solid Models Using Skeletons
    IEEE Transaction on Visualization and Computer Graphics, 2007, Vol. 13, July/August, 675-685.
    Qian-Yi Zhou, Tao Ju and Shi-Min Hu

    We present a method for repairing topological errors on solid models in the form of small surface handles, which often arise from surface reconstruction algorithms. We utilize a skeleton representation that offers a new mechanism for identifying and measuring handles. Our method presents two unique advantages over previous approaches. First, handle removal is guaranteed not to introduce invalid geometry or additional handles. Second, by using an adaptive grid structure, our method is capable of processing huge models efficiently at high resolutions.

    Slides: Download slides here (24.8MB). A poster for this paper is also available, download poster here (7.5MB).

    Software: A software TopoMender based on this paper is now available, please refer to webpage: http://graphics.usc.edu/~qianyizh/software.html



    Robust Feature Classification and Editing
    IEEE Transaction on Visualization and Computer Graphics, 2007, Vol. 13, No.1, January/Feburary, 34-45.
    Yu-Kun Lai, Qian-Yi Zhou, Shi-Min Hu, Johannes Wallner and Helmut Pottmann

    Sharp edges, ridges, valleys and prongs are critical for the appearance and an accurate representation of a 3D model. In this paper, we propose a novel approach that deals with the global shape of features in a robust way. Based on a remeshing algorithm which delivers an isotropic mesh in a feature sensitive metric, features are recognized on multiple scales via integral invariants of local neighborhoods. Morphological and smoothing operations are then used for feature region extraction and classification into basic types such as ridges, valleys and prongs. The resulting representation of feature regions is further used for feature-specific editing operations.



    Handling Degenerate Cases in Exact Geodesic Computation on Triangle Meshes
    The Visual Computers, 2007, Vol. 23, No. 9-11, 661-668.
    Yong-Jin Liu, Qian-Yi Zhou and Shi-Min Hu

    The computation of exact geodesics on triangle meshes is a widely used operation in computer-aided design and computer graphics. Practical algorithms for computing such exact geodesics have been recently proposed by Surazhsky et al (2005). By applying these geometric algorithms to real-world data, degenerate cases frequently appear. In this paper we classify and enumerate all the degenerate cases in a systematic way. Based on the classification, we present solutions to handle all the degenerate cases consistently and correctly. The common users may find the present techniques useful when they implement a robust code of computing exact geodesic paths on meshes.




    3D morphing using strain field interpolation
    Journal of Computer Science and Technology, 2007, Vol. 22, No. 1, 147-155.
    Han-Bing Yan, Shi-Min Hu, Ralph R Martin

    The computation of exact geodesics on triangle meshes is a widely used operation in computer-aided design and computer graphics. Practical algorithms for computing such exact geodesics have been recently proposed by Surazhsky et al (2005). By applying these geometric algorithms to real-world data, degenerate cases frequently appear. In this paper we classify and enumerate all the degenerate cases in a systematic way. Based on the classification, we present solutions to handle all the degenerate cases consistently and correctly. The common users may find the present techniques useful when they implement a robust code of computing exact geodesic paths on meshes.

    2006



    Reassembling Fractured Objects by Geometric Matching
    ACM Transactions on Graphics, Vol. 25, No. 3, 569-578. (ACM SIGGRAPH 2006)
    Qi-Xing Huang, Simon Flory, Natasha Gelfand, Michael Hofer and Helmut Pottmann

    We present a system for automatic reassembly of broken 3D solids. Given as input 3D digital models of the broken fragments, we analyze the geometry of the fracture surfaces to find a globally consistent reconstruction of the original object. Our reconstruction pipeline consists of a graph-cuts based segmentation algorithm for identifying potential fracture surfaces, feature-based robust global registration for pairwise matching of fragments, and simultaneous constrained local registration of multiple fragments. We develop several new techniques in the area of geometry processing, including the novel integral invariants for computing multi-scale surface characteristics, registration based on forward search techniques and surface consistency, and a non-penetrating iterated closest point algorithm.
    We illustrate the performance of our algorithms on a number of real-world examples.



    Geometric Modeling with Conical Meshes and Developable Surfaces
    ACM Transactions on Graphics, Vol. 25 , No. 3, 681-689. (ACM SIGGRAPH 2006)
    Yang Liu, Helmut Pottmann, Johannes Wallner, Yong-Liang Yang and Wenping Wang

    In architectural freeform design, the relation between shape and fabrication poses new challenges and requires more sophistication from the underlying geometry. The new concept of conical meshes satisfies central requirements for this application: They are quadrilateral meshes with planar faces, and therefore particularly suitable for the design of freeform glass structures. Moreover, they possess a natural offsetting operation and provide a support structure orthogonal to the mesh. Being a discrete analogue of the network of principal curvature lines, they represent fundamental shape characteristics. We show how to optimize a quad mesh such that its faces become planar, or the mesh becomes even conical. Combining this perturbation with subdivision yields a powerful new modeling tool for all types of quad meshes with planar faces, making subdivision attractive for architecture design and providing an elegant way of modeling developable surfaces.



    Geometry and Convergence Analysis of Algorithms for Registration of 3D Shapes
    Geometry and convergence analysis of algorithms for registration of 3D shapes, International Journal of Computer Vision, 2006, Vol. 67, No. 3, 277-296.
    Helmut Pottmann, Qi-Xing Huang, Yong-Liang Yang and Shi-Min Hu

    The computation of a rigid body transformation which optimally aligns a set of measurement points with a surface and related registration problems are studied from the viewpoint of geometry and optimization.We provide a convergence analysis for widely used registration algorithms such as ICP, using either closest points (Besl and McKay [2]) or tangent planes at closest points (Chen and Medioni [4]), and for a recently developed approach based on quadratic approximants of the squared distance function [24]. ICP based on closest points exhibits local linear convergence only. Its counterpart which minimizes squared distances to the tangent planes at closest points is a Gauss-Newton iteration; it achieves local quadratic convergence for a zero residual problem and { if enhanced by regularization and step size control { comes close to quadratic convergence in many realistic scenarios. Quadratically convergent algorithms are based on the approach in [24]. The theoretical results are supported by a number of experiments; there, we also compare the algorithms with respect to global convergence behavior, stability and running time.



    Surface Fitting Based on a Feature Sensitive Parameterization
    Computer-Aided Design, 2006, Vol. 38, No. 7, 800--807.
    Yu-Kun Lai, Shi-Min Hu and Helmut Pottmann

    Most approaches to least squares fitting of a B-spline surface to measurement data require a parametrization of the data point set and the choice of suitable knot vectors. We propose to use uniform knots in connection with a feature sensitive parametrization. This parametrization allocates more parameter space to highly curved feature regions and thus automatically provides more control points where they are needed.



    A Sweepline Algorithm for Euclidean Voronoi Diagram of Circles
    Computer-Aided Design, 2006, Vol. 38, No. 3, 260-278.
    Li Jin, Donguk Kim, Lisen Mu, Deok-Soo Kim and Shi-Min Hu

    Presented in this paper is a sweepline algorithm to compute the Voronoi diagram of a set of circles in a two-dimensional Euclidean space. The radii of the circles are non-negative and not necessarily equal. It is allowed that circles intersect each other, and a circle contains others. The proposed algorithm constructs the correct Voronoi diagram as a sweepline moves on the plane from top to bottom. While moving on the plane, the sweepline stops only at certain event points where the topology changes occur for the Voronoi diagram being constructed. The worst-case time complexity of the proposed algorithm is O((nCm)log n), where n is the number of input circles, and m is the number of intersection points among circles. As m can be O(n2), the presented algorithm is optimal with O(n2 log n) worst-case time complexity.



    Robust Principal Curvatures on Multiple Scales
    Proceedings of 4th Eurographics Symposium on Geometry Processing (2006). Eurographics Association, 223-226.
    Yong-Liang Yang, Yu-Kun Lai, Shi-Min Hu and Helmut Pottmann

    Geometry processing algorithms often require the robust extraction of curvature information. We propose to achieve this with principal component analysis (PCA) of local neighborhoods, defined via spherical kernels centered on the given surface F. Intersection of a kernel ball Br or its boundary sphere Sr with the volume bounded by F leads to the so-called ball and sphere neighborhoods. Information obtained by PCA of these neighborhoods turns out to be more robust than PCA of the patch neighborhood Br \F previously used. The relation of the quantities computed by PCA with the principal curvatures of F is revealed by an asymptotic analysis as the kernel radius r tends to zero. This also allows us to define principal curvatures “at scale r” in a way which is consistent with the classical setting. The advantages of the new approach are discussed in a comparison with results obtained by normal cycles and local fitting; whereas the former method somewhat lacks in robustness, the latter does not achieve a consistent behavior at features on coarse scales. As to applications, we address computing principal curves and feature extraction on multiple scales.



    Surface Mosaics
    In: Proceedings of Pacific Graphics, special issues of The Visual Computer, 2006, Vol. 22, No. 9-10, 604-611.
    Yu-Kun Lai, Shi-Min Hu and Ralph R. Martin

    This paper considers the problem of placing mosaic tiles on a surface to produce a surface mosaic. We assume that the user specifies a mesh model, the size of the tiles and the amount of grout, and optionally, a few control vectors at key locations on the surface indicating the preferred tile orientation at these points. From these inputs, we place equal-sized rectangular tiles over the mesh such as to almost cover it, with controlled orientation. The alignment of the tiles follows a vector field which is interpolated over the surface from the control vectors, and also forced into alignment with any sharp creases, open boundaries, and boundaries between regions of different colors. Our method efficiently solves the problem by posing it as one of globally optimizing a spring-like energy in the Manhattan metric, using overlapping local parameterizations.We demonstrate the effectiveness of our algorithm with various examples.



    Spherical Harmonics Scaling
    In: Proceedings of Pacific Graphics, special issues of The Visual Computer, 2006, Vol. 22, No. 9-10
    Jiaping Wang, Kun Xu, Kun Zhou, Stephen Lin, Shimin Hu and Baining Guo

    In this paper, we present a new SH operation, called spherical harmonics scaling, to shrink or expand a spherical function in frequency domain. We show that this problem can be elegantly formulated as a linear transformation of SH projections, which is efficient to compute and easy to implement on a GPU. Spherical harmonics scaling is particularly useful for extrapolating visibility and radiance functions at a sample point to points closer to or farther from an occluder or light source. With SH scaling, we present applications to low frequency shadowing for general deformable object, and to efficient approximation of spherical irradiance functions within a mid-range illumination environment.



    Feature Sensitive Mesh Segmentation
    ACM Symp. Solid and Physical Modeling, 7-16, 2006.
    Yu-Kun Lai, Qian-Yi Zhou, Shi-Min Hu and Ralph R. Martin

    Segmenting meshes into natural regions is useful for model understanding and many practical applications. In this paper, we present a novel, automatic algorithm for segmenting meshes into meaningful pieces. Our approach is a clustering-based top-down hierarchical segmentation algorithm. We extend recent work on feature sensitive isotropic remeshing to generate a mesh hierarchy especially suitable for segmentation of large models with regions at multiple scales. Using integral invariants for estimation of local characteristics, our method is robust and efficient. Moreover, statistical quantities can be incorporated, allowing our approach to segment regions with different geometric characteristics or textures.



    Rendering Soft Shadows using Multilayered Shadow Fins
    Computer Graphics Forum, 2006, Vol.25, No.1, 1-14.
    Xiao-Hua Cai, Yun-Tao Jia, Xi Wang, Shi-Min Hu and Ralph R. Martin

    Generating soft shadows in real-time is difficult. Exact methods (such as ray tracing, and multiple light source simulation) are too slow, while approximate methods often over-estimate the umbra regions. In this paper, we introduce a new algorithm based on the shadow map method to quickly and accurately render soft shadows produced by a light source. Our method builds inner and outer translucent fins on objects to represent the penumbra area inside and outside hard shadows respectively. The fins are traced into multi-layered light space maps to store illuminance adjustment to shadows. The viewing space illuminance buffer is then calculated using those maps. Finally, by blending illuminance and shading, a scene with highly accurate soft shadow effects is produced. Our method does not suffer from umbra over-estimation. Physical relations between light, objects, and shadows demonstrate the soundness of our approach.

    2005



    Video Completion using Tracking and Fragment Merging
    The Visual Computer, 2005, Vol. 21, No. 8-10, 601-601. (Pacific Graphics 2005)
    Yun-Tao Jia, Shi-Min Hu and Ralph R. Martin

    Video completion is the problem of automatically filling space-time holes in video sequences left by the removal of unwanted objects in a scene. We solve it using texture synthesis, filling a hole inwards using three steps iteratively: we select the most promising target pixel at the edge of the hole, we find the source fragment most similar to the known part of the target neighborhood, and we merge source and target fragments to complete the target neighborhood, reducing the size of the hole. Earlier methods were slow, due to searching the whole video data for source fragments or completing holes pixel by pixel; they also produced blurred results due to sampling and smoothing. For speed, we track moving objects, allowing us to use a much smaller search space when seeking source fragments; we also complete holes fragment by fragment instead of pixelwise. Fine details are maintained by use of a graph cut algorithm when merging source and target fragments. Further techniques ensure temporal consistency of hole filling over successive frames. Examples demonstrate the effectiveness of our method.



    Geometric texture synthesis and transfer via geometry images
    ACM Solid and Physical Modeling, MIT, USA, June 13-15, 2005, 15-26.
    Yu-Kun Lai, Shi-Min Hu, Xianfeng Gu, Ralph R. Martin

    In this paper, we present an automatic method which can transfer geometric textures from one object to another, and can apply a manually designed geometric texture to a model. Our method is based on geometry images as introduced by Gu et al. The key ideas in this method involve geometric texture extraction, boundary consistent texture synthesis, discretized orientation and scaling, and reconstruction of synthesized geometry. Compared to other methods, our approach is efficient and easy-to-implement, and produces results of high quality.

    Other publications in 2005

    1. Xu-Ping Zhu, Shi-Min Hu, Chiew-Lan Tai, and Ralph R Martin, A Marching Method for Computing Intersection Curves of Two Subdivision Solids, in Mathematics of Srufaces XI, Eds. R. R. Martin, H. Bez, M. A. Sabin, 458-471, 2005.
    2. Johannes Wallner, Hans-Peter Schrocker, Shi-min Hu, Tolerance in geometric constraints solving, Reliable Computing, 2005, Vol. 11, No. 3, 235-251.
    3. Shi-min Hu, Johannes Wallner, A second order algorithm for orthogonal projection onto curves and surfaces, Computer Aided Geometric Design, 2004, Vol.22, No. 3, 251-260.
    4. Qi-Xing Huang, Shi-Min Hu and Ralph R. Martin, Fast degree elevation and knot insertion for B-spline curves, Computer Aided Geometric Design, 2005, Vol 22, No. 2, 183-197.

    2004



    Generalized Displacement Maps
    Proceedings of Eurographics Symposium on Rendering, 2004
    Xi Wang, Xin Tong, Stephen Lin, Shimin Hu, Baining Guo and Heung-Yeung Shum

    In this paper, we introduce a real-time algorithm to render the rich visual effects of general non-height-field geometric details, known as mesostructure. Our method is based on a five-dimensional generalized displacement map (GDM) that represents the distance of solid mesostructure along any ray cast from any point within a volumetric sample. With this GDM information, we propose a technique that computes mesostructure visibility jointly in object space and texture space which enables both control of texture distortion and efficient computation of texture coordinates and shadowing. GDM can be rendered with either local or global illumination as a per-pixel process in graphics hardware to achieve real-time rendering of general mesostructure.

    Other publications in 2004

    1. Han-Bing Yan, Shi-Min Hu, Ralph R. Martin, Morphing Based on Strain Field Interpolation, Journal of Computer Animation and Virtual Worlds (CAVW), 2004, Vol.15, No.3-4, 443-452.
    2. Shi-min Hu, Johannes Wallner, Error Propagation through Geometric Transformations, Journal for Geometry and Graphics, 2004, Vol.8, No.2, 171-183.
    3. Shi-Min Hu, Chen-feng Li, Hui Zhang, Actual Morphing: A phsical-based approach for blending two 2D/3D shapes, ACM Symposium on Solid Modeling and Applications, Genova, Italy, June 9-11, 2004.

    2003



    Interactive Modeling of Tree Bark
    In: Proceedings of Pacific Graphics 2003, IEEE CS Press, Oct 8-10, 2003
    Xi Wang, Lifeng Wang, Ligang Liu, Shi-Min Hu and Baining Guo

    There exist many computer graphics techniques which could achieve high quality tree generation. However, only a few works focus on realistic modeling of tree bark. Difficulties lie in the complex appearance of the bark surfaces which are largely determined by their mesostructures. Unlike traditional physical based methods, in this paper, we present an appearance-based method to model tree bark surfaces from a single image. We address three main issues here: feature specification, height field assignment and texture correction. For feature specification, we use texton channel analysis to specify a variant of common bark features, including ironbark, vertical and horizontal fractures, tessellation, furrowed cork, and lenticels. For height field assignment, we develop an intuitive and easy-to-use user interface (UI). Here similarity-based texture editing is used for assigning height fields within a texton channel mask. For texture correction, we use the modeled height fields to eliminate the underlying lighting effects in a captured texture. Our modeling system is image-based: it takes as input a bark image and produces as output a textured height field representing a bark sample. We demonstrate that our method is an effective and easy-to-use technique to interactively model a variety of photo realistic bark surfaces.



    View-Dependent Displacement Mapping
    In: Proceedings of SIGGRAPH 2003, ACM Transaction on Graphics, Vol. 22, No. 3. 334-339.
    Lifeng Wang, Xi Wang, Xin Tong, Steve Lin, Shimin Hu, Baining Guo and Heung-Yeung Shum

    Significant visual effects arise from surface mesostructure, such as fine-scale shadowing, occlusion and silhouettes. To efficiently render its detailed appearance, we introduce a technique called viewdependent displacement mapping (VDM) that models surface displacements along the viewing direction. Unlike traditional displacement mapping, VDM allows for efficient rendering of selfshadows, occlusions and silhouettes without increasing the complexity of the underlying surface mesh. VDM is based on per-pixel processing, and with hardware acceleration it can render mesostructure with rich visual appearance in real time.

    Other publications in 2003

    1. Xu-Ping Zhu, Shi-Min Hu and Martin Ralph, Skeleton-Based Seam Computation for Triangulated Surface Parameterization, In Proceedings of Mathematics in Surfaces X, Sept 2003, Leeds, UK; Lecture Notes in Computer Science, 2003. [PS]
    2. Chiew-Lan Tai, Hu Shi-Min and Qixing Huang, Approximate merging of B-Spline curves via knot adjustment and constrained optimization, Computer Aided Design, 2003, Vol. 35, No. 10, 893 - 899.
    3. Tao Wang, Yong Rui, Shi-Min Hu and Jia-guang Sun, Adaptive tree similarity learning for image retrieval, Multimedia Systems, 2003, Vol. 9, 131-143.

    2002

    1. Shi-Min Hu, Chiew-Lan Tai, Song-Hai Zhang, An Extension algorithm for B-spline curves by curve unclamping, Computer Aided Design, 2002, Vol. 34, No. 5, 415-4191.
    2. Yan-Tao Li, Shi-Min Hu and Jia-Guang Sun, A Constructive Approach to Solving 3-D Geometric Constraint Systems Using Dependence Analysis, Computer Aided Design, 2002, Vol. 34, No. 2, 97-108.
    3. Liu Shi-Xia, Hu Shi-Min, Sun Jiaguang, Two accelerating techniques for 3D reconstruction, Journal of Computer Science and Technology, 17(3), 362-368, 2002.


    2001

    1. Shi-Xia Liu, Shi-Min Hu, Yu-Jian Chen, Jia-Guang Sun, Reconstruction of curved solids from engineering drawings, Computer Aided Design, 2001, Vol. 33, No. 14, 1059-1072.
    2. Shi-Min Hu, Youfu Li, Tao JU, Xiang Zhu, Modifying the shape of NURBS surfaces with geometric constraints, Computer Aided Design, 2001, Vol. 33, No. 12, 903-912.
    3. Shi-Min, Hu Conversion between triangular and rectangular Bezier patches, Computer Aided Geometric Design, 2001, Vol.18, No. 7, 667-671. (In Special issue of memory of P. Bezier).
    4. Shi-Min Hu, Hui Zhang, Chiew-Lan Tai, Jia-Guang Sun, Direct Manipulation of FFD: Efficient Explicit Solutions and Decomposible Multiple Point Constraints, The Visual Computers, 2001, Vol. 17, No. 6, 370-379.
    5. Jun-Hai Yong, Shi-Min Hu, Jia-Guang Sun, Degree reduction of B-spline curves, Computer Aided Geometric Design, 2001, Vol. 13, NO. 2, 2001, 117-127.
    6. Shi-Min Hu, Ruofeng Tong, Tao JU, Jia-Guang Sun, Approximate merging of a pair of Bezier curves, Computer Aided Design, Vol 33, No. 2, 125-136, 2001.
    7. Jun-Hai Yong, Shi-Min Hu, JIa-Guang Sun, CIM Algorithm for Approximating Three Dimensional Polygonal Curves, Journal of Computer Science and Technology, 16(6), 489-497,2001.
    8. Tao Wang, Yong Rui and Shi-Min Hu, Optimal Adaptive Learning for Image Retrieval, Proceedings of IEEE Computer Vision and Pattern Recognition (CVPR 2001), I-1140 to 1147, Kauai, Hawaii, December 11-13, 2001.
    9. Yan-Tao Li, Shi-Min Hu, Jia-Guang Sun, On the numerical redundancies of geometric constraint systems, Proceedings of Pacific Graphics 2001, 118-123, IEEE Computre Society Press, 2001, Tokyo.
    10. Jian-Hua Wu, Shi-Min Hu, Chiew-Lan Tai and Jia-Guang Sun, An effective feature-preserving mesh simplification scheme based on face constriction, Proceedings of Pacific Graphics 2001, 12-21, IEEE Computre Society Press, 2001, Tokyo.