3d游戲碰撞檢測和響應(yīng)

1、Improved Collision detection and ResponseKasper Faucrbykasperperoxide.dkhttp: / / www. p croxi cle. cl k25th July 2003Contents1 Introduction31.1 Previous work 31.2 The algorithm 31.3 How to read this document 42 Vector spaces52.1 Definition of a vector space 52.2 Case study: /?3 62.3 Coordinates 72.

2、4 Ellipsoid space 73 Collision detection93.1 Ovendew 93.2 Checking a single triangle 113.3 Colliding with the inside of a triangle 133.4 The sweep test 143.5 Tn summary 164 Collision response184.1 The sliding plane 184.2 Sliding the sphere204.3 Gravity 224.4 In summary235 Conclusions25ACalculating t

3、he normal to a regular surface27BThe plane class32CUtility functions34D Solving quadratic equations35E Code for collision step3744F Code for response step2Chapter 1Introduction1.1 Previous workThis paper describes an updated version of the collision detection and response algorithm 1 first presented

4、 in |FauO()|. Some of the material has been copied directly from that article but the entire section on the collision detection step has been rewritten using a swept sphere technique as described in |Rou03|. This paper has been written in a way so it shouldirt be nessesary to read to any of the refe

5、renced papers but if soniething seems unclear, in particular regarding the swept sphere technique, then I encourage you to read Rouwes paper as it might go into more details oil certain aspects of the algorithm. The response step is still based partly on the ideas first presented in |Net()()| and pa

6、rtly from my own work.This time a demo with full source will eventuallv be available at: littp;/vv ww.clr-uoilc.coin. The dcino will most ly be dune by a friend of mine, Matt Ostlund also known by some as Rhone Ranger with probably just a little intervention by myself in the core collision code. So

7、keep cin eye on his site as well. A huge thanks to him for taking on this task!1.2 The algorithmThe algorithm presented in this paper handles collision detection against arbitrary meshes stored as a so-called polygon soup. When a collision is detected the algorithm will slide the moving entity along

8、 the obstacles as it is typically seen in 3d computer games. The moving entity is approximated with an ellipsoid which gives a fairly tight fit for most humanoid or animal shapes Ellipsoids have a very friendly* shape that allows them to slide smoothly of the obstacles they collides against which is

9、 a good thing in a 3game where the i)layer does not want to get stuck against a hard egde in the middle of a fast-paced battleThis updated version of the algorithm fixes in particular the problem where colliding against triangle edges could cause the original algorithm to fail resulting in the pkiye

10、r being stuck or fall tlirough the world geometry.1.3 How to read this documentFirst of all let me say: this stuff is certainly not easy! It/ll take a long time to understand correctly and probably several readings of this text. So give Yourself time to fully understand what's written in a secti

11、on before moving on to the next. To fully understand the theory presented you will need to have ci fairly good understanding of linear algebra - i.e. vectors, matrices, vector spaces and the like. This paper is split up into two major parts one on collision detection and one on collision response. N

12、ow what s the difference? Collision detection deals with finding out whether or not we41 bump into something when we move our ellipsoid though 3d space and if so, what do we hit and where? Collision response deals with what to do when a collision do occur Do we stop? Do we continue movement in anoth

13、er direction ? What do we do? The collision response step is very important for the overall feel of your game.Fll assume tlicit the niu«h being chucked for collision i« placed in the same space as the player - in world space In other words I ll assume that each mesh has the identitv matrix

14、 as its world matrix. If this is not the case then it's easy to apply the actual world matrix to the vertices before we check the triangles for collision.Chapter 2Vector spacesThis algorithm makes heavy use of non-standard vector spaces to simplify certain calculations Those of vou already famil

15、iar with the definition of vector spaces and most importantly with change-of-basis matrices to move between spaces can skip most of this chapter and only cast a glance on the section on the “ellipsoid space". The rest of you read on but be aware that this is only a very quick crash-course on th

16、e subject. A full explanation would include too much math and is beyond the scope of this paper iuiyway.2.1 Definition of a vector spaceMost of you will never have encountered any other vector spaces than the standard two and three dimensional spaces we usually think of from school math. These are c

17、alled R? and R3 and are those we use in a ustandardn coordinate system (like the one D3D or openGL operates in).As it turns out we can easily define vector spaces or 4, 5 or even infinitely many diinensions by listing a few rules (or axioms) which every vector space must follow R> ciiid R3 follow

18、s these rules too! The rules are: It must be closed under addition and scalar multiplication .This means that given two vectors from the vector space, say X and V, then Z = X 4- / must also be in the same space. For any real number 廠讓 X is in the space then so must rX IiifoTinnlly said we cannot eve

19、r 叫eave" the vector space using these operations. It must contain a zero-vector 嶺 so for all vectors X in the space Vq 十 X = X For all vectors X it must also be true that OX = % It must follow standard mathematical rules such as the associative law, commutative law etc.Now Fll introduce to you

20、the concept of a linear combination of vectors from a vector space. Said in words it 's what you get if you combine vectors from the space using addition and multiplication with scalars (real numbers). For example if you have vectors X、Y and Z you could combine them like this: V = 2X + 4Y + (3)Z

21、 and then V would be a linear combination of the vectors X，Y and ZOK, what can we say about V? Well, from rule number 1 above we can see that V must belong to the same vector space as X, V and Z Cool, that/s what we need to define what a basis for a given vector space is.A basis for a vector space i

22、s a collection of vectors, belonging to the space, for which the following holds: Every vector in the vector space is a linear conibiiiatioii of vectors from the basis. Each of the vectors in the basis can not be made from a linear combi- nation of the other basis vectorsThe miniinal number of vecto

23、rs licccssarv to create a basis for a vector space is equal to the dimention of the space. So how many vectors are in the basis for A3? Or RQ2.2 Case study: R31 think it's time to take a break from the abstract definitions above and look at a fcimiliar example. After reading and luiderstanding t

24、his example you should understand the stuff above well enough fur this paper. Let us look at the standard 3D vector space we know as Is it a vector space? WelL we check the rules (very informally). Is it closed under addition? If we have two vectors from say X = (2,5,4) and Y = (6.3,8), is Z = X + Y

25、 = (8, & 12) in /?3? Yes, we believe this is the case.For any real niunbcr r, say r = 2, is rX = (4.10.8) in R3? Check! First rule holds.Is there a zero vector then? Yes, wc use Vq = (0 0 0) and the rule holds. Checking the third rule involves a lot of tedious checks so fll just mention the comm

26、utative kiw saving that X -Y = y + X Obviously that, holds for vectors from R3.So R3 is a vector space! What is its basis? The basis for R3 is called the "standard basis” and contains 3 vectors (ei.e2,e3). What are those vectors? They are: ex = (1,0.0), e2 = (0,1,0) and e3 = (0,0,1).WclL if tha

27、t is indeed the basis for R3 then we should be able to derive any vector from as a linear combination of those vectors right? Well, well lkive to convince ourselves about this so given any vector from R3、sayV = (5 2、4), can we derive this from a linear combination of (ei,e2. e3)? Yes, because in thi

28、s case 5®+2切+4£3 = 5(1,0.0)4-2(0,1.0)4-4(0,0.1) = (5,2,4). It?s clear that ® cannot, be made from e2 and e3 because no matter how you combine them the first vector component would still be zero right? Same can be said for the other two basis vectors.2.3 Coorclina tesNow for an importa

29、nt (lefinition: the coordinate. The coordinate for a point in a vector space is build from the scalars that are multiplied to the basis vectors in the linear combination for the point hi the example above the pointV has the coordinate (5.2,4)- This might seem obvious because we're used to workin

30、g with R3 but make sure you see why that is indeed its coordinate:V = 5ei + 2&2 + 4匂 so the scalars are (5,2,4) - its coordinate.2.4 Ellipsoid spaceI3y now you should be convinced that R3 is a vector space following the axioms for general vector spaces It should also be clear that other vector s

31、paces could exist - even other spaces of 3 diineiisions. For example what about the vector space macle from the basis 5 = (2,0,0), v2 = (0,2,0) and V3 = (0,0.2). W hich vectors or points does this space contain? Tlie same as B3 of course but with different coordinates!Given a point (2.2,2) in R3 - w

32、hich coordinate would that same point have if we converted it into our new space? It would have the coordinate (1,1,1) because: lvi + lv2 + lv3 = (2.2,2).fhis is exactly the trick we'll use in this paper to create a very special vector space which has the property that the ellipsoid vve re using

33、 to approximate our player with becomes a unit-sphere in that space! A unit sphere is a sphere with radius = 1 but ifs also an ellipsoid with radius vector (1：1,1), right?So how do we create such a space? Well, well have to come up with a basis for the space If the ellipsoid is defined by a radius v

34、ector of (x. y.z) then well just chose the basis to be: v = (x, 0.0). v-2 = (0, y. 0) and = (0,0. z). Now in this space the ellipsoids radius vector will be (1, L 1) - it 11 be a unit sphere as wc desired. You can check if tlmt choice of basis really defines avalid vector space if you want or you ca

35、n just take my word for it. Well call our newly defined vector space for the ''ellipsoid space'.The last thing we need to know is how to translate a point from R3 into the ellipsoid space. We?re in luck, because it turns out that because a linear coinbination is a linecir function we Cci

36、ii get away with just describing what to do with the 3 basis vectors (ei,e2,e3) (remember these from above?).We find that if we use the basis(522,5)from above, then:ei = -vi + OV2 + OV3.(2.1) /e2 = Ovi 十-v2 十 0v3.(2.2)ye3 = Ovi + 0f2 4- -v3.(2.3)zWe list the coordinates for ei,e2 and 63 as column ve

37、ctors in a 3x3 matrix and get a “change of basis” matrix which has the effect of translating any vector from R3 into the ellipsoid space.The matrix looks like this:CBM =ITO oo lro(2.4)As long as we stick to defining new spaces for which the change of basis matrix looks like above (only has entries o

38、n the diagonal) then wc can simplify the multiplication of a vector to the matrix into just a component-wise multiplication For example we translate a vector V into our ellipsoid space like this (remember (xyz) is simply the radius vector for the ellipsoid defining the space):111VVe = CBM * V = (-,-

39、)V = (2.5)y z(x.y.z)At mentioned above this only holds for change of basis matrices which only has entries 011 the diagonal and those spaces just happens to include those you get from R3 when you multiply each basis vector(6©,內(nèi))with a constant If you check back, thafs exactly wliat we do to ach

40、ieve the scaling trick* aboveChapter 3Collision detection3.1 OverviewOK, enough talk lets get started! So, we have our guy we wish to move around the world HcM represented by an ellipsoid with a center which we will consider his position and a radius vector defining the ellipsoids size along the thr

41、ee axis. Sec Figure 3.1.radius =Figure 3.1: Ellipsoid radius vectorVe move our guy though the world by applying a force to him in sonic direction. This is represented by a velocity vector. We wish to move the ellipsoid through the world so its new position equals its current position plus the veloci

42、ty vector. See Figure 32But we doirt know if we can do that though as there might be something in his way - one or more of the triangles making up our world might be obstructing the path Wc have no chance of knowing exactly which triangle he'll hit, so to some degree well have to check them all

43、(it is possible, and reconnneiided. to split up large meshes into ail octree which can then be queried to check only those triangles close to the player).Also we cannot stop once we find one triangle he'll hit - well have to check all potential colliders to find the closest collision. Figure 3.3

44、 shows what happens if we detect a collision with triangle A and then stops without checking the rest, including for example triangle B.First of all well reduce the complexity of the problem greatly by working in the ellipsoid space that Fve discussed above in section 2.4 - from now on referred to a

45、s eSpace As yoifll recall this is a vector space in which the ellipsoid is really a unit sphere so from now on we?ll only consern ourselves with detecting collision between a triangle and a unit sphere. To work in cSpacc we have to translate the tricingles, the velocity vector and the player positio

46、n from R3 into the space by applying the CBM matrix listed above. Once our collision detection routine has finished the result will also be in eSpace but we can translate the result back into R3 by applying the inverse of the CBM matrix to the result V here the transition from R3 to eSpace was clone

47、 by a division of the point with the ellipsoid radius vector it turns out that the transition back from eSpace to /?3 can be rc<luced to a multiplication of the point with the ellipsoid radius vector.As it turns out wc need two things for the collision response step in thetnaiiglc LJtriangle AFig

48、ure 3.3: We must, check all trianglescase of a collision: File position where the sphere hits the geometry. The distance along the velocity vector that the sphere must travel before the collision occurs.So to check a single triangle for collision well first have to figure out if a collision occurs a

49、nd then if that is the case the algorithm must be able to calculate the two things above.3.2 Checking a single triangleSo given a triangle defined by points p2 and p:i in cSpace and in clockwise order we want to check for collision against a sphere positioned at base Point and moving along a vector

50、velocityIf we parameterize the movement of the sphere along the velocity with t then well get a formula for the position of the sphere that looks like this:C(t) = basePoint + £ * velocity t 0,1(3.1)A sphere in 3d can be defined as a position and a radius (which in our case will be 1 because we&

51、#39;re working in eSpace) For a moving sphere the radius will remain constant but the position will of course change. Thus the formula above gives us the orientation of the collision sphere at any time t moving “l(fā)ong the velocity vector. This is what is meant by a swept sphereThe first task is to ch

52、eck if the swept sphere will intersect with the triangle plane. If this is not the case then it certainly calf t collide with the triangle, can it? So we construct the plane trianglePlane from the points of the triangle (see Appendix B for help with this). If we have the normalized plane normal N an

53、d the plane constant Cp then we can calculate the signed distance from a point p to the plane as:SignedDistancep) = N p + Cp(3.2)If the swept sphere intersects with the triangle plane then at some time 心 it'll rest on the front side of the plane and at some other time 仃 itTl rest on the back sid

54、e. At all time values t G Joi the swept spliere will intersect with the plane The time is exactly when the signed distance from the swept sphere to the triangle plane is 1 so we can calculate it like this:Sig lied D i stance (C (f 0) = 1 =>N (basePoint + £()* velocity) + Cp = 1 =>N basePo

55、int + (N vdocity) + Cp = 1 =>to * (N velocity) + SigriedDistance(basePoint) = 1 =>1 Signed Di st ance(base Point)0N velocityThe time is when the signed distance from the swept sphere position to the triangle plane is 1 so similar to above it can be calculated as:1 SignedDistance(basePoint)t=N

56、velocityNow, if both and is outside the range 0.1 then we know that the swept sphere will not at any point, along the velocity intersect with the plane and thus it cannot collide with the triangle. Otherwise we know that a collision with the triangle will occur at a time tCoiiision Notice that there

57、 is a special case if N - velocity = 0 then we obviously caift use the formulas above But when does this happen? Tliat happens when the velocity vector is perpcndicukir to the plane normal in other words when the sphere is travelling in parallel to the triangle plane. In this case there are two poss

58、ibilities, either tlie absolute distance from basePoint to the triangle plane is smaller than 1 and the sphere is embedded in the triangle plane If this is the case then we set = 0 and 仃 =1 as the swept sphere intersects the plane at all times. If the distance is greater than 1 then we know that a c

59、ollision cannot ever happen and we can return early from the fiuiction.Now that, wc have found the two time values t()and tA there are three cases for a potential collision: The sphere can collide with the inside of the triangle. Die sphere can collide against one of the three vertices of the triangle. The s