Author Topic: Mar 27, 2016 - How (not) to generate a planet  (Read 5074 times)


  • Administrator
  • Hero Member
  • *****
  • Thank You
  • -Given: 337
  • -Receive: 1171
  • Posts: 22,128
  • Toronto, Canada
    • View Profile
Mar 27, 2016 - How (not) to generate a planet
« on: March 27, 2016, 04:40:27 AM »
Has it really been a month already since the last log entry? Time certainly flew by...

Let's see what happened since then... After a bit of struggle, I finally managed to migrate to Unity 5. The reason for that ended up being the desire to have more control over the rendering process. There were visual rendering artifacts with the tri-planar approach in Unity 5 when specularity was added to the mix and I wasn't able to get it fixed on Unity 4's side, but I did fix it in Unity 5 by normalizing... the s.Normal in the lighting function, I think? I don't even remember anymore... I updated the shader I included at the end of the previous post after I got it working.

Curiously enough, terrain generation code is a lot slower in Unity 5 -- but only in the editor. In Unity 4 it was taking an average of 1150 milliseconds to generate the cratered terrain from the first post. The same task takes Unity 5 anywhere from 1650 to 3600 milliseconds to complete. Oddly enough, doing a build produces the opposite results. Unity 5 64-bit stand-alone build created the terrain 15% faster than Unity 4 -- which is why I ultimately decided to ignore it.

Moving forward I created two sphere generation algorithms -- one using a quad sphere described in the previous post, and another using an icosahedron. As it turned out, the icosahedron's triangles are not perfect after all, and they do get skewed -- which is something I should have realized, in hindsight. There's less skewing, but it still happens:

Quadsphere has a nice advantage over the icosahedron sphere: its UV coordinates are very simple, and if desired, one could even map 6 square textures to it without using any kind of projection or blending just because it's always about working with quads. There was still the outstanding issue of vertices near the corners being skewed to the point of being less than quarter of the size of ones in the center, but I was able to resolve it by simply pre-skewing all vertices using a simple mathematical operation:
  1. x = (x * 0.7 + x * x * 0.3);
The hardest part was figuring out the inverse of that operation, as I needed to be able to take any 3D world position on the sphere and convert it to a 2D position on the sphere's side for the purpose of determining how to subdivide the sphere as well as which regions the player should currently listen to (multiplayer). After busting my head a bit over this highschool math problem that was so far in the past as to almost appear beyond me, I was able to figure it out:
  1.         static double InverseTransform (double x)
  2.         {
  3.                 const double d233 = 0.7 / 0.3;
  4.                 const double d116 = d233 * 0.5;
  5.                 const double d136 = d116 * d116;
  7.                 if (x < 0.0) -(System.Math.Sqrt(-x / 0.3 + d136) - d116);
  8.                 else System.Math.Sqrt(x / 0.3 + d136) - d116;
  9.         }
After I was done with that math problem, I went straight into... more math. How to subdivide the quad sphere into patches? How to do it so that no two adjacent patches exceed each other by more than one size difference? And more importantly, how to do it in a memory-efficient manner? Naturally I didn't want to do any of this math stuff... too much math already. I figured I'd just start coding first, do that silly unnecessary math later.

I first started with the most naive approach, just to see it working. I figured -- hey, KSP used a 10 level-deep subdivision in their planets. I'll just go-ahead and pre-generate all the nodes right away, making it easy to know which node has which neighbor and parent, so traversing them will be a breeze!

Well, here's how it went... First time I hit play, I sat there twiddling thumbs for over 10 seconds while it generated those nodes. They weren't game objects, mind you -- not at all. They were simple instances of a custom QuadSphereNode class I created that had a bunch of references (to siblings, to potential renderers, meshes, etc). No geometry was ever generated -- not yet. I was merely creating the nodes. So naturally, the 10 second wait to generate enough nodes for just 1 planet was a surprise to me. And then I looked at my memory usage... Unity was at 3.5 gigabytes of RAM. Ouch!

That's when I decided to get my head out of my ass and do some math, again.
  1. 6 nodes, 10 subdivisions:
  2. 0 = 6
  3. 1 = 24
  4. 2 = 96
  5. 3 = 384
  6. 4 = 1536
  7. 5 = 6144
  8. 6 = 24576
  9. 7 = 98304
  10. 8 = 393216
  11. 9 = 1572864
  12. Total = 2,097,150 nodes
So to generate 2 million nodes, it was taking Unity 10 seconds, and it was eating up over 3 gigs of RAM, leading me to guesstimate that each class was adding ~1500 bytes RAM. The word "unacceptable" didn't quite cover it.

Not willing to delve into the whole "doing subdivision properly" logic just yet I decided to see if I could reduce the size of my classes first. That's when I learned that SizeOf() doesn't work properly in Unity. If you ever need to use it, use it in Visual Studio instead. It doesn't take into account unassigned fields pointing to class types. Long story short, by simply moving the geometry-related stuff out into its own class, and then leaving a null-by-default field pointing to that geometry for each node I was able to reduce memory usage down to 33% (1 gigabyte), and the generation time down to 2.3 seconds.

Of course that was still too much to be used in practice, and so I finally decided to delve into proper subdivision logic. On the bright side, it didn't take as long as I thought it would to get the "what's neighbor of what" code working in a very efficient manner and generate meshes on the fly on demand. On the downside, at the time of this writing, I still haven't actually finished per say. What the code does right now is given the directional vector and distance to the surface of the planet, it figures out what subdivision level is required. It then dives right into the subdivision logic, creating only the nodes that are needed to reach the 4 nodes closest to the observer. After that's done, it propagates outwards from those 4 nodes, creating higher and higher level neighbors until the entire sphere is covered. The code had to take into account neighbor sides on the sphere (and account for their varied rotation) and ensure that no patch is next to another patch that's more than 1 level above or below it in subdivisions.

Long story short, memory usage is negligible now, and generation time takes a mere 134 milliseconds to generate a planet going down all the way to the 10th subdivision -- including all the meshes necessary to render it, all the renderers and all the colliders. Over half of that time is spent baking PhysX collision data according to the profiler:

You may notice that the memory usage in there as well. A mere 12.3 MB were allocated during the planet's creation. So yes... from 10,000 milliseconds and 3 gigabytes not including geometry, down to 63 milliseconds and 12.3 megabytes that includes the geometry. Not bad! The final mesh looks like this: