algorithm - 如何排序/绘制伪 3D 建筑物，以免它们在视觉上重叠

Question

我的 map 上有建筑物的矢量数据，并希望它们根据已知高度突出显示。

我知道这是一项常见任务，但我没有找到任何令人满意的解决方案。

我在 mapnik 中看到了实现，他们使用多边形中所有顶点的最小 Y 值进行简单排序。结果，大部分画对了，但有些仍然重叠(大约 2-3%)。

在大多数情况下，只需将建筑物很好地排序(以某种方式？)并按适当的顺序绘制它们就足够了(对于上述情况，此顺序为 3-2-1)。

在更复杂的情况下，当多边形是凹面且彼此距离太近时，每一面墙和屋顶(屋顶)都应单独绘制(见下文)。

更新:

因此，要绘制两种类型的线段:墙壁和盖子。墙段很容易订购(按最小 Y)。我不知道如何订购上限。

谢谢。

Answer 1

在直墙的情况下，很容易按深度对它们进行分类。只考虑它们的基线，它们是直线段。请注意，每条线将平面分为两部分，其中一部分离观察者较近，另一部分较远。对于任何段 A，将较近的部分称为 A+，将较远的部分称为 A-。现在，对于任意两个段 A 和 B，至少有一个命题成立:

1. A完全属于B+
2. A完全在于B-
3. B完全位于A-
4. B完全属于A+
5. 一段与视线平行，另一段完全位于视线左侧或右侧
6. A 和 B 相交

在情况1和情况3中，B应该在A之前绘制(A可以遮挡B，但B不能遮挡A)；在情况 (2) 和 (4) 中，A 先于 B；对于情况 5，没关系；正常墙壁不应出现 6。

您现在可以对墙壁进行拓扑排序，并从最远到最近绘制它们。

至于屋顶，这对于凹形建筑来说是不可能的，因为屋顶的一部分可能被墙遮挡，而墙又遮挡了同一屋顶的另一部分。想象一个低矮的 U 形建筑物，从它的侧面可以看到，在 U 形的中间有一座高塔。塔将被 U 形屋顶遮挡和遮挡，所以无论您以何种顺序绘制它们，图片都将是错了。

因此，您必须将凹形屋顶分割为凸多边形。然后按照相同的原则将它们与墙壁一起分类应该很容易。

另一种方法是使用 Z 缓冲区，它使您无需考虑顺序。我的印象是现在最低端的低功耗手机显卡都可以得到 Z-buffer。