4

所以，首先，我不太擅长计算机图形学。我正在尝试实现一个 GUI 工具包，其中一个功能是能够将 3D 转换应用于 2D“层”。（一个图层只有一个 Z 坐标，作为预变换，它是一个二维轴对齐的矩形）

现在，这非常简单，直到您遇到将图层向后推的 3D 转换，需要将图层拆分为多个多边形才能正确渲染，如此处所示。而且因为我们可以有透明度，所以图层可能不会完全被遮挡，但仍然需要拆分。

所以这里有一个描述问题和预期结果的插图。在这种情况下，蓝色层（称为B）位于红色层（R）的顶部，同时具有相同的 Z 位置（但B是在R之后添加的）。在这种情况下，如果我们旋转B，它的顶部两个点的 Z 索引将低于 0，而底部点的索引将高于 0（锚点是唯一剩下的点/线为 0）。

例子

有人可以建议在 CPU 上执行此操作的好方法吗？我一直在努力寻找适合这种情况的合适算法实现（在 C++ 或 C 中）。

编辑：为了澄清我自己，在管道的这个阶段，还没有渲染。我们只需要为每一层生成一组多边形，然后代表层的变换和遮挡几何。然后，如果需要，渲染（软件或硬件）会在需要时完成，但情况并非总是如此（例如，在进行命中测试时）。

编辑 2：我将二进制空间分区视为实现此目的的一种选择，但我只能找到一个实现（在 中GL2PS），我不确定如何使用它。我对 BSP 的工作原理有一个模糊的理解，但我不确定它们如何用于遮挡剔除。

编辑 3：我不想在这个阶段进行颜色和透明度混合。只是纯几何。透明度可以由渲染器处理，过度绘制是可以的。在这种情况下，蓝色的多边形可以只画在红色的下面，但是对于更复杂的情况，可能需要深度排序甚至拆分多边形（如下面的可怕案例示例）。虽然视口是固定的，但由于所有图层都可以进行 3D 变换，因此可以创建如下所示的形状。

所以我真正在寻找的是一种算法，它将B层几何分割成两个蓝色形状，其中一个将绘制在“上方”，其中一个将绘制在R下方。“下面”的部分会透支，是的，但这不是主要问题。所以B只需要被分成两个多边形，这样当这些多边形按顺序绘制时，它就会穿过R。无需担心混合。

圆

编辑 4：为此，我们根本无法渲染任何东西。这一切都必须以纯几何方式完成（生成2D多边形）。这就是我最初的目的。

编辑 5：我应该注意到每个子场景的四边形总数约为 30（平均）。绝对不会超过 100。除非图层经过 3D 转换（这是出现此问题的地方），否则它们只是在绘制之前按 Z 位置排序的基数。具有相同 Z 位置的图层按添加顺序（先进先出）绘制。

抱歉，如果我在原始问题中没有说清楚。

4

2 回答 2

2

如果您“不擅长计算机图形学”，如果多边形可以是透明的，那么在 CPU（软件渲染）上进行操作对您来说将非常困难。

最简单的方法是使用 GPU 渲染 (OpenGL/Direct3D) 和深度剥离技术。

处理器解决方案：

解决方案＃1（非常困难）：

（我忘记了这个算法的名称）。

您需要将多边形 B 一分为二，例如，使用多边形 A 作为裁剪平面，然后使用画家算法渲染结果。为此，您需要更改渲染例程，以便它们不再使用四边形，而是使用纹理多边形，此外，您还必须编写/调试剪辑例程，这些例程将以这样的方式分割场景中存在的三角形：将不再破坏 paitner 的算法。

大问题：如果你有很多多边形，这个解决方案可能会将场景分割成无数个三角形。另外，自己编写纹理渲染代码也不是很有趣，所以建议使用 OpenGL/Direct3D。

要做到这一点非常困难。我认为这种方法在“Francis S. Hill”的“Computer Graphics Using OpenGL 2nd edition”中讨论过——在他们的一项练习中。

另请查看有关Hidden Surface Removal的维基百科文章。

解决方案#2（更简单）：

您需要实现多层z 缓冲区，最多可存储 N 个透明像素及其深度。

解决方案 #3（计算成本高）：只需使用ray-tracing。您将获得完美的渲染结果（没有深度剥离和 cpu 解决方案#2 的限制），但它的计算成本很高，因此您需要大量优化渲染例程。

底线：

如果您正在执行软件渲染，请使用解决方案 #2 或 #3。如果您在硬件上进行渲染，请使用类似于深度剥离的技术，或在硬件上实现光线追踪。

--edit-1--

实现#1 和#2 所需的知识是“线平面相交”。如果您了解如何使用平面将线（在 3d 空间中）分成两部分，则可以轻松实现光线跟踪或裁剪。

#2 所需的知识是“带纹理的 3d 三角形渲染”（算法）。这是一个相当复杂的话题。

为了实现 GPU 解决方案，您需要能够找到一些处理着色器的 OpenGL 教程。

--编辑-2--

透明度是相关的，因为为了获得正确的透明度，您需要使用画家算法从后到前（从最远到最近）绘制多边形。在某些情况下正确排序多边形是不可能的，因此必须拆分它们，或者您应该使用列出的技术之一，否则在某些情况下会出现伪影/错误渲染的图像。

如果没有透明度，你可以实现标准的 zbuffer 或者使用硬件 OpenGL 绘制，这是一个非常简单的任务。

--edit-3--

我应该注意到每个子场景的四边形总数约为 30（平均）。绝对不会超过100。

如果你要分割多边形，它很容易超过 100。

有可能以这样的方式定位多边形，即每个多边形将分割所有其他多边形。

现在，2^29 是 536870912，但是，不可能以这样的方式用平面分割一个表面，即在每次分割过程中多边形的数量会加倍。如果一个多边形被分割 29 次，在最好的情况下你会得到 30 个多边形，如果分割平面不平行，在最坏的情况下可能会得到数千个多边形。

这是应该起作用的粗略算法大纲：

  1. 准备场景中所有三角形的列表。
  2. 去除背面的三角形。
  3. 找到所有在 3d 空间中相交的三角形，并使用相交线将它们分割。相交线
  4. 计算所有三角形的所有顶点的屏幕空间坐标。
  5. 按画家算法的深度排序。
  6. 为新的原语准备额外的列表。
  7. 查找在 2D（投影后）屏幕空间中重叠的三角形。
  8. 对于所有重叠的三角形，检查它们的渲染顺序。基本上，将要在另一个三角形“下方”渲染的三角形不应该有位于另一个三角形上方的部分。
    8.1。为此，使用相机原点和三角形边缘将原始三角形分割成几个子区域，然后检查区域是否符合已建立的排序顺序（为画家算法准备）。区域是通过使用由相机原点和三角形边缘创建的 6 个剪辑平面分割现有的三​​角形对来创建的。在此处输入图像描述
    8.2. 如果所有区域都符合渲染顺序，则保留三角形。如果没有，则从列表中删除三角形，并将它们添加到“新基元”列表中。
  9. 如果新基元列表中有任何基元，则将列表与三角形列表合并，然后转到#5。

通过查看该算法，您可以轻松理解为什么现在每个人都使用 Z-buffer。

想一想，这对于专门研究CG的大学来说是一个很好的培训练习。那种可能会让你的学生讨厌你的练习。

于 2013-05-16T11:12:49.160 回答
0

我要出来说给出更简单的解决方案，这可能不适合你的问题。为什么不只是改变你的作品来防止这个问题发生。

在问题 1 中，只需在 Maya 或其他任何东西中预先划分多边形。对于 3 线问题，再次在交叉点划分多边形以防止打架。预先计算的解决方案总是比运行中的解决方案运行得更快——尤其是在有限的硬件上。从专业经验来看，我可以说它也可以缩放，它可以缩放。它只需要从艺术方面和技术审查方面进行一些调整，以确保没有“非法”创建。与动态渲染相比，您最终可能会获得更多的多边形，但至少您不必在可能无法完成任务的 CPU 上进行大量数学运算。

如果您无法控制艺术作品流水线，这将不起作用，因为编写某种转换器比启动和运行 BSP 细分例程需要更长的时间。尽管如此，KISS 通常是最好的解决方案。

于 2013-05-17T18:31:47.063 回答