在地图渲染中,建筑物、公园和道路等复杂形状是以多边形的形式存储的——即顶点组成的封闭轮廓。然而,图形处理器 (GPU) 是为填充三角形设计的,而不是任意多边形。为了弥补这一差距,每个多边形都必须经过“三角剖分”,即被切割成一系列三角形。虽然存在多种用于此任务的算法,但 GLOBUS 地图引擎的开发人员发现,他们之前的处理方法(受限 Delaunay 三角剖分)在处理大规模数据时效率低下。具体而言,处理来自华沙某一区域的 370 万个多边形在单核上耗时近三秒,他们寻求通过切换到“耳裁剪”方法来消除这一瓶颈。

耳裁剪的工作原理是识别“耳朵”——即多边形的一个凸角,其两个相邻顶点之间的连线不会与形状的任何其他部分相交。通过反复“剪掉”这些耳朵,多边形最终会坍缩成一组三角形。GLOBUS 团队开发了 'earstrip' 来完善这一过程。他们实施了多项优化,以降低“是否为耳朵”测试的计算成本,这是该算法中最频繁的操作。关键改进包括识别“凹陷”(反射顶点)以缩小搜索区域、跳过对已经是凸多边形的测试,以及使用“桶”系统对凹陷进行空间排序。这些改进使他们能够仅用 489 毫秒处理同样的 370 万个多边形,相比 Delaunay 方法实现了显著的加速。

除了原始速度外,团队还优化了生成的三角形存储方式,以提高 GPU 效率。通过识别多边形内的凸环,他们可以生成“三角形带”——这是一种 GPU 重用前一个三角形的两个顶点来形成下一个三角形的方法。这减少了测试集中产生的 2150 万个三角形所需的索引总数。虽然耳裁剪方法对于大多数地图多边形更快,但团队指出存在一个权衡:对于非常大且复杂的多边形(超过 257 个顶点),Delaunay 方法仍然略快一些,因为耳裁剪的复杂度随多边形大小的平方增长。尽管如此,'earstrip' 为通用的地图渲染任务提供了一个高性能且符合许可要求的替代方案。