Research On Collision Detection For Deformable Objects Based On Probability Calculation

As one fundamental subject in many fields such as computationalgeometry, system simulation, computer animation, robotics etc., CollisionDetection (CD) is called for higher requirements as the world forges ahead.For example, in apparel CAD, it is necessary to simulate the innervations ofthe clothes in real-time, and in the simulation of a car accident, thedeformation states of the vehicle and so on. In many fields, such as the onesmentioned above, the capabilityof the real-time interaction between computerand users is needed, which can only be frequently realized depending on highlevel collision detection rate. So how to improve the efficiency of CollisionDetection Algorithm and to fulfill the process of Collision Response whichwould give the whole Virtual process the character of real-time become theemphasesoftherecentresearch.Collision Detection Algorithms is comprised of two main classes ofalgorithms, one of which is collision detection algorithm based on spaceentities, and the other is Collision Detection Algorithm Based on Image.According to different models used by entities, entity-based algorithm iscomprised of two classes below: Space Decomposition based on BSPtree, k-dtree, Octree etc., and hierarchical bounding volumes trees. According to thedifferent of bounding volumes, hierarchical bounding volumes trees can beclassifiedinto:Aligned AxisBoundingBox,OrientedBoundingBox,DiscreteOrientation Polytope, Convex Hulls, Mixed hierarchical bounding volumestreesandsoon.However, these methods all deal with the collision detection algorithm ofrigid body. For deforming objects,the construction and partition of thebounding box is almost the same with the rigid body's in the pre-processingstage. While the object deformed, the relative position of its Vertex willchange, but would not happened in solid body. Thus hierarchical boundingvolumes trees can not be updated bythe changes of translation and rotation asrigid body. This makes the update of hierarchical bounding volumes treesmore complicated, need more magnitudes of detection and lower theefficiency of algorithm. To deal with Deformation body, it needs not only thegeometry of objects but also the topology information of objects. And whenthe bodydeformed, its structure needs to update as follow. That would greatlyaffectboththespanofapplicationandtheeffectofdetection.From the recent research and observations, it was indicated that peopleapperceivechangesofbodyinthereal-timeVirtual InteractiveSystemthroughthe effects produced during the collision, rather than exact simulation of thedeforming objects. In addition, for physiological factor, people can not Abstractdistinguish the real motion of the objects as exactly as computer, but vaguemoving. Therefore, the random collision detection algorithms of precisionreplacing efficiency become one hot point in the field of collision detection.Now there are two categories of algorithms: one is based on Pairs of features.It is comprised of some optional random pairs which are characteristic ofcollision and are the initial suppose of potential crossing region. Then itrealized exact detection of local minimum through local tracking of thesecharacters. There is one disadvantage: it isn't suitable for free deformingobjects because it need topology information of the deforming objects whenusing hierarchical bounding volumes trees. The other performs intersectingtests through establishment of distant field of objects. It is mainly used indetection of the collision between the soft and the rigid. Furthermore, themethodofdistancefieldcandealwellwithscenes inwhichthedeformationordisplacementoftheobjectislittlebutnotfitsforhugeones.In this paper, we research in the aspects below and propose somedetecting approaches for collisions with the intensive surveys andcomprehensiveanalysesofvariousissuesinthefieldsofcollisiondetection1. Using octree in the period of constructing Bounding VolumeHierarchies. Although BinaryTree has its own advantages such as simplestructureandlesstimecostforsearching,forconductingwithDeformationobjects, octree is better choice than binary ones. In the case of Octree, theamount of Bounding Volume box will be much less in each time step andthe research in contacting region will get into the inner tree more quickly.This will fasten the renewing process of hierarchical bounding volumestrees. Furthermore, Octree can reduce the depth of hierarchical boundingvolumestreeswhichfacilitatestoimprovetheefficiencyofthealgorithm.2. Using updated algorithm from middle to top and bottom during theupdatingstageofhierarchicalboundingvolumestreesandComparingthe updated strategy of hierarchical bounding volumes trees ofbottom-up and top-down. We found that: if many deep nodes werevisited, then the bottom-up strategy will implemented better; if only somedeep nodes were visited, then the top-down strategy will be implementedfaster.Therefore,weproposeahybridapproachthatbottom-upapproachisused to update the first half of the tree nodes and only if there is notupdatednotebevisited,thentop-downmodesworks.3. Proposing random collision detection algorithm based on probabilitycalculation. It will replace the exact testing process in the hierarchicalbounding volumes trees and barter precision for efficiency so as toimprove the character of real-time in the collision detection of thedeforming objects. In our opinion, the recursion process of the detectedcollision pair can be interrupted and instructed by possibility of includinginteraction triangle of the surrounding box. with respect to a given quality criterion. And then, statistics of the number of possible collisions unitswhich consisted of interaction triangle in object's pairs was done.Moreover, whether objects intersect can be determined by probabilityapproach through the number statistics of possible collision unit. Inaddition, this paper also discusses the objects motion in the collisionresponse and in order to perfect the research of the collision process of thedeformingobjects,thetheoryofthecollisionresponseandcollisionIn conclusion, the results of our research results enrich the approaches tocollision detection technology and the applications of deformable objects. Weinvestigated the precision and efficiency evaluation about the algorithm andfound that it might be a reasonable choice for complex component. We hopethat intensive and further research will be aroused through our research, andfacilitatethedevelopmentofrelativetechnologyinfuture.