In robotic task planning, symbolic planners using rule-based representations like PDDL are effective but struggle with long-sequential tasks in complicated environments due to exponentially increasing search space. Meanwhile, LLM-based approaches, which are grounded in artificial neural networks, offer faster inference and commonsense reasoning but suffer from lower success rates. To address the limitations of the current symbolic (slow speed) or LLM-based approaches (low accuracy), we propose a novel neuro-symbolic task planner that decomposes complex tasks into subgoals using LLM and carries out task planning for each subgoal using either symbolic or MCTS-based LLM planners, depending on the subgoal complexity. This decomposition reduces planning time and improves success rates by narrowing the search space and enabling LLMs to focus on more manageable tasks. Our method significantly reduces planning time while maintaining high success rates across three task planning domains, as well as real-world and simulated robotics environments. More details are available at http://graphics.ewha.ac.kr/LLMTAMP/.

Panoramic RGB-D cameras enable high-quality 3D scene reconstruction but require manual viewpoint selection and physical camera transportation, making the process time-consuming and tedious—especially for novice users. Key challenges include ensuring sufficient feature overlap between camera views and planning collision-free paths. We propose a fully autonomous scan planner that generates efficient and collision-free tours with adequate viewpoint overlap to address these issues. Experiments in both synthetic and real-world environments show that our method achieves up to 99% scan coverage and is up to three times faster than state-of-the-art view planning approaches.

ABSTRACT We propose new crowd simulation methods to virtually reenact the Itaewon disaster that occurred in 2022 due to the extreme crowd density. Conventional techniques make it challenging to simulate diverse, extremely dense crowd behaviors such as crowd surge, fluidization, and falls observed at the Itaewon disaster. This paper proposes a kinodynamic agent simulation combining kinematic agents for low‐density crowds, hydrodynamic and hydrostatic agents for high‐density crowds, and articulated passive agents for high‐density crowds in dense contact. In order to perform co‐simulation among heterogeneous agent types, we use a message‐passing mechanism to share relevant kinematic and dynamic information among agents and make agent‐type transitions based on crowd density and contact forces. Experiments show that the proposed hybrid simulation approach can accurately reenact crowd phenomena observed at the Itaewon compared to the CCTV footage. Moreover, our ablation study supports the use of kinodynamic agents to faithfully reconstruct the Itaewon crowd behavior. Furthermore, we run three what‐if scenarios to explore the possibilities of using our techniques to help prevent incidents in the future. Finally, to demonstrate the applicability of our proposed methods to other types of extreme crowd behaviors besides the Itaewon disaster, we simulate two other real‐world crowd incidents using our techniques.

We present an efficient and scalable learning-based autonomous exploration system for mobile robots navi-gating unknown indoor environments. Our system incorporates three network models trained to identify the frontier region (FR), to evaluate the detected FR regions based on their proximity to the robot (A*-Net), and to measure the coverage reward at the FR regions (Viz-Net). Our method employs an active window of the map that moves along with the robot, offering scalable exploration capabilities while maintaining a high rate of exploration coverage owing to the two exploratory measures utilized by A*-Net (proximity) and Viz-Net (coverage). Consequently, Our system completes over 99% coverage in a large-scale benchmarking world, scaling up to 135m × +80m. In contrast, other state-of-the-art approaches completed only less than 40% of the same world with a 30% slower exploration speed than ours.

We present a new robotic drawing system based on stroke-based rendering (SBR). Our motivation is the artistic quality of the whole performance. Not only should the generated strokes in the final drawing resemble the input image, but the stroke sequence should also exhibit a human artist's planning process. Thus, when a robot executes the drawing task, both the drawing results and the way the robot executes would look artistic. Our SBR system is based on image segmentation and depth estimation. It generates the drawing strokes in an order that allows for the intended shape to be perceived quickly and for its detailed features to be filled in and emerge gradually when observed by the human. This ordering represents a stroke plan that the drawing robot should follow to create an artistic rendering of images. We experimentally demonstrate that our SBR-based drawing makes visually pleasing artistic images, and our robotic system can replicate the result with proper sequences of stroke drawing.

We present a semiautonomous robotic pen-drawing system, called SSK, that is capable of creating pen art on a large nonplanar surface. Our robotic system relies on a seven-degree-of-freedom impedance-controlled manipulator with a three-degree-of-freedom holonomic mobile platform. We use a vector-graphics engine to take an artist's pen drawing as input, and we generate Bézier spline curves to be drawn on the given target drawing canvas. Then, our system finds a set of minimal, discrete configurations for the mobile platform to cover the entire canvas surface while considering the reachability of the manipulator. The drawing is split into multiple subdrawings according to the found configurations. Our system replicates the spline drawing on the target surface using impedance control, which enables us to compensate for the uncertainty and incompleteness inherent to canvas-surface representations and various robotic and sensor noises. We demonstrate that our system can create visually pleasing and complicated pen art on large, nonplanar surfaces.

We propose a fully autonomous system for mobile robot exploration in unknown environments. Our system employs a novel frontier detection algorithm based on the fast front propagation (FFP) technique and uses parallel path planning to reach the detected front regions. Given an occupancy grid map in 2D, possibly updated online, our algorithm can find all the frontier points that can allow mobile robots to visit unexplored regions to maximize the exploratory coverage. Our FFP method is six~seven times faster than the state-of-the-art wavefront frontier detection algorithm in terms of finding frontier points without compromising the detection accuracy. The speedup can be further accelerated by simplifying the map without degrading the detection accuracy. To expedite locating the optimal frontier point, We also eliminate spurious points by the obstacle filter and the novel boundary filter. In addition, we parallelize the global planning phase using the branch-and-bound A*, where the search space of each thread is confined by its best knowledge discovered during the parallel search. As a result, our parallel path-planning algorithm operating on 20 threads is about 30 times faster than the vanilla exploration system that operates on a single thread. Our method is validated through extensive experiments, including autonomous robot exploration in both synthetic and real-world scenarios. In the real-world experiment, we show that an autonomous navigation system using a human-sized mobile manipulator robot equipped with a low-end embedded processor that fully integrates our FFP and parallel path-planning algorithms.

Probabilistic volumetric mapping (PVM) represents a 3D environmental map for an autonomous robotic navigational task. A popular implementation such as Octomap is widely used in the robotics community for such a purpose. The Octomap relies on an octree to represent a PVM and its main bottleneck lies in massive ray-shooting to determine the occupancy of the underlying volumetric voxel grids.In this paper, we propose GPU-based ray shooting to drastically improve the ray shooting performance in Octomap. Our main idea is based on the use of recent ray-tracing RTX GPU, mainly designed for real-time photo-realistic computer graphics and the accompanying graphics API, known as DXR. Our ray-shooting first maps leaf-level voxels in the given octree to a set of axis-aligned bounding boxes (AABBs) and employ massively parallel ray shooting on them using GPUs to find free and occupied voxels. These are fed back into the CPU to update the voxel occupancy and restructure the octree. In our experiments, we have observed more than three-orders-of-magnitude performance improvement in terms of ray shooting using ray-tracing RTX GPU over a state-of-the-art Octomap CPU implementation, where the benchmarking environments consist of more than 77K points and 25K~34K voxel grids.

We propose a novel RGB-D camera tracking system that robustly reconstructs hand-held RGB-D camera sequences. The robustness of our system is achieved by two independent features of our method: adaptive visual odometry (VO) and integer programming-based key-frame selection. Our VO method adaptively interpolates the camera motion results of the direct VO (DVO) and the iterative closed point (ICP) to yield more optimal results than existing methods such as Elastic-Fusion. Moreover, our key-frame selection method locates globally optimum key-frames using a comprehensive objective function in a deterministic manner rather than heuristic or experience-based rules that prior methods mostly rely on. As a result, our method can complete reconstruction even if the camera fails to be tracked due to discontinuous camera motions, such as kidnap events, when conventional systems need to backtrack the scene. We validated our tracking system on 25 TUM benchmark sequences against state-of-the-art works, such as ORBSLAM2, Elastic-Fusion, and DVO SLAM, and experimentally showed that our method has smaller and more robust camera trajectory errors than these systems.

We present a novel algorithm for physics-based real-time facial animation driven by muscle deformation. Unlike the previous works using 3D finite elements, we use a 2D shell element to avoid inefficient or undesired tessellation due to the thin structure of facial muscles. To simplify the analysis and achieve real-time performance, we adopt real-time thin shell simulation of [Choi et al. 2007]. Our facial system is composed of four layers of skin, subcutaneous layer, muscles, and skull, based on human facial anatomy. Skin and muscles are composed of shell elements, subcutaneous fatty tissue is assumed as a uniform elastic body, and the fixed part of facial muscles is handled by static position constraint. We control muscles to have stretch deformation using modal analysis and apply mass-spring force to skin mesh which is triggered by the muscle deformation. In our system, only the region of interest for skin can be affected by the muscle. To handle the coupled result of facial animation, we decouple the system according to the type of external forces applied to the skin. We show a series of real-time facial animation caused by selected major muscles that are relevant to expressive skin deformation. Our system has generality for importing new types of muscles and skin mesh when their shape or positions are changed.

We propose a novel method adaptive subdivision (AS) to evaluate the distance function for moving general polygonal models. The distance function can have a positive and a negative value, each of which corresponds to the Euclidean distance and penetration depth, respectively. In our approach, the distance between a pair of objects can be evaluated along any time interval of the object's trajectory; therefore it is called “continuous”, and a minimum of the continuous distance (MCD) is determined for collision avoidance. In order to compute a MCD for general polygonal models, we calculate the upper and lower bounds of the distance in the time interval and abandons the time intervals that cannot realize the MCD. We have implemented our distance evaluation method, and have experimentally validated the proposed methods to effectively and accurately find the MCDs to generate a collision-free motion for the HRP-2 humanoid robot.

We present a robotic pen-drawing system that is capable of faithfully reproducing pen art on an unknown surface. Our robotic system relies on an industrial, seven-degree-of freedom manipulator that can be both position- and impedance-controlled. In order to estimate a rough geometry of the target, continuous surface, we first generate a point cloud of the surface using an RGB-D camera, which is filtered to remove outliers and calibrated to the physical canvas surface. Then, our control algorithm physically reproduces digital drawing on the surface by impedance-controlling the manipulator. Our impedance-controlled drawing algorithm compensates for the uncertainty and incompleteness inherent to a point-cloud estimation of the drawing surface. Moreover, since drawing 2D vector pen art on a 3D surface requires surface parameterization that does not destroy the original 2D drawing, we rely on the least squares conformal mapping. Specifically, the conformal map reduces angle distortion during surface parameterization. As a result, our system can create distortion-free and complicated pen drawings on general surfaces with many unpredictable bumps robustly and faithfully.

In this paper, we propose a novel penetration metric, called deformable penetration depth PDd, to define a measure of inter-penetration between two linearly deforming tetrahedra using the object norm [1]. First of all, we show that a distance metric for a tetrahedron deforming between two configurations can be found in closed form based on object norm. Then, we show that the PDdbetween an intersecting pair of static and deforming tetrahedra can be found by solving a quadratic programming (QP) problem in terms of the distance metric with non-penetration constraints. We also show that the PDdbetween two, intersected, deforming tetrahedra can be found by solving a similar QP problem under some assumption on penetrating directions, and it can be also accelerated by an order of magnitude using pre-calculated penetration direction. We have implemented our algorithm on a standard PC platform using an off-the-shelf QP optimizer, and experimentally show that both the static/deformable and deformable/deformable tetrahedra cases can be solvable in from a few to tens of milliseconds. Finally, we demonstrate that our penetration metric is three-times smaller (or tighter) than the classical, rigid penetration depth metric in our experiments.

We present a semi-autonomous robotic pen-drawing system that is capable of creating pen art on an arbitrary surface with varying thickness of pen strokes but without reconstructing the surface explicitly. Our robotic system relies on an industrial, seven-degree-of-freedom (7DoF) manipulator that can be both position- and impedance-controlled. We use a vector-graphics engine to take an artist's pen drawing as input and generate Bézier spline curves with varying offsets. In order to estimate geometric details of the target, unknown surface, during drawing, we rely on incremental and adaptive sampling on the surface using a combination of position and impedance control. Then, our control algorithm physically replicates this drawing on any arbitrary, continuous surface by impedance-controlling the manipulator. We demonstrate that our system can create visually-pleasing and complicated artistic pen drawings on general surfaces without explicit surface-reconstruction nor visual feedback.

Abstract With virtual reality, digital painting on 2D canvas is now being extended to 3D space. In this paper, we generalize the 2D pixel canvas to a 3D voxel canvas to allow artists to synthesize volumetric color fields. We develop a deep and dynamic octree‐based painting and rendering system using both CPU and GPU to take advantage of the characteristics of both processors (CPU for octree modeling and GPU for volume rendering). On the CPU‐side, we dynamically adjust an octree and incrementally update the octree to GPU with low latency without compromising the frame rates of the rendering. Our octree is balanced and uses a novel 3‐neighbor connectivity for format simplicity and efficient storage, while allowing constant neighbor access time in ray casting. To further reduce the GPU‐side 3‐neighbor computations, we precompute a culling mask in CPU and upload it to GPU. Finally, we analyze the numerical error‐propagation in ray casting through high resolution octree and present a theoretical error bound.

The cover image, by Yaesol Kim et al., is based on the Special Issue Paper Encountered-type Haptic Display for Large VR Environment using Per-plane Reachability Maps, https://doi.org/10.1002/cav.1814.

Abstract We show a novel encountered‐type haptic system, H‐Wall, to enable haptic feedback using a manipulator of seven degrees of freedom suitable for simulating indoor virtual reality environments, which are characterized and confined by a set of vertical walls and revolving doors. At runtime, our system tracks hand motion using a red–green–blue depth sensor and locates its configuration. Then, the robotic manipulator plans a trajectory for the end effector, attached to a rectangular rigid board, to make contact with the hand to deliver a sense of touch as long as the perceived hand contact force is substantial. The force feedback is generated in a passive sense for static walls that the rigid board, corresponding to a vertical wall, holds its position as long as the perceived hand contact force is substantial. For a revolving door, the force feedback is generated in an active sense based on impedance control. In order to address the issue of limited workspace, we also propose a new reachability map, calledper‐plane reachability map, that is optimized to answer whether passive haptic feedback can be generated by a manipulator when the user touches a vertical wall at a given orientation. We successfully demonstrate our system to provide an illusion to the user in a virtual environment with touch sensation to the surrounding environment.

Abstract In this paper, an effective, interactive grasping algorithm is proposed to provide physically realistic interactions in the virtual world. We have provided a solution to lacking dynamic control resulting in penetrations and frictionless contact due to kinematic virtual hand provided by hand‐tracking devices, by including a proxy hand in the system. The introduced proxy hand not only provides correct visual feedback but also is used to simulate dynamics between the hand and virtual objects. Our method also provides semiautonomous assistive grasping, coupled with physics‐based grasping, which makes the system help the user in achieving a grasp by identifying grasp pose and orienting the object in the hand to be grasped robustly. We have implemented and evaluated our technique with various benchmarks, conducted a user study to compare our method against the state‐of‐the‐art, pinch‐based grasping mechanism, and showed that our technique provides physically realistic, stable, and time‐efficient real‐time interactions.

Abstract We present a novel, compact bounding volume hierarchy, TSS BVH, for ray tracing subdivision surfaces computed by the Catmull‐Clark scheme. We use Tetrahedron Swept Sphere (TSS) as a bounding volume to tightly bound limit surfaces of such subdivision surfaces given a user tolerance. Geometric coordinates defining our TSS bounding volumes are implicitly computed from the subdivided mesh via a simple vertex ordering method, and each level of our TSS BVH is associated with a single distance bound, utilizing the Catmull‐Clark scheme. These features result in a linear space complexity as a function of the tree depth, while many prior BVHs have exponential space complexity. We have tested our method against different benchmarks with path tracing and photon mapping. We found that our method achieves up to two orders of magnitude of memory reduction with a high culling ratio over the prior AABB BVH methods, when we represent models with two to four subdivision levels. Overall, our method achieves three times performance improvement thanks to these results. These results are acquired by our theorem that rigorously computes our TSS bounding volumes.

We present a novel algorithm to compute a gradient-continuous penetration depth (PhongPD) between two interpenetrated polygonal models. Our penetration depth (PD) formulation ensures separating the intersected models by translation, and the amount of such translation is close to an optimal motion to resolve interpenetration in most cases. In order to achieve the gradient-continuity in our algorithm, we interpolate tangent planes continuously over the contact space and then perform a projection along a normal direction defined by the interpolated tangent planes; this projection scheme is known as Phong projection. We have implemented our PhongPD algorithm and certifies its continuity using three benchmarks consisting of diverse combinatorial complexities, and show that our algorithm shows smoother PD results than a conventional Euclidean-projection-based PD method.

We present a new hybrid approach to computing penetration depth (PD) for general polygonal models. Our approach exploits both local and global approaches to PD computation and can compute error-bounded PD approximations for both deep and shallow penetrations. We use a two-step formulation: the first step corresponds to a global approximation approach that samples the configuration space with bounded error using support vector machines; the second step corresponds to a local optimization that performs a projection operation refining the penetration depth. We have implemented this hybrid algorithm on a standard PC platform and tested its performance with various benchmarks. The experimental results show that our algorithm offers significant benefits over previously developed local-only and global-only methods used to compute the PD.

We present a novel, real-time algorithm to accurately approximate the generalized penetration depth ( PD g ) between two overlapping rigid or articulated models. Given the high complexity of computing PD g , our algorithm approximates PD g based on iterative, constrained optimization on the contact space, defined by the overlapping objects. The main ingredient of our algorithm is a novel and general formulation of distance metric, the object norm , in a configuration space for articulated models, and a compact closed-form solution for it. Then, we perform constrained optimization, by linearizing the contact constraint, and minimizing the object norm under such a constraint. In practice, our algorithm can compute locally optimal PD g for rigid or articulated models consisting of tens of thousands of triangles in tens of milliseconds. We also suggest three applications using PD g computation: retraction-based motion planning, physically-based animation, and data-driven grasping.

Most techniques for real-time construction of a signed distance field, whether on a CPU or GPU, involve approximate distances. We use a GPU to build an exact adaptive distance field, constructed from an octree by using the Morton code. We use rectangle-swept spheres to construct a bounding volume hierarchy (BVH) around a triangulated model. To speed up BVH construction, we can use a multi-BVH structure to improve the workload balance between GPU processors. An upper bound on distance to the model provided by the octree itself allows us to reduce the number of BVHs involved in determining the distances from the centers of octree nodes at successively lower levels, prior to an exact distance query involving the remaining BVHs. Distance fields can be constructed 35-64 times as fast as a serial CPU implementation of a similar algorithm, allowing us to simulate a piece of fabric interacting with the Stanford Bunny at 20 frames per second.

We present fast CCD algorithm for general rigid and articulated models based on conservative advancement. We have implemented the CCD algorithm with two different acceleration techniques which can handle rigid models, and have extended one of them to articulated models. The resulting algorithms take a few milliseconds for rigid models with tens of thousands of triangles, and a few milliseconds for articulated models with tens of links. We show that the performance of our algorithms is much faster than existing CCD algorithms for polygon-soup models and it is also comparable to competing CCD algorithms that are limited to manifold models.

We present a new parallel algorithm for collision detection using many-core computing platforms of CPUs or GPUs. Based on the notion of a $(p)$-partition front, our algorithm is able to evenly partition and distribute the workload of BVH traversal among multiple processing cores without the need for dynamic balancing, while minimizing the memory overhead inherent to the state-of-the-art parallel collision detection algorithms. We demonstrate the scalability of our algorithm on different benchmarking scenarios with and without using temporal coherence, including dynamic simulation of rigid bodies, cloth simulation, and random collision courses. In these experiments, we observe nearly linear performance improvement in terms of the number of processing cores on the CPUs and GPUs.

We present six-degree-of-freedom (6DoF) haptic rendering algorithms using translational (PDt) and generalized penetration depth (PDg). Our rendering algorithm can handle any type of object/object haptic interaction using penalty-based response and makes no assumption about the underlying geometry and topology. Moreover, our rendering algorithm can effectively deal with multiple contacts. Our penetration depth algorithms for PDtand PDgare based on a contact-space projection technique combined with iterative, local optimization on the contact-space. We circumvent the local minima problem, imposed by the local optimization, using motion coherence present in the haptic simulation. Our experimental results show that our methods can produce high-fidelity force feedback for general polygonal models consisting of tens of thousands of triangles at near-haptic rates, and are successfully integrated into an off-the-shelf 6DoF haptic device. We also discuss the benefits of using different formulations of penetration depth in the context of 6DoF haptics.

We present a novel GPU-based parallel algorithm to solve continuous-state POMDP problems. We choose the MCVI (Monte Carlo Value Iteration) method as our base algorithm [1], and parallelize this algorithm using multi-level parallel formulation of MCVI. For each parallel level, we propose efficient algorithms to effectively utilize the massive data parallelism of GPUs. To obtain the maximum parallel performance at highest level, we introduce two workload distribution techniques such as data/compute interleaving and workload balancing. To the best of our knowledge, our algorithm is the first parallel algorithm that executes POMDP efficiently on GPUs. Our GPU-based algorithm outperforms the existing CPU-based algorithm by a factor of 75~90 on different benchmarks.

In this paper we introduce a new bounding box method for footstep planning for humanoid robots. Similar to the classic bounding box method (which uses a single rectangular box to encompass the robot) it is computationally efficient, easy to implement and can be combined with any rigid body motion planning library. However, unlike the classic bounding box method, our method takes into account the stepping over capabilities of the robot, and generates precise leg trajectories to avoid obstacles on the ground. We demonstrate that this method is well suited for footstep planning in cluttered environments.

We present a new bounding volume structure, k-IOS that is an intersection of k spheres, for accelerating proximity query including collision detection and Euclidean distance computation between arbitrary polygon-soup models that undergo rigid motion. Our new bounding volume is easy to implement and highly efficient both for its construction and runtime query. In our experiments, we have observed up to 4.0 times performance improvement of proximity query compared to an existing well-known algorithm based on swept sphere volume (SSV) [1]. Moreover, k-IOS is strictly convex that can guarantee a continuous gradient of distance function with respect to object's configuration parameter.

We propose three novel methods to evaluate a distance function for robotic motion planning based on semiinfinite programming (SIP) framework; these methods include golden section search (GSS), conservative advancement (CA) and a hybrid of GSS and CA. The distance function can have a positive and a negative value, each of which corresponds to the Euclidean distance and penetration depth, respectively. In our approach, each robot's link is approximated and bounded by a capsule shape, and the distance between some selected link pairs is continuously evaluated along the joint's trajectory, provided by the SIP solver, and the global minimum distance is found. This distance is fed into the SIP solver, which subsequently suggests a new trajectory. This process is iterated until no negative distance is found anywhere in the links of the robot.We have implemented the three distance evaluation methods, and experimentally validated that the proposed methods effectively and accurately find the global minimum distances to generate a self-collision-free motion for the HRP-2 humanoid robot. Moreover, we demonstrate that the hybrid method outperforms other two methods in terms of computational speed and reliability.

ABSTRACT We present an efficient, user‐guided volumetric approximation algorithm, specifically designed for physically based animation. Our method combines automatic and interactive segmentation methods to give users an intuitive and easy way to approximate 3D meshes. Our approach first constructs the simplified medial axis transform of the input mesh object, and segments the medial axis into parts in terms of swept sphere volumes using a region growing method. Then, we decompose the object surface into regions based on the mapping between the segmented medial axis and the object surface. Each segmented region is approximated with a swept sphere volume. These decomposed surface regions can be interactively refined further by splitting and/or merging using a sketch‐based input. Experimental results show that our approach produces good volumetric approximation results for different types of object shapes. Moreover, rigid‐body dynamics simulation based on our volumetric approximation provides a visually pleasing result. Copyright © 2012 John Wiley & Sons, Ltd.

We present a real-time algorithm that finds the Penetration Depth (PD) between general polygonal models based on iterative and local optimization techniques. Given an in-collision configuration of an object in configuration space, we find an initial collision-free configuration using several methods such as centroid difference, maximally clear configuration, motion coherence, random configuration, and sampling-based search. We project this configuration on to a local contact space using a variant of continuous collision detection algorithm and construct a linear convex cone around the projected configuration. We then formulate a new projection of the in-collision configuration onto the convex cone as a Linear Complementarity Problem (LCP), which we solve using a type of Gauss-Seidel iterative algorithm. We repeat this procedure until a locally optimal PD is obtained. Our algorithm can process complicated models consisting of tens of thousands triangles at interactive rates.

We present a simple and efficient approach for continuous collision detection of deforming triangles based on conservative advancement. The efficiency of our approach is due to a sequence of simple collision-free conditions for deforming triangles. In our experiment, we show that our CCD algorithm achieves 2-30 times performance improvement over existing algorithms for triangle primitives.

We present a novel algorithm to perform continuous collision detection(CCD) between non-rigid, deformable models using local advancement. Given the initial and final configurations of a deformable model, our algorithm computes linear deformation by interpolating the vertices from the initial to the final configurations with a straight line path and checks for collision along that path. Our approach is applicable to polygon-soup models with arbitrary topology, handles self-collisions and makes no assumption about the underlying non-rigid motion. We accelerate the algorithm by computing motion bounds on the primitives and their bounding volumes. These bounds are combined with hierarchical culling techniques and used for fast collision checking. In practice, we have observed up to four times improvement in running time because of local advancement.

This course is intended for instructing students and practitioners on recent developments related to collision and proximity computations for interactive games and simulations.

Abstract We present simple and fast parallel proximity algorithms for rigid polygonal models. Given two polygon‐soup models in space, if they overlap, our algorithm can find all the intersected primitives between them; otherwise, it reports their Euclidean minimum distance. Our algorithm is performed in a parallel fashion and shows scalable performance in terms of the number of available computing cores. The key ingredient of our algorithm is a simple load‐balancing metric based on the penetration depth (PD) (for collision detection) and approximate Euclidean distance (for Euclidean distance computation) between bounding volumes. To compute the PD between oriented bounding boxes (OBBs), we present a novel algorithm based on the well‐known separating axis theorem (SAT) and also shows that the PD can be trivially obtained as a byproduct of SAT. We have implemented these algorithms on a commodity PC with eight cores and benchmarked their performance on complicated geometric models. In practice, the performance of our algorithm shows up to 5 and 9.7 times improvement for collision and distance queries, respectively, compared to single core computation. Copyright © 2010 John Wiley & Sons, Ltd.

We cull collisions between very large numbers of moving bodies using graphics processing units (GPUs). To perform massively parallel sweep-and-prune (SaP), we mitigate the great density of intervals along the axis of sweep by using principal component analysis to choose the best sweep direction, together with spatial subdivisions to further reduce the number of false positive overlaps. Our algorithm implemented entirely on GPUs using the CUDA framework can handle a million moving objects at interactive rates. As application of our algorithm, we demonstrate the real-time simulation of very large numbers of particles and rigid-body dynamics.

We present a simple and fast algorithm to perform continuous collision detection between polygonal models undergoing rigid motion for interactive applications. Our approach can handle all triangulated models and makes no assumption about the underlying geometry and topology. The algorithm uses the notion of conservative advancement (CA), originally developed for convex polytopes. We extend this formulation to general models using swept sphere volume hierarchy and present a compact formulation to compute the motion bounds along with a novel controlling scheme. We have implemented the algorithm and highlight its performance on various benchmarks. In practice, our algorithm can perform continuous collision queries in few milli-seconds on models composed of tens of thousands of triangles.

We present a simple algorithm to generate a topology-preserving, error-bounded approximation of the outer boundary of the volume swept by a polyhedron along a parametric trajectory. Our approach uses a volumetric method that generates an adaptive volumetric grid, computes signed distance on the grid points, and extracts an isosurface from the distance field. In order to guarantee geometric and topological bounds, we present a novel sampling and front propagation algorithm for adaptive grid generation. We highlight the performance of our algorithm on many complex benchmarks that arise in geometric and solid modeling, motion planning and CNC milling applications. To the best of our knowledge, this is the first practical algorithm that can generate swept volume approximations with geometric and topological guarantees on complex polyhedral models swept along any parametric trajectory.

Abstract The standard C/C++ implementation of a spatial partitioning data structure, such as octree and quadtree, is often inefficient in terms of storage requirements particularly when the memory overhead for maintaining parent‐to‐child pointers is significant with respect to the amount of actual data in each tree node. In this work, we present a novel data structure that implements uniform spatial partitioning without storing explicit parent‐to‐child pointer links. Our linkless tree encodes the storage locations of subdivided nodes using perfect hashing while retaining important properties of uniform spatial partitioning trees, such as coarse‐to‐fine hierarchical representation, efficient storage usage, and efficient random accessibility. We demonstrate the performance of our linkless trees using image compression and path planning examples.

We present a simple algorithm to compute the Hausdorff distance between complicated, polygonal models at interactive rates. The algorithm requires no assumptions about the underlying topology and geometry. To avoid the high computational and implementation complexity of exact Hausdorff distance calculation, we approximate the Hausdorff distance within a user-specified error bound. The main ingredient of our approximation algorithm is a novel polygon subdivision scheme, calledVoronoi subdivision, combined with culling between the models based on bounding volume hierarchy (BVH). Thiscross-cullingmethod relies on tight yet simple computation of bounds on the Hausdorff distance, and it discards unnecessary polygon pairs from each of the input models alternatively based on the distance bounds. This algorithm can approximate the Hausdorff distance between polygonal models consisting of tens of thousands triangles with a small error bound in real-time, and outperforms the existing algorithm by more than an order of magnitude. We apply our Hausdorff distance algorithm to the measurement of shape similarity, and the computation of penetration depth for physically-based animation. In particular, the penetration depth computation using Hausdorff distance runs at highly interactive rates for complicated dynamics scene.

Abstract We propose a method for view‐dependent simplification of articulated‐body dynamics, which enables an automatic trade‐off between visual precision and computational efficiency. We begin by discussing the problem of simplifying the simulation based on visual criteria, and show that it raises a number of challenging questions. We then focus on articulated‐body dynamics simulation, and propose a semi‐predictive approach which relies on a combination of exact, a priori error metrics computations, and visibility estimations. We suggest several variants of semi‐predictive metrics based on hierarchical data structures and the use of graphics hardware, and discuss their relative merits in terms of computational efficiency and precision. Finally, we present several benchmarks and demonstrate how our view‐dependent articulated‐body dynamics method allows an animator (or a physics engine) to finely tune the visual quality and obtain potentially significant speed‐ups during interactive or off‐line simulations. Copyright © 2008 John Wiley & Sons, Ltd.

We present an efficient algorithm for complete motion planning that combines approximate cell decomposition (ACD) with probabilistic roadmaps (PRM). Our approach uses ACD to subdivide the configuration space into cells and computes localized roadmaps by generating samples within these cells. We augment the connectivity graph for adjacent cells in ACD with pseudo-free edges that are computed based on localized roadmaps. These roadmaps are used to capture the connectivity of free space and guide the adaptive subdivision algorithm. At the same time, we use cell decomposition to check for path non-existence and generate samples in narrow passages. Overall, our hybrid algorithm combines the efficiency of PRM methods with the completeness of ACD-based algorithms. We have implemented our algorithm on 3-DOF and 4-DOF robots. We demonstrate its performance on planning scenarios with narrow passages or no collision-free paths. In practice, we observe up to 10 times improvement in performance over prior complete motion planning algorithms.

The problem of distance computation arises in many applications including motion planning, CAD/CAM, dynamic simulation and virtual environments. Most prior work in this area has been restricted to separation or penetration distance computation between two objects. In this paper, we address the problem of computing a measure of distance between two configurations of a rigid or articulated model. The underlying distance metric is defined as the length of the longest displacement vector over the corresponding vertices of the model between two configurations. Our algorithm is based on Chasles theorem in Screw theory, and we show that the maximum distance can be realized only by a vertex of the convex hull of a rigid object. We use this formulation to compute the distance, and present two acceleration techniques to speed up the computation: incremental walking on the dual space of the convex hull and culling vertices on the convex hull using a bounding volume hierarchy (BVH). Our algorithm can be easily extended to articulated models by maximizing the distance over its each link and we also present culling techniques to accelerate the computation. We highlight the performance of our algorithm on many complex models and describe its application to proximity queries and motion planning.

We present a fast continuous collision detection (CCD) algorithm for articulated models using Taylor models and temporal culling. Our algorithm is a generalization of conservative advancement (CA) from convex models [Mirtich 1996] to articulated models with non-convex links. Given the initial and final configurations of a moving articulated model, our algorithm creates a continuous motion with constant translational and rotational velocities for each link, and checks for interferences between the articulated model under continuous motion and other models in the environment and for self-collisions. If collisions occur, our algorithm reports the first time of contact (TOC) as well as collision witness features . We have implemented our CCD algorithm and applied it to several challenging scenarios including locomotion generation, articulated-body dynamics and character motion planning. Our algorithm can perform CCDs including self-collision detection for articulated models consisting of many links and tens of thousands of triangles in 1.22 ms on average running on a 3.6 GHz Pentium 4 PC. This is an improvement on the performance of prior algorithms of more than an order of magnitude.

We present an interactive and accurate collision detection algorithm for deformable, polygonal objects based on the streaming computational model. Our algorithm can detect all possible pairwise primitive-level intersections between two severely deforming models at highly interactive rates. In our streaming computational model, we consider a set of axis aligned bounding boxes (AABBs) that bound each of the given deformable objects as an input stream and perform massively-parallel pairwise, overlapping tests onto the incoming streams. As a result, we are able to prevent performance stalls in the streaming pipeline that can be caused by expensive indexing mechanism required by bounding volume hierarchy-based streaming algorithms. At runtime, as the underlying models deform over time, we employ a novel, streaming algorithm to update the geometric changes in the AABB streams. Moreover, in order to get only the computed result (i.e., collision results between AABBs) without reading back the entire output streams, we propose a streaming en/decoding strategy that can be performed in a hierarchical fashion. After determining overlapped AABBs, we perform a primitive-level (e.g., triangle) intersection checking on a serial computational model such as CPUs. We implemented the entire pipeline of our algorithm using off-the-shelf graphics processors (GPUs), such as nVIDIA GeForce 7800 GTX, for streaming computations, and Intel Dual Core 3.4G processors for serial computations. We benchmarked our algorithm with different models of varying complexities, ranging from 15K up to 50K triangles, under various deformation motions, and the timings were obtained as 30 approximately 100 FPS depending on the complexity of models and their relative configurations. Finally, we made comparisons with a well-known GPU-based collision detection algorithm, CULLIDE [4] and observed about three times performance improvement over the earlier approach. We also made comparisons with a SW-based AABB culling algorithm [2] and observed about two times improvement.

We present a simple algorithm for approximating the free configuration space of robots with low degrees of freedom (DOFs). We represent the free space as an arrangement of contact surfaces. We approximate the free space using an adaptive volumetric grid that is computed by performing simple geometric tests on the contact surfaces. We use an isosurface extraction algorithm to compute a piecewise-linear approximation to the boundary of the free space. We prove that our approximation is topologically equivalent to the exact free space boundary. We also ensure that our approximation is geometrically close to the exact free space boundary by bounding its two-sided Hausdorff error. We have applied our algorithm to compute the free configuration space for the following instances: (1) a 2D polygonal robot with translational and rotational DOFs navigating among polygonal obstacles, and (2) a 3D polyhedral robot translating among polyhedral obstacles. In practice, our algorithm works well on robots with three DOFs

The configuration space of a robot is partitioned into free space and C-obstacle space. Most of the prior work in collision detection and motion planning algorithms is targeted towards checking whether a configuration or a 1D path lies in the free space. In this paper, we address the problem of checking whether a C-space primitive or a spatial cell lies completely inside C-obstacle space, without explicitly computing the boundary of C-obstacle. We refer to the problem as the C-obstacle query. We present a fast and conservative algorithm to perform this C-obstacle query. Our algorithm uses the notion of generalized penetration depth that takes into account both translational and rotational motion. We compute the generalized penetration depth for polyhedral objects and compare it with the extent of the motion that the polyhedral robot can undergo. Our approach is general and useful for designing practical algorithms for complete motion planning of rigid robots. We have integrated our query computation algorithm with star-shaped roadmaps (G. Varadhan and D. Manocha, 2005) - a deterministic sampling approach for complete motion planning. We have applied our modified planning algorithm to planar robots undergoing translational and rotational motion in complex 2D environments. Our algorithm is able to perform the C-obstacle query in milliseconds and improves the performance of the complete motion planning algorithm

Penetration depth (PD) is a distance metric that is used to describe the extent of overlap between two intersecting objects. Most of the prior work in PD computation has been restricted to translational PD, which is defined as the minimal translational motion that one of the overlapping objects must undergo in order to make the two objects disjoint. In this paper, we extend the notion of PD to take into account both translational and rotational motion to separate the intersecting objects, namely generalized PD. When an object undergoes rigid transformation, some point on the object traces the longest trajectory. The generalized PD between two overlapping objects is defined as the minimum of the longest trajectories of one object under all possible rigid transformations to separate the overlapping objects.We present three new results to compute generalized PD between polyhedral models. First, we show that for two overlapping convex polytopes, the generalized PD is same as the translational PD. Second, when the complement of one of the objects is convex, we pose the generalized PD computation as a variant of the convex containment problem and compute an upper bound using optimization techniques. Finally, when both the objects are non-convex, we treat them as a combination of the above two cases, and present an algorithm that computes a lower and an upper bound on generalized PD. We highlight the performance of our algorithms on different models that undergo rigid motion in the 6-dimensional configuration space. Moreover, we utilize our algorithm for complete motion planning of polygonal robots undergoing translational and rotational motion in a plane. In particular, we use generalized PD computation for checking path non-existence.

This paper presents an effective approach to generate a set of small textures from an input texture that can be tiled together to synthesize large textures. Such a small set can be useful in texturing any large area realistically and efficiently while consuming only a small amount of texture memory. Our approach is advantageous in its ability to generate a smaller number of tiles that can embed much more texture patterns and with less conspicuous seams within each tile than earlier approaches. As a result, our approach can generate large textures that look as if each were from a continuous part of the input texture while avoiding highly repetitive patterns. In general, our approach performs very well and shows a particular strength, compared to earlier approaches, for input textures of elaborate or relatively large features, or with distinctive colors.

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.

No abstract available.

We present improved subdivision and isosurface reconstruction algorithms for polygonizing implicit surfaces and performing accurate geometric operations. Our improved reconstruction algorithm uses directed distance fields (Kobbelt et al., 2001) to detect multiple intersections along an edge, separates them into components and reconstructs an isosurface locally within each components using the dual contouring algorithm (Ju et al., 2002). It can reconstruct thin features without creating handles and results in improved surface extraction from volumetric data. Our subdivision algorithm takes into account sharp features that arise from intersecting surfaces or Boolean operations and generates an adaptive grid such that each voxel has at most one sharp feature. The subdivision algorithm is combined with our improved reconstruction algorithm to compute accurate polygonization of Boolean combinations or offsets of complex primitives that faithfully reconstruct the sharp features. We have applied these algorithms to polygonize complex CAD models designed using thousands of Boolean operations on curved primitives.

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.