Cesium: Vector Data on Terrain

[pjcozzi]

Vector data: polygons, polylines, and billboards/labels.

For now just a placeholder to gather reading material. More to come.

• Usability Oriented Visualization Techniques for 3D Navigation Map Display. 2014.
• An improved algorithm for vector data rendering in virtual terrain visualization. 2013.
• A screen-space approach to rendering polylines on terrain. 2011.
• Visualization methods of vector data on a Digital Earth System. 2010.
• RENDERING 3D VECTOR DATA USING THE THEORY OF STENCIL SHADOW VOLUMES. 2008.
• Efficient and accurate rendering of vector data on virtual landscapes. 2007.

[vmora]

Last link seems broken, here is the paper http://wscg.zcu.cz/WSCG2007/Papers_2007/journal/B17-full.pdf

And a review here http://vterrain.org/Misc/draping.html

[pjcozzi]

@bagnell can you evaluate volume decals as an approach for polygons/polylines on terrain? Think about performance and precision.

• Volume roads
• Volume decals

I don't know how to make it fast for polygons; it needs either a convex decomposition (not necessarily as fine-grained as triangulation) or a per-pixel point-in-polygon test (which, if done with a 2D texture of the polygon would have all the drawbacks of just rasterizing a texture as an image layer).

[pjcozzi]

@bagnell here are some notes for the shadow volume approach:

• [x] Remember not to use the bounding sphere for the polygon itself since the real polygon is where the volume intersects terrain. The most conservative thing to do is to use the bounding sphere of the volume, but I think we can do better.
• [ ] To save fillrate, instead of using the max altitude to extrude up, we should add a function to the terrain provider to return the max (and perhaps min) height of an extent based on the loaded terrain (perhaps with a callback for refinement?). To start, this could be based on the bounding sphere of each (or max height when it is lower), but we could make this much better with a quantized-mesh extension that keeps min/max per node. This could also be a web service.

[pjcozzi]

Notes from our discussion on billboards/labels:

• [x] Depth test origin in vertex shader using terrain depth buffer. This will require VTF, which is 97% supported (MAX_VERTEX_TEXTURE_IMAGE_UNITS).
• [x] Query height from terrain provider. Have callback for when it refines. Entity layer will update the billboards height.
• [ ] Longer-term, we might need to ability to only show the closest/most-important x number of labels and not depth test them. This allows us to see labels through terrain, buildings, etc.

[pjcozzi]

Also, I expect screen-space approaches (shadow volume, decal, etc.) to be much better for runtime editing than texture and sub-sampling approaches (sub-sampling may be OK, but I expect re-rasterizing the texture, especially if we made a sparse quadtree out of it, would be painfully slow).

[pjcozzi]

Query height from terrain provider.

I'm not sure what the implementation looks like now, but we can do much better than brute force look at each triangle. We can assume the triangle last used will be used next, and also use adjacency information (pre-compute once on the client I guess, or as a quantized-mesh extension) or a quad-tree arrangement inside the tile to find the right triangle.

Have callback for when it refines. Entity layer will update the billboards height.

This could be done on a web worker, e.g., each time we get a new tile, a web worker looks at all the subscribed positions to queue up callbacks (or events). This could be the same worker that processes the tile for visualization or a separate one to decrease the latency for terrain visualization at the cost of delaying the vector data update.

[pjcozzi]

@bagnell perhaps we do polylines last. We can evaluate shadow volumes for them using the corridor geometry and sub-sampling using the infrastructure we'll build for billboards/labels. Chapter 3 of Usability Oriented Visualization Techniques for 3D Navigation Map Display is a nice comparison, but their sub-sampling does exact line-segment/triangle intersections - and still does not get adequate visual quality for high-resolution terrain.

[kring]

To start, this could be based on the bounding sphere of each (or max height when it is lower), but we could make this much better with a quantized-mesh extension that keeps min/max per node.

Not sure what you mean here. Quantized mesh tiles already know the min and max height of any point within the tile. Is that what you're referring to, or do you need something else? Actually, heightmap tiles do, too, it's just computed at load time.

[pjcozzi]

do you need something else?

No. That will do it. I clearly didn't look at the format.

[pjcozzi]

@bagnell I had more ideas about point-in-volume.

We already discussed:

• If not already in it: bounding sphere -> extruded convex hull -> exact test
• If already in it: inscribed sphere -> inscribed convex hull -> exact test (actually probably check bounding sphere and extruded convex hull before the exact test)
• Later: consider BVH to avoid O(n) over all polygons.

Here's a few more ideas:

• Probably need a heuristic to see if the convex hull is worth it, e.g., if the polygon is already convex or can be broken into a few convex regions.
• I think we should start by coding the generic point (or near plane?) in extruded volume, but I suspect we will also want an optimized version for our unique case:
  
  
  
  • We don't need to check the bottom cap under terrain
  
  
  • In general, we'll need to check the top cap, testing each triangle would be slow, but I think we can get away with just checking the camera's height. However, I expect there will be an issue because that assumes an infinite tessellate of the top cap, so we may need to check a conservative height, and then check the triangles (unless the camera is above a max height).
  
  

[pjcozzi]

Recent paper:

• Practical line rasterization for multi-resolution textures, 2014

[bagnell]

• [ ] Add dynamic minimum height. (Needs changes to supported geometries)
• [ ] Query terrain for tighter maximum height.
• [ ] Add option to geometries for creating different bounding volumes.
• [ ] Batch by color?
• [ ] Tighter OBB? Maybe compute from triangles

[likangning93]

Usability Oriented Visualization Techniques for 3D Navigation Map Display. 2014.

That thing is like a Hitchiker's Guide or something waoww

[pjcozzi]

I only read the abstraction, but this could be interesting:

Deferred vector map visualization

Interactive rendering of large scale vector maps is a key challenge for high-quality geographic visualization software systems. In this paper we present a novel approach for the visualization of large scale vector maps over detailed height-field terrains. Our method uses a deferred line shading approach to render large scale vector maps directly in a screen-space shading stage over a terrain visualization. The fact that there is no traditional geometric polygonal rendering involved allows our algorithm to outperform conventional vector map rendering algorithms for geographic information systems. Our flexible clustered deferred line rendering approach allows a user to interactively customize and apply advanced vector styling methods, as well as the integration into a vector map level-of-detail system.

https://dl.acm.org/citation.cfm?doid=3002151.3002157

@likangning93 have a read and let us know what you think.

[Thoenu]

Dear patrick and others, you might want to consider the journal article to the link above, which contains some more perfomance analysis:

http://onlinelibrary.wiley.com/doi/10.1111/cgf.13294/abstract

[hpinkos]

Thanks for sharing @Thoenu!

[likangning93]

Deferred vector map visualization
https://dl.acm.org/citation.cfm?doid=3002151.3002157

This approach is amazing and terrifying. The crux is that instead of rendering "lines" as geometry, they do a full-screen post process pass that checks each terrain fragment in the current view to see how close it is to a line segment, with all the line segments stored in textures using a uniform grid of BVHs.

Unconfirmed concerns about precision issues aside, is it finally time for me to write a GPU BVH traversal? Is it finally my time?!

[EDIT] okay an actual list of concerns:

• aforementioned precision issues: this paper backprojects terrain fragments to "world coordinates" and then does 2D checks to see if they are "close" to lines. I suspect we can't get sufficient accuracy given how big our "world coordinate" space is
• also, that 2D checks thing - this doesn't work well on a globe, you might have to define a series of local coordinate systems. Or maybe remap everything to spherical coordinates? But that comes with its own set of accuracy/precision issues.
• how expensive is adding/removing lines? That seems like a lot of datastructure to update.
• how would this integrate with Entities/Primitives? This technique attempts to pack all polylines into a single constant set of passes.
• how to behave when line count in a cluster overwhelms the cluster's pixel allocation? Add another polyline collection?

I'm falling in love with the idea though, which is dangerous. I wonder how much math we can move to eyespace... and texture partial updates aren't that slow... and storing polylines in float textures at double precision is possible...

[likangning93]

A screen-space approach to rendering polylines on terrain

Via wayback machine

One beef I have with this technique is the requirement to render both a wall and a shadow volume, which seems more expensive for us because WebGL. However, combining this with ideas leveraging the batch table for fragment culling in https://github.com/AnalyticalGraphicsInc/cesium/pull/6393, I wonder if we could:

• render a thin volume for each line segment, carrying a batch ID mapping to start/end positions and a vector or something that taken with start/end describes a local coordinate system with the XY plane tangent to the ellipsoid
• for each fragment, look up globe depth and compute an eye-space position. Squash that position and start/end positions into the XY plane of the local coordinate system transformed to eyespace and check for colinearity with start/end, which have likewise been squashed.

We'd have to disable early Z I think, for example if the camera's looking down at the volumes very closely so that the "top" of a volume draws over the adjacent volumes. But maybe that's not such a large price to pay to cut this down to a single pass.

We can also maybe modulate the "thickness" of the shadow volume using a normal vertex attribute that gets added to the positions based on camera distance.

Some back of the envelope math for batch table consumption:

• 5000 polylines with 10 points each makes for 5000 * 9 = 45,000 segments and batch table entries
• let's say each segment has 1 high-precision vec3 position for the start position, 1 vec3 offset to get to the end position, and 1 naive vec3 normal. That's 12 floats, so let's say we split all data across 3 textures
• that's something like 3 256 x 256 RBGA float textures, which doesn't seem too terrible

[likangning93]

The colinearity approach also gives us data that could be vital for doing style stuff.

[likangning93]

Question: what's the extent of material support that we want here? There's an awesome development Polyline Color sandcastle and I'm... not sure how to do that when we're working in fragment space.

Something something pass two colors per segment and lerp maybe...

[pjcozzi]

For style, start with color and line width. Then dash. Then textures.

[likangning93]

So the "single pass shadow volume for lines" trick above probably has the same problems as a conventional shadow volume algorithm for polylines on terrain, namely, difficulty keeping constant screen space width:

• when drawn perpendicular to the gradient of a steep slope and viewed wall-on
• when viewed at horizon-facing angles on flat ground

But since it's single-pass and doesn't require any special render state it can possibly still share a draw call with @pjcozzi's wall algorithm, which a conventional shadow volume can't do. So that's still kind of promising.

[EDIT] come to think of it, "Deferred vector map visualization" probably also suffers from smears and edge-on problems because it relies on something like the 2D colinearity technique for checking if a fragment is part of a line segment.

[likangning93]

"single pass shadow volume for lines" trick

I think this technique has enough promise that we can start assembling a gameplan. Here's a couple shots of my prototype at various view distances, we should be able to simulate "constant screen space width" reasonably well:

| |

:-------------------------:|:-------------------------:|:-----------:
near | far | wherever you are

I think through the Primitive API this is going to look something like a custom Geometry type (to be used via a method that builds arrays of GeometryInstances) and a custom Primitive type that will really just be a lightweight wrapper around Primitive but might have to tangle a bit with GroundPrimitive for terrain info.

How should this integrate into the Entity API though? Just something like an onTerrain flag that you can add to polyline entities? I'm reasonably sure that this is going to need its own spaghetti of updaters and batchers under the hood due to the custom Primitive.

It might also be wisest to start off with material support limited to, say, simple colors, but I'll try to have a more concrete idea of how difficult full material support will be soon.

[hpinkos]

@likangning93 at the entity level, polylines already have a followSurface option that defaults to true. I imagine we would use this as the new default and use PolylineGeometry when followSurface: false or if it's using a material that's unsupported

[likangning93]

followSurface option that defaults to true

One thing with this is that the current API lets users define polylines following the planet curve with per-point altitude:

var orangeOutlined = viewer.entities.add({
    name : 'Orange line with black outline at height and following the surface',
    polyline : {
        positions : Cesium.Cartesian3.fromDegreesArrayHeights([-75, 39, 250000,
                                                               -125, 39, 250000]),
        width : 5,
        material : new Cesium.PolylineOutlineMaterialProperty({
            color : Cesium.Color.ORANGE,
            outlineWidth : 2,
            outlineColor : Cesium.Color.BLACK
        })
    }
});

If anyone's depending on this behavior right now this is going to be a breaking API change, and they're going to have to write their own methods for interpolating between points with altitude. We could just check if any of the points specified are at height 0 above the ellipsoid, but then if users actually want 0 altitude for each point's height they again need to handle point interpolation themselves. Is that niche enough to be ok if we just document it?

I can also see a combination of per-point heights and followTerrain being kind of confusing to Google Earth users since in KML you can specify a line that follows terrain contours at a height above the terrain:

[likangning93]

when drawn perpendicular to the gradient of a steep slope and viewed wall-on

Fun idea: we might already have slopes available somewhere because of materials on terrain, and if not we can also compute per-fragment terrain slopes like we do for materials on ground primitives. Wonder if this would be useful for reducing smearing on slopes.

Something to experiment with a little later.

[mramato]

@hpinkos can confirm, but I believe we compute slopes in the material shader and it requires vertexnormals be part of the the terrain data (so they are technically not always available). I'm fine with requiring them, but we may need to either throw an error or provide a fallback (which can be not clamping to terrain).

[hpinkos]

I believe we compute slopes in the material shader and it requires vertexnormals be part of the the terrain data (so they are technically not always available)

Yep, see https://cesiumjs.org/Cesium/Build/Apps/Sandcastle/?src=Globe%20Materials.html

[pjcozzi]

@likangning93 can we close this?

[likangning93]

@pjcozzi :+1: from me