Sunday, May 11, 2014

Double precision approximations for map projections in OpenGL

(written mainly for my own reference, but it's also possible that someone else finds it useful as well)

The problem: OpenGL specification/extension ARB_gpu_shader_fp64 that brings support for double precision operations on the GPU specifically states that double-precision versions of angle, trigonometry, and exponential functions are not supported. All we get are the basic add/mul operations and sqrt.

In rendering planetary-scaled geometry you'll often hit numerical precision issues, and it's a good idea to avoid using 64-bit floats altogether because they come at a price. Performance hit is usually even larger than it could be, as some vendors intentionally cripple the double precision operations, to make a greater gap between their consumer and professional GPU lines.

In some cases it's not worth going into the trouble of trying to solve both the performance and precision problems at once, for example in tools that process real world data or project maps. These usually need trigonometric functions when converting between different map projection types, and a higher precision than 32 bit floats can give.
Unless one can/want to use OpenCL interoperation, here are some tricks how to reduce some of the used equations to just the basic supported double-precision operations.

fp64 atan2 approximation

In our case we needed to implement the geographic and Mercator projections. For both we need atan (or better atan2) function, which we'll get through a polynomial approximation.

Article on Lol Engine blog colorfully talks about why it's not a good idea to use Taylor series for approximating functions over an interval, and compares it with Ramez/minimax method. What's nice is that the good folks also released a tool for computing the minimax approximations, called remez exchange toolbox. Using this tool we can get a good atan approximation with custom adjustable polynomial degree / maximum error.

Here's the source code for the atan2 approximation with error less than 5 ⋅ 10-9, computed using the lolremez tool. Angular error of 5 ⋅ 10-9 translates to ~ 3cm error on Earth surface, which is very good for our purposes.

// atan2 approximation for doubles for GLSL
// using

double atan2(double y, double x)
    const double atan_tbl[] = {

    /* argument reduction: 
       arctan (-x) = -arctan(x); 
       arctan (1/x) = 1/2 * pi - arctan (x), when x > 0

    double ax = abs(x);
    double ay = abs(y);
    double t0 = max(ax, ay);
    double t1 = min(ax, ay);
    double a = 1 / t0;
    a *= t1;

    double s = a * a;
    double p = atan_tbl[9];

    p = fma( fma( fma( fma( fma( fma( fma( fma( fma( fma(p, s,
        atan_tbl[8]), s,
        atan_tbl[7]), s, 
        atan_tbl[6]), s,
        atan_tbl[5]), s,
        atan_tbl[4]), s,
        atan_tbl[3]), s,
        atan_tbl[2]), s,
        atan_tbl[1]), s,
        atan_tbl[0]), s*a, a);

    double r = ay > ax ? (1.57079632679489661923LF - p) : p;

    r = x < 0 ?  3.14159265358979323846LF - r : r;
    r = y < 0 ? -r : r;

    return r;

Mercator projection

While the geographic projection can do with the above atan2 function to compute the longitude and latitude, Mercator uses a different mapping for the y-axis, to preserve the shapes:

Where φ is the latitude angle. Bad luck, neither ln nor tan functions are available with double arguments. Logarithm approximation doesn't give a good precision with reasonable polynomial degree, but it turns out we actually do not need to approximate neither ln nor tan function.

It follows that:

Given that, going from 3D coordinates, we can get the value of tan φ simply from the 3D coordinates (assuming ECEF coordinate system):

Meaning that the inner logarithm expression now consists solely of operations that are supported by the ARB_gpu_shader_fp64 extension.

Finally, we can get rid of the logarithm itself by utilizing the identity:

and using the single-precision logarithm function to compute a delta value from some reference angle computed on the CPU. Typically that means computing sqrt(k^2+1) + |k| for the screen coordinate center, and using the computed logarithm difference directly as the projected screen y coordinate.

Since the resulting value of a/b is very close to 1 in cases when we need extra double precision (zoomed in),  we can even use the crudest ln approximation around 1: ln(x) ≅2*x/(2+x) with double arithmetic.


Sunday, February 9, 2014

2013 Retrospective, 2014 Look Ahead

A brief list of main features that were released in Outerra Anteworld sandbox in the past year:
There's been lots more stuff being worked on that hasn't yet surfaced in the public version, and of course an enormous amount of bug fixes and things needed for the not yet released features.

What's been happening behind the scenes

Outerra engine is in its current state already used in several special simulation projects, and thus a lot of coding went into the support, custom features and the API for use by these projects. We can't disclose many details until these projects are officially revealed, but here's something that we can show: a video showing OT in one such project, where it is used (apart from other things) to render a full 360° dome using 2x8 FullHD projectors:

The whole setup used several computers linked together in a LAN, three of which were used to render the dome - two of them driving 2x3 projectors (5760x2160 screen on R7970) , and one the remaining 2x2. Several additional networked computers were used for other displays used within the simulator, including a smaller dome in front of aircraft cockpit.

There's of course a lot more stuff being developed for this side, and most of it will also ultimately get into the public Outerra version.

Upcoming updates

Several features are in various stages of completion and going to be released progressively in public builds of the Outerra Tech Demo.

Material rendering enhancements, environment reflections

Material rendering in Outerra has been further enhanced, adding environment reflections and completing the physically based lighting implementation. At the moment it works only on objects; terrain needs some extra work to be able to use it.

Material news/fixes:
  • Blinn-Phong BRDF model with Schlick fresnel approximation
  • prefiltered cubemap for environment reflection
  • irradiance map computed from environment used for ambient light (needs a few improvements)
  • fixed environment reflection and ambient intensity for objects (terrain needs more work)
  • fixed transparency shader (TODO alpha masked geometry)
  • fixed metallic materials
  • a few performance optimizations

Another important feature in the works is an in-game material editor, that will allow tuning the materials without having to edit the material file outside and restart.

Water rendering enhancements, foam

Ocean rendering is still a weak part in OT, with several updates and TODO's on the way. This time the sun and sky reflections were enhanced, as well as adding a basic foam after the boats.

Obviously missing are the wake effects, reflections of boats and terrain in the water. The water is also quite patterned, as it's currently made just of several waves summed together.

The boats feel lighter than they are because the models currently use just 2 sampling points that compute the hydro forces, so any wave bump that happens to act directly on the sampling point behaves as if it was much larger and acting on half of the boat.

Characters, animations

True FPS/TPS modes are finally coming in the next update, replacing the existing "stick to terrain" free-camera mode. We are using animations from a commercial package so not everything fits as it should yet, it's more a proof of the concept for us to test the whole animation system and the FPS/TPS mode. 
  • dual-quaternion skinning, it preserves mesh volume in deformation (TODO linear skinning)
  • animation system is using a simple blending; sometimes a leg or arms are not properly synchronized and this part needs some additional work
  • current mercenary model has 81 bones, including the face bones.
A short video showing it in action:

With the new characters and object rendering changes we also did a bit of profiling and improving the performance of rendering for larger numbers of objects.

This includes:
  • improved draw call performance
  • a few CPU side optimizations to free the CPU but it still needs a bunch more, because it's not as efficient as we'd like (especially on older CPUs)
  • utilized instanced draw calls; if the same object is used multiple times it's hyper fast, although the triangle count is still the limiting factor, the rendering won't be stalled by the draw call overhead (which still exists even in OpenGL and especially on AMD hardware)
  • improved shadowmap performance (especially for NV hardware), shadow culling algorithm needs additional work, current implementation is rather naive and sometimes buggy, but it's the first required step to get the terrain self-shadowing to work


You may have seen early development images from the clouds implementation on the forums already:

Some info about the implementation:
  • clouds are volumetric, generated from noise with a variable threshold that allows to alter % of cloud cover
  • the screens above are showing just the volumes, without a finer cloud mask applied that will provide additional detail especially up close
  • it's designed so that there can be a rougher global cloud map used in the future, defining the local cloud density
  • currently uses just a single layer of clouds, but can use multiple ones
  • the cloud rendering back-end is suitable also for things like contrails and rocket trails
Clouds will become available in the demo once we resolve some major issues in the current implementation. For example, they do not yet work globally, if you zoom out farther they vanish and also lose quality and pixelate too visibly. Lighting inside the cloud isn't right yet, and there are also some rendering artifacts. 

OSM roads, buildings

Many people aren't content with the pristine unspoiled world, and are asking about getting all the civilization stuff in. Since OT can overlay vector data over the procedurally generated terrain, and the existing road engine generates the roads from vector data, import of an existing vector database of roads and other data will be possible as well.

OpenStreetMap is one of the possible sources for the road data and much more - rivers, fields, artificial forests and parks, building footprints etc. The roads and rivers will be the first to import, after the engine exposes interfaces for import plugins, allowing programmatical creation of OT roads and other entities. Import process will produce binary files usable directly by the terrain generator. The format is probably not going to be published - it's likely to change as the engine evolves, and for example right now the data even cannot be generated without knowing some of the data from the internal engine structures representing the terrain.

Some of the internal features being developed to handle the needs in this area:
  • extended road system capabilities - separate properties for the left/right side, configurable road profiles, markings
  • seamless road joins, splits (the existing data format puts some limitations on it)
  • "river bed" road profiles and river water surface shaders
  • polygonal vector mode for larger overlays - large rivers with well defined bank shapes, lakes, but also for fields, pastures, artificial trees or tree removal, terrain leveling etc

Multiple lighting sources, terrain self-shadowing

In Catalyst 13.12 AMD has implemented the OpenGL extension we needed to be able to handle planetary distances more efficiently, and ultimately allowing us to implement better solution especially for the multiple lights rendering. The upcoming update will automatically switch to the new mode if it finds the extension, and people with AMD cards are advised to update to the latest driver version.

It's likely that every AMD/ATI card owner will have to update to version 13.12 or better, since our recent rendering pipeline updates seem to have uncovered some kind of a bug in earlier driver versions, that causes missing terrain shadows or abysmal performance when the shadows are enabled.

There are similar issues with older Nvidia drivers: Quadro users need to update to newer drivers to resolve a weird lighting issue, and some older mobile graphics drivers have the problem as well. We try to add the known problematic driver versions into a bad driver list that is checked upon start, but in any case, whenever you encounter missing shadows or unusual issues with the lighting, please update your graphics drivers first.


Apart from Earth and the Middle-Earth planet (done by ME-DEM project folks), there soon can be a new planet available - Mars. Below is the first screenshot from a testing run. The Mars there is with its canyons flooded and an earthly atmosphere:

There are several issues that need to be addressed. Mars data have considerably lower resolution, approximately 500m. While OT will procedurally refine the data down to the ground level anyway, its algorithms were so far tuned for details below 100m, so it needs a new profile for Mars.

There are other issues, as you can see on the screen, there's a ghosting on the craters - it's because the elevation and color data do not match up. I'm not sure where the longitudinal offset comes from yet. The color map is of quite poor quality in general; craters have baked-in lighting that should be removed as the lighting is handled in real time. Also, the colors were apparently run through some odd filters that made the ice caps pink; white balancing helps that but the texture ends up being acid yellowish.

For Mars to work nicely we have to fix all of the above, and also separate the individual planet configuration data, as at the moment they are global.

Other news
We did a lot of demoing and presentations in the past year and got into several projects that now allow us to grow and speed up the development. In addition to working with dedicated development teams on special simulation projects based on Outerra, we will be also expanding our core team here in Bratislava, Slovakia. New people are expected to work mainly on the import tools, server side back-end and on the UI, replacing our programmer's design.

The breadth of the scope of possible Outerra applications is huge, and we are also investigating other possibilities to launch development of other OT-based projects. A hot candidate is a unified simulator platform with the primary initial focus on a flight simulator, as it makes the largest group of inquiries we are getting. This would mean a dedicated development team working closely with the core, and in cooperation with content makers working on scenery, aircraft, simulation cores for flight and other types of vehicles.

In any case, a project of this scale would require a sufficient funding, and so we are currently discussing the development of a prototype usable for launching a Kickstarter funding campaign with several interested developers.

Sunday, August 4, 2013

Absolute positioning with Oculus Rift development kit

After incorporating support for Oculus Rift into our Outerra tech demo (see the Outerra + Oculus Rift Test 2 - MiG 29 flight video), I've been pondering about a possibility to add absolute positional tracking to the Oculus Rift devkit. During the forum discussions about the support for FreeTrack/FaceTrackNoIR/opentrack in Outerra, Stanisław Halik, one of the opentrack developers, pointed me to ArUco.

ArUco is a library built on top of OpenCV, providing the ability to analyze video image and detect coded markers an their positional information. ArUco supports up to 1024 different markers, that are encoded in a 5x5 grid. ArUco tracker is supported in recent builds of opentrack, so I could use it with our recently added support for FreeTrack protocol.

For my tests I picked the marker code 787, printed it and stuck it on the Rift.

Using a recent build of opentrack (≥ opentrack-20130803), and a video camera (tested with Logitech C270 and an older Sonix SN9C201 camera) with FreeTrack protocol output I managed to get the positional tracking working in addition to the Rift tracker, with only a few minor changes required to our FT client implementation.

Here's a short video showing the augmented Rift tracking in action:

A couple of notes:
  • the added positional tracking definitely helps with the dizziness, the brain doesn't get confused by the missing degree of motion
  • currently the positional tracking does not use any filtering, resulting in occasional oscillation
  • ArUco in opentrack is currently quite sensitive to lighting conditions, bright parts of captured image outside of the marker can break the detection
  • when opentrack loses the track of the marker, camera stays on the last position, and after the position info is regained, the camera may suddenly jump into a new position
In Outerra the positional tracking is automatically used whenever a FreeTrack source is detected, and that means that any tracker plugin that provides the positional info will work with the Rift. I have personally tried it also with a 3-LED cap, but in combination with bulky Rift it's a bit impractical.

With ArUco marker the usage is very simple, but it has to be made more robust. Some ideas for enhancement:
  • using multiple markers - ArUco can detect an array of markers, so there can be multiple ones covering also the sides, that would not lose track when you turn your head to the sides
  • direct integration of ArUco - simplifying the setup even more
  • ultimately it would be best to use the info from Rift's accelerometer to capture the positional movement dynamics, and use the absolute positional info from the auxiliary tracker just to correct the drift

Since only the positional information is needed from the tracker, the simplest and probably the most robust implementation of a positional tracker would be adding just 2 wide-angle LEDs on the Rift, and using the point tracker plugin with it. Point light from the LEDs will be strong enough to overcome the problems of detection in various lighting conditions. However, it would require a small modification of the Rift.

Steps to set it up with Outerra:
  • print one of the ArUco markers (or print the 787 marker used here)
  • download a recent opentrack build
  • in opentrack, select the aruco tracker and configure your camera in the settings
  • select FreeTrack 2.0 for the game protocol, and optionally one of the filters
  • start opentrack, verify that it can see and interpret marker position and orientation correctly
  • once this works, leave opentrack running and launch outerra.exe
  • Outerra will automatically use Rift tracker together with any FreeTrack tracker it finds running