Use collision detection in Direct3D programs

Almost all 3D games are inseparable from collision detection - whether collision detection between the objects, or the collision detection between objects and scenes. In the real world, you can't wear a wall naturally, so many people naturally neglect the process of detecting this process of collision when playing various 3D games. However, the process of collision detection is important. If you don't have it, you will fly unchanged in CS - if you consider gravity, you will keep down, until the number of symbols overflow (or you can't stand this long process. Leave the game). Collision detection is achieved when programming. Don't think that collision detection is done by the graphics card while displaying 3D images - this is a naive view - there is no hardware to support collision detection. After watching these, you may have an interest in collision detection, or you as a 3D programming enthusiast is looking for the principles and methods of collision detection, or have been found for a long time, I haven't found it. (I am a little poverty: P), So let's take a look at an algorithm that is very effective and easy to understand. This algorithm is a collision detection between objects and scenes. It requires your scene to be composed of a lot of triangles. At present, almost all 3D programs are composed of many triangles, so this is not a problem. In addition, you need to record the position of the object in the previous frame and the position of the current frame. This is also easy. In addition to these, every other requirement. Then let's take a look at it.

First, principle

First, calculate the position of the object at the time of a frame (current frame) at the time of the motion (current frame) according to the motion regular or user of the object (which does not consider the problem of collision detection) and then circulates each triangle in the scene. During the cycle, do the following: 1. Find the plane where the current triangle is located, we are called flat S. It is a panning that it can be proximally along the plane of the plane of the plane, indicating the distance between the object and the plane. 2, judging the position of the object in the previous frame and the current frame, the relationship between the newPosition and the plane S: If the previous frame is in front of the plane, and the current frame is behind the plane, as shown in the figure below:

Further 3. Otherwise, skip 3, 4, do 5.3, because the two frames of the object appear on the plane, indicating that the object passes through the plane S. But at this time, it can't say that the object has collided with the triangle because the plane is boundless, and it is necessary to further determine whether the object is within three sides of the triangle. Three sides of the triangle, doing vertical planes PS1, PS2, PS3. And make their normal to the interior of the triangle, as shown in the following figure:

In order to reflect the shortest distance that the object and triangle can be close, these three planes also need to make a panning L, but it is only the negative direction of its normal:

We will rely on these three planes to determine if the object is within the range defined in the triangular three sides. However, if the triangle has a very sharp acute angle, it will define the area excessively, as shown in Figure4. So we need two three planes PS4, PS5, and PS6 they are in parallel (Figure 5). It is easy to generate these three planes, just pull the PS1, PS2, PS3 to their normal positive directions to the opposite vertices, plus L.

Now, it is judge whether or not the object location is within these six planes. If so, do 4, otherwise, do 5.4, we have been able to determine the object with the current triangle collision, then correct the current frame NEWPosition , The movement of the object is parallel to the plane S. 5. We have been able to determine that the object does not have a collision with the current triangle. The next triangle is formed as a current triangle, returns to 1. When all triangles are traversed once, the position of the object is detected and fixed by collision. In this position, the objects and scenes are rendered, and the old position is the location of the current frame (OldPosition = newPosition). In summary, the principle of this algorithm is to give a triangular-determined whether the object is on the side of the triangle - and then judge whether the object is passed through the inner interior. Let's take a look at the specific implementation. Second, specific implementation in a specific implementation, we may encounter the following problems. First, how to get the plane where the triangle is located? A plane can be represented by the normal vector and its distance from the origin, suppose we have a triangular ABC, which is S, as shown below:

Its vertex position is three three-dimensional vector a, b, c. We first get a triangular method N :( Vector below represents three-dimensional vector, float indicates floating point scalar) Vector V1 = b - a 'is directed to the side vector V2 = C - a' by a point B by a point C Side vector. Vector n = normalize (v1 x v2) 'X represents the fork, pay attention to the fork will be in order, if V1 and V2 interchange, the result vector will be reversed. Normalize indicates that the result of the resulting result is set. The resulting N is a triangular method vector Vector Sn = n 'triangle method is also the method of plane S. Then, we calculate the distance of the plane and the origin SD: float sd = n * a' * represents point multiplication, calculation results The length of the projection of the triangular vertices A to the normal, namely the distance SD, is a scalar. With the normal and distance, you can represent a plane. If you want to pan the plane, simply modify the value of S.d. So, how do you judge the side of the object in the plane? It is only necessary to compare the position of the object position on the planar pattern and the D value of the plane. It is assumed that our object position is used to represent float dp = S.N * P 'points, and DP is the projection length of the object position on the plane S method N, which is a scalar. IF (DP - S.d)> 0, on the front of the plane. IF (DP - S.D) <0, on the back of the plane S. There is also a problem, how is it obtained by plane PS1, PS2, and PS3 mentioned above. This is not difficult, can be obtained from the following method (take PS1 as an example): vector ps1.n = Normalize (Sn x V1) 'plane S method to N and triangle side vector V1 fork and unit, result is PS1 .N represents the method of PS1. Float ps1.d = ps1.n * a - l 'Triangular vertex a on the projection length of the method of PS1, then minus the flat PS4 corresponding to the L. can be obtained: vector ps4.n = -PS1. N 'two plane normal relative float ps4.d = ps1.n * c - l' takes the method of PS4 with vertices C to minus L (# _ # These formula is really headache, I have tried I want to make them some of them.) Let us enter the substantive stage - the writing of the code. Third, writing code still remembers an article on DirectX Mesh optimization before recently? There is a very simple so-called "first person shooting" game - "no collision detection, no lighting, no lightmap, no BSP tree, no enemy (no AI), no weapon: God, no ! "Well, let us give it to collision detection now. Below is the three custom functions I have added to the program: collision (), precheckcollision () and checkcollision (). Where the collision () function completes the entire collision detection process. Different functions are called inside them. PrecheckCollision () mainly determines whether the object location (in the program is the position of the player) passes a plane. The checkcollision () function further determines whether the passing position is inside the triangle.

/ / =========================================================================================================================================================================================== ===== // Function Name: COLLISION () // Function: Complete collision detection // Remarks: Use Optimized Scene Grid Model // Parameter Description: // Player_State * LPPS: Player_State is the status of the player status // Customize the structure. The VNewPOS, // VoldPos member variable will be used for collision detection. // Function accepts a pointer LPPS for this structure. // LevelMap * LPMAP: levelmap is a custom structure representing the scene. // The M_PMESH member variable is a // id3dxmesh interface pointer, saving the network // of the map. / / -------------------------------------------------------------------------------------------- ----- HRESULT Collision (Player_State * lpPs, LevelMap * lpMap) {WORD * pIndexData; CustomVertex * pVertexData; D3DXVECTOR3 vNormal, vP1, vP2, vP3; FLOAT fdistance; if (lpMap == NULL) return E_FAIL; if (lpMap -> m_pmesh == null) Return E_FAIL; if (LPPS == NULL) RETURN E_FAIL; if (lpmap-> m_dwnumindices == 0) Return E_FAIL; if (lpmap-> m_dwnumvertices == 0) Return E_FAIL; in DirectX 8 graphics In the mesh model of the scene, the mesh model of the scene is composed. The vertex buffer saves all the apex information, while each of the three elements in the index buffer represents a triangle, and the value of these elements is the index number of the three vertices of the triangle in the vertex buffer. We can thus get the position of the three vertices of triangles. The following code locks the vertices and index buffers in the grid model and gets the pointer to them.

LPMAP-> m_pmesh-> lockindexbuffer (D3DLOCK_READOONLY, (Byte **) & pindexdata); lpmap-> m_pmesh-> lockvertexbuffer (D3DLock_ReadOnly, (Byte **) & pvertexdata);

Then, the triangles of the grid are traversed:

For (Word i = 0; i m_dwnumindices; i = 3) {Word a = PINDEXDATA [i 0]; // A: Triangle's first vertex index word b = pindexdata [i 1] ; // b: Triangular second vertex index word c = pindexdata [i 2]; // C: The index of the third vertex of the triangle D3DXVector3 V1 = PVERTEXDATA [B] .p - pvertexdata [a]. p; // v1: Vector D3DXVector3 V2 = PVERTEXDATA [C] .p - pvertexdata [a] .p; // v2: Vector D3DXVEC3CROSS (& Vnormal, & V1, & V2); // Forks to Triangle Method. D3DXVEC3NORMALIZE (& Vnormal, & Vnormal); fdistance = d3dxvec3dot (& vnormal, & pvertexdata [a] .p) 5.0F; // Verde A in the projection length, that is, the distance from the origin. IF (PrecheckCollision (LPPS, & VNORMAL, FDISTANCE) == 1) {// If the player passes the top IF of the triangle (CheckCollision (LPPS, A, B, C, & Vnormal, PvertexData == 1) {// If It is the location of the player in // to pass through the triangular three-sidide, so that it cannot wear a wall. LPPS-> VNEWPOS = VNORMAL * (FDISTANCE - D3DXVEC3DOT (& vnormal, & lpps-> vnewpos) 0.2);}} / / Otherwise, continue to cycle, determine the next triangle. } // The cycle is over, and the vertex and index buffer must be unlocked before exiting. LPMAP-> m_pmesh-> unlockvertexbuffer (); lpmap-> m_pmesh-> unlockindexbuffer (); RETURN S_OK;} The following is the code of function precheckcollision () and checkcollision ().

/ / =========================================================================================================================================================================================== = // Function name: precheckcollision () // function: Judging whether the player passes the current plane. // Parameter Description: // _player_state * LPPS: The status of the player, contains location information. // vnromal: Current plane method (unitized) // fdistance: Distance // return value of the current plane and origin: Returns 1 // otherwise return 0 if needed. / / -------------------------------------------------------------------------------------------- -INT PreCheckCollision (Player_State * lpps, D3DXVECTOR3 * pvNormal, FLOAT fDist) {float StartSide, EndSide; // calculate the old location and the player's plane distance StartSide = D3DXVec3Dot (pvNormal, & lpps-> vOldPos) - fDist; // calculate players New location and flat distance Endside = D3DXVEC3DOT (PVNORMAL, & LPPS-> VNEWPOS) - fdist; // If the old position of the player before the plane, the new location is behind the plane, / / ​​instead through the plane. IF (Startside> 0 && Endside <= 0) Return 1; Else Return 0;} // ============================= ==================================================================================================================================================== // Parameter Description: // _player_state * LPPS: The status of the player, contains location information. // a, b, and c: the index of the vertices of the triangle in the vertex // buffer. // d3dxvector3 * vnormal: Triangular Method // CustomvertEx * Pvertices: Pointer Pointer Pointer Pointer // Return Value: If the player passes inside the triangle, return 1 / / Otherwise return 0 / / ------- --------------------------------------- Int CheckCollision (Player_State * LPPS, Word A, Word B, Word C, D3DXVector3 * PVNORMAL, CUSTOMVERTEX * PVERTICES) {D3DXVector3 perplanenormal; // Vertical plane (perpendicular plane) method of vertical Fperpland; // Vertical plane and origin distance. D3DXVector3 V1; // Used to record the vector of the triangle current side.

/ / =========================================================================================================================================================================================== ============ // Check if the object is in the vertical plane // of the triangular first side AB and within the plane opposite it. // First calculate the AB edge vector of the triangle. V1 = pvertices [b] .p-pvertices [a] .p; // calculates the method of vertical planes of this side. D3DXVEC3CROSS (& Perplanenormal, Pvnormal, & V1); D3DXVEC3NORMALIZE (& Perplanenormal, & Perplanenormal); // guarantees the direction of the vertical side to point to the inside of the triangle. IF (D3DXVEC3DOT (& (Pvertices [C] .p-pvertices [a] .p), & perplanylmal) <0) perplanenormal = -perplanenormal; // calculate the distance from the vertical plane and the origin, and minus objects and triangles can be close The shortest distance. Fperpland = D3DXVEC3DOT (& PERPLANENORMAL, & PVERTICES [A] .P) - 5.0F; // Returns 0 if the object is in this vertical plane. IF (D3DXVEC3DOT (& LPPS-> VOLDPOS) -fperplatedist <0) return 0; // Since this vertical plane is parallel to its relative vertical plane, // is directly calculated directly to calculate the distance from the origin. Fperplatedist = D3DXVEC3DOT (& Perplanenormal, & PVertices [C] .p) 5.0F; // If the object is also opposite the opposite plane of this vertical plane, it returns 0. IF (D3DXVEC3DOT (& perplanenormal, & lpps-> voldpos) -fperplatedist> 0) Return 0; // ============================= =============================================================== // Lower within. // The step is basically similar to the above.

V1 = pvertices [c] .p-pvertices [b] .p; d3dxvec3cross (& Perplanenormal, Pvnormal, & V1); D3DXVEC3NORMALIZE (& Perplanenormal, & Perplanenormal); if (D3DXVEC3DOT (& (Pvertices [a] .p-pvertices [b]. p), & PerPlaneNormal) <0) PerPlaneNormal = -PerPlaneNormal; fPerPlaneDist = D3DXVec3Dot (& PerPlaneNormal, & pVertices [b] .p) - 5.0f; if (D3DXVec3Dot (& PerPlaneNormal, & lpps-> vOldPos) -fPerPlaneDist <0) return 0; fPerPlaneDist = D3DXVEC3DOT (& Perplanenormal, & PVertices [a] .p) 5.0F; if (D3DXVEC3DOT (& Perplanenormal, & LPPS-> VOLDPOS) -fperplatedist> 0) Return 0; // ============ ======================================================= // It is then the vertical plane of the side CA and its relative plane. V1 = pvertices [a] .p-pvertices [c] .p; d3dxvec3cross (& Perplanenormal, Pvnormal, & V1); D3DXVEC3NORMALIZE (& Perplanenormal, & Perplanenormal); if (D3DXVEC3DOT (& (pvertices [b] .p-pvertices [c]. p), & PerPlaneNormal) <0) PerPlaneNormal = -PerPlaneNormal; fPerPlaneDist = D3DXVec3Dot (& PerPlaneNormal, & pVertices [c] .p) - 5.0f; if (D3DXVec3Dot (& PerPlaneNormal, & lpps-> vOldPos) -fPerPlaneDist <0) return 0; fPerPlaneDist = D3DXVEC3DOT (& Perplanenormal, & PVertices [b] .p) 5.0F; if (D3DXVEC3DOT (& Perplanenormal, & LPPS-> VOLDPOS) -fperplatedist> 0) Return 0; // If the object is except for any six planes above, then the function I have already returned 0. // If it has not returned here, it means that the object is within six sides, / / ​​should return 1. Return 1;}

Note: The above three functions are written in accordance with the principles of the algorithm, although it is normal in my procedure, but because of the limited levels, it is inevitable that there will be omissions, and because it is written for routines, Not very good. However, the algorithm of this collision detection in the function is still relatively faithful. In summary, the algorithm is further illustrated. Some improvements are above, we have always expressed the minimum distance from the object and the plane. However, this is equal to seeing the object as a sphere, and does not reflect some of the characteristics of the object shape. For example, the length and width of the body are greater than high. When collision detection, it is best to see a high ellipsoid. A simple way to solve this problem is to calculate the minimum distance of the object and the plane according to the triangular normal of the desired judge, the steep the triangle, the smaller the distance. The specific algorithm will be given in the reference. About routines and source code used herein can click here to download. Due to time and level relationship, this routine is far from being perfect, so it does not have good versatility, and some errors may be included. To run the program, you need DirectX 8 or above. To compile the source program, you need DirectX 8 or more version of the SDK. (There is downloaded on this site download area). Control in the program: W Backward S back A to left translation D to the right flush up the arrow up arrow drop ESC to exit the mouse control direction Mouse right key

The procedure about the reference this article is the algorithm of the "Collision Detection and Collision Handling" section of "Physics In BSP-Trees" section in the "Binary Space Parts" section of Samuel Ranta-eskola's "Binary Space Part In" For Direct3D, only the algorithm of the pseudo code representation is given. This author has made a little modification on some of these parts. This reference is an Adobe PDF format, please click here to download.