有一次，在游戏开发过程中，我遇到了现代PC的性能问题。 我们的建模者有一台功能强大的现代红色装配计算机。 但是他让我们的项目非常缓慢，加载了一个处理器核心。
原因很简单-新处理器具有许多内核，但实际上它们在单线程应用程序中的效率较低。 当时，我在一个流中制作了一个渲染图。 但实际上，原因并不多。 在发现问题的过程中，我决定计算场景中存在多少个多边形：
在平均游戏地图上，具有最大距离并带有大量棕榈树
-15 824 756个三角形！ 差不多1600万！ 数量庞大。
在使用地图生成器玩了一点之后，我设法找到了一个1675万的地方：
尽管在这里，一个类似圣诞树的地方只提供了850万个三角形：
平均场景约为400万：
总的来说，我很高兴我的渲染可以处理如此大量的三角形，但是三角形的数量却过多。 解决方案是在表面上：
- 优化模型中的多边形数量。
- 优化景观的多边形网格。
- 实现多线程渲染。
对于那些可能对我们的优化计划的第一部分不感兴趣的人，例如经验不足的专家，我建议您安全地进入第二部分。
1.优化模型中的多边形数量
在我们的引擎中，植被是按“包装”绘制的，整个景观分为瓷砖和小块，最小包装是一个小块。
一包就是一个网格，因为减少网格数量会大大减少CPU-> GPU调用的数量。
最初，我们的树木由截锥组成，移到全锥，我们设法删除了几个额外的三角形：
蛋糕上的樱桃决定将树干从树上移开，因为从我们的摄影机角度来看，它们根本不可见。
结果，我们设法将一包圣诞树上的多边形数量平均减少了40％。 差异几乎是看不见的：
对于棕榈树来说，难度更大，但需要修复成捆的5000-6000个多边形。 如何实现丛林的规模和密度？ 由于大量的棕榈树，丛林的高密度得以实现：
我们决定简化手掌，并引入第二层植被，这使我们能够保持可见的密度并达到每包600至700个所需的多边形。
将多边形的数量减少10倍是一个极好的结果。
2.多边形网格景观的优化
最初，景观网格为：
屏幕截图显示了景观的平原部分，这些部分是草地，平原和其他光滑表面的瓷砖。 我决定删除景观中的小不规则之处。 因此，他增加了相同高度瓷砖的面积。 通过巧妙地检查瓦片和子瓦片的所有顶点的高度是否相等，我无法实现以下结果：
仍然有可以优化的平坦地方，我开始从那些具有相同高度的三角形构建多边形。 拍摄了一块瓷砖，并将其所有三角形分类为不等高三角形的数组以及由高度相等和相邻三角形组成的数组的列表。
在给定的示例中，结果是：无法更改的1个三角形数组，因为它们都是不同的高度（红色三角形），并且由两个具有相同高度的三角形数组组成的列表（这些数组用颜色填充）。
现在的任务是从三角形阵列中找到它们的凸凹轮廓（凹壳），许多三角形可能有孔。 早些时候，我在工作中遇到了Convex Hull，但它们没有问题，我已经使用了Graham算法。 但是凹面船体的建造存在问题。事实证明，在互联网上查找有关此主题的信息非常困难。 我不得不从头开始编写算法的实现。 如果我说我已经读过关于该主题的十篇不同的论文，我不会说谎。 但是所有提出的算法都给出了近似结果，但有一些误差。 经过一周的折磨和痛苦，我想到了算法的想法。
我试图从三角形的顶点集构建轮廓，即 我将三角形数组转换为顶点数组，并已经在它们上构建了一个壳。 但是对于我的任务，这不是必需的。 根据我的结论，直接从三角形构建壳体更容易，并且凹壳的精度为100％。
最初，我想在这里放一个算法的源代码的拼凑而成，但简而言之似乎更容易描述它：基本原则是：如果三角形的顶点包含在四个或更少的三角形中，那么形成顶点的边之一就位于边界上。 接下来，考虑到相同边缘的去除，形成这样的边缘的列表。 我们找到具有最小X和Y的边，并从中开始对边进行通过/排序，并在列表中添加唯一的顶点。 此列表将是许多三角形的外壳。 最后，唯一的事情就是从列表中删除共线点。
结果，我可以建造几乎任何复杂的凹面船体。 该算法不适用于孔组，但我通过简单地将此组分为两个半孔来解决了这个问题。 然后我得到了电路并对其进行了三角测量：
一切都很好：
但是最后，我对结果感到不安。 我开发的算法在渲染场景时显着提高了性能，因为多边形的平均数量减少了60-70％。 但是与此同时，卡片生成的速度开始慢了10倍。 结果证明该算法非常耗时。
花了三天的时间来考虑算法的轻量级版本，以优化景观的多边形网格，从而得出以下结果：
现在，在地图生成的背景下，用于优化的数据计算变得不那么明显了，多边形的数量平均减少了40-50％。
本文是试验性和肤浅的。 如果有人对游戏开发这个主题感兴趣，我准备继续并以具体的步骤，解决方案和未来计划作为扩展。 另外，我想您会对构建用Java开发的多线程Open GL应用程序感兴趣，我将在下一篇文章中尝试讨论该主题。