Abstract Crowd simulators are commonly used to populate movie or game scenes in the entertainment industry. Even though it is crucial to consider the presence of groups for the believability of a virtual crowd, most crowd simulations only take into account individual characters or a limited set of group behaviors. We introduce a unified solution that allows for simulations of crowds that have diverse group properties such as social groups, marches, tourists and guides, etc. We extend the Velocity Obstacle approach for agent‐based crowd simulations by introducing Velocity Connection; the set of velocities that keep agents moving together while avoiding collisions and achieving goals. We demonstrate our approach to be robust, controllable, and able to cover a large set of group behaviors.

Association rules have been widely used for detecting relations between attribute-value pairs of categorical datasets. Existing solutions of mining interesting association rules are based on the support-confidence theory. However, it is non-trivial for the user to understand and modify the rules or the results of intermediate steps in the mining process, because the interestingness of rules might differ largely for various tasks and users. In this paper we propose to reinforce conventional association rule mining process by mapping the entire process into a visualization assisted loop, with which the user workload for modulating parameters and mining rules is reduced, and the mining efficiency is greatly improved. A matrix-based visualization technique is employed to encode the measure computation value, the data distribution and the intermediate results. We also design a set of visual exploration tools to support interactively inspection and manipulation of association measures, constraints of different types, and the results of intermediate steps. The effectiveness of our approach is demonstrated with various scenarios.

The state search is an important component of any object tracking algorithm. Numerous algorithms have been proposed, but stochastic sampling methods (e.g., particle filters) are arguably one of the most effective approaches. However, the discretization of the state space complicates the search for the precise object location. In this paper, we propose a novel tracking algorithm that extends the state space of particle observations from discrete to continuous. The solution is determined accurately via iterative linear coding between two convex hulls. The algorithm is modeled by an optimal function, which can be efficiently solved by either convex sparse coding or locality constrained linear coding. The algorithm is also very flexible and can be combined with many generic object representations. Thus, we first use sparse representation to achieve an efficient searching mechanism of the algorithm and demonstrate its accuracy. Next, two other object representation models, i.e., least soft-threshold squares and adaptive structural local sparse appearance, are implemented with improved accuracy to demonstrate the flexibility of our algorithm. Qualitative and quantitative experimental results demonstrate that the proposed tracking algorithm performs favorably against the state-of-the-art methods in dynamic scenes.

The art of visual tracking has been widely studied in the past decades [6]. While most of researches focus on exploring new methods to represent object appearance, little attention has been paid on the description of object motion. In this paper we propose a novel motion model for visual tracking, and in comparison with previous methods, it can better parameterize instantaneous image motion caused by both object and camera movements. Our approach is inspired by the subspace theory of image motion, that is, for a rigid object imaged by a projective camera, the displacements matrix of its trajectories over a short period of time should approximately lie in a low-dimensional subspace with a certain rank upper bound [2, 5]. We adopt this subspace as the state transition space in particle filtering (PF) [3]. This differs from affine model in two ways: first, the dimension number as well as the sampling weight for each dimension at each moment can be determined by the rank of the subspace automatically; second, the subspace motion model can naturally represent the disparity brought by object or camera rotation. We will show that when compared with the affine model, the subspace motion model is superior in accuracy. Figure 1 illustrates the procedures of our method. To estimate the motion model, some 2D feature points of the object are first tracked by the standard KLT approach [4]. Assuming that k successive frames have been tracked before the current frame It , then the displacements matrix can be built as:

Tensor field design plays an essential role in various computer graphics applications. One of the main challenges in field design is how to obtain a smooth field preserving meaningful singularities presented in the original scene. Compared with well-studied point singularities, line singularities, commonly occur on object boundaries and occluding contours, are not exploited enough for field design in previous work. In this paper, we discuss the definition of line singularities, and introduce a line-singularity-based interactive tensor field design method, allowing the user to design feature-preserving tensor fields with less effort and to preserve both input singularities and user-specified stroke directions. To avoid introducing extra interaction burdens to the user, our method automatically locates line singularities using a geodesic-based segmentation. We demonstrate the capabilities of our method on tensor field design with various nonphotorealistic rendering applications and the real-time performance accelerated on GPU.

With the strong demand for human machine interaction, action recognition has attracted more and more attention in recent years. Traditional video-based approaches are very sensitive to background activity, and also lack the ability to discriminate complex 3D motion. With the emergence and development of commercial depth cameras, action recognition based on 3D skeleton joints is becoming more and more popular. However, a skeleton-based approach is still very challenging because of the large variation in human actions and temporal dynamics. In this paper, we propose a hierarchical model for action recognition. To handle confusing motions in a large feature space, a motion-based grouping method is first proposed, which can efficiently assign each video a group label, and then for each group, a pre-trained classifier is used for frame-labeling. Unlike previous methods, we adopt a bottom-up approach that first performs action recognition for each frame. The final action label is obtained by fusing the classification to its frames, with the effect of each frame being adaptively adjusted based on its local properties. The proposed method is evaluated using two challenge datasets captured by a Kinect. Experiments show that our method can perform more robustly than state-of-the-art approaches.

Abstract We propose a novel approach to simulate the illumination of augmented outdoor scene based on a legacy photograph. Unlike previous works which only take surface radiosity or lighting related prior information as the basis of illumination estimation, our method integrates both of these two items. By adopting spherical harmonics, we deduce a linear model with only six illumination parameters. The illumination of an outdoor scene is finally calculated by solving a linear least square problem with the color constraint of the sunlight and the skylight. A high quality environment map is then set up, leading to realistic rendering results. We also explore the problem of shadow casting between real and virtual objects without knowing the geometry of objects which cast shadows. An efficient method is proposed to project complex shadows (such as tree's shadows) on the ground of the real scene to the surface of the virtual object with texture mapping. Finally, we present an unified scheme for image composition of a real outdoor scene with virtual objects ensuring their illumination consistency and shadow consistency. Experiments demonstrate the effectiveness and flexibility of our method.

ABSTRACT Because existing image abstraction systems can hardly incorporate with the changing light, we present an integrated image abstraction and relighting rendering system, which is based on a salient edge‐guided luminance field optimization approach. For an input image, we first adopt a sparsity prior‐based illumination decomposition method to remove its original illumination and have an intrinsic image. Meanwhile, we iteratively extract the salient edge inside by employing a message‐passing strategy. Then, we simplify this image with a proposed salient edge‐guided image abstraction optimization algorithm in the luminance field. Finally, we put forward a salient edge‐guided image relighting optimization method to simulate the effect of dynamic lighting along different directions. Experiment results show that our system can artistically adjust the illumination of the abstracted image and makes it more vivid. Copyright © 2013 John Wiley & Sons, Ltd.

ABSTRACT The establishment of trust relations is recognized as an important approach to initiate cooperation between unfamiliar entities in distributed computing environments. Particularly, trust relations can play a key role to help nodes make decisions on service discoveries in wireless environments. Visualizing trust relations can help us understand and analyze the real‐time threats that the distributed system is facing and consequently identify the attacks in order to deploy corresponding countermeasures. The main challenges to visualize trust in such distributed environments are as follows: (i) visually reorganizing and presenting trust relations to show underlying cooperation between attackers; (ii) mapping attacker behaviors to visual patterns in an ambiguity‐free manner; (iii) properly organizing and encoding other contextual information to analyze how these factors play along with trust. In this paper, we introduce TrustVis, a tool that helps users visually analyze trust relations to identify attacks in a semi‐automatic fashion. In parallel with a running trust evaluation engine that actively monitors trust relations, TrustVis reorganizes and presents trust relations with a matrix to map the cooperative attack schemes to visual patterns. By coordinating the trust matrix and other contextual information into a multi‐faceted view, TrustVis incorporates the intelligence of domain experts to interactively monitor the networked system toward identifying both the attackers' identities and the adopted attack schemes. Copyright © 2012 John Wiley & Sons, Ltd.

Graph is an intuitive and powerful tool to present relationships between entities. Efficiently visualizing graphs with node-link diagrams is a great challenge due to visual clutter induced by edge crossing and node-edge overlapping. Many edge bundling methods are proposed to disclose high-level edge patterns. Though previous methods can successfully reveal the coarse graph structure, the relation patterns at individual node level can be overlooked. In addition, many edge bundling algorithms are computationally complex to prevent them from scaling up for extremely large graphs. In this paper, we propose SideKnot, an efficient node-based bundling method to cluster and knot edges. SideKnot is light, runs faster than most existing algorithms, and can disclose the relation patterns of an individual node such as its standing in the graph and pattern of relations with its neighbors.

ABSTRACT Creating an attractive mesh animation is a laborious and time‐consuming task. In this paper, we propose a practical deformation transfer algorithm to make it easier. To achieve a robust numerical solver, we perform the transfer process in the dual domain; that is, the deformations are transferred between the dual meshes of the source and target meshes. Firstly, the source animation is analyzed and visualized to help the user specify markers in the large deformation regions. Then, through respecting the coherence information, a fast and deformation‐aware surface correspondence approach is presented to determine how the source animation is transferred. Finally, the transferred result can be reconstructed via dual Laplacian optimization. Various experimental results demonstrate the effectiveness and applicability of this paper. Moreover, a user study is carefully designed to perceptually validate our motivation and advantages. Copyright © 2012 John Wiley & Sons, Ltd.

Existing video object cutout systems can only deal with limited cases. They usually require detailed user interactions to segment real-life videos, which often suffer from both inseparable statistics (similar appearance between foreground and background) and temporal discontinuities (e.g. large movements, newly-exposed regions following disocclusion or topology change). In this paper, we present an efficient video cutout system to meet this challenge. A novel directional classifier is proposed to handle temporal discontinuities robustly, and then multiple classifiers are incorporated to cover a variety of cases. The outputs of these classifiers are integrated via another classifier, which is learnt from real examples. The foreground matte is solved by a coherent matting procedure, and remaining errors can be removed easily by additive spatio-temporal local editing. Experiments demonstrate that our system performs more robustly and more intelligently than existing systems in dealing with various input types, thus saving a lot of user labor and time.

The articles in this special section contain selected papers from the 2010 ACM Virtual Reality Software and Technology Symposium.

We introduce a non-uniform composition that integrates multiple rendering styles in a picture driven by an importance map. This map, either issued from saliency estimation or designed by a user, is introduced both in the creation of the multiple styles and in the final composition. Our approach accommodates a variety of stylization techniques, such as color desaturation, line drawing, blurring, edge-preserving smoothing and enhancement. We illustrate the versatility of the proposed approach and the variety of rendering styles on different applications such as images, videos, 3D scenes and even mixed reality. We also demonstrate that such an approach may help in directing user attention.

While many approaches have been developed to visualize 3D city scenes, most of them exhibit the visualization results in a uniform rendering style. This paper presents an expressive rendering approach for visualizing large-scale 3D city scenes with various rendering styles integrated in a seamless way. Each view is actually a combination of the photorealistic rendering, the nonphotorealistic rendering, and the line drawing, so as to highlight the information that is interesting for the users and de-emphasize the other that is less important. At run-time, the users are allowed to specify their interested locations with pre-determined 3D landmarks. Our system automatically computes the salience of each location and visualize the entire scene with emphasis in the area of interests. The GPU-based implementation enables real-time performance, and demonstrates outstanding practicality.

Many applications involve map visualization. Nevertheless, almost all of them display the map in the same style, which often cause information overloading. In this paper, we present a novel user-centered 2.5D focus context map visualization technique. Instead of treating all the information equally, we can custom the map according to user requirements. The main contributions of our technique are in three aspects. Firstly, our system can automatically construct a hierarchical representation of the city according to the focus point of the users by using the R-trees data structure, then presenting users the map in multiple rendering styles, highlighting the user concerned information and deemphasizing the less important information. Secondly, a landmark margin is automatically added to the original map according to the points-of-interest(POI), which illustrates the context information and enables users to maintain a macro view of the city. Moreover, by applying the 2.5D technique, we can reduce the amount of data and accelerate the transport of the information. The results show that our user-centered map visualization technique can greatly improve the efficiency for users to get their concerned information.

In augmented reality, consistent illumination plays an important role when integrating a virtual object into a video of real scene. In this paper, we propose a novel image based framework to estimate-on-line the dynamic ally changing illumination parameters of outdoor video sequences captured by a fixed camera. Unlike previous approaches which either request to know the scene geometry or involve huge storage to preserve time dependent basis images or statistic parameters, our approach requires very simple interaction at the initialization stage by a few brushes to select areas with specified surface normal, which are used to calculate the sunlight parameters. An optimization procedure is also applied, ensuring the robustness and precision of our estimation. Experimental results demonstrate the effectiveness and flexibility of the proposed approach.

Automatic segmentation without any user interaction is very difficult due to potentially high complexity of the scene. No wonder, most existing segmentation algorithms are based on user interactions. However, automatic segmentation in some special situations has great significance. In this paper, we introduce an automatic segmentation algorithm for frontal head-and-shoulder images. Our algorithm combines edge feature and shape prior to extract the foreground silhouette automatically. The novelty of our approach lies in two aspects, namely, the Cost Path Segmentation (CPS) algorithm to extract the initial foreground silhouette, and a general active prior shape model, to extract the final foreground segmentation. We demonstrate the high quality and performance of the proposed approach with a variety of head-and-shoulder images. Compared with previous methods, our approach is much more robust for images with complex color distributions in foreground and background.

This paper presents a real-time foveation rendering algorithm to simulate the gaze contingent vision of a 3Dscene. The novelty of our approach lies in two aspects, namely, an image-space adaptive sampling mask adhering to the Contrast Sensitivity Function (CSF) of the HVS, an image based multi-layer representation of the 3D scene constructed by depth peeling. We demonstrate high quality and performance of the proposed approach with a variety of examples, and provide comparisons with recent methods.

Simulating the local behavior of small pedestrian groups among a crowd is an emerging problem. Small groups are commonly found in general crowds and their behavior are significantly distinguished from that of individual pedestrians. In this paper, we propose a novel approach to simulate the walking behavior of such small groups. We construct dynamic group formations which not only facilitate easy communication between members within the same group but also adapt to the environment constraint. Moreover, an extended collision avoidance algorithm based on Optimal Reciprocal Collision Avoidance (ORCA) is proposed taking into account the factors of group cohesion and reaction flexibility so as to generate diverse interaction behavior between walkers. Several examples demonstrate the efficiency of the proposed algorithm.

In this paper, we propose a robust deformation transfer algorithm. Unlike previous work, the transfer process is performed in the dual domain, i.e., the deformations are transferred between the dual meshes of the source and target meshes. Firstly, the source mesh sequence and the target mesh are converted to their dual meshes. Then the source animation is analyzed and represented as a set of affine transformations. After the surface correspondence is built, the transferred result can be reconstructed by dual Laplacian optimization. The experimental results demonstrate that our algorithm is simple but very effective.

ABSTRACT The seamless integration of virtual characters into dynamic scenes captured by video is a challenging problem. In order to achieve consistent composite results, both the virtual and real characters must share the same geometrical constraints and their interactions must follow some common sense. One essential question is how to detect the motion of real objects—such as real characters moving in the video—and how to steer virtual characters accordingly to avoid unrealistic collisions. We propose an online solution. First, by analysis of the input video, the motion states of the real pedestrians are recovered into a common world 3D coordinate system. Meanwhile, a simplified accuracy measurement is defined to represent the confidence of the motion estimate. Then, under the constraints imposed by the real dynamic objects, the motion of virtual characters are accommodated by a uniform steering model. The final step is to merge virtual objects back to the real video scene by taking into account visibility and occlusion constraints between real foreground objects and virtual ones. Several examples demonstrate the efficiency of the proposed algorithm. Copyright © 2011 John Wiley & Sons, Ltd.

To date, comparing and visualizing genome sequences remain challenging due to the large genome size. Existing approaches take advantage of the stable property of oligonucleotides and exhibit the main characteristics of the whole genome, yet they commonly fail to show progression patterns of the genome adjustably. This paper presents a novel visual encoding technique, which not only supports the binning process (phylogenetic analysis), but also allows the sequential analysis of the genome. The key idea is to regard the combination of each k -nucleotide and its reverse complement as a visual word, and to represent a long genome sequence with a list of local statistical feature vectors derived from the local frequency of the visual words. Experimental results on a variety of examples demonstrate that the presented approach has the ability to quickly and intuitively visualize DNA sequences, and to help the user identify regions of differences among multiple datasets.

Online foreground extraction is very difficult due to the complexity of real scenes. Almost all the previous methods assume that the background is stationary, which not only incur unreliable result due to background activities like dynamic shadow, moving background objects etc., but also makes them hard to be extended to the case of non-stationary background. In this paper we assume that the background is continuous instead of stationary, and present a transductive video segmentation method that can handle dynamic scenes captured by a hand-held moving camera. The segmentation is propagated based on local color models and temporal prior, as well as a dynamic global color model (DGKDE) in the case of occlusion. A novel local color modeling method, FLKDE, is proposed to model both local color distribution and temporal prior at each pixel. FLKDE can be learned additively to reach real-time speed. Finally, a very fast geodesic-based method is adopted to solve for the segmentation. Experiments show that our method can generate good quality segmentation for wide variety of scenes, and can reach 15~25 fps for 640 × 480 size of input image sequences.

We introduce an on-line framework for the visualizing of underground structures that improves X-Ray vision and Focus and Context Rendering for Augmented Reality. Our approach does not require an accurate reconstruction of the 3D environment and runs on-line on modern hardwares. For these purposes, we extract characteristic features from video frames and create visual cues to reveal occlusion relationships. To enhance the perception of occluding order, the extracted features are either directly rendered, or used to create hybrid blending masks: we thus ensures that the resulting cues are clearly noticeable.

Abstract Illumination consistency plays an important role in realistic rendering of virtual characters which are integrated into a live video of real scene. This paper proposes a novel method for estimating the illumination conditions of outdoor videos captured by a fixed viewpoint. We first derive an analytical model which relates the statistics of an image to the lighting parameters of the scene adhering to the basic illumination model. Exploiting this model, we then develop a framework to estimate the lighting conditions of live videos. In order to apply the above approach to scenes containing dynamic objects such as intrusive pedestrians and swaying trees, we enforce two constraints, namely spatial and temporal illumination coherence, to refine the solution. Our approach requires no geometric information of the scenes and is sufficient for real‐time performance. Experiments show that with the lighting parameters recovered by our method, virtual characters can be seamlessly integrated into the live video. Copyright © 2010 John Wiley & Sons, Ltd.

In this paper, we introduce a feature-preserving denoising algorithm. It is built on the premise that the underlying surface of a noisy mesh is piecewise smooth, and a sharp feature lies on the intersection of multiple smooth surface regions. A vertex close to a sharp feature is likely to have a neighborhood that includes distinct smooth segments. By defining the consistent subneighborhood as the segment whose geometry and normal orientation most consistent with those of the vertex, we can completely remove the influence from neighbors lying on other segments during denoising. Our method identifies piecewise smooth subneighborhoods using a robust density-based clustering algorithm based on shared nearest neighbors. In our method, we obtain an initial estimate of vertex normals and curvature tensors by robustly fitting a local quadric model. An anisotropic filter based on optimal estimation theory is further applied to smooth the normal field and the curvature tensor field. This is followed by second-order bilateral filtering, which better preserves curvature details and alleviates volume shrinkage during denoising. The support of these filters is defined by the consistent subneighborhood of a vertex. We have applied this algorithm to both generic and CAD models, and sharp features, such as edges and corners, are very well preserved.

In this paper, we present a new adaptive model for real-time fluid simulation with complex boundaries based on smoothed particle hydrodynamics (SPH) framework. Firstly, we introduce an adaptive SPH framework that is based on our character field function composed of 4 factors: geometrical complexity, boundary condition, physical complexity and complementary condition in terms of the neighboring particle number. Meanwhile, the rule for particle adaptation is presented. We also present a two-step method to fast detect collision with complex boundary. The first step is voxelization on the complex scene. In the second step, based on the result of voxelization, we propose a three-phase method to fast detect collisions between complex boundaries and particles. By using this method, we avoid most of the useless intersection detection computation and greatly enhance the computation efficiency. In addition, a subdivision of boundary is pre-computed before the collision interaction method so that fluid in a scene with complex boundary can still be simulated at relatively high speed and system stability risk is reduced greatly. To further accelerate the simulation, a highly parallel fluid algorithm is presented and implemented using GPU so that we can simulate dynamic fluid with mutual interaction between fluid and complex boundary at a considerably fast speed without compromising realism.

While various techniques of image deformation have been developed and extensively applied in animation and morphing, there are few works to extend these techniques to handle videos, especially real-time warping of a meaningful moving part in the video like human face. An efficient online algorithm is proposed in this paper to implement real-time face warping for video sequence. We employ AdaBoost to detect the sixteen human facial feature points and implement a fast face warping frame by frame while maintaining both temporal and spatial continuity of the warped video. In order to reduce the shaking of the detected facial feature points due to the noise in the video, we develop a novel model called Frame Buffer. All these procedures are designed efficient to guarantee the real-time performance of our system (15 fps). In addition, many other types of warping functions are also compatible with our framework. It is shown that our algorithm can be applied in real-time special effect editing in video as well as other entertainment applications.

A new image completion algorithm called Structural Priority Belief Propagation (SPBP) is presented to deal with LDV based image completion in this paper. LDV completion is a new form of image completion based on another large displacement view (LDV) of the same scene, no wonder, it has the potential of repairing large unknown region with salient structure information. In order to complete such unknown region, SPBP makes two important extensions over existing Priority-BP: dynamic weight of structural consistency and structural priority inheritance so as to propagate linear structure with correct priority, meanwhile it promotes texture propagation adhering to a global optimization scheme. Experimental results demonstrate that SPBP can obtain more satisfactory results than other LDV completion algorithms and it also performs well for traditional single image completion.

Abstract We present a new adaptive model for real‐time fluid simulation based on Smoothed Particle Hydrodynamics (SPH) framework. Unlike traditional time‐consuming SPH methods, our model can simulate fluid at a considerably faster speed without losing realism. In our model, we first introduce the non‐uniform particle system and propose a generalized distance field function which considers not only geometrical complexity but also physical complexity of fluid body. And the new sampling rules for splitting and merging of particles are also presented. This can greatly reduce the computation time of the dynamic fluid simulation. Then, a new pressure state equation and an adaptive surface tension model are proposed to enhance the stability of the system and to make the free surface more realistic. To further accelerate the computation, a special fluid solver is designed and implemented using GPU. Various fluid phenomena like breaking wave and flood are simulated at real‐time. Experiments demonstrate that our new adaptive model can greatly enhance the computation efficiency of fluid simulation compared with previous adaptive methods. Copyright © 2009 John Wiley & Sons, Ltd.

Abstract It is a fundamental but challenging problem to efficiently edit complex 3D objects. By embedding the input models into coarse tetrahedral control meshes, this paper develops a unified framework to discuss two useful editing operations: interactive deformation and deformation transfer. First, a new rigidity energy is proposed to make the tetrahedral control mesh deform as rigidly as possible, which yields intuitive detail and volume preservation even under large deformations. And an error‐driven refinement approach is presented to further improve the deformation result. Then, based on this deformation scheme, a volumetric correspondence method is introduced to perform the deformation transfer task between the tetrahedral control meshes of the source and target models, which greatly lessens the burden of the user. Experimental results show our algorithm is effective, easy to control, supports various shape representations, and well transfers deformations between non‐homeomorphous models. Copyright © 2009 John Wiley & Sons, Ltd.

Visual exploration is essential to the visualization and analysis of densely sampled 3D DTI fibers in biological specimens, due to the high geometric, spatial, and anatomical complexity of fiber tracts. Previous methods for DTI fiber visualization use zooming, color-mapping, selection, and abstraction to deliver the characteristics of the fibers. However, these schemes mainly focus on the optimization of visualization in the 3D space where cluttering and occlusion make grasping even a few thousand fibers difficult. This paper introduces a novel interaction method that augments the 3D visualization with a 2D representation containing a low-dimensional embedding of the DTI fibers. This embedding preserves the relationship between the fibers and removes the visual clutter that is inherent in 3D renderings of the fibers. This new interface allows the user to manipulate the DTI fibers as both 3D curves and 2D embedded points and easily compare or validate his or her results in both domains. The implementation of the framework is GPU based to achieve real-time interaction. The framework was applied to several tasks, and the results show that our method reduces the user's workload in recognizing 3D DTI fibers and permits quick and accurate DTI fiber selection.

Abstract We present a new image completion method based on an additional large displacement view (LDV) of the same scene for faithfully repairing large missing regions on the target image in an automatic way. A coarse‐to‐fine distortion correction algorithm is proposed to minimize the perspective distortion in the corresponding parts for the common scene regions on the LDV image. First, under the assumption of a planar scene, the LDV image is warped according to a homography to generate the initial correction result. Second, the residual distortions in the common known scene regions are revealed by means of a mismatch detection mechanism and relaxed by energy optimization of overlap correspondences, with the expectations of color constancy and displacement field smoothness. The fundamental matrix for the two views is then computed based on the reliable correspondence set. Third, under the constraints of epipolar geometry, displacement field smoothness and color consistency of the neighboring pixels, the missing pixels are orderly restored according to a specially defined repairing priority function. We finally eliminate the ghost effect between the repaired region and its surroundings by Poisson image blending. Experimental results demonstrate that our method outperforms recent state‐of‐the‐art image completion methods for repairing large missing area with complex structure information.

Abstract This paper presents a new exemplar‐based framework for video completion, allowing aesthetically pleasing completion of large space‐time holes. We regard video completion as a discrete global optimization on a 3D graph embedded in the space‐time video volume. We introduce a new objective function which enforces global spatio‐temporal consistency among patches that fill the hole and surrounding it, in terms of both color similarity and motion similarity. The optimization is solved by a novel algorithm, calledweighted priority belief propagation(BP), which alleviates the problems of slow convergence and intolerable storage size when using the standard BP. This objective function can also handle video texture synthesis by extending an input video texture to a larger texture region. Experiments on a wide variety of video examples with complex dynamic scenes demonstrate the advantages of our method over existing techniques: salient structures and motion information are much better restored. Copyright © 2008 John Wiley & Sons, Ltd.

This paper presents an approach of replacing textures of specified regions in the input image and video using stretch-based mesh optimization.. The retexturing results have the similar distortion and shading effects conforming to the underlying geometry and lighting conditions. For replacing textures in single image,two important steps are developed: the stretch-based mesh parametrization incorporating the recovered normal information is deduced to imitate perspective distortion of the region of interest; the Poisson-based refinement process is exploited to account for texture distortion at fine scale. The luminance of the input image is preserved through color transfer in YCbCr color space. Our approach is independent of the replaced textures. Once the input image is processed, any new texture can be applied to efficiently generate the retexturing results. For video retexturing, we propose key-frame-based texture replacement extended and generalized from the image retexturing. Our approach repeatedly propagates the replacement result of key frame to the rest of the frames. We develop the local motion optimization scheme to deal with the inaccuracies and errors of robust optical flow when tracking moving objects. Visibility shifting and texture drifting are effectively alleviated using graphcut segmentation algorithm and the global optimization to smooth trajectories of the tracked points over temporal domain. Our experimental results showed that the proposed approach can generate visually pleasing results for both image and video.

It is difficult to render caustic patterns at interactive frame rates. This paper introduces new rendering techniques that relax current constraints, allowing scenes with moving, non-rigid scene objects, rigid caustic objects, and rotating directional light sources to be rendered in real-time with GPU hardware acceleration. Because our algorithm estimates the intensity and the direction of caustic light, rendering of non-Lambertian surfaces is supported. Previous caustics algorithms have separated the problem into pre-rendering and rendering phases, storing intermediate results in data structures such as photon maps or radiance transfer functions. Our central idea is to use specially parameterized spot lights, called caustic spot lights (CSLs), as the intermediate representation of a two-phase algorithm. CSLs are flexible enough that a small number can approximate the light leaving a caustic object, yet simple enough that they can be efficiently evaluated by a pixel shader program during accelerated rendering.We extend our approach to support changing lighting direction by further dividing the pre-rendering phase into per-scene and per-frame components: the per-frame phase computes frame-specific CSLs by interpolating between CSLs that were pre-computed with differing light directions.

In this paper, we exploit the level set methods to extract and analyze the feature of macromolecular field. For the 3D volume data of the field, we propose a novel variational formulation of the geometric active contour, which is composed of an external energy to drive the active contours' motion, and an internal energy which penalizes the level set function adoptively to avoid periodically re-initializing. We adjust the parameters of each component and examine their influences in the whole process. Our approach provides an intuitive way to study spatial relationships of the segmented regions. And it is shown to be more accurate and efficient on the feature extraction regarding the HIV-1 protease molecular field and the DPS protein molecular field. During the exploration, we successfully found the escape route of water molecules hidden in the HIV-1 protease and the internal cavity of the DPS protein for the iron atom 's entry and deposition, which are both in accordance with the experimental results.

Fast display of realistic dynamic cloud scene is a challenging task for researchers in computer graphics. This paper describes a novel method of simulating animations of cloud. We first model the motion of cloud based on the physical theory of cloud formation. Then, the physical model of cloud is solved in discrete sparse grids. Thus, we can get approximate motion of cloud. Next, we advect texture image using the calculated velocity field to add the local detail of dynamic cloud scene. Here the texture image we used is Perlin noise map. The color of arbitrary point in the simulation space is got by calculating the product of the density texture and the regenerated Perlin noise texture. Finally, by changing different noise maps, realistic dynamic cloud scenes in different light environment are generated at high rendering rates.

In the paper, we propose a robust and fast image denoising method. The approach integrates both Non-Local means algorithm and Laplacian Pyramid. Given an image to be denoised, we first decompose it into Laplacian pyramid. Exploiting the redundancy property of Laplacian pyramid, we then perform non-local means on every level image of Laplacian pyramid. Essentially, we use the similarity of image features in Laplacian pyramid to act as weight to denoise image. Since the features extracted in Laplacian pyramid are localized in spatial position and scale, they are much more able to describe image, and computing the similarity between them is more reasonable and more robust. Also, based on the efficient Summed Square Image (SSI) scheme and Fast Fourier Transform (FFT), we present an accelerating algorithm to break the bottleneck of non-local means algorithm - similarity computation of compare windows. After speedup, our algorithm is fifty times faster than original non-local means algorithm. Experiments demonstrated the effectiveness of our algorithm.

Summary form only given. Traditionally, synthesizing the animation of floral blossom is accomplished mostly manually and hence a time-consuming and laborious task. In this paper we propose an interactive biology-based flower modeling and animating approach. We model the initial shape of the floral components including petal, pistil, stamen and pedicel, and two terminal status of floral blossom with a parameterized sketching interface. The subtle geometry of the whole flower is created according to the phyllotactic rules. We then extract a set of growth parameters for describing the floral blossom, and build a dynamic growth model to regulate the continuous morphing of floral components in the process of blossom. Finally, a sequence of naturally deforming flower models is generated with these parameters. Our initial experimental results demonstrate that our approach can efficiently generate visually pleasing simulation of floral blossom, which is consistent with biological rules.

This paper presents two novel approaches for stereo matching. First, a bitwise algorithm for stereo matching is proposed. It represents the disparity of each pixel as a binary number, treats each bit separately and determines them step by step, each step determines one bit of the disparities and involves only a single graph cut computation. It reduces the computation complexity to (9(log2 n). Second, bilayer stereo matching for scenes consisting of foreground and background is proposed. Disparity field of foreground and background layers are recovered independently, and the final disparity field is composed using the disparity field of two layers. Discontinuity between foreground and background can be preserved successfully by this schema. Experimental results show that the combination of bitwise algorithm and bilayer stereo matching can support realtime applications such as desktop-based 3D visual communication.

Facial feature localization is an important research area in both computer vision and pattern analysis. We present in this paper a hierarchical face model. It unifies both the global and local face appearance together with geometric information for precise feature localization. Face detection is used to obtain the face rough position and scale in the image. A coarse global AAM (active appearance model) is then applied to obtain the initial position of each part. Local detailed part-level AAM models (like the eyes, mouth) are used to refine the localization. This coarse-to-fine scheme constraints the search in the correct space which makes the localization more accurate. In the part-level localization, we consider the geometric relationship of the local parts and the global face model. The whole procedure is formulated into a maximum-a-posteriori (MAP) framework. Experiments demonstrate the effectiveness of our approach

UNLABELLED: Cage-shaped protein, with its special structure, may have potential applications in biomedicine and nanotechnology. We developed a program CSPro (Cage-Shaped Protein) for efficient identification of cage-shaped proteins based on quaternary structure. CSPro is capable of revealing the corresponding cage-shaped feature more clearly and quickly than traditional visualization tools. Using CSPro, we have searched the full set of PDB (protein data bank) and three types of proteins are retrieved with notably large central cavities inside. CSPro can be used to validate if the quaternary structure of a protein is cage shaped in molecular simulation. AVAILABILITY: http://www.cad.zju.edu.cn/home/humin

Abstract In this paper, we introduce a new representation – radiance transfer fields (RTF) – for rendering interreflections in dynamic scenes under low frequency illumination. The RTF describes the radiance transferred by an individual object to its surrounding space as a function of the incident radiance. An important property of RTF is its independence of the scene configuration, enabling interreflection computation in dynamic scenes. Secondly, RTFs naturally fit in with the rendering framework of precomputed shadow fields, incurring negligible cost to add interreflection effects. In addition, RTFs can be used to compute interreflections for both diffuse and glossy objects. We also show that RTF data can be highly compressed by clustered principal component analysis (CPCA), which not only reduces the memory cost but also accelerates rendering. Finally, we present some experimental results demonstrating our techniques.

Abstract In computer graphics community, face model is one of the most useful entities. The automatic detection of 3D face model has special significance to computer graphics, vision, and human‐computer interaction. However, few methods have been dedicated to this task. This paper proposes a machine learning approach for fully automatic 3D face detection. To exploit the facial features, we introducegeometric context, a novel shape descriptor which can compactly encode the distribution of local geometry and can be evaluated efficiently by using a new volume encoding form, namedintegral volume. Geometric contexts over 3D face offer the rich and discriminative representation of facial shapes and hence are quite suitable to classification. We adopt an AdaBoost learning algorithm to select the most effective geometric context‐based classifiers and to combine them into a strong classifier. Given an arbitrary 3D model, our method first identifies the symmetric parts as candidates with a new reflective symmetry detection algorithm. Then uses the learned classifier to judge whether the face part exists. Experiments are performed on a large set of 3D face and non‐face models and the results demonstrate high performance of our method. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract This paper describes a physically based method for modeling and animating sandstorm, a type of disastrous natural phenomenon. The method adopts a relatively stable incompressible multiple fluid model to simulate the motion of air, sand, and dust particles. The wind field of sandstorm is established based on Reynold‐average Navier‐Stokes equations. The sand and dust particle flow is therefore computed taking interaction among the wind, sand, and dust particles into account. To accelerate the modeling process of a dynamic sandstorm scene, a special Multi‐Fluid Solver is designed and implemented on GPU. Various illumination effects of sandstorm scenes can be simulated by spectral sampling scattering calculation. Animations of realistic sandstorms occurring in desert and urban areas based on our model are demonstrated. Compared with the real sandstorm photos, our simulated results are satisfactory. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract Realistic rendering of sky scene is important in game development and virtual reality. Traditional methods did not consider both the affect of atmospheric scattering and refraction, thus failing to realistically simulate the change of shape, color, and light ring of sky scene. In this paper, a new sky light model considering atmospheric scattering and refraction is proposed. We first calculate the refractional track of light through the atmosphere according to the refraction index. Then we adopt the scattered volume model to simplify the calculation of scattering light intensity. By adapting a path tracing algorithm considering refraction, the intensity distribution of sky light is calculated. Finally, various sky scenes in sunny day, foggy day, and that with rainbow and mirage under different conditions are realistically rendered in real time. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract We present a data‐driven approach that synthesizes tree animations from a set of pre‐computed motion data. Our approach improves previous motion synthesis algorithms for character animation in several aspects. We first introduce a simple yet effective sampling scheme to generate a rich and reusable motion database for each tree model. We also propose a novel technique to generate a fine set of transitions that are uniformly distributed in the motion database. The transition lengths are adaptively determined according to the similarity of the transiting frame pairs. In the runtime, we employ a greedy searching algorithm to synthesize smooth tree animations under an adjustable wind condition. Experimental results show that our approach achieves comparable quality to physically based methods, while in orders of magnitude faster performance. Copyright © 2007 John Wiley & Sons, Ltd.

Many graphics applications, including computer games and 3D animated films, make heavy use of deforming mesh sequences. In this paper, we generalize gradient domain editing to deforming mesh sequences. Our framework is keyframe based. Given sparse and irregularly distributed constraints at unevenly spaced keyframes, our solution first adjusts the meshes at the keyframes to satisfy these constraints, and then smoothly propagate the constraints and deformations at keyframes to the whole sequence to generate new deforming mesh sequence. To achieve convenient keyframe editing, we have developed an efficient alternating least-squares method. It harnesses the power of subspace deformation and two-pass linear methods to achieve high-quality deformations. We have also developed an effective algorithm to define boundary conditions for all frames using handle trajectory editing. Our deforming mesh editing framework has been successfully applied to a number of editing scenarios with increasing complexity, including footprint editing, path editing, temporal filtering, handle-based deformation mixing, and spacetime morphing.

For the non-local denoising approach presented by Buades et al., remarkable denoising results are obtained at high expense of computational cost. In this paper, a new algorithm that reduces the computational cost for calculating the similarity of neighborhood windows is proposed. We first introduce an approximate measure about the similarity of neighborhood windows, then we use an efficient summed square image (SSI) scheme and fast Fourier transform (FFT) to accelerate the calculation of this measure. Our algorithm is about fifty times faster than the original non-local algorithm both theoretically and experimentally, yet produces comparable results in terms of mean-squared error (MSE) and perceptual image quality.

Abstract We propose an efficient approach for authoring dynamic and realistic waterfall scenes based on an acquired video sequence. Traditional video based techniques generate new images by synthesizing 2D samples, i.e., texture sprites chosen from a video sequence. However, they are limited to one fixed viewpoint and cannot provide arbitrary walkthrough into 3D scenes. Our approach extends this scheme by synthesizing dynamic 2D texture sprites and projecting them into 3D space. We first generate a set of basis texture sprites, which capture the representative appearance and motions of waterfall scenes contained in the video sequence. To model the shape and motion of a new waterfall scene, we interactively construct a set of flow lines taking account of physical principles. Along each flow line, the basis texture sprites are manipulated and animated dynamically, yielding a sequence of dynamic texture sprites in 3D space. These texture sprites are displayed using the point splatting technique, which can be accelerated efficiently by graphics hardware. By choosing varied basis texture sprites, waterfall scenes with different appearance and shapes can be conveniently simulated. The experimental results demonstrate that our approach achieves realistic effects and real‐time frame rates on consumer PC platforms. Copyright © 2006 John Wiley & Sons, Ltd.

Previous methods for soft shadows numerically integrate over many light directions at each receiver point, testing blocker visibility in each direction. We introduce a method for real-time soft shadows in dynamic scenes illuminated by large, low-frequency light sources where such integration is impractical. Our method operates on vectors representing low-frequency visibility of blockers in the spherical harmonic basis. Blocking geometry is modeled as a set of spheres; relatively few spheres capture the low-frequency blocking effect of complicated geometry. At each receiver point, we compute the product of visibility vectors for these blocker spheres as seen from the point. Instead of computing an expensive SH product per blocker as in previous work, we perform inexpensive vector sums to accumulate the log of blocker visibility. SH exponentiation then yields the product visibility vector over all blockers. We show how the SH exponentiation required can be approximated accurately and efficiently for low-order SH, accelerating previous CPU-based methods by a factor of 10 or more, depending on blocker complexity, and allowing real-time GPU implementation.

Most of the existing algorithms for protein similarity comparison focus on the sequence comparison and structure comparison. However, the 3D structure of a protein is determined by the force field generated by all of its atoms in essence. Thus the similarity of force field implies the similarity of 3D structure. In this paper, we propose a novel approach to compare the similarity of protein's force fields. First, we use blurred map to sample the force field into volumetric data sets. Second, the volume data set is resampled into a unified resolution. Third, the data set is band-pass filtered and quantized to reveal its physical attributes. The resulting voxels are then normalized into a canonical coordinate system concerning the center of mass and scale. Subsequently, a series of uniformly spaced concentric shells around the center of mass are constructed, based on which spherical harmonics analysis (SHA) is applied. The coefficient of SHA constitutes rotation invariant spectrum descriptors which are used to measure the similarity between two data sets. The algorithm has been performed on a set of proteins (taken from PDB) and the preliminary results are fairly inspiring.

Haptic rendering is a highly device-dependent process. Accordingly, haptic rendering algorithms should be designed regarding the specific physical features of a haptic device. The Immersion CyberGrasp is a force feedback device which can provide an individual force roughly perpendicular to the fingertip of each finger. In this paper, we propose a novel force rendering algorithm for the Immersion CyberGrasp considering the feature of area contacts between the virtual hand avatar and target geometric models. Line segment clusters are used as haptic proxies for the real-time collision detection between the fingertips and target geometric models. Force computations are conducted directly using the collision detection results. Spatial subdivision is performed on target geometric models to facilitate real-time collision detection. Experimental results show that our algorithm can provide stable and realistic force feedback.

Abstract We propose a novel image/video retexturing approach that preserves the original shading effects without knowing the underlying surface and lighting conditions. For static images, we first introduce the Poisson equation‐based algorithm to simulate the texture distortion on the projected interest region of the underlying surface, while preserving the shading effect of the original image. We further work on videos by retexturing the key frame as static image and then propagating the results onto the other frames. In video retexturing, we have introduced the mesh based optimization for object tracking to avoid texture drifting, and the graph cut algorithm to effectively deal with visibility shift between frames. The graph cut algorithm is applied on a trimap along the boundary of the object to extract the textured part inside the trimap. The proposed approach is developed in image/video retexturing at nearly interactive rate, and our experimental results have showed the satisfactory performance of our approach. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract Simulation of dynamic natural scene is one of the most challenging tasks in computer graphics. In this paper, we propose a new approach to dynamic modeling and rendering of grasses wagging in wind. Through length preserving free‐form deformation of the 3D skeleton lines of each grass blade and using the alpha test to implement transparent texture mapping, we successfully model grasses of different shapes with rich details. To simulate the real time waggle of grasses, the grasses of a meadow are represented in LOD, while their skeleton lines are dynamically deformed according to some physical models. Simplification technique is also employed to accelerate the collision detection between neighboring grasses. Experiments show that our method can realistically render the animated grass scenes under wind of different speeds and types in real time. Copyright © 2005 John Wiley & Sons, Ltd.

Intuitive and natural interactions are key aspects of virtual assembly applications. In this paper, we present intuitive virtual hand interactions with parts, subassemblies and tools. Grasping patterns are developed based on the abstraction of various mechanic shapes, kinematics model of virtual hand is built upon the anatomic structure of the human hand to guarantee motion realism, and real-time collision detection scheme is used to identify whether the current finger configuration matches a specific grasping pattern. Experiments on assembly models with a CyberGlove dataglove show that our virtual grasping scheme works well for virtual assembly tasks.

In this paper, we present an efficient voxelization algorithm for complex polygonal models by exploiting newest programmable graphics hardware. We first convert the model into three discrete voxel spaces according to its surface orientation. The resultant voxels are encoded as 2D textures and stored in three intermediate sheet buffers called directional sheet buffers. These buffers are finally synthesized into one worksheet, which records the volumetric representation of the target. The whole algorithm traverses the geometric model only once and is accomplished entirely in GPU (graphics processing unit), achieving real-time frame rate for models with up to 2 million triangles.

In this paper we present an interactive collision detection algorithm for complex and deformable objects. For two target models, our approach rapidly calculates their region of interests (ROI), which is the overlapping of their axis aligned bounding boxes (AABBs), in CPU. The surfaces of both models inside the ROI are then voxelized using a novel GPU-based real-time voxelization method. The resultant volumes are represented by two 2D textures in video memory. The collision query is efficiently accomplished by comparing these 2D textures in GPU. The algorithm is robust to handle arbitrary shapes, no matter geometric models are convex or concave, closed or open, rigid or deformable. Our preliminary implementation achieves interactive frame rate for complex models with up to one million triangles on commodity desktop PCs.

Texture mapping greatly influences the performance of visualization in many 3D applications. Sometimes the texture data is so large that it has to be stored in slower external storage, rather than fast texture memory or host memory. In these circumstances, texture mapping becomes the performance bottleneck. In this paper, we present a compact multiresolution model, Texture Mipmap Quadtree (TMQ), to represent large-scale textures. It facilitates fast loading and pre-filtering of textures from slower external storage. Integrating continuous LOD model of terrain geometry, we present a criterion to select proper textures from TMQ according to viewing parameters during rendering stage. By exploiting temporal coherence, a dynamic texture management scheme is devised based on two-level cache hierarchy to further increase the performance of texture mapping.

Abstract We propose a novel morphing algorithm for objects represented by point‐sampled geometry. The fundamental problem of point‐sampled geometry morphing is how to set the correspondence between points of the two objects which are usually of different size. The two objects are first parameterized by projecting the sample points onto a common parametric domain. As both objects are densely sampled, we present a novel accelerated parameterization algorithm employing the technique of LOD. The common parameter domain is then split recursively into clusters. The correspondence between sample points of the two objects is established by performing a local mapping in each cluster. As for complex geometries, the establishment of correspondence is facilitated by decomposing the geometry into patches using geodesic decomposition curves. To preserve the features during morphing, a process of features assignment is incorporated. By re‐sampling the in‐between object dynamically and adaptively, the cracks that would occasionally occur during morphing are successfully eliminated. Experiment results show that our algorithms are fast, stable and easy to implement. High‐quality morphing is produced. Copyright © 2004 John Wiley & Sons, Ltd.

Occlusion culling is an important technique to speed up the rendering process for walkthroughs in a complex environment. In this paper, we present a new approach for occlusion culling with respect to a view cell. A compact representation, the Global Occlusion Map (GOM), is proposed for storing the global visibility information of general 3D models with respect to the view cell. The GOM provides a collection of Directional Visibility Barriers (DVB), which are virtual occluding planes aligned with the main axes of the world coordinates that act as occluders to reject invisible objects lying behind them in every direction from a view cell. Since the GOM is a two-dimensional array, its size is bounded, depending only on the number of the sampled viewing directions. Furthermore, it is easy to conservatively compress the GOM by treating it as a depth image. Due to the axial orientations of the DVBs, both the computational and storage costs for occlusion culling based on the GOM is minimized. Our implementation shows the Global Occlusion Map is effective and efficient in urban walkthrough applications.

Real-time rendering for large-scale, complex dynamic virtual scenes is a challenging problem in computer graphics. In this paper, we propose a hybrid rendering algorithm of dynamic virtual environments that seamlessly fuses the point-based scheme and polygon-based scheme. In our algorithm, the scene is organized into a BSP-tree. Objects in the leaf-nodes of the BSP tree are further subdivided into a quad-tree hierarchy, which contains both the sample points and polygon rendering information at each level. The accelerated rendering algorithm integrates the hierarchical occlusion map technique, image caching technique and BSP technique to fast render complex dynamic scenes. During navigation, our system adaptively determines the rendering mode and the level of details of objects, and achieves smooth transition between the two rendering modes by effectively controlling the rendering precision. The dynamic objects can be processed in the system uniformly. Our experimental results have demonstrated the satisfactory performance of the proposed hybrid-rendering scheme for the dynamic virtual environments.

A new approach of point-based rendering is presented for objects with complex shape. By this approach, an object is represented by a set of discrete sample points, each point stands for a sampled surface area whose boundary is assumed to be a circle when viewed along its normal. An algorithm is proposed to build a point-based model with level of details. Efficiency of the rendering process is ensured by performing adaptive sampling of the model without calculating the sample points on the fly. To get rid of the aliasing effects due to point sampling, we have developed a delta-z-buffer and a flag buffer to smooth the boundary of two adjacent sampled areas and to fill the holes that may appear inside the image of an object. Experimental results show that our new approach is capable of rendering complex objects consisting of only 50,000 points with acceptable image quality, and high rendering efficiency.

In this paper, we present a novel fairing algorithm for the removal of noise from uniform triangular meshes without shrinkage and serious distortion. The key feature of this algorithm is to keep all triangle centers invariant at each smoothing step by including some constraints in the energy minimization functional. The constrained functional is then minimized efficiently using an iterative method. Further, we apply this smoothing technique to a multiresolution representation to remove arbitrary levels of detail. A volume‐preserving decimation algorithm is presented to generate the multiresolution representation. The experimental results demonstrate the combined algorithm's stability and efficiency.

Free-form deformation, abbreviated to FFD, plays an important role in both computer animation and geometric modeling. When polygonal objects are deformed by the traditional FFD scheme, however aliasing will appear since the deformation only acts on the sample points of the objects. To eliminate this problem, a new method of accurate B-spline FFD was proposed by authors previously, which is based on functional composition. Unfortunately it is a time consuming process because generalized de Casteljau algorithm is adopted to solve the functional composition. In this paper we propose a fast accurate B-spline FFD method. The proposed method makes use of the polynomial interpolation and symbolic computation to solve the functional composition. Both theoretical analysis and implementation results show that the proposed method runs faster than the original one.

A novel progressive geometry compression scheme is presented in this paper. In this scheme, a mesh is represented as a base mesh followed by some groups of vertex split operations using an improved simplification method in which each level of the mesh can be refined into the next level by carrying out a group of vertex split operations in any order. Consequently, the progressive mesh (PM) representation can be effectively encoded by permuting the vertex split operations in each group. Meanwhile, a geometry predictor using the Laplacian operator is designed to predict each new vertex position using its neighbours. The correction is quantized and encoded using a Huffman coding scheme. Experimental results show that our algorithm obtains higher compression ratios than previous work. It is very suitable for the progressive transmission of geometric models over the Internet.

Presents a new efficient texture mapping algorithm for polygonal meshes. Texture coordinates are assigned to the vertices of the mesh using the variational interpolation technique. For each patch to be mapped, the algorithm first samples equidistantly the boundaries of the patch. In order to decrease distortion, the patch is further sampled as uniformly as possible while its texture domain are correspondingly sampled. The variational interpolation technique is then invoked to yield a parameterization of the patch. The experimental results demonstrate that the algorithm has a great number of potential applications in texture mapping and surface modeling.

A distributed virtual reality system based on a hybrid rendering scheme is presented in this paper. Unlike the traditional image based rending algorithm, our approach divides the local scene within the frustum of the current viewpoint into two layers, i.e., the front layer and the back layer. Objects in the front layer are rendered in real time with a geometry based hardware z-buffer algorithm. To generate the image of back layer, we first perform a nonlinear transformation to all visible points of a keyframe adjacent to the current viewpoint to reveal their coplanar characteristics. A hierarchical quadrangle approximation of the local scene is then set up, the intermediate image of the back layer at the current viewpoint is then obtained by re-projecting these quadrangles onto the current image plane, gaps that might appear on the intermediate image am filled by bi-directional backward warping. As our approach consists of two independent phases, it can be easily implemented in parallel or distribution mode. Experimental results show that our approach has a satisfactory performance.

A new non-linear view interpolation algorithm is presented in this paper. Unlike the linear interpolation scheme, our method can exactly simulate the perspective viewing transformation during walkthrough. To accelerate the view interpolation, the algorithm employs a binary subdivision scheme to optimize the decomposition of the source image so that the number of resultant blocks is greatly reduced. Holes in the intermediate image are filled by two steps, namely enlarging the transferred blocks at the sides adjacent to holes and retrieving the local image within holes from the destination images by multidirectional interpolation. Experimental results demonstrate that our algorithm is much more accurate and efficient than the traditional one. Copyright © 1999 John Wiley & Sons, Ltd.

A new nonlinear view interpolation algorithm is presented. Unlike the linear interpolation scheme, our method can exactly simulate the perspective viewing transformation during the walkthrough. To accelerate the view interpolation, the algorithm employs a binary subdivision scheme to optimize the decomposition of the source image so that the number of the resultant blocks is greatly reduced. Holes on the intermediate image are filled by two steps, namely enlarging the transferred blocks at the side adjacent to holes and retrieving the local image within the holes from the destination images by multiple-directional interpolation. Experimental results demonstrate our algorithm is much more accurate and efficient than the traditional one.

Space deformation is an important tool in computer animation and shape design. We propose a new local deformation model based on generalized metaballs. The user specifies a series of constraints, which can be made up of points, lines, surfaces and volumes, their effective radii and maximum displacements; the deformation model creates a generalized metaball for each constraint. Each generalized metaball is associated with a potential function centered on the constraint, the potential function drops from 1 on the constraint to 0 on the effective radius. This deformation model operates on the local space and is independent of the underlining representation of the object to be deformed. The deformation can be finely controlled by adjusting the parameters of the generalized metaballs. We also present some extensions and the extended deformation model to include scale and rotation constraints. Experiments show that this deformation model is efficient and intuitive. It can deal with various constraints, which is difficult for traditional deformation model.

The paper proposes an infrared image synthesis model based on infrared physics and heat transfer. The model successfully reproduces the infrared images of the object under different viewing, ambient and internal conditions. Experimental examples illustrate the potential of our method.

A new 3D morphing algorithm for polyhedral objects with the same genus is presented in the paper. Our main contribution is an efficient and general algorithm for setting up the vertex correspondence between the polyhedra. The proposed algorithm first interactively partitions the two original polyhedra into the same number of polygonal patches, the patch correspondence is also established during partitioning. Each pair of corresponding patches is then parametrized and resampled by using the harmonic maps. A feature polyhedron is finally constructed for each original polyhedron, and the vertex correspondence between each original polyhedron and its feature polyhedron is automatically established following a cluster scheme. The shape transition between the original polyhedral models is accomplished by composing three successive transformations using their feature polyhedra as the bridges. Experimental results demonstrate that our algorithm is very robust, and can deal with very general cases (non‐zero genus polyhedral cases).

This paper proposes a new preprocessing method for interactive rendering of complex polygonal virtual environments. The approach divides the space that observer can reach into many rectangular viewpoint regions. For each region, an outer rectangular volume (ORV) is established to surround it. By adaptively partitioning the boundary of the ORV together with the viewpoint region, all the rays that originate from the viewpoint region are divided into the beams whose potentially visible polygon number is less than a preset threshold. If a resultant beam is the smallest and intersects many potentially visible polygons, the beam is simplified as a fixed number of rays and the averaged color of the hit polygons is recorded. For other beams, their potentially visible sets (PVS) of polygons are stored respectively. During an interactive walkthrough, the visual information related to the current viewpoint is retrieved from the storage. The view volume clipping, visibility culling and detail simplification are efficiently supported by these stored data. The rendering time is independent of the scene complexity.

In real life, some objects may deform along axial curves and the lengths of their skeletons usually remain constant during the axial deformation, such as a swimming fish, a swaying tree, etc. This paper presents a practical approach of arc-length-based axial deformation and axial-length-preserved animation. The space spanned by the arc-length parameter and the rotation-minimizing frame on the axis is taken as the embedding space. During animation, the keyframe axial curves are consistently approximated by polylines after sufficient subdivisions and both the edge lengths and the directional vertex angles of the keyframe polylines (or unit edge vectors) are then interpolated to generate the intermediate polylines which are regarded as the discrete expressions of the intermediate axes. Experiments show that our method is very useful, intuitive and easy to control.

Intuitive 30 sulfate control and deformation are czucial to CAD/CAM.To do this in a virtual environment, however, the tecZznique must be very efficient.A common method for shape deformation is the free-form deformation (FFD) method, in which the complete object is deformed by defozming a 30 grid of the object.In this paper, we propose an intuitive method for sulfate deformation based on deforming a hand s&ace, which is basically a bicubic B-spline sudace interpolating or approximating key data points of a sensor glove (i.e.finger joints and palm center of the user's hand).By setting up a corresponding mapping between the virtual object being deformed and the hand sugace, the object can be deformed with tlze control of the sensor glove.As the usersexes hislherfingers, the object changes its shape accordingly.Such control can be local or global.For local deformation, we introduce a region jilter function which imposes locality on the mapping/deformation.The new algorithm is made very efficient tlzrough incremental update.It is also intuitive as zfthe zzser were using his hand to deform the object directly.Experimental results show the potential of the new method.

Abstract A new shading model for curve light sources is presented. It accounts for both diffuse reflection and specular reflection of the illuminated surface. By regarding a linear light source as a directional quadrilateral light source with very small width, a simple formula is derived first for calculating the diffuse reflection component due to the illumination of the linear segment. The diffuse reflection of the surface by direct illumination of a curve light source is then evaluated by approximating the curve light with a series of linear segments. The specular reflection component due to a curve light source is represented by an integration taking Phong's specular model as the kernel and evaluated by summing the contributions from the linear segments. Finally, an efficient shadow detection algorithm for curve light sources is proposed. The images rendered with the shading model are very photo‐realistic.

Abstract This paper introduces a kind of new wavelet radiosity method called multiresolution B‐spline radiosity, which uses B‐splines of different scales to represent radiosity distribution functions. A set of techniques and algorithms, such as function extrapolation, adaptive quadrature, scale adjustment and octree, are proposed to implement it. This method sets up hierarchical structures on surfaces, keeps radiosity distribution continuous at element boundaries, does not need postprocessing, and does not prevent the use of any surface whose parameter domain is rectilinear.

Abstract Based on the theory of light energy transfer between two differential diffuse surface areas, a generalized radiosity approach is presented. Unlike the conventional radiosity method, curved surfaces are subdivided into triangular surface patches, radiosity is assummed to be vary across each triangular surface patch. By adopting linear interpolation scheme over each triangular surface patch, we have established a complete set of approximated radiosity equations. Their unknowns are radiosities of differential surface areas located at all vertices of surface patches. The generalized radiosity equation has also been extended to non‐diffuse environments. Theoretical analysis and experimental results demonstrate the great potential of this method,

Abstract Smoothing of polyhedron with arbitrary topology is an important issue in CAGD and CAD/CAM, but so far it is deemed to be difficult to smooth the complex corners of a polyhedron. In this paper, the concept of distance surfaces of a surface and a solid is introduced, and the incisive properties of such surfaces are addressed which provide a theoretical foundation for modifying a general corner. The method is based on making constricted volume and the maximum distance the volume can be constricted is given too. It is shown that by the proposed method in this paper any polyhedron can be G1 smoothed with quadraic and, sometimes toroidal surfaces. The new approach is suitable for engineering design and NC machining. The associated algorithm based on the classification theorem of corners is simple, fast and robust.

A new functional modeling approach - -functional modeling, is presented to depict various classes of natural terrain. While this approach possesses the functions of several previous methods, it does not suffer the drawbacks of creases or periodity. By choosing the control parameters properly, our approach can easily generate different terrains related to various smoothness, such as cliffs,fractal mountains and smooth terrains. It can also simulate the natural weathering processes as from the cliff to the fractal mountain and to the smooth terrain not only in the appearance but also in quantity. And it is capable of modeling the terrain whose "rock bed” and "rock quilt" are associated with different smoothness.

As form-factor calculation costs about 90% of the computing time when applying radiosity approach for realistic image synthesis, it is of great significance to reduce the required computation, An accelerated radiosity algorithm for general complex environments, based on environment localization and the directional form-factor concept, is presented in this paper. First we subdivide the object space into many regions. Objects contained in each region are adjacent to each other and pose more illumination effects to their neighbours. Then form-factors are calculated in each local environment,. The radiant light energy transfer between different regions is evaluated at their common boundaries. Directional form-factors are introduced to simulate the interaction of light between local environments and between non-diffuse surfaces. Comparison is made to existing algorithms. Statistic results and theoretical analysis show that the new algorithm is much faster than previous ones. The technique is especially fit for interactive design and animation sequence since modification to the shape or location of objects usually happens in local environments.

A new algorithm, based on the hemi-cube formulation, which calculates the form-factors required by the solution of the rendering equation, is presented. The concept of form-factors of the standard radiosity method is developed, In particular, the concept of specular form-factors is proposed. These new form-factors are also purely geometric terms describing the transfer of energy from one surface to another within a non-diffuse environment. The new form-factor is evaluated by numerical integrations based on the hemi-cube algorithm. The equations of the effective diffuse radiosity are presented and solved by numerical methods. The extension fully develops the characteristic of radiosity method and successfully solves the view-independent energy transfer in a general environment.

According to the rendering equation, the diffuse and the specular components of the outgoing intensity of each surface patch should be solved simultaneously. Rather than establishing a huge set of linear equations defining the unknown directional intensities for all directions and all surface patches, we expand the concept of the delta form-factor which concerns the light energy transfer of a surface patch along a respective direction. As the delta form-factor for non-diffuse surface patches are dependent on the spatial and spectral distributions of light energy, they could not be calculated geometrically. In this paper, we present a new radiosity approach which progressively approximates the delta form-factors and the light energy distributions within a general environment to the correct solution. The nucleus of our approach is procedural iteration. Statistics indicate the potentials of this method for complex non-diffuse environments.

A fast ray tracing algorithm is presented. Spatial coherency is exploited by adopting a linear octree data structure which corresponds to an adaptive partitioning of space. A ray strides over a number of empty regions aligning on its way and intersects the desired objects directly, Efficiency of the algorithm is achieved by decreasing the number of regions that the ray must be checked with, by reducing the computations involved in skipping an empty region and by performing a binary search to find the next region. An efficient algorithm based on linear programming for mapping the whole environment into a sorted linear octree is also described. Only the terminal nodes containing boundary surfaces of objects are explicitly represented, which not only shortens the searching process but also leads to a considerable saving on storage space.