asp。net网站开发,wordpress给用户注册,flash网站建设公司,庐江县住房和城乡建设局网站3D渲染引擎设计者面临的最大问题之一是可见性计算#xff1a;只必须绘制可见的墙壁和物体#xff0c;并且必须以正确的顺序绘制它们#xff08;应该在远处的墙壁前面绘制近墙#xff09; 。 更重要的是#xff0c;对于游戏等应用程序来说#xff0c;开发能够快速渲染场景…
3D渲染引擎设计者面临的最大问题之一是可见性计算只必须绘制可见的墙壁和物体并且必须以正确的顺序绘制它们应该在远处的墙壁前面绘制近墙 。 更重要的是对于游戏等应用程序来说开发能够快速渲染场景的算法非常重要。 因此现在存在多种解决可见性计算问题的方法。
二进制空间分区 (BSP) 是一种可用于大大加快 3D 渲染中可见性计算速度的技术。 它已被多款著名游戏使用例如《Doom》和《Quake》。
Map — 这是指正在渲染的区域在游戏中这是游戏地图或关卡。Viewpoint——我们渲染的视角Field of View — 视野从视点的位置和角度可见的地图区域
使用 Doom 使用的二维地图示例来解释该系统。 然而BSP 可以轻松扩展到 3 维或更多——代替 2 维线可以使用 3 维平面等。
1、预先计算
在渲染地图之前我们必须对其执行大量计算。 然而一旦执行这些计算其结果就可以多次使用。 这是 BSP 的优点之一——一旦执行了计算就不需要再次执行除非地图发生更改。 BSP 只允许“静态”地图或者不移动的地图。 如果地图有任何移动部分那么它们必须单独渲染。
必须做的是将地图划分为凸多边形。 凸多边形是所有内角都小于或等于180度的多边形。 例如以下形状是凸多边形 然而以下形状不是凸形的 如果地图被认为是一个非凸多边形我们可以通过在其上画一条分界线将其分成两个子多边形。 例如考虑以下地图 将这个多边形一分为二时我们创建了两个“子多边形”。 这种划分可以用一个简单的树来表示 现在可以递归地划分两个子多边形中的每一个。 每个分支都会为树产生一个新的“分支”。 递归一直持续到地图被划分为凸多边形即树的“叶子”。 出于显而易见的原因如果可能的话希望保持树“平衡”也就是说保持树两侧的高度大致相等。 2、渲染
使用 BSP 树的渲染也是使用递归算法完成的。 最常见的方法是从根节点树的顶部开始并递归地向下工作。 这就是为什么需要保持树平衡这减少了递归的数量。 递归到大深度可能会显着减慢渲染速度。
可见性排序系统的核心在于渲染函数递归的顺序。 也就是说给定节点的左子树还是右子树是否先渲染。 对于任何特定节点都有一条分界线将其分为两个子节点。 如果这条线延伸到无穷远我们渲染的视点可以被认为是在“左”或“右”侧。 视点所在的一侧决定首先渲染哪个子节点。 请注意实际上有两种执行渲染的方式
从后到前
在从后到前的渲染器中首先渲染远处的墙壁并被较近的墙壁遮挡。 这是上图中使用的系统。 从后到前渲染的缺点之一是过度绘制 - 绘制的部分墙壁被较近的墙壁遮挡而看不到。 这是不必要的开销。
从前到后
从前到后渲染器以相反的方式工作首先渲染较近的墙壁然后将较远的墙壁剪裁到已绘制的墙壁上。 因为它没有过度绘制所以几乎所有实用的 BSP 渲染器都使用从前到后的方法。
因此简单的从后到前渲染器的一些示例伪代码将是
function render(node)
{if this node is a leaf{draw this node to the screen}else{determine which side of the dividing line the viewpoint isif it is on the left side{render(right subnode)render(left subnode)}else{render(left subnode)render(right subnode)}}
}
bsp 树的主要缺点是整个地图必须是静态的不可移动——如果其中一部分移动则必须重建整个树。 克服这个问题的一种方法是将静态和移动部分分开并分别渲染它们。 3、BSP 树的其他用途
除了可见性排序之外BSP 树还有许多其他用途。 其中之一是以分层方式划分地图例如这样允许将地图的大部分排除在渲染过程之外 - 如果所有特定节点都在视点的视野之外则该节点可以从渲染中丢弃。 这是加速渲染引擎的快速有效的方法。
这棵树还可以用于许多其他效果例如阴影。
