Jump to content

Developer Insights #10 – Collisions


Intercept Games

Recommended Posts

  • KSP Team

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 (see previous Dev Diary by Paul Furio). 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.

Collision detection 1

Collision detection 2

Collision detection 3

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.

 

Four command pods each traveling at 2510 m/s on a collision course with and without using the continuous collision detection algorithm.


Until we collide again,

Michael Dodd, Ph.D.

View the full article

Link to comment
Share on other sites

1 minute ago, gussi111 said:

Is anyone else having trouble playing the video?

If you're not able to view the video in the post here, please try viewing the post directly on the KSP website and see if you're able to view it there. Link:  https://www.kerbalspaceprogram.com/dev-diaries/developer-insights-10-collisions/

Link to comment
Share on other sites

17 minutes ago, Minmus Taster said:

@KSPStarare the demo images in the post from the game or is it a test scene?

Please don't be one of those people who assume the game looks like it was made in 2010 based on 300px picture.
Everything should be assumed as test environment, period. You've seen how the terrain can look like.

In any case, some technicalities instead of typical Show n Tell is a nice change. I'm wondering though how all the switching between moving objects, collision detections etc is going to affect performance.

Edited by The Aziz
Link to comment
Share on other sites

7 hours ago, Intercept Games said:

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.

This sounds like the "magic sauce", which isn't gone into much more detail. I wonder what level of impact it will have on the game in practice.

Maybe something like the small "hitch" that happens when getting close to another ship that needs to load into physics range might occur. 

Link to comment
Share on other sites

Great to hear there's a plan to help with jittery leg syndrome. Will this help with bouncing/exploding on load? Another issue I've seen in the past is big jumps in relative position between two craft in orbit when exiting time-warp, especially on very low velocity docking maneuvers. Will this help address that at all?

Edited by Pthigrivi
Link to comment
Share on other sites

1 hour ago, gussi111 said:

Unfortunately same issue, no sound and a black screen.

The video has been tested and is working properly. The issue you're encountering may require some troubleshooting on your end. (If you're viewing on mobile, try viewing on desktop. If using Chrome, try Firefox,  or try clearing your cache, etc.)

57 minutes ago, Minmus Taster said:

@KSPStarare the demo images in the post from the game or is it a test scene?

They screenshots are from in-game. The video is a test scene. All in-game screenshots are from the work in progress game, so any images/video associated with Show and Tell, Dev Diaries, etc. are WIP status. 

23 minutes ago, Superbdul1 said:

What about Show and Tell?

There is no "Show and Tell" post today. Today's KSP2 related post is the Dev Diary. 

 

Link to comment
Share on other sites

I absolutely love that this project has some real talent, education, and experience like this behind it. Some of the problems like this that need to be solved are anything but trivial and it is going to be such a better experience in the end as a result of having the people with the right skill sets doing the jobs. 

Link to comment
Share on other sites

Awesome hearing about fixes and enhancements from what we are use to in KSP1.

This means that objects can collide at orbital velocities. Guess we will have to pay attention to any crossing orbits.

Link to comment
Share on other sites

I'm curious: 

What if two players set up their velocity so that their orbits are very close to one another,  but with inclinations nearly exactly 180° apart, so that their relative velocities are basically 2x orbital speed; 

I imagine the continuous collision check is happening every frame where their trajectories are similar. Wouldn't this have an impact on performance, even if the players were in opposing positions on their orbits where collisions wouldn't happen (yet)?

Link to comment
Share on other sites

Great post! I had been hoping to see another dev diary about the physics.

On 7/23/2021 at 2:26 PM, starcaptain said:

I'm curious: 

What if two players set up their velocity so that their orbits are very close to one another,  but with inclinations nearly exactly 180° apart, so that their relative velocities are basically 2x orbital speed; 

I imagine the continuous collision check is happening every frame where their trajectories are similar. Wouldn't this have an impact on performance, even if the players were in opposing positions on their orbits where collisions wouldn't happen (yet)?

I think this is addressed at the end of the diary when talking about high speed collisions between vessels.

Edit: l originally misinterpreted the question.

Edited by The Physics Engineer
Link to comment
Share on other sites

50 minutes ago, starcaptain said:

I'm curious: 

What if two players set up their velocity so that their orbits are very close to one another,  but with inclinations nearly exactly 180° apart, so that their relative velocities are basically 2x orbital speed; 

I imagine the continuous collision check is happening every frame where their trajectories are similar. Wouldn't this have an impact on performance, even if the players were in opposing positions on their orbits where collisions wouldn't happen (yet)?

Forwarded your question to Dr. Dodd, and here's his answer: "We had to leave out a lot of details on the continuous collision check. One of those details is that it includes a broad-phase algorithm to improve performance. This algorithm performs a low cost sweep of all the objects to rule out pairs of objects that do not collide with each other. The next step is narrow-phase algorithm which performs the detailed and more costly collision checks on objects that are expected to collide based on output from the broad-phase. Thus, if two players are in opposing positions, their vessels collision pair would be removed by the broad-phase algorithm."

Link to comment
Share on other sites

This thread is quite old. Please consider starting a new thread rather than reviving this one.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...