Abstract
We consider the problem of labeling linear objects, such as streets,
in interactive 3D maps, where the user can continuously pan,
zoom, and rotate a perspective view of the scene.
We dynamically annotate streets that belong to a user's route,
assuming that the future course of the route, within the currently
visible part of the map, is known or well predicted.
We use billboards as annotations,
that is, each label is a rectangle holding the annotation text,
is oriented towards the user,
placed at some distance above the midpoint of the street to be labeled,
and connected to the point by a vertical line segment, the leader.
Our goal is to maintain an overlap-free labeling that
reacts to changes of the view in real time.
To this end, we dynamically vary the lengths of the leaders.
In order to achieve that labels move smoothly,
we do not strictly forbid label–label overlaps.
We present a force-directed algorithm
that applies forces to labels to cause overlapping labels to repel each other,
while keeping leaders as close to their desired length as possible.
On real-world data, with a realistic number of labels,
we obtain frame rates of more than 400 frames per second,
while drastically reducing the total overlapped area per frame,
compared to an algorithm with fixed leader lengths.
Video
The following videos show the implementation of our algorithm. We drive along a street
in the downtown of Würzburg (a town of 120,000 inhabitants in southern Germany).
For the map, we used (an extraction of) an OpenStreetMap data set that is provided by
GEOFABRIK.
We set the number of placed labels to n = 7.
The camera angle we used might be a rather strange one for navigation systems.
Using, however, a steeper angle of the camera to the xy-plane, we
would, at any time, see only a very small number of labels.
In the input data, for many streets, there is no name given.
If we do not know the name of a street, we just use the name of the preceding or the succeeding street.
This is why it seems as if we label the same street several times.
For the first video, we use a rather smooth rotation. On that account, the triangle indicating the car does not always
point straight to the top. We used this type of camera path for the tests presented in the PhD thesis of Nadine Schwartges.
Alternatively, you can download a version of the video with higher resolution (28 MB).
For comparison, we also made a video of the static algorithm where we fixed the lengths of the leaders.
Alternatively, you can download a version of the video with higher resolution (25 MB).
In the final video, for rotations, the pointer stops its drive, rotates, and then it continues its drive.
We used this type of camera path for the tests presented in the paper of AGILE 2015.
Alternatively, you can download a version of the video with higher resolution (28 MB).
For her
PhD thesis (download),
Nadine Schwartges also combined the algorithm for labeling streets along a route with billboards and
the algorithm for embedding curved labels into their streets. For the following video, we use the
same map as before but we remove streets if we do not know the name of the street. On that account, the camera paths differ.
If the video does not work, you can download it (24 MB).