Collision Detection and Deformable Objects Real-time meshless deformation

使用判别训练的部件模型进行目标检测Pedro F. Felzenszwalb, Ross B.Girshick, David McAllester and Deva Ramanan使用判别训练的部件模型进行目标检测 Object Detection with Discriminatively Trained Part Based Models摘要本文介绍了一个基于混合多尺度可变形部件模型(mixtures of multiscale deformablepart model) 的目标检测系统。

此系统可以表示各种多变的目标并且在PASCAL目标检测挑战赛上达到了目前最优结果(state-of-the-art)。

虽然可变形部件模型现在很流行，但它的价值并没有在类似PASCAL这种较难的测试集上进行展示。

此系统依赖于使用未完全标注(partially labeled)的样本进行判别训练的新方法。

我们提出了一种间隔敏感(margin-sensitive)的难例挖掘方法(data-mining hard negativeexample)，称为隐藏变量SVM(latent SVM, LSVM)，是MI-SVM 加入隐藏变量后的重新表示。

LSVM的训练问题是一个半凸规划(semi-convex)问题，但如果将正样本的隐藏变量的值指定后，LSVM的训练问题变为凸规划问题。

最终可以使用一个迭代训练方法来解决，此迭代算法不断交替地固定正样本的隐藏变量和最优化目标函数。

关键词目标识别(ObjectRecognition)，可变形模型(Deformable Models)，图结构模型(Pictorial Structures)，判别训练(Discriminative Training)，隐藏变量SVM(Latent SVM)1 引言目标检测是计算机视觉领域内一项基础性的工作。

本论文研究在静态图片中检测并定位某一类目标(例如人或车)的问题。

The Research of Collision Detection Algorithm Based on Spatial SubdivisionHanjun Jin, Zhiliang Liu, Tianzhen Wu Department of Computer ScienceHuazhong Normal UniversityWuhan, Chinali2920ning@Yanxia WangSchool of Remote Sensing and Information EngineeringWuhan UniversityWuhan, Chinawyx_happy1314@Abstract—Interactive environments for dynamically deforming objects play an important role in virtual environment. These environments require fast and efficient collision detection handling techniques. In this paper, we propose a new collision detection algorithm based on spatial subdivision, which can solve the collision detection problems between deformable objects. The object space is uniformly subdivided into a series of voxels, and then determines whether collision detection will happen by constructing binary sort tree. Based on distribution density of objects, an optimal method is proposed to compute the size of voxels in uniform division, compared to other collision detection algorithm through a serial of tests, the results show that the algorithm this paper proposes is superior in performance when massive objects are uniformly distributed; Besides, the performance of algorithmis more stable than other algorithms in consideration of variable correlation among objects.Keywords-virtual environment; collision detetion; voxels; uniform subdivision.I.I NTRODUCTIONFor many years, collision detection has been of major interest in CAD, computer graphics, robotics, games, computational geometry, surgery simulation, and cloth simulation, numerous approaches has been investigated to detect collisions between objects in virtual environment. While many of the original collision detection methods especially address the problem of rigid objects, recent approaches have started focusing on deformable objects.Deformable objects collision detection is an essential component in physically-based simulations and animation which is a rapidly growing research area. Fig. 1 illustrates one of the major applications for deformable collision detection, namely cloth simulation. Such applications require collision detection algorithms that are especially appropriate for deformable and animated objects.In order to realistically process interaction between deformable objects, timely and precise self-collisions are required. Furthermore, the information and performance by the collision detection approach should allow for an efficient and physically-correct collision response.Figure 1. In interactive cloth simulation, efficient deformable collisiondetection is a key componentIn this paper, we describe a new algorithm for the detection of collisions and self-collisions of deformable objects based on spatial division. By dividing the space uniformly into voxels, we choose an appropriate voxel size and use a binary sort tree; therefore, the efficiency of collision detection is improved since the potential collision regions are significantly reduced and located rapidly.The rest of the paper is organized as follows. Section 2 discusses the state-of-the art in collision detection for rigid and deformable objects. Section 3 presents the proposed algorithm. In Section 4 experiments are described. Finally, we conclude this paper in Section. 5.II.R ELATED WORKEfficient collision detection is an essential component in physically-based simulation or animation [1], [2], including cloth modeling [3]. Further applications can be found in robotics, computer animation, surgery simulation, and games.Collision detection algorithms based on bounding-volume (BV) hierarchies have proven to be very efficient and many types of BVs have been investigated, such as spheres [4], [5], [6], axis-aligned bounding boxes [7], [8], Initially, BV approaches have been designed for rigid objects. In contrast to hierarchies for rigid objects, hierarchies for deformable objects need to be updated in each time step, so they still pose a substantial computational burden and storage overhead for physically-basedapplications. As an additional limitation for physically-2009 International Conference on Computer Engineering and Technology 978-0-7695-3521-0/09 $25.00 © 2009 IEEEDOI 10.1109/ICCET.2009.80452based applications, BV approaches typically detect intersecting surfaces.As an alternate to object partitioning, distance fields have been employed to detect collisions and even self-collisions in non-interactive applications. Although efficient algorithm for computing distance fields have been proposed recently, this generation is still not fast enough for real-time processing of geometrically complex objects [9], where distance fields have to be updated during run-time due to deforming geometry.There exist various approaches that propose spatial subdivision for collision detection. These algorithms employ uniform grids [10], [11], [12] or BSPs [13]. In [10], spatial hashing for collision detection is mentioned for the first time. In [14], a hierarchical spatial hashing approach is presented as part of a robot motion planning algorithm, which is restricted to rigid bodies.III. C OLLISION DETECTION ALGORITHMIn this section, we present a collision detection method using the uniform spatial subdivision technique. Then, we describe how to choose an appropriate voxel size, and introduce a simple way to detect the collisions for the deformable objects.A. The size of voxelsIn the algorithm, we can replace the objects with points in three-dimensional space when describing the characteristics of objects if assuming that the size of objects is smaller (compared to the whole virtual space), and the distribution of objects is uniform relatively. We need to calculate the quantity of the objects in the voxels to calculate the complexity of the voxels updating. So we introduced the definition about border domain of voxels. Definition: the region space surrounding the border of voxels whose specific construction is the cuboids region which uses the plane of voxels as the bottom and the bandwidth of border as the thickness, is the border domain of the voxel. If 0V represents three-dimensional space, the point distributing density of which is )(v P , 0),,(V z y x v ∈, and 0V is divided into 1V , 2V …m V , which meet with=0V ∪mj j V 1=, )(k j V V k j ≠Φ=∩, and m is the numberof division, j N is the points distribution density of j V ,0N represents the points distribution density of 0V ,then ∑==mj j N N 1.If assuming that jb D represents the border domain space ofj V , jb N is the distribution density of j V ,∫∫∫=dv v P N jb )(, K represents the computation ofcollision of j V ,F represents the whole computationquantity about 0V , then we can get the following formula:j mj jb j N N N F 21log )(⋅+=∑= (1)Generally speaking, we can consider 0V as a cube, l asthe size of voxel, and w as the bandwidth of border domain, then the volume of voxel 3l V j =, the volume of borderdomain w l V bj 26=, we can get the following formula from(1):)log log 3(1)(2260p l N l F l w +⋅+⋅= (2)The derivation of (2) can be calculated as follows:)log 2log 66(3)(2220'p w l w w l lNl F −−+= (3)Supposing p w l w w l l f 22log 2log 66)(−−+=, the derivation of )(l f can be calculated as follows:lwl f 2'ln 61)(−= (4) Obviously, when equals to 2ln6w, )(l F gets the minimum,the value of l is the most reasonable value.B. Process for collision detectionThe process can be divided into two steps as follows: 1) Distributing voxels for the objects: Firstly, according to the result of formula (4), we can ascertain the appropriate size of the voxel, and then construct the AABB bounding volume for the inside of objects. Thus we can determine the ownership of the AABB for every object. After distributing process and constructing the AABB bounding volume of these objects to x, y, z axis respectively by means of one-dimensional space sort. Finally we can create three lists (corresponding to the axis) and sort these lists by the method of binary sort tree.2) Data updating of the voxels: For the deformable collision, the data structure to be pre-processed must be updated frequently and rapidly, so it is very important to construct a proper data structure for the data structure updating in voxels. The binary sort tree is suited to dynamic update, and it has low level of complexity. We adopt it to perform the updating of data structure in this algorithm.a) If objects are moved out of voxels, we should delete the relevant nodes in binary sort tree.b) If objects are moved into voxels, we should insert relevant nodes in binary sort tree.c) If location of the object changes, we should adjust relevant nodes in the binary sort tree.d)If objects are deformed, we should redesign the size of voxels and reconstruct its AABBs, then update the binary sort tree.IV.S IMULATION TESTAs mentioned above, as for the collision detection in virtual environment, bounding volume hierarchies is an effective method. In order to verify the performance of the algorithm in uniform space, we do tests in a PC (CPU P4 2.0 GHz, memory 1 G, memory for the Graphics card 512 M).In the experiment, assuming that the objects are particles, which were distributed in space randomly, the differences in size of the objects are tiny, as the collision detection of the distorted objects, the distribution density of objects and velocity have a obvious effect on the complexity of the algorithm.On the assumption that objects move as the rate of V,the size of three-dimensional space isD, the number of objects is N , the number of collision detection is K in the time of t, so we can use cdps (cdps=tK) to denote the efficiency of collision detection.As is seen from Fig. 2, the speed of I-COLLIDE is higher than that of the algorithm when N is larger. With the increase in N, the speed of the two algorithms tends to decline, and the decline speed of I-COLLIDE is higher than that of algorithm. That is to say, the spending of computation which is brought about by spatial subdivision is larger than that brought out by it in each vowel when Nis smaller. Thus, it weakens the efficiency of collision detection. The efficiency brought about by spatial subdivision in the voxels is significantly higher than the spending of computation brought in by it when N is larger. Therefore, it is more efficient than I-COLLIDE. If the two curves are seen as lines, the computational complexity of the algorithm is superior to that of I-COLLIDE, which can be seen from the slope of the lines.From Fig. 3 we can see that, if V is certain, the density of objects distribution effect on the efficiency of the algorithm is quite different: as for the uniform subdivision adopting this algorithm, reducing the density will increase the efficiency of collision detection, but when reducing to a certain level, the efficiency of this algorithm stays basically in the same level, we can explain it as follows: When the density of objects is reduced, the possibility of the collision is reduced greatly, and so do the time of construction and storage binary sort tree, but when reducing to a certain extent, the size of voxel will be unchanged; However, the AABBs, the binary trees need to be adjusted when density is reduced, then the probability of overlap between boxes increased significantly, finally the efficiency of the algorithm is reduced accordingly.Fig. 4 shows that V has slight effect on the method of uniform subdivision; nevertheless it has a greater effect on the AABBs. We can explain it as follows: when V is quicker, the possibility of deformation is also increased, which need modifying and updating the bounding volumefrequently, the efficiency of the algorithm is reduced.Figure 2.Comparison between the I –COLLIDE and Uniform subdivisionFigure 3. The effect of objects’ distributed densityFigure 4. The effect of VV.CONCLUSIONIn this paper, a collision detection algorithm based on spatial subdivision has been presented. Experiments show that the algorithm is superior in performance when massive objects are uniformly distributed; furthermore, the performance of algorithm is more stable than the other algorithm in consideration of variable correlation between objects. In this paper, we use this method to detect collision for particles in virtual environment. In fact, the method can be applied to other deformable objects. Future work remains to be done. The algorithm probably should be modified when objects are non-uniform distributed.A CKNOWLEDGMENTThis work is supported by Natural Science Foundation of Hubei Province (No.2007ABA328).R EFERENCES[1] D.Baraff, “Collision and contact,”SIGGRAPH’01 Course Notes,2001.[2]G. Debunne, M. Desbrun, M.-P. Cani, A. Barr, “Dynamic real–timedeformations using space & time adaptive sampling,” Proceedings ofSIGGRAPH ’01, pp.31–36, 2001.[3]R. Bridson, R. Fedkiw, J. Anderson, “Robust treatment of collisions,contact and friction for cloth animation,” Proceedings of SIGGRAPH ’02, pp.594-603, 2002.[4]P.Hubbard, “Interactive collision detection,” Proceedings of IEEESymposium on Research Frontiers in virtual Reality ’93, pp. 24-31, 1993.[5]S.Quinlan, “Efficient distance computation between non-convexobjects,” Proceedings of IEEE Int. Conf.on Robotics and Automation, pp, 3324-3329, 1994.[6]G.Bradshaw, C.O’Sullivan, “Sphere-tree construction usingmedial-axis approximation,” Proceedings of the ACM SIGGRAPH Symposium on Computer Animation SCA’02,, pp.33-40, 2002[7]Gottschalk S, Lin M C. Manocha D. OBB-Tree: A HierarchicalStructure for Rapid Interference Detection [A]. In: Proceedings of SIGGRAPH ’96[c]. 1996.171-180.[8]G. van den Bergen, “Efficient collision detection of complexdeformable models using AABB trees,” Journal of Graphics Tools, vol.2, no, 4, pp.1-13, 1997.[9]G.Hirota, S.Fisher, M. Lin, “Simulation of non-penetratingelastic bodies using distance of fields,” Technical Report TR00-018, University of North Carolina at Chapel Hill, 2000.[10]F.Ganovelli, J.Dingliana, C.O’Sullivan, “Bucket Tree:Improving collision detection between deformable objects,”Proceedings Spring Conference on Computer graphics SCCG’00, Budmerice Castle, Bratislava, 2000[11]G. Turk, “Interactive collision detection for molecular graphics,”Technical Report TR90-014, University of North Carolina at Chapel Hill, 1990.[12] D. zhang, M. Yuen, “Collision detection for clothed hunmananimation,” Proceedings of Pacific Graphics’00, pp. 328-337, 2000. [13]S. Melax, “Dynamic plane shifting BSP traversal,” Proceedings ofGraphics Interface’00, pp.213-220, 2000.。

2003-12-17 2003- 12-
5
Introduction
Different kinds of colliding bodies: Three levels of difficulity: (1) Convex rigid bodies; (2) General rigid bodies; (3) Deformable bodies;
The hybrid bottom-up/top-down tree update method.
2003-12-17 2003- 1228
Some Other Topics
Collision Response
Collision response for a sphere approaching a plane. To the left the velocity vector V is divided into two components, Vn and Vp. To the right, pergectly elastic collision is shown, where the new velocity is V'=Vp-Vn. For a less elastic collision, the length of –Vn could be decreased.
2003-12-17 2003- 12-
2
Introduction
Collision Collision is a fundamental task in virtual reality: (1) Haptic rendering (force--feedback); (2) Physically-based simulation; (3) Virtual training ( Medical, drivers ); (4) Robot technique; (5) Computer games.

C S T e c h n i c a l R e p o r t #395, A p r i l 8, 2003Institute of ScientificComputingVolumetric Collision Detectionfor Derformable ObjectsBruno Heidelberger, Matthias Teschner, Markus GrossComputerScience DepartmentETH Zurich, Switzerland e-mail: {heidelberger, teschner, grossm}@inf.ethz.chhttp://graphics.ethz.chVolumetric Collision Detection for Deformable ObjectsBruno Heidelberger Matthias Teschner Markus GrossComputer Graphics LaboratoryETH ZurichFigure1:This sequence shows two deforming objects with150k and5k faces.An explicit representation of the red intersection volume can be computed at interactive frame rate.AbstractWe present a new algorithm for the efficient detection of colli-sions of geometrically complex objects.Our approach requires nei-ther expensive setup nor sophisticated spatial data structures and is hence specifically suitable for handling deformable objects with ar-bitrarily shaped,closed surfaces.The algorithm is based on a Lay-ered Depth Image(LDI)decomposition of the intersection volume. Currently,we have implemented two types of collision queries.The first one comprises an explicit representation of the intersection vol-ume.The second one computes vertex-in-volume tests.All queries are processed on the LDI–based volume representation.Our algo-rithm is very easy to implement and can be accelerated in graphics hardware by using OpenGL.Keywords:Collision Detection,Computational Geometry,Lay-ered Depth Image,Shape Approximation,Deformable Modeling, Physically–based Modeling,Graphics Hardware1IntroductionThe detection of collisions of geometric objects constitutes a fun-damental problem in computer graphics,computational geometry, modeling,robotics,and many other areas.Most research is devoted to the design of algorithms for the efficient computation of queries, such as intersecting surfaces or penetration depth.For complex ob-jects,such queries are computationally expensive,because they re-quire the testing of many individual graphics primitives.Hence,ef-ficient collision detection algorithms are accelerated by spatial data structures including bounding–box hierarchies,distancefields,or other ways of spatial partitioning.Such object representations are built in a pre–processing stage,and once they are created,perform very well for rigid objects.Modern physics–based simulation,as for instance used in game engines or computational surgery,demand the detection of colli-sions of objects deforming over time.In the case of deformable objects,the aforementioned acceleration structures have to be up-dated to adapt to changes of the geometry.While some of these algorithms have been successfully employed in such cases,the ac-celeration structures constitute an additional overhead in memory consumption and computational efficiency.We propose a simple and efficient algorithm based on Layered Depth Images(LDI)[Shade et al.1998]as the fundamental repre-sentation to accelerate collision detection of rigid and deformable objects.While most existing approaches consider object surfaces, our method is inherently volumetric.Rather than explicitly detect-ing surface intersections,the LDI provides a discrete representation of the intersection volume and allows for volume–based collision queries as shown in Fig.1.The generation of LDIs is extremely efficient and can be accelerated by graphics hardware.Various op-timizations minimize buffer read–backs.Our algorithm proceeds in three stages.First,we calculate the intersection of axis–aligned bounding boxes of pairs of objects.If an intersection is non–empty,a second stage computes an LDI rep-resentation of each object within the bounding–box intersection.Fi-nally,we obtain the overall intersection volume by simple Boolean operations on the LDI representation.The simplicity of the algorithm,the absence of expensive setup and the ease of implementation in OpenGL makes it especially at-tractive for real–time simulation and computer games.1.1ContributionsThe contributions of this work can be summarized as follows:•We present a new algorithm for the computation of volumetric penetrations of geometrically complex,deformable objects in real time.Our method handles arbitrarily shaped,closed sur-faces of manifold geometry.•We currently process two different types of collision queries: Thefirst one includes the explicit computation of the intersec-tion volume of two objects.The second one performs vertex-in-volume tests.Our approach is also robust in cases,where one object lies completely inside another object.•Unlike most existing approaches,our method does not require an involved setup or the implementation of a sophisticatedspatial data structure.It is memory efficient,computation-ally economical and performs on deformable models of up to hundred thousands of primitives.1.2Background and Related WorkDue to the importance of the topic,the interference detection of geometrically complex objects has been investigated extensively in various areas.Collision algorithms.In graphics,efficient collision detection is an essential component in physically–based simulationtion [Baraff 2001],[Debunne et al.2001],including cloth [Bridson et al.2002].Further applications can be found in computer animation,medical simulations,and games.Collision detection algorithms based on hierarchies have proven to be very efficient and many BVs have been investigated.Among the acceleration find spheres [Hubbard 1993],[Quinlan 1994],ing boxes [Hughes et al.1996],[van den Bergen oriented bounding boxes [Gottschalk et al.1996],and oriented polytopes [Klosowski et al.1996].Initially,BV approaches were designed for rigid context,the hierarchy is computed in a pre–processing case of deforming objects,however,this hierarchy must at run time.While effort has been spent to optimize BV for deformable objects [Larsson and Akenine-Moeller still pose a substantial computational burden and storage for complex objects.As an additional limitation for cations,BV approaches typically detect intersecting computation of the intersection volume requires an As an alternative to object partitioning,other ploy discretized distance fields as volumetric object for collision detection.The presented results,however,this data structure is less suitable for real–time metrically complex objects [Hirota et al.2000].Recently,various approaches have been introduced that employ graphics hardware for collision detection.In [Baciu et al.1999],a multi–pass rendering method is proposed for collision detection.However,this algorithm is restricted to convex objects.In [Lom-bardo et al.1999],the interaction of a cylindrical tool with de-formable tissue is accelerated by graphics hardware.The method is restricted to collisions of simplified surgical tools with object surfaces.[Hoff III et al.2001]proposes a multi–pass rendering approach for collision detection of 2–D objects,while [Kim et al.2002]and [Kim et al.2003]perform closest–point queries using bounding–volume hierarchies along with a multipass–rendering ap-proach.The aforementioned approaches decompose the objects into convex polytopes.Layered Depth Images (LDI).LDIs have been introduced as an efficient image–based rendering technique.The LDI data structure essentially stores multiple depth values per pixel.Thus,an LDI can be used to approximate the volume of an object.A method for generating LDIs is presented,for instance,in the depth–peeling approach to order–independent transparency [Everitt 2001].This implementation,however,demands a complex setup including two active depth buffers and texture shaders.In contrast,our approach to LDI generation is much simpler by employing a more efficient rendering setup based on plain OpenGL 1.4.Hardware–based approaches to interactive CSG rendering,e.g.[Goldfeather et al.1986]and [Rappoport and Spitz 1997],could also be employed for LDI generation.However,since such CSG rendering implementations have to handle more complex modeling operations they feature more involved rendering setups.Further-more,these CSG rendering approaches do not explicitly compute the resulting solid.2Method This section presents an overview of our algorithm followed by a detailed description of the three stages.Input.Our approach takes 3–D closed objects of manifold geome-try as an input.Although the approach is not confined to triangular (a)Stage 1.(b)Stage 2.(c)Stage 3a.Figure 2:Algorithm overview in 2–D and 3–D.(a)AABB inter-section.(b)LDI generation within the V oI.(c)Computation of the intersection volume.Algorithm overview.Our approach proceeds in three stages.Stage 1computes the AABB intersection for a pair of objects.If the intersection is empty,the two objects do not overlap.If it is not,stages 2and 3are applied to the AABB intersection volume.We will refer to it as V olume-of-Interest (V oI).Stage 2computes two LDIs,one for each object.LDI gener-ation is restricted to the V oI.The depth values of the LDI can be interpreted as the intersections of parallel rays or 3–D scan lines entering or leaving the object.Thus,an LDI classifies the V oI into inside and outside regions with respect to an object.Likewise,we classify the corresponding intersections into entry points and leav-ing points .The concept is similar in spirit to well–known scan–conversion algorithms to fill concave polygons [Foley et al.1990],where intersections of a scan line with a polygon represent transi-tions between interior and exterior.Stage 3performs the actual collision detection.Currently,we distinguish two different types of queries:a)Both LDIs are com-bined using Boolean intersection.If the intersection of all inside regions is not empty,a collision is detected.This operation also pro-vides an explicit representation of the intersection volume.b)Indi-vidual vertices within the V oI of one object are transformed into the LDI of the second object.If such a vertex lies in an inside region,a collision is detected.This query can also be used to check atomic or point–sampled objects for intersection.Fig.2illustrates the three stages of our algorithm.For a detailed description of all stages,refer to Sections2.1–2.3.2.1AABB IntersectionAABB intersections are computed for pairs of objects.If two AABBs do not overlap,the corresponding objects cannot interfere. Otherwise,the intersection volume provides a V oI,which is con-sidered for further processing.Although AABBs do not provide an optimal,i.e.smallest,bounding volume,they can be computed very efficiently.Furthermore,the intersection of two AABBs is again an AABB which keeps subsequent stages of the algorithm simple.Alternative BVs,such as object–oriented bounding boxes [Gottschalk et al.1996]or discrete–oriented polytopes[Klosowski et al.1996],provide tighterfitting object approximations.How-ever,the computation of these representations is more involved and the resulting intersection volume can have a more complex shape making it much more difficult for further processing.In addition, such structures are impractical for deforming objects,which require a dynamic adaptation of the bounding box.In order to simplify and accelerate further computations,the V oI has to meet the following requirements:Firstly,to guarantee proper boundary conditions,we have to render the LDI for each object from the outside.We select one of the six faces of the V oI,the so–called outside face,as the near rendering plane for each object(see Fig.3).If a sorted LDI is generated with respect to this face,en-try points and leaving points alternate.For closed objects,thefirst layer is assumed to contain entry points,the second layer leaving points and so on.Secondly,outside faces for both objects should correspond to opposite sides of the V oI(see Fig.3(a)).This sim-plifies the combination of both LDIs for the computation of the intersection volume.(a)V oI for A and B.(b)Extended V oI to obtainan outside face for A. Figure3:The intersection of the AABBs of two objects A and B provides the V oI.The intersection volume of two AABBs,i.e.the V oI,is bounded by parts of their faces.Fig.3(a)shows a V oI with corresponding outside faces.In some cases,for instance when one box is en-tirely within another box,appropriate outside faces for both objects cannot be found.This problem is solved by extending the V oI.If the outside face of one object isfixed,the opposite face of the V oI can be scaled to touch the bounding box of the other object(see Fig.3(b)).If several eligible pairs of outside faces exist,we choose the ones with the smallest distance between them.This criterion is a fast heuristic to optimize depth complexity for LDI generation assum-ing that depth complexity scales with the distance between the two outside faces.and their opposite faces defining the far planes.The remaining faces define top,bottom,left,and right of the rendering volume. Orthographic projection is used for rendering.The resolution of the LDI,which defines the accuracy of the object approximation,is specified by the user.Objects are rendered n max times for LDI gen-eration,where n max denotes the depth complexity of the relevant part of the object within the V oI.Thus,the computational com-plexity of the LDI generation is O(n max).For details regarding the OpenGL implementation,refer to Sec.3.Thefirst rendering pass generates a single LDI layer and com-putes n max.Depth testing and face culling are disabled.Only the stencil test is employed to discard fragments.The stencil test con-figuration allows thefirst fragment per pixel to pass,while the cor-responding stencil value is incremented.Subsequent fragments are discarded by the stencil test,but still increment the stencil buffer. Hence,after thefirst rendering pass the depth buffer contains the first object layer per pixel and the stencil buffer contains a map rep-resenting the depth complexity per pixel.Thus,n max is found by searching the maximum stencil value.Note,that the max()com-putation constitutes a very small computational burden,given the typical LDI resolution.If n max>1,additional rendering passes2to n max generate the remaining layers.The rendering setup is similar to thefirst pass. However,during the n-th rendering pass,thefirst n fragments per pixel pass the stencil test and,as a consequence,the resulting depth buffer contains the n-th LDI layer.During these passes,the stencil buffer is not incremented,if the stencil test fails.Since fragments are rendered in arbitrary order,the algorithm generates an unsorted LDI.For further processing,the LDI is sorted per pixel.Only thefirst n p layers per pixel are considered,where n p is the depth complexity of this pixel.n p is taken from the stencil buffer as computed in thefirst rendering pass.If n p is smaller than n max,layers n p+1to n max do not contain valid LDI values for this pixel and are discarded(see Fig.5).Although the order in which the fragments of an object are ren-dered is arbitrary,our algorithm relies on consistency across the individual passes.Our LDIs store normalized values.For advanced collision queries,additional information,such as viewing direction and viewing volume are stored as well.The accuracy of the method can be adjusted.In(x,y)-direction, accuracy corresponds with the user–defined LDI resolution.The accuracy in z-direction is given by the depth–buffer resolution.Figure 5:LDI for two pixels,unsorted and sorted with respect to depth values.Compared to alternative data structures,such as bounding–volume hierarchies or distance fields,the LDI representation is very memory efficient.Both the memory consumption and the perfor-mance of the LDI generation depend on the geometric complexity and the depth complexity of the objects.However,our results pre-sented in Sec.4suggest,that the number of LDI layers does not exceed reasonable values even for complex objects.Further,col-lision queries performed on the generated LDIs are very efficient even in the case of a large number of LDI layers.2.3Collision DetectionThe computed LDIs can be utilized to process a variety of collision queries in an efficient way.Our current implementation comprises two different types of collision queries:Intersection volume.Two LDIs can be combined to compute an intersection volume.The LDIs for two colliding objects are dis-cretized with the same resolution on corresponding sampling grids,but with opposite viewing directions.Hence,pixels in bothLDIs represent corresponding volume spans.Therefore,intersection vol-umes can be computed by a pixelwise intersection of the inside re-gions of both LDIs.Ifthe resulting intersection is non–empty,a collision is detected.The sum of all pixelwise intersection regions constitutes a discrete representation of the intersection volume (see Fig.6(a)).(a)Intersection volume.(b)Vertex-in-volume.Figure 6:Two types of collision queries.Pixelwise intersection and testing of the LDIs.Vertex-in-volume.Individual vertices can also be tested against an LDI.To this end,the vertex is transformed into the local coordinate system of the LDI.If the transformed vertex intersects with an in-side region,a collision is detected (see Fig.6(b)).As demonstrated in Fig.11and Fig.12,this query can be used to compute collisionswith atomic objects,such as particles.3Implementation The implementation of V oI computation (stage 1)and collision queries (stage 3)can be easily accomplished by following the de-scriptions in Sec.2.1and Sec.2.3,respectively.This section de-scribes some details regarding the efficient implementation of the LDI generation (see Sec.2.2)using core OpenGL 1.4functionality.The LDI generation is performed in a multi–pass rendering pro-cess following the rendering setup as described in Sec.2.2.To im-prove performance,the color buffer is disabled.Each LDI layer is generated in one rendering pass.Except for the first pass,which computes the depth complexities per pixel,all passes are identical.Our actual OpenGL implementation is very similar to the following pseudo code.rendering setup;//pass 1computes n max and the first LDI layer glClear(GL DEPTH BUFFER BIT |GL STENCIL BUFFER BIT);glStencilFunc(GL GREATER,1,0xff);glStencilOp(GL INCR,GL INCR,GL INCR);render object;depth complexities ←stencil buffer;n max ←max(depth complexities);layer [1]←depth buffer;//passes 2to n max compute the remaining LDI layers n ←2;while n ≤n max begin glClear(GL DEPTH BUFFER BIT |GL STENCIL BUFFER BIT);glStencilFunc(GL GREATER,n,0xff);glStencilOp(GL KEEP,GL INCR,GL INCR);render object;layer [n ]←depth buffer;n ←n +1;end;Each rendering pass actually requires a buffer read–back.Read-ing back buffers from the GPU,however,can be expensive de-pending on the actual architecture.We propose two methods for optimizing the data transfer using OpenGL extensions.Firstly,depth and stencil values of a pixel are usually stored in the same 32–bit word in the framebuffer.This allows to read–back both buffers in a single pass using an OpenGL extension,such as GL NV packed depth stencil.Secondly,all rendering passes can be performed independently from each other except for the first pass.We exploit this fact to render individual layers into differ-ent regions of the framebuffer.Once finished,the whole frame-buffer is read back in a single pass.This optimization reduces the number of read–backs to a maximum of two,assuming that the framebuffer memory is sufficiently large.It reduces stalls in the rendering pipeline and substantially improves the performance of the algorithm.4Results All of the experiments described in this section have been per-formed on a PC with 2.8GHz Intel Pentium IV ,2GB main mem-ory,and NVidia GeForce 4Ti 4600graphics card with 128MB on–board memory.Results for the two types of collision queries are presented using five different test objects (see Fig.7).Intersection volume.In Tab.1,computing times for six cases are given.Since the performance of our algorithm depends on the ge-ometrical complexity of the object and on the depth complexities of both objects within the V oI,we have carried out experiments asshown in Fig.8and Fig.9.In the worst case,when both AABBs coincide,the V oI and the depth complexity are maximal.Hence, both LDIs are computed for the entire object.The performance of these cases can be derived from Tab.2,where timings for the LDI generation for entire objects are given.Objects Faces DepthCom-plexityStage1+2[ms]Stage3a[ms]Fig.Knot/Rabbit12k/50k3/11918 Knot/Rabbit12k/50k4/65619 Rabbit/Reptile50k/110k7/53618 Rabbit/Reptile50k/110k4/24819 Reptile/Santa110k/150k1/32518 Reptile/Santa110k/150k8/611419 Table1:Computation of the intersection volume using various ob-ject pairs as shown in Fig.8and Fig.9.The resolution of the LDI is 128x128.The depth complexities are given for both objects within the V oI.Stage1and2compute the AABBs,the V oI,and both LDIs. Stage3a generates the intersection volume.In the case of rigid ob-jects,stages1and2can be pre–computed.An additional scenario with a very complex intersection volume is illustrated in Fig.10.The Knot and the Dragon have12k faces and520k faces,respectively.Depth complexities within the V oI are 7and8.With an LDI resolution of128x128the intersection volume can be computed in256ms.puting times for the vertex-in-volume test are given in Tab.2.For each object,100,000arbitrarily positioned vertices within the AABB of an object are tested.Fig.11illustrates the experiment for one of the test objects.Object FacesDepthComplexityStage1+2[ms]Stage3b[ms]Knot12k81126Rabbit50k82927Reptile110k128328Santa150k87926Dragon520k1030727 Table2:Vertex-in-volume test for various objects.The V oI com-puted in stage1coincides with the AABB of the object.Stage2 computes the LDI representation for the entire object with a reso-lution of128x128.In stage3,100,000vertices with arbitrary posi-tions within the AABB of the object are tested.In the case of rigid objects,stages1and2can be pre–computed.Fig.11illustrates the test for one object.An application of the vertex-in-volume test is shown in Fig.12. The simulation environment includes20,000particles and the de-forming Santa with10k faces.The object deformation,the particle dynamics,the collision detection and response can be computed and rendered in real time with29fps.5Conclusions5.1DiscussionWe have presented a fast,hardware–accelerated method for volu-metric collision detection.As a central acceleration structure our algorithm computes an LDI that approximates the intersection vol-ume.Unlike many existing collision detection schemes,our method does not require expensive setup or pre–processing and is,hence, specifically suited for deformable objects and dynamic simulation. Currently,we have implemented two different types of collision queries and demonstrated that the method performs at interactive rates up to very complex geometry.As a limitation,our collision detection approach is restricted to objects with closed,watertight surfaces,since it relies on the notion of inside and outside.5.2Future WorkCurrently,collision queries are computed on the CPU.The perfor-mance of the algorithm could be improved by using the GPU.Em-ploying pixel shaders with multiple render targets for LDI genera-tion might support GPU–based queries.While we compute an explicit representation of the intersection volume,additional queries,such as penetration depth or closest point,might be needed for advanced collision response.This is also subject to future research.At this point,self–collisions are not detected.Actually,our al-gorithm could be extended towards self–collisions by treating the front and back faces separately during the rendering process.This would allow us to efficently detect an invalid ordering of front and back faces.6AcknowledgementsThis project is funded by the National Center of Competence in Research“Computational Medicine”(NCCR Co–Me). ReferencesB ACIU,G.,W ONG,W.S.-K.,AND S UN,H.1999.RECODE:an image–based col-lision detection algorithm.The Journal of Visualization and Computer Animation 10,181–192.B ARAFF,D.2001.Collision and contact.SIGGRAPH2001Course Notes.B RIDSON,R.,F EDKIW,R.,AND A NDERSON,J.2002.Robust treatment of colli-sions,contact and friction for cloth animation.In Proc.of the29th annual confer-ence on Computer graphics and interactive techniques,ACM Press,594–603.D EBUNNE,G.,D ESBRUN,M.,C ANI,M.-P.,AND B ARR,A.H.2001.Dynamicreal-time deformations using space&time adaptive sampling.In Proc.of the28th annual conf.on Computer graphics and interactive techniques,ACM Press,31–36.E VERITT, C.2001.Interactive order–independent transparency.Technical report,NVIDIA Corporation.F OLEY,J.D.,VAN D AM,A.,F EINER,S.K.,AND H UGHES,puterGraphics:Principles and Practics.Addison-Wesley Publishing Company.G OLDFEATHER,J.,H ULTQUIST,J.P.M.,AND F UCHS,H.1986.Fast constructive–solid geometry display in the pixel–powers graphics system.In Proc.of the13th annual conference on Computer graphics and interactive techniques,ACM Press, 107–116.G OTTSCHALK,S.,L IN,M.C.,AND M ANOCHA,D.1996.Obbtree:a hierarchicalstructure for rapid interference detection.In Proc.of the23rd annual conference on Computer graphics and interactive techniques,ACM Press,171–180.H IROTA,G.,F ISHER,S.,AND L IN,M.C.2000.Simulation of non–penetratingelastic bodies using distancefields.Technical Report TR00-018,University of North Carolina at Chapel Hill.H OFF III,K.E.,Z AFERAKIS,A.,L IN,M.C.,AND M ANOCHA,D.2001.Fast andsimple2d geometric proximity queries using graphics hardware.In Proc.of2001 Symposium on Interactive3D Graphics,145–148.H UBBARD,P.M.1993.Interactive collision detection.In Proc.IEEE Symposium onResearch Frontiers in Virtual Reality,24–31.H UGHES,M.,D I M ATTIA,C.,L IN,M.C.,AND M ANOCHA,D.1996.Efficient andaccurate interference detection for polynomial deformation and soft object anima-tion.In Proc.of Computer Animation,155–166.K IM ,Y.J.,O TADUY ,M.A.,L IN ,M.C.,AND M ANOCHA ,D.2002.Fast pen-etration depth computation for physically-based animation.In Proc.of the ACM SIGGRAPH symposium on Computer animation ,ACM Press,23–31.K IM ,Y.J.,H OFF III,K.E.,L IN ,M.C.,AND M ANOCHA ,D.2003.Closest point query among the union of convex polytopes using rasterization hardware.Journal of Graphics Tools ,to appear.K LOSOWSKI ,J.T.,H ELD ,M.,M ITCHELL ,J.S.B.,S OWIZRAL ,H.,AND Z IKAN ,K.1996.Efficient collision detection using bounding volume hierarchies of k–DOPs.In Proc.of the 23rd annual conference on Computer graphics and interac-tive techniques ,ACM Press,171–180.L ARSSON ,T.,AND A KENINE -M OELLER ,T.2001.Collision detection for continu-ously deforming bodies.In Proc.of Eurographics 2001,325–333.L OMBARDO ,J.C.,C ANI ,M.-P.,AND N EYRET ,F.1999.Real–time collision detec-tion for virtual surgery.In Proc.of Computer Animation ’99,33–39.Q UINLAN ,S.1994.Efficient distance computation between non–convex objects.In Proc.IEEE Int.Conference on Robotics and Automation ,IEEE,3324–3329.R APPOPORT ,A.,AND S PITZ ,S.1997.Interactive boolean operations for conceptual design of 3–D solids.In Proc.of the 24th annual conference on Computer graphics and interactive techniques ,ACM Press/Addison-Wesley Publishing Co.,269–278.S HADE ,J.,G ORTLER ,S.,WEI H E ,L.,AND S ZELISKI ,yered depth im-ages.In Proc.of the 25th annual conference on Computer graphics and interactive techniques ,ACM Press,231–242.VAN DEN B ERGEN ,G.1997.Efficient collision detection of complex deformable models using aabb trees.Journal of Graphics Tools 2,4,1–13.Figure 7:Test objects:Dragon,Santa,Rabbit,Reptile,Knot.Figure 8:Computation of the intersection volume.AABBs,V oI,and intersection volume are shown for three examples with simpleintersections.Figure 9:Computation of the intersection volume.AABBs,V oI,and intersection volume are shown for three examples with complex intersections.Figure 10:Intersection volume for Knot andDragon.Figure 11:Vertex-in-volume test.Left:The LDI representation is computed for the entire object.V oI and AABB coincide.Right:The vertex-in-volume test is processed for 100,000arbitrarily posi-tionedvertices.Figure 12:Deforming Santa and particles.Red color on the right–hand side indicates actual or recent contact.。