3D geospatial data is frequently augmented with vector data, like points, lines, and polygons, to enhance understanding. For example, a polygon can represent a building footprint or a swath of satellite coverage. Some of these polygons can become particularly large and even encircle the entire globe.
Polygons that approached this scale were sometimes seeing strange visual artifacts. Something in our polygon rendering pipeline was going amiss. So what's so special about big polygons on a 3D globe?
To render any geometry, we must break it down into triangles to create a mesh. The process to break an arbitrary simple polygon into triangles has been well defined in 2D. In CesiumJS, we use a library called earcut, which is fast enough for real-time triangulation in the browser.
We must first project the polygon positions to 2D. Previously, we would always project the polygon vertices onto a plane tangent to the ellipsoid. This worked great for polygons that did not span a large extent around the globe, as the projection produced little distortion when near the point of tangency.
But it's not possible to project all points on an ellipsoid or sphere to a single plane. As you get farther from the point of tangency, there is more distortion. For extents of more than 180 degrees, the projection to a tangent plane always produces incorrect results, as positions "wrapped back" on themselves when viewed in 2D.
From a performance standpoint, splitting polygons can be an expensive operation at the time of geometry creation, as the algorithm operates on each polygon edge and for each splitting plane. However, once triangulated, any split polygons are recombined later in the pipeline as part of the geometry batching step to ensure the same rendering performance as before.
Based on the polygon’s extent, we can save time by performing splitting operations only when we know it’s large enough. But for each time we project to a different space, the more times we’ll need to run through the splitting algorithm and the more the penalty there will be on runtime performance.
Even assuming an extent of no larger than 90 degrees, we would need to split a polygon a maximum of three times: on the x-axis, y-axis, and z-axis.
Maybe the cartesian coordinate system is limiting us here. What about a different projection? For instance, cubemaps are a well-known way of projecting a 3D sphere to a 2D space for rendering skyboxes or environment maps.
The problem here is that not all projections are conformal; they do not properly preserve shape or the relative angles between the points. Although they can commonly distort area (which is why this type of projection is not commonly seen for mapping outside of polar regions), preserving shape is crucial for the geometric operations we perform on polygons. We rely on shape not only for the accuracy of triangulation but also for any clipping operations, determining winding order, or tests if the poles lie inside or outside the polygon.
One projection in particular had very few locations which would require splitting a polygon. Stereographic, or polar, 3D cartesian points can be projected from the South Pole to a plane tangent to the North Pole, or vice versa.
The catch is that, because of precision issues with trigonometric functions at small angles, these projections are valid only for a little greater than one hemisphere. To handle this, we split polygons at the equator, making sure to handle the correct arc type for each edge. We need to perform only one split operation on the plane where z = 0.
Using stereographic coordinates also allows us to do many operations that would be tricky on a sphere with "simple" vector math. For example, we can now determine whether a pole lies inside or outside a polygon based on the sum of the angles of the polygon relative to the origin, and we can generate the correct cartographic bounds for the polygon.
If you have datasets with larger polygons, give them a try in the most recent version of CesiumJS!