Convex-Hull-Directed Edge Routing Geometric Optimization

The realistic Digital Earth, whose surface is covered with terrain elevation and remote sensing image, brings terrain occlusion and image disturbance to 3D graph visualization. We propose a terrain-constrained 3D edge routing optimization problem to obtain the optimal edge with the shortest length and the fewest terrain feature points while keeping the convexity and terrain disocclusion. The main idea is to solve combinatorial optimization using a convex-hull-directed geometric technique. A convex hull capability model (CHCM) describes that the convex hull can not only extract topographic feature points, but also support graph aesthetic criteria. Under the guidance of CHCM, the optimization is solved by the two chains of geometric evolution: the first one extracts topographic feature polyline via an auxiliary closed convex hull on the 2D earth slice, and the second one uses convex-hull-based convex-preserving Bezier interpolation to further smooth the polyline as optimal edge. In addition, the lightness of the remote sensing image is adjusted in color space to reduce image interference. Simulation results show that our approaches can eliminate visual clutters such as piercing mountains and visual zigzags caused by terrain occlusion, in the experimental case, the number of 3D projected edge intersections is reduced by 42%, and topographic feature points only account for 24% of the total sampling points. The geometric and image-based compound framework will provide a general design solution for 3D graphic visualization on various realistic earth platforms.