This article presents a Model Predictive Control framework with a visuomotor system that synthesizes eye and head movements coupled with physics-based full-body motions while placing visual attention on objects of importance in the environment. As the engine of this framework, we propose a visuomotor system based on human visual perception and full-body dynamics with contacts. Relying on partial observations with uncertainty from a simulated visual sensor, an optimal control problem for this system leads to a Partially Observable Markov Decision Process, which is difficult to deal with. We approximate it as a deterministic belief Markov Decision Process for effective control. To obtain a solution for the problem efficiently, we adopt differential dynamic programming, which is a powerful scheme to find a locally optimal control policy for nonlinear system dynamics. Guided by a reference skeletal motion without any a priori gaze information, our system produces realistic eye and head movements together with full-body motions for various tasks such as catching a thrown ball, walking on stepping stones, balancing after being pushed, and avoiding moving obstacles.

Playing with a soccer ball is not easy even for a real human because of dynamic foot contacts with the moving ball while chasing and controlling it. The problem of online full-body soccer motion synthesis is challenging and has not been fully solved yet. In this paper, we present a novel motion control system that produces physically-correct full-body soccer motions: dribbling forward, dribbling to the side, and shooting, in response to an online user motion prescription specified by a motion type, a running speed, and a turning angle. This system performs two tightly-coupled tasks: data-driven motion prediction and physics-based motion synthesis. Given example motion data, the former synthesizes a reference motion in accordance with an online user input and further refines the motion to make the character kick the ball at a right time and place. Provided with the reference motion, the latter then adopts a Model Predictive Control (MPC) framework to generate a physically-correct soccer motion, by solving an optimal control problem that is formulated based on dynamics for a full-body character and the moving ball together with their interactions. Our demonstration shows the effectiveness of the proposed system that synthesizes convincing full-body soccer motions in various scenarios such as adjusting the desired running speed of the character, changing the velocity and the mass of the ball, and maintaining balance against external forces.

Abstract This paper presents a novel online model predictive control framework based on automatic time warping. In general, existing model predictive control frameworks employ reference motions with sampling time uniform and fixed. Unlike these, our framework allows to change the sampling time of a reference motion based on physics‐based simulation so that the character effectively responds to external forces unexpectedly applied to it. In order to do so, we formulate an optimal control problem, taking into account both optimal time warping and full‐body dynamics simultaneously. We adopt differential dynamic programming to produce an optimal control policy by solving the problem, which is used to compute the optimal feedback information for character motion and sampling time. We show the robustness of our framework to external perturbations through experiments. We also show the effectiveness of this framework for rhythmic motion synthesis.

Abstract In this paper, we propose an efficient data‐guided method based on Model Predictive Control (MPC) to synthesize a full‐body motion. Guided by a reference motion, our method repeatedly plans the full‐body motion to produce an optimal control policy for predictive control while sliding the fixed‐span window along the time axis. Based on this policy, the method computes the joint torques of a character at every time step. Together with contact forces and external perturbations if there are any, the joint torques are used to update the state of the character. Without including the contact forces in the control vector, our formulation of the trajectory optimization problem enables automatic adjustment of contact timings and positions for balancing in response to environmental changes and external perturbations. For efficiency, we adopt derivative‐based trajectory optimization on top of state‐of‐the‐art smoothed contact dynamics. Use of derivatives enables our method to run much faster than the existing sampling‐based methods. In order to further accelerate the performance of MPC, we propose efficient numerical differentiation of the system dynamics of a full‐body character based on two schemes: data reuse and data interpolation. The former scheme exploits data dependency to reuse physical quantities of the system dynamics at near‐by time points. The latter scheme allows the use of derivatives at sparse sample points to interpolate those at other time points in the window. We further accelerate evaluation of the system dynamics by exploiting the sparsity of physical quantities such as Jacobian matrix resulting from the tree‐like structure of the articulated body. Through experiments, we show that the proposed method efficiently can synthesize realistic motions such as locomotion, dancing, gymnastic motions, and martial arts at interactive rates using moderate computing resources.

Abstract In the paper, we present an online real‐time method for automatically transforming a basic locomotive motion to a desired motion of the same type, based on biomechanical results. Given an online request for a motion of a certain type with desired moving speed and turning angle, our method first extracts a basic motion of the same type from a motion graph, and then transforms it to achieve the desired moving speed and turning angle by exploiting the following biomechanical observations: contact‐driven center‐of‐mass control, anticipatory reorientation of upper body segments, moving speed adjustment, and whole‐body leaning. Exploiting these observations, we propose a simple but effective method to add physical and behavioral naturalness to the resulting locomotive motions without preprocessing. Through experiments, we show that our method enables a character to respond agilely to online user commands while efficiently generating walking, jogging, and running motions with a compact motion library. Our method can also deal with certain dynamical motions such as forward roll. Copyright © 2016 John Wiley & Sons, Ltd.

Abstract In this paper, we present an on‐line real‐time physics‐based approach to motion control with contact repositioning based on a low‐dimensional dynamics model using example motion data. Our approach first generates a reference motion in run time according to an on‐line user request by transforming an example motion extracted from a motion library. Guided by the reference motion, it repeatedly generates an optimal control policy for a small time window one at a time for a sequence of partially overlapping windows, each covering a couple of footsteps of the reference motion, which supports an on‐line performance. On top of this, our system dynamics and problem formulation allow to derive closed‐form derivative functions by exploiting the low‐dimensional dynamics model together with example motion data. These derivative functions and their sparse structures facilitate a real‐time performance. Our approach also allows contact foot repositioning so as to robustly respond to an external perturbation or an environmental change as well as to perform locomotion tasks such as stepping on stones effectively.

We propose a physically-based approach to separate reflection using multiple polarized images with a background scene captured behind glass. The input consists of three polarized images, each captured from the same view point but with a different polarizer angle separated by 45 degrees. The output is the high-quality separation of the reflection and background layers from each of the input images. A main technical challenge for this problem is that the mixing coefficient for the reflection and background layers depends on the angle of incidence and the orientation of the plane of incidence, which are spatially varying over the pixels of an image. Exploiting physical properties of polarization for a double-surfaced glass medium, we propose a multiscale scheme which automatically finds the optimal separation of the reflection and background layers. Through experiments, we demonstrate that our approach can generate superior results to those of previous methods.

We propose a physically-based approach to separate reflection using multiple polarized images with a background scene captured behind glass. The input consists of three polarized images, each captured from the same view point but with a different polarizer angle separated by 45 degrees. The output is the high-quality separation of the reflection and background layers from each of the input images. A main technical challenge for this problem is that the mixing coefficient for the reflection and background layers depends on the angle of incidence and the orientation of the plane of incidence, which are spatially-varying over the pixels of an image. Exploiting physical properties of polarization for a double-surfaced glass medium, we propose an algorithm which automatically finds the optimal separation of the reflection and background layers. Thorough experiments, we demonstrate that our approach can generate superior results to those of previous methods.

This paper addresses the problem of computing the geodesic distance map from a given set of source vertices to all other vertices on a surface mesh using an anisotropic distance metric. Formulating this problem as an equivalent control theoretic problem with Hamilton-Jacobi-Bellman partial differential equations, we present a framework for computing an anisotropic geodesic map using a curvature-based speed function. An ordered upwind method (OUM)-based solver for these equations is available for unstructured planar meshes. We adopt this OUM-based solver for surface meshes and present a triangulation-invariant method for the solver. Our basic idea is to explore proximity among the vertices on a surface while locally following the characteristic direction at each vertex. We also propose two speed functions based on classical curvature tensors and show that the resulting anisotropic geodesic maps reflect surface geometry well through several experiments, including isocontour generation, offset curve computation, medial axis extraction, and ridge/valley curve extraction. Our approach facilitates surface analysis and processing by defining speed functions in an application-dependent manner.

In this paper, we deal with a problem of separating the effect of reflection from images captured behind glass. The input consists of multiple polarized images captured from the same view point but with different polarizer angles. The output is the high quality separation of the reflection layer and the background layer from the images. We formulate this problem as a constrained optimization problem and propose a framework that allows us to fully exploit the mutually exclusive image information in our input data. We test our approach on various images and demonstrate that our approach can generate good reflection separation results.

We propose a method for deblurring of spatially variant object motion. A principal challenge of this problem is how to estimate the point spread function (PSF) of the spatially variant blur. Based on the projective motion blur model of, we present a blur estimation technique that jointly utilizes a coded exposure camera and simple user interactions to recover the PSF. With this spatially variant PSF, objects that exhibit projective motion can be effectively de-blurred. We validate this method with several challenging image examples.

Abstract This paper presents a hybrid approach to multiple fluid simulation that can handle miscible and immiscible fluids, simultaneously. We combine distance functions and volume fractions to capture not only the discontinuous interface between immiscible fluids but also the smooth transition between miscible fluids. Our approach consists of four steps: velocity field computation, volume fraction advection, miscible fluid diffusion, and visualization. By providing a combining scheme between volume fractions and level set functions, we are able to take advantages of both representation schemes of fluids. From the system point of view, our work is the first approach to Eulerian grid‐based multiple fluid simulation including both miscible and immiscible fluids. From the technical point of view, our approach addresses the issues arising from variable density and viscosity together with material diffusion. We show that the effectiveness of our approach to handle multiple miscible and immiscible fluids through experiments.

Abstract Given a pair of keyframe formations for a group consisting of multiple individuals, we present a spectral‐based approach to smoothly transforming a source group formation into a target formation while respecting the clusters of the involved individuals. The proposed method provides an effective means for controlling the macroscopic spatiotemporal arrangement of individuals for applications such as expressive formations in mass performances and tactical formations in team sports. Our main idea is to formulate this problem as rotation interpolation of the eigenbases for the Laplacian matrices, each of which represents how the individuals are clustered in a given keyframe formation. A stream of time‐varying formations is controlled by editing the underlying adjacency relationships among individuals as well as their spatial positions at each keyframe, and interpolating the keyframe formations while producing plausible collective behaviors over a period of time. An interactive system of editing existing group behaviors in a hierarchical fashion has been implemented to provide flexible formation control of large crowds.

Abstract Conventional level set‐based approaches have an inherent difficulty in tracking miscible fluids due to its discrete treatment for interface. This paper proposes a unified framework to efficiently handle both miscible and immiscible fluid simulations. Based on the chemical potential energy, our method describes the evolution of multiple fluids as time‐varying concentration fields. Handling of multiple fluids is straightforward and, unlike level set methods, ad hoc reinitialization or fictitious particle deployment is not necessary. For numerical computation of the Navier—Stokes equations, we adopt advanced lattice Boltzmann methods (LBMs) for computational efficiency. The experiments show that our approach works well with immiscible fluids, miscible fluids, and interaction with objects. Copyright © 2008 John Wiley & Sons, Ltd.

In this paper, we deal with the problem of synthesizing novel motions of standing-up martial arts such as Kickboxing, Karate, and Taekwondo performed by a pair of human-like characters while reflecting their interactions. Adopting an example-based paradigm, we address three non-trivial issues embedded in this problem: motion modeling, interaction modeling, and motion synthesis. For the first issue, we present a semi-automatic motion labeling scheme based on force-based motion segmentation and learning-based action classification. We also construct a pair of motion transition graphs each of which represents an individual motion stream. For the second issue, we propose a scheme for capturing the interactions between two players. A dynamic Bayesian network is adopted to build a motion transition model on top of the coupled motion transition graph that is constructed from an example motion stream. For the last issue, we provide a scheme for synthesizing a novel sequence of coupled motions, guided by the motion transition model. Although the focus of the present work is on martial arts, we believe that the framework of the proposed approach can be conveyed to other two-player motions as well.

Abstract For applications such as video games and virtual walk‐throughs, on‐line locomotion control is an important issue. In general, the user prescribes a sequence of motions one by one while providing an input trajectory. Since the input trajectory lacks in human characteristics, one may not synthesize quality motions by blindly following it. In this paper, we present a novel data‐driven scheme for transforming a user‐prescribed trajectory to a human trajectory in an on‐line manner. As preprocessing, we analyze example motion data to extract human steering behavior. At run‐time, the input trajectory is refined to reflect the steering behavior. Together with an existing on‐line motion synthesis system, our scheme forms a feedback loop, in which the user effectively specifies an intended human trajectory. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract Given a still picture, tour into the picture (TIP) generates a walk‐through animation of a 3D scene constructed from the picture. In this paper, we generalize TIP to deal with water surface reflection while allowing foreground objects to move. We formulate a non‐linear optimization problem to find the 3D scene parameters with respect to the camera position, to automatically construct a reasonable 3D scene model, provided with a set of points and their corresponding points on the water surface. To synthesize a stream of reflected images on the water surface in accordance with the camera movement, we propose a novel image‐based approach, which makes the best of the limited information available in the input picture. Furthermore, we incorporate water surface movement data acquired from water simulation on top of stochastic motion textures for objects such as trees and plants, to create a dynamic scene. Copyright © 2006 John Wiley & Sons, Ltd.

Video taken from a single monocular camera is the most common means of recording human motion. In this article, we present a practical, semiautomatic method for synthesizing a human motion that is guided by such video. After preprocessing an input video, we select a precaptured motion clip called a reference motion from a motion library. We then compute the sequence of body configurations of a virtual character by deforming this motion, according to spacetime constraints derived from a sequence of 2D features in the input video. Experimental results show that our method can synthesize highly dynamic motions, such as kicking and header motions of soccer players. We also showed the potential of our scheme as a new paradigm for motion capture, that is, capturing motions from videos taken with a monocular camera, even outside a motion capture studio.

Abstract In this paper, we present a feature‐based approach to cloning facial expressions from an input face model to an output model, using predefined source key‐models and the corresponding target key‐models. Adopting a scattered data interpolation technique, our approach consists of two parts: analysis of face key‐models and synthesis of facial expressions. In the analysis part carried out once at the beginning, key‐models are segmented automatically into five regions, each containing one of five facial features, that is, eyes, cheeks, and the mouth, which give rise to five sets of source key‐shapes and the corresponding sets of target key‐shapes. Using the key‐shapes of each source feature, those of the corresponding target feature are parameterized. In the synthesis part, given a sequence of face models comprising an input animation, five output features are obtained separately by blending their own target key‐shapes. These separately produced features are combined to synthesize the output face model at each frame. Our feature‐based approach enables cloning of diverse expressions including asymmetric ones convincingly with a small number of face key‐models while exhibiting an on‐line, real‐time performance. Copyright © 2005 John Wiley & Sons, Ltd.

In numerically controlled (NC) machining simulation, the Z-map is frequently used to represent the workpiece. Since the Z-map is usually represented by a set of Z-axis aligned vectors, the machining process can be simulated through updating it with the intersection points between the vectors and the tool swept surface. In our previous work (S.R. Maeng et al., 2003), we achieved a fast Z-map update method for linearly moving tools. On the other hand, typical NC simulation codes contain lots of circular tool movements especially for the free-form surface machining. This paper represents how to directly calculate the intersection points for the circularly moving tools. For fast computation, we express each of intersection points with a single-variable nonlinear function and calculate the candidate interval in which the unique intersection point exists. Then, we prove the existence of a solution and its uniqueness in this candidate interval. Based on these properties, we can effectively apply numerical methods to finally calculate the solution of the nonlinear function within a given precision. Due to space limitations, we focus on the filleted-end mills, the most general case of the APT (automatically programmed tool) tools. Since other tools such as ball-end mills and flat-end mills can be regarded as the special cases of the filleted-end mills, our result can be applied to the circular motions of any APT tools. Combining it to our previous result on the linear motion, we can cover most of NC simulation codes. Finally, our implementation and its result show that the new numerical approach is more efficient and reliable, in comparison to the previous methods.

Abstract In this paper, we pose a motion cloning problem of retargeting the motion of a source character to a target character with a different structure. Based on scattered data interpolation, an example‐based approach to motion cloning is proposed. Provided with a set of example motions, our method automatically extracts a small number of representative postures called source key‐postures. The animator then creates the corresponding key‐postures of the target character, breathing his/her imagination and creativity into the output animation. Exploiting this correspondence, each input posture is cloned frame by frame to the target character to produce an initial animation, which is further adjusted in space and time for retargeting and timewarping and then finalized with some interactive fine tuning. With rich animation data available, our motion cloning method aims at rapid prototyping of an animation to verify an animator's concept at an early stage. Copyright © 2004 John Wiley & Sons, Ltd.

Abstract In this paper, we present an integrated framework of on‐line motion blending for locomotion generation. We first provide a novel scheme for incremental timewarping, which always guarantees that the time goes forward. Combining the idea of motion blending with that of posture rearrangement, we introduce a motion transition graph to address on‐line motion blending and transition simultaneously. Guided by a stream of motion specifications, our motion synthesis scheme moves from node to node in an on‐line manner while blending a motion at a node and generating a transition motion at an edge. For smooth on‐line motion transition, we also attach a set of example transition motions to an edge. To represent similar postures consistently, we exploit the inter‐frame coherency embedded in the input motion specification. Finally, we provide a comprehensive solution to on‐line motion retargeting by integrating existing techniques. Copyright © 2004 John Wiley & Sons, Ltd.

Typical high-level directives for locomotion of human-like characters are useful for interactive games and simulations as well as for off-line production animation. In this paper, we present a new scheme for planning natural-looking locomotion of a biped figure to facilitate rapid motion prototyping and task-level motion generation. Given start and goal positions in a virtual environment, our scheme gives a sequence of motions to move from the start to the goal using a set of live-captured motion clips. Based on a novel combination of probabilistic path planning and hierarchical displacement mapping, our scheme consists of three parts: roadmap construction, roadmap search, and motion generation. We randomly sample a set of valid footholds of the biped figure from the environment to construct a directed graph, called a roadmap, that guides the locomotion of the figure. Every edge of the roadmap is associated with a live-captured motion clip. Augmenting the roadmap with a posture transition graph, we traverse it to obtain the sequence of input motion clips and that of target footprints. We finally adapt the motion sequence to the constraints specified by the footprint sequence to generate a desired locomotion.

Real-time animation of human-like characters is an active research area in computer graphics. The conventional approaches have, however, hardly dealt with the rhythmic patterns of motions, which are essential in handling rhythmic motions such as dancing and locomotive motions. In this paper, we present a novel scheme for synthesizing a new motion from unlabelled example motions while preserving their rhythmic pattern. Our scheme first captures the motion beats from the example motions to extract the basic movements and their transitions. Based on those data, our scheme then constructs a movement transition graph that represents the example motions. Given an input sound signal, our scheme finally synthesizes a novel motion in an on-line manner while traversing the motion transition graph, which is synchronized with the input sound signal and also satisfies kinematic constraints given explicitly and implicitly. Through experiments, we have demonstrated that our scheme can effectively produce a variety of rhythmic motions.

Tour Into the Picture (TIP) is a method for generating a sequence of walk-through images from a single reference image. By navigating a 3D scene model constructed from the image, TIP provides convincing 3D effects. This paper presents a comprehensive scheme for creating walk-through images from a video sequence by generalizing the idea of TIP. The purpose of this work is to let users experience the feel of navigating into a video sequence with their own interpretation and imagination about a given scene. To generate images from new viewpoints, we first extract the background and the foreground information from the video, and then exploit the notion of a vanishing circle to construct a 3D scene model. The proposed scheme covers various types of video films of dynamic scenes such as sports coverage, cartoon animation, and movie films, in which objects are continuously changing their shapes and locations. It can also be used to produce a variety of synthetic video sequences by importing and merging dynamic foreign objects with the original video.

Capturing live motion has gained considerable attention in computer animation as an important motion generation technique. Canned motion data are comprised of both position and orientation components. Although a great number of signal processing methods are available for manipulating position data, the majority of these methods cannot be generalized easily to orientation data due to the inherent nonlinearity of the orientation space. In this paper, we present a new scheme that enables us to apply a filter mask (or a convolution filter) to orientation data. The key idea is to transform the orientation data into their analogues in a vector space, to apply a filter mask on them, and then to transform the results back to the orientation space. This scheme gives time-domain filters for orientation data that are computationally efficient and satisfy such important properties as coordinate invariance, time invariance and symmetry. Experimental results indicate that our scheme is useful for various purposes, including smoothing and sharpening.

Tour into the picture (TIP) proposed by Horry et al.13 is a method for generating a sequence of walk-through images from a single reference picture (or image). By navigating a 3D scene model constructed from the picture, TIP produces convincing 3D effects. Assuming that the picture has one vanishing point, they proposed the scene modeling scheme called spidery mesh. However, this scheme has to go through major modification when the picture contains multiple vanishing points or does not have any well-defined vanishing point. Moreover, the spidery mesh is hard to generalize for other types of images such as panoramic images. In this paper, we propose a new scheme for TIP which is based on a single vanishing line instead of a vanishing point. Based on projective geometry, our scheme is simple and yet general enough to address the problems faced with the previous method. We also show that our scheme can be naturally extended to a panoramic image.

Computer puppetry maps the movements of a performer to an animated character in real-time. In this article, we provide a comprehensive solution to the problem of transferring the observations of the motion capture sensors to an animated character whose size and proportion may be different from the performer's. Our goal is to map as many of the important aspects of the motion to the target character as possible, while meeting the online, real-time demands of computer puppetry. We adopt a Kalman filter scheme that addresses motion capture noise issues in this setting. We provide the notion of dynamic importance of an end-effector that allows us to determine what aspects of the performance must be kept in the resulting motion. We introduce a novel inverse kinematics solver that realizes these important aspects within tight real-time constraints. Our approach is demonstrated by its application to broadcast television performances.

Digital watermarking is one of commonly used solutions for copyright protection. A watermark should be imperceptible and robust to various attacks. In this paper, we address watermarking for motion data. Our watermarking scheme is based on two well‐known ideas, so called multiresolution representation and spread spectrum. We embed a watermark into a motion signal by perturbing large detail coefficients of its multiresolution representation, and extract the watermark by analyzing perturbation of coefficients from a suspected signal. For more effective watermark extraction, we align suspected motion data to the original using dynamic time warping. Our scheme has merits of spread spectrum such as the resilience to common signal processing as well as the robustness to time warping.

Visibility-based pursuit-evasion problems are as follows: given a polygonal region, one or more searchers with visibility, and an unpredictable intruder that is arbitrarily faster than the searcher, plan the motion of the searchers so as to see the intruder.In this paper, we consider several visibility-based pursuit-evasion problems with a single searcher: l Given a simple polygon with a door (i.e., penetrable vertex) d, can a searcher find an intruder within the polygon in such a way that the intruder couldn't make a dash for the door d? l Given a simple polygon with a door d, can a searcher make no undetected intruder remain in the polygon (that is, find the intruder or evict it from the polygon through d)? l Given a building (represented as a sequence of simple polygons joined by staircases), can the searcher find the intruder within it?For each of the three problems above, we give a characterization of the class of regions that admits a search strategy and present an O(n2)-time algorithm for constructing a search path, if one exists, for an n-sided region.Interestingly, our characterizations imply that each of the above regions searchable by a searcher with omnidirectional vision (i.e., 360' vision) is also searchable by a searcher with two flashlights (i.e., ray visions).As a by-product, we improves the time complexity of the corridor search problem in [2], by a factor of log n. *This work was partially supported by KOSEF 98-0102-07-01-3.permission lo make digital or hard copies of all

This paper presents a technique for adapting existing motion of a human-like character to have the desired features that are specified by a set of constraints. This problem can be typically formulated as a spacetime constraint problem. Our approach combines a hierarchical curve fitting technique with a new inverse kinematics solver. Using the kinematics solver, we can adjust the configuration of an articulated figure to meet the constraints in each frame. Through the fitting technique, the motion displacement of every joint at each constrained frame is interpolated and thus smoothly propagated to frames. We are able to adaptively add motion details to satisfy the constraints within a specified tolerance by adopting a multilevel B-spline representation which also provides a speedup for the interpolation. The performance of our system is further enhanced by the new inverse kinematics solver. We present a closed-form solution to compute the joint angles of a limb linkage. This analytical m...

This paper proposes a new approach to image‐based rendering that generates an image viewed from an arbitrary camera position and orientation by rendering optical flows extracted from reference images. To derive valid optical flows, we develop an analysis technique that improves the quality of stereo matching. Without using any special equipments such as range cameras, this technique constructs reliable optical flows from a sequence of matching results between reference images. We also derive validity conditions of optical flows and show that the obtained flows satisfy those conditions. Since environment geometry is inferred from the optical flows, we are able to generate more accurate images with this additional geometric information. Our approach makes it possible to combine an image rendered from optical flows with an image generated by a conventional rendering technique through a simple Z‐buffer algorithm.

This paper presents an event-driven approach that efficiently detects collisions among multiple ballistic spheres moving in the 3D space. Adopting a hierarchical uniform space subdivision scheme, we are able to trace the trajectories of spheres and their time-varying spatial distribution. We identify three types of events to detect the sequence of all collisions during our simulation: collision, entering, and leaving. The first type of event is due to actual collisions, and the other two types occur when spheres move from subspace to subspace in the space. Tracing all such events in the order of their occurring times, we are able to avoid fixed time step simulation. When the size of the largest sphere is bounded by a constant multiple of that of the smallest, it takes O(n~/sub c/ log n+n~/sub e/ log n) time with O(n) space after O(n log n) time preprocessing to simulate n moving spheres, where n~/sub c/ and n~/sub e/ are the number of actual collisions and that of entering and leaving events during the simulation, respectively. Since n~/sub e/, depends on the size of subspaces, we modify the collision model from kinetic theory for molecular gas to determine the subspace sizes for the space subdivision scheme, that minimize simulation time. Experimental results show that collision detection can be done in linear time in n over a large range.

We present a new ray classification scheme that considerably reduces memory consumption while preserving its inherent time efficiency. Our key idea is due to the fact that the rays lying on the same line are duplicated over many cells in the ray classification scheme. We are thus able to lower the dimensions of the ray space by classifying lines instead of rays. Our scheme produces much simpler-shaped, compact ray cells that eventually accelerate ray shooting operations.

The paper presents an event driven approach that efficiently detects collisions among multiple moving spheres of uniform radius. We divide the space containing the spheres into uniform subspaces of cell structure. Each sphere intersecting a subspace is tested against the others intersecting the same subspace for possible collisions. We identify three types of events to detect the sequence of all collisions during our simulation: collision, entering, and leaving. The first type of events is due to actual collisions, and the other two types occur when spheres move from subspace to subspace. By tracing all such events in the order of their occurring times, we are able to simulate n moving spheres with proper collision response in O(n/sub c/ log n+n/sub e/ log n) time with O(n) space after O(n log n) time preprocessing, where n/sub c/ and n/sub e/ are the number of actual collisions and that of entering and leaving events during the simulation, respectively. Since n/sub e/ depends on the size of subspaces, we adopt the collision model from kinetic theory for molecular gas (Feynmann et al., 1963) to determine the subspace size that minimizes simulation time. Experimental results show that collision detection can be done in linear time in n over a large range.

This paper presents an event-driven approach that efficiently detects collisions among multiple moving spheres of uniform radhs.We divide the space containing the spheres into uniform subspaces of cell structure.Each sphere intersecting a subspace is teated against the others intersecting the same subspace for possible collisions.We identify three types of events to detect the sequence of all collisions during our simulation: collision, entering, and leaving.The first type of events is due to actual collisions, and the other two types occur when spheres move from subspace to subspace.By tracing all such events in the order of their occuring times, we are able to simulate n moving spheres with proper collision response[l, 5, 10] in O(rzc log n + n. log n) time with O(n) space after O(n log n) time preprocessing, where n= and ne are the number of actual collisions and that of entering and Ieaving events during the simulation, respectively.Since n, depends on the size of subspaces, we adopt the collision model from kinetic theory for molecular gas[3] to determine the subspace size that minimizes simulation time.Experimental re.dts show that collision detection can be done in linear time in n over a large range.

We consider searching problems in robotics that a robot has to find a path to a target by traveling in an unknown starshaped polygon P. The goal is to minimize the ratio of the distance traveled by the robot to the length of the shortest start-to-target path.Let s be a starting point in P. We first present a competitive strategy to find a path from s to the closest kernel point k of P. The length of the path that the robot generates is less than 1 + 2W (< 3.829) times the distance from s to k, which improves the best previous bound 5. 331 [3].Second, given a specified target t in P, we present a competitive strategy to find a path from s to t whose length does not exceed 17 times the length of the shortest s-t path.

Pacific Graphics '95, the third international conference on Computer Graphics and its Applications, was held on 21-24 August 1995, in Seoul, Korea.Following on the success of the two previous conferences: Pacific Graphics '93 (Seoul, Korea) and Pacific Graphics '94 (Beijing, China), we received 62 submissions from 22 different countries all over the world and, after peer review, selected 24 papers for publication in the conference proceedings: Computer Graphics and Applications, published by World-Scientific, Singapore.(The proceedings also include 10 invited papers.)The four papers presented in this special issue were judged by the programme committee members to be the best of the 24 selected papers presented at the conference.Each of the four papers was further reviewed by experts in the respective research area and the papers were further improved on the basis of comments received.The first paper, by Kim and Elber, presents a symbolic approach to generate blending surfaces between two polynomial and/or rational surfaces.Using a purely symbolic technique, the authors demonstrate how to compute various cross boundary tangent vector fields on each rail curve and represent the blending surfaces as polynomial or rational surfaces.The next paper, by Sun, Wang and Chin, presents a 3D morphing algorithm which transforms one polyhedral model into another.Considering each polyhedron as a graph representing vertex adjacencies, the authors develop a simple and elegant method which generalizes the 2D polygonal morphing algorithms of Sederberg to a 3D polyhedral morphing algorithm.The third paper, by Lee and Shin, presents an efficient ray casting algorithm for terrain rendering from DTMs (digital terrain models).The authors introduce a formal analysis to vertical ray coherence.Based on this analysis, they propose a new technique which covers the entire image plane with non-parallel ray lines.This

The paper describes a fast algorithm for scattered data interpolation and approximation. Multilevel B-splines are introduced to compute a C/sup 2/ continuous surface through a set of irregularly spaced points. The algorithm makes use of a coarse to fine hierarchy of control lattices to generate a sequence of bicubic B-spline functions whose sum approaches the desired interpolation function. Large performance gains are realized by using B-spline refinement to reduce the sum of these functions into one equivalent B-spline function. Experimental results demonstrate that high fidelity reconstruction is possible from a selected set of sparse and irregular samples.

Motion capturing is widely used for generating realistic motions. A 3D input device captures a sequence of 6 DOF rigid motion samples. The sampled data consists of two components, translation and orientation; the former is represented by a vector in R/sup 3/ and the latter by a rotation matrix in the rotation group, SO(3). Since the sequence of data contains sampling noises, the captured motion is now smooth and wiggles along the moving path. There are well-known fairing algorithms in Euclidean space based on difference geometry. Extending these for the motion data, we present a new fairing algorithm. The new algorithm iteratively minimizes the energy function reflecting the forces and torques, exerted on a moving object, to perform motion fairing.

This paper presents a compact differential formula for the first derivative of a unit quaternion curve defined on SO(3) or S3. The formula provides a convenient way to compute the angular velocity of a rotating 3D solid. We demonstrate the effectiveness of this formula by deriving the differential properties of various unit quaternion curves1–5 at the curve end points.

This paper presents a new image morphing method using a two-dimensional deformation technique which provides an intuitive model for a warp. The deformation technique derives aC1-continuous and one-to-one warp from a set of point pairs overlaid on two images. The resulting in-between image precisely reflects the correspondence of features specified by an animator. We also control the transition behaviour in a metamorphosis sequence by taking another deformable surface model, which is simpler and thus more efficient than the deformation technique for a warp. The proposed method separates transition control from feature interpolation and is easier to use than the previous techniques. The multigrid relaxation method is employed to solve a linear system in deriving a warp or transition rates. This method makes our image morphing technique fast enough for an interactive environment.

This paper describes an image metamorphosis technique to handle scattered feature constraints specified with points, polylines, and splines. Solutions to the following three problems are presented: feature specification, warp generation, and transition control. We demonstrate the use of snakes to reduce the burden of feature specification. Next, we propose the use of multilevel free-form deformations (MFFD) to compute C/sup 2/-continuous and one-to-one mapping functions among the specified features. The resulting technique, based on B-spline approximation, is simpler and faster than previous warp generation methods. Furthermore, it produces smooth image transformations without undesirable ripples and foldovers. Finally, we simplify the MFFD algorithm to derive transition functions to control geometry and color blending. Implementation details are furnished and comparisons among various metamorphosis techniques are presented.

An algorithm is presented that constructs a C/sup 2/-continuous B-spline quaternion curve which interpolates a given sequence of unit quaternions on the rotation group SO(3). The de Casteljau type construction method of B-spline curves can be extended to generate B-spline quaternion curves; however, the B-spline quaternion curves do not have C/sup 2/-continuity in SO(3). The authors recently suggested a new construction method that can extend a B-spline curve to a similar one in SO(3) while preserving the C/sup k/-continuity of the B-spline curve. We adapt this method for the construction of a B-spline quaternion interpolation curve. Thus, the problem essentially reduces to the problem of finding the control points for the B-spline interpolation curve. However, due to the non-linearity of the associated constraint equations, it is non-trivial to compute the B-spline control points. We provide an efficient iterative refinement solution which can approximate the control points very precisely.>

This paper proposesa new class of unit quaternion curves in SO(3). A general method is developed that transforms a curve in R 3 (defined as a weighted sum of basis functions) into its unit quaternion analogue in SO(3). Applying the method to well-known spline curves (such as Bezier, Hermite, and B-spline curves), we are able to construct various unit quaternion curves which share many important differential properties with their original curves. Many of our naive common beliefs in geometry break down even in the simple non-Euclidean space S 3 or SO(3). For example, the de Casteljau type construction of cubic B-spline quaternion curves does not preserve C 2 -continuity [10]. Through the use of decomposition into simple primitive quaternion curves, our quaternion curves preserve most of the algebraic and differential properties of the original spline curves. CR Descriptors: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling -- Curve, surface, solid, and object representation, -- Geometric algorithms. Keywords: Quaternion, rotation, orientation, SO(3), Bezier, Hermite, B-spline 1

This paper presents new solutions to the following three problems in image morphing: feature specification, warp generation, and transition control.To reduce the burden of feature specification, we first adopt a computer vision technique called snakes.We next propose the use of multilevel free-form deformations (MFFD) to achieve C 2 -continuous and one-to-one warps among feature point pairs.The resulting technique, based on B-spline approximation, is simpler and faster than previous warp generation methods.Finally, we simplify the MFFD method to construct C 2 -continuous surfaces for deriving transition functions to control geometry and color blending.

This paper presents a new image morphing technique using deformable surfaces. Drawbacks of previous techniques are overcome by a physically-based approach which provides an intuitive model for a warp. A warp is derived by two deformable surfaces which specify horizontal and vertical displacements of points on an image. This paper also considers the control of transition behavior in a metamorphosis sequence. The presented technique separates the transition control from interpolating features making it much easier to use than the previous techniques. The multigrid relaxation method is used to compute a deformable surface for a warp or transition rates. This method makes the presented image morphing technique fast enough for an interactive environment.>

By treating the floor plan of the building as a polygon, the authors study the problem of locating a camera for surveillance. A polygon P is point-visible if there exists a point x in P such that every other point in P is visible from x. If the polygon is point-visible then only one camera is needed. A visible edge corresponds to the wall on which the camera is to be mounted. While a given edge can be tested for visibility in time linear in the number of edges, there can be O(n) such edges. An O(n) time algorithm for finding all visible edges in a point-visible polygon is given. Specifically, it is shown that if the kernel of a simple polygon is nonempty, then all visible edges, whether completely, strongly, or weakly visible, can be found in O(n) time.>