Introduction

In the previous two articles, we introduced how to implement a PhysX-based multi-backend and physics component design.

1. The First Physics Installment: Cross-Platform Compilation of PhysX Based on WebAssembly and PVD Joint Debugging
2. The Second Physics Installment: Multi-Backend Physics and Component Architecture Design

The collision detection and ray detection methods originally included in the Galacean Engine have been refactored into the @Physics-Lite package (hereinafter referred to as the Lite package). This allows non-heavy physics applications to use a lighter physics package to improve loading efficiency. In this article, we will introduce how to implement the Lite package based on the Physics interface, and during the introduction, we will showcase a series of design principles and optimization techniques derived from @Physics-PhysX. So if you are only interested in PhysX, you are also welcome to read this article.

Brief Review

In the previous article, we mentioned that the interface layer mainly has three types that need to be implemented:

1. ColliderShape for describing specific collision geometry
2. Collider for organizing collision geometry and providing overall control and physical response
3. PhysicsManager for organizing the physical scene, providing scene update and raycast methods

ColliderShape

ColliderShape needs to be able to set local position, scale, UniqueID, physical material, and other properties. The Lite package does not support physical materials, but for the sake of interface uniformity, we still provided an empty implementation. The displacement and scaling transformations in ColliderShape need to be combined with the transformation matrix in Collider in subsequent ray detection and collision detection. For convenience, we trimmed the engine's Transform component to LiteTransform and placed it in the Lite package to handle calculations including LocalMatrix and GlobalMatrix. Since LiteTransform is no longer a component and cannot directly find its "parent transformation," we need to add an owner member to LiteTransform and modify the _getParentTransform function. This function determines if it belongs to a ColliderShape, then it can update the WorldMatrix through the Collider object saved in ColliderShape:

  private _owner: LiteColliderShape | LiteCollider;
 
  set owner(value: LiteColliderShape | LiteCollider) {
    this._owner = value;
  }
 
  private _getParentTransform(): LiteTransform | null {
    if (!this._isParentDirty) {
      return this._parentTransformCache;
    }
    let parentCache: LiteTransform = null;
    if (this._owner instanceof LiteColliderShape) {
      let parent = this._owner._collider;
      parentCache = parent._transform;
    }
 
    this._parentTransformCache = parentCache;
    this._isParentDirty = false;
    return parentCache;
  }

In the Lite package, only two simple collider shapes are implemented:

1. LiteBoxColliderShape
2. LiteSphereColliderShape

In Galacean Engine 0.5, BoxCollider and SphereCollider are subclasses of the Collider component, but here they are subclasses of ColliderShape. As readers of the previous article will know, Collider can be seen as a container for ColliderShape. Therefore, this time the Lite package refactoring allows combining Box and Sphere on a collider component to form a composite collider shape.

Collider

The implementation of Collider in the Lite package precisely reflects that "Collider is a container for ColliderShape," because apart from needing to set global transformations, it mainly involves trimming the ColliderShape interface. Based on this, two types of colliders are implemented:

1. LiteStaticCollider
2. LiteDynamicCollider

In fact, the Lite package does not include any physical response handling, so the above two types of colliders are almost identical. The reason for this is the custom physics specification of the Galacean Engine and the general principles of industry physics engines: such as the principle of PhysX: If a collision event needs to be triggered, at least one collider must be dynamic. Although there is no physical response handling, this approach is very important for performance optimization of triggers. Only dynamic colliders will act as initiators of collision detection. Therefore, we added LiteDynamicCollider and hope developers follow this principle when setting physical components. This way, even if the backend physics package is replaced with @Physics-PhysX, the entire program will still run normally.

PhysicsManager

PhysicsManager, as the manager of the physical scene, mainly has three functions:

1. Save Collider objects
2. Provide an update method to update the scene. In the Lite package, this mainly involves trigger detection and emitting corresponding trigger events.
3. Provide a raycast method for ray detection and return the detected object information.

These two important methods rely on the specific implementations of Collider and ColliderShape introduced in the previous sections. Next, let's see how they are done. It should be particularly noted that the algorithm implemented in the current Lite package is not efficient and does not rely on any acceleration structures. However, it has been optimized in implementation details to avoid frequent garbage collection. If you need to perform collision detection in complex scenes, please use the**_@Physics-PhysX package_**.

Collision Detection

Without considering acceleration structures, the principle of collision detection is simply to compare two ColliderShape objects one by one. If they intersect, an event is triggered. Since there are three events to consider, the state of the last update needs to be recorded for comparison. This inevitably creates new objects during runtime, which can frequently trigger garbage collection if not implemented well. In fact, even in @Physics-PhysX, since PhysX's callback functions only include onTriggerBegin and onTriggerEnd, and there is no function named onTriggerPersist, triggering the onTriggerStay function in the Galacean Engine script also requires storing the state for judgment.

To this end, we designed a special data structure to store the state, which has three layers:

1. Upper layer currentEvents: Type DisorderedArray<TriggerEvent>, saves the triggered events in the current scene into a linear array, so that the loop during the trigger event does not need the forEach function.
2. Middle layer eventMap: Type Record<number, Record<number, TriggerEvent>>, this mapping table can conveniently index specific events through the ID on the ColliderShape and modify the state.
3. Lower layer eventPool: Type TriggerEvent[], the event pool saves the peak collision events in the physical scene.

In this way, the entire process is divided into two parts: collision detection and triggering events:

In this structure, eventMap and currentEvents are actually just proxies for eventPool. All events will return to eventPool and will only be released after the program ends, thus avoiding the impact of the garbage collection mechanism on performance.

In fact, similar caching mechanisms rely on the component system architecture to control the destruction sequence of components. If the user deletes the physical component in the onTriggerEnter script function triggered during the traversal of currentEvents, it will cause problems in the traversal of the cache. Galacean Engine has sorted out similar logic, marking components that need to be destroyed and unifying the destruction of all components at the end of each frame. In this way, the traversal of the event queue will not be disrupted midway.

Ray Detection

Without considering acceleration structures, the principle of ray detection is also to poll all ColliderShape objects in the scene. If a collision occurs, the distance is updated until all ColliderShape objects are traversed. Of course, applying acceleration structures such as BVH is also very straightforward. Calculate the collision boxes for all objects, then traverse the tree structure to improve detection efficiency. However, for simple applications, since objects move, the tree structure needs to be constantly updated and then traversed, which does not significantly optimize and increases the complexity of the algorithm.

In the Lite package, ray detection loops through all Colliders, and each Collider is responsible for looping through ColliderShape to check for collisions and return information about the nearest collision point. LiteSphereColliderShape and LiteBoxColliderShape correspond to different ray detection methods.

Ray and Sphere Detection

Ray and sphere detection occur in the world coordinate system, so the center coordinates of the sphere need to be transformed through the WorldMatrix. Then, according to the sphere's parameter coordinates, solve the quadratic equation. If there is no solution, there is no collision.

Ray and Box Detection

Ray and box detection occur in the local coordinate system, so the ray needs to be transformed into the local coordinate system through the inverse transformation of the WorldMatrix. In this coordinate system, the box will be axis-aligned. By checking the range of each axis of the axis-aligned bounding box, it is easy to know if a collision occurred. For specific algorithms, refer to Intersection Calculation on BVH.

In the local coordinate system or the world coordinate system, specific situations need to be considered. For a sphere, no matter how it rotates, it remains the same, so processing in the world coordinates only requires transforming the sphere's center coordinates. However, for a box, detection is more convenient when it is axis-aligned, but in this case, both the ray's origin and direction must be transformed simultaneously.

Summary

This article introduces collision detection and ray detection implementation in the physics engine around @Physics-Lite. Although this implementation is very rough, it is also very lightweight, suitable for applications that are not physics-intensive. During the introduction, we also showcased our optimization details and design principles related to PhysX.

In the next milestone, we will further strengthen DynamicCollider, add physical responses, physical constraints, and add components such as character controllers. With these components, it will be easy to develop applications like pinball and shooting games, so stay tuned. This series of articles will also continue to introduce more content around PhysX and the physics engine.

If you have any physics-related technical points you want to know about or urgently need, feel free to leave us a message.