A Line-feature Label Placement Algorithm For Interactive 3D Map

As a fundamental part of cartographic representation in the expression of spatial information,map annotation can help users establish relations between objects in the real world and their symbolic representations on a map and get information that can' t be directly derived from the real world,for example,the area of a land and the length of a road.Label placement has been playing an important role in Cartography.When placing labels,the relationship between an annotation and its feature should be easy to identify and there shouldn't be any overlap among labels.Label placement problem in 3D maps bears obvious distinctions from that in 2D maps.In an interactive three-dimensional(3D)map,the relief of the terrain can obstruct annotations.As the perspective moves and rotates freely in 3D space,the occlusion relationship among annotations changes accordingly.The direction of a line in general definitively influences the orientations of the characters in its annotation label,which affects its readability.Furthermore,a line that extends deep into 3D space requires annotation-reference line segments at different scales because the distant parts of a line appear less detailed than closer ones,and the positioning of the text of its annotation should be adjusted accordingly.Supported by the National Natural Science Foundation of China--"Research on Overlaying Typical 2D Vector Features onto 3D Terrain Surface Algorithms"(41371365),a rule set for 3D interactive map line-feature annotations is proposed and a screen-based line-feature annotation-placement algorithm is implemented.The annotation-reference line is clamped to the terrain and a static annotation-reference line hierarchy tree is built in the preprocessing phase.When rendering each frame,a dynamic view dependent annotation-reference line is constructed with the help of this static annotation-reference line tree.View frustum culling,occlusion culling based on shadow map and monotone split are performed on the annotation-reference line,which is then projected onto the screen space.The conflicts among annotations are resolved on screen space using a greedy graph coloring algorithm.The purpose of our algorithm is to ensure that the annotations are readable from multiple angles,not obstructed by other annotations,terrains,or artificial structures,convey the directions of the lines,and conform to the traditional positioning preferences in cartography.The result of experiments shows good readability and high performance.