Declutter roadmap

[pjcozzi]

A ESA Summer of Code in Space 2013 project.

Usecases

Expect 10s to 100s to 1,000s of labels. We don't need to do the advanced cases below right away.

• Lots of static labels, e.g., labels for all the states in the US.
• Lots of dynamic labels, e.g., our KML of all the satellites.
• Combination of static and dynamic labels.
• Adding and removing labels at runtime.
• Changing a label's scale, pixel offset, eye offset, etc. at runtime.
• Have 2D screen-space regions that are keepout zones, i.e., areas that decluttered labels can't enter. These areas may be used for a heads-up-display or credits display.
• Advanced: (well not that advanced), declutter billboards and declutter groupings like labels and billboards linked together.
• Advanced: Keep labels above and/or in front of terrain. Perhaps based on Enhancing the Visibility of Labels in 3D Navigation Maps.
• Advanced: Declutter a label from a model with articulations, e.g., using dynamic eye offsets.

Design Goals

• Practical - it's one thing to just minimize overlap between 2D bounding boxes on a 2D screen, but it is another thing to usefully declutter labels in the scene and convey labels at the right level of detail in a meaningful way. For example, making it so that 2,000 labels don't overlap still clutters the screen with 2,000 labels. Hierarchical approaches need to be used.
• Robust - given the wide array of usecases, our algorithm needs to be tested with a variety of input.
• Performance - the algorithm needs to run very quickly since it needs to be recomputed frame-to-frame. Can we exploit frame-to-frame coherence? Will web workers lag too many frames behind? Is a GPU implementation possible?
• Temporal coherence - when labels or the camera move, the declutter algorithm shouldn't drastically snap labels into place. Instead the label should be moved into place over several frames.

We care much more about a useful solution than a fancy implementation.

Approaches

Some ideas discussed with @ognjenb for brainstorming...

Low-tech

• Change label scale, translucency (even down to 0 - transparent), or screen-space rotation angle based on one or more criteria:
  • Distance to label from the viewer
  • Number of overlapping labels, e.g., if two labels collide, fade one or both out
  • As the view changes from a top-down to a horizon view (useful for ground scenarios)
• Limited: change a label's horizontal and vertical origins to move it to the right/left or up/down. A label's pixel offset provides more fine-grained control.
• Use priority to minimize the movement of labels from their initial position. For example, static labels may stay fixed, but dynamic labels are allowed to move. In general, a Cesium app will not often know a priority other than static or dynamic.
• Allow the user to select the maximum number of labels to show, then pick the "best labels" each frame.
• Option to draw lines from a decluttered label to its original world-space position.
• Define a maximum distance that we are willing to move a label before we allow it to overlap (perhaps with translucency).

Hight-tech

• Combining labels in hierarchies built in advance (not per frame) using k-means clustering in world space, i.e., 3D space, not 2D screen-space. Combine based on similar strings and proximity?
• Combining labels dynamically based on bounding-box overlap in screen space.
• Force vectors, masses and springs, and collision via separating axis theorem of bounding boxes. Temporally Coherent Real-Time Labeling of Dynamic Scenes. Can we speed this up by only using forces in a local neighborhood? And/or only running this on parts of the screen that need it?

Supporting Cesium Features

• Compute the 2D screen-space bounding-box for a label. Start with computeScreenSpacePosition in Label.js, and then take into account the width and height of the label based on the width and height of all the billboards it is composed of.
• Change label scale based on distance Scale labels based on distance #1075
• Change label translucency based on distance Scale translucency based on distance #1076
• If we implement the force-based approach, we should make a generic particle system for the mass-spring system based on Physically Based Modeling: Principles and Practice. Later we would build a full particle system with it (roadmap).

Test Data

TBA

Papers

• An Empirical Study of Algorithms for Point-Feature Label Placement. 1995
• Physically Based Modeling: Principles and Practice. 1997
• Temporally Coherent Real-Time Labeling of Dynamic Scenes. 2012
• Enhancing the Visibility of Labels in 3D Navigation Maps. 2012

[ognjenb]

Thank you for the summary! There are 2 studies I did not see before.

[pjcozzi]

Chapter 4 of Usability Oriented Visualization Techniques for 3D Navigation Map Display (2014) may also be useful.

[adivalerio80]

I am having an issue in facilities.kml where the labels are cluttered. I have looked ant your suggestions above. I resized the labels and the text but it doesn't solve the whole issue. I am currently trying to make the labels a fixed size in the kml so that when you zoom in they labels naturally get bigger. Do you have any suggestions?

[pjcozzi]

Initial implementation: #4240