Tham khảo tài liệu 'crc press - robotics and automation handbook episode 2 part 7', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | FIGURE Flowchart showing interconnection of the dynamics solver collision detector and interaction calculator. Collision Detector To calculate a global solution in a computationally efficient manner it is very common to handle the collision detection problem in two parts a broad phase which involves a coarse global search for potentially interacting surfaces and a narrow phase which is usually based on a fast local optimization scheme on convex surface patches. To handle nonconvex shapes preprocessing is performed to decompose them into sets of convex surface patches. However there exist shapes for which such a decomposition is not possible for example a torus. Broad Phase The broad phase is composed of two major steps. First a global proximity test is performed using hierarchies of bounding volumes or spatial decompositions for each surface patch. Among the most widely used bounding volumes and space decompositions are the octrees 36 k-d trees 37 BSP-trees 38 axis-aligned bounding boxes AABBs 39 and oriented bounding boxes OBBs 40 . During the global proximity test the distances between bounding boxes for each pair of surface patches drawn from all pairs of bodies are compared with a threshold distance and surfaces that are too distant to be contacting are pruned away. Remaining surfaces are set to be active. In the second step of the broad phase approximate interaction points on active surfaces are calculated. For example if the geometric models are represented by non-uniform rational B-splines NURBS control polygons of the active surface models can be used to calculate a first order approximation to the closest points on these surfaces. Specifically bounding box centroids of each interacting surface patch can be projected onto the polygonal control mesh of the other patch. Using the strong convex hull property of Copyright 2005 by CRC Press LLC NURBS surfaces one can determine the candidate span and interpolate the surface parameters from .
