Developer Insights #9 – Orbit Tessellation

[Intercept Games]

Hello all, I’m Johannes Peter – A programmer on Kerbal Space Program 2 – and I love solving interesting problems!

The problems we face in game development rarely have a single “correct” answer. The more specialized your game is, the more specialized your problems are, and the more creative your solutions need to be. As a rocketry simulator on an interplanetary scale, Kerbal Space Program has already tackled a wealth of unique programming challenges.

Today I want to share a solution I’ve worked on for a problem that is fairly unique to KSP: How to draw accurate orbits that look stellar regardless of where they’re viewed from?

I’ll briefly cover a standard approach for drawing orbits, touch on some of the issues with that approach, and then look at the solution that KSP2 is using now: screen space orbit tessellation.

This dev diary will get a bit into the technical side of KSP2’s development, with diagrams to help illustrate some of the core concepts. We will mainly focus on this test scene of Kerbin orbiting Kerbol:

Quick disclaimer:

• All visuals were created specifically for this dev diary, and are in no way representative of how anything may look in the final game.
  It’s just programmer art.
• All code, while functional, is simplified for clarity.
• All orbits are to scale and celestial bodies are a constant screen size to make them easy to see.

Orbital Trajectories in KSP

I hope it isn’t too hyperbolic of me to say, but KSP is all about orbits. Building, flying, and crashing rockets are all core to KSP’s identity, but if I had to describe KSP with one defining characteristic, it would be that it teaches you how orbits work on an intuitive level, just by playing it.

While there are definitely exceptions (you know who you are), most players depend on the Map View to plan their journeys from launchpad A to crater B, so being able to display lots of orbits without visual artifacts is critical.

What is an Orbit?

An orbit is the path that an object takes as it moves through space while under the gravitational influence of other objects around it. Real life orbits are chaotic and not deterministic. Without performing many small iterative calculations, it is generally not possible to say for certain where an object will be in space at an arbitrary point in time.

This is one of the reasons why KSP simplifies its orbital mechanics so that generally you’re only within the sphere of influence of one celestial body at a time. These kinds of orbits are known as Kepler orbits where position and velocity at any point on the orbit can be described using parametric equations. With a parametric equation we can plug in a parameter—like a time or an angle—and get an accurate position or velocity.

If a curve can be described as a parametric equation it is easy for us to draw.

Drawing Parametric Curves

In general, to draw a parametric curve we need to:

• Choose a start and end parameter, as well as how many points we want to generate.
• Generate the points by passing values into the parametric function that range from start to end.
• Draw a line between each consecutive pair of points.

For example, to draw a standard sine wave, we can use this parametric function:

Vector3 GetParametricPoint(float parameter)
{
    float x = parameter;
    float y = Mathf.Sin(parameter);
    return new Vector3(x, y, 0);
}

With that function we can use a start and end parameter to generate our points:

void GenerateParametricPoints(
    List<Vector3> points, float start, float end, int count)
{
    points.Clear();
    // Need at least two points to draw a line
    if(count < 2) return; 

    // Generate points using a parameter that
    // inclusively ranges from 'start' to 'end'
    float stepSize = (end - start) / (count - 1);
    for(int step = 0; step < count; ++step)
    {
        float parameter = start + stepSize * step;
        Vector3 point = GetParametricPoint(parameter);
        points.Add(point);
    }
}

And assuming that we have a function to draw a line between two points, we can finally draw the lines between the points we just generated:

void DrawParametricCurve(List<Vector3> points)
{
    int count = points.Count - 1;
    for(int step = 0; step < count; ++step)
    {
        Vector3 from = points[step];
        Vector3 to = points[step + 1];
        Draw.Line(from, to);
    }
}

Here is an example of what that looks like:

The green line is the ideal sine curve that we want to draw, and the blue line is the result of our GenerateParametricPoints and DrawParametricCurve functions.

Changing the start and end parameters (shown here in degrees) affects the position and length of the curve and the more points we generate the better the lines match the ideal curve.

Drawing an Orbit

Let’s assume that we have the following:

• A parametric equation of our orbit. The exact equation is outside the scope of this post, but for those curious, you can see better results if it uses the eccentric anomaly as its parameter.
• A start and an end parameter that we’ll step between. A full orbit’s parametric equation generally ranges from 0 to 2π radians, or 0 to 360 degrees.
• The number of points we want to generate. The default in KSP1 is 180 points for a full orbit.
• A graphics package to do the rendering. We need a way to draw a line between two points.

As with the sine wave, we generate points using parameters ranging from the start to the end value, and by increasing the number of points we generate, we get a smoother looking orbit:

 

 

Of course there’s a lot that I’m glossing over here, such as more efficient ways to draw lines than one at a time or other optimizations, but in a nutshell this is how orbits were drawn in KSP1.

Adding some Perspective

Evenly distributing the points of an orbit yields excellent results when viewed from far away, specifically when the camera is not close to the plane that the orbit is on.

However, in KSP you frequently view orbits from extremely flat angles. For example, when zoomed in close enough to see the moon of a planet, the orbit of the planet will be almost completely flat.

Let’s add the orbits of Kerbin’s moons Mun and Minmus to our example scene:

When we zoom in on Kerbin’s moons, we see sharp corners on Kerbin’s orbit. The orbit line also misses Kerbin by a significant margin.

Even though we generated Kerbin’s orbit with 180 points, the distance between two points is still about 5 times larger than Minmus’ entire orbit:

 

If we evenly distribute the points around the orbit, then with orbits as large as those in KSP we run into scenarios where there may not be enough points from the camera’s point of view to look smooth.

We could increase the point count, but we’ll quickly run into diminishing returns. Much of the orbit already looks smooth so adding points there would be a waste, while due to the angle of the camera other parts of the orbit don’t have enough points.

… What if we could add points only where they’re needed?

Screen Space Line Tessellation

If you have two points that were generated with a parametric equation you can generate a new point between them by averaging their parameters:

Vector3 pointA = GetParametricPoint(parameterA);
Vector3 pointB = GetParametricPoint(parameterB);

float parameterMid = (parameterA + parameterB) * 0.5f;
Vector3 pointMid = GetParametricPoint(parameterMid);

We can start with a small set of points and insert new ones by averaging their parameters. The curve becomes smoother each time we do this:

In computer graphics tessellation is the process of dividing geometry to make it smoother. We are effectively tessellating our parametric curve.

We really only care that the curve appears smooth on the screen, so we want to evaluate the smoothness of our points in screen space, where the X and Y coordinates correspond to the point’s screen position:

Vector3 screenA = camera.WorldToScreenPoint(pointA);
Vector3 screenB = camera.WorldToScreenPoint(pointB);
Vector3 screenC = camera.WorldToScreenPoint(pointC);

With our points in screen space, we can insert a new point between points A and B based on how smooth the curve is there. But how do we define ‘smoothness’?

Choosing a Smoothness Heuristic

A heuristic is a rule-of-thumb; a method for solving a problem very fast while being adequately accurate. We need a heuristic to efficiently decide if our points are ‘smooth enough’.

We’ve mentioned two heuristics so far:

• The distance between points. If points are visually close together then they’re less noticeable.
• The angle between points. The closer three points are to a straight line the less their middle corner stands out.

A convenient heuristic that incorporates both is the triangle area, which we can compute very quickly using the Shoelace formula:

float ComputeTriangleAreaXY(Vector3 a, Vector3 b, Vector3 c)
{
    return Mathf.Abs(a.x*b.y + b.x*c.y + c.x*a.y 
                   - a.y*b.x - b.y*c.x - c.y*a.x) * 0.5f;
}

If the triangle of a, b and c in screen space has an area larger than a given upper limit, then we insert a new point between a and b to smooth out the curve.

We evaluate our heuristic on every consecutive set of three points, until all points satisfy our heuristic, or we reach another end condition like how many points we have in total.

It can help to visualize the triangles:

 

Putting it all together

We can apply the triangle heuristic to our orbits, coloring each point based on the Iteration it was added in—red first, then orange, yellow, and so on:The orbits are tessellated using the top-right camera and the turquoise lines show the viewing bounds of that camera. The top-left shows a close up of Kerbin and its moons.

The closer the camera moves to the orbit, the more iterations need to be performed to satisfy our heuristic, but we also use far fewer points overall because we only generate points where needed. For example the orbits of Mun and Minmus only generate new points when they become visible.

Here’s the original shot again with tessellation enabled and all debug drawing removed:

 

 

 

And that, in a nutshell, is how orbits are drawn in KSP2.

Closing Thoughts

When working on programming problems your first solution is rarely perfect, and it’s possible for your solution to have its own problems that you need to solve.

There is far more that went into the development of this feature that I’d love to share here, from implementation details like additional heuristics, culling optimizations and choosing the right data structure for efficient point insertions, to how this can be used for more than just Keplerian orbits, but this is enough for one post.

If you enjoyed this technical deep dive and want to see more stuff like it please let us know! Having the chance to share something like this with you all is very special to me. I wouldn’t be in this industry if it wasn’t for so many developers sharing their passions and inspiring me through their work online.

I’ll leave you with one last debug visualization, showing the spatial partitioning used to decide when points are worth subdividing even if they’re not on screen (but one of their descendants might be):

 

View the full article

 

[Spaceman.Spiff]

This seems very interesting!

[Starhelperdude]

cool!

[RealKerbal3x]

This is a proper deep dive! I love reading about this sort of stuff - maybe I'm just a nerd, but then again, who here isn't?

[Lewie]

Awesome!! This is a really neat dive into the technical aspects of the game, loved to see this! Semi-relaed question....will ksp2 suffer from flickering orbits?

Edited April 15, 2021 by Lewie

[Spaceman.Spiff]

Just now, Lewie said:

ksp2 suffer from flickering orbits?

Hopefully there will be less laser spaghetti

[HebaruSan]

8 hours ago, Intercept Games said:

• The distance between points. If points are visually close together then they’re less noticeable.
• The angle between points. The closer three points are to a straight line the less their middle corner stands out.

A convenient heuristic that incorporates both is the triangle area, which we can compute very quickly using the Shoelace formula:

float ComputeTriangleAreaXY(Vector3 a, Vector3 b, Vector3 c)
{
    return Mathf.Abs(a.x*b.y + b.x*c.y + c.x*a.y 
                   - a.y*b.x - b.y*c.x - c.y*a.x) * 0.5f;
}

Nice! Now I'm excited for this game! It's great that old annoyances like spiky orbits are being addressed. "Tessellation as applied to orbit rendering" sounds like something somebody might be able to patent, but I guess that's only useful if you have competitors that might want to use it.

(I assume you guys know you can drop that "* 0.5f" factor for speed and the metric would be just as useful, and that it was left in solely for our benefit. )

[MechBFP]

I absolutely love this post. Thank you for all the technical details, as well as the awesome graphs to visualize the problem and the solution. Stuff like this is why I think I am going to love KSP 2. The attention to detail is very evident.

[Guest]

yes this is great  

[Johannes]

2 hours ago, RealKerbal3x said:

This is a proper deep dive! I love reading about this sort of stuff - maybe I'm just a nerd, but then again, who here isn't?

You were my main target demographic  Glad you enjoyed it!

1 hour ago, Lewie said:

Awesome!! This is a really neat dive into the technical aspects of the game, loved to see this! Semi-relaed question....will ksp2 suffer from flickering orbits?

I hope not! It's a completely new system so that shouldn't be an issue any more. (it's had its own quirks, but I hope nothing as jarring as that makes it into release, knock on wood)

1 hour ago, HebaruSan said:

(I assume you guys know you can drop that "* 0.5f" factor for speed and the metric would be just as useful, and that it was left in solely for our benefit. )

Yep, had I left it out you know I would have been called out for it

Edited April 15, 2021 by Johannes

[jshu]

Very cool, thanks a lot! Would love to see more posts like this.

[Dientus]

Too awesome. Love the way you explain it. I am only a hobbyist, but I understood perfectly. Keep up the great work and believe me when I say that there are definitely people out here who appreciate your, and the others, attention to detail!

 

9 hours ago, Intercept Games said:

All visuals were created specifically for this dev diary, and are in no way representative of how anything may look in the final game.
It’s just programmer art.

VERY glad you included that

Now to see how many ask this very question..

[Johannes]

11 hours ago, jshu said:

Very cool, thanks a lot! Would love to see more posts like this.

Excellent - I really enjoyed writing it and I hope I get more opportunities to talk about some of the other cool new systems we're working on!

Heck, I could easily write another post about this system alone - I really only described the basic implementation that my first prototype used. If you were to implement it as is you might notice some edge cases where the triangle heuristic doesn't quite cut it. If you look closely enough you might even notice some slight differences between what I described and the behavior in the renders (which use the current version of the system) 

11 hours ago, Dientus said:

Too awesome. Love the way you explain it. I am only a hobbyist, but I understood perfectly. Keep up the great work and believe me when I say that there are definitely people out here who appreciate your, and the others, attention to detail!

That's honestly the biggest compliment I could ask for - Over the years I've learned so much from blog posts that covered topics that were way over my head at the time, but were written well enough to still be able to get something out of. I just want to pay it forward

Edited April 16, 2021 by Johannes

[SpaceFace545]

Maybe we could see some gameplay instead of proof that you guys know what you are doing. We get it, you guys understand how to make a game.

[HebaruSan]

13 minutes ago, SpaceFace545 said:

Maybe we could see some gameplay instead of proof that you guys know what you are doing. We get it, you guys understand how to make a game.

Maybe we could let the people who enjoy this post, enjoy it?

[Spaceman.Spiff]

@Johannes

I didn't understand the more code-y bits, but that's because i'm a fool. 

However, I thought the visual representations were very helpful in showing the progression here.

[mcwaffles2003]

This is the kind of content that reassures me the devs know what they're doing and will give something great to the community! Keep up the good work and thanks for showing us the progress

[minerbat]

cool! will you also PLEASE fix the bug with orbits where maneuver nodes can't make up their minds if you get an encounter or not and your orbit changes when you timewarp? even if KSP 2 is just KSP 1 without that bug, i would still be very happy. also, i love technical stuff! i also like programming but i'm about 0.000001% as good as this...

[PlutoISaPlanet]

@minerbat I hate when the game can't decide if you got a encounter or not.

[minerbat]

Just now, PlutoISaPlanet said:

@minerbat I hate when the game can't decide if you got a encounter or not.

especcially when you decide to go for it, it decides NO and you're playing hard mode without quicksafes. that is why i still make quicksafes in hard mode, but only use them in case of glitches like that...

[Dr. Kerbal]

Interesting........

12 hours ago, Intercept Games said:

hen we zoom in on Kerbin’s moons, we see sharp corners on Kerbin’s orbit. The orbit line also misses Kerbin by a significant margin.

This is still a bug in KSP.  I wonder if this can be fixed.

12 hours ago, Intercept Games said:

void GenerateParametricPoints(
    List<Vector3> points, float start, float end, int count)
{
    points.Clear();
    // Need at least two points to draw a line
    if(count < 2) return; 

    // Generate points using a parameter that
    // inclusively ranges from 'start' to 'end'
    float stepSize = (end - start) / (count - 1);
    for(int step = 0; step < count; ++step)
    {
        float parameter = start + stepSize * step;
        Vector3 point = GetParametricPoint(parameter);
        points.Add(point);
    }
}

And assuming that we have a function to draw a line between two points, we can finally draw the lines between the points we just generated:

void DrawParametricCurve(List<Vector3> points)
{
    int count = points.Count - 1;
    for(int step = 0; step < count; ++step)
    {
        Vector3 from = points[step];
        Vector3 to = points[step + 1];
        Draw.Line(from, to);
    }
}

Amazing.

12 hours ago, Intercept Games said:

We can apply the triangle heuristic to our orbits, coloring each point based on the Iteration it was added in—red first, then orange, yellow, and so on:

The orbits are tessellated using the top-right camera and the turquoise lines show the viewing bounds of that camera. The top-left shows a close up of Kerbin and its moons.

Mind blown. Your 30 steps ahead of me.

[minerbat]

yes, indead amazing! and i haven't even figured out how to get 3D rendering to work yet...

[Dr. Kerbal]

12 hours ago, Intercept Games said:

Here’s the original shot again with tessellation enabled and all debug drawing removed:

And that, in a nutshell, is how orbits are drawn in KSP2.

Nice. However. Shouldn't Kerbin's icon come first? When laying the icons?

[minerbat]

Just now, Dr. Kerbal said:

Nice. However. Shouldn't Kerbin's icon come first? When laying the icons?

this is not the game, just a quick and dirty presentation. there is no reason to make such detail on this, it's just extra work

[Dr. Kerbal]

6 minutes ago, minerbat said:

this is not the game, just a quick and dirty presentation. there is no reason to make such detail on this, it's just extra work

I guess so. I read the entire article and its pretty neat.  Th orbits look so nice and pretty.  I cant image the Kerbin, Mun, and Minmus icons when shown on the map.  What a master peice.

8 minutes ago, Dr. Kerbal said:

Here’s the original shot again with tessellation enabled and all debug drawing removed:

And that, in a nutshell, is how orbits are drawn in KSP2.

I cant imagine the whole Kerbol system in this skybox. Nice skybox.   

2 hours ago, Johannes said:

Heck, I could easily write another post about this system alone - I really only described the basic implementation that my first prototype used. If you were to implement it as is you might notice some edge cases where the triangle heuristic doesn't quite cut it. If you look closely enough you might even notice some slight differences between what I described and the behavior in the renders (which use the current version of the system) and what I described

Nice! I have to give credit to you @Johannes. The rending of the orbit is very smooth. Like it. I cant imagine when the entire Kerbol system is complete. I mean, your practically making the universe in a game. I can barley code gravity in Scratch and yet your doing things that blow my mine! Thanks so much. I wish you the best of luck!  

Edited April 15, 2021 by Dr. Kerbal
Why autocorrect.