您好,欢迎光临本网站![请登录][注册会员]  
文件名称: Linear Algebra & Trigonometry
  所属分类: C++
  开发工具:
  文件大小: 51mb
  下载次数: 0
  上传时间: 2019-03-04
  提 供 者: qq_30******
 详细说明:Linear Algebra & TrigonometryContents 25 Collision Detection 25.1 Broad phase collision Detection 25.2 Mid phase coll 25. 3 Narrow Phase Collision Detection 17 25.4 Collision Detection with rays 25.5 Dynamic Cd Using bsP Trees 25.6 Time-Critical Collision Detection 25.7 Deformable models 25.8 Continuous collision detection 31 25.9 Collision Response 25.10 Particle 25.11 Dynamic Intersection Testing Referenc 43 Bibliography 45 d 51 Chapter 25 Collision detection To knock a thing down, especially if it is cocked at an arrogant angle, is a deep delight to the blood eorge santayana Collision detection( Cd)is a fundamental and important ingredient in many computer graphics applications. Areas where CD plays a vital role include virtual manufactur- ing, CAD/CAM, computer animation, physically based modeling, games. Hight and vehicle simulators, robotics, path and motion planning(tolerance verification),assem bly, and almost all virtual reality simulations. Due to its huge number of uses, CD has been and still is a subject of extensive research Collision dctection is part of what is often referred to as collision handling, which can be divided into three major parts: collision detection, collision determination and collision. respon se. The result, of collision detection is a. boolean saying whet, her two or more objects collide, while collision determination finds the actual intersections between objects; finally, collision response determines what actions should be taken in response to the collision of two objects Consider an old-style clock consisting of springs and cog-wheels. Say this clock is represented as a detailed three-dimensional model in the computer. Now imagine that the clock's movements are to be simulated using collision detection. The spring is wound and the clock's motion is simulated as collisions are detected and responses are generated. Such a system would require collision detection between possibly thousands of pairs of objects. Another challenge would be to simulate all the ants and all the pine needles in an anthill. a brute-force search of all possible collision pairs would be incredibly inefficient and so is impractical under these circumstances. An example of complex collision detection is shown in Figure 25.1 To cope with large scenes, it is common to divide a collision detection system into three phases. Broad phase CD works on a per object level and finds pairs of objects whose BVs overlap(Section 25. 1). Mid phase CD(Section 25. 2)continues the work and detects parts of two objects that Inlay overlap, and finally, larrow phase CD (Section 25.3 )works on leaves of primitives or on convex parts of objects. These three hases can be used together in a large CD system 25. Collision Detection Figure 25.l. Rigid-body collision detection using tens of thousands of small geometrical objects mostly boxes, torii, and an occasional ragdoll. (Images generated using the PhysX Kapla demo courtesy of NVIDIA Corporation In Section 25. 4 we discuss simple and extremely fast collision detection techniques that are useful in some scenarios. The main idea is to approximate a complex ob ject using a set of line segments. These line segments are then tested for intersection with the primitives of the environment. This technique is sometimes used in games Another approximative method is described in Section 25.5, where a bsP tree rep resentation of the environment is used, and a cylinder may be used to describe a charactcr. Howevcr, all objects cannot always bc approximated with linc scgmcnts or cylinders, and soine applications Inlay require Inore accurate tests Time-critical collision detection is a technique for doing approximate collision de- tection in constant time. and is treated in Section 25.6. Then follows sections on deformable models, continuous CD, collision response, and finally, how to handle par- ticles. in Section 25.10 It must be pointed out that performance evaluations are difficult in the case of cD since the algorithms are sensitive to the collision scenarios, and there is no algorithm that per forIns best in all cases 33. Also, Iote that CD is often perforMed on the CPU side, but due to the generality of GPUs, all algorithms can be executed on the GPU s well. In gcncral, algorithms nccd to bc adapted to the particular architccturc's memory system and feature set in order to maximize performance To conclude, we present some dynamic intersection tests. Determining whether two moving objects collide during a given duration adds literally another dimension to the problem: time. This final section provides common tests for various primitive combinations and tools for deriving more complex interactions 25.1. Broad Phase Collision Detection Object transformations Broad phasc Overlapping objects collision Mid phase Simulation (object st Colliding arrow Collision pl response convex parts) Figure 25.2. A collision dctection systcm that is fcd ob jcct transformations using somc kind of simulation. All objects in a scene are then processed by broad phase CD in order to quickly find objects pairs whose bounding volumes overlap. Next, the mid phase cd continues to work on pairs of objects to find leaves of primitives or convex parts that overlap. Finally, the CD system performs the lowest level operations in the Ilarrow phase, where onle can compute priImlitive-priInitive intersections or use distance queries and then feed the result to collision response 25.1 Broad Phase Collision Detection In this section, we describe several broad phase Cd algorithms. Ilowever, first we illustrate the broad, mid, and narrow phase of Cd in Figure 25.2, which is a two- level CD system [16 where the last phase has been split up into a mid and a narrow hase The target is large-scale environments with multiple objects in motion. The broad phase of this system reports potential collisions among all the objects in the environment. Next, the mid phase works on pairs of objects and attempts to leaves of primitives that potentially overlap or convex parts that overlap, for example The marrow phase computes prilnlitive-priInlitive intersections or uses distance queries to make sure that objects do not penetrate each ot her. Finally, collision response (Section 25. 9) is computed, whose result is fed into a simulation subsystem that can compute final transforms for each object Since a scene may contain thousands of moving objects, a good CD system must handle such situations well. If the scene contains n moving and m static objects, then a naive method would perform 25 object tests for each frame. The first term corresponds to testing the number of static objects against the dynamic(moving)objects, and the last term corresponds to testing the dynamic objects against each other. The naive approach quickly becomes expensive as /I and T, rise. This situation calls for SIllarter Inethods, which are th subject this section 25. Collision Detection The goal of each phase is to minimize the amount of work passed to the subsequent phase, i. e, we want to minimize pairs of objects, primitives, convex parts, etc, that are fed to the next phase. At the first phase. testing is done On the object level anld it is therefore often called broad phase CD Most algorithms for this phasc start by enclosing cach object in a BV, and then apply some technique to find all BV/BV pairs that overlap. A simple approach is to use an a.xis-a. ligned bounding box(AaBB) for each object. To avoid recomputing this AABB for an object undergoing rigid-body motion, the AABB is adjusted to be a ficed cube large enough to contain the object in any arbitrary orientation. The fixed cubes are used to rapidly determine which pairs of objects' bounding volumes are disjoint. Sometimes it may be better to use dynamically resized AABBs, which are fast to recompute for oricnted boxes, spheres, and capsules, for cxamplc Spheres call be used instead of fixed cubes. This is reasonable, since the sphere is the perfect Bv with which to enclose an object at any orientation. It is also possible to use the apex map 53(Section 22 13.4). In the following, we describe three algorithms for broad phase cd, namely, sweep-and-prune, using grids, and using BVHs. An entirely different method is to use the loose octree structure presented in ection 19.1.3 25.1.1 Sweep-and-Prune We assume that each object has an enclosing AABB. In the sweep-and-prune tech nique 3, 62, 93, temporal coherence, which often is present in typical applications, is exploited. Temporal coherence mcans that objects undergo rclativcly small (if an changes in their position and orientation froin fraile to fraile (and so it is also called frame-to-frame coherence). Lin 62 points out that the overlapping bounding box problem in three dimensions can be solved in O(nlog n+k) time(where k is the number of pairwise overlaps), but it can be improved upon by exploiting coherence and so can be reduced to O(n+k) However, this assumes that the animation has a fair amount of temporal coherence If two AABBs overlap, all three one-dimensional intervals(formed by the start and enld points of AABBs) ill each main axis direction Illust also overlap. Here, we will describe how all overlaps of a number of one-dimensional intervals can be detected cfficicntly when the framc-to-framc coherency is high. Givcn that solution, the thrcc dimensional problem for AABBs is solved by using the one-dimensional algorithm for each of the three main axes Assume that n intervals(along a particular axis) are represented by si and ei where si x ei and 0
(系统自动生成,下载前可以参看下载内容)

下载文件列表

相关说明

  • 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
  • 本站是交换下载平台,提供交流渠道,下载内容来自于网络,除下载问题外,其它问题请自行百度
  • 本站已设置防盗链,请勿用迅雷、QQ旋风等多线程下载软件下载资源,下载后用WinRAR最新版进行解压.
  • 如果您发现内容无法下载,请稍后再次尝试;或者到消费记录里找到下载记录反馈给我们.
  • 下载后发现下载的内容跟说明不相乎,请到消费记录里找到下载记录反馈给我们,经确认后退回积分.
  • 如下载前有疑问,可以通过点击"提供者"的名字,查看对方的联系方式,联系对方咨询.
 输入关键字,在本站1000多万海量源码库中尽情搜索: