遮挡剔除3D变换后的2D矩形？

Question

遮挡剔除3D变换后的2D矩形？

4

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

现在，这很简单，直到你遇到需要将层推回的3D转换，需要将层分成几个多边形来正确呈现它，如下图所示。由于可以有透明度，层可能没有完全被遮挡，同时需要分割。

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

example

请问有人能够建议一种在CPU上完成此操作的好方法吗？我已经很难找到适合这种情况的算法实现（使用C ++或C）。 编辑： 为了澄清，此阶段尚未进行渲染。我们只需要为每个层生成一组多边形，这些多边形将表示层的变换和遮挡几何。然后，如果需要，进行渲染（软件或硬件），并不总是必须的（例如，在执行命中测试时）。 编辑2： 我考虑过二进制空间分割作为实现这一目标的选项，但我只能找到一个实现（在GL2PS中），我不知道如何使用它。我对BSP的工作原理有些模糊的了解，但我不确定它们如何用于遮挡剔除。 编辑3： 我不是在尝试进行颜色和透明度混合。仅处理纯几何体。透明度可以由渲染器处理，并且重绘是可以接受的。在这种情况下，蓝色多边形可以在红色多边形下面绘制，但对于更复杂的情况，可能需要深度排序甚至拆分多边形（像下面这样的可怕案例的示例）。虽然视口是固定的，但由于所有层都可以在3D中变换，因此可以创建下面显示的形状。

我需要的算法是将图层B几何地分成两个蓝色形状，其中一个形状会被“上面”绘制，另一个则会被“下面”的R覆盖部分遮盖，但这不是主要问题。因此，只需将B分成两个多边形，这样在以顺序绘制这些多边形时，它们似乎穿过了R。无需担心混合效果。编辑4：就此而言，我们不能渲染任何内容。这一切都必须纯粹地通过几何方式实现（生成2D多边形）。这就是我最初想到的。 编辑5：我应该指出，每个子场景的总四边形数量约为30（平均值）。除非图层被3D变换（这就是这个问题出现的地方），否则它们只是按Z位置进行基数排序，然后按添加顺序（先进先出）绘制具有相同Z位置的图层。如果我没有在原始问题中表述清楚，那我很抱歉。

- Kristina Brooks

根据解决方案的普遍性，这里有一个问题概述（来自OpenGL的角度），请点击此链接：http://www.opengl.org/wiki/Transparency_Sorting。 - Brett Hale

我可以问一下你不使用GPU来做这件事情的目的是什么吗？OpenGL或其他API的版本会使这个过程更容易且可移植。 - Michael Dorgan

@Michael Dorgan：这个程序旨在适用于多个平台，其中一些平台没有任何OpenGL功能，只能填充2D纹理多边形（有些甚至没有GPU，因此必须使用纯软件来完成）。这个想法是拥有一种通用的方式来构建场景图，然后让后端绘制多边形。 - Kristina Brooks

这将迫使您采用最低公共分母风格编码。在Color Gameboy样式图形下运行XBox360不会很受欢迎。这可能是您需要为低端系统提供OpenGL解决方案和“虚假”解决方案的情况。 - Michael Dorgan

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/30149/discussion-between-christina-brooks-and-michael-dorgan - Kristina Brooks

显示剩余7条评论

2个回答

0

我打算直截了当地给出一个简单的解决方案，这可能不适合你的问题。为什么不直接修改你的艺术作品，以防止这个问题的发生。

对于问题1，在Maya或其他软件中事先分割多边形。对于3条线的问题，同样，在交叉处将你的多边形进行分割，以防止冲突。预先计算的解决方案总是比即时计算的更快-特别是在有限的硬件上。根据我的专业经验，我可以说，它也具备可扩展性，尽管可能需要从艺术方面进行一些微调和技术审查，以确保没有创建"非法"的东西。使用这种方法可能会导致多一些的多边形，但至少你不必在可能无法胜任任务的CPU上进行大量的数学计算。

如果你无法控制艺术工作流程，那么这种方法就行不通了，因为编写某种转换器所需的时间比启动并运行一个BSP子细分程序更长。不过，简单始终是最好的解决方案。

- Michael Dorgan

这是通过编程动态创建的场景。所涉及的嵌入式CPU实际上在执行数学运算方面并不差，并且具有SIMD扩展。那么BSP是最好的选择吗？请记住，我们最多只会在一个图层中使用30个左右的多边形。遮挡剔除是按图层平面进行的，仅在需要时进行（如果应用了3D变换，则不常见）。 - Kristina Brooks

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SigTerm · Accepted Answer

如果您“不擅长计算机图形”，使用CPU进行软件渲染将非常困难，特别是当多边形可以透明时。最简单的方法是使用GPU渲染（OpenGL / Direct3D）和深度剥离技术。

CPU解决方案：

解决方案＃1（极其困难）：

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

您需要将多边形B分成两部分，例如使用多边形A作为裁剪平面，然后使用画家算法渲染结果。为此，您需要更改渲染例程，使其不再使用四边形，而是使用纹理多边形，并编写/调试剪辑例程，以使场景中存在的三角形以不会破坏画家算法的方式进行拆分。

一个大问题是：如果有许多多边形，则此解决方案可能将场景拆分为无限数量的三角形。此外，自己编写纹理渲染代码并不好玩，因此建议使用OpenGL / Direct3D。

这可能非常难以正确实现。我认为这种方法在“使用OpenGL进行计算机图形学第二版”（作者：Francis S. Hill）中有所讨论，可能在其中一个练习中。

另外，请查看维基百科关于隐藏表面去除的文章。 解决方案＃2（更简单）：

您需要实现多层z-buffer，它可以存储最多N个透明像素及其深度。 解决方案＃3（计算昂贵）：

只需使用光线追踪。您将获得完美的渲染结果（没有深度剥离和CPU解决方案＃2的限制），但它将是计算上昂贵的，因此您需要大量优化渲染例程。 底线： 如果您正在执行软件渲染，请使用解决方案＃2或＃3。如果您正在使用硬件渲染，请使用类似于深度剥离的技术，或在硬件上实现光线追踪。 - 编辑-1 - 实现 #1 和 #2 所需的知识是 "线-平面交点"。如果你理解如何使用平面将一条线（在三维空间中）分成两段，你可以轻松地实现光线追踪或剪辑。

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

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

--编辑-2--

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

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

--编辑-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缓冲区。

想一想，这是一个对于专攻计算机图形的大学非常好的训练练习。这种练习可能会让你的学生讨厌你。