Collision detection is a very important technical point in game development. Optimizing collision detection performance is an integral part of improving the game experience. The developer “My Name is 98K” has written a lightweight collision system to improve the collision performance issues and package problems encountered by 3D games on different platforms. See the end of this article for the download.
CollisionMaster - Lightweight Collision System is a high-performance, lightweight 3D collision manager for Cocos Creator 3.4 and above, providing an efficient collision system and ray detection system for Mesh models and basic geometry to improve 3D collision detection performance and reduce package size (especially for H5 platforms) on different platforms.
Let’s start by looking at a few sets of application results through the online experience.
Scenario 1, Crash Test
Scenario 1, 1000-ray test
Scenario 2, Crash Test
Scenario 2, 1000-ray test
In this article, we will introduce the functions and usage of the most important custom collision system in CollisionMaster, as well as its implementation ideas and technical points.
Functional Features
The main functional features of the CollisionMaster are.
- Multi-object scene management: Octree, for efficient division of scene objects for queries.
- Model triangulation management: Kdtree, efficient partitioning of object surfaces for querying.
- General 3D collision calculation: GJK+EPA, accurate calculation of corrected objects after the collision.
- 3D Character Controller: Free movement of 3D objects under scene collision system.
- Efficient ray detection: accelerated ray detection based on Octree and Kdtree.
We compare 98K and Bullet in an HTML5 environment, PhysX (not involved in comparison due to Cannon’s imperfect support for mesh colliders).
| CollisionMaster | Bullet | PhysX | |
|---|---|---|---|
| Size | 50kb | 1.5MB | 5MB |
| Function | Some | Complete | Complete |
| Platforms | Full Support | Full Support | No Support for Mini-games |
Although compared with Bullet and PhysX, CollisionMaster is not comprehensive enough, but in the games of MMO, SLG, FPS, and other 3D scenes that need to use 3D collision detection and ray detection, the functions provided by CollisionMaster can meet the needs at present, and CollisionMaster is lighter and a bit easier to use so that it can replace Bullet and PhysX.
How to use
The 3D parkour game demo created by iwae some time ago uses CollisionMaster, so let’s take this as an example to see how this system can be used in an actual game project and how it works.
Source Code Download
Play it online
http://learncocos.com/jare/?v=1.01
The game scene has over 1 million surfaces and irregular terrain, so that the overall overhead would be higher with Bullet+Mesh Collider, so iwae used CollisionMaster to get better performance.
Compared to Bullet Mesh Collider’s disadvantages of full initialization and troublesome setup, CollisionMaster’s Mesh Collider can be said to be a key setup.
We can make one small script that adds a CollisionMaster collision component to all the meshes in the editor environment.
Then add all objects with Object3D collision components to our main scene below.
Enter the scene and then build it.
If you need to add or delete collision bodies later, you can do so by using the methods in World.
Also, CollisionMaster provides ray detection. We can ray detect the ground to handle logic such as jumps.
Another feature of the CollisionMaster is the use of simple mathematical formulas. This part allows for fixed-point processing and facilitates online games to handle frame synchronization, which developers have secondarily developed.
Technical Points
The following section briefly describes the technical implementation points of the custom collision system in CollisionMaster and thoughts and reasons for choosing the current optimization solution.
Before you build a wheel, you must understand how it’s composed to modify it better.
Functional hierarchical structure diagram
The physics engine’s basic process of collision detection consists of three parts.
- Board-Phase (rough screening of collision pairs)
- Narrow-Phase (exact calculation of collision pairs)
- Resolve-Phase (correction of collision velocity position)
Board-Phase
The goal of the Board-Phase is to improve the efficiency of subsequent collision detection by quickly eliminating object pairs that are unlikely to collide. Spatial segmentation is the most 0important part of this phase. In game development, we commonly use various spatial data structures to speed up the computation.
Multinomial trees: quadtrees and octrees
| Build tree | Check | Space | Increase | Ray Trace | Application | |
|---|---|---|---|---|---|---|
| Quadtree | Quick | Medium | Large | support | Quick | 2D |
| Octree | Quick | Medium | Large | Support | Convenient | 3D |
Quadtree
Quadtrees are a very common 2D collision detection method, and there are a variety of implementations. However, attention should be paid to optimization details in the concrete implementation to control the tree-building time consumption and tree-building space size, especially in the JavaScript environment. However, quadtree ray detection and region detection are more efficient, and the tree is updated quickly, generating multiple divisions of objects and taking up a lot of space.
Octree
Although octrees are not as accurate as BVH (improved by available state compression) and take up more space (overdivision), they are very fast to build and add/delete and are suitable for object filtering. Currently, CollisionMaster uses an octree for spatial partitioning of enclosing model boxes. It is more cost-effective to build a tree simply and efficiently than to build an exact computational tree (e.g., BVH tree building can be computationally intensive). The disadvantage is that the quadtree, ray detection, and region detection are faster, the tree is updated quickly, generating multiple divisions of objects, and the space occupation becomes quite large.
Binary trees: BVH, BSP, k-d
| Tree building | Check | Space | Increase | Ray | Verbal | |
|---|---|---|---|---|---|---|
| BVH tree | Medium | Quick | Small | Support | Quick | 2D/3D |
| BSP tree | Slow | Quick | Small | No Support | Quick | 2D/3D |
| k-d tree | Quick | Medium | Small | No Support | Convenient | 2D/3D |
BVH
The quadtree and octree divide the objects by the average space. The division algorithm is simple, while BVH divides the space of the current set of objects, pursuing a relatively balanced size of the left and suitable spaces without intersection. BVH builds a general binary tree, and the division algorithm is complex.
Mainstream physics engines have adopted BVH because of its complete functional support, high accuracy of lookup, and good performance. But its consumption is high to maintain the balanced tree when building the tree and adding, deleting, and changing. For this problem, there are some temporal space optimization methods to achieve optimization by reducing additions and deletions, and interested parties can refer to the implementation methods in the major physics engines.
BSP
BSP (Binary Space Partitioning Tree) is a very classic, first used in the famous game DOOM in 1993. Early games also used BSP for terrain collision. BSP is usually calculated to get a reasonable arbitrary angle slice or normal, and then the space is divided. The standard BSP is efficient but time-consuming for tree construction, usually pre-processed by the editor, and more suitable for static models or static scenes.
k-d tree
The k-d tree is a special type of BSP tree that divides the model based on three dynamically computed axes. k-d trees may not be as accurate compared to BSP. Still, the tree-building time is significantly reduced, and they are suitable for use because of the simplicity of the algorithm for dividing the axes. Currently, CollisionMaster uses the k-d tree approach to maintain the triangle data of the model for collision and ray detection.
Other: SAP
| Tree building | Check | Space | Increase | Ray | Verbal | |
|---|---|---|---|---|---|---|
| SAP | Quick | Medium | Small | Support | Medium | 2D/3D |
SAP
SAP (Sweep And Prune), also known as the sweep method, is a common collision detection method for physics engines.SAP is relatively lightweight, faster to add and delete, objects are not divided multiple times and is very fast for static models. Its only drawback is that the performance is less stable, only a single axis can be scanned at a time, and sometimes a large number of objects are projected to overlap, resulting in unstable queries. And ray detection and area detection need additional extensions to optimize. Performance is generally not as convenient and efficient as the tree structures above.
Narrow-Phase
In this phase, we need to accurately calculate these possible collisions after filtering to determine whether they have collided and, if so, to calculate details such as collision points and collision normals.
Geometric calculation
Mathematical methods, which determine collisions from a separation perspective, are generally used for high-speed collision calculations between common geometries. Good physics engines are essential to these mathematical methods and can be found in all major engines.
GJK + EPA
Convex packet algorithms explore collisions from overlapping perspectives. The core of the principle of GJK is that when two objects overlap, they must have a coordinate subtracted from the origin. After GJK detects the collision, it uses EPA to further calculate the penetration distance to the collision point and collision normal under the data constructed by GJK.
Basically, all mainstream physics engines use GJK+EPA, which can greatly improve the performance of collision computation when mixed with the previous geometry and mathematics methods. 98K also uses a mixture of the above two methods, supporting the calculation of basic geometry models and the calculation of triangulated or convex-wrapped mesh.
Resolve-Phase
In the previous phase, we determined whether collisions occurred and the details of the collisions. The final phase is to correct their positions and velocities. This process is very time-consuming, and 98K currently provides only simple and efficient fixes, focusing more on solving existing collision performance problems.
CollisionMaster Optimization Solution
The physics engine is a complex and complete process. There is no way to split it up functionally, so there is a certain amount of unnecessary performance consumption, such as in the Resolve phase, and a large number of necessary variable cache calculations in the process. The physics engine code is written in a way that is not too aggressive in terms of robustness, readability, and the usage of caches.
In some projects - such as lightweight RPGs, MMOs, and FPSs - we often need efficient collisions and corrections. We do not need an entirely realistic physics simulation (if you only need simple gravity effects or collision effects, you can usually just implement the simulation yourself).
Therefore, CollisionMaster optimized several modules of the physics engine in terms of algorithms, writing, and caching to make it more streamlined and efficient. After a series of evaluations, CollisionMaster ended up with the following solution.
- Optimization 1: Octree, filtering objects
- Optimization 2: kdtree, filtering triangles
- Optimization 3: geometry, filtering triangles
- Optimization 4: GJK + EPA, filtering and calculation
Octree and kdtree were chosen for optimization not only because of their better performance but also because they can support ray detection acceleration, so CollisionMaster also implements a high-performance ray detection system.
Resource Links
Download the source code
Try online (Note: the performance of this demo is not optimal.)