Rapid Labels: Point-Feature Labeling on GPU.

Labels, short textual annotations are an important component of data visualizations, illustrations, infographics, and geographical maps. In interactive applications, the labeling method responsible for positioning the labels should not take the resources from the application itself. In other words, the labeling method should provide the result as fast as possible. In this work, we propose a greedy point-feature labeling method running on GPU. In contrast to existing methods that position the labels sequentially, the proposed method positions several labels in parallel. Yet, we guarantee that the positioned labels will not overlap, nor will they overlap important visual features. When the proposed method is searching for the label position of a point-feature, the available label candidates are evaluated with respect to overlaps with important visual features, conflicts with label candidates of other point-features, and their ambiguity. The evaluation of each label candidate is done in constant time independently from the number of point-features, the number of important visual features, and the resolution of the created image. Our measurements indicate that the proposed method is able to position more labels than existing greedy methods that do not evaluate conflicts between the label candidates. At the same time, the proposed method achieves a significant increase in performance. The increase in performance is mainly due to the parallelization and the efficient evaluation of label candidates.

Mixed Labeling: Integrating Internal and External Labels.

In this article, we present an algorithm capable of mixed labeling of 2D and 3D objects. In mixed labeling, the given objects are labeled with both internal labels placed (at least partially) over the objects and external labels placed in the space around the objects and connected with the labeled objects with straight-line leaders. The proposed algorithm determines the position and type of each label based on the user-specified ambiguity threshold and eliminates overlaps between the labels, as well as between the internal labels and the straight-line leaders of external labels. The algorithm is a screen-space technique; it operates in an image where the 2D objects or projected 3D objects are encoded. In other words, we can use the algorithm whenever we can render the objects to an image, which makes the algorithm fit for use in many domains. The algorithm operates in real-time, giving the results immediately. Finally, we present results from an expert evaluation, in which a professional illustrator has evaluated the label layouts produced with the proposed algorithm.