%%% %%% PhD Thesis %%% @phdthesis{l-efdar-93 , author = "M. C. Lin" , title = "Efficient Collision Detection for Animation and Robotics" , type = "Ph.{D}. Thesis" , school = "Dept. Elec. Engin. Comput. Sci., Univ. California" , address = "Berkeley, CA" , year = 1993 , keywords = "doctoral thesis" , update = "96.05 klosowski" } @phdthesis{m-ibdsrbs-96 , author = "B. Mirtich" , title = "Impulse-based Dynamic Simulation of Rigid Body Systems" , type = "Ph.{D}. Thesis" , school = "Dept. Elec. Engin. Comput. Sci., Univ. California" , address = "Berkeley, CA" , year = 1996 , update = "98.04 Li" } @phdthesis{h-cdiga-94 , author = "P.M. Hubbard" , title = "Collision Detection for Interactive Graphics Applications" , type = "Ph.{D}. Thesis" , school = "Dept. Comput. Sci., Brown Univ." , year = 1994 , update = "98.04 Li" } @phdthesis{q-rtmcfp-94 , author = "S. Quinlan" , title = "The Real-Time Modification of Collision-Free Paths" , type = "Ph.{D}. Thesis" , school = "Dept. Comput. Sci., Stanford Univ." , address = "Palo Alto, CA" , year = 1994 , update = "98.04 Li" } %%% %%% Papers %%% @article{c-cdmp-86 , author = "John Canny" , title = "Collision Detection for Moving Polyhedra" , journal = "IEEE Trans. Pattern Anal. Mach. Intell." , volume = "PAMI-8" , number = 2 , year = 1986 , pages = "200--209" , update = "95.01 mitchell" } @article{gjk-fpcdb-88 , author = "E. G. Gilbert and D. W. Johnson and S. S. Keerthi" , title = "A fast procedure for computing the distance between complex objects" , journal = "IEEE Journal of Robotics and Automation" , volume = 4 , number = 2 , year = 1988 } @inproceedings{w-cdmpp-89 , author = "C. A. Wang" , title = "Collision detection of a moving polygon in the presence of polygonal obstacles in the plane" , booktitle = "Abstracts 1st Canad. Conf. Comput. Geom." , year = 1989 , pages = 35 } @inproceedings{dk-dsppu-90 , author = "D. P. Dobkin and D. G. Kirkpatrick" , title = "Determining the separation of preprocessed polyhedra -- {A} unified approach" , booktitle = "Proc. 17th Internat. Colloq. Automata Lang. Program." , series = "Lecture Notes Comput. Sci." , volume = 443 , publisher = "Springer-Verlag" , year = 1990 , pages = "400--413" , update = "97.07 agarwal" } @inproceedings{lc-eaidc-91 , author = "M. C. Lin and J. F. Canny" , title = "A fast algorithm for incremental distance calculation" , booktitle = "Proc. IEEE Internat. Conf. Robot. Autom." , volume = 2 , year = 1991 , pages = "1008--1014" , update = "96.05 klosowski" } @article{dhks-cidp-93 , author = "D. Dobkin and J. Hershberger and D. Kirkpatrick and S. Suri" , title = "Computing the intersection-depth of polyhedra" , journal = "Algorithmica" , volume = 9 , year = 1993 , pages = "518--533" , update = "96.05 ramkumar" } @InCollection{Rabbitz:1994:FCD, author = "Rich Rabbitz", editor = "Paul Heckbert", booktitle = "Graphics Gems IV", title = "Fast Collision Detection of Moving Convex Polyhedra", publisher = "Academic Press", address = "Boston", pages = "83--109", year = "1994", keywords = "animation, collision detection, computational geometry, polyhedron", summary = "A turn-key piece of software that solves a difficult but basic problem in physically based animation and interactive modeling. Contains C code.", bibsource = "sig-11-1994", } @inproceedings{st-ecdmp-95 , author = "Elmar Sch{\"o}mer and Christian Thiel" , title = "Efficient Collision Detection for Moving Polyhedra" , booktitle = "Proc. 11th Annu. ACM Sympos. Comput. Geom." , year = 1995 , pages = "51--60" , keywords = "intersection detection, linearization, range queries, parametric search, Plucker coordinates" , update = "95.09 mitchell" } @article{gjs-facpp-96 , author = "P. Gupta and R. Janardan and M. Smid" , title = "Fast algorithms for collision and proximity problems involving moving geometric objects" , journal = "Comput. Geom. Theory Appl." , volume = 6 , year = 1996 , pages = "371--391" , succeeds = "gjs-facpp-94i" , update = "97.03 devillers+smid" } @incollection{lm-idbco-93 , author = "M. C. Lin and D. Manocha" , title = "Interference Detection Between Curved Objects for Computer Animation" , booktitle = "Models and Techniques in Computer Animation" , publisher = "Springer-Verlag" , year = 1993 , pages = "43--57" , update = "96.05 klosowski" } @article{lm-fidgm-95 , author = "M. C. Lin and D. Manocha" , title = "Fast Interference Detection Between Geometric Models" , journal = "Visual Comput." , volume = 11 , number = 10 , year = 1995 , pages = "542--561" , update = "96.05 held+klosowski" } @inproceedings{clmp-iciec-95 , author = "J. D. Cohen and M. C. Lin and D. Manocha and M. K. Ponamgi" , title = "I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments" , booktitle = "Proc. ACM Interactive 3D Graphics Conf." , year = 1995 , pages = "189--196" , succeeds = "clmp-iecdl-94" , update = "96.05 klosowski, 96.01 held" } @inproceedings{pml-iacdb-95 , author = "M. K. Ponamgi and D. Manocha and M. C. Lin" , title = "Incremental Algorithms for Collision Detection between General Solid Models" , booktitle = "Proc. ACM Siggraph Sympos. Solid Modeling" , year = 1995 , pages = "293--304" , succeeds = "pml-iacdb-94" , update = "96.05 klosowski, 96.01 held" } @article{glm-othsr-96 , author = "S. Gottschalk and M. C. Lin and D. Manocha" , title = "{OBB}-Tree: {A} Hierarchical Structure for Rapid Interference Detection" , journal = "Comput. Graph." , volume = "??" , year = 1996 , note = "Proc. SIGGRAPH '96" , keywords = "collision detection" , comments = "To Appear" , update = "96.09 devillers, 96.05 klosowski" } @article{lm-ecdde--97 , author = "M. Lin and D. Manocha" , title = "Efficient Contact Determination in Dynamic Environments" , journal = "Internat. J. Comput. Geom. Appl." , volume = 7 , year = 1997 , pages = "123--151" , update = "97.07 devillers" } @inproceedings{kplm-sshob-98 , author = "S. Krishnan and A. Pattekar and M. Lin and D. Manocha" , title = "Spherical Shell: A Higher Order Bounding Volume for Fast Proximity Queries" , booktitle = "Proc. WAFR'98" , year = 1998 } @inproceedings{kglmp-racds-98 , author = "S. Krishnan and M. Gopi and M. Lin and D. Manocha and A. Pattekar" , title = " Rapid and accurate contact determination between spline models using ShellTrees" , booktitle = "Eurographics'98" , year = 1998 } @InProceedings{Hudson:1997:VCA, author = "Thomas C. Hudson and Ming C. Lin and Jonathan Cohen and Stefan Gottschalk and Dinesh Manocha", title = "{V}-{COLLIDE}: Accelerated Collision Detection for {VRML}", booktitle = "VRML 97: Second Symposium on the Virtual Reality Modeling Language", editor = "Rikk Carey and Paul Strauss", year = "1997", organization = "ACM SIGGRAPH / ACM SIGCOMM", publisher = "ACM Press", address = "New York City, NY", month = feb, note = "ISBN 0-89791-886-x", keywords = "virtual reality modeling language, VRML, collision detection", annote = "Collision detection is essential for many applications involving simulation, behavior and animation. However, it has been regarded as a computationally demanding task and is often treated as an advanced feature. Most commonly used commercial CAD/CAM packages and high performance graphics libraries, such as SGI Performer, provide limited support for collision detection. As users continue to stretch the capabilities of VRML, collision detection will soon become an indispensable capability for many applications. In this paper, we present a system for accelerated and robust collision detection and describe its interface to VRML browsers. We demonstrate that it is possible to perform accurate collision detection at interactive rates in VRML environments composed of large numbers of complex moving objects.", } @Article{Ponamgi:1997:IAC, author = "Madhav K. Ponamgi and Dinesh Manocha and Ming C. Lin", title = "Incremental Algorithms for Collision Detection Between Polygonal Models", journal = "IEEE Transactions on Visualization and Computer Graphics", year = "1997", volume = "3", number = "1", month = jan # "--" # mar, note = "ISSN 1077-2626", keywords = "Collision detection, contacts, interference, dynamic simulation, physically based modeling, convex hulls, hierarchical representation", annote = "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. We 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. We highlight its performance on different applications.", } @inproceedings{bk-rsrcd-88 , author = "S. Bonner and R. B. Kelley" , title = "A representation scheme for rapid 3-d collision detection" , booktitle = "IEEE International Symposium on Intelligent Control" , year = 1988 , pages = "320--325" } @InProceedings{Duff:1992:IAR, author = "Tom Duff", title = "Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry", pages = "131--138", booktitle = "Computer Graphics (SIGGRAPH '92 Proceedings)", volume = "26", year = "1992", month = jul, editor = "Edwin E. Catmull", conference = "held in Chicago, Illinois; 26-31 July 1992", keywords = "antialiasing, compositing, computer-aided animation, recursive subdivision, image synthesis, dynamic simulation, collision detection", annote = "", } @inproceedings{q-edcnc-94 , author = "S. Quinlan" , title = "Efficient distance computation between non-convex objects" , booktitle = "Proceedings f International Conference on Robotics and Automation" , year = 1994 , pages = "3324--3329" } @article{h-cdiga-95 , author = "Philip M. Hubbard" , title = "Collision detection for interactive graphics applications" , journal = "IEEE Trans. Visualization and Computer Graphics" , volume = 1 , number = 3 , month = sep , year = 1995 , pages = "218--230" , keywords = "collision detection, intersection detection, sphere trees" , update = "96.09 devillers, 96.01 mitchell" } @article{h-apstc-96 , author = "P. M. Hubbard" , title = "Approximating Polyhedra with Spheres for Time-Critical Collision Detection" , journal = "ACM Trans. Graph." , volume = 15 , number = 3 , month = jul , year = 1996 , pages = "179--210" , update = "97.03 held" } @Article{Sheehy:1996:SDM, author = "Damian J. Sheehy and Cecil G. Armstrong and Desmond J. Robinson", title = "Shape Description By Medial Surface Construction", journal = "IEEE Transactions on Visualization and Computer Graphics", year = "1996", volume = "2", number = "1", month = mar, pages = "62--72", note = "ISSN 1077-2626", keywords = "Voronoi diagram, medial axis, skeleton, collision detection, mesh generation, feature recognition, solid modeling", annote = "The medial surface is a skeletal abstraction of a solid that provides useful shape infommation, which compliments existing model representation schemes. The medial surface and its associated topological entities are defined, and an algorithm for computing the medial surface of a large class of B-rep solids is then presented. The algorithm is based on the domain Delaunay triangulation of a relatively sparse distribution of points, which are generated on the boundary of the object. This strategy is adaptive in that the boundary point set is refined to guarantee a correct topological representation of the medial surface.", } @inproceedings{c-cdfdint-90 , title = "Collision detection by four-dimensional intersection testing" , author = "S. Cameron" , booktitle = "Proc. IEEE Internat. Conf. Robot. Autom." , year = 1990 , pages = "291--302" } @article{c-ctfac-97 ,title = "A comparison of two fast algorithms for computing the distance between convex polyhedra" ,author = "S. Cameron" ,journal = "IEEE Trans. Robotics and Automation" ,volume = 13 ,year = 1997 , number = 6 , pages = "915--920" } @inproceedings{c-egjk-97 ,title = "Enhancing {GJK}: computing minimum and penetration distances between convex polyhedra" ,author = "S. Cameron" ,booktitle = "ICRA" ,year = 1997 } @inproceedings{c-cdnur-98 ,title = "Computing distances between NURBS-defined convex objects" ,author = "S. Cameron and Colin Turnbull" ,booktitle = "ICRA" ,year = 1998 } @article{hbz-gctdps-90 , title = "Geometric collisions for time-dependent parametric surfaces" , author = "B. V. Herzen and A. H. Barr and H. R. Zatz" , journal = "Computer Graphics" , year = 1990 , volume = 24 , number = 4 , pages = "39-48" } @article{tpf-hmdm-91 , author = "Demetri Terzopoulos and John Platt and Kurt Fleischer" , title = "Heating and melting deformable models" , journal = "Journal of Visualization and Computer Animation" , year = 1991 , volume = 2 , pages = "68--73" } @InProceedings{Snyder:1993:IMM, author = "John M. Snyder and Adam R. Woodbury and Kurt Fleischer and Bena Currin and Alan H. Barr", title = "Interval Method for Multi-point Collision Between Time-dependent Curved Surfaces", booktitle = "Computer Graphics (SIGGRAPH '93 Proceedings)", year = "1993", editor = "James T. Kajiya", pages = "321--334", month = aug, volume = "27", annote = "We present an efficient and robust algorithm for finding points of collision between time-dependent parametric and implicit surfaces. The algorithm detects simultaneous collisions at multiple points of contact. When the regions of contact form curves or surfaces, it returns a finite set of points uniformly distributed over each contact region. Collisions can be computed for a very general class of surfaces: those for which inclusion functions can be constructed. Included in this set are the familiar kinds of surfaces and time behaviors encountered in computer graphics. We use a new interval approach for constrained minimization to detect collisions, and a tangency condition to reduce the dimensionality of the search space. These approaches make interval methods practical for multi-point collisions between complex surfaces. An interval Newton method based on the solution of the interval linear equation is used to speed convergence to the collision time and location. This method is more efficient than the Krawczyk-Moore iteration used previously in computer graphics.", keywords = "Computational Geometry and Object Modeling, Reliability and Robustness, collision detection, parametric surface, constrained minimization, interval analysis, nclusion function, interval Newton method, interval linear equation", } @Article{Liu:1996:CAC, author = "{Jen-Duo} Liu and {Ming-Tat} Ko and {Ruei-Chuan} Chang", title = "Collision avoidance in cloth animation", journal = "The Visual Computer", year = "1996", volume = "12", number = "5", pages = "234--243", note = "ISSN 0178-2789", publisher = "Springer-Verlag", annote = "For cloth modeling and animation, we use a physically based model to simulate the dynamic formation of folds, pleats, and wrinkles and the final static appearance of cloth draped over a rigid object. To simulate the behavior of the cloth and its final static appearance on the model, we propose a new collision and self-collision avoidance method to prevent penetration between the cloth and rigid objects and between parts of the cloth. At each time step, we enforce constraints over those grid points about to penetrate other objects. Our method is easier and more robust than conventional methods at representing interaction between the cloth and various objects.", keywords = "cloth animation, physically based modeling, iteration method, collision detection and avoidance, self-collision", } @Article{Cani-Gascuel:1997:ADM, author = "Marie-Paule Cani-Gascuel and Mathieu Desbrun", title = "Animation of Deformable Models Using Implicit Surfaces", journal = "IEEE Transactions on Visualization and Computer Graphics", year = "1997", volume = "3", number = "1", month = jan # "--" # mar, note = "ISSN 1077-2626", keywords = "Animation, implicit surfaces, deformable models, collision detection, collision response, inelasticity", annote = "This paper presents a general approach for designing and animating complex deformable models with implicit surfaces. Implicit surfaces are introduced as an extra layer coating any kind of structure that moves and deforms over time. Offering a compact definition of a smooth surface around an object, they provide an efficient collision detection mechanism. The implicit layer deforms in order to generate exact contact surfaces between colliding bodies. A simple physically based model approximating elastic behavior is then used for computing collision response. The implicit formulation also eases the control of the object's volume with a new method based on local controllers. We present two different applications that illustrate the benefits of these techniques. First, the animation of simple characters made of articulated skeletons coated with implicit flesh exploits the compactness and enhanced control of the model. The second builds on the specific properties of implicit surfaces for modeling soft inelastic substances capable of separation and fusion that maintain a constant volume when animated.", } @article{mp-gdcpsa , author = "Gavin Miller and Andrew Pearce" , title = "Globular dynamics: a connected particle system for animating viscous fluids" , journal = "Comput. Graphics" , volume = 13 , number = 3 , year = 1989 , pages = "305--309" } @article{l-hsbss-91 , author = "Boris D. Lubachevsky" , title = "How to simulate billiards and similar systems" , journal = "Journal of Computational Physics" , year = 1991 , volume = 94 , pages = "255--283" , keywords = "sphere, elastic collision, dynamics" } @inproceedings{bv-cdapb-91 , author = "W. J. Bouma and G. {Van{\v e}{\v c}ek Jr.}" , title = "Collision Detection and Analysis in a Physically Based Simulation" , booktitle = "Second Eurographics Workshop on Animation and Simulation" , year = 1991 , update = "95.01 mitchell" } @incollection{mc-ibds-95 , author = "B. Mirtich and J. Canny" , title = "Impulse-based dynamic simulation" , editor = "K. Goldberg and D. Halperin and J. C. Latombe and R. Wilson" , booktitle = "The Algorithmic Foundations of Robotics" , publisher = "A. K. Peters" , address = "Boston, MA" , year = 1995 , update = "97.11 bibrelex" } @techreport{m-vclip-97 , author = "B. Mirtich" , title = "{V-Clip}: fast and robust polyhedral collision detection" , type = "Technical {Report}" , number = "TR-97-05" , institution = "Mitsubishi Electrical Research Laboratory" , year = 1997 , update = "98.04 Li" } @article{v-bfcac-94 , author = "G. {Van{\v e}{\v c}ek, Jr.}" , title = "Back-face Culling Applied to Collision Detection of Polyhedra" , journal = "J. Visualizat. and Comput. Animation" , volume = 5 , number = 1 , year = 1994 , update = "97.03 held" } @InProceedings{Barrus:1997:QFM, author = "John W. Barrus and Richard C. Waters", title = "{QOTA}: {A} Fast, Multi-Purpose Algorithm For Terrain Following in Virtual Environments", booktitle = "VRML 97: Second Symposium on the Virtual Reality Modeling Language", editor = "Rikk Carey and Paul Strauss", year = "1997", organization = "ACM SIGGRAPH / ACM SIGCOMM", publisher = "ACM Press", address = "New York City, NY", month = feb, note = "ISBN 0-89791-886-x", keywords = "quadtrees, terrain following, collision detection", annote = "To keep avatars and other moving objects on the ground in virtual environments, it is necessary to find the points where these objects should contact the terrain. This is often done using collision detection; however, this is inefficient, because general collision detection solves a problem that is inherently more complex than merely determining terrain contact points. Because the Quick Oriented Terrain Algorithm (QOTA) focuses solely on the problem of intersecting lines of a predetermined orientation with a terrain model, it provides very rapid support for terrain following. For example, given a 13,000 polygon terrain, QOTA running on a 250MHz R4400 MIPS processor can calculate an intersection point in less than 19 microseconds \((1.9 x 10^{-5}\) seconds). Given a preferred orientation, such as the direction of the gravity vector, for the lines to be intersected with a terrain, QOTA uses a pre-processing step that sorts the terrain polygons into a quadtree and adds bounding boxes and polygon edge equation parameters to speed up polygon containment checking. In the example above, this preprocessing takes approximately 2 seconds. In addition to terrain following, QOTA is useful for detecting certain limited kinds of collision detection and determining containment.", } @article{aa-lpba-95 , author = "M.D.S. Aliyu and K.S. Al-Sultan" , title = "LP-based algorithms for detection the collision of moving objects" , journal = "Journal of the Operational Research Society" , volume = 46 , number = 7 , year = 1995 , pages = "854--866" , annote = " In this paper, we consider the problem of detecting the collision of moving objects in three-dimensional space. We develop two algorithms that use linear programming techniques to detect exact possible collisions between the objects in both time and space when the objects are represented as polyhedral sets in R/sup 2/ or R/sup 3/. The algorithms can handle the case of a rigid body moving on a general path with simultaneous translation and rotation. Computational experience on the developed algorithms is also presented." } @article{hafg-ecpam-95 , author = "V. Hayward and S. Aubry and A. Foisy and Y. Ghallab" , title = "Efficient collision prediction among many moving objects" , journal = "International Journal of Robotics Research" , volume = 14 , number = 2 , year = 1995 , pages = "129--143" , annote = "We consider the problem of flagging all collisions between a large number of dynamic objects. Because the number of possible collisions grows quadratically with the number of objects, a brute force approach is not applicable with finite computational resources. Hence, we propose a scheduling mechanism that reduces the computational load by exploiting the coherence of the world throughout time. This mechanism has a very simple structure and easily lends itself to distributed processing. It considers all pairwise interactions between objects and maintains a structure that reflects the imminence, or urgency, of collision for each pair. Bounds on the urgency of collisions can be computed given minimal knowledge of the system dynamics. For example, we represent physical objects by their positions and by bounds on their relative speeds and accelerations. These are assumed to be available at all times. If the environment does not change too rapidly, the mechanism flags all collisions. False alarms may also be generated but can be eliminated with a specialized exact collision post-processor. We address the question of how often to perform the collision checks while guaranteeing that all collisions will be caught. Given the large number of possible environments and motions, no general optimal answer can be provided. Yet the soundness and efficiency of the proposed algorithm is experimentally verified in the case of a simple world consisting of many spheres moving simultaneously and randomly." } @inproceedings{b-cscnr-90 , author = "David Baraff" , title = "Curved surfaces and coherence for non-penetrating rigid body simulation" , booktitle = "Proc. SIGGRAPH'90" , year = 1990 , pages = "19--29" } @inproceedings{bw-dsnfb-92 , author = "David Baraff and Andrew Witkin" , title = "Dynamics simulation of non-penetrating flexible bodies" , booktitle = "Proc. SIGGRAPH'92" , year = 1992 , pages = "303--308" } @inproceedings{vt-escds-94 , author = "P. Volino and N. Magnenat Thalmann" , title = "Efficient self-collision detection on smoothly discretised surface animations using geometrical shape regularity" , booktitle = "Proc. EuroGraphics'94" , year = 1994 , pages = "155--166" } @inproceedings{vct-vetsc-95 , author = "P. Volino and M. Courchesne and N. M. Thalmann" , title = "Versatile and efficient techniques for simulating cloth and other deformable objects" , booktitle = "Proc. SIGGRAPH'95" , year = 1995 , pages = "137--144" }