Drawing Curved Lines in Space

2d Lines in 2d

Background

At the tail end of June, I put my indie game development goals into overdrive, and Nixiesoft signed a lease for a small space in Norwalk, CT. I hired a few people, got immensely lost in the paperwork associated with that, and after going through an absurd bureaucratic process, received a Certificate of Occupancy to set up shop.

The first task was to build a game about space. The space part of space, none of this straight line flying silliness, Gravity Matters (as it soon would be called) was about using real physics to coast around planets and stars by using gravity to pick up (or lose) speed.

Early in this rebooted dev cycle, I decided to switch from the earlier 2d space simulation written in Godot to full 3d. But how do you see your orbital lines? In the 2d version, I plotted them as you moved on a 2d bitmap which was rendered under the gameplay, so you could see which way you were moving.

Getting that to work in 3d turned out to be more work than I expected. Here’s how it went.

Attempt 0 - Load a stack of points and move them

My first thought was to create a stack of points (all basically sitting on top of each other), and then just move some of them out as the space ship flew and the line needed to be drawn, since it would take one a few bytes of updates on each frame over the bridge between the CPU and the GPU. While I still like this idea, I didn’t see a reasonable way to make this approach work with godot without modifying the data interface between the CPU and GPU, and since this project had started some time ago and was still in godot3, I didn’t have access to GPU data buffers. I’ll revisit this approach in a future revision, if there’s time, but in the meantime, I quickly scuttled this idea.

Attempt 1 - ImmediateGeometry

With the world(s) now rendered in 3d, the simple matter of plotting where you’d been in 2d wasn’t so trivial anymore. At first, I tried rendering the lines in 3d using Godot’s ImmediateGeometry. This was supposed to be the simple way to draw in 3d. The plan was simple enough:

  1. Mark where you were.
  2. If the space ship moved more than a certain amount, go back to step 1.

The nuance is in determining how much movement constitutes a certain amount in that plan. Too few points, and instead of nice curved lines we’ll get large straight angular segments between points. Too many points and we’ll bog down the amount of geometry we send to the GPU, causing the frame rate to drop.

After a little bit of a tuning, I’d found some parameters that seemed to balance things out. After an initial run in period, each successive point added to the ImmediateGeometry was causing memory to grow a bit and the frame rate to drop. While the orbital lines looked good, I think ImmediateGeometry was intended for lighter use than what it was soon trying to process, and I didn’t have a build I felt comfortable shipping anywhere.

Immediate Geometry Line Drawing

Attempt 2 - 2d plane in 3d

Given the geometry limitations in Attempt 1, I went almost entirely the other direction, to turn this back into a 2d problem. The idea was to emulate something closer to the original line drawing, namely to use a 2d bitmap and draw the orbital lines on that, then upload that bitmap as a texture to the GPU and draw it on a really big flat square (quad) placed just below where the game play was happening.

There were a bunch of gotchas with this approach:

  1. To render well, the size of each point you rendered on the quad (texel) needed to be about the same size as each pixel. The texels could be larger than the pixels, but then when they were rendered as squarish blocks (Gravity Matters usually has a 3d perspective camera set directly above the player pointed down at the play space). Blocky lines didn’t look great.

  2. Increasing the size of the textures (and decreasing the texel size) led to massive video memory use. A 1024 x 1024 x 32bit RGBA (need the alpha channel to see through to the skybox (universebox) below) is 4MB of GPU VRAM (and potentially more for the drawing surface while rendering it). At 4K (4096 x 2160) you’re over 32MB, and if the player scrolls a little by flying offscreen, you’ll need to allocate more chunks.

I did some antialiasing on the line draw before sending the texture to the GPU, but the line still wasn’t a nice cleanly rendered orbital line. I added a shader to further refine the line, which was sadly more expensive than I hoped, as most of the filters I used required a lot of texture lookups, and the results still weren’t very clean.

The raw data itself wasn’t that big - in a typical level, the game may collect around 10,000 orbital points, and if each one is a [float32, float32, float32] or 12 bytes per Vector3 (or however a PoolVector3Array stores it), it was only 120,000 bytes or just over 117KB in main RAM. This meant I could break the massive squarish quad into a series of smaller quads and only keep them around while they were showing up on the screen. The rest could be deallocated and then regenerated if the player moved back towards an area with one.

This approach worked, but there were a lot of gotchas:

  1. The lines were either fuzzy (from the antialiasing + scaling + texturing) or blocky (resolution too low with no filtering). The alternative was a gargantuan use of video memory, which seemed like a non-starter.

  2. Each of the quads (“orbital patches” as I called them) could cause frame hiccups during regeneration, so there was a complex scheduling / memory management problem going this route.

  3. The lines were no longer one piece, since a spaceship could leave a particular orbital patch to fly to another, then fly back into an earlier orbital patch. The earlier drawing code naively assumed that after the first point, every point was a line between itself and the point before it. This led to more data structure complexity in keeping a fast list of points available to redraw any given orbital patch.

  4. Boundaries were also tricky - the point dropped where the spaceship was rarely coincided exactly with the edge of a quad, so a bunch of cleanup math was required when entering and exiting orbital patches to calculate a point exactly on the border to keep the line continuous.

  5. The perspective camera led to occasional glitching around planets. The 2d drawn surface had no real notion of perspective, so at extreme angles (say the camera was zoomed out and the player had cut a tight orbit around a planet at the edge), the planet would occasionally show on the near or far side of the line.

So while this worked, for the amount of engineering involved, the end reality wasn’t very satisfying.

2d plane in 3d

Attempt 3 - Real 3d, triangle strips

Despite some coaxing to get the 2d drawing technique to look ok, I wasn’t thrilled about shipping the game in this state. The 2d adventure had taught me that the rendering really needed to be in 3d to get the perspective right and to get a nice clean crisp line filtered at the appropriate camera distance to avoid alias effects and keep scene-compatible lighting (without implementing 2d lighting gymnastics). I knew that GPU line rendering through loaded geometry in GL definitely worked at the size and scale I was working in, so I decided to give it another try. After a fresh cup of coffee and some much needed sleep, I went into the compiler with the “if this doesn’t work I’m going to extend Godot until it works!” attitude, after striking out earlier with ImmediateGeometry.

While I was ready to dive deep into gdnative or the godot code itself, I knew that going with this approach would lead to a difficult to support cross platform compilation mess, and I really didn’t want to give that up too early. I looked deep in the documentation and through some of the source, and came across the ArrayMesh interface.

Godot does drop various hints in the docs that ArrayMesh is more complicated to use than the higher level interfaces like ImmediateGeometry or the MeshDataTool, but given a choice between direct GL and the porting tax or figuring out this interface, I figured it was worth a try. Right in the doc page, they give you an example to get you up and running on the custom array interface you need to provide, so it was off to the races.

Often geometry is sent to the GPU as a set of triangles, or an x, y, and z coordinate for each vertex of a triangle. For a triangle, that’s 3 floats per vertex times 3 vertices per triangle, or 9 floats of data. For 32 bit floats, that’s 36 bytes per triangle.

To cut down on the amount of geometry you’re sending to the GPU, you can specify that the vertices are presented as a triangle strip, one of the core GL options for specifying the format of geometry. A strip of triangles is similar to the triangle above, except instead of fully specifying each triangle, we assume that the next triangle reuses the second edge of the previous triangle. Starting at vertex A to vertex B (edge 1), then on from vertex B to vertex C (edge 2), but before going back from vertex C to vertex A (edge 3), we can reuse edge 2 as the first edge of the next triangle to form a strip of triangles. If they all share one vertex (say vertex A, say going around it in a circle), it’s called a triangle fan, but I didn’t see an efficient way to use that for line drawing.

Triangle Strips for Line Drawing

Of course, in the real world, nothing is ever so simple, and it’s easy to get turned around when specifying a triangle strip. If you specify the vertices in the wrong order, the triangle will break the winding order rules and the triangle (or all of them) will disappear). It’s also easy to spend a lot of processor time on math spelling out where the triangles are relative to the space ship points, so it took a little experimenting to find something workable.

Conclusion

The 3rd attempt produced nice clean crisp orbital lines. It was relatively flat in memory (it needs some limits depending on constraints around the total number of points) staying within a few MB of initial use despite large numbers of points, and didn’t noticeably affect frame rates at all. Now that we knew where we were, it was time to plot out where we were going! Now that the line drawing was working well, I put together 4 levels in short order and sent the first binary off to steam for review for early access.

If you’re interested in Gravity Matters, please wishlist the game on steam! There’s also links there to our discord where we do occasional bug squashes ahead of general release!