Recent probabilistic methods for 3D triangular meshes capture diverse shapes by differentiable mesh connectivity, but face high computational costs with increased shape details. We introduce a new differentiable mesh processing method in 2D and 3D that addresses this challenge and efficiently handles meshes with intricate structures. Additionally, we present an algorithm that adapts the mesh resolution to local geometry in 2D for efficient representation. We demonstrate the effectiveness of our approach on 2D point cloud and 3D multi-view reconstruction tasks. Visit our project page (https://sonsang.github.io/dmesh2-project) for source code and supplementary material.

In this work, we introduce the Time-Aware World Model (TAWM), a model-based approach that explicitly incorporates temporal dynamics. By conditioning on the time-step size, $\Delta t$, and training over a diverse range of $\Delta t$ values – rather than sampling at a fixed time-step – TAWM learns both high- and low-frequency task dynamics across diverse control problems. Grounded in the information-theoretic insight that the optimal sampling rate depends on a system’s underlying dynamics, this time-aware formulation improves both performance and data efficiency. Empirical evaluations show that TAWM consistently outperforms conventional models across varying observation rates in a variety of control tasks, using the same number of training samples and iterations. Our code can be found online at: github.com/anh-nn01/Time-Aware-World-Model.

Achieving robustness in image segmentation models is challenging due to the fine-grained nature of pixel-level classification. These models, which are crucial for many real-time perception applications, particularly struggle when faced with natural corruptions in the wild for autonomous systems. While sensitivity analysis can help us understand how input variables influence model outputs, its application to natural and uncontrollable corruptions in training data is computationally expensive. In this work, we present an adaptive, sensitivity-guided augmentation method to enhance robustness against natural corruptions. Our sensitivity analysis on average runs 10 times faster and requires about 200 times less storage than previous sensitivity analysis, enabling practical, on-the-fly estimation during training for a model-free augmentation policy. With minimal fine-tuning, our sensitivity-guided augmentation method achieves improved robustness on both real-world and synthetic datasets compared to state-of-the-art data augmentation techniques in image segmentation.

Handling pre-crash scenarios is still a major challenge for self-driving cars due to limited practical data and human-driving behavior datasets. We introduce DISC (Driving Styles In Simulated Crashes), one of the first datasets designed to capture various driving styles and behaviors in precrash scenarios for mixed autonomy analysis. DISC includes over 8 classes of driving styles/behaviors from hundreds of drivers navigating a simulated vehicle through a virtual city, encountering rare-event traffic scenarios. This dataset enables the classification of pre-crash human driving behaviors in unsafe conditions, supporting individualized trajectory prediction based on observed driving patterns. By utilizing a custom-designed VR-based in-house driving simulator, TRAVERSE, data was collected through a driver-centric study involving human drivers encountering twelve simulated accident scenarios. This dataset fills a critical gap in human-centric driving data for rare events involving interactions with autonomous vehicles. It enables autonomous systems to better react to human drivers and optimize trajectory prediction in mixed autonomy environments involving both human-driven and self-driving cars. In addition, individual driving behaviors are classified through a set of standardized questionnaires, carefully designed to identify and categorize driving behavior traits. We correlate data features with driving behaviors, showing that the simulated environment reflects real-world driving styles. DISC is the first dataset to capture how various driving styles respond to accident scenarios, offering significant potential to enhance autonomous vehicle safety and driving behavior analysis in mixed autonomy environments.

We present a parallelized differentiable traffic simulator based on the Intelligent Driver Model (IDM), a car-following framework that incorporates driver behavior as key variables. Our vehicle simulator efficiently models vehicle motion, generating trajectories that can be supervised to fit real-world data. By leveraging its differentiable nature, IDM parameters are optimized using gradient-based methods. With the capability to simulate up to 2 million vehicles in real time, the system is scalable for large-scale trajectory optimization. We show that we can use the simulator to filter noise in the input trajectories (trajectory filtering), reconstruct dense trajectories from sparse ones (trajectory reconstruction), and predict future trajectories (trajectory prediction), with all generated trajectories adhering to physical laws. We validate our simulator and algorithm on several datasets including NGSIM and Waymo Open Dataset. The code is publicly available at: https://github.com/SonSang/diffidm.

Autonomous systems have advanced significantly, but challenges persist in accident-prone environments where robust decision-making is crucial. A single vehicle’s limited sensor range and obstructed views increase the likelihood of accidents. Multi-vehicle connected systems and multi-modal approaches, leveraging RGB images and LiDAR point clouds, have emerged as promising solutions. However, existing methods often assume the availability of all data modalities and connected vehicles during both training and testing, which is impractical due to potential sensor failures or missing connected vehicles. To address these challenges, we introduce a novel framework MMCD (Multi-Modal Collaborative Decision-making) for connected autonomy. Our framework fuses multi-modal observations from ego and collaborative vehicles to enhance decision-making under challenging conditions. To ensure robust performance when certain data modalities are unavailable during testing, we propose an approach based on cross-modal knowledge distillation with a teacher-student model structure. The teacher model is trained with multiple data modalities, while the student model is designed to operate effectively with reduced modalities. In experiments on connected autonomous driving with ground vehicles and aerial-ground vehicles collaboration, our method improves driving safety by up to 20.7%, surpassing the best-existing baseline in detecting potential accidents and making safe driving decisions. More information can be found on our website https://ruiiu.github.io/mmcd.

Trajectory forecasting has become a popular deep learning task due to its relevance for scenario simulation for autonomous driving. Specifically, trajectory forecasting predicts the trajectory of a short-horizon future for specific human drivers in a particular traffic scenario. Robust and accurate future predictions can enable autonomous driving planners to optimize for low-risk and predictable outcomes for human drivers around them. Although some work has been done to model driving style in planning and personalized autonomous polices, a gap exists in explicitly modeling human driving styles for trajectory forecasting of human behavior. Human driving style is most certainly a correlating factor to decision making, especially in edge-case scenarios where risk is nontrivial, as justified by the large amount of traffic psychology literature on risky driving. So far, the current real-world datasets for trajectory forecasting lack insight on the variety of represented driving styles. While the datasets may represent real-world distributions of driving styles, we posit that fringe driving style types may also be correlated with edge-case safety scenarios. In this work, we conduct analyses on existing real-world trajectory datasets for driving and dissect these works from the lens of driving styles, which is often intangible and non-standardized.

Multi-modal learning has emerged as a key technique for improving performance across domains such as autonomous driving, robotics, and reasoning. However, in certain scenarios, particularly in resource-constrained environments, some modalities available during training may be absent during inference. While existing frameworks effectively utilize multiple data sources during training and enable inference with reduced modalities, they are primarily designed for single-agent settings. This poses a critical limitation in dynamic environments such as connected autonomous vehicles (CAV), where incomplete data coverage can lead to decision-making blind spots. Conversely, some works explore multi-agent collaboration but without addressing missing modality at test time. To overcome these limitations, we propose Collaborative Auxiliary Modality Learning (CAML), a novel multi-modal multi-agent framework that enables agents to collaborate and share multi-modal data during training, while allowing inference with reduced modalities during testing. Experimental results in collaborative decision-making for CAV in accident-prone scenarios demonstrate that CAML achieves up to a 58.1% improvement in accident detection. Additionally, we validate CAML on real-world aerial-ground robot data for collaborative semantic segmentation, achieving up to a 10.6% improvement in mIoU.

This paper presents a novel adjoint solver for differentiable fluid simulation based on bidirectional flow maps. Our key observation is that the forward fluid solver and its corresponding backward, adjoint solver share the same flow map as the forward simulation. In the forward pass, this map transports fluid impulse variables from the initial frame to the current frame to simulate vortical dynamics. In the backward pass, the same map propagates adjoint variables from the current frame back to the initial frame to compute gradients. This shared long-range map allows the accuracy of gradient computation to benefit directly from improvements in flow map construction. Building on this insight, we introduce a novel adjoint solver that solves the adjoint equations directly on the flow map, enabling long-range and accurate differentiation of incompressible flows without differentiating intermediate numerical steps or storing intermediate variables, as required in conventional adjoint methods. To further improve efficiency, we propose a long-short time-sparse flow map representation for evolving adjoint variables. Our approach has low memory usage, requiring only 6.53GB of data at a resolution of 1923 while preserving high accuracy in tracking vorticity, enabling new differentiable simulation tasks that require precise identification, prediction, and control of vortex dynamics.

Scene-aware Complementary Item Retrieval (CIR) is a challenging task which requires to generate a set of compatible items across domains. Due to the subjectivity, it is difficult to set up a rigorous standard for both data collection and learning objectives. To address this challenging task, we propose a visual compatibility concept, composed of similarity (resembling in color, geometry, texture, and etc.) and complementarity (different items like table vs chair completing a group). Based on this notion, we propose a compatibility learning framework, a category-aware Flexible Bidirectional Transformer (FBT), for visual ``scene-based set compatibility reasoning'' with the cross-domain visual similarity input and auto-regressive complementary item generation. We introduce a ``Flexible Bidirectional Transformer (FBT),'' consisting of an encoder with flexible masking, a category prediction arm, and an auto-regressive visual embedding prediction arm. And the inputs for FBT are cross-domain visual similarity invariant embeddings, making this framework quite generalizable. Furthermore, our proposed FBT model learns the inter-object compatibility from a large set of scene images in a self-supervised way. Compared with the SOTA methods, this approach achieves up to 5.3% and 9.6% in FITB score and 22.3% and 31.8% SFID improvement on fashion and furniture, respectively.

Vector fields are widely used to represent and model flows for many science and engineering applications. This paper introduces a novel neural network architecture for learning tangent vector fields that are intrinsically defined on manifold surfaces embedded in 3D. Previous approaches to learning vector fields on surfaces treat vectors as multi-dimensional scalar fields, using traditional scalar-valued architectures to process channels individually, thus fail to preserve fundamental intrinsic properties of the vector field. The core idea of this work is to introduce a trainable vector heat diffusion module to spatially propagate vector-valued feature data across the surface, which we incorporate into our proposed architecture that consists of vector-valued neurons. Our architecture is invariant to rigid motion of the input, isometric deformation, and choice of local tangent bases, and is robust to discretizations of the surface. We evaluate our Vector Heat Network on triangle meshes, and empirically validate its invariant properties. We also demonstrate the effectiveness of our method on the useful industrial application of quadrilateral mesh generation.

Collaborative decision-making is an essential capability for multi-robot systems, such as connected vehicles, to collaboratively control autonomous vehicles in accident-prone scenarios. Under limited communication bandwidth, capturing comprehensive situational awareness by integrating connected agents’ observation is very challenging. In this paper, we propose a novel collaborative decision-making method that efficiently and effectively integrates collaborators’ representations to control the ego vehicle in accident-prone scenarios. Our approach formulates collaborative decision-making as a classification problem. We first represent sequences of raw observations as spatiotemporal graphs, which significantly reduce the package size to share among connected vehicles. Then we design a novel spatiotemporal graph neural network based on heterogeneous graph learning, which analyzes spatial and temporal connections of objects in a unified way for collaborative decision-making. We evaluate our approach using a high-fidelity simulator that considers realistic traffic, communication bandwidth, and vehicle sensing among connected autonomous vehicles. The experimental results show that our representation achieves over 100x reduction in the shared data size that meets the requirements of communication bandwidth for connected autonomous driving. In addition, our approach achieves over 30% improvements in driving safety.

We present a novel learning-based trajectory generation algorithm for outdoor robot navigation. Our goal is to compute collision-free paths that also satisfy the environment-specific traversability constraints. Our approach is designed for global planning using limited onboard robot perception in mapless environments while ensuring comprehensive coverage of all traversable directions. Our formulation uses a Conditional Variational Autoencoder (CVAE) generative model that is enhanced with traversability constraints and an optimization formulation used for the coverage. We highlight the benefits of our approach over state-of-the-art trajectory generation approaches and demonstrate its performance in challenging and large outdoor environments, including around buildings, across intersections, along trails, and off-road terrain, using a Clearpath Husky and a Boston Dynamics Spot robot. In practice, our approach results in a 6% improvement in coverage of traversable areas and an 89% reduction in trajectory portions residing in non-traversable regions. Our video is here: https://youtu.be/3eJ2soAzXnU

Environments for autonomous driving can vary from place to place, leading to challenges in designing a learning model for a new scene. Transfer learning can leverage knowledge from a learned domain to a new domain with limited data. In this work, we focus on end-to-end autonomous driving as the target task, consisting of both perception and control. We first utilize information bottleneck analysis to build a causal graph that defines our framework and the loss function; then we propose a novel domain-agnostic learning method for autonomous steering based on our analysis of training data, network architecture, and training paradigm. Experiments show that our method outperforms other SOTA methods.

Various heuristic objectives for modeling hand-object interaction have been proposed in past work. However, due to the lack of a cohesive framework, these objectives often possess a narrow scope of applicability and are limited by their efficiency or accuracy. In this paper, we propose HANDYPRIORS, a unified and general pipeline for pose estimation in human-object interaction scenes by leveraging recent advances in differentiable physics and rendering. Our approach employs rendering priors to align with input images and segmentation masks along with physics priors to mitigate penetration and relative-sliding across frames. Furthermore, we present two alternatives for hand and object pose estimation. The optimization-based pose estimation achieves higher accuracy, while the filtering-based tracking, which utilizes the differentiable priors as dynamics and observation models, executes faster. We demonstrate that HANDYPRIORS attains comparable or superior results in the pose estimation task, and that the differentiable physics module can predict contact information for pose refinement. We also show that our approach generalizes to perception tasks, including robotic hand manipulation and human-object pose estimation in the wild.

Data for training learning-enabled self-driving cars in the physical world are typically collected in a safe, normal environment. Such data distribution often engenders a strong bias towards safe driving, making self-driving cars unprepared when encountering adversarial scenarios like unexpected accidents. Due to a dearth of such adverse data that is unrealistic for drivers to collect, autonomous vehicles can perform poorly when experiencing such rare events. This work addresses much-needed research by having participants drive a VR vehicle simulator going through simulated traffic with various types of accidental scenarios. It aims to understand human responses and behaviors in simulated accidents, contributing to our understanding of driving dynamics and safety. The simulation framework adopts a robust traffic simulation and is rendered using the Unity Game Engine. Furthermore, the simulation framework is built with portable, light-weight immersive driving simulator hardware, lowering the resource barrier for studies in autonomous driving research.

In trajectory forecasting tasks for traffic, future output trajectories can be computed by advancing the ego vehicle’s state with predicted actions according to a kinematics model. By unrolling predicted trajectories via time integration and models of kinematic dynamics, predicted trajectories should not only be kinematically feasible but also relate uncertainty from one timestep to the next. While current works in probabilistic prediction do incorporate kinematic priors for mean trajectory prediction, variance is often left as a learnable parameter, despite uncertainty in one time step being inextricably tied to uncertainty in the previous time step. In this paper, we show simple and differentiable analytical approximations describing the relationship between variance at one timestep and that at the next with the kinematic bicycle model. In our results, we find that encoding the relationship between variance across timesteps works especially well in unoptimal settings, such as with small or noisy datasets. We observe up to a 50% performance boost in partial dataset settings and up to an 8% performance boost in large-scale learning compared to previous kinematic prediction methods on SOTA trajectory forecasting architectures out-of-the-box, with no fine-tuning.

We present a differentiable representation, DMesh, for general 3D triangular meshes. DMesh considers both the geometry and connectivity information of a mesh. In our design, we first get a set of convex tetrahedra that compactly tessellates the domain based on Weighted Delaunay Triangulation (WDT), and select triangular faces on the tetrahedra to define the final mesh. We formulate probability of faces to exist on the actual surface in a differentiable manner based on the WDT. This enables DMesh to represent meshes of various topology in a differentiable way, and allows us to reconstruct the mesh under various observations, such as point clouds and multi-view images using gradient-based optimization. We publicize the source code and supplementary material at our project page (https://sonsang.github.io/dmesh-project).

As industrial models and designs grow increasingly complex, the demand for optimal control of large-scale dynamical systems has significantly increased. However, traditional methods for optimal control incur significant overhead as problem dimensions grow. In this paper, we introduce an end-to-end quantum algorithm for linear-quadratic control with provable speedups. Our algorithm, based on a policy gradient method, incorporates a novel quantum subroutine for solving the matrix Lyapunov equation. Specifically, we build a *quantum-assisted differentiable simulator* for efficient gradient estimation that is more accurate and robust than classical methods relying on stochastic approximation. Compared to the classical approaches, our method achieves a *super-quadratic* speedup. To the best of our knowledge, this is the first end-to-end quantum application to linear control problems with provable quantum advantage.

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

Embedding polygonal mesh assets within photorealistic Neural Radience Fields (NeRF) volumes, such that they can be rendered and their dynamics simulated in a physically consistent manner with the NeRF, is under-explored from the system perspective of integrating NeRF into the traditional graphics pipeline. This paper designs a two-way coupling between mesh and NeRF during rendering and simulation. We first review the light transport equations for both mesh and NeRF, then distill them into an efficient algorithm for updating radiance and throughput along a cast ray with an arbitrary number of bounces. To resolve the discrepancy between the linear color space that the path tracer assumes and the sRGB color space that standard NeRF uses, we train NeRF with High Dynamic Range (HDR) images. We also present a strategy to estimate light sources and cast shadows on the NeRF. Finally, we consider how the hybrid surface-volumetric formulation can be efficiently integrated with a high-performance physics simulator that supports cloth, rigid and soft bodies. The full rendering and simulation system can be run on a GPU at interactive rates. We show that a hybrid system approach outperforms alternatives in visual realism for mesh insertion, because it allows realistic light transport from volumetric NeRF media onto surfaces, which affects the appearance of reflective/refractive surfaces and illumination of diffuse surfaces informed by the dynamic scene.

Driven by the need from real-world applications, Auxiliary Modality Learning (AML) offers the possibility to utilize more information from auxiliary data in training, while only requiring data from one or fewer modalities in test, to save the overall computational cost and reduce the amount of input data for inferencing. In this work, we formally define ``Auxiliary Modality Learning'' (AML), systematically classify types of auxiliary modality (in visual computing) and architectures for AML, and analyze their performance. We also analyze the conditions under which AML works well from the optimization and data distribution perspectives. To guide various choices to achieve optimal performance using AML, we propose a novel method to assist in choosing the best auxiliary modality and estimating an upper bound performance before executing AML. In addition, we propose a new AML method using generalized curriculum distillation to enable more effective curriculum learning. Our method achieves the best performance compared to other SOTA methods.

We present a learning algorithm, DifFAR, for human activity recognition in videos. Our approach is designed for UAV videos, which are mainly acquired from obliquely placed dynamic cameras that contain a human actor along with background motion. Typically, the human actors occupy less than one-tenth of the spatial resolution. DifFAR simultaneously harnesses the benefits of frequency domain representations, a classical analysis tool in signal processing, and data driven neural networks. We build a differentiable static-dynamic frequency mask prior to model the salient static and dynamic pixels in the video, crucial for the underlying task of action recognition. We use this differentiable mask prior to enable the neural network to intrinsically learn disentangled feature representations via an identity loss function. Our formulation empowers the network to inherently compute disentangled salient features within its layers. Further, we propose a cost-function encapsulating temporal relevance and spatial content to sample the most important frame within uniformly spaced video segments. We conduct extensive experiments on the UAV Human dataset and the NEC Drone dataset and demonstrate relative improvements of 5.72% - 13.00% over the state-of-the-art and 14.28% - 38.05% over the corresponding baseline model.

In this paper, we propose a novel learning framework for autonomous systems that uses a small amount of “auxiliary information” that complements the learning of the main modality, called “small-shot auxiliary modality distillation network (AMD-S-Net)”. The AMD-S-Net contains a two-stream framework design that can fully extract information from different types of data (i.e., paired/unpaired multi-modality data) to distill knowledge more effectively. We also propose a novel training paradigm based on the “reset operation” that enables the teacher to explore the local loss landscape near the student domain iteratively, providing local landscape information and potential directions to discover better solutions by the student, thus achieving higher learning performance. Our experiments show that AMD-S-Net and our training paradigm outperform other SOTA methods by up to 12.7% and 18.1% improvement in autonomous steering, respectively.

Haptic feedback is an important component of creating an immersive mixed reality experience. Traditionally, haptic forces are rendered in response to the user's interactions with the virtual environment. In this work, we explore the idea of rendering haptic forces in a proactive manner, with the explicit intention to influence the user's behavior through compelling haptic forces. To this end, we present a framework for active haptic guidance in mixed reality, using one or more robotic haptic proxies to influence user behavior and deliver a safer and more immersive virtual experience. We provide details on common challenges that need to be overcome when implementing active haptic guidance, and discuss example applications that show how active haptic guidance can be used to influence the user's behavior. Finally, we apply active haptic guidance to a virtual reality navigation problem, and conduct a user study that demonstrates how active haptic guidance creates a safer and more immersive experience for users.

While there have been advancements in autonomous driving control and traffic simulation, there have been little to no works exploring their unification with deep learning. Works in both areas seem to focus on entirely different exclusive problems, yet traffic and driving are inherently related in the real world. In this paper, we present Traffic-Aware Autonomous Driving (TrAAD), a generalizable distillation-style method for traffic-informed imitation learning that directly optimizes for faster traffic flow and lower energy consumption. TrAAD focuses on the supervision of speed control in imitation learning systems, as most driving research focuses on perception and steering. Moreover, our method addresses the lack of co-simulation between traffic and driving simulators and provides a basis for directly involving traffic simulation with autonomous driving in future work. Our results show that, with information from traffic simulation involved in the supervision of imitation learning methods, an autonomous vehicle can learn how to accelerate in a fashion that is beneficial for traffic flow and overall energy consumption for all nearby vehicles.

Place recognition plays an important role in multi-robot collaborative perception, such as aerial-ground search and rescue, in order to identify the same place they have visited. Recently, approaches based on semantics showed the promising performance to address cross-view and cross-modal challenges in place recognition, which can be further categorized as graph-based and geometric-based methods. However, both methods have shortcomings, including ignoring geometric cues and affecting by large non-overlapped regions between observations. In this paper, we introduce a novel approach that integrates semantic graph matching and distance fields (DF) matching for cross-view and cross-modal place recognition. Our method uses a graph representation to encode visual-spatial cues of semantics and uses a set of class-wise DFs to encode geometric cues of a scene. Then, we formulate place recognition as a two-step matching problem. We first perform semantic graph matching to identify the correspondence of semantic objects. Then, we estimate the overlapped regions based on the identified correspondences and further align these regions to compute their geometric-based DF similarity. Finally, we integrate graph-based similarity and geometry-based DF similarity to match places. We evaluate our approach over two public benchmark datasets, including KITTI and AirSim. Compared with the previous methods, our approach achieves around 10% improvement in ground-ground place recognition in KITTI and 35% improvement in aerial-ground place recognition in AirSim.

We introduce a novel policy learning method that integrates analytical gradients from differentiable environments with the Proximal Policy Optimization (PPO) algorithm. To incorporate analytical gradients into the PPO framework, we introduce the concept of an α-policy that stands as a locally superior policy. By adaptively modifying the α value, we can effectively manage the influence of analytical policy gradients during learning. To this end, we suggest metrics for assessing the variance and bias of analytical gradients, reducing dependence on these gradients when high variance or bias is detected. Our proposed approach outperforms baseline algorithms in various scenarios, such as function optimization, physics simulations, and traffic control environments. Our code can be found online: https://github.com/SonSang/gippo.

We present a Body Measurement network (BMnet) for estimating 3D anthropomorphic measurements of the human body shape from silhouette images. Training of BMnet is performed on data from real human subjects, and augmented with a novel adversarial body simulator (ABS) that finds and synthesizes challenging body shapes. ABS is based on the skinned multiperson linear (SMPL) body model, and aims to maximize BMnet measurement prediction error with respect to latent SMPL shape parameters. ABS is fully differentiable with respect to these parameters, and trained end-to-end via backpropagation with BMnet in the loop. Experiments show that ABS effectively discovers adversarial examples, such as bodies with extreme body mass indices (BMI), consistent with the rarity of extreme-BMI bodies in BMnet's training set. Thus ABS is able to reveal gaps in training data and potential failures in predicting under-represented body shapes. Results show that training BMnet with ABS improves measurement prediction accuracy on real bodies by up to 10%, when compared to no augmentation or random body shape sampling. Furthermore, our method significantly outperforms SOTA measurement estimation methods by as much as 3x. Finally, we release BodyM, the first challenging, large-scale dataset of photo silhouettes and body measurements of real human subjects, to further promote research in this area. Project website: https://adversarialbodysim.github.io.

Despite significant advancements, collision-free navigation in autonomous driving is still challenging, considering the navigation module needs to balance learning and planning to achieve efficient and effective control of the vehicle. We propose a novel framework of inverse reinforcement learning with hybrid-weight trust-region optimization and curriculum learning (IRL-HC) for autonomous maneuvering. Our method can incorporate both expert demonstration (from real driving) and domain knowledge (hard constraints such as collision avoidance, goal reaching, etc. encoded in reward functions) to learn an effective control policy. The hybrid-weight trustregion optimization is used to determine the difficulty of the task curriculum for fast incremental curriculum learning and improve the efficiency of inverse reinforcement learning by hybrid weight tuning of different sets of hyperparameters. IRL-HC is also compatible with domain-dependent techniques such as learn-from-accident, which can further boost performance. Overall, IRL-HC can reduce the number of collisions up to 48%, increase the training efficiency by 2.8x, and enable the vehicle to drive 10x further compared to other methods.

Reflective and textureless surfaces such as windows, mirrors, and walls can be a challenge for scene reconstruction, due to depth discontinuities and holes. We propose an audio-visual method that uses the reflections of sound to aid in depth estimation and material classification for 3D scene reconstruction in robot navigation and AR/VR applications. The mobile phone prototype emits pulsed audio, while recording video for audio-visual classification for 3D scene reconstruction. Reflected sound and images from the video are input into our audio (EchoCNN-A) and audio-visual (EchoCNN-AV) convolutional neural networks for surface and sound source detection, depth estimation, and material classification. The inferences from these classifications enhance 3D scene reconstructions containing open spaces and reflective surfaces by depth filtering, inpainting, and placement of unmixed sound sources in the scene. Our prototype, demos, and experimental results from real-world with challenging surfaces and sound, also validated with virtual scenes, indicate high success rates on classification of material, depth estimation, and closed/open surfaces, leading to considerable improvement in 3D scene reconstruction for robot navigation.

We formulate the first differentiable analog quantum computing framework with specific parameterization design at the analog signal (pulse) level to better exploit near-term quantum devices via variational methods. We further propose a scalable approach to estimate the gradients of quantum dynamics using a forward pass with Monte Carlo sampling, which leads to a quantum stochastic gradient descent algorithm for scalable gradient-based training in our framework. Applying our framework to quantum optimization and control, we observe a significant advantage of differentiable analog quantum computing against SOTAs based on parameterized digital quantum circuits by {\em orders of magnitude}.

We present a method for learning 3D geometry and physics parameters of a dynamic scene from only a monocular RGB video input. To decouple the learning of underlying scene geometry from dynamic motion, we represent the scene as a time-invariant signed distance function (SDF) which serves as a reference frame, along with a time-conditioned deformation field. We further bridge this neural geometry representation with a differentiable physics simulator by designing a two-way conversion between the neural field and its corresponding hexahedral mesh, enabling us to estimate physics parameters from the source video by minimizing a cycle consistency loss. Our method also allows a user to interactively edit 3D objects from the source video by modifying the recovered hexahedral mesh, and propagating the operation back to the neural field representation. Experiments show that our method achieves superior mesh and video reconstruction of dynamic scenes compared to competing Neural Field approaches, and we provide extensive examples which demonstrate its ability to extract useful 3D representations from videos captured with consumer-grade cameras.

Visual Media were recommended by the associate editors as candidate papers for the Best Paper Award.The Editor-in-Chief then invited the three of us to serve as the committee for choosing the Best Paper.After careful discussion by the committee, the following paper is chosen as the winner of the Best Paper Award: EfficientPose: Efficient human pose estimation with neural architecture search [1] while two other papers are awarded the Honorable Mention Awards: Efficient fastest-path computations for road maps [2]Inferring object properties from human interaction and transferring them to new motions [3] The Best Paper Award Committee would like to offer congratulations to the winners, who in addition to the prestige conferred upon them by the awards, will also receive cash prizes: the Best Paper will receive US

We introduce a novel differentiable hybrid traffic simulator , which simulates traffic using a hybrid model of both macroscopic and microscopic models and can be directly integrated into a neural network for traffic control and flow optimization. This is the first differentiable traffic simulator for macroscopic and hybrid models that can compute gradients for traffic states across time steps and inhomogeneous lanes. To compute the gradient flow between two types of traffic models in a hybrid framework, we present a novel intermediate conversion component that bridges the lanes in a differentiable manner as well. We also show that we can use analytical gradients to accelerate the overall process and enhance scalability. Thanks to these gradients, our simulator can provide more efficient and scalable solutions for complex learning and control problems posed in traffic engineering than other existing algorithms. Refer to https://sites.google.com/umd.edu/diff-hybrid-traffic-sim for our project.

We introduce an efficient differentiable fluid simulator that can be integrated with deep neural networks as a part of layers for learning dynamics and solving control problems. It offers the capability to handle one-way coupling of fluids with rigid objects using a variational principle that naturally enforces necessary boundary conditions at the fluid-solid interface with sub-grid details. This simulator utilizes the adjoint method to efficiently compute the gradient for multiple time steps of fluid simulation with user defined objective functions. We demonstrate the effectiveness of our method for solving inverse and control problems on fluids with one-way coupled solids. Our method outperforms the previous gradient computations, state-of-the-art derivative-free optimization, and model-free reinforcement learning techniques by at least one order of magnitude.

We present a method for efficient differentiable simulation of articulated bodies. This enables integration of articulated body dynamics into deep learning frameworks, and gradient-based optimization of neural networks that operate on articulated bodies. We derive the gradients of the contact solver using spatial algebra and the adjoint method. Our approach is an order of magnitude faster than autodiff tools. By only saving the initial states throughout the simulation process, our method reduces memory requirements by two orders of magnitude. We demonstrate the utility of efficient differentiable dynamics for articulated bodies in a variety of applications. We show that reinforcement learning with articulated systems can be accelerated using gradients provided by our method. In applications to control and inverse problems, gradient-based optimization enabled by our work accelerates convergence by more than an order of magnitude.

An important aspect of dynamic urban coverage is how building collision avoidance is incorporated into the overall coverage mission. We consider a multi-agent urban dynamic coverage problem in which a team of flying agents uses downward facing cameras to observe the street-level environment outside of buildings. Cameras are assumed to be ineffective above a maximum altitude (lower than building height), such that agents must move around or over buildings to complete their mission. The main objective of this paper is to compare three different building avoidance strategies that are compatible with dynamic ergodic methods. To provide context for these results, we also compare our results to three other common coverage methods including: boustrophedon coverage (lawn-mower sweep), Voronoi region based coverage, and a naive grid method. All algorithms are evaluated in simulation with respect to four performance metrics (percent coverage, revisit count, revisit time, and the integral of area viewed over time), across team sizes ranging from 1 to 25 agents, and in five types of urban environments of varying density and height. We find that the relative performance of algorithms changes based on the ratio of team size to search area, as well the height and density characteristics of the urban environment.

Autonomous systems often rely on neural networks to achieve high performance on planning and control problems. Unfortunately, neural networks suffer severely when input images become degraded in ways that are not reflected in the training data. This is particularly problematic for robotic systems like autonomous vehicles (AV) for which reliability is paramount. In this work, we consider robust optimization methods for hardening control systems against image corruptions and other unexpected domain shifts. Recent work on robust optimization for neural nets has been focused largely on combating adversarial attacks. In this work, we borrow ideas from the adversarial training and data augmentation literature to enhance robustness to image corruptions and domain shifts. To this end, we train networks while augmenting image data with a battery of image degradations. Unlike traditional augmentation methods, we choose the parameters for each degradation adversarially so as to maximize system performance. By formulating image degradations in a way that is differentiable with respect to degradation parameters, we enable the use of efficient optimization methods (PGD) for choosing worst-case augmentation parameters. We demonstrate the efficacy of this method on the learning to steer task for AVs. By adversarially training against image corruptions, we produce networks that are highly robust to image corruptions. We show that the proposed differentiable augmentation schemes result in higher levels of robustness and accuracy for a range of settings as compared to baseline and state-of-the-art augmentation methods.

We present a method for differentiable simulation of soft articulated bodies. Our work enables the integration of differentiable physical dynamics into gradient-based pipelines. We develop a top-down matrix assembly algorithm within Projective Dynamics and derive a generalized dry friction model for soft continuum using a new matrix splitting strategy. We derive a differentiable control framework for soft articulated bodies driven by muscles, joint torques, or pneumatic tubes. The experiments demonstrate that our designs make soft body simulation more stable and realistic compared to other frameworks. Our method accelerates the solution of system identification problems by more than an order of magnitude, and enables efficient gradient-based learning of motion control with soft robots.

We introduce a simple yet effective framework for improving the robustness of learning algorithms against image corruptions for autonomous driving. These corruptions can occur due to both internal (e.g., sensor noises and hardware abnormalities) and external factors (e.g., lighting, weather, visibility, and other environmental effects). Using sensitivity analysis with FID-based parameterization, we propose a novel algorithm exploiting basis perturbations to improve the overall performance of autonomous steering and other image processing tasks, such as classification and detection, for self-driving cars. Our model not only improves the performance on the original dataset, but also achieves significant performance improvement on datasets with multiple and unseen perturbations, up to 87% and 77%, respectively. A comparison between our approach and other SOTA techniques confirms the effectiveness of our technique in improving the robustness of neural network training for learning-based steering and other image processing tasks.

Digital try-on systems for e-commerce have the potential to change people’s lives and provide notable economic benefits. However, their development is limited by practical constraints, such as accurate sizing of the body and realism of demonstrations. We enumerate three open challenges remaining for a complete and easy-to-use try-on system that recent advances in machine learning make increasingly tractable. For each, we describe the problem, introduce state-of-the-art approaches, and provide future directions.

Differentiable physics is a powerful approach to learning and control problems that involve physical objects and environments. While notable progress has been made, the capabilities of differentiable physics solvers remain limited. We develop a scalable framework for differentiable physics that can support a large number of objects and their interactions. To accommodate objects with arbitrary geometry and topology, we adopt meshes as our representation and leverage the sparsity of contacts for scalable differentiable collision handling. Collisions are resolved in localized regions to minimize the number of optimization variables even when the number of simulated objects is high. We further accelerate implicit differentiation of optimization with nonlinear constraints. Experiments demonstrate that the presented framework requires up to two orders of magnitude less memory and computation in comparison to recent particle-based methods. We further validate the approach on inverse problems and control scenarios, where it outperforms derivative-free and model-free baselines by at least an order of magnitude.

Existing state-of-the-art object tracking can run into challenges when objects collide, occlude, or come close to one another. These visually based trackers may also fail to differentiate between objects with the same appearance but different materials. Existing methods may stop tracking or incorrectly start tracking another object. These failures are uneasy for trackers to recover from since they often use results from previous frames. By using audio of the impact sounds from object collisions, rolling, etc., our audio-visual object tracking (AVOT) neural network can reduce tracking error and drift. We train AVOT end to end and use audio-visual inputs over all frames. Our audio-based technique may be used in conjunction with other neural networks to augment visually based object detection and tracking methods. We evaluate its runtime frames-per-second (FPS) performance and intersection over union (IoU) performance against OpenCV object tracking implementations and a deep learning method. Our experiments, using the synthetic Sound-20K audio-visual dataset, demonstrate that AVOT outperforms single-modality deep learning methods, when there is audio from object collisions. A proposed scheduler network to switch between AVOT and other methods based on audio onset maximizes accuracy and performance over all frames in multimodal object tracking.

Simulation data can be utilized to extend real-world driving data in order to cover edge cases, such as vehicle accidents. The importance of handling edge cases can be observed in the high societal costs in handling car accidents, as well as potential dangers to human drivers. In order to cover a wide and diverse range of all edge cases, we systemically parameterize and simulate the most common accident scenarios. By applying this data to autonomous driving models, we show that transfer learning on simulated data sets provide better generalization and collision avoidance, as compared to random initialization methods. Our results illustrate that information from a model trained on simulated data can be inferred to a model trained on real-world data, indicating the potential influence of simulation data in real world models and advancements in handling of anomalous driving scenarios.

Abstract Virtualized traffic via various simulation models and real‐world traffic data are promising approaches to reconstruct detailed traffic flows. A variety of applications can benefit from the virtual traffic, including, but not limited to, video games, virtual reality, traffic engineering and autonomous driving. In this survey, we provide a comprehensive review on the state‐of‐the‐art techniques for traffic simulation and animation. We start with a discussion on three classes of traffic simulation models applied at different levels of detail. Then, we introduce various data‐driven animation techniques, including existing data collection methods, and the validation and evaluation of simulated traffic flows. Next, we discuss how traffic simulations can benefit the training and testing of autonomous vehicles. Finally, we discuss the current states of traffic simulation and animation and suggest future research directions.

We propose a scalable neural network framework to reconstruct the 3D mesh of a human body from multi-view images, in the subspace of the SMPL model. Use of multi-view images can significantly reduce the projection ambiguity of the problem, increasing the reconstruction accuracy of the 3D human body under clothing. Our experiments show that this method benefits from the synthetic dataset generated from our pipeline since it has good flexibility of variable control and can provide ground-truth for validation. Our method outperforms existing methods on real-world images, especially on shape estimations.

Autonomous driving has gained significant advancements in recent years. However, obtaining a robust control policy for driving remains challenging as it requires training data from a variety of scenarios, including rare situations (e.g., accidents), an effective policy architecture, and an efficient learning mechanism. We propose ADAPS for producing robust control policies for autonomous vehicles. ADAPS consists of two simulation platforms in generating and analyzing accidents to automatically produce labeled training data, and a memoryenabled hierarchical control policy. Additionally, ADAPS offers a more efficient online learning mechanism that reduces the number of iterations required in learning compared to existing methods such as DAGGER [1]. We present both theoretical and experimental results. The latter are produced in simulated environments, where qualitative and quantitative results are generated to demonstrate the benefits of ADAPS.

Existing work to estimate the weight of a liquid poured into a target container often require predefined source weights or visual data. We present novel audio-based and audio-augmented techniques, in the form of multimodal convolutional neural networks (CNNs), to estimate poured weight, perform overflow detection, and classify liquid and target container. Our audio-based neural network uses the sound from a pouring sequence-a liquid being poured into a target container. Audio inputs consist of converting raw audio into mel-scaled spectrograms. Our audio-augmented network fuses this audio with its corresponding visual data based on video images. Only a microphone and camera are required, which can be found in any modern smartphone or Microsoft Kinect. Our approach improves classification accuracy for different environments, containers, and contents of the robot pouring task. Our Pouring Sequence Neural Networks (PSNN) are trained and tested using the Rethink Robotics Baxter Research Robot. To the best of our knowledge, this is the first use of audio-visual neural networks to analyze liquid pouring sequences by classifying their weight, liquid, and receiving container.

We propose a differentiable cloth simulator that can be embedded as a layer in deep neural networks. This approach provides an effective, robust framework for modeling cloth dynamics, self-collisions, and contacts. Due to the high dimensionality of the dynamical system in modeling cloth, traditional gradient computation for collision response can become impractical. To address this problem, we propose to compute the gradient directly using QR decomposition of a much smaller matrix. Experimental results indicate that our method can speed up backpropagation by two orders of magnitude. We demonstrate the presented approach on a number of inverse problems, including parameter estimation and motion control for cloth.

Many virtual locomotion interfaces allowing users to move in virtual reality have been built and evaluated, such as redirected walking (RDW), walking-in-place (WIP), and joystick input. RDW has been shown to be among the most natural and immersive as it supports real walking, and many newer methods further adapt RDW to allow for customization and greater immersion. Most of these methods have been demonstrated to work with vision, in this paper we evaluate the ability for a general distractor-based RDW framework to be used with only auditory display. We conducted two studies evaluating the differences between RDW with auditory distractors and other distractor modalities using distraction ratio, virtual and physical path information, immersion, simulator sickness, and other measurements. Our results indicate that auditory RDW has the potential to be used with complex navigational tasks, such as crossing streets and avoiding obstacles. It can be used without designing the system specifically for audio-only users. Additionally, sense of presence and simulator sickness remain reasonable across all user groups.

Abstract Inspired by skeletal animation, a novel rigging‐skinning flow control scheme is proposed to animate fluids intuitively and efficiently. The new animation pipeline creates fluid animation via two steps: fluid rigging and fluid skinning. The fluid rig is defined by a point cloud with rigid‐body movement and incompressible deformation, whose time series can be intuitively specified by a rigid body motion and a constrained free‐form deformation, respectively. The fluid skin generates plausible fluid flows by virtually fluidizing the point‐cloud fluid rig with adjustable zero‐ and first‐order flow features and at fixed computational cost. Fluid rigging allows the animator to conveniently specify the desired low‐frequency flow motion through intuitive manipulations of a point cloud, while fluid skinning truthfully and efficiently converts the motion specified on the fluid rig into plausible flows of the animation fluid, with adjustable fine‐scale effects. Besides being intuitive, the rigging‐skinning scheme for fluid animation is robust and highly efficient, avoiding completely iterative trials or time‐consuming nonlinear optimization. It is also versatile, supporting both particle‐ and grid‐ based fluid solvers. A series of examples including liquid, gas and mixed scenes are presented to demonstrate the performance of the new animation pipeline.

Abstract We present a grid‐based fluid solver for simulating viscous materials and their interactions with solid objects. Our method formulates the implicit viscosity integration as a minimization problem with consistently estimated volume fractions to account for the sub‐grid details of free surfaces and solid boundaries. To handle the interplay between fluids and solid objects with viscosity forces, we also formulate the two‐way fluid‐solid coupling as a unified minimization problem based on the variational principle, which naturally enforces the boundary conditions. Our formulation leads to a symmetric positive definite linear system with a sparse matrix regardless of the monolithically coupled solid objects. Additionally, we present a position‐correction method using density constraints to enforce the uniform distributions of fluid particles and thus prevent the loss of fluid volumes. We demonstrate the effectiveness of our method in a wide range of viscous fluid scenarios.

In physically-based simulation, it is essential to choose appropriate material parameters to generate desirable simulation results. In many cases, however, choosing appropriate material parameters is very challenging, and often tedious trial-and-error parameter tuning steps are inevitable. In this paper, we propose a real-to-virtual parameter transfer framework that identifies material parameters of viscous fluids with example video data captured from real-world phenomena. Our method first extracts positional data of fluids and then uses the extracted data as a reference to identify the viscosity parameters, combining forward viscous fluid simulations and parameter optimization in an iterative process. We evaluate our method with a range of synthetic and real-world example data, and demonstrate that our method can identify the hidden physical variables and viscosity parameters. This set of recovered physical variables and parameters can then be effectively used in novel scenarios to generate viscous fluid behaviors visually consistent with the example videos.

Modal sound synthesis has been used to create realistic sounds from rigid-body objects, but requires accurate real-world material parameters. These material parameters can be estimated from recorded sounds of an impacted object, but external factors can interfere with accurate parameter estimation. We present a novel technique for estimating the damping parameters of materials from recorded impact sounds that probabilistically models these external factors. We represent the combined effects of material damping, support damping, and sampling inaccuracies with a probabilistic generative model, then use maximum likelihood estimation to fit a damping model to recorded data. This technique greatly reduces the human effort needed and does not require the precise object geometry or the exact hit location. We validate the effectiveness of this technique with a comprehensive analysis of a synthetic dataset and a perceptual study on object identification. We also present a study establishing human performance on the same parameter estimation task for comparison.

Abstract Cloth simulations, widely used in computer animation and apparel design, can be computationally expensive for real‐time applications. Some parallelization techniques have been proposed for visual simulation of cloth using CPU or GPU clusters and often rely on parallelization using spatial domain decomposition techniques that have a large communication overhead. In this paper, we propose a novel time‐domain parallelization technique that makes use of the two‐level mesh representation to resolve the time‐dependency issue and develop a practical algorithm to smooth the state transition from the corresponding coarse to fine meshes. A load estimation and a load balancing technique used in online partitioning are also proposed to maximize the performance acceleration. Our method achieves a nearly linear performance scaling on manycore clusters and outperforms spatial‐domain parallelization on a diverse set of benchmarks.

Abstract Real world dendritic growths show charming structures by their exquisite balance between the symmetry and randomness in the crystal formation. Other than the variety in the natural crystals, richer visual appearance of crystals can benefit from artificially controlling of the crystal growth on its growing directions and shapes. In this paper, by introducing one extra dimension of freedom, i.e. the orientation field, into the simulation, we propose an efficient algorithm for dendritic crystal simulation that is able to reproduce arbitrary symmetry patterns with different levels of asymmetry breaking effect on general grids or meshes, including spreading on curved surfaces and growth in 3D. Flexible artistic control is also enabled in a unified manner by exploiting and guiding the orientation field in the visual simulation. We show the effectiveness of our approach by various demonstrations of simulation results.

Abstract We propose a hybrid smoothed particle hydrodynamics solver for efficientlysimulating incompressible fluids using an interface handling method for boundary conditions in the pressure Poisson equation. We blend particle density computed with one smooth and one spiky kernel to improve the robustness against both fluid–fluid and fluid–solid collisions. To further improve the robustness and efficiency, we present a new interface handling method consisting of two components: free surface handling for Dirichlet boundary conditions and solid boundary handling for Neumann boundary conditions. Our free surface handling appropriately determines particles for Dirichlet boundary conditions using Jacobi‐based pressure prediction while our solid boundary handling introduces a new term to ensure the solvability of the linear system. We demonstrate that our method outperforms the state‐of‐the‐art particle‐based fluid solvers.

Most recent garment capturing techniques rely on acquiring multiple views of clothing, which may not always be readily available, especially in the case of pre-existing photographs from the web. As an alternative, we propose a method that is able to compute a 3D model of a human body and its outfit from a single photograph with little human interaction. Our algorithm is not only able to capture the global shape and overall geometry of the clothing, it can also extract the physical properties (i.e., material parameters needed for simulation) of cloth. Unlike previous methods using full 3D information (i.e., depth, multi-view images, or sampled 3D geometry), our approach achieves garment recovery from a single-view image by using physical, statistical, and geometric priors and a combination of parameter estimation, semantic parsing, shape/pose recovery, and physics-based cloth simulation. We demonstrate the effectiveness of our algorithm by re-purposing the reconstructed garments for virtual try-on and garment transfer applications and for cloth animation on digital characters.

Image and video understanding enables better reconstruction of the physical world. Existing methods focus largely on geometry and visual appearance of the reconstructed scene. In this paper, we extend the frontier in image understanding and present a method to recover the material properties of cloth from a video. Previous cloth material recovery methods often require markers or complex experimental set-up to acquire physical properties, or are limited to certain types of images or videos. Our approach takes advantages of the appearance changes of the moving cloth to infer its physical properties. To extract information about the cloth, our method characterizes both the motion and the visual appearance of the cloth geometry. We apply the Convolutional Neural Network (CNN) and the Long Short Term Memory (LSTM) neural network to material recovery of cloth from videos. We also exploit simulated data to help statistical learning of mapping between the visual appearance and material type of the cloth. The effectiveness of our method is demonstrated via validation using both the simulated datasets and the real-life recorded videos.

Rapid urbanization and increasing traffic have caused severe social, economic, and environmental problems in metropolitan areas worldwide. Traffic reconstruction and visualization using existing traffic data can provide novel tools for vehicle navigation and routing, congestion analysis, and traffic management. While traditional data collection methods are becoming increasingly common (e.g. using in-road sensors), GPS devices are also becoming ubiquitous. In this paper, we address the problem of traffic reconstruction, visualization, and animation using mobile vehicle data (i.e. GPS traces). We first conduct city-scale traffic reconstruction using statistical learning on mobile vehicle data for traffic animation and visualization, and then dynamically complete missing data using metamodel-based simulation optimization in areas of insufficient data coverage. We evaluate our approach quantitatively and qualitatively, and demonstrate our results with 2D visualization of citywide traffic, as well as 2D and 3D animation of reconstructed traffic in virtual environments.

We introduce a unified particle framework which integrates the phase-field method with multi-material simulation to allow modeling of both liquids and solids, as well as phase transitions between them. A simple elasto-plastic model is used to capture the behavior of various kinds of solids, including deformable bodies, granular materials, and cohesive soils. States of matter or phases , particularly liquids and solids, are modeled using the non-conservative Allen-Cahn equation. In contrast, materials---made of different substances---are advected by the conservative Cahn-Hilliard equation. The distributions of phases and materials are represented by a phase variable and a concentration variable, respectively, allowing us to represent commonly observed fluid-solid interactions. Our multi-phase, multi-material system is governed by a unified Helmholtz free energy density. This framework provides the first method in computer graphics capable of modeling a continuous interface between phases. It is versatile and can be readily used in many scenarios that are challenging to simulate. Examples are provided to demonstrate the capabilities and effectiveness of this approach.

The papers in this special section were presented at the 2015 ACM Symposium on Virtual Reality Software and Technology (VRST’15).

In this paper, we present a novel pairwise-force smoothed particle hydrodynamics (PF-SPH) model to enable simulation of various interactions at interfaces in real time. Realistic capture of interactions at interfaces is a challenging problem for SPH-based simulations, especially for scenarios involving multiple interactions at different interfaces. Our PF-SPH model can readily handle multiple types of interactions simultaneously in a single simulation; its basis is to use a larger support radius than that used in standard SPH. We adopt a novel anisotropic filtering term to further improve the performance of interaction forces. The proposed model is stable; furthermore, it avoids the particle clustering problem which commonly occurs at the free surface. We show how our model can be used to capture various interactions. We also consider the close connection between droplets and bubbles, and show how to animate bubbles rising in liquid as well as bubbles in air. Our method is versatile, physically plausible and easy-to-implement. Examples are provided to demonstrate the capabilities and effectiveness of our approach.

No abstract available.

Material property has great importance in medical robotics. The mechanical properties of the human soft tissue, are important to characterize the tissue deformation of each patient. The (recovered) elasticity parameters can assist surgeons to perform better pre-op surgical planning and enable medical robots to carry out personalized surgical procedures. In this paper, we present a novel algorithm on mechanical-property estimation from a temporal sequence of deformation samples. It does not require an external force-application measurement device or landmark-based displacement tracking. We test our approach on the reconstruction the Young's modulus of a human heart and further validate the results derived from videos using known parameters of tennis and foam balls.

We present a modal sound synthesis technique using a generalized proportional damping (GPD) model capable of capturing nonlinear frequency-dependent damping functions. We extend a prior method for automatic extraction of audio material parameters directly from recorded audio clips to determine material parameters for alternative damping models. We demonstrate the results with example-guided synthesized sounds, accompanied by a preliminary, perceptual study comparing the audio quality of the commonly used, linear Rayleigh damping model against a collection of alternative models.

Summary form only given. Extending the frontier of visual computing, an interactive, multimodal VR environment utilizes audio and touch-enabled interfaces to communicate information to a user and augment the graphical rendering. By harnessing other sensory channels, an immersive multimodal display can further enhance a user's experience in a virtual world. In addition to immersive environments, multimodal display can provide a natural and intuitive human-computer interface for many desktop applications such as computer games, online virtual worlds, visualization, simulation, and training. Compared to visual and haptic rendering, sound rendering has extremely demanding computing requirements, making the problem of auditory display highly challenging. In this talk, I will give an overview of our recent work on interactive auditory display consisting of sound synthesis and sound propagation. These include generating realistic physically-based sounds from perceptually-guided principles and dynamic simulation. I will also describe novel algorithms for immersive sound effects based on improved numerical techniques and fast geometric sound propagation. Finally, I present new techniques on cross-modal interaction for VR. These systems improve the state of the art in sound rendering by at least one to two orders of magnitude and will be demonstrated in complex, dynamic virtual environments and VR applications. I conclude by discussing possible future research directions on multimodal interaction with VR systems.

Abstract We propose a geometric multilevel solver for efficiently solving linear systems arising from particle‐based methods. To apply this method to particle systems, we construct the hierarchy, establish the correspondence between solutions at the particle and grid levels, and coarsen simulation elements taking boundary conditions into account. In addition, we propose a new solid boundary handling method to solve a pressure Poisson equation in a unified manner. We demonstrate that our method can handle general fluid simulation scenarios including two‐way fluid‐solid coupling, and the computational cost of this new solver scales nearly linearly with respect to the number of unknowns, unlike previous solvers for particle‐based methods.

As sound propagation algorithms become faster and more accurate, the question arises as to whether the additional efforts to improve fidelity actually offer perceptual benefits over existing techniques. Could environmental sound effects go the way of music, where lower-fidelity compressed versions are actually favored by listeners? Here we address this issue with two acoustic phenomena that are known to have perceptual effects on humans and that, accordingly, might be expected to heighten their experience with simulated environments. We present two studies comparing listeners’ perceptual response to both accurate and approximate algorithms simulating two key acoustic effects: diffraction and reverberation. For each effect, we evaluate whether increased numerical accuracy of a propagation algorithm translates into increased perceptual differentiation in interactive virtual environments. Our results suggest that auditory perception does benefit from the increased accuracy, with subjects showing better perceptual differentiation when experiencing the more accurate rendering method: the diffraction experiment shows a more linearly decaying sound field (with respect to the diffraction angle) for the accurate diffraction method, whereas the reverberation experiment shows that more accurate reverberation, after modest user experience, results in near-logarithmic response to increasing room volume.

Microscopic crowd simulators rely on models of local interaction (e.g. collision avoidance) to synthesize the individual motion of each virtual agent. The quality of the resulting motions heavily depends on this component, which has significantly improved in the past few years. Recent advances have been in particular due to the introduction of a short-horizon motion prediction strategy that enables anticipated motion adaptation during local interactions among agents. However, the simplicity of prediction techniques of existing models somewhat limits their domain of validity. In this paper, our key objective is to significantly improve the quality of simulations by expanding the applicable range of motion predictions. To this end, we present a novel local interaction algorithm with a new context-aware, probabilistic motion prediction model. By context-aware, we mean that this approach allows crowd simulators to account for many factors, such as the influence of environment layouts or in-progress interactions among agents, and has the ability to simultaneously maintain several possible alternate scenarios for future motions and to cope with uncertainties on sensing and other agent's motions. Technically, this model introduces "collision probability fields" between agents, efficiently computed through the cumulative application of Warp Operators on a source Intrinsic Field. We demonstrate how this model significantly improves the quality of simulated motions in challenging scenarios, such as dense crowds and complex environments.

Recent research in sound simulation has focused on either sound synthesis or sound propagation, and many standalone algorithms have been developed for each domain. We present a novel technique for coupling sound synthesis with sound propagation to automatically generate realistic aural content for virtual environments. Our approach can generate sounds from rigid-bodies based on the vibration modes and radiation coefficients represented by the single-point multipole expansion. We present a mode-adaptive propagation algorithm that uses a perceptual Hankel function approximation technique to achieve interactive runtime performance. The overall approach allows for high degrees of dynamism - it can support dynamic sources, dynamic listeners, and dynamic directivity simultaneously. We have integrated our system with the Unity game engine and demonstrate the effectiveness of this fully-automatic technique for audio content creation in complex indoor and outdoor scenes. We conducted a preliminary, online user-study to evaluate whether our Hankel function approximation causes any perceptible loss of audio quality. The results indicate that the subjects were unable to distinguish between the audio rendered using the approximate function and audio rendered using the full Hankel function in the Cathedral, Tuscany, and the Game benchmarks.

We present a practical approach for automatically estimating the material properties of soft bodies from two sets of images, taken before and after deformation. We reconstruct 3D geometry from the given sets of multiple-view images; we use a coupled simulation-optimization-identification framework to deform one soft body at its original, non-deformed state to match the deformed geometry of the same object in its deformed state. For shape correspondence, we use a distance-based error metric to compare the estimated deformation fields against the actual deformation field from the reconstructed geometry. The optimal set of material parameters is thereby determined by minimizing the error metric function. This method can simultaneously recover the elasticity parameters of multiple types of soft bodies using Finite Element Method-based simulation (of either linear or nonlinear materials undergoing large deformation) and particle-swarm optimization methods. We demonstrate this approach on real-time interaction with virtual organs in patient-specific surgical simulation, using parameters acquired from low-resolution medical images. We also highlight the results on physics-based animation of virtual objects using sketches from an artist's conception.

We present a multimodal virtual percussion instrument system on consumer mobile devices that allows users to design and configure customizable virtual percussion instruments and interact with them in real time. Users can create virtual instruments of different materials and shapes interactively, by editing and selecting the desired characteristics. Both the visual and auditory feedback are then computed on the fly to automatically correspond to the instrument properties and user interaction. We utilize efficient 3D input processing algorithms to approximate and represent real-time multi-touch input with key meta properties and adopt fast physical modeling to synthesize sounds. Despite the relatively limited computing resources on mobile devices, we are able to achieve rich and responsive multimodal feedback based on real-time user input. A pilot study is conducted to assess the effectiveness of the system.

Abstract Representing the majority of living animals, insects are the most ubiquitous biological organisms on Earth. Being able to simulate insect swarms could enhance visual realism of various graphical applications. However, the very complex nature of insect behaviors makes its simulation a challenging computational problem. To address this, we present a general biologically‐inspired framework for visual simulation of insect swarms. Our approach is inspired by the observation that insects exhibit emergent behaviors at various scales in nature. At the low level, our framework automatically selects and configures the most suitable steering algorithm for the local collision avoidance task. At the intermediate level, it processes insect trajectories into piecewise‐linear segments and constructs probability distribution functions for sampling waypoints. These waypoints are then evaluated by the Metropolis‐Hastings algorithm to preserve global structures of insect swarms at the high level. With this biologically inspired, data‐driven approach, we are able to simulate insect behaviors at different scales and we evaluate our simulation using both qualitative and quantitative metrics. Furthermore, as insect data could be difficult to acquire, our framework can be adopted as a computer‐assisted animation tool to interpret sketch‐like input as user control and generate simulations of complex insect swarming phenomena.

Abstract We propose a stable and efficient particle‐based method for simulating highly viscous fluids that can generate coiling and buckling phenomena and handle variable viscosity. In contrast to previous methods that use explicit integration, our method uses an implicit formulation to improve the robustness of viscosity integration, therefore enabling use of larger time steps and higher viscosities. We use Smoothed Particle Hydrodynamics to solve the full form of viscosity, constructing a sparse linear system with a symmetric positive definite matrix, while exploiting the variational principle that automatically enforces the boundary condition on free surfaces. We also propose a new method for extracting coefficients of the matrix contributed by second‐ring neighbor particles to efficiently solve the linear system using a conjugate gradient solver. Several examples demonstrate the robustness and efficiency of our implicit formulation over previous methods and illustrate the versatility of our method.

This article presents a novel and flexible bubble modelling technique for multi-fluid simulations using a volume fraction representation. By combining the volume fraction data obtained from a primary multi-fluid simulation with simple and efficient secondary bubble simulation, a range of real-world bubble phenomena are captured with a high degree of physical realism, including large bubble deformation, sub-cell bubble motion, bubble stacking over the liquid surface, bubble volume change, dissolving of bubbles, etc. Without any change in the primary multi-fluid simulator, our bubble modelling approach is applicable to any multi-fluid simulator based on the volume fraction representation.

Material property has great importance in deformable body simulation and medical robotics. The elasticity parameters, such as Young's modulus of the deformable bodies, are important to make realistic animations. Further in medical applications the (recovered) elasticity parameters can assist surgeons to perform better pre-op surgical planning and enable medical robots to carry out personalized surgical procedures. Previous elasticity parameters estimation methods are limited to recover one elasticity parameter of one deformable body at a time. In this paper, we propose a novel elasticity parameter estimation algorithm that can recover the elasticity parameters of multiple deformable bodies or multiple regions of one deformable body simultaneously from (at least two sets of) images. We validate our algorithm with both synthetic test cases and real patient CT images.

Multiple-fluid interaction is an interesting and common visual phenomenon we often observe. In this paper, we present an energy-based Lagrangian method that expands the capability of existing multiple-fluid methods to handle various phenomena, such as extraction, partial dissolution, etc. Based on our user-adjusted Helmholtz free energy functions, the simulated fluid evolves from high-energy states to low-energy states, allowing flexible capture of various mixing and unmixing processes. We also extend the original Cahn-Hilliard equation to be better able to simulate complex fluid-fluid interaction and rich visual phenomena such as motion-related mixing and position based pattern. Our approach is easily integrated with existing state-of-the-art smooth particle hydrodynamic (SPH) solvers and can be further implemented on top of the position based dynamics (PBD) method, improving the stability and incompressibility of the fluid during Lagrangian simulation under large time steps. Performance analysis shows that our method is at least 4 times faster than the state-of-the-art multiple-fluid method. Examples are provided to demonstrate the new capability and effectiveness of our approach.

Presents the EIC farewell message and the introduction of the new EIC.

We present an interactive wave-based sound propagation system that generates accurate, realistic sound in virtual environments for dynamic (moving) sources and listeners. We propose a novel algorithm to accurately solve the wave equation for dynamic sources and listeners using a combination of precomputation techniques and GPU-based runtime evaluation. Our system can handle large environments typically used in VR applications, compute spatial sound corresponding to listener's motion (including head tracking) and handle both omnidirectional and directional sources, all at interactive rates. As compared to prior wave-based techniques applied to large scenes with moving sources, we observe significant improvement in runtime memory. The overall sound-propagation and rendering system has been integrated with the Half-Life 2 game engine, Oculus-Rift head-mounted display, and the Xbox game controller to enable users to experience high-quality acoustic effects (e.g., amplification, diffraction low-passing, high-order scattering) and spatial audio, based on their interactions in the VR application. We provide the results of preliminary user evaluations, conducted to study the impact of wave-based acoustic effects and spatial audio on users' navigation performance in virtual environments.

We present an approach to "participatory route planning," a novel concept that takes advantage of mobile devices, such as cellular phones or embedded systems in cars, to form an interactive, participatory network of vehicles that plan their travel routes based on the current traffic conditions and existing routes planned by the network of participants, thereby making more informed travel decision for each participating user. The premise of this approach is that a route, or plan, for a vehicle is also a prediction of where the car will travel. If routes are created for a sizable percentage of the total vehicle population, an estimate for the overall traffic pattern is attainable. Taking planned routes into account as predictions allows the entire traffic route planning system to better distribute vehicles and minimize traffic congestion. We present an approach that is suitable for realistic, city-scale scenarios, a prototype system to demonstrate feasibility, and experiments using a state-of-the-art microscopic traffic simulator.

Understanding and modeling how a crowd behaves in a wide variety of situations is an important problem in many areas. For example, during the planning stages, city, traffic, and evacuation engineers use crowd behavior modeling to predict usage patterns and to do safety analysis of their designs. Several research areas benefit from realistic simulation of crowds such as augmented reality, animation, games, virtual therapy, and virtual training. Not only is a realistic rendering of a virtual environment required for these applications, but also a realistic simulation of virtual humans is essential to providing an immersive experience for the users.

Abstract We present a novel framework to evaluate multi‐agent crowd simulation algorithms based on real‐world observations of crowd movements. A key aspect of our approach is to enable fair comparisons by automatically estimating the parameters that enable the simulation algorithms to best fit the given data. We formulate parameter estimation as an optimization problem, and propose a general framework to solve the combinatorial optimization problem for all parameterized crowd simulation algorithms. Our framework supports a variety of metrics to compare reference data and simulation outputs. The reference data may correspond to recorded trajectories, macroscopic parameters, or artist‐driven sketches. We demonstrate the benefits of our framework for example‐based simulation, modeling of cultural variations, artist‐driven crowd animation, and relative comparison of some widely‐used multi‐agent simulation algorithms.

This article presents a versatile and robust SPH simulation approach for multiple-fluid flows. The spatial distribution of different phases or components is modeled using the volume fraction representation, the dynamics of multiple-fluid flows is captured by using an improved mixture model, and a stable and accurate SPH formulation is rigorously derived to resolve the complex transport and transformation processes encountered in multiple-fluid flows. The new approach can capture a wide range of real-world multiple-fluid phenomena, including mixing/unmixing of miscible and immiscible fluids, diffusion effect and chemical reaction, etc. Moreover, the new multiple-fluid SPH scheme can be readily integrated into existing state-of-the-art SPH simulators, and the multiple-fluid simulation is easy to set up. Various examples are presented to demonstrate the effectiveness of our approach.

Local collision avoidance algorithms in crowd simulation often ignore agents beyond a neighborhood of a certain size. This cutoff can result in sharp changes in trajectory when large groups of agents enter or exit these neighborhoods. In this work, we exploit the insight that exact collision avoidance is not necessary between agents at such large distances, and propose a novel algorithm for extending existing collision avoidance algorithms to perform approximate, long-range collision avoidance. Our formulation performs long-range collision avoidance for distant agent groups to efficiently compute trajectories that are smoother than those obtained with state-of-the-art techniques and at faster rates. Comparison to real-world data demonstrates that crowds simulated with our algorithm exhibit an improved speed sensitivity to density similar to human crowds. Another issue often sidestepped in existing work is that discrete and continuum collision avoidance algorithms have different regions of applicability. For example, low-density crowds cannot be modeled as a continuum, while high-density crowds can be expensive to model using discrete methods. We formulate a hybrid technique for crowd simulation which can accurately and efficiently simulate crowds at any density with seamless transitions between continuum and discrete representations. Our approach blends results from continuum and discrete algorithms, based on local density and velocity variance. In addition to being robust across a variety of group scenarios, it is also highly efficient, running at interactive rates for thousands of agents on portable systems.

IEEE Transactions on Visualization and Computer Graphics (TVCG) has published more papers in 2013 than in any previous year. TVCG continues to be in an excellent state. For the first time, the entire proceedings of IEEE VAST 2013 papers became part of the VIS special issue of TVCG. At the start of October 2013, TVCG had received more than 265 regular submissions, more than last year at the same time. This year we also observed a healthy number of 150 and 402 submissions to the IEEE VR Conference issue and the VIS conference issue that contains the Proceedings of the IEEE Information Visualization, Scientific Visualization, and Visual Analytics Science and Technology 2013 Conferences, respectively. We are expecting a total of nearly 900 submissions to TVCG by the end of 2013. A total of 137 articles were published in the first 10 regular issues with 1,769 printed pages, and the VR and VIS special issues containing 21 and 101 conference papers, respectively. All submissions in both special issues went through a rigorous two-round journalquality review process. Practically all the 2012 papers have also been decided. From the 293 regular submissions (including 20 extended versions of Best Papers from several top venues in graphics and visualization), 76 regular papers and all 20 special section papers were eventually accepted; 86 out of 333 SciVis plus InfoVis conference submissions were published in the VIS special issue. TVCG continues to offer authors a remarkably effi cient processing of submitted manuscripts: The average time from submission to fi rst decision is about three months and the average time from submission to publication as a preprint in the digital library is about seven months. Its 2012 impact factor is 1.895 with the largest number of total publications appeared two years prior. During 2013, the authors of TVCG regular papers were invited to give an oral presentation of their recent work at TVCG’s partner conferences. A total of 35 TVCG papers were presented at the IEEE Virtual Reality Conference, ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Pacifi c Graphics, and IEEE VIS 2013.

The IEEE Computer Society's policy limits the terms of the members of its Editorial Board. This policy allows new people and expertise to come in and benefits the growth and vitality of the journal. On behalf of the IEEE Computer Society and TVCG's Editorial Board, I would like to express our appreciation and gratitude to the retiring Associate Editors including Ronan Boulic, Wojciech Matusik, and Dieter Schmalstieg for their remarkable service, particularly Boulic and Schmalstieg have both been recognized for their distinguished performance as Best Associate Editors of 2011 and 2012, respectively. It is my pleasure to announce TVCG's new Associate Editors-in-Chief: Amitabh Varshney, who has served on the TVCG Editorial Board in the past and will return to help TVCG continue to thrive and establish its new Multimedia Center. I am also happy to introduce Baoquan Chen, Miguel Otaduy, and Xin Tong, who have recently joined TVCG as Associate Editors. Biographical sketches listing their accomplishments and areas of expertise are provided.

The success of a journal relies heavily on the quality of submissions and of their reviews. The latter is primarily the work and efforts of the associate editors and the anonymous reviewers. The dedication of associate editors and of external reviewers is essential to the continuing growth of the journal. To continue recognizing these "unsung heroes" who drive the scientific peer review process for IEEE Transactions on Visualization and Computer Graphics (TVCG), it is my pleasure to announce the 2013 Best Associate Editor Award and the 2013 Best Reviewer Award. Three associate editors (AEs) for are recognized their dedication and hard work in 2013: Shi-Min Hu, Alla Sheffer, and Shigeo Takahashi. They handled a large number of submissions efficiently with the quickest turnaround (averaging less than 50 days) and provided consistently high-quality, thoughtful AE summary to the authors. In recognizing their distinguished service to the IEEE TVCG, the 2013 TVCG Best Associate Editor Award goes to Shi-Min Hu, Alla Sheffer, and Shigeo Takahashi.

Local collision avoidance algorithms in crowd simulation often ignore agents beyond a neighborhood of a certain size. This cutoff can result in sharp changes in trajectory when large groups of agents enter or exit these neighborhoods. In this work, we exploit the insight that exact collision avoidance is not necessary between agents at such large distances, and propose a novel algorithm for extending existing collision avoidance algorithms to perform approximate, long-range collision avoidance. Our formulation performs long-range collision avoidance for distant agent groups to efficiently compute trajectories that are smoother than those obtained with state-of-the-art techniques and at faster rates.

“Haptic rendering” or “haptic display” can be broadly defined as conveying information about virtual objects or data to a user through the sense of touch. Among all applications of haptic rendering, force-feedback display of contact interactions with rigid and deformable virtual models through the sense of touch has matured considerably over the last decade. In this paper, we present a general framework for force-feedback display of rigid and virtual environments, and we outline its major building blocks. We focus on computational aspects, and we classify algorithms and representations successfully used in the three major subproblems of force-feedback display: collision detection, dynamics simulation, and constrained optimization. In addition, force-feedback display is an integral part of a multimodal experience, often involving both visual and auditory display; therefore, we also discuss the choice of algorithms and representations for force feedback as a part of multimodal display.

Linear modal synthesis methods have often been used to generate sounds for rigid bodies. One of the key challenges in widely adopting such techniques is the lack of automatic determination of satisfactory material parameters that recreate realistic audio quality of sounding materials. We introduce a novel method using prerecorded audio clips to estimate material parameters that capture the inherent quality of recorded sounding materials. Our method extracts perceptually salient features from audio examples. Based on psychoacoustic principles, we design a parameter estimation algorithm using an optimization framework and these salient features to guide the search of the best material parameters for modal synthesis. We also present a method that compensates for the differences between the real-world recording and sound synthesized using solely linear modal synthesis models to create the final synthesized audio. The resulting audio generated from this sound synthesis pipeline well preserves the same sense of material as a recorded audio example. Moreover, both the estimated material parameters and the residual compensation naturally transfer to virtual objects of different sizes and shapes, while the synthesized sounds vary accordingly. A perceptual study shows the results of this system compare well with real-world recordings in terms of material perception.

'Virtualized traffic' reconstructs and displays continuous traffic flows from discrete spatio-temporal traffic sensor data or procedurally generated control input to enhance a sense of immersion in a dynamic virtual environment. In this paper, we introduce a fast technique to reconstruct traffic flows from in-road sensor measurements or procedurally generated data for interactive 3D visual applications. Our algorithm estimates the full state of the traffic flow from sparse sensor measurements (or procedural input) using a statistical inference method and a continuum traffic model. This estimated state then drives an agent-based traffic simulator to produce a 3D animation of vehicle traffic that statistically matches the original traffic conditions. Unlike existing traffic simulation and animation techniques, our method produces a full 3D rendering of individual vehicles as part of continuous traffic flows given discrete spatio-temporal sensor measurements. Instead of using a color map to indicate traffic conditions, users could visualize and fly over the reconstructed traffic in real time over a large digital cityscape.

We present a novel hybrid approach that couples geometric and numerical acoustic techniques for interactive sound propagation in complex environments. Our formulation is based on a combination of spatial and frequency decomposition of the sound field. We use numerical wave-based techniques to precompute the pressure field in the near-object regions and geometric propagation techniques in the far-field regions to model sound propagation. We present a novel two-way pressure coupling technique at the interface of near-object and far-field regions. At runtime, the impulse response at the listener position is computed at interactive rates based on the stored pressure field and interpolation techniques. Our system is able to simulate high-fidelity acoustic effects such as diffraction, scattering, low-pass filtering behind obstruction, reverberation, and high-order reflections in large, complex indoor and outdoor environments and Half-Life 2 game engine. The pressure computation requires orders of magnitude lower memory than standard wave-based numerical techniques.

The journal continues to be in an excellent state. For the fi rst time, the entire proceedings of IEEE VR 2012 long papers became a special issue of TVCG (April 2012 issue). At the start of October 2012, TVCG had received more than 220 regular submissions, slightly fewer than last year at the same time, but more than years prior to 2011. This year, we also observed an excellent number of 95 and 437 submissions, respectively, to the IEEE VR Conference issue and the VisWeek Conference issue, which contains the Proceedings of the IEEE Visualization and Information Visualization 2011 Conferences, as well as the 10 best papers from the IEEE Conference on Visual Analytics Science and Technology (VAST). We are expecting a total of more than 800 submissions to TVCG by the end of 2012. A total of 145 articles were published in the fi rst 10 regular issues with 1,912 pages, and the VR and VisWeek special issues containing 15 and 96 conference papers, respectively. All submissions in both special issues went through a rigorous two-round journalquality review process. Practically all the 2011 papers have also been decided. From the 326 regular submissions (including 28 extended versions of Best Papers from several top venues in graphics and visualization), 70 regular papers and all 28 special section papers were eventually accepted; 93 out of 366 conference submissions were published in the VisWeek special issue. The acceptance rate is about 23 percent for the regular papers and 25 percent for the papers submitted to the VisWeek conference issue. TVCG continues to offer authors a remarkably effi cient processing of submitted manuscripts: The average time from submission to fi rst decision is less than three months and the average time from submission to publication as a preprint in the CSDL is less than seven months. With its 2011 impact factor of 2.22, TVCG remains clearly as the top journal in visualization and computer graphics overall. During 2012, the authors of TVCG regular papers were invited to give an oral presentation of their recent work at TVCG’s partner conferences. A total of 35 TVCG papers were presented at the IEEE Virtual Reality Conference, ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Pacifi c Graphics, and IEEE VisWeek 2012. Started in 2011, this new arrangement provides a unique opportunity for the audience of these conferences to keep abreast of high-quality research featured in TVCG, while encouraging more TVCG authors to attend these conferences. Both the TVCG authors and the conference attendees have been extremely positive about this new initiative and we plan to continue this conference-journal parternship in 2013.

THE IEEE Computer Society's policy limits the terms of the members of its Editorial Board. This allows new people and expertise to come in and benefi ts the growth and vitality of the journal. The success of the journal relies on the quality of the submissions and reviews, and the work of the associate editors. The dedication of associate editors is essential to the continuing growth of the journal. On behalf of the IEEE Computer Society and IEEE Transactions on Visualization and Computer Graphics (TVCG) Editorial Board, the Editor-in-Chief (EiC) would like to express our appreciation and gratitude to the retiring Associate Editors: Kavita Bala, Gerik Scheuermann, and Wenping Wang. It is the EiC's pleasure to introduce Doug Bowman and Alla Sheffer, who have recently joined the TVCG Editorial Board as Associate Editors. Biographical sketches listing their accomplishments and areas of expertise are provided. The TVCG Editorial Board is pleased to welcome these outstanding researchers to their new role.

The IEEE Computer Society's policy limits the terms of the members of its Editorial Board. This allows new people and expertise to come in and benefi ts the growth and vitality of the journal. The success of the journal relies on the quality of the submissions and reviews, and the work of the associate editors. The dedication of associate editors is essential to the continuing growth of the journal. On behalf of the IEEE TVCG's Editorial Board, it is the Editor-in-Chief's pleasure to introduce Gennady Andrienko and Steve Marschner, who have recently joined the TVCG Editorial Board as Associate Editors. Below are the biographical sketches listing their accomplishments and areas of expertise. The TVCG Editorial Board is pleased to welcome these outstanding researchers to their new role.

T HE success of a journal relies heavily on the quality of submissions and of their reviews.The latter is primarily the work and efforts of the associate editors and the anonymous reviewers.The dedication of associate editors and of external reviewers is essential to the continuing growth of the journal.To continue recognizing these "unsung heroes" who drive

The nonlinear and nonstationary nature of Navier-Stokes equations produces fluid flows that can be noticeably different in appearance with subtle changes. In this paper, we introduce a method that can analyze the intrinsic multiscale features of flow fields from a decomposition point of view, by using the Hilbert-Huang transform method on 3D fluid simulation. We show how this method can provide insights to flow styles and help modulate the fluid simulation with its internal physical information. We provide easy-to-implement algorithms that can be integrated with standard grid-based fluid simulation methods and demonstrate how this approach can modulate the flow field and guide the simulation with different flow styles. The modulation is straightforward and relates directly to the flow's visual effect, with moderate computational overhead.

Accurately modeling the intrinsic material-dependent damping property for interactive sound rendering is a challenging problem. The Rayleigh damping model is commonly regarded as an adequate engineering model for interactive sound synthesis in virtual environment applications, but this assumption has never been rigorously analyzed. In this paper, we conduct a formal evaluation of this model. Our goal is to determine if auditory perception of material under Rayleigh damping assumption is 'geometry-invariant', i.e. if this approximation model is transferable across different shapes and sizes. First, audio recordings of same-material objects in various shapes and sizes are analyzed to determine if they can be approximated by the Rayleigh damping model with a single set of parameters. Next, we design and conduct a series of psychoacoustic experiments, in subjects evaluate if audio clips synthesized using the Rayleigh damping model are from the same material, when we alter the material, shape, and size parameters. Through both quantitative and qualitative evaluation, we show that the acoustic properties of the Rayleigh damping model for a single material is generally preserved across different geometries of objects consisting of homogeneous materials and is therefore a suitable, geometry-invariant sound model. Our study results also show that consistent with prior crossmodal expectations, visual perception of geometry can affect the auditory perception of materials. These findings facilitate the wide adoption of Rayleigh damping for interactive auditory systems and enable reuse of material parameters under this approximation model across different shapes and sizes, without laborious per-object parameter tuning.

We propose a new technique to simulate dynamic patterns of crowd behaviors using stress modeling. Our model accounts for permanent, stable disposition and the dynamic nature of human behaviors that change in response to the situation. The resulting approach accounts for changes in behavior in response to external stressors based on well-known theories in psychology. We combine this model with recent techniques on personality modeling for multi-agent simulations to capture a wide variety of behavioral changes and stressors. The overall formulation allows different stressors, expressed as functions of space and time, including time pressure, positional stressors, area stressors and inter-personal stressors. This model can be used to simulate dynamic crowd behaviors at interactive rates, including walking at variable speeds, breaking lane-formation over time, and cutting through a normal flow. We also perform qualitative and quantitative comparisons between our simulation results and real-world observations.

We present an interactive virtual percussion instrument system, Tabletop Ensemble, that can be used by a group of collaborative users simultaneously to emulate playing music in real world while providing them with flexibility of virtual simulations. An optical multi-touch tabletop serves as the input device. A novel touch handling algorithm for such devices is presented to translate users' interactions into percussive control signals appropriate for music playing. These signals activate the proposed sound simulation system for generating realistic user-controlled musical sounds. A fast physically-based sound synthesis technique, modal synthesis, is adopted to enable users to directly produce rich, varying musical tones, as they would with the real percussion instruments. In addition, we propose a simple coupling scheme for modulating the synthesized sounds by an accurate numerical acoustic simulator to create believable acoustic effects due to cavity in music instruments. This paradigm allows creating new virtual percussion instruments of various materials, shapes, and sizes with little overhead. We believe such an interactive, multi-modal system would offer capabilities for expressive music playing, rapid prototyping of virtual instruments, and active exploration of sound effects determined by various physical parameters in a classroom, museum, or other educational settings. Virtual xylophones and drums with various physics properties are shown in the presented system.

Estimation of tissue stiffness is an important means of noninvasive cancer detection. Existing elasticity reconstruction methods usually depend on a dense displacement field (inferred from ultrasound orMR images) and known external forces.Many imaging modalities, however, cannot provide details within an organ and therefore cannot provide such a displacement field. Furthermore, force exertion and measurement can be difficult for some internal organs, making boundary forces another missing parameter. We propose a general method for estimating elasticity and boundary forces automatically using an iterative optimization framework, given the desired (target) output surface. During the optimization, the input model is deformed by the simulator, and an objective function based on the distance between the deformed surface and the target surface is minimized numerically. The optimization framework does not depend on a particular simulation method and is therefore suitable for different physical models. We show a positive correlation between clinical prostate cancer stage (a clinical measure of severity) and the recovered elasticity of the organ. Since the surface correspondence is established, our method also provides a non-rigid image registration, where the quality of the deformation fields is guaranteed, as they are computed using a physics-based simulation.

Simulating fluids in large-scale scenes with appreciable quality using state-of-the-art methods can lead to high memory and compute requirements. Since memory requirements are proportional to the product of domain dimensions, simulation performance is limited by memory access, as solvers for elliptic problems are not compute-bound on modern systems. This is a significant concern for large-scale scenes. To reduce the memory footprint and memory/compute ratio, vortex singularity bases can be used. Though they form a compact bases for incompressible vector fields, robust and efficient modeling of nonrigid obstacles and free-surfaces can be challenging with these methods. We propose a hybrid domain decomposition approach that couples Eulerian velocity-based simulations with vortex singularity simulations. Our formulation reduces memory footprint by using smaller Eulerian domains with compact vortex bases, thereby improving the memory/compute ratio, and simulation performance by more than 1000x for single phase flows as well as significant improvements for free-surface scenes. Coupling these two heterogeneous methods also affords flexibility in using the most appropriate method for modeling different scene features, as well as allowing robust interaction of vortex methods with free-surfaces and nonrigid obstacles.

We present an information-theoretic method to measure the similarity between a given set of observed, real-world data and visual simulation technique for aggregate crowd motions of a complex system consisting of many individual agents. This metric uses a two-step process to quantify a simulator's ability to reproduce the collective behaviors of the whole system, as observed in the recorded real-world data. First, Bayesian inference is used to estimate the simulation states which best correspond to the observed data, then a maximum likelihood estimator is used to approximate the prediction errors. This process is iterated using the EM-algorithm to produce a robust, statistical estimate of the magnitude of the prediction error as measured by its entropy (smaller is better). This metric serves as a simulator-to-data similarity measurement. We evaluated the metric in terms of robustness to sensor noise, consistency across different datasets and simulation methods, and correlation to perceptual metrics.

This paper presents algorithms for optimal grasping forces. The previous work reveals that contact forces with minimal sum or maximum of normal force components can be written as positive combinations of primitive contact forces, to which the corresponding primitive contact wrenches express the required resultant wrench as their positive combination with minimum coefficients in terms of theL1orL∞metric. On this basis, we first propose an algorithm to compute such a set of primitive contact forces and the minimum contact forces. Moreover, considering the uncertainty in the actual friction coefficient, we develop another algorithm to determine the minimum required friction coefficient and the corresponding minimum contact forces within a given limit on their magnitude so that such contact forces are more reliable in practice. As our algorithms do not rely on any general optimization technique, they are very efficient and easy to implement. These algorithms can also be used in grasp quality evaluation and optimal grasp planning.

There exists a vast amount of geographic information system (GIS) data that model road networks around the world as polylines with attributes. In this form, the data are insufficient for applications such as simulation and 3D visualization-tools which will grow in power and demand as sensor data become more pervasive and as governments try to optimize their existing physical infrastructure. In this paper, we propose an efficient method for enhancing a road map from a GIS database to create a geometrically and topologically consistent 3D model to be used in real-time traffic simulation, interactive visualization of virtual worlds, and autonomous vehicle navigation. The resulting representation provides important road features for traffic simulations, including ramps, highways, overpasses, legal merge zones, and intersections with arbitrary states, and it is independent of the simulation methodologies. We test the 3D models of road networks generated by our algorithm on real-time traffic simulation using both macroscopic and microscopic techniques.

One of the most ubiquitous AI applications is vehicle route planning. While state-of-the-art systems take into account current traffic conditions or historic traffic data, current planning approaches ignore the impact of their own plans on the future traffic conditions. We present a novel algorithm for self-aware route planning that uses the routes it plans for current vehicle traffic to more accurately predict future traffic conditions for subsequent cars. Our planner uses a roadmap with stochastic, time-varying traffic densities that are defined by a combination of historical data and the densities predicted by the planned routes for the cars ahead of the current traffic. We have applied our algorithm to large-scale traffic route planning, and demonstrated that our self-aware route planner can more accurately predict future traffic conditions, which results in a reduction of the travel time for those vehicles that use our algorithm.

Virtual coupling is commonly used to maintain stability of penalty-based haptic rendering. However, due to dozens of design parameters involved in the dynamics and force model, to increase transparency while maintaining stability using virtual coupling remains a challenge for 6-Degree-of-Freedom (DOF) haptic rendering. Using an equivalent-angle analysis, we transform 3-DOF rotation into 1-DOF rotation, thereby transforming the 6-DOF dynamics into six 1-DOF dynamics. For each 1-DOF dynamics, a damped vibration model is proposed to analyze the computation of the `graphic tool'. The equilibrium position/angle is defined to analyze the convergence of numerical integration. With this approach, we can improve the transparency of 6-DOF haptic rendering in both free space and constraint space by experimentally determining only two parameters: the integration time step and the number of integrations in each simulation loop. Using this method, we can improve the coupling stiffness to fully exploit the display capability of the haptic device and maintain the stability of the haptic rendering.

We present a novel, real-time algorithm for modeling large-scale, realistic traffic using a hybrid model of both continuum and agent-based methods for traffic simulation. We simulate individual vehicles in regions of interest using state-of-the-art agent-based models of driver behavior, and use a faster continuum model of traffic flow in the remainder of the road network. Our key contributions are efficient techniques for the dynamic coupling of discrete vehicle simulation with the aggregated behavior of continuum techniques for traffic simulation. We demonstrate the flexibility and scalability of our interactive visual simulation technique on extensive road networks using both real-world traffic data and synthetic scenarios. These techniques demonstrate the applicability of hybrid techniques to the efficient simulation of large-scale flows with complex dynamics.

We present a novel approach to direct and control virtual crowds using navigation fields. Our method guides one or more agents toward desired goals based on guidance fields. The system allows the user to specify these fields by either sketching paths directly in the scene via an intuitive authoring interface or by importing motion flow fields extracted from crowd video footage. We propose a novel formulation to blend input guidance fields to create singularity-free, goal-directed navigation fields. Our method can be easily combined with the most current local collision avoidance methods and we use two such methods as examples to highlight the potential of our approach. We illustrate its performance on several simulation scenarios.

We present a novel concept, Virtualized Traffic, to reconstruct and visualize continuous traffic flows from discrete spatiotemporal data provided by traffic sensors or generated artificially to enhance a sense of immersion in a dynamic virtual world. Given the positions of each car at two recorded locations on a highway and the corresponding time instances, our approach can reconstruct the traffic flows (i.e., the dynamic motions of multiple cars over time) between the two locations along the highway for immersive visualization of virtual cities or other environments. Our algorithm is applicable to high-density traffic on highways with an arbitrary number of lanes and takes into account the geometric, kinematic, and dynamic constraints on the cars. Our method reconstructs the car motion that automatically minimizes the number of lane changes, respects safety distance to other cars, and computes the acceleration necessary to obtain a smooth traffic flow subject to the given constraints. Furthermore, our framework can process a continuous stream of input data in real time, enabling the users to view virtualized traffic events in a virtual world as they occur. We demonstrate our reconstruction technique with both synthetic and real-world input.

We present an approach to reciprocal collision avoidance, where multiple mobile agents must avoid collisions with each other while moving in a common workspace. Each agent acts fully independently, and does not communicate with others. Yet our approach guarantees that all agents will be collision-free for at least a fixed amount of time. Our approach provides a sufficient condition for collision-free motion. Given the agent's objective, the optimal collision-free action can be computed very efficiently, as it is the solution to a two-dimensional linear program. We show our approach on dense and complex simulation scenarios involving thousands of agents at fast real-time running times.

We present an efficient algorithm for solving the ray-shooting problem on high dimensional sets. Our algorithm computes the intersection of the boundary of a compact convex set with a ray emanating from an interior point of the set and represents the intersection point as a convex combination of a set of affinely independent points. We use our intersection algorithm to compute two types of optimal grasping forces, where either the sum or the maximum of normal force components is minimized. In our simulation, the algorithm converges well and performs the computations in tens of milliseconds on a laptop.

We present a new method to generate biped walking patterns for biped robots on uneven terrains. Our formulation uses a universal stability criterion that checks whether the resultant of the gravity wrench and the inertia wrench of a robot lies in the convex cone of the wrenches resulting from contacts between the robot and the environment. We present an algorithm to compute the feasible acceleration of the robot's CoM (center of mass) and use that algorithm to generate biped walking patterns. Our approach is more general and applicable to uneven terrains as compared with prior methods based on the ZMP (zero-moment point) criterion. We highlight its applications on some benchmarks.

Crowds and groups are a vital element of life, and simulating them in a convincing manner is one of the great challenges in computer graphics and interactive techniques. This course focuses on the problem of efficiently simulating realistic crowd and group behavior for a range of applications, including games and design of spaces. It covers data driven methods, where the characteristics of crowds are simulated based on real world data; evaluation and perceptual issues, and creation of behavioral variety; interactive simulation and control of large scale crowds and traffic for games and other real time applications; and finally a case study of using crowd simulation for design of spaces in the Disney theme parks.

Designing a fixture layout of an object can be reduced to computing the largest simplex and the resulting simplex is classified using the radius of the largest inscribed ball centered at the origin. We present three different algorithms to compute such a simplex: a simple randomized algorithm, an interchange algorithm, and a branch-and-bound algorithm. We evaluate their complexity and also present methods to combine different algorithms to improve the performance and highlight their performance on complex 3D models consisting of thousands of triangles. Our randomized algorithm computes a feasible fixture layout in linear time and is well-suited for realtime applications. The interchange algorithm computes an optimal simplex in linear time such that no single vertex can be changed to enlarge the simplex. The branch-and-bound algorithm computes the largest simplex by using lower and upper bounds on the radius of the inscribed ball.

We present a new interaction handling model for physics-based sound synthesis in virtual environments. A new three-level surface representation for describing object shapes, visible surface bumpiness, and microscopic roughness (e.g. friction) is proposed to model surface contacts at varying resolutions for automatically simulating rich, complex contact sounds. This new model can capture various types of surface interaction, including sliding, rolling, and impact with a combination of three levels of spatial resolutions. We demonstrate our method by synthesizing complex, varying sounds in several interactive scenarios and a game-like virtual environment. The three-level interaction model for sound synthesis enhances the perceived coherence between audio and visual cues in virtual reality applications.

Abstract We present a novel method for the synthesis and animation of realistic traffic flows on large‐scale road networks. Our technique is based on a continuum model of traffic flow we extend to correctly handle lane changes and merges, as well as traffic behaviors due to changes in speed limit. We demonstrate how our method can be applied to the animation of many vehicles in a large‐scale traffic network at interactive rates and show that our method can simulate believable traffic flows on publicly‐available, real‐world road data. We furthermore demonstrate the scalability of this technique on many‐core systems.

Abstract We present a new algorithm to generate plausible motions for high‐DOF human‐like articulated figures in constrained environments with multiple obstacles. Our approach is general and makes no assumptions about the articulated model or the environment. The algorithm combines hierarchical model decomposition with sample‐based planning to efficiently compute a collision‐free path in tight spaces. Furthermore, we use path perturbation and replanning techniques to satisfy the kinematic and dynamic constraints on the motion. In order to generate realistic human‐like motion, we present a new motion blending algorithm that refines the path computed by the planner with motion capture data to compute a smooth and plausible trajectory. We demonstrate the results of generating motion corresponding to placing or lifting object, walking, and bending for a 38‐DOF articulated model. Copyright © 2010 John Wiley & Sons, Ltd.

We present a novel approach for synthesizing liquid sounds directly from visual simulation of fluid dynamics. Our approach takes advantage of the fact that the sound generated by liquid is mainly due to the vibration of resonating bubbles in the medium and performs automatic sound synthesis by coupling physically-based equations for bubble resonance with multiple fluid simulators. We effectively demonstrate our system on several benchmarks using a real-time shallow-water fluid simulator as well as a hybrid grid-SPH simulator.

We present a novel continuum-based model that enables efficient simulation of granular materials. Our approach fully solves the internal pressure and frictional stresses in a granular material, thereby allows visually noticeable behaviors of granular materials to be reproduced, including freely dispersing splashes without cohesion, and a global coupling between friction and pressure. The full treatment of internal forces in the material also enables two-way interaction with solid bodies. Our method achieves these results at only a very small fraction of computational costs of the comparable particle-based models for granular flows.

We present a method for real-time sound propagation that captures all wave effects, including diffraction and reverberation, for multiple moving sources and a moving listener in a complex, static 3D scene. It performs an offline numerical simulation over the scene and then applies a novel technique to extract and compactly encode the perceptually salient information in the resulting acoustic responses. Each response is automatically broken into two phases: early reflections (ER) and late reverberation (LR), via a threshold on the temporal density of arriving wavefronts. The LR is simulated and stored in the frequency domain, once per room in the scene. The ER accounts for more detailed spatial variation, by recording a set of peak delays/amplitudes in the time domain and a residual frequency response sampled in octave frequency bands, at each source/receiver point pair in a 5D grid. An efficient run-time uses this precomputed representation to perform binaural sound rendering based on frequency-domain convolution. Our system demonstrates realistic, wave-based acoustic effects in real time, including diffraction low-passing behind obstructions, sound focusing, hollow reverberation in empty rooms, sound diffusion in fully-furnished rooms, and realistic late reverberation.

Extending the frontier of visual computing, sound rendering utilizes auditory display to communicate information to a user and offers an alternative means of visualization. By harnessing the sense of hearing, sound rendering can further enhance a user's experience in a multimodal virtual world. In addition to immersive environments, auditory displays can provide a natural and intuitive human-computer interface for many desktop applications. In this paper, we give a brief overview of recent work at UNC Chapel Hill on fast algorithms for sound synthesis and sound propagation. These include physically-based sound synthesis for rigid bodies and liquid sound generation, as well as numeric and geometric algorithms for sound propagation. We highlight their performance on different benchmarks and briefly discuss some problems for future research.

We present a novel approach to compute collision-free paths for multiple robots subject to local coordination constraints. More specifically, given a set of robots, their initial and final configurations, and possibly some additional coordination constraints, our goal is to compute a collision-free path between the initial and final configuration that maintains the constraints. To solve this problem, our approach generalizes the social potential field method to be applicable to both convex and nonconvex polyhedra. Social potential fields are then integrated into a “physics-based motion planning” framework which uses constrained dynamics to solve the motion planning problem. Our approach is able to plan for over 200 robots while averaging about 110 ms per step in a variety of environments.

We present a method to control the behavior of elastic, deformable material in a dynamic simulation. We introduce dynamic morph targets, the equivalent in dynamic simulation to the geometric morph targets in (quasi-static) modeling. Dynamic morph targets define the pose-dependent physical state of soft objects, including surface deformation and elastic and inertial properties. Given these morph targets, our algorithm then derives a dynamic model that can be simulated in time-pose-space, interpolating the dynamic morph targets at the input poses. Our method easily integrates with current modeling and animation pipelines: at different poses, an artist simply provides a set of dynamic morph targets. Whether these input states are physically plausible is completely up to the artist. The resulting deformable models expose fully dynamic, pose-dependent behavior, driven by the artist-provided morph targets, complete with inertial effects.

We present a novel concept, Virtualized Traffic, to reconstruct and visualize continuous traffic flows from discrete spatio-temporal data provided by traffic sensors or generated artificially to enhance a sense of immersion in a dynamic virtual world. Given the positions of each car at two recorded locations on a highway and the corresponding time instances, our approach can reconstruct the traffic flows (i.e. the dynamic motions of multiple cars over time) in between the two locations along the highway for immersive visualization of virtual cities or other environments. Our algorithm is applicable to high-density traffic on highways with an arbitrary number of lanes and takes into account the geometric, kinematic, and dynamic constraints on the cars. Our method reconstructs the car motion that automatically minimizes the number of lane changes, respects safety distance to other cars, and computes the acceleration necessary to obtain a smooth traffic flow subject to the given constraints. Furthermore, our framework can process a continuous stream of input data in real time, enabling the users to view virtualized traffic events in a virtual world as they occur.

Large dense crowds show aggregate behavior with reduced individual freedom of movement. We present a novel, scalable approach for simulating such crowds, using a dual representation both as discrete agents and as a single continuous system. In the continuous setting, we introduce a novel variational constraint calledunilateral incompressibility, to model the large-scale behavior of the crowd, and accelerate inter-agent collision avoidance in dense scenarios. This approach makes it possible to simulate very large, dense crowds composed of up to a hundred thousand agents at near-interactive rates on desktop computers.

We present a novel algorithm for collision-free navigation of a large number of independent agents in complex and dynamic environments. We introduce adaptive roadmaps to perform global path planning for each agent simultaneously. Our algorithm takes into account dynamic obstacles and interagents interaction forces to continuously update the roadmap based on a physically-based dynamics simulator. In order to efficiently update the links, we perform adaptive particle-based sampling along the links. We also introduce the notion of 'link bands' to resolve collisions among multiple agents. In practice, our algorithm can perform real-time navigation of hundreds and thousands of human agents in indoor and outdoor scenes.

The three papers in this special section are expanded versions of the three best papers from the IEEE VR 2008 proceedings.

Accurate sound rendering can add significant realism to complement visual display in interactive applications, as well as facilitate acoustic predictions for many engineering applications, like accurate acoustic analysis for architectural design (Monks et al., 2000). Numerical simulation can provide this realism most naturally by modeling the underlying physics of wave propagation. However, wave simulation has traditionally posed a tough computational challenge. In this paper, we present a technique which relies on an adaptive rectangular decomposition of 3D scenes to enable efficient and accurate simulation of sound propagation in complex virtual environments. It exploits the known analytical solution of the wave equation in rectangular domains, and utilizes an efficient implementation of the discrete cosine transform on graphics processors (GPU) to achieve at least a 100-fold performance gain compared to a standard finite-difference time-domain (FDTD) implementation with comparable accuracy, while also being 10-fold more memory efficient. Consequently, we are able to perform accurate numerical acoustic simulation on large, complex scenes in the kilohertz range. To the best of our knowledge, it was not previously possible to perform such simulations on a desktop computer. Our work thus enables acoustic analysis on large scenes and auditory display for complex virtual environments on commodity hardware.

In this paper, we propose a new concept - the "Reciprocal Velocity Obstacle"- for real-time multi-agent navigation. We consider the case in which each agent navigates independently without explicit communication with other agents. Our formulation is an extension of the Velocity Obstacle concept [3], which was introduced for navigation among (passively) moving obstacles. Our approach takes into account the reactive behavior of the other agents by implicitly assuming that the other agents make a similar collision-avoidance reasoning. We show that this method guarantees safe and oscillation- free motions for each of the agents. We apply our concept to navigation of hundreds of agents in densely populated environments containing both static and moving obstacles, and we show that real-time and scalable performance is achieved in such challenging scenarios.

We present a novel approach for interactive navigation and planning of multiple agents in crowded scenes with moving obstacles. Our formulation uses a precomputed roadmap that provides macroscopic, global connectivity for wayfinding and combines it with fast and localized navigation for each agent. At runtime, each agent senses the environment independently and computes a collision-free path based on an extended "Velocity Obstacles" concept. Furthermore, our algorithm ensures that each agent exhibits no oscillatory behaviors. We have tested the performance of our algorithm in several challenging scenarios with a high density of virtual agents. In practice, the algorithm performance scales almost linearly with the number of agents and can run at interactive rates on multi-core processors.

We present an efficient technique to model sound propagation accurately in an arbitrary 3D scene by numerically integrating the wave equation. We show that by performing an offline modal analysis and using eigenvalues from a refined mesh, we can simulate sound propagation with reduced dispersion on a much coarser mesh, enabling accelerated computation. Since performing a modal analysis on the complete scene is usually not feasible, we present a domain decomposition approach to drastically shorten the pre-processing time. We introduce a simple, efficient and stable technique for handling the communication between the domain partitions. We validate the accuracy of our approach against cases with known analytical solutions. With our approach, we have observed up to an order of magnitude speedup compared to a standard finite-difference technique.

The realism of a computer simulated system for virtual environments often depends heavily on three main components: graphics, behavior, and sound. Thanks to four decades of research in modeling, rendering, and advances in VLSI technologies for graphics hardware, today's game systems are able to render near photorealistic images at interactive rates. To further increase the player's experience and immersion, the recent trend has been on introduction of physics-based simulation and behaviors. However, many computational challenges remain due to the simultaneous quest for sensory realism and performance requirements of these systems. Some of the key research issues include interactive motion synthesis of physically-plausible behavior of soft and articulated bodies, fast simulation of large-scale heterogeneous crowds, and real-time multi-sensory interaction. In this talk, I will present a few highlights of our recent efforts on addressing these problems. I will also demonstrate the results on several interactive applications, including cloth simulation for feature animation, sound rendering for computer games, 3D virtual painting for training and education, catheterization procedure for liver chemoembolization, and crowd simulation for virtual cityscapes. I will conclude by suggesting some research opportunities and applications.

Abstract We present a technique for coupling simulated fluid phenomena that interact with real dynamic scenes captured as a binocular video sequence. We first process the binocular video sequence to obtain a complete 3D reconstruction of the scene, including velocity information. We use stereo for the visible parts of 3D geometry and surface completion to fill the missing regions. We then perform fluid simulation within a 3D domain that contains the object, enabling one‐way coupling from the video to the fluid. In order to maintain temporal consistency of the reconstructed scene and the animated fluid across frames, we develop a geometry tracking algorithm that combines optic flow and depth information with a novel technique for “velocity completion”. The velocity completion technique uses local rigidity constraints to hypothesize a motion field for the entire 3D shape, which is then used to propagate and filter the reconstructed shape over time. This approach not only generates smoothly varying geometry across time, but also simultaneously provides the necessary boundary conditions for one‐way coupling between the dynamic geometry and the simulated fluid. Finally, we employ a GPU based scheme for rendering the synthetic fluid in the real video, taking refraction and scene texture into account.

Abstract We present a fast goal‐directed motion synthesis technique that integrates sample‐based planning methods with constraint‐based dynamics simulation using a finite element formulation to generate collision‐free paths for deformable models. Our method allows the user to quickly specify various constraints, including a desired trajectory as a sparse sequence of waypoints, and it automatically computes a physically plausible path that satisfies geometric and physical constraints. We demonstrate the performance of our algorithm by computing animated realistic motion of deformable characters and simulation of a medical procedure. Copyright © 2008 John Wiley & Sons, Ltd.

We present a novel technique for the animation of turbulent fluids by coupling a procedural turbulence model with a numerical fluid solver to introduce subgrid-scale flow detail. From the large-scale flow simulated by the solver, we model the production and behavior of turbulent energy using a physically motivated energy model. This energy distribution is used to synthesize an incompressible turbulent velocity field, whose features show plausible temporal behavior through a novel Lagrangian approach for advected noise. The synthesized turbulent flow has a dynamical effect on the large-scale flow, and produces visually plausible detailed features on both gaseous and free-surface liquid flows. Our method is an order of magnitude faster than full numerical simulation of equivalent resolution, and requires no manual direction.

The four papers in this special section focus on the field of virtual reality. The papers are summarized here.

We present a novel approach for efficient path planning and navigation of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed using first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. Moreover, we use the path information and proximity relationships for local dynamics computation of each agent by extending a social force model [Helbing05]. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues and present techniques to improve the accuracy of our algorithm. Our algorithm is used for real-time multi-agent planning in pursuit-evasion, terrain exploration and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.

We present a novel motion planning algorithm that efficiently generates physics-based samples in a kinematically and dynamically constrained space of a highly articulated chain. Similar to prior kinodynamic planning methods, the sampled nodes in our roadmaps are generated based on dynamic simulation. Moreover, we bias these samples by using constraint forces designed to avoid collisions while moving toward the goal configuration. We adaptively reduce the complexity of the state space by determining a subset of joints that contribute most towards the motion and only simulate these joints. Based on these configurations, we compute a valid path that satisfies non-penetration, kinematic, and dynamics constraints. Our approach can be easily combined with a variety of motion planning algorithms including probabilistic roadmaps (PRMs) and rapidly-exploring random trees (RRTs) and applied to articulated robots with hundreds of joints. We demonstrate the performance of our algorithm on several challenging benchmarks

We present a novel algorithm for motion planning of multiple robots amongst dynamic obstacles. Our approach is based on a new roadmap representation that uses deformable links and dynamically retracts to capture the connectivity of the free space. We use Newtonian physics and Hooke's Law to update the position of the milestones and deform the links in response to the motion of other robots and the obstacles. Based on this roadmap representation, we describe our planning algorithms that can compute collision-free paths for tens of robots in complex dynamic environments.

We present a route planning algorithm for cable and wire layouts in complex environments. Our algorithm precomputes a global roadmap of the environment by using a variant of the probabilistic roadmap method (PRM) and performs constrained sampling near the contact space. Given the initial and the final configurations, we compute an approximate path using the initial roadmap generated on the contact space. We refine the approximate path by performing constrained sampling and use adaptive forward dynamics to compute a penetration-free path. Our algorithm takes into account geometric constraints like non-penetration and physical constraints like multi-body dynamics and joint limits. We highlight the performance of our planner on different scenarios of varying complexity.

We present a novel approach for real-time path planning of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed from the first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues for accurate computation. Our algorithm is used for real-time multi-agent planning in pursuit-evasion and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal

We present a novel algorithm for navigating a large number of independent agents in complex and dynamic environments. We compute adaptive roadmaps to perform global path planning for each agent simultaneously. We take into account dynamic obstacles and inter-agents interaction forces to continuously update the roadmap by using a physically-based agent dynamics simulator. We also introduce the notion of 'link bands' for resolving collisions among multiple agents. We present efficient techniques to compute the guiding path forces and perform lazy updates to the roadmap. In practice, our algorithm can perform real-time navigation of hundreds and thousands of human agents in indoor and outdoor scenes.

Abstract Fast contact handling of soft articulated characters is a computationally challenging problem, in part due to complex interplay between skeletal and surface deformation. We present a fast, novel algorithm based on a layered representation for articulated bodies that enables physically‐plausible simulation of animated characters with a high‐resolution deformable skin in real time. Our algorithm gracefully captures the dynamic skeleton‐skin interplay through a novel formulation of elastic deformation in the pose space of the skinned surface. The algorithm also overcomes the computational challenges by robustly decoupling skeleton and skin computations using careful approximations of Schur complements, and efficiently performing collision queries by exploiting the layered representation. With this approach, we can simultaneously handle large contact areas, produce rich surface deformations, and capture the collision response of a character/s skeleton.

Abstract Turing first theorized that many biological patterns arise through the processes of reaction and diffusion. Subsequently, reaction‐diffusion systems have been studied in many fields, including computer graphics. We first show that for visual simulation purposes, reaction‐diffusion equations can be made unconditionally stable using a variety of straightforward methods. Second, we propose an anisotropy embedding that significantly expands the space of possible patterns that can be generated. Third, we show that by adding an advection term, the simulation can be coupled to a fluid simulation to produce visually appealing flows. Fourth, we couple fast marching methods to our anisotropy embedding to create a painting interface to the simulation. Unconditional stability is maintained throughout, and our system runs at interactive rates. Finally, we show that on the Cell processor, it is possible to implement reaction‐diffusion on top of an existing fluid solver with no significant performance impact. Copyright © 2007 John Wiley & Sons, Ltd.

We present a fast method for simulating, animating, and rendering lightning using adaptive grids. The "dielectric breakdown model" is an elegant algorithm for electrical pattern formation that we extend to enable animation of lightning. The simulation can be slow, particularly in 3D, because it involves solving a large Poisson problem. Losasso et al. recently proposed an octree data structure for simulating water and smoke, and we show that this discretization can be applied to the problem of lightning simulation as well. However, implementing the incomplete Cholesky conjugate gradient (ICCG) solver for this problem can be daunting, so we provide an extensive discussion of implementation issues. ICCG solvers can usually be accelerated using "Eisenstat's trick," but the trick cannot be directly applied to the adaptive case. Fortunately, we show that an "almost incomplete Cholesky" factorization can be computed so that Eisenstat's trick can still be used. We then present a fast rendering method based on convolution that is competitive with Monte Carlo ray tracing but orders of magnitude faster, and we also show how to further improve the visual results using jittering.

We present a novel technique for synthesizing textures over dynamically changing fluid surfaces. We use both image textures as well as bump maps as example inputs. Image textures can enhance the rendering of the fluid by either imparting realistic appearance to it or by stylizing it, whereas bump maps enable the generation of complex micro-structures on the surface of the fluid that may be very difficult to synthesize using simulation. To generate temporally coherent textures over a fluid sequence, we transport texture information, i.e. color and local orientation, between free surfaces of the fluid from one time step to the next. This is accomplished by extending the texture information from the first fluid surface to the 3D fluid domain, advecting this information within the fluid domain along the fluid velocity field for one time step, and interpolating it back onto the second surface -- this operation, in part, uses a novel vector advection technique for transporting orientation vectors. We then refine the transported texture by performing texture synthesis over the second surface using our "surface texture optimization" algorithm, which keeps the synthesized texture visually similar to the input texture and temporally coherent with the transported one. We demonstrate our novel algorithm for texture synthesis on dynamically evolving fluid surfaces in several challenging scenarios.

Realistic hair modeling is a fundamental part of creating virtual humans in computer graphics. This paper surveys the state of the art in the major topics of hair modeling: hairstyling, hair simulation, and hair rendering. Because of the difficult, often unsolved problems that arise in all these areas, a broad diversity of approaches are used, each with strengths that make it appropriate for particular applications. We discuss each of these major topics in turn, presenting the unique challenges facing each area and describing solutions that have been presented over the years to handle these complex issues. Finally, we outline some of the remaining computational challenges in hair modeling.

We present an interactive approach for generating realistic physically-based sounds from rigid-body dynamic simulations. We use spring-mass systems to model each object's local deformation and vibration, which we demonstrate to be an adequate approximation for capturing physical effects such as magnitude of impact forces, location of impact, and rolling sounds. No assumption is made about the mesh connectivity or topology. Surface meshes used for rigid-body dynamic simulation are utilized for sound simulation without any modifications. We use results in auditory perception and a novel priority-based quality scaling scheme to enable the system to meet variable, stringent time constraints in a real-time application, while ensuring minimal reduction in the perceived sound quality. With this approach, we have observed up to an order of magnitude speed-up compared to an implementation without the acceleration. As a result, we are able to simulate moderately complex simulations with upto hundreds of sounding objects at over 100 frames per second (FPS), making this technique well suited for interactive applications like games and virtual environments. Furthermore, we utilize OpenAL and EAX™ on Creative Sound Blaster Audigy 2™ cards for fast hardware-accelerated propagation modeling of the synthesized sound.

We present a data-driven method for interactive simulation and visualization of fibrin fibers, a major component of blood clotting. A fibrin fiber is a complex system consisting of a hierarchy with at least three separate levels of detail. Using measurements acquired with an atomic force microscope (AFM) at the smallest scale in this hierarchy, a physically-based model for the larger scales can be constructed and then simulated. Unlike most traditional work dealing with Monte Carlo (MC) or Molecular Dynamics (MD) simulations, our method makes simplifying assumptions about the simulation and enables interactive visualization of simulated fibers in a virtual environment.

We have developed a physically-based VR system that enables users to interactively style dynamic virtual hair by using multiresolution simulation techniques and graphics hardware rendering acceleration for simulating and rendering hair in real time. With a 3D haptic interface, users can directly manipulate and position hair strands, as well as employ real-world styling applications (cutting, blow-drying, etc.) to create hairstyles more intuitively than previous techniques.

This paper presents a modular algorithm for six-degree-of-freedom (6-DOF) haptic rendering. The algorithm is aimed to provide transparent manipulation of rigid models with a high polygon count. On the one hand, enabling a stable display is simplified by exploiting the concept of virtual coupling and employing passive implicit integration methods for the simulation of the virtual tool. On the other hand, transparency is enhanced by maximizing the update rate of the simulation of the virtual tool, and thereby the coupling impedance, and allowing for stable simulation with small mass values. The combination of a linearized contact model that frees the simulation from the computational bottleneck of collision detection, with penalty-based collision response well suited for fixed time-stepping, guarantees that the motion of the virtual tool is simulated at the same high rate as the synthesis of feedback force and torque. Moreover, sensation-preserving multiresolution collision detection ensures a fast update of the linearized contact model in complex contact scenarios, and a novel contact clustering technique alleviates possible instability problems induced by penalty-based collision response

We present a reliable culling algorithm that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs for eliminating a subset of primitives that are not in close proximity. In order to overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. We integrate our culling algorithm with CULLIDE [1] and use it to perform reliable GPU-based collision queries at interactive rates on all types of models, including nonmanifold geometry, deformable models, and breaking objects.

We present a fast and reliable collision detection algorithm using graphics processors. We use visibility computations to prune non-overlapping pairs of triangles. We overcome the accuracy problems due to limited viewport resolution using Minkowski sums of primitives and a pixel-size sphere.

We present a novel algorithm for motion planning of a deformable robot in a static environment. Given the initial and final configuration of the robot, our algorithm computes an approximate path using the probabilistic roadmap method. We use "constraint-based planning" to simulate robot deformation and make appropriate path adjustments and corrections to compute a collision-free path. Our algorithm takes into account geometric constraints like non-penetration and physical constraints like volume preservation. We highlight the performance of our planner on different scenarios of varying complexity.

Proximity query is an integral part of any motion planning algorithm and takes up the majority of planning time. Due to performance issues, most existing planners perform queries at fixed sampled configurations, sometimes resulting in missed collisions. Moreover, randomly determining collision-free configurations makes it difficult to obtain samples close to, or on, the surface of C-obstacles in the configuration space. In this paper, we present an efficient and practical local planning method in contact space which uses “continuous collision detection” (CCD). We show how, using the precise contact information provided by a CCD algorithm, a randomized planner can be enhanced by efficiently sampling the contact space, as well as by constraining the sampling when the roadmap is expanded. We have included our contact-space planning methods in a freely available state-of-the-art planning library - the Stanford MPK library. We have been able to observe that in complex scenarios involving cluttered and narrow passages, which are typically difficult for randomized planners, the enhanced planner offers up to 70 times performance improvement when our contact-space sampling and constrained sampling methods are enabled.

We describe a novel algorithm for visibility ordering among non-overlapping geometric objects in complex and dynamic environments. Our algorithm rearranges the objects in a back-to-front or a front-to-back order from a given viewpoint. We perform comparisons between the primitives by using occlusion queries on the GPUs and exploit frame to frame coherence to reduce the number of occlusion queries. Our visibility ordering algorithm requires no preprocessing and is applicable to all kind of models, including polygon soups and deformable models. We have used our algorithm for order-independent transparency computations in high-depth complexity environments and performing N-body collision culling in dynamic environments. We have implemented our algorithm on a PC with a 3.4 GHz Pentium IV CPU with a NVIDIA GeForce FX 6800 Ultra GPU and applied it to complex environments with tens or hundreds of thousands of polygons. Our algorithm can compute a visibility ordering among the objects and triangles at interactive frame rates.

Design and analysis of articulated mechanical structures, commonly referred to as linkages, is an integral part of any CAD/CAM system. The most common approaches formulate the problem as purely geometric in nature, though dynamics or quasi-statics of linkages should also be considered. Existing optimal algorithms that compute forward dynamics or quasi-statics of linkages have a linear runtime dependence on the number of joints in the linkage. When forces are applied to a linkage, these techniques need to compute the accelerations of all the joints and can become impractical for rapid prototyping of highly complex linkages with a large number of joints.We introduce a novel algorithm that enables adaptive refinement of the forward quasi-statics simulation of complex linkages. This algorithm can cull away joints whose contribution to the overall linkage motion is below a given user-defined threshold, thus limiting the computation of the joint accelerations and forces to those that contribute most to the overall motion. It also allows a natural trade-off between the precision of the resulting simulation and the time required to compute it. We have implemented our algorithm and tested its performance on complex benchmarks consisting of up to 50,000 joints. We demonstrate that in some cases our algorithm is able to achieve up to two orders of magnitude of performance improvement, while providing a high-precision, error-bounded approximation of the quasi-statics of the simulated linkage.

We present a fast collision culling algorithm for performing interand intra-object collision detection among complex models using graphics hardware. Our algorithm is based on CULLIDE [8] and performs visibility queries on the GPUs to eliminate a subset of geometric primitives that are not in close proximity. We present an extension to CULLIDE to perform intra-object or selfcollisions between complex models. Furthermore, we describe a novel visibility-based classification scheme to compute potentiallycolliding and collision-free subsets of objects and primitives, which considerably improves the culling performance. We have implemented our algorithm on a PC with an NVIDIA GeForce FX 6800 Ultra graphics card and applied it to three complex simulations, each consisting of objects with tens of thousands of triangles. In practice, we are able to compute all the self-collisions for cloth simulation up to image-space precision at interactive rates.

Abstract We present a novel multi‐resolution algorithm for simulation of complex cloth‐like deforming meshes. Our algorithm precomputes a multi‐resolution hierarchy by using a combination of ‘chromatic decomposition’1and polygonal simplification of the underlying mesh. At runtime we selectively refine or coarsen the mesh based on the collision proximity of the mesh primitives with non‐adjacent primitives. Our algorithm handles all kind of contacts, including self collisions among mesh primitives. The multi‐resolution hierarchy is used to compute simplification of contact manifolds and to accelerate collision detection and response computations. We have implemented our algorithm on a high‐end PC and applied it to complex simulations with tens of thousands of polygons. In practice, our algorithm is able to achieve interactive performance, while maintaining good visual fidelity. Copyright © 2005 John Wiley & Sons, Ltd.

We present a novel algorithm for accurately detecting all contacts, including self-collisions, between deformable models. We precompute a chromatic decomposition of a mesh into non-adjacent primitives using graph coloring algorithms. The chromatic decomposition enables us to check for collisions between non-adjacent primitives using a linear-time culling algorithm. As a result, we achieve higher culling efficiency and significantly reduce the number of false positives. We use our algorithm to check for collisions among complex deformable models consisting of tens of thousands of triangles for cloth modeling and medical simulation. Our algorithm accurately computes all contacts at interactive rates. We observed up to an order of magnitude speedup over prior methods.

Forward dynamics is central to physically-based simulation and control of articulated bodies. We present an adaptive algorithm for computing forward dynamics of articulated bodies: using novel motion error metrics, our algorithm can automatically simplify the dynamics of a multi-body system, based on the desired number of degrees of freedom and the location of external forces and active joint forces. We demonstrate this method in plausible animation of articulated bodies, including a large-scale simulation of 200 animated humanoids and multi-body dynamics systems with many degrees of freedom. The graceful simplification allows us to achieve up to two orders of magnitude performance improvement in several complex benchmarks.

Guest Editorial: Special Issue on Haptics, Virtual, and Augmented Reality

We present a flexible modeling approach capable of realistically simulating many varieties of brushes commonly used in painting. Our geometric model of brush heads is a combination of subdivision surfaces and hundreds of individual bristles represented by thin polygonal strips. We exploit bristle-to-bristle coherence, simulating only a fraction of the bristles and using interpolation for the remainder. Our dynamic model incorporates realistic physically-based deformation, including anisotropic friction, brush plasticity, and tip spreading. We use an energy minimization framework with a novel geometric representation of the brush head to generate a wider variety of brushes. Finally, we have developed an improved haptic model that provides realistic force feedback, directly related to the results of the brush dynamic simulation. Using this model, we are able to simulate a wide range of brush styles and create an excellent variety of strokes such as the crisp, curvy strokes of Western decorative painting, or rough scratchy strokes like certain Oriental calligraphy. We have also developed an exporter for a popular free 3D modeling package that makes it easier for non-programmers to create any desired style of brush, real or fanciful.

We present a physically-based method for animating and rendering lightning and other electric arcs. For the simulation, we present the dielectric breakdown model, an elegant formulation of electrical pattern formation. We then extend the model to animate a sustained, 'dancing' electrical arc, by using a simplified Helmholtz equation for propagating electromagnetic waves. For rendering, we use a convolution kernel to produce results competitive with Monte Carlo ray tracing. Lastly, we present user parameters for manipulation of the simulation patterns.

Given the increasing power and usage of commodity graphics processor units (GPUs), promising potential exists for exploiting the fast growing computational power on GPUs for general-purpose computing. We present some of our recent research on fast geometric queries and interactive physical simulation using GPUs.

We present new algorithms for performing fast computation of several common database operations on commodity graphics processors. Specifically, we consider operations such as conjunctive selections, aggregations, and semi-linear queries, which are essential computational components of typical database, data warehousing, and data mining applications. While graphics processing units (GPUs) have been designed for fast display of geometric primitives, we utilize the inherent pipelining and parallelism, single instruction and multiple data (SIMD) capabilities, and vector processing functionality of GPUs, for evaluating boolean predicate combinations and semi-linear queries on attributes and executing database operations efficiently. Our algorithms take into account some of the limitations of the programming model of current GPUs and perform no data rearrangements. Our algorithms have been implemented on a programmable GPU (e.g. NVIDIA's GeForce FX 5900) and applied to databases consisting of up to a million records. We have compared their performance with an optimized implementation of CPU-based algorithms. Our experiments indicate that the graphics processor available on commodity computer systems is an effective co-processor for performing database operations.

Surface texture is among the most salient haptic characteristics of objects; it can induce vibratory contact forces that lead to perception of roughness. We present a new algorithm to display haptic texture information resulting from the interaction between two textured objects. We compute contact forces and torques using low-resolution geometric representations along with texture images that encode surface details. We also introduce a novel force model based on directional penetration depth and describe an efficient implementation on programmable graphics hardware that enables interactive haptic texture rendering of complex models. Our force model takes into account important factors identified by psychophysics studies and is able to haptically display interaction due to fine surface textures that previous algorithms do not capture.

We present a reliable culling algorithm that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs for eliminating a subset of primitives that are not in close proximity. To overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. We integrate our culling algorithm with CULLIDE [8] and use it to perform reliable GPU-based collision queries at interactive rates on all types of models, including non-manifold geometry, deformable models, and breaking objects.

Abstract We present a viscous paint model for use in an interactive painting system based on the well‐known Stokes' equations for viscous flow. Our method is, to our knowledge, the first unconditionally stable numerical method that treats viscous fluid with a free surface boundary. We have also developed a real‐time implementation of the Kubelka‐Munk reflectance model for pigment mixing, compositing and rendering entirely on graphics hardware, using programmable fragment shading capabilities. We have integrated our paint model with a prototype painting system, which demonstrates the model's effectiveness in rendering viscous paint and capturing a thick,impasto‐like style of painting. Several users have tested our prototype system and were able to start creating original art work in an intuitive manner not possible with the existing techniques in commercial systems. Copyright © 2004 John Wiley & Sons, Ltd.

Abstract We present an interactive technique on virtual contact handling for avatars in virtual environments using geometry‐driven physics. If a contact has occurred between an articulated avatar and a virtual environment, the global penetration depth and contact points are estimated based on a fast local penetration depth computation for decomposed convex pieces. The penetration depth and contact information are then used to resolve overlap between the avatar and the virtual environment. If applicable, joint angles for an articulated body are computed using an inverse kinematics approach based on cyclic coordinate descent. Resulting dynamic response with friction is modeled with impulse‐based dynamics under the Coulomb friction law. We demonstrate the algorithm on a modestly complex virtual environment. The resulting system is able to maintain an interactive frame rate of 30–60 Hz. Copyright © 2004 John Wiley & Sons, Ltd.

We present a fast algorithm to estimate the penetration depth between convex polytopes in 3D. The algorithm incrementally seeks a "locally optimal solution" by walking on the surface of the Minkowski sums. The surface of the Minkowski sums is computed implicitly by constructing a local dual mapping on the Gauss map. We also present three heuristic techniques that are used to estimate the initial features used by the walking algorithm. We have implemented the algorithm and compared its performance with earlier approaches. In our experiments, the algorithm is able to estimate the penetration depth in about a milli-second on an 1 GHz Pentium PC. Moreover, its performance is almost independent of model complexity in environments with high coherence between successive instances.

We present a novel approach for modeling hair using level-of-detail representations. The set of representations include individual strands, hair clusters, and hair strips. They are represented using subdivision curves or surfaces, and have the same underlying base skeleton to maintain consistent high-level physical behavior when a transition between different levels-of detail occurs. This framework supports automatic simplification of dynamic simulation, collision detection, and graphical rendering of animated hair. It also offers flexibility to balance between the overall performance and visual quality, and can be used to model and render different hairstyles. We have used these level-of-detail representations to animate various hairstyles and obtained noticeable performance improvement, with little loss in visual quality.

No abstract available.

We present a novel approach for adaptively grouping and subdividing hair using discrete level-of-detail (LOD) representations. The set of discrete LODs include hair strands, clusters and strips. Their dynamic behavior is controlled by a base skeleton. The base skeletons are subdivided and grouped to form clustering hierarchies using a quad-tree data structure during the precomputation. At run time, our algorithm traverses the hierarchy to create continuous LODs on the fly and chooses both the appropriate discrete and continuous hair LOD representations based on the motion, the visibility, and the viewing distance of the hair from the viewer. Our collision detection for hair represented by the proposed LODs relies on a family of "swept sphere volumes" for fast and accurate intersection computations. We also use an implicit integration method to achieve simulation stability while allowing us to take large time steps. Together, these approaches for hair simulation and collision detection offer the flexibility to balance between the overall performance and visual quality of the animated hair. Furthermore, our approach is capable of modeling various styles, lengths, and motion of hair.

We present a novel approach for interactive navigation in complex 3D synthetic environments using path planning. Our algorithm precomputes a global roadmap of the environment by using a variant of randomized motion planning algorithm along with a reachability-based analysis. At runtime, our algorithm performs graph searching and automatically computes a collision-free and constrained path between two user specified locations. It also enables local user-steered exploration, subject to motion constraints and integrates these capabilities in the control loop of 3D interaction. Our algorithm only requires the scene geometry, avatar orientation, and parameters relating the avatar size to the model size. The performance of the preprocessing algorithm grows as a linear function of the model size. We demonstrate its performance on two large environments: a power plant and a factory room.

We introduce a novel "sensation preserving" simplification algorithm for faster collision queries between two polyhedral objects in haptic rendering. Given a polyhedral model, we construct a multiresolution hierarchy using " filtered edge collapse", subject to constraints imposed by collision detection. The resulting hierarchy is then used to compute fast contact response for haptic display. The computation model is inspired by human tactual perception of contact information. We have successfully applied and demonstrated the algorithm on a time-critical collision query framework for haptically displaying complex object-object interaction. Compared to existing exact contact query algorithms, we observe noticeable performance improvement in update rates with little degradation in the haptic perception of contacts.

We present an incremental algorithm to estimate the penetration depth between convex polytopes in 3D. The algorithm incrementally seeks a "locally optimal solution" by walking on the surface of the Minkowski sums. The surface of the Minkowski sums is computed implicitly by constructing a local Gauss map. In practice, the algorithm works well when there is high motion coherence in the environment and is able to compute the optimal solution in most cases.

We present a survey of our recent research on the development of haptic interfaces for simulating creative processes with digital media, including 3D multiresolution modeling and 2D and 3D painting. We discuss the design issues involved and lessons learned. Based on the preliminary user studies, we observe that haptic interfaces can improve the level of usability of digital design systems and assist in capturing the feel of creative processes.

We present a system, ArtNova, for 3D model design with a haptic interface. ArtNova offers the novel capability of interactively applying textures onto 3D surfaces directly by brush strokes, with the orientation of the texture determined the stroke. Building upon the framework of inTouch (Gregory et al., 2000), it further provides an intuitive physically-based force response when deforming a model. This system also uses a user-centric viewing technique that seamlessly integrates the haptic and visual presentation, by taking into account the user's haptic manipulation in dynamically determining the new viewpoint locations. Our algorithm permits automatic placement of the user viewpoint to navigate about the object. ArtNova has been tested by several users and they were able to start modeling and painting with just a few minutes of training. Preliminary user feedback indicates promising potential for 3D texture painting and modeling.

We present a method to efficiently construct and render a smooth surface for approximation of large functional scattered data. Using a subdivision surface framework and techniques from terrain rendering, the resulting surface can be explored from any viewpoint while maintaining high surface fairness and interactive frame rates. We show the approximation error to be sufficiently small for several large data sets. Our system allows for adaptive simplification and provides continuous levels of detail, taking into account the local variation and distribution of the data. Categories and Subject Descriptors (according to ACM CCS): G.1.2 [Approximation]: Approximation of surfaces, Least squares approximation, Piecewise polynomial approximation; I.3.3 [Picture/Image Generation]: Display algorithms, Viewing algorithms; I.3.5 [Computational Geometry and Object Modeling]: Surface representation.

We present a novel framework for automatically simplifying the dynamics computation of particle systems to improve simulation speeds. Our approach is based on a physically-based subdivision scheme to generate a hierarchy of approximated motion models or simulation levels of detail (SLOD). At each time step, the SLODs are updated on-the-fly, and the appropriate SLOD is chosen adaptively to reduce computational costs. We have tested a prototype implementation on the simulation of a water fountain and a galaxy system. The preliminary results show a significant performance gain on these scenarios with little loss in the visual appearance of the simulation, indicating the potential to generalize this approach to other dynamical systems.

We present a fast penetration depth estimation algorithm between deformable polyhedral objects. We assume the continuum of non-rigid models are discretized using standard techniques, such as finite element or finite difference methods. As the objects deform, the pre-computed distance fields are deformed accordingly to estimate the penetration depth, allowing an enforcement of non-penetration constraints between two colliding elastic bodies. This approach can automatically handle self-penetration and inter-penetration in a uniform manner. We demonstrate its effectiveness on moderately complex simulation scenes.

We present a hybrid path planning algorithm for rigid and articulated bodies translating and rotating in a 3D workspace. Our approach generates a Voronoi roadmap in the workspace and combines it with "bridges" computed by a randomized path planner with Voronoi-biased sampling. The Voronoi roadmap is computed from a discrete approximation to the generalized Voronoi diagram (GVD) of the workspace, which is generated using graphics hardware. By using this GVD, portions of the path can be generated without random sampling, substantially reducing the number of random samples needed for the full query. The planner has been implemented and tested on a number of benchmarks. Some preliminary comparisons with a randomized motion planner indicate that our planner performs more than an order of magnitude faster in several challenging scenarios.

We present a new approach for computing generalized proximity information of arbitrary 2D objects using graphics hardware. Using multi-pass rendering techniques and accelerated distance computation, our algorithm performs proximity queries not only for detecting collisions, but also for computing intersections, separation distance, penetration depth, and contact points and normals. Our hybrid geometry and image-based approach balances computation between the CPU and graphics subsystems. Geometric object-space techniques coarsely localize potential intersection regions or closest features between two objects, and image-space techniques compute the low-level proximity information in these regions. Most of the proximity information is derived from a distance field computed using graphics hardware. We demonstrate the performance in collision response computation for rigid and deformable body dynamics simulations. Our approach provides proximity information at interactive rates for a variet...

We present a novel painting system with an intuitive haptic interface, which serves as an expressive vehicle for interactively creating painterly works. We introduce a deformable, 3D brush model, which gives the user natural control of complex brush strokes. The force feedback enhances the sense of realism and provides tactile cues that enable the user to better manipulate the paint brush. We have also developed a bidirectional, two-layer paint model that, combined with a palette interface, enables easy loading of complex blends onto our 3D virtual brushes to generate interesting paint effects on the canvas. The resulting system, DAB, provides the user with an artistic setting, which is conceptually equivalent to a real-world painting environment. Several users have tested DAB and were able to start creating original art work within minutes.

We present several techniques for user-centric viewing of the virtual objects or datasets under haptic exploration and manipulation. Depending on the type of tasks performed by the user, our algorithms compute automatic placement of the user viewpoint to navigate through the scene, to display the near-optimal views, and to reposition the viewpoint for haptic visualization. This is accomplished by conjecturing the user's intent based on the user's actions, the object geometry, and intra- and inter-object occlusion relationships. These algorithms have been implemented and interfaced with both a 3-DOF and a 6-DOF PHANToM arms. We demonstrate their application on haptic exploration and visualization of a complex structure, as well as multiresolution modeling and 3D painting with a haptic interface.

The need to perform fast and accurate proximity queries arises frequently in physically-based modeling, simulation, animation, real-time interaction within a virtual environment, and game dynamics. The set of proximity queries include intersection detection, tolerance verification, exact and approximate minimum distance computation, and (disjoint) contact determination. Specialized data structures and algorithms have often been designed to perform each type of query separately. We present a unified approach to perform any of these queries seamlessly for general, rigid polyhedral objects with boundary representations which are orientable 2-manifolds. The proposed method involves a hierarchical data structure built upon a surface decomposition of the models. Furthermore, the incremental query algorithm takes advantage of coherence between successive frames. It has been applied to complex benchmarks and compares very favorably with earlier algorithms and systems.

Abstract We present an intuitive system,inTouch, for interactively editing and painting a polygonal mesh using a force‐feedback device. An artist or a designer can use this system to create and refine a three‐dimensional multi‐resolution polygonal mesh. The appearance can be further enhanced by directly painting onto its surface. The system allows users to naturally create complex forms and patterns aided not only by visual feedback but also by their sense of touch. Copyright © 2001 John Wiley & Sons, Ltd.

No abstract available.

We present techniques for fast motion planning by using discrete approximations of generalized Voronoi diagrams, computed with graphics hardware. Approaches based on this diagram computation are applicable to both static and dynamic environments of fairly high complexity. We compute a discrete Voronoi diagram by rendering a 3D distance mesh for each Voronoi site. The sites can be points, line segments, polygons, polyhedra, curves and surfaces. The computation of the generalized Voronoi diagram provides fast proximity query toolkits for motion planning. The tools provide the distance to the nearest obstacle stored in the Z-buffer, as well as the Voronoi boundaries, Voronoi vertices and weighted Voronoi graphs extracted from the frame buffer using continuation methods. We have implemented these algorithms and demonstrated their performance for path planning in a complex dynamic environment composed of more than 140,000 polygons.

We present new distance computation algorithms using hierarchies of rectangular swept spheres. Each bounding volume of the tree is described as the Minkowski sum of a rectangle and a sphere, and fits tightly to the underlying geometry. We present accurate and efficient algorithms to build the hierarchies and perform distance queries between the bounding volumes. We also present traversal techniques for accelerating distance queries using coherence and priority directed search. These algorithms have been used to perform proximity queries for applications including virtual prototyping, dynamic simulation, and motion planning on complex models. As compared to earlier algorithms based on bounding volume hierarchies for separation distance and approximate distance computation, our algorithms have achieved significant speedups on many benchmarks.

We present an accelerated proximity query algorithm between moving convex polyhedra. The algorithm combines Voronoi-based feature tracking with a multi-level-of-detail representation, in order to adapt to the variation in levels of coherence and speed up the computation. It provides a progressive refinement framework for collision detection and distance queries. We have implemented our algorithm and have observed significant performance improvements in our experiments, especially on scenarios where the coherence is low.

We present a new approach for faster rendering of large synthetic environments using video-based representations. We decompose the large environment into cells and pre-compute video based impostors using MPEG compression to represent sets of objects that are far from each cell. At runtime, we decode the MPEG streams and use rendering algorithms that provide nearly constant-time random access to any frame. The resulting system has been implemented and used for an interactive walkthrough of a model of a house with 260,000 polygons and realistic lighting and textures. It is able to render this model at 16 frames per second (an eightfold improvement over simpler algorithms) on average on a Pentium II PC with an off-the-shelf graphics card.

We present an algorithm for haptic display of moderately complex polygonal models with a six degree of freedom (DOF) force feedback device. We make use of incremental algorithms for contact determination between convex primitives. The resulting contact information is used for calculating the restoring forces and torques and thereby used to generate a sense of virtual touch. To speed up the computation, our approach exploits a combination of geometric locality, temporal coherence, and predictive methods to compute object-object contacts at kHz rates. The algorithm has been implemented and interfaced with a 6-DOF PHANToM Premium 1.5. We demonstrate its performance on force display of the mechanical interaction between moderately complex geometric structures that can be decomposed into convex primitives.

We present an intuitive 3D interface for interactively editing and painting a polygonal mesh using a force feedback device. An artist or a designer can use the system to create and refine a three-dimensional multiresolution polygonal mesh. Its appearance can be further enhanced by directly painting onto its surface. The system allows users to naturally create complex forms and patterns not only aided by visual feedback, but also by their sense of touch.

No abstract available.

No abstract available.

Article Fast computation of generalized Voronoi diagrams using graphics hardware Share on Authors: Kenneth E. Hoff University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , John Keyser University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Ming Lin University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Dinesh Manocha University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Tim Culver University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile Authors Info & Claims SIGGRAPH '99: Proceedings of the 26th annual conference on Computer graphics and interactive techniquesJuly 1999 Pages 277–286https://doi.org/10.1145/311535.311567Published:01 July 1999 311citation3,192DownloadsMetricsTotal Citations311Total Downloads3,192Last 12 Months86Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present a framework for fast and accurate collision detection for haptic interaction with polygonal models. Given a model, we pre-compute a hybrid hierarchical representation, consisting of uniform grids and trees of tight-fitting oriented bounding box trees (OBB-Trees). At run time, we use hybrid hierarchical representations and exploit frame-to-frame coherence for fast proximity queries. We describe a new overlap test, which is specialized for intersection of a line segment with an oriented bounding box for haptic simulation and takes 6-36 operations excluding transformation costs. The algorithms have been implemented as part of H-COLLIDE and interfaced with a PHANToM arm and its haptic toolkit, GHOST, and applied to a number of models. As compared to the commercial implementation, we are able to achieve up to 20 times speedup in our experiments and sustain update rates over 1000 Hz on a 400 MHz Pentium II.

Abstract We present a sub-linear algorithm to compute the set of back-facing polygons in a polyhedral model. The algorithm partitions the model into hierarchical clusters based on the orientations and positions of the polygons. As a pre-processing step, the algorithm constructs spatial decompositions with respect to each cluster. For a sequence of back-face computations, the algorithm exploits the coherence in view-point movement to efficiently determine whether it is in front of or behind a cluster. Due to coherence, the algorithm's expected running time is linear in the number of clusters on average. We have applied this algorithm to speed up the rendering of polyhedral models. On average, we are able to cull about 40% of the polygons. The algorithm accounts for 5% of the total CPU time per frame on an SGI Onyx. The overall frame rate is improved by 40–75% as compared to the standard back-face culling implemented in hardware. We also present an extension of our back-face computation algorithm to determine silhouettes of polygonal models. Our technique finds true perspective silhouettes by collecting edges at the common boundaries of back-facing and front-facing clusters.

We describe an approach for interactive collision detection and proximity computations on massive models composed of millions of geometric primitives. We address issues related to interactive data access and processing in a large geometric database, which may not fit into main memory of typical desktop workstations or computers. We present a new algorithm using overlap graphs for localizing the “regions of interest” within a massive model, thereby reducing runtime memory requirements. The overlap graph is computed off‐line, pre‐processed using graph partitioning algorithms, and modified on the fly as needed. At run time, we traverse localized sub‐graphs to check the corresponding geometry for proximity and pre‐fetch geometry and auxiliary data structures. To perform interactive proximity queries, we use bounding‐volume hierarchies and take advantage of spatial and temporal coherence. Based on the proposed algorithms, we have developed a system called IMMPACT and used it for interaction with a CAD model of a power plant consisting of over 15 million triangles. We are able to perform a number of proximity queries in real‐time on such a model. In terms of model complexity and application to large models, we have improved the performance of interactive collision detection and proximity computation algorithms by an order of magnitude.

Presents a new approach for establishing correspondence between two homeomorphic 3D polyhedral models. The user can specify corresponding feature pairs on the polyhedra with a simple and intuitive interface. Based on these features, our algorithm decomposes the boundary of each polyhedron into the same number of morphing patches. A 2D mapping for each morphing patch is computed in order to merge the topologies of the polyhedra one patch at a time. We create a morph by defining morphing trajectories between the feature pairs and by interpolating them across the merged polyhedron. The user interface provides high-level control as well as local refinement to improve the morph. The implementation has been applied to several complex polyhedra composed of thousands of polygons. The system can also handle non-simple polyhedra that have holes.

In this paper, we present an efficient algorithm for contact determination between spline models. We make use of a new hierarchy, called ShellTree, that comprises of spherical shells and oriented bounding boxes. Each spherical shell corresponds to a portion of the volume between two concentric spheres. Given large spline models, our algorithm decomposes each surface into Bézier patches as part of pre‐processing. At runtime it dynamically computes a tight fitting axis‐aligned bounding box across each Bézier patch and efficiently checks all such boxes for overlap. Using off‐line and on‐line techniques for tree construction, our algorithm computes ShellTrees for Bézier patches and performs fast overlap tests between them to detect collisions. The overall approach can trade off runtime performance for reduced memory requirements. We have implemented the algorithm and tested it on large models, each composed of hundred of patches. Its performance varies with the configurations of the objects. For many complex models composed of hundreds of patches, it can accurately compute the contacts in a few milliseconds.

: Many applications in computer graphics and virtual environments need to render datasets with large numbers of primitives and high depth complexityatinteractive rates. However, standard techniques like view frustum culling and a hardware z-bu#er are unable to display datasets composed of hundred of thousands of polygons at interactive frame rates on current high-end graphics systems. We add a #conservative" visibility culling stage to the rendering pipeline, attempting to identify and avoid processing of occluded polygons. Given a moving viewpoint, the algorithm dynamically chooses a set of occluders. Each occluder is used to compute a shadow frustum, and all primitives contained within this frustum are culled. The algorithm hierarchicallytraverses the model, culling out parts not visible from the current viewpoint using e#cient, robust, and in some cases specialized interference detection algorithms. The algorithm's performance varies with the location of the viewpoint and the depth...

No abstract available.

Fast and accurate collision detection between general polygonal models is a fundamental problem in physically based and geometric modeling, robotics, animation, and computer-simulated environments. Most earlier collision detection algorithms are either restricted to a class of models (such as convex polytopes) or are not fast enough for practical applications. The authors present an incremental algorithm for collision detection between general polygonal models in dynamic environments. The algorithm combines a hierarchical representation with incremental computation to rapidly detect collisions. It makes use of coherence between successive instances to efficiently determine the number of object features interacting. For each pair of objects, it tracks the closest features between them on their respective convex hulls. It detects the objects' penetration using pseudo internal Voronoi cells and constructs the penetration region, thus identifying the regions of contact on the convex hulls. The features associated with these regions are represented in a precomputed hierarchy. The algorithm uses a coherence based approach to quickly traverse the precomputed hierarchy and check for possible collisions between the features. They highlight its performance on different applications.

We present efficient and accurate algorithms for interference detection among objects undergoing polynomial deformation. The scope of our algorithms include physically-based models undergoing dynamic simulation subject to non-penetration constraints, variational models, deformable models used in soft object animation, geometric models including polygonal meshes, parametric surfaces such as Bezier patches and B-splines, and solid models defined by such surfaces. Our algorithms use axis aligned bounding boxes and convex hulls of the objects to identify the object pairs in close vicinity. They use subdivision, convex hull properties and linear programming to perform surface intersection tests and loop intersection tests. Frame-to-frame coherence is utilized to achieve incremental computations. The resulting algorithms have been implemented and work well in practice. In particular we are able to compute all contacts accurately and at interactive speeds for flexible bodies undergoing second-order polynomial deformations.

Article OBBTree: a hierarchical structure for rapid interference detection Share on Authors: S. Gottschalk Department of Computer Science, University of North Carolina, Chapel Hill, NC Department of Computer Science, University of North Carolina, Chapel Hill, NCView Profile , M. C. Lin Department of Computer Science, University of North Carolina, Chapel Hill, NC and U.S. Army Research Office Department of Computer Science, University of North Carolina, Chapel Hill, NC and U.S. Army Research OfficeView Profile , D. Manocha Department of Computer Science, University of North Carolina, Chapel Hill, NC Department of Computer Science, University of North Carolina, Chapel Hill, NCView Profile Authors Info & Claims SIGGRAPH '96: Proceedings of the 23rd annual conference on Computer graphics and interactive techniquesAugust 1996 Pages 171–180https://doi.org/10.1145/237170.237244Online:01 August 1996Publication History 959citation5,396DownloadsMetricsTotal Citations959Total Downloads5,396Last 12 Months262Last 6 weeks40 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

No abstract available.

We present fast algorithms for penetration detection and contact determination between polyhedral models in dynamic environments. They are based on a distance computation algorithm for convex polytopes and a hierarchical coherence-based algorithm to compute contacts. In particular, we extend an earlier expected constant time algorithm for distance computation between convex polytopes to detect penetrations. The algorithm computes all the contacts between the convex hulls of the polytopes. After identifying the contact regions it traverses the features lying beneath them to more precisely determine the contact regions. The traversal employs a dynamic technique, sweep and prune, to overcome the O(n/sup 2/) pairwise feature checks. The complexity of the overall algorithm is output sensitive. We demonstrate its performance on the dynamic simulation of a threaded insertion.

we present an exact and interactive collision detection system, I-COLLIDE, for large-scale environments. Such environments are characterized by the number of objects undergoing rigid motion and the complexity of the models. The algorithm does not assume the objects' motions can be expressed as a closed form function of time. The collision detection system is general and can be easily interfaced with a variety of applications. The algorithm uses a two-level approach based on pruning multiple-object pairs using bounding boxes and performing exact collision detection between selected pairs of polyhedral models. We demonstrate the performance of the system in walkthrough and simulation environments consisting of a large number of moving objects. In particular, the system takes less than 1/20 of a second to determine all the collisions and contacts in an environment consisting of more than 1000 moving polytopes, each consisting of more than 50 faces on an HP-9000/750.

No abstract available.

We present an efficient contact determination algorithm for objects undergoing rigid motion. The environment consists of polytopes and models described by algebraic sets. We extend an expected constant time collision detection algorithm between convex polytopes to concave polytopes and curved models. The algorithm makes use of hierarchical representations for concave polytopes and local, global methods for solving polynomial equations to determine possible contact points. We also propose techniques to reduce O(n/sup 2/) pairwise intersection tests for a large environment of n objects. These algorithms work well in practice and give real time performance for most environments.>

A simple and efficient algorithm for finding the closest points between two convex polynomials is described. Data from numerous experiments tested on a broad set of convex polyhedra on R/sup 3/ show that the running time is roughly constant for finding closest points when nearest points are approximately known and is linear in total number of vertices if no special initialization is done. This algorithm can be used for collision detection, computation of the distance between two polyhedra in three-dimensional space, and other robotics problems. It forms the heart of the motion planning algorithm previously presented by the authors (Proc. IEEE ICRA, p.1554-9, 1990).>

A robot planning algorithm that constructs a global skeleton of free-space by incremental local methods is described. The curves of the skeleton are the loci of maxima of an artificial potential field that is directly proportional to the distance of the robot from obstacles. The method has the advantage of fast convergence of local methods in uncluttered environments, but it also has a deterministic and efficient method of escaping local extremal points of the potential function. The authors present a general algorithm, for configuration spaces of any dimension, and describe instantiations of the algorithm for robots with two and three degrees of freedom.>