Collision Detection In Virtual Environment Based On Octree

Collision detection has been researched in many fields such asrobot motion planning and computer graphics for a long time. In thelater years, with the rising of virtual reality and distributed interactivesimulation, many researches focus on collision detection,especiallycollision detection with flexible objects . Efficient and Exact collisiondetection is very important to improve reality and enhance immersionfor virtual environment, and the complexity and real-time of virtualenvironment bring new requirement to collision detection.Bounding volume hierarchy provides an effective method toresolve the intrinsic time complexity in collision detection. The ideabehind it is to approximate the object with a simpler bounding volumethat is a little bigger than the object. In building hierarchies on object,one can obtain increasingly more accurate approximations of theobjects. So during traversing bounding volume hierarchy, it speeds upcollision detection by prune away primitive pairs, which will notintersect clearly though rapid intersection test between boundingvolumes and just deal with those whose bounding volume isintersected. The choice of bounding volume is the basic and keyproblem of this approach.With the background of surgery simulation, this paper proposesa collision detection method based on fixed direction hull boundingvolume octree. Fixed direction hulls is a pecial convex hull, whoseoutward normal of facets comes from a fixed direction set. It overcomelimitations of other bounding volumes and makes a promise between tightness and simpleness. We select octrees( d =8)in our collisiondetection system, this is based on the consideration of following twosides. First, in consideration of the medical science CT characteristicsof the data and the demand of the 3D reconstruction,adopt AABB andsurround a box the method for combining together with octrees tocarry on a collision detection, so surrounding a box with octrees iseasier. Secondly, adopting octrees will make the tree lower highly.Through space octree,The algorithm is a mesh cent calculate way withnot- even space. This algorithm will imply the whole space cube offield view to press three directions to cut up into eight statures cubemesh, organization become 1 octtrees.The collision detection algorithm process:1. The Path TracksOn the supposition that we have already distinguished to onestatic state environment object E and one movable object F built upto surround a box octree layer models.(brief name for surrounding abox of tree)Let the path start orders for 0 P , the direction is R,getting octtrees of the cube mesh of the place unit first to code Q. Thisneeds first to each summit weight to take the integral part to get unitcube a mesh of front left descend Cape to summit P, then we canimmediately use equation(? ) calculation code Q. If the P point locatesboundary of world cube, then we need according to going forwardwhether direction discretion have already exercised to be present theoutside of the view or not. If the path has already throughout a view,the algorithm then ends. Otherwise check to seek Q in the space line of octree node. The checking result is denoted with two varieties. Thefirst is a bool variety T which check to seek whether it is successful ornot. The other is B which do not get to match number. Let Qdenoting q₁q₂…q_N. then when the octree includes node is true. This is because this node'smatching mesh include place of minimum mesh unit. Notice that thisnode not empty of the end order. It denotes that P₀ locates a slice andside of the triangle noodles and the length is of inner part or boundaryof the space mesh. The no matching number B is defined to octree endto order in acquire the biggest degree with Q to match the node. Thisnode codes ,then B is N-i. It is decided whether currentcube includes a scenery slice, but through Q and B or not can thenmake sure space position and size of current cube by T. For octree, itcan speed a search speed to adopt binary tree search.If the searching result takes a true value for the T, then use path andthe triangle slice in this cube to attain interaction point.If the interaction point exists, then return to latest interaction point, thealgorithm ends. Otherwise, re-place T for false.If T is false, then should step over current cube to continue to searchforward. While searching result takes a false for the T, the point locatean empty of match a node most to have common ancestry in this spacemesh and line octree. Obviously, including P₀ and not including thebiggest space mesh of any scenery slice. Its length is 2^B-1 .Space mesh front left descend ordinate is decided by equation (? ?).Whengetting interaction point is over failure but place T for false, then stepover a current mesh. It is easy to know that its length is 2Band frontleftdescendordinateisdecidedcorrespondingly.Exercise after crossingover one space mesh the path get into closetogetheranext spacemesh. Theexit ofthis current spacemesh orders,and order to sit a mark to reset according to the exit. The most simpleexit's algorithm is path with current six boundary surfaces of spacemesh to get the interaction point, but doing like this takes more andgreatly. If passing at each sit mark flat surface up cast shadow linearintercept and inclining rate is calculated in advance, then it canthrough discretion path to get exit point. After calculating the exitpoint's ordinate, let it be the new starting point, it repeatsabove-mentioned calculation process and until keep to the pathprojectionafieldavieworgettheinteractionpoint.2. Bounding box and basic geometrical element's interactiontest1).Boundingbox'sinteractiontest2).Basicgeometricalelement'sinteractiontesta.Thetriangle'sinteractiontestin3Dspaceb.Thetriangle'sinteractiontestin2Dspace...