Accelerated Algorithms
- 格式：pdf
- 大小：5.63 MB
- 文档页数：86
26
2.2 八叉树
八叉树有一个非常明显的不足，就是会将位于八叉树中心的（比较小）物体放置在最 高节点上。这样，效率就会很低，因为一开始总要和这个物体进行比较。解决方法： （1）对这个物体进行分割，但是会引入更多的图元 ；
（2）在每个叶子长方体所包含的物体上放置一个指针，但是却会丧失效率，同时使得 八叉树的编辑变得更为困难 。
• What is it? – Data structure that organizes geometry in 2D or 3D or higher – The goal is faster processing – Needed for most ”speed-up techniques” • Faster real-time rendering • Faster intersection testing • Faster collision detection • Faster ray tracing and global illumination – Games use them extensively – Movie production rendering tools always use them too
Ulrich提出了第三种解决方法：松散八叉树。所谓松散就是 说对空间的分割比较任意。
27
2.2 八叉树: 松散八叉树
松散八叉树的基本思想与普通八叉树一样，但是每个长方体的大小选择比较宽松。如 果一个普通长方体的边长为l，那么就可以使用kl，其中k1，下图所示为k=1.5的松散 八叉树和一个普通八叉树的比较。通过使用大的长方体，就可以减少穿过分割平面的 物体数量，从而将物体沿着八叉树放置在更深的位置。
20
2.2 BSP树(Binary Space Partitioning Tree
Two different types: – Axis-aligned – Polygon-aligned General idea: – Divide space with a plane – Sort geometry into the space it belongs – Done recursively If traversed in a certain way, we can get the geometry sorted along an axis. – Exact for polygon-aligned – Approximately for axis-aligned
排序：
25
2.2 八叉树
八叉树类似于轴对齐BSP树。沿着长方体的三条轴对长方体进行同时分割，分割点 必须位于这个长方体的中心，这样可以生成8个新的长方体。
开始，用一个包围盒将所有的多边形包围起来，如最左边的图 所示。然后，以递归方式将这个包围盒分割为四个大小相等的 盒子，直到每个盒子都是空的或者只包含一个物体。
精确方法 - Compute all the polygons which are at least partially visible but only those 近似方法 - Compute most of the visible polygons and possibly some of the hidden ones 保守方法 - Compute all visible polygons plus maybe some hidden ones
4
１ 实 时 加 速 算 法 的 研 究 动 机 Big Models:
Submarine Torpedo Room
700,000 polygons
5
１ 实 时 加 速 算 法 的 研 究 动 机 Big Models:
Coal-fired Power Plant
13 million polygons
•场景复杂程度和规模的增大很难满足实时性要求
现实场景的规模更是庞大
10
１ 实 时 加 速 算 法 的 研 究 动 机
•解决策略
(1) 硬件加速； (2) 减少绘制负荷；
•具体方法
(1) 空间数据的有效组织； (2) 可见性裁减； (3) LOD技术； (4) 基于图像的绘制
11
２ 空 间 数 边形对齐BSP树
将多边形作为分隔物，对空间进行平分。
多边形分别从A到G。首先用多边形A对空间进行分割，生成的两个 半空间分别由多边形B和C分割，由B形成的风格平面与左下角的多 边形相交，将其分割为两个多边形D和E。最后形成的BSP树如右图 所示。
24
2.2 BSP树：用途示例
实时绘制的加速算法
普建涛
pjt@ 理科2号楼2224房间
北京大学视觉与听觉国家重点实验室 2003-09-10
“Now here, you see, it takes all the running you can do to keep in the same place. If you want to get somewhere else, you must run at least twice as fast as that!” —Lewis Carroll
6
１ 实 Big Models: Plant Ecosystem Simulation 时 加 16.7 million polygons (sort of) l 速 算 法 的 研 究 动 机
7
１ 实 时 加 速 算 法 的 研 究 动 机
潜水艇整个模型 （>82 million三角形面片）
•场景复杂程度和规模的增大很难满足实时性要求
主要目的是通过对遮挡关系进行快速判断，扔弃大量不需要绘制 的图形对象，降低场景的复杂程度，实现低负荷绘制和最佳的绘 制效果，在需要网络传输的时候，也可以降低传输负荷。
31
３ 可 见 性 裁 减 技 术
•可见性问题的难点：
(1)复杂场景的非连续变化性。观察者视点空间位置的微 小变动可能会造成显示帧率急剧变化，产生“POPING”或 者空白现象，影响漫游效果。
内 容 提 要
为什么要研究实时加速算法 g 空间数据组织 g 可见性裁减技术 g LOD技术 g 总结
g
2
１ 实 时 加 速 算 法 的 研 究 动 机
应该强调的是，足够高的帧率和平稳（没有变化）的帧率同样 重要。通常希望得到一个平滑、连续的帧率，帧率过低会给人 一种快速抖动的感觉。
•在实时绘制中，在性能上至少有三个目标:
12
２ 空 间 数 据 组 织
• 具体方法
– 包围体树 – BSP树 – 八叉树
13
2.1 包围体树
一个包含6个物体的简单场景，每个物体都由一 个包围球封闭起来，其中可以将包围球归组为 一个更大的包围球。如此类推，直到所有的物 体由最大的球体包围。
14
2.1 包围体树: 示例
In follow example, assume we click on screen, and want to find which object we clicked on。
)
21
2.2 BSP树：轴对齐BSP树
沿X\Y\Z轴进行分割:
22
2.2 BSP树：轴对齐BSP树
Each internal node holds a divider plane Leaves hold geometry Differences compared to BVH – Encloses entire space and provides sorting – The BV hierarchy can be constructed in any way (no sort) – BVHs can use any desirable type of BV
The data structure is a k-ary tree: – Leaves hold geometry – Internal nodes have at most k children – Internal nodes hold BVs that enclose all geometry in its subtree.
1) Test the root first 2) Descend recursively as needed 3) Terminate traversal when possible In general: get O(log n) instead of O(n)
点击位置
15
2.1 包围体树
Most common bounding volumes (BVs): – Sphere; – Boxes (AABB and OBB); The BV does not contribute to the rendered image -- rather, encloses an object.
视点的稍微变化导致场景复杂度急剧变化：
•可见性问题的难点：
33
3.1 可见性判断分类
可见性问题的表现形式可以分为三种： （1）基于视锥的可见性判断； （2）实体自身的可见性判断； （3）实体之间的遮挡关系判断。
存在三种可见性状态：完全可见、完全不可见、部分可见部分不可见。
34
3.1 可见性判断分类
潜水艇舱内部 （>60万三角形面片）
8
１ 实 时 加 速 算 法 的 研 究 动 机 Big Models:
The Digital Michelangelo Project
David: 56,230,343 polygons St. Matthew: 372,422,615 polygons
9
１ 实 时 加 速 算 法 的 研 究 动 机
17
2.1 包围体树: 创建方法1
Find minimal box, then split along longest axis：
