Working to a Solution in Precision issues

GOOD NEWS/UPDATE: Chris has just implemented a much quicker, novel solution in the latest source code. As a result, I'm tabling this problem until we get to 1" pixels :-). Thank you Chris!

It's getting close to implementation time for solving the precision problems in the WorldWind base. To review, worldwind uses a lat,lon,meters coordinate system. When navigating in this space, any given location is subject to the precision of the numbers being used to represent your position (and the precision of all objects in the space). WW is constrained (as are most PC-based 3D applications) to Single precision 32 bit floating point precision. This works great for viewing the earth from outerspace, all the way down to a few meters. But, starting dealing with items below a few meters and the precision errors cause a number of problems, including jitter in the camera.

For more background, please see the earlier post (I believe the first post).

There are several potential implementation solutions, but lets first talk about why some of the quick hacks don't work (to remind ourselves why TANFL):

• Why not just switch to doubles? Great idea! Except the graphics cards these days do not support doubles in hardware. All rendering would become software based, and there goes those lovely framerates.
• Why not just use doubles everywhere, and then switch to singles at the last moment? This actually does help -- anytime you multiply/add/trig-ify single precision floating point numbers you worsen their error. Making all these calcs be double precision minimizes that error. This is a necessity in any solution. But the end problems still exist inside WW the moment you do your final double to single conversion. The viewpoint is inherent constrained to be at the finite and discrete set of numbers representable by single precision. You camera and objects will always be jumping to those points.
• What if we just make the viewpoint be super high res through some custom method (e.g. doublizing), and then just update the viewpoint calculations to be CPU based instead of native GPU based? Great... except you've got all the objects on the planet too... what coordinate space are they in? -- still the same old single-fp coordinate system. How do you map the two together? Ultimately, they will have to be mapped together, and as long as you are using geodetic lat/lon/alt centered in the earth, you'll hit the issue.
• What if we maximize our coordinate system around zero by using smaller numbers? The discrete space representated by floating points inherently have more precision around zero. When not make lat/lon be represented by radians, and altitude to be representated by kms? I actually like this as a quick fix... but at most it will give you a 2-3X improvement, which will get you down to 2 foot resolution, but still with areas of inconsistency. And the solution has its limits -- significant digits are significant digits in the end, despite the radial nature of the floating point implementation around zero.
• What if we just put the fix into QTS? I like it, but this is still problematic... think of the lat/lon grid lines. Ultimately, they must all share the same rendered coordinate system in order to be visually consistent.

Ok.. quick hacks are a no go. What next?

In his paper at http://planet-earth.org/cw05/FloatingOrigin.pdf, Chris Thorne points out three classes of solutions:

• On the fly shifting of coordinates
• Multiple local coordinate systems
• Piecewise shifting of coordinates in a continuous virtual world

I've taken the bent that we should strive to have Worldwind operate in as much of a continuous world as possible. The user should be able to zoom in smoothly to any spot on the globe... This presents problems with nearly all approaches, except his FO solution.

A problem that Chris Thorne does not seem to address in his paper regarding his Floating Origin solution lies in the updating of all those objects to be moved around the now constant eyepoint. Before, with a roaming eyepoint, we allowed the GPU to perform one last matrix operation near the end of the pipeline to construct the rendered image. With the FO approach, however, you've taken that operation out of the pipeline and have placed it in the object's position earlier in the pipeline. But worse, you've likely taken it out of the GPU and into the CPU. All objects must be recalced with a viewpoint change.

There are likely some ways to ensure that the change stays in the GPU. (Need to think more here).

But until then, I personally am leaning towards a piecewise solution of multiple local coordinate systems. Here, we make the origin be to some local location, and then move the eyepoint within this state. Recalculation of all the object locations only occurs when you transition from this local coordinate space to another.

First question: what grid structure?
Well.. what do you know... Worldwind already has a grid structure in place as defined by its QTS naming scheme. Granted, this structure varies from one QTS to the next, but the underlying SRTM terrain grid effectively is always loaded. I am thinking to use this SRTM level 0 (or more likely 1 or 2) gridding to be basis for the local coordinate systems.

The grid structure needs to be not just lat/lon based, but altitude based. This allows us to retain our current earth centered coordinate system when zoomed completely out. We can then rotate the earth like crazy without incurring coordinate system shifts.

Next question: how do we implement the local coordinate system?
Well, first off, we base the coordinate system on the lat/lon/alt of level 1 or 2 of SRTM. All objects call a single routine (usually) to convert a lat/lon/altitude into the final coordinate space. This function needs to be updated to take into account the local coordinate system if present. All objects drawing items into the coordinate space must use this function to translate from lat/lon/alt to coordinate space. If they don’t, then they won’t work. Furthermore, this function needs knowledge of the current coordinate system in place. I don’t think it will always be derivable from the current camera position, so better to store it directly in the drawArgs, which gets passed into these coordinate translation routines.


Next question: how do we handle the transition – specifically the recalculation of all the objects? Doing the smoothly is the biggest question, and one that I’m not going to try and solve. Why?... read on

The recalculation to the new coordinate space is effectively like performing a device reset (e.g. resize the window). I believe that the coordinate system switch should even force such a path of execution to occur in the code. Force all items to dispose themselves (or at least their MDX resources) and reconstruct themselves based on the new coordinate space. This seems drastic yes... but think about it... after a device reset, the various (well-behaved) layers do what they can immediately on the primary render thread, and then use the background update thread to load up their various resources. This will allow us to do all of the moving of the objects on the background thread with no new code. The downside is that after a transition, you’ll see data disappear and then reappear.

That’s not too bad.. But bad enough that I think a fix for QTS is warranted to prevent it from doing an actual dispose of the MDX resources, but rather, just a remapping (it’s the reloading of those textures from disk that scares me).

Next question: how do we prevent jitter on the transition boundaries?
First.. remember how I suggest that we make the coordinate systems be 3D? This is to allow us to keep our existing global coordinate system at zoomed out locations.

Noting this makes it clear that transitions, however, occur in a 3D space. You can hover between two coordinate systems in both lat,lon locations as well as altitude.

Now, how to handle these 3D boundaries? We should have plenty of room in the precision of the coordinate spaces to not worry about being a full grid off. Therefore, we should have a “tolerance” of grid changes to be a full grid size. That is, don’t switch to the next coordinate system until we’ve gone two coordinate systems away. This effectively makes each coordinate system have a bleeding edge of one additional unit.

Next question: how do we handle flight? What if we are going from one location in one coordinate space to another location in another coordinate space?
The camera movement class must also be aware of coordinate space transitions.

So, in going with a local coordinate system, we incur a frame rate spike on a coordinate system switch.

Open Item : adjusting the clipping planes and z-buffer

Why are there no comments in Worldwind?

Obvious no? It ensures faster checkout times.

Struts, Struts, Struts

Ok -- struts -- what are they? how do I get rid of them? and why are they there?

Ever seen something like the above picture? You've inserted your own image, particularly one that has been converted to a QuadTileSet (QTS) -- e.g. with dstile -- and then display it, and you get this bizarre under structure, seemingling holding up your picture off the ground. These are what I call struts.

Why are struts there?
Struts are part of WorldWind code base ironically to solve another problem: intra-tile seams/cracks. Imagine if you were to take a white sheet of paper, cut it into 50 equal tiles, and then reassemble that piece of paper into its original shape on top of a flourescent orange desktop. No matter how good you are at putting those tiled pieces of paper together, you are bound to see through the tiles to the underlying desk, particularly if you were to take a look at it from various directions. Imagine this piece of paper was crumbled up first, then "flattened" again, and the texture of the "terrain" of the paper would make the problem even worse.

Well, that "even worse" example is exactly what the 3D rendering engine has to do inside WorldWind and your graphics card. You eventually start to see through the spaces in between the tiles. Plus, the tile to terrain mapping varies from one QTS to the next, exacerbating the problem. Each point is calculated uniquely, with potentially different parameters -- leading to disconnect between tiles.

Struts were a novel solution for this problem. Effectively, they created a similarly colored structure at the corners of each tile projected down to the spherical geoid that WW uses as the "sea level" earth. Furthermore, the z buffer is cleared before displaying the QTS layer, allowing you to see the struts on top of what should otherwise be displayed underneath it.

If your imagery is largely continuous, then this really presents no problem, as there will be no location where you can see the imagery from the side. That's why it works great for the primary data sources. For your own imagery, however (such as the example above), you'll hit the problem.

More info can be found at: http://www.worldwindcentral.com/chat/irclog/worldwind-dev/2006-01-19.log.

Quick Fix: Removing Struts
Let's say you want to prevent the struts from drawing. Well, Chris put in a simple quick fix for removing the struts from view. With 1.3.3.1, WorldWind supports alpha blended layers. As you can imagine, alpha blended layers with struts can cause havoc to a scene. Therefore, WW is set to remove struts from the render loop when an image is in any way transparent. Therefore, as ddh and mazop have suggested, switch your layer's opacity to 254 and set the blending to bothsrcalpha. This is the quick and easy fix with no programming necessary. Note: in doing this, however, you've just traded the struts problem for the underlying seams problem -- which will now rear its ugly head.

Another way to remove the struts is just to modify the code to expose a UseStruts property off of the QTS. This UseStruts property should map to a UseStruts boolean inside the QuadTileArgs setting. Then, in your QuadTile::CreateElevatedMesh() routine, simply add the check for the UseStruts boolean:

if ((!QuadTileArgs.UseStruts m_CurrentOpacity <>&&
heightData != null) {
radius = layerRadius +
heightData[terrainLatitudeIndex + latitudePoint,
terrainLongitudeIndex + longitudePoint] *
verticalExaggeration;
} else {
radius = meshBaseRadius;
}

Other solutions

The above trick, just trades one problem for another. The solution space to the strut problem is divided into two camps: #1) use the struts, but make them not visible, and #2) removing the struts altogether, and solving the underlying seams problem a different way.

Ideas for #1: Making the struts invisible
Here are my brainstormed ideas on how to make the struts still present but just not visible on non continuous imagery:

• A quick hack would be to not clear the Zbuffer, and let the previous terrain hide it. Problem is, you start to have zbuffer fighting from data placed on top of each other. Plus, you will always have to have underlying data.
• What if we implement a global ImageAccessor that behaves more like the TerrainAccessor in WW? Here, we have one global image, on which textures are rendered. Then, we just logically replace the image space for that pixel area. Then, at the final render, we map that accumulated screen-sized texture down to the mesh. The downside with this is that it moves the heavy lifting out of the GPU -- effectively modeling your own frame buffer. Overkill and not a good idea.
• What about just shortening the struts, or even varying their length based on the obliquity of the camera?
• What about some funky experimentation with backface culling? I noticed that the fact that the struts do have backface culling doesn't seem to interrupt their ability to solve the problem when they should be being backfaced culled. What if we turned on back and front culling!? possible?
  

Ideas for #2: Solving the Seams problem a different way
More ideas, this time to solve the seams through a different method. Note: these all assume that you've removed the struts.

• Use vertex shaders on the edge vertices of a tile, similar to what Hoppe proposes.
• The seams are exacerbated by the tiles being drawn on a grid different than the source mesh data. If you were to match your QTS parameters of your imagery to that of the terrain data, you should have imagery/texture tiles being mapped one-to-one (at least on the edges) to the underlying terrain/mesh tiles. Then, interpolation becomes almost irrelevant, and in theory, the seams disappear. (not sure if this really works though -- more thought needed)
• Similarly, if you map your imagery to the underlying "reference" imagery texture QTS tile parameters, then you should be guaranteed to generate the exact same altitude values for each mesh vertex. Then, make the Zbuffer to not be cleared. Then, you should see identical z values stored for your mesh, and your imagery's texture should replace the reference imagery (i.e. z-fighting won't be an issue). This works assuming a) only one reference imagery underneath, and b) the two layers have their Update()'s called relatively simultaneously. This solution hints more at the need for a common grid. More thought is needed -- and keep in mind this reminder from DDH: "the TerrainAccessor is only used to get a elevation from a lat/lon, it's not part of the mesh system. but the problem is that the QTS layers are not defined in a single well-defined grid, they can be arbitrarily defined."
• Similarly, can we draw directly onto the landsat mesh, instead of creating our own?
• I'm not sure the tiles are always using the TerrainAccessor at the best resolution. This difference could easily cause disparities in the mesh, exacerbating the seams. Look into possible fixes like one that always force the highest resolution terrain tile (on GetElevationAt()) with the highest #of samples per degree for all mesh points on the edge vertices of a tile. More thought needed - not sure if it does this already.
• Also, each tile may be calling the TerrainAccessor with different values -- those in the distance may be using a lower samples-per-degree number than nearby tiles. Where these tiles butt up against each other will show seams. Perhaps force a mesh-wide tile level inside QTArgs?
• Similarly, I've noticed that the seams go away if you've got better imagery at a higher tile level. This makes me continue to think that having one or two more levels of finer grain mesh and/or imagery than your current visible would alleviate much of the problem. This can be easily implemented using QTSubset.
• Similarly again, what if we were to use QTSubset to draw something else underneath, e.g. a quad that is slightly larger than the tile, and a colors that match the four corners. Hacky, yes.
• There are hints from Mashi that there is a bug in the WW code that makes the seams worse than they should be. From dpatton: "150 samples in a terrain tile, and Chris was using 150 as an upper bound, rather than 149(i.e. 0-149)". This would cause a problem -- and worth looking into. I can't imagine it would solve it completely -- but would help make the tiles line up tighter.

What am I personally going to do to solve it? For me, with higher resolution data, the seams actually are manageable, as long as you wait for the higher res terrain+imagery tiles to come in. Thus, I've just disabled the strut code as above -- which appears to handle the problem sufficiently for short term needs. I think the best next-round solution is to force higher res on the mesh/texture -- or at least figure out conclusively why it is solving the seams problem for me. This would start to lean towards some of the solutions proposed in #2 above.

What is the relationship between QuadTile, QuadTileSet, and QuadTileSubset?

You know, I've had to re-answer this question so many times to myself, that its overdue that I write it down. If you want to do much with spatial data in world wind, the QTS is a must-know.

I don't want to explain what QuadTiles are in general, or why they are there. Suffice it to say, it is WorldWind's mechanism for preprocessing large areas of imagery to be more quickly rendered. It is effectively the LOD solution in WW for spatial data. It handles mipmapping and chunking, and simultaneously/parallel downloading of individual small chunks - among many things.

QTS: QuadTileSet is the master object in the QTS tree. It contains the QuadTileArgs, and the topmost QuadTiles (as stored in m_topmostTiles hash).

QTA: QuadTileArgs are the base class for storing all the information on how a QTS tree is to be rendered, and is used to communicate rendering data between the parent QuadTileSet (which "owns" the QTA object) and its QT's.

QT: A QuadTile represents a single QuadTile in the tree. It represents a single block of imagery out of the larger QTS tree, and each is rendered separately. It also contains pointers to its four children in the quadtree. It maintains its own vertices for each quadrant. Of important note: a QT actually renders itself by breaking its own tile into four quadrants with corresponding vertices, using the corresponding quadrant subsets of the tile's imagery as its texture. That is why it needs vertices for each quadrant. Lastly, it has pointers to its QTSub's.... which lead's us to....

QTSub: Everything above is as you'd expect. So what's this QuadTileSubset stuff? Subset of what? QTSubs are special variations of the QuadTile that are at the leaves of a QuadTileSet tree (only created at level+1 >= QTA.IA.LevelCount). QTSubs allow continued tiling at and after the furthest level is reached for a QTS tree. They link back to the parent QT tile that has imagery stored in a texture. Much of the QTSub code is copy/pasted from QT, with minor tweaks.

Now -- the obvious question -- why is there a QTSub? Why do you need to keep tiling and tiling once you've run out of imagery? The answer lies in the fact that you are rendering not just spatial imagery, but terrain. The QTSub objects forces the imagery to be shown with full terrain detail, ** particularly when the terrain detail exceeds the resolution of your spatial imagery.

Other QTS Questions:

• Does it render all QTS tiles from level 0 to n (where n is the level currently visible)? Because a tile is actually rendered by rendering the quadrant subsections of its image, it can check for success when passing a render call to its children. If it fails, then it draws itself. Therefore, each QTS QuadTile will render a tile only if its child hasn't taken care of rendering the quadrant, and so on, and so on.
• What does the surface renderer due? is it used?
• How are tile sizes calc'd in the infamous row/col/level tuple <-> lat/lon coordinate mapping functions?: tile sizes are always determine from the distance beween north and south (lat).

What would I do if I could run the candy store? I'd start by getting rid of the variations between QTS, QT and QTSub. It should be a relationship similar to .NET collection and collection members. QTS should be a lightweight collection-like class (tree oriented), with a single root tile (it's 80% there). QT and QTSub should be merged, with the access to the imagery being better abstracted to handle "subset" cases.

Running WorldWind without a net connection or with local storage...

This seems to be a common question and need. I'm going to jot down my notes as I go along. I don't have a solution yet (not for complexity, just time).

First, if a net connection is "kind of" there, but not really (e.g. a net connection in need of repair, or a bad url), the underlying .NET infrastructure is ruthlessly persistent at trying to make a broken connection work -- gladly running off for up to 100 seconds before failing. Multiply this by the 25 or so tiles that are trying to be shown at any given moment, and your Update thread will be spinning for hours (well... 41:40 minutes to be exact). You will be left with spin lat/lon lines over an empty earth for at least 4-5 minutes before it really gives up.

Quick simple hack it to adjust the request.Timeout to be ~3-4 seconds in WorldWind.Net.WebDownload's Download() routine. This is still hacky, as it waits around for still 10's of seconds, while potentially killing downloads for those with slow net connections.

One real solution is to maintain some knowledge of the net connection across all of the quad tile requests, and ideally allocate one thread for testing connectivity to each potential datasource on the net. This will not tie up the main update thread with connection requests, as a tile can gladly check the state of the connectivity before doing anything.

Caveat/Todo: I have not yet looked closely at the GeoSpatialDownloadRequest DownloadRequest inside a Quadtile to see if it is shared by all tiles in a QTS (assuming a QTS will have a common server). If this is the case, then perhaps this code really does the universal connection management or just needs augmenting (e.g. to force it off the main update thread). From all accounts, the download queues held in QuadTileArgs should do all this, haven't had time yet to figure out why not.

It would also be nice to have the imageAccessor be smart about accessing data for "permanent" directory data -- a discussion in a previous post. The quadtiles are set up to fail frequently, instead of flagging incompletes. See http://issues.worldwind.arc.nasa.gov/browse/WW-478 as an example.

What's this blog about?

OK, I've made a few posts, and found that it can be helpful to me.

So what is this blog all about?

It's captures my mental state when coding and extending elements of WorldWind. If you are a WorldWind user, then this blog is not for you. If you are a WorldWind coder, then you might find it useful.

And as for you, dear reader.... I assume nothing about you, as it is written primarily for my own purposes. I just need a place to jot notes down about the WorldWind code base. So -- everything I write here can be wrong, poorly worded, naive and incomplete. I am posting it up to the world for the sake of openness, ala the spirit of OpenSource.

Lastly, because these are notes, I am frequently updating blog entries from previous days as new data/info comes available.

But also to the spirit of opensource, feel free to comment and contact me, though, if you have questions. Enjoy!

What is an ImageAccessor anyways?

I keep thinking the ImageAccessor is the answer to all my problems, and I keep getting disappointed (with all due respect to ddh, it's just the name that's killing me). I keep thinking the ImageAccessor is a onestop shop for all WW objects to access the current imagery at any particular lat lon across all layers. Not too much different than the terrainAccessor.

Alas, it's almost, but no. There has been plenty of discussion about implementing a global mesh and/or a global imagery/texture object -- but the image accessor is not that. (at least for now, in 1.3.3.1)

• Foremost, there is one and only one ImageAccessor per QTS tree, as specified in its QuadTileArgs. Essentially, you should always create a new ImageAccessor before creating a new QuadTileSet.
• It really is just a class to help translate, for any given QTS, the level/row/col tuple for the QTS into a specific filename of an image.

Real Basic.... but for potential to be so much more :-)

Dynamic QTS

One of the things we've been working on is a dynamic QTS solution. We need to have support for QTS trees that are created underneath us dynamically on our local drive. Why? Imagine spawning a dstile from within WorldWind when a user clicks on a local image.

Implementing this bumps up against several issues inside WW. First, QTS trees must be implemented to spawn the task request to tile an image (e.g. to dstile). Second, it must be able to "fix" the exception handling inside a QTS tree for missing tiles (which now becomes acceptable, assuming you are waiting for that particular tile to render). Thirdly, it must implement a dynamic timeout for finding tiles in a QTS tree.

To solve the first task (spawning the request), the solution is trivial.

To solve the second task (fixing the exception in 1.3.3.1), see the bug I posted in http://issues.worldwind.arc.nasa.gov/browse/WW-478.

Lastly, to implement the dynamic timeout for a tree tile, simply follow the suggested solution inside the above JIRA bug notice.

Now... here's the tricky part. What if you're imagery is not contiguous, or has areas where no imagery is present. In this case, your QTS tree file generator (e.g. dstile) should be smart enough to not create the file to begin with. But... with a dynamic QTS, you'll not know how to distinguish between a valid tile that just hasn't had its file written yet, and a blank one that will never be written. Worse yet, in the normal case, you'll frequently be doing disk checks (hopefully just fstats, underneath the .net hood) for the file's existence on the update worker thread.

To solve this last problem really requires better integration with your tiler, e.g. dstile.

If you'd like sample source of what I've done, let me know. But... we've got our own dstile'r.

Solving the coordinate precision problems in WorldWind

This posting is meant to store away relevant material for solving the coordinate system precision problems in WorldWind. It's written for me as notes for me, but maybe it will help you!

#1 -- Statement of problem:

• http://issues.worldwind.arc.nasa.gov/browse/WW-76
• http://issues.worldwind.arc.nasa.gov/browse/WW-477
• http://www.terrainmap.com/rm45.html

#2 -- Problem manifestations

• "Jitter" at high resolution
• Poor Picking Rays -- difficulty with moving the camera in high res
• tiling naming output :

#3 -- Google search terms:

• worldwind jitter
• gamasutra jitter
• global coordinate scenery jitter
• Heizenberg range
  

#4 -- Possible solutions / Problem discussions

• http://www.surak.com.au/~chris/PrecisionInVRML/PrecisionInVRML.htm for the same issue in GeoVRML
• nhv suggestion: FlightGear, http://www.flightgear.org
• http://www.blitzcoder.com/cgi-bin/ubb-cgi/postdisplay.cgi?forum=Forum4&topic=000352
• http://planet-earth.org/cw05/FloatingOrigin.pdf
• http://www.gamasutra.com/features/20020712/oneil_01.htm##
• http://www.ai.sri.com/~reddy/geovrml/double/
• http://pastebin.com/527915 -- ddh's recent work (splitting lat SP into two separate values -- haven't evaluated yet)
• http://www.gameprogrammer.com/4-fixed.html
• http://java.sun.com/products/java-media/3D/forDevelopers/J3D_1_2_API/j3dguide/VirtualUniverse.doc.html#49034
• http://www.surak.com.au/~chris/PrecisionInVRML/SinglePrecisionGeoVRML.html
• http://sourceforge.net/projects/retinax/ and http://sourceforge.net/forum/forum.php?forum_id=523573 for scene graphs
• If someone is interested, Celestia has already solved this problem. I don't know specifically how they do it, but apparently, they are able to render a "BigInt" or something that is the equivalent of a 128 or 256-bit number. I'm going to assume it's the manipulation of the Matrix stack from global to local coordinate systems.
• Look at Worldwind logs for 5-26-2005, 5-27-2005, 5-28-2005

#5 -- Methods:

• Force Camera at 0,0,0 -- get the most precision possible.
• Localized camera coordinate space - e.g. shift the mantissa at established camera positions
• Doublize by methods in above locations (although, alledgedly, this is quickly runs out too).
• Doublize by software-based vp (ugh)
• Add a decimal camera position, at least compute picking rays on decimal. Solve the jitter by forcing consistent roundoff error, or weighting based on altitude
• Perhaps force a localized zclipping that is more impervious (search on imposters)
• Finish reading items in #4 for more alternatives.

#6 -- My solution:

• My personal solutions was constrained by: a) lack of time, and b) desire to impact the Worldwind code base to the least amount possible (I hate branching and merging).
• Thus I have gone with a localized solution that bumps up the coordinate projection system by several powers of two after a certain altitude is reached. This allows me to preserve adequate precision. It of course has ramifications throughout worldwind code, but I think I've gotten it fairly managed. I still need more testing to see if additional tweaks are necessary.