3D扫描技术的进步使数亿多边形网格的实际创建得以实现。用于显示、简化渐进式网格传输的传统算法对于这种尺寸的数据集而言是不切实际的。我们定义了一个用于表示和逐步显示这些网格的系统,这些网格将基于边界球体的多分辨率层次结构与基于点的渲染系统结合在一起。
专门使用一个数据结构用于视锥截取,背面剔除,细节层次选择和渲染。这种表示方法非常紧凑,可以快速计算,适用于大型数据集。我们是为了用于大型3D数字化项目而编写的,它可以快速启动,保持用户可设置的交互式帧速率,而不管对象的复杂程度或相机位置如何,在运动过程中产生合理的图像质量,并在空闲时逐渐细化为高的最终图像质量。我们已经在包含数亿样本的扫描模型上演示了该系统。
分类和学科描述:
I.3.3 [计算机图形]:图片/图像生成 - 显示算法;
I.3.5 [计算机图形]:计算几何和对象建模 - 曲线,曲面,实体和对象表示;
I.3.6 [计算机图形]:方法和技术 - 图形数据结构和数据类型。
关键词:渲染系统,空间数据结构,细节层次算法,压缩算法
1 简介
计算机图形学最近的一个重大趋势是在渲染过程中向着使用实时对象采样表现方式转变。这种趋势的一个例子是越来越多地使用三维扫描系统,它可以生成物理对象三维采样模型。然而,3D扫描仪的一个问题是如何处理他们生产的大量数据。在过去几年中,3D扫描系统的硬件和软件组件的改进已经将实际可获得的扫描网格大小增加到数亿个样本。
当前工作站不能实时显示这种尺寸的网格,传统网格简化和逐步显示算法的运行时间和空间需求使得这些方法对于包含超过几百万个样本的扫描网格来说不切实际。而且,许多这样的技术着重于优化单个边和顶点的布局,每个顶点将会消耗大量精力。然而,扫描的数据通常具有大量的顶点,并且由于噪声的原因,它们的位置往往不够精确。这揭示存在一种替代方法,这种方法将个别点视为相对不重要,这样对原始网格而言实际上降低了消耗。最近采用这种范式的研究包括Krishnamurthy和Levoy的样条拟合系统[Krishnamurthy 96],Curless和Levoy[的距离图像合并系统Curless 96],以及基于八叉树粒子的Yemez和Schmitt渲染系统[Yemez 99]。这些算法不会精确处理范围数据,实际上也不会保留原始网格的任何样本的3D位置。
遵循这种低基本成本算法的趋势,我们开发了一种用于大型网格交互式显示的新算法。这个被称为QSplat的算法是在一个大型3D数字化项目[Levoy 00]的过程中设计的。由于它使用基于遍历边界球体层次结构的简单渲染算法,因此适合浏览此项目中生成的模型,该模型包含1亿至10亿个样本。此外,QSplat不保持输入网格的连通性(在扫描固有数据时仅能用于解决深度不连续性而没有其他意义),而是依赖于基于点的表示和图示渲染(splat rendering)。因此,我们的系统比类似的基于多边形的系统具有更低的预处理和渲染成本。
在本文中,我们将介绍QSplat数据结构和渲染算法,并讨论一些权衡和设计决策,以使其适用于大型网格。我们描述系统的渲染性能,并讨论它的预处理成本。最后,我们考虑它与以前用于显示大型网格的算法的关系,并描述用于渲染其他类型大型几何数据集的一些未来扩展。
2 QSplat数据结构和算法
QSplat使用层次结构的边界球体[Rubin 80,Arvo 89]进行可见性剔除,细节层次控制和渲染。树的每个节点都包含球体中心和半径,法线,普通锥体的宽度[Shirman 93]以及可选的颜色。可以从多边形,体素或点云中生成这样的边界球体层次结构,但对于我们的应用程序,我们只需要一种用于从三角形网格生成层次结构的算法。层次结构被进行预处理,然后写入磁盘。
2.1 渲染算法
一旦构建了层次结构,将使用以下算法进行显示:
TraverseHierarchy(node) {
if (node not visible)
skip this branch of the tree
else if (node is a leaf node)
draw a splat
else if (benefit of recursing further is too low)
draw a splat
else
for each child in children(node)
TraverseHierarchy(child)
}
我们现在详细研究这个基本算法的几个阶段。
可见性剔除: 当我们递归边界球体层次时,我们剔除不可见的节点。通过测试每个球体相对视锥体的位面来进行视锥剔除。如果球体位于外部,则它和其子树将被丢弃并且不会被进一步处理。如果球体完全位于平截头体的内部,不会尝试对该节点的子节点进行进一步的视锥体剔除。
我们还将在渲染过程中使用存储在每个节点的法线和法线锥来进行执行背面剔除。如果锥面完全离开观察者,则丢弃该节点及其子树。我们还将检测锥体完全指向观察者的情况,并将其子树标记为不适合进行背面剔除。
确定何时进行递归: QSplat使用启发式算法,递归次数取决于屏幕上的投影大小。也就是说,如果投影到观察面上的球体的面积超过阈值,则对节点进行细分。递归的中值可以调整帧与帧之间的间隔来保持用户选择的帧速率。我们目前使用一个简单的反馈方案,通过前一帧中从实际到预期的渲染时间的比率来调整阈值区域。Funkhouser和Séquin已经展示了一种预测性的LOD控制算法[Funkhouser 93],可以缩短渲染时间的帧间变化。但是,我们没有实现这一点。我们还没有导入任何平滑过渡算法用于做过模型细节层次改变,例如Hoppe渐进网格系统[Hoppe 98]中的地形。鉴于我们为应用程序中经典快速变化和提炼选择了最适度变化方案,我们尚未发现光滑视觉效果的缺失;但是,其他应用程序或许会从平滑过渡中受益。
尽管屏幕空间区域是LOD控制最流行的指标,其他启发式算法[Duchaineau 97,Hoppe 97]已经用于确定递归的深度。在我们系统的框架内,可以在高曲率区域(使用标准锥体宽度)或在屏幕的中央“中心凹”区域中结合围绕边(使用每个节点的法线)进一步制定递归的规则(只使用投影位置)。
上述帧率控制的实现将会在模型的交互操作期间使用。一旦用户停止移动鼠标,我们相继用较小的阈值重绘场景,直到达到一个像素的大小为止。 图1显示了QSplat在几个细化层次上呈现的示例场景。
绘制Splats: 一旦我们已经到达叶节点或者决定停止递归,我们绘制一个代表当前球体的图示[Westover 89]。图示的大小基于当前球体的投影直径,其颜色是根据基于当前每球法线和颜色的光照计算获得的。使用启用Z缓冲来绘制Splats以解决遮挡问题。我们在3.3节讨论每个图示的形状。
2.2 预处理算法
我们的预处理算法从待编码模型的三角形网格的表现开始。尽管可以直接从点云建立QSplat层次结构,但从网格开始,可以轻松计算每个节点的法线。如果我们没有网格,我们将不得不通过将平面拟合到每个点周围小邻域中的顶点来计算法线。从网格开始,还可以将球体大小分配给输入顶点(它们成为我们的边界球体层次结构中的叶节点),以便在渲染过程中不留下任何空洞。为了保证这一点,必须选择尺寸,使得如果两个顶点通过原始网格的边连接,那么放置在这些顶点处的球体的大小足以相交。我们当前的算法使得球体的大小等于接触该顶点的所有三角形的边界球体的最大尺寸。这是一种保守的方法 - 它可能会导致球体太大,但保证不留下任何空隙。
一旦我们分配了叶球大小,我们使用以下算法来构建树的其余部分:
BuildTree(vertices[begin..end]) {
if (begin == end)
return Sphere(vertices[begin])
else
midpoint = PartitionAlongLongestAxis(vertices[begin..end])
leftsubtree = BuildTree(vertices[begin..midpoint])
rightsubtree = BuildTree(vertices[midpoint+1..end])
return BoundingSphere(leftsubtree, rightsubtree)
}
该算法沿着其边界框的最长轴分割顶点集合,递归计算两个子树并找到两个子球体的边界球来构建树。随着树的建立,内部节点上的每个顶点属性(例如法线和颜色)被预设为子树中这些属性的平均值。当递归到达单个顶点时,我们只需创建一个球体,其中心是顶点的位置。由于树的总大小取决于每个节点的分支因子,因此我们组合树中的节点将平均分支因子增加到大约4。这减少了内部节点的数量,从而减少了树的存储需求。如3.1节所述,预处理的最后一步是量化每个节点的所有属性。
3 设计决策和权衡
现在让我们考虑一下在进行QSplat时做出的一些决定,这些决定将使算法适用于大型扫描数据集的可视化应用。我们将描述如何权衡量化文件布局,图示形状以及那些受到快速渲染和紧凑表现额外影响的选择。
3.1 节点布局和量化
图2c中显示了边界层次结构中每个节点的布局。节点包含球体相对于其父体的位置和大小,法线,法线锥体的宽度,可选颜色以及用于表示树结构的几个比特位。我们在3.2节讨论树的结构和文件内节点的布局。
位置和半径:每个球体在边界球体层级中的位置和半径以其父节点为参考系进行编码(使用相对值)。为了节省空间,这些量被量化为13个值。也就是说,一个球体的半径可以在其父部的半径的1/13至13/13范围内,并且球体的中心相对于其父体的中心的偏移量(在X,Y和Z)是父球面的直径的1/ 13的倍数。量化从上到下进行,子球体的位置和大小相对于其父体的量化位置进行编码; 因此,量化误差不会沿着网格传播。为了保证量化过程不会引入任何空洞,量化半径总是四舍五入到最接近的可表示值,以确保量化球体完全包围真实球体。
请注意,并非所有的$13^{4}$的可能的组合(x, y, z)中心偏移和半径比都是有效的,因为许多结果的子球体并不被父球体包住。实际上,只有7621个可能的组合是有效的,这意味着我们可以仅使用13位(使用查找表)对量化的位置和半径进行编码。对于半径为1的父球体,这种编码方案组成的子球体中,(x,y和z)会有0.04平均量化误差,半径会有0.15的平均误差。半径误差之所以大于位置误差,是因为半径首先根据球体位置的量化误差来增加(以确保量化球体包围真实球体),而且总是向上取表示值。当然我们可以通过不要求量化的球体完全包围原始图像来获得较低的半径量化误差。但是,这样做会导致量化后球体不再相交的可能性。这可能会在我们的渲染中产生空洞。
通过增量编码来表示诸如球体位置等几何量的想法,实质上扩展了层次结构中各个层次之间的数量位,这意味着与传统的网格压缩方法不同,它依赖于沿网格边缘的某些路径编码时的顶点位置[Taubin 98]。实际上,这种“分层三角形编码”更接近用于Eck等人的多分辨率分析[Eck 95]中的几何形状的小波表示。我们每个节点13比特位的空间需求比state-of-the-art传统压缩方法更有竞争力。依靠顶点位置的初始量化优势,它们平均每个节点有9-15比特。然而,这并不是一个完全有效的比较,因为传统的几何压缩方法也表示网格连通性(我们不需要表示),并且我们每个节点的13位还包含球体半径。
渲染过程中,每个节点的位置和半径都可以实时解码。因此,我们的数据结构不仅在磁盘上紧凑,而且在渲染过程中需要的内存少于在渲染前必须解压缩数据的方法。
法线: 每个节点的法线量化存储为14位。可表示法线在立方体6个面的每个面上,各对应5252网格上的点,这样可以更均匀的弯曲向样品空间。在渲染过程中使用查找表来解码可表示法线。在实践中只使用5252*6 =16224种不同的法线(导致大约0.01弧度的平均量化误差)在漫反射组成中不产生可见的伪影,但是在低曲率的宽广区域内的镜面反射周围可见一些带状伪影。通过移动到每一条相对于父球体进行增量编码的法线上,可以消除这些伪影,并且实现更好的压缩。当然,这会增加算法内部循环的计算复杂度,这是一种时间-空间的权衡。与节点位置范围不同,法线空间是有界的,因此固定的量化表就足以编码任意场景的正则表达式。因此,此时我们选择了对法线使用固定量化,这只需要在运行时查找单个表。随着处理器速度的增加,我们预计增量量化方案将变得更具吸引力。
颜色: 当前存储的颜色量化为5-6-5共16位。正常情况下,颜色使用增量编码会节省空间,但在运行时会更加昂贵。
法线锥体: 经过一些实验后,我们决定将每个节点的法向锥体的宽度量化为2比特位。四个表示的值对应于锥体,其半角具有正弦1/16,4/16,9/16,和16/16。在典型的数据集上,使用这种量化的正常圆锥体进行背面剔除时丢弃的节点中,超过90%是使用精确的正常圆锥体宽度也会被剔除的节点。请注意,我们在表示法线锥体宽度时总是保守的,所以我们从未丢弃应该显示的几何体。与法线和颜色一样,标准锥体宽度可以相对于父节点处的宽度来表示,但这会降低渲染速度。
3.2 文件布局和指针
边界球体层次的节点以宽度优先的顺序排列(内存和磁盘)。这样做的主要结果是文件的第一部分包含低分辨率的整个网格。因此,我们只需要读取文件的第一部分便足以使用低分辨率来可视化模型; 随着从磁盘读取文件的更多信息,我们将能看到更多细节。我们目前使用操作系统提供的内存映射作为工作集管理的基础,因此当用户查看时,模型的给定部分的高分辨率数据将从磁盘读取。这种渐进式加载对于大型模型的可用性而言有非常重要的意义,因为从磁盘加载整个数据集的时间可能需要几分钟。不过由于数据是根据需要加载的,当用户首次放大模型的某个区域时,渲染性能会降低 – 帧速率控制方法基于反馈导致帧速率出现问题。然而,接触模型相同区域的后续帧会全速渲染。[Funkhouser 92,Funkhouser 96,Aliaga 99]提出了一种推测预取方法来减少这种变动,但是我们目前没有实现这一点。
已经提出了几种无指针方案用于树编码,包括线性八叉树和基于完全树的方法[Samet 90]。但是,这些数据结构对我们的应用来说不合适。线性八叉树和相关想法需要遍历整个树来恢复其结构,这在我们的系统中是不切实际的。基于完整树的数据结构可以用于部分遍历,但是因为我们用来生成树的算法是基于轴对齐的二等分,所以我们不能保证结果树会完整和平衡。此外,修改预处理算法生成完整的树并不是必需的,因为在每个子树中放入相同数量的顶点可能会使分裂平面偏离中心。
尽管我们不能为我们的树使用无指针编码,但我们至少应该尽量减少所需指针的数量。考虑到我们按照广度优先顺序存储树,树中的每个兄弟组(即,单个父球体的子节点)都有一个指针指向这些节点的子节点就足够了。而且,如果这些球体都没有子节点(即它们都是叶节点),那么该指针就不是必需的。使用这种方案,大约总存储成本的8%到10%用于指针,我们认为这些指针足够小,以至于我们没有寻求更复杂的方法来进一步降低指针成本。为了能够遍历树,我们在每个节点上存储两位编码节点的子节点数的位(0,2,3或4个子节点 - 不允许有单个子节点),同时使用一个比特位来指示该节点的左右子节点是否是叶节点。
现在可以将树的总存储需求计算为树中的节点数乘以每个节点的成本,再加上由于指针引起的开销。对于平均分支因子为3.5的树,节点总数将是叶节点数量的1.4倍,从而使整个树的净存储需求大约为9字节*叶节点数,如果不存储颜色则为6字节。
3.3 图示形状
用于表示渲染点样本的内核选择可能会对最终图像的质量产生重大影响。最简单,最快的选项是非抗锯齿OpenGL点,它被视为一个正方形。第二种选择是一个不透明的圆,它可以作为一组小三角形呈现,或者作为在大多数OpenGL实现中成本较低,作为单个纹理映射的多边形。另一种选择模糊点,拥有以高斯或某种近似值进行径向衰弱的透明通道。我们使用的特定近似值是在图示的标准半径中不透明度下降到1/2的样条函数。后两个选项绘制速度较慢,因为它们需要向图形管道发送更多数据。此外,由于混合和Z缓冲之间的相互作用,绘制高斯图示需要特别注意绘制图示的顺序。Levoy和Whited在纯软件的渲染器[Levoy 85]中讨论了这个问题;他们提出了一种基于桶的方法,以确保遮挡和混合均正确发生。在OpenGL中,我们可以使用多通道渲染来实现正确的行为。在第一通道中,通过$z_{0}值$来描述与观察者相距的偏离深度,我们只渲染深度缓冲区。对于第二通道,我们关闭深度偏移并将其叠加渲染到颜色缓冲区中,并且不进行深度更新。这将具有在表面深度范围$z_{0}内将所有图示混合在一起的效果,同时保持正确的遮挡。图3比较了图示内核的这三种选择。由于每个内核的每个图示绘图时间对于每个内核都不相同,因此我们在不同的图示大小和不变的运行时间下进行比较。
关于图示形状另外一个需要决定的选项,图示总为圆形(或OpenGL点的平方)或是总为椭圆形。在后一种情况下,每个节点处的法线用于确定椭圆的偏心率和方向。当法线指向观察者时,图示将是圆形的。否则,每个椭圆的短轴将沿着法线的投影指向观察平面,并且短轴与长轴的比率将等于n v,其中n是图示法线,v是指向观察者的向量。与圆形图示相比,这提高了轮廓边缘的质量,减少了噪音和增厚。我们在图4中比较了圆形和椭圆形图示的使用。
因为我们构造了我们的边界球体层次结构,使得沿着连续表面放置的球体永远不会留下空洞,所以我们可以保证正方形和圆形内核总是会可以无空洞再构造。我们对高斯内核的近似也保证在起始于连续曲面的区域产生完全不透明度。当我们移动到椭圆内核时,我们不能再保证无空洞的再构造,因为法线不需要沿着表面连续。实际上,当使用椭圆形内核时,我们偶尔会看到空洞,特别是在轮廓边缘附近。我们发现,限制椭圆的最大缩短率(例如,将主轴与次轴的最大比率限制为10)实际上填充了所有这些空洞。
3.4 基于点的系统的结果
点渲染对于具有统一尺寸几何细节的物体,以及在不需要以比样本间距更高的分辨率观察模型的应用中,对于具有均匀尺寸几何细节的物体最为有效。如果模型具有大的,平坦的或巧妙的曲面,那么多边形模型可以更紧凑和更快地绘制。同样,如果需要放大以使样本间距比像素大小更大,多边形可提供更高的视觉质量,特别是在尖锐的边缘和角落附近。图5显示了基于点和多边形的渲染之间的比较。
QSplat的开发旨在将扫描模型可视化,其中包含大量精细细节,并且接近扫描分辨率。我们使用体积范围图像处理(VRIP)系统[Curless 96]将原始扫描合并到我们的最终模型中,并使用行进立方体算法[Cline 88]提取多边形网格。由于后者生成的样本具有均匀的空间,所以点渲染非常适合我们的应用领域。对于具有较大平滑区域的场景,我们预计相对于基于多边形的系统,QSplat效果会较差。但是,如果大型多边形被切块,那么所得模型的视觉质量仍然很好,就像在REYES架构中一样[Cook 87]。对于包含高频细节和大平坦区域的应用,混合点/多边形方案可能是合适的选择。
4 性能
如第3节所述,交互性的目标决定了我们系统的许多设计决策。除此之外,我们还通过多种方式优化了实施,以增加可视化模型的大小。
4.1 渲染性能
我们系统中的大部分渲染时间都花费在遍历层次结构的内部循环中,计算每个节点的位置和半径,执行可见性剔除,并决定是绘制点还是进一步递归。这个内部循环被调整来消除昂贵的操作,特别是在树的较低级别时。例如,我们不在树的低层执行精确的透视分割,当节点的屏幕空间大小达到几个像素时切换到近似值。因此,一旦从磁盘读取数据,平均而言,我们的算法可以在SGI Onyx2上每秒渲染1.5至2.5百万点。确切的速率取决于缓存效果(例如,我们发现当工作在L2高速缓存环境下,速度会有提升)以及树中哪些级别的数据被剔除。
我们的显示速率可以与Hoppe报道的每秒48万个多边形(在相同的硬件上)进行比较,因为他为ROAM系统实现了渐进网格[Hoppe 98]或每秒18万个多边形[Duchaineau 97]。对于我们的应用,我们通常使用5-10赫兹的帧速率,这意味着我们在交互式渲染过程中每帧画出200到30万点。请注意,与上述两个系统不同,QSplat没有明确使用帧到帧的一致性,例如缓存可能可见的初始化列表。图6总结了QSplat的渲染性能。
我们算法的简单性使其非常适合在低端机器上实施。作为一个极端的例子,我们在没有3D图形硬件(366 MHz Intel Pentium II处理器,128 MB内存)的笔记本电脑上实现了QSplat。由于渲染是用软件来执行的,系统是有限制的。对于500x500的典型窗口大小和5 Hz的帧速率,实现可以每秒钟运行250到400千点,每秒填充速率为4000万像素,并且通常每帧可以绘制50到70个splats 。在这个情况下,这个实现仍然很好用。尽管目前大多数桌面系统都具有3D图形硬件,但对于便携式和手持式系统以及数字电视机顶盒等应用来说,情况并非如此。
4.2 预处理性能
虽然预处理时间并不像渲染时间那么重要,但对于非常大的网格的实际可视化仍然很重要。Hoppe报告10个小时作为20万个顶点渐进网格的预处理时间[Hoppe 97]。Luebke和Erikson报告121秒作为实施分层动态简化的281,000个版本的预处理时间[Luebke 97]。相比之下,我们对20万顶点的预处理时间在5秒以内(在同一硬件上)。图6给出了本文数字中所用模型的预处理时间和空间需求的一些统计数据。
我们可以比较预处理时间的另一类算法是用于网格简化和抽取的算法。 尽管这些算法与QSplat的目标不同,但它们通常也用于生成多分辨率表示或简化网格以进行显示。 Lindstrom和Turk发表了几个最近的网格简化方法的比较[Lindstrom 98]。 他们报告30秒到45分钟之间的时间,以简化35000个顶点的兔子网格。 文件没有考虑的一种方法是基于体素的简化Rossignac和Borrel [Rossignac 93],它在与Lindstrom和Turk使用的硬件相同的硬件上花费了一秒钟时间。 我们对这个网格的预处理时间是0.6秒。 因此,我们的算法比大多数当前网格抽取算法快得多,并且与Rossignac和Borrel方法相比具有竞争性。
5 前期工作
以前用于表示和显示大型模型的方法可以分为点渲染,可见性剔除,细节层级控制和几何压缩。
5.1 点渲染
传统上计算机图形系统使用三角形作为渲染原语。为了减少包含大量几何图形场景的三角形的设置和光栅化成本,已经提出了许多更简单的基元。使用点作为连续曲面的显示基元由Levoy和Whitted [Levoy 85]引入,最近又由Grossman和Dally [Grossman 98]重新研究。点渲染已被纳入到商业产品中 - 例如,Animatek鱼子酱系统在视频游戏[Animatek]中将点渲染用于动画角色。粒子也被用于更特殊的环境中,如渲染火焰,烟雾和树木[Csuri 79,Reeves 83,Max 95]。
数据结构来实现空间空间区域的压缩,Laur和Hanrahan已经研究了使用八分音符表示的音量的等级划分[Laur 91]。 尽管splatting最适合在投影体素大小在像素大小的情况下使用,但也已经检验过在其他体系中的有效性。 Cline等人提出的微分立方体算法适用于体素大于像素的情况。对于小于像素的体素,Swan等人[Cline 88]已经提出了正确生成反锯齿结果的算法[Swan 97]。
5.2 可见性剔除
大量计算机图形系统中出现了诸如QSplat所使用的视锥和背面剔除算法。基于数据结构(如oc树)的层次平截体剔除一直是大多数渲染大型场景系统的标准功能[Samet 90]。基元的背面剔除通常在硬件中实现,Kumar和Manocha提出了基于法线圆锥的分层背面剔除算法[Kumar 96]。
另一类可见性剔除算法包括用于遮挡剔除的方法。Greene等人描述一种通用算法,用于丢弃被更紧密的几何体使用分层Z缓冲区阻塞的基元[Greene 93]。如果场景高度结构化,也可以使用其他更专用的遮挡算法。例如,建筑飞行系统通常使用单元和门户的概念来剔除整个不可见的房间[Teller 91]。 QSplat目前不执行任何种类的遮挡剔除,它将为查看我们正在考虑的扫描模型提供最小的益处。 然而,遮挡剔除对于更复杂深度的场景是一个有用的补充。
5.3 细节控制的级别
在低倍率下渲染大型数据集通常会导致原始像素小于输出设备像素。为了尽量减少这些情况下的渲染时间,最好切换到更低分辨率的数据集,并使用更接近输出显示分辨率的基元。在LOD算法中,可以将那些以离散细节层次存储整个对象的算法与执行更细粒度LOD控制的方法区分开来。后一类中的算法可以连续控制图元的数量,最大限度地减少“弹出”伪影,并且通常会改变整个场景中的细节水平,以补偿透视投影的变化放大率。
多分辨率分析将一个对象表示为“基本网格”,并将一系列校正值存储为小波系数[Eck 95]。Certain等人已经实现了基于多分辨率网格的实时查看器,该网格可以选择任意数量的要使用的小波系数,因此可以绘制任意数量的多边形网格[Certain 96]。他们的观察对象还包括诸如逐行传输和几何和颜色的小波系数分离集等功能。
渐进网格使用基础网格和一系列顶点拆分操作[Hoppe 96]。渐进网格已被纳入实时查看器中,该查看器对数百万个多边形场景的实时飞行进行视点相关改进[Hoppe 97,Hoppe 98]。观察者不仅可以选择任意数量的多边形进行绘制,还可以将对象的不同部分细化为不同的分辨率。其他最近允许在整个场景中改变水平的系统包括ROAM 地形渲染系统[Duchaineau 97]和LDI树[Chang 99]。QSplat中LOD控制的实现与这些系统具有相同的目标,允许根据投影的屏幕尺寸在整个场景中细节级别平滑地变化。
5.4 几何压缩
几何压缩的目标是减少大网格的存储和内存要求以及传输成本。Deering提出了一个压缩网格连通性,顶点位置,颜色和法线的系统,后来在硬件中实现[Deering 95]。最近的研究,如Taubin和Rossignac 的拓扑外科方案,已经集中在降低表示网格连通性和改善顶点位置压缩的成本[Taubin 98]。Pajarola和Rossignac对渐进网格进行了压缩,产生了一种将细节层次控制和渐进式细化与紧凑表示相结合的方案[Pajarola 99]。然而,他们的算法比QSplat具有更高的预处理和解码成本。
6 结论和未来工作
QSplat系统演示了大型模型的实时渐进渲染。QSplat的体系结构与最先进的逐行显示算法的渲染速度相匹配,预处理时间可与当前最快的网格化抽取器相媲美,实现了接近当前几何压缩技术的压缩比。
由于QSplat查看器非常轻便,可以在低成本硬件上实现,因此我们认为它有可能允许在以前不实用的应用程序中使用3D渲染,例如在博物馆中内置自助服务终端。1999年5月6日,我们在佛罗伦萨Medici教堂的一台计算机上安装了QSplat,显示我们部分完成的Dawn雕像计算机模型,并让游客玩耍(见图7)。
先前介绍的几种技术可以纳入当前的QSplat框架中,以使其更加节省时间和空间:
霍夫曼编码[Huffman 52]或其他无损压缩方案可用于使当前表示更加紧凑。这对于通过低带宽通信链路进行离线存储或传输非常有用,但是需要在渲染之前对模型进行解压缩。
对于渲染速度比紧密表示更重要的情况,可以通过消除球体位置和大小的压缩和增量编码(如3.1节所述)来加速算法,并将这些数量简单地存储为彩车。此外,正常的口罩和能见度掩模(如Grossman和Dally使用的口罩和能见度掩模)可以在有大量大面积封闭的情况下加速渲染[Zhang 97,Grossman 98]。速度的进一步提高可以通过并行渲染算法来实现,将树的一部分分配给不同的处理器。虽然我们在本文中报告了单处理器的结果,但我们已经可以通过将网格分解为多个tile来并行化我们的预处理算法。
进一步的分析对于理解QSplat的时间一致性和缓存行为是必要的。对地形渲染和建筑漫游系统[Funkhouser 96]中的帧速率控制和工作集管理技术进行了大量的系统研究,这些算法将提高用户与QSplat交互的平滑度。以下是帕特COM的图形中结合了不同种类的算法QSplat方法未来研究的潜在领域:
QSplat使用的边界球体层次结构非常适合作为光线追踪的加速度数据结构。潜在地,这可以用于高质量渲染,并具有以QSplat格式存储的模型的高级渲染效果。
实例化将很容易融入我们的基于树的数据结构和渲染算法,大大减少了许多程序化定义场景的内存需求。这可以被认为是一种依赖视图的精灵的新形式,允许在场景中的多个位置有效地包含几何图形。
除法线和颜色以外的项目可以存储在每个节点。透明度(alpha),BRDF和BTDF将是明显的候选对象,这会增加QSplat可以表现的视觉复杂度,使其具有与现代体积渲染器相似的功能[Kajiya 89]。更复杂的对象,如光场,依赖视图的纹理,空间变化的BRDF以及分层深度图像也可能存储在每个节点上,从而创建点渲染系统和当代基于图像的渲染器的混合。
1 条评论
四月清和雨乍晴,南山当户转分明。
更无柳絮因风起,惟有葵花向日倾。