I suspect building a lifelike virtual world (i.e., Google Earth comes to life like a video game), is an attractive idea for a lot of software developers. However, most of them don’t know where to start. It’s a huge undertaking. Like me, many of you bought the 3D Engine Design for Virtual Globes book written by Patrick Cozzi and Kevin Ring. It is an excellent book that I recommend. And as most of you know, Patrick went on to create Cesium, the JavaScript-powered 3D globe, which is also excellent. Patrick and his team have been doing great work and are pioneers in the “Open Geospatial Metaverse” space. However, there are things that Cesium (like Google Earth) doesn’t do that keeps me pushing forward on my own virtual world. For example, a lifelike 3D ocean. Back to the book, I won’t repeat content that is written there as it covers a variety of topics very well. Instead, I will provide more practical descriptions for true-scale planet rendering, as well as describing areas the book does not cover.
Having said the above, I am no expert in true-scale planetary rendering. That’s because there are no experts! One can really just talk about their own experience. There have been people before me like Ben Discoe who developed and still maintains the Virtual Terrain Project. And I would be remiss if I did not mention Brano Kemen, the genius behind Outerra. As for myself, besides the passion described in my Hello Again, World blog post, probably my most significant (and relevant) accomplishment was building a radar simulator for the Canadian Air Force. I designed the simulator such that it would dynamically load terrain data so it could go anywhere in the world. It was delivered to the Department of National Defence (DND) and is still used today to train radar operators working on the CP 140 Aurora maritime patrol aircraft. In this project and others, my background is more on the geospatial side of the house, not games per se. It has been and continues to be an uphill journey learning the ins and outs of game development. I hired several people from the game development community but turns out planet-scale rendering is hard, even for a seasoned game dev. If you are someone who thinks they can help me out, or you know of someone, give me a shout. Okay, enough of the background chatter, let’s get to the good stuff.
Coordinate Systems
One of the first things you need to do when setting up a game development environment is determine where the world origin is. For Earth, we start with the Earth-Centered, Earth-Fixed (ECEF) coordinate system.
Having said the above, I am no expert in true-scale planetary rendering. That’s because there are no experts! One can really just talk about their own experience. There have been people before me like Ben Discoe who developed and still maintains the Virtual Terrain Project. And I would be remiss if I did not mention Brano Kemen, the genius behind Outerra. As for myself, besides the passion described in my Hello Again, World blog post, probably my most significant (and relevant) accomplishment was building a radar simulator for the Canadian Air Force. I designed the simulator such that it would dynamically load terrain data so it could go anywhere in the world. It was delivered to the Department of National Defence (DND) and is still used today to train radar operators working on the CP 140 Aurora maritime patrol aircraft. In this project and others, my background is more on the geospatial side of the house, not games per se. It has been and continues to be an uphill journey learning the ins and outs of game development. I hired several people from the game development community but turns out planet-scale rendering is hard, even for a seasoned game dev. If you are someone who thinks they can help me out, or you know of someone, give me a shout. Okay, enough of the background chatter, let’s get to the good stuff.
Coordinate Systems
One of the first things you need to do when setting up a game development environment is determine where the world origin is. For Earth, we start with the Earth-Centered, Earth-Fixed (ECEF) coordinate system.
ECEF Figure from Wikipedia
The ECEF coordinate system is centered on Earth’s center (of mass that is) with the X axis pointing off the coast of Africa, the Y axis in the Indian ocean and the Z axis at the [true] North pole. The latitude and longitude are shown as the φ and λ angles respectively. The point represented by the outer corner of the green box has XYZ coordinates in this frame.
From the figure you can see the surface normal at the example point doesn’t extend down through the center of Earth. This is due to the oblate spheroid shape of the Earth and results in φ angles referred to as geodetic latitudes. The line extending from the surface point through to the center of Earth yields a φ angle known as the geocentric latitude. For practical purposes, just use geodetic latitudes as they are the most common. The λ angle is the longitude and together, they are commonly referred to as geographic coordinates. If you add in the height above or below the reference ellipsoid, the trio of numbers is often referred to as geodetic coordinates. To convert geographic/geodetic coordinates to ECEF, refer to the Geographic coordinate conversion page on Wikipedia.
From the figure you can see the surface normal at the example point doesn’t extend down through the center of Earth. This is due to the oblate spheroid shape of the Earth and results in φ angles referred to as geodetic latitudes. The line extending from the surface point through to the center of Earth yields a φ angle known as the geocentric latitude. For practical purposes, just use geodetic latitudes as they are the most common. The λ angle is the longitude and together, they are commonly referred to as geographic coordinates. If you add in the height above or below the reference ellipsoid, the trio of numbers is often referred to as geodetic coordinates. To convert geographic/geodetic coordinates to ECEF, refer to the Geographic coordinate conversion page on Wikipedia.
Geodetic coordinate conversion from Wikipedia
To convert back from ECEF to geodetic, I use the iterative method described in the paper “Transformation from Cartesian to Geodetic Coordinates Accelerated by Halley’s Method” by T. Fukushima. It seems the paper is now behind paywalls so I have snipped the XYZToLatLon() function from Bending Time and made it available here to download. Note there may be newer methods than this one from Fukushima in 2006 but generally, the reverse process from XYZ to Lat/Lon/Height is an iterative one.
Other useful calculations in a 3D globe are ellipsoid distance and bearing/range. For these, I use the Vincenty direct and inverse formulae, which are described in his original paper at https://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf. You can find implementations of his formulae all over the web.
An even more accurate solution for ellipsoid distance and bearing/range was developed by Charles Karney who developed the GeographicLib project, which can be found at https://geographiclib.sourceforge.io/.
Once you are armed with these geodetic, ECEF and ellipsoid functions, you have the basis for a 1-cm-precise 3D virtual world. I say precise and not accurate because the calculations may be accurate but the data you use may not be. Which leads us back to maps.
Map Projections
Most municipalities around the world map out their region on Earth and maintain a Geographic Information System (GIS) to manage and use the data. They hire surveyors to map out the city, take measurements and upload the data to the GIS. As part of their mapping process, they use GPS antennae, which gives them very precise geodetic coordinates however, the geo format is not easy to understand. It doesn’t directly translate into how many meters long a sidewalk is for example. So, they typically save the data in map-projected coordinates like those from the Universal Transverse Mercator (UTM) grid system. This gives them and the people who read the maps a nice view where all the pixels are square in linear units like meters or feet.
Other useful calculations in a 3D globe are ellipsoid distance and bearing/range. For these, I use the Vincenty direct and inverse formulae, which are described in his original paper at https://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf. You can find implementations of his formulae all over the web.
An even more accurate solution for ellipsoid distance and bearing/range was developed by Charles Karney who developed the GeographicLib project, which can be found at https://geographiclib.sourceforge.io/.
Once you are armed with these geodetic, ECEF and ellipsoid functions, you have the basis for a 1-cm-precise 3D virtual world. I say precise and not accurate because the calculations may be accurate but the data you use may not be. Which leads us back to maps.
Map Projections
Most municipalities around the world map out their region on Earth and maintain a Geographic Information System (GIS) to manage and use the data. They hire surveyors to map out the city, take measurements and upload the data to the GIS. As part of their mapping process, they use GPS antennae, which gives them very precise geodetic coordinates however, the geo format is not easy to understand. It doesn’t directly translate into how many meters long a sidewalk is for example. So, they typically save the data in map-projected coordinates like those from the Universal Transverse Mercator (UTM) grid system. This gives them and the people who read the maps a nice view where all the pixels are square in linear units like meters or feet.
Universal Transverse Mercator (UTM) Grid System
If you’re interested in learning more about map projections, I recommend the bible in the domain “Map Projections: A working manual” by John Snyder, which can be found at https://pubs.usgs.gov/publication/pp1395. I bought a bound version online as hard copies make referencing things so much easier imo.
The reason I’m circling back to maps is they are the major source of data for a 3D virtual Earth. As I talk about in my It’s Your Planet blog post, the open data trend continues and many cities offer their data for free with a commercial-friendly open license, albeit often in map-projected coordinates.
Given the square and equidistant pixels in map-projected coordinates, one might think this would be a suitable coordinate system to use when a user is playing on the ground in the lifelike virtual world. And it’s true, this would work but only for small regions at a time. If the user moves too far away from the map projection area, the math breaks down and you have to move your region to another zone, or use another projection or what have you. In other words, the world is no longer seamless and transitioning from one zone to another could be problematic.
Having said that, one interesting idea I had was to use the Universal Polar Stereographic (UPS) coordinates for the polar regions, esp. Antarctica. A lot of data that is collected near the poles are encoded in polar stereographic coordinates and so having the world use the same map projection as the data would alleviate a lot of map conversion work. I thought a gameable environment in Antarctica would be unique and could be pretty fun however the cost/risk/benefit ratios were not adding up so this idea never materialzed. (Though I still have copious data for Antarctica, mostly in polar stereographic coordinates.)
The reason I’m circling back to maps is they are the major source of data for a 3D virtual Earth. As I talk about in my It’s Your Planet blog post, the open data trend continues and many cities offer their data for free with a commercial-friendly open license, albeit often in map-projected coordinates.
Given the square and equidistant pixels in map-projected coordinates, one might think this would be a suitable coordinate system to use when a user is playing on the ground in the lifelike virtual world. And it’s true, this would work but only for small regions at a time. If the user moves too far away from the map projection area, the math breaks down and you have to move your region to another zone, or use another projection or what have you. In other words, the world is no longer seamless and transitioning from one zone to another could be problematic.
Having said that, one interesting idea I had was to use the Universal Polar Stereographic (UPS) coordinates for the polar regions, esp. Antarctica. A lot of data that is collected near the poles are encoded in polar stereographic coordinates and so having the world use the same map projection as the data would alleviate a lot of map conversion work. I thought a gameable environment in Antarctica would be unique and could be pretty fun however the cost/risk/benefit ratios were not adding up so this idea never materialzed. (Though I still have copious data for Antarctica, mostly in polar stereographic coordinates.)
Universal Polar Stereographic (UPS) Grid System
A good reference for both UTM and UPS (aka the Universal Grids) can be found at https://apps.dtic.mil/sti/tr/pdf/ADA323733.pdf.
The one other thing that you need to watch out for when using data from different sources is the geodetic datum that is used in the map projection calculations. That is the shape of the ellipsoid at a point in time. When building a true-scale 3D Earth, your data must all align otherwise terrestrial features may look odd or out of place. The common solution is to transform all your data to the World Geodetic System 1984 geodetic datum, however, there’s a lot of other factors that go beyond the scope of this blog post so I will leave it at that; just use WGS84.
Local Tangent Plane Coordinate Systems
Another coordinate system to be aware of, which are used in aerospace applications all the time, are the local tangent plane coordinate systems; specifically, the East-North-Up (ENU) and North-East-Down (NED) coordinate frames. The ENU frame is useful to model objects on the surface while the NED frame is often used for objects above the surface looking down (e.g., aircraft).
One of the best (and easy to understand) references for the ENU and NED frames that I found is “A Pseudo-Reversing Theorem for Rotation and its Application to Orientation Theory” by Don Koks, which can be downloaded from apps.dtic.mil/sti/citations/ADA561412. In particular, the figure he drew to explain the rotations needed to produce a NED vector from geographic coordinates is clear and easy to understand.
The one other thing that you need to watch out for when using data from different sources is the geodetic datum that is used in the map projection calculations. That is the shape of the ellipsoid at a point in time. When building a true-scale 3D Earth, your data must all align otherwise terrestrial features may look odd or out of place. The common solution is to transform all your data to the World Geodetic System 1984 geodetic datum, however, there’s a lot of other factors that go beyond the scope of this blog post so I will leave it at that; just use WGS84.
Local Tangent Plane Coordinate Systems
Another coordinate system to be aware of, which are used in aerospace applications all the time, are the local tangent plane coordinate systems; specifically, the East-North-Up (ENU) and North-East-Down (NED) coordinate frames. The ENU frame is useful to model objects on the surface while the NED frame is often used for objects above the surface looking down (e.g., aircraft).
One of the best (and easy to understand) references for the ENU and NED frames that I found is “A Pseudo-Reversing Theorem for Rotation and its Application to Orientation Theory” by Don Koks, which can be downloaded from apps.dtic.mil/sti/citations/ADA561412. In particular, the figure he drew to explain the rotations needed to produce a NED vector from geographic coordinates is clear and easy to understand.
NED Rotations from “A Pseudo-Reversing Theorem for Rotation and its Application to Orientation Theory” by Don Koks
It's the same rotations for ENU just mind your axes. One can imagine, a local tangent plane modeled in square meters AND accounting for the curvature of the Earth could be pretty useful and I can tell you that it is! I discuss this a little more below.
Depth Buffer
One of the topics covered by the virtual globe book is the depth buffer. At large scales, your rendering software will suffer from depth buffer precision/resolution. The result is erroneous depth occluding (e.g., z-fighting). As mentioned in the book, Outerra uses a logarithmic depth buffer. The authors discuss another solution which is to use multiple frustums. Because Bending Time uses Unity, it was simple to add a second “close” camera to achieve multiple frustums.
Coordinate Precision
Another area of concern for planet-scale rendering is object jitter. I.e., an object begins to shake when its coordinates get too large. Read Chapter 5 in the book for more info. This is still one of the main problems with planetary-scale rendering. The virtual globe book provides three solutions:
Early on in Bending Time, I explored the solution space for #1. In a nutshell, every game object has coordinates relative to something else, a parent. It makes sense algorithmically however, once I got into the coding, working with the coordinates was cumbersome. It was difficult to know where an object was located just by looking at its coordinates. And my mental model was blurred.
Render relative to eye has been a longstanding concept stemming back to the original OpenGL days. Instead of rotating the camera around the world, rotate the world around the camera. In recent times, Dr. Chris Thorne at https://floatingorigin.com/ seems to be the main proponent of this approach. I didn’t get very far down this path before turning around because so much of my work was in the pre-render stage. Pre-runtime stage even! Managing all the map data, re-projecting and transforming, etc. Then in the code, streaming the terrain data based on the observer’s position and perspective, loading the data onto the GPU and then finally rendering, it didn’t make sense to try and change my coordinate systems at that point. However, the core idea has merit and may be worth exploring in some scenarios.
That led me to solution #3, emulating a 64 bit coordinate. I had done some research and learned that there was a significant performance hit so stopped there. However, that was almost 8 years ago and I suspect optimizations have continued like they usually do. For example, I came across an idea from a tweet from Sebastian Aaltonen where he describes using three 32 bit integers to emulate 64 bit planet-scale coordinates. Integers are full rate as he says so there wouldn’t be a performance loss per se, except you’d need 3x more memory. Worth exploring for sure.
Where I ended up was dynamically switching to a local ENU plane as the observer reached a certain height above ground. The coordinates in Bending Time are managed in Geographic/ECEF pairs from loading data to pushing the data to the GPU. The transformation to the ENU frame is done on the GPU and uses trigonometry around the lat/lon angles so the hope is object jitter will be reduced. (Lat/lon angles only need 6 decimals for approximately 1 cm precision.) Plus, the coordinates all go through the same pipe before going to the GPU in Bending Time so, if it's determined that a translation from Geo/ECEF to something else is needed, it can be done in that pipe.
Once I complete the “here’s where I am now” blog series, I will dust off my development environment and explore this topic further with example videos.
Locus on terra.
--Sean
Depth Buffer
One of the topics covered by the virtual globe book is the depth buffer. At large scales, your rendering software will suffer from depth buffer precision/resolution. The result is erroneous depth occluding (e.g., z-fighting). As mentioned in the book, Outerra uses a logarithmic depth buffer. The authors discuss another solution which is to use multiple frustums. Because Bending Time uses Unity, it was simple to add a second “close” camera to achieve multiple frustums.
Coordinate Precision
Another area of concern for planet-scale rendering is object jitter. I.e., an object begins to shake when its coordinates get too large. Read Chapter 5 in the book for more info. This is still one of the main problems with planetary-scale rendering. The virtual globe book provides three solutions:
- Render relative to center
- Render relative to eye
- Emulate 64 bits on the GPU using two 32 bit floats
Early on in Bending Time, I explored the solution space for #1. In a nutshell, every game object has coordinates relative to something else, a parent. It makes sense algorithmically however, once I got into the coding, working with the coordinates was cumbersome. It was difficult to know where an object was located just by looking at its coordinates. And my mental model was blurred.
Render relative to eye has been a longstanding concept stemming back to the original OpenGL days. Instead of rotating the camera around the world, rotate the world around the camera. In recent times, Dr. Chris Thorne at https://floatingorigin.com/ seems to be the main proponent of this approach. I didn’t get very far down this path before turning around because so much of my work was in the pre-render stage. Pre-runtime stage even! Managing all the map data, re-projecting and transforming, etc. Then in the code, streaming the terrain data based on the observer’s position and perspective, loading the data onto the GPU and then finally rendering, it didn’t make sense to try and change my coordinate systems at that point. However, the core idea has merit and may be worth exploring in some scenarios.
That led me to solution #3, emulating a 64 bit coordinate. I had done some research and learned that there was a significant performance hit so stopped there. However, that was almost 8 years ago and I suspect optimizations have continued like they usually do. For example, I came across an idea from a tweet from Sebastian Aaltonen where he describes using three 32 bit integers to emulate 64 bit planet-scale coordinates. Integers are full rate as he says so there wouldn’t be a performance loss per se, except you’d need 3x more memory. Worth exploring for sure.
Where I ended up was dynamically switching to a local ENU plane as the observer reached a certain height above ground. The coordinates in Bending Time are managed in Geographic/ECEF pairs from loading data to pushing the data to the GPU. The transformation to the ENU frame is done on the GPU and uses trigonometry around the lat/lon angles so the hope is object jitter will be reduced. (Lat/lon angles only need 6 decimals for approximately 1 cm precision.) Plus, the coordinates all go through the same pipe before going to the GPU in Bending Time so, if it's determined that a translation from Geo/ECEF to something else is needed, it can be done in that pipe.
Once I complete the “here’s where I am now” blog series, I will dust off my development environment and explore this topic further with example videos.
Locus on terra.
--Sean
RSS Feed