Developer Insights #10 – Collisions

July 23, 2021

Hi, my name is Michael Dodd, and I’m the Physics Engineer on the KSP2 development team. Before joining KSP2, I studied fluid mechanics using supercomputers for 8 years and obtained a Ph.D. in Aerospace Engineering. My goal is to add physical realism to the game while keeping the physics simulation robust, efficient, and scalable.

One of the problems we’ve had to solve was the ability to accurately detect and resolve collisions at orbital velocities of 10 kilometers per second or more. Collisions in KSP can be grouped into two main categories: (i) collisions with static objects like terrain and buildings and (ii) collisions with dynamic objects, like vessels. I want to tell you about some of the work we have been doing to improve both.

KSP is special—and challenging from an engineering perspective—because gameplay occurs over a vast range of length scales. Players may want to travel lightyears across the galaxy to a distant celestial body and then perform an orbital rendezvous that requires millimeter precision. Computers have limited precision to represent these distances, and when it comes to rendering objects to the screen or performing rigid body physics simulations, we are limited to 32 bit floating-point numbers. Floating point numbers are ideal for representing numbers spanning multiple orders of magnitude. However, floating-point numbers are distributed unevenly on the number line. As their value, or distance from the origin, increases, so does the difference between successive values.

To maximize numerical precision in KSP2, we use two approaches that work in tandem. A floating origin like that used in KSP1, which we’ll discuss later, and hierarchical positioning. In the latter system, a tree structure is used to organize and store relative offsets to a nearby object. For example, Kerbin is positioned relative to Kerbol, the Kerbal Space Center (KSC) is positioned relative to Kerbin, and so on.

However, this approach can still lead to numerical errors, especially on larger celestial bodies. If we consider positioning the KSC on Kerbin, which has a 600,000-meter radius, it can be positioned with a maximum of approximately 10 centimeters of accuracy relative to Kerbin’s center.

While a 10-centimeter error may sound negligible when compared to the vastness of the KSP galaxy, at the scale of an individual Kerbal this inaccuracy is noticeable. It causes objects to visually jitter and reduces the accuracy of collision detection. In some scenarios, the collision algorithm will miss the collision entirely, leading to tunneling: the object passing through the mesh, which we will discuss in more detail later. To improve collision fidelity, we created a system that positions surface objects, like terrain colliders and buildings, relative to a local origin located at the planetary surface instead of the center. As the player moves, we dynamically reposition this local origin and the objects that are positioned relative to it, so that surface objects near the player keep their positional values close to (0,0,0). This greatly increases the accuracy with which we can detect collisions and eliminates issues like a landed vessel jittering on the ground.

While this works well for low-speed collisions, high-speed collisions need additional care. We define a high-speed collision as when the distance traveled by an object in a single frame is greater than its own size. Let us consider a command pod with a nominal size of 2 meters hurtling towards the surface of the Mun at 1000 meters per second. Assume the timestep between physics simulation states is 0.02 seconds. This means the object travels 20 m during a physics update. Given that the command pod is 2 meters means the object’s entire geometry could pass through the surface of the Mun without intersecting it. One solution is to decrease the time step, but this would increase the CPU workload. Instead, we use a continuous collision detection algorithm. Instead of advancing the object forward in time and checking if its mesh intersects a collision mesh, we use the object’s current motion to predict if and when it will collide.

It is important to note that this only works if the mesh colliders of our static objects are stationary. In addition to the floating origin system like KSP1 used that ensures our point of interest is centered in the scene, we added the local origin for planetary surface objects and dynamically update their positions. Specifically, the player’s active vessel is simulated in a coordinate system that is traveling with a constant velocity (inertial frame of reference; “Krakensbane” from KSP1) so that it appears at rest (or close to it) from the viewpoint of the physics simulation. The position and velocity of the reference frame are updated whenever the vessel’s position and velocity deviate from it by some margin. That means when your command pod is falling towards the surface of the Mun due to gravity, the ground is moving towards it instead of it moving towards the ground.

This causes the continuous collision detection algorithm to fail. Why? The terrain and other surface objects are kinematic objects, i.e., objects that move without any notion of mass or force. To maximize performance, the positions of kinematic objects are updated outside the physics engine because we do not need to model their dynamics. Therefore, the physics engine knows the current positions of kinematic objects, but it is unaware of their motion. To solve this problem, when we expect a collision between an active vessel and a surface (i.e., kinematic) object, we switch the reference frames of the physics simulation. Instead of the ground accelerating towards the vessel, we switch back to the vessel accelerating towards the ground. The result is accurate collision detection at extreme speeds.

Snapshots of a vessel traveling at 1,596 m/s on a collision course with the Kerbal Space Center grounds. (Top row) Prior to improvements, showing mesh tunneling (middle row) after improvements without collision damage (bottom row) and with collision damage.

We also want to be able to detect high-speed collisions between vessels, especially in a multiplayer setting. Because vessels are dynamic objects, their positions and rotations are being updated by the physics engine based on the applied forces and torques. The physics simulation has full knowledge of each dynamic object’s motion and therefore it can perform continuous collision detection. So when flying around space, our goal is that player’s ability to collide with objects is not limited by the collision system but only by Kerbal piloting aptitude.