QSplat基于多分辨率处理大规模网格的点绘制系统

1、qsplat：基于多分辨率处理大规模网格的点绘制系统（部 分）来源：斯坦福大学计算机图形实验室作者：szymon rusinkiewiczmarc levoy卜道成译摘要：随着3d扫描技术的发展，在实践中冇着上亿数量级的网格的多边形都能被 创造出来。传统的网格的显示，简化，渐进传输的算法已经不适合如此大规模的 数据集。我们描述的这个系统将表示并逐步妞示这些网格，它是基于边界球的多 分辨率层次和基于点绘制系统的结合。一个专门的数据结构被用来做视域剔除， 背面剔除，多细节层次选择以及绘制。这种表示方法不仅紧凑，而且能被快速的 计算出来，这些使得它适合那些大规模的数据集。我们的执行程序，服务于大型

2、的3d数字项a。不管物体的复杂程度还是摄影位置，我们的程序都能迅速启动, 维护用户设置的交互式帧频，在模型移动中也能产生合理的图象质量并在机器空 转吋逐步求精达到一个高的最终的图象质量。我们已经论证了这个系统是可以扫 描乜含上亿数量级采样点的模型的。范畴和课题描述：1.3.3 computer graphics:降|片/阁象的生成显示算法；puter graphics:计算几何和物体建模曲线、而、体以及物体的表示方法；puter graphics:方法论和技巧图形的数据结构和数据类型。关键字：绘制系统，空间数据结构，多细节层次算法，压缩算法1绪论在绘制过程屮，计算机图形学方而一种新的意义重大的

3、趋势已经朝使用样本 来代表实际物体开始转变。这种趋势的一个实例已经成为生成实物三维样木模型 的3d扫描系统的一个新增应用。但是对于3d扫描器來说，处理大量cj身生成 的数据仍然是一个m题。在过去的几年研究里，3d扫描系统在硬件和软件组件 方而的改进在实践屮增加了系统在扫描数量级达到几亿网格的样本的可行性。目前的工作站还不能实时地显示这样数量级的网格，并且传统的网格的简化 和渐进的显示算法在运行的时间和空间需求上使这些为了扫描包含超过几百万 规模的网格样木的途径变得不切实际。此外，很多这样的技术都把精力集屮在个 别边和顶点的定位上，这样在每个顶点上要消耗相当大的精力。尽管如此，由于 噪声的原因，

4、仍然导致经过扫描的含省大量顶点和顶点位置的数据常常不精确。 这就暗示了一种把个别点看成相对不重耍的点和因此在每个原始点上花少点的 精力这两者之间可供选择的方法。口前研究这个范例的也括krishnamurthy和 levoy 的 spline-fitting 系统，curless 和 levoy 的 range image merging 系统以及丫emez和schmitt的基于octree particles的绘制系统。这些算法 都不能使得数据范围达到精确，并且事实上不能保护任何一个样本的原始网格的 3d位置。随着算法对每个原始点的低消耗这一趋势，我们己经开发出一种新的为了交 互显示大规模网格

5、算法。这个方法我们称之为：qsplat，并且在大型3d数字 化项目课题中已经设计出來。因为它使用了简单的绘制算法，这种算法基于穿越 边界球的层次结构。它在这个项屮适合浏览生成的模型，而这些模型都包含1 亿到10亿的采样点。除此之外，qsplat不维护输入网格的连通性（这些连通 性的数据在被扫描的数据中，他木身在对解决不连通性的深度食用，其他儿乎没 宥什么意义），取而代之的是依赖基于点的表示法和splat绘制法。结果，我们 的系统介:预处理和绘制的消耗方面比可比较的基于多边形的系统要低。qsplat 们动迅速，可调整多细节层次去维护交互的帧频，以及在内存和磁盘使用方而有 紧凑的表示方法。在这篇论

6、文中，我们呈现了 qsplat的数据结构和绘制算法以及讨论了关于 使它能在处理大规模网格上有实际使用价值方面的设计决定和一些权衡。我们描 述了系统的绘制执行情况，并且讨论了它的预处理价值。最后，我们认为它关系 到丫先前显示大规模网格的算法，同时我们也描述y些将来对于绘制其他种类 大规模几何数据集的扩展。2 qsplat的数据结构和算法qsplat用边界球的层次结构作为可见性剔除技术，多细v层次的控制以及 绘制。树中每个节点都钮含球心位置和半径，法矢和法锥面的宽度，以及颜色（可 选）。尽管对我们的程序来说，我们仅需要-种算法从三角网格中生成这种边界 球的足次结构，似是qsplat还能从多边形、体

7、素或者点云模型生成这样的m次 结构。这种层次结构作为一种预处理被构造，并被写入到磁盘上。2.1绘制算法这种层次结构一旦被构造，下血的算法就可以用來显示:traversehierarchy(node)if (node not visible) skip this branch of the treeelse if （node is a leaf node） draw a splatelse if （benefit of recursing further is too low） draw a splatelsefor each child in children（node）traversehie

8、rarchy（child）下面我们将对这个基木的算法的儿种情况做详尽的讨论：可见性剔除技术：当我们在边界球的层次上做递归时，我们剔除那些不口j*见的节点。视域剔除是通过测试每个球体对着视域的位面完成的。如果球位于 平截头体（视域平头四棱锥）的外面，那么它和它了树的节点都会被丢弃或者不 做进一步的处理。如果球完全位于平截头体（视域平尖四棱锥）的里血，这种情 况下就要注意了，不用对节点的孩子节点试图做进一步的视域剔除。我们在绘制的吋候通过使用法矢和法锥面也可进行背面剔除。如果锥面完全 竹离视点，那么这些节点和它的了树节点都会被丢弃。我们也不难发现锥面完全 指向视点，然后把组成这些血的t点的孩子t点

9、不作为背血剔除的候选t点这一 事实。决定什么时候去做递归：启发式的使用qsplat去决定递归到什么程度是基于屏幕上的投影尺寸。也就是说，如果球投影到观察血上的区域超过一个极 限时，就得对这个节点做细分。递归的中止为了维护用广选择的帧频，从而做从 一帧到另一帧地调整。我们0前使用的是简单的反馈方案，这种方案通过实际的 比率在先前帧的基础上渴望获得绘制时间来调整极限ix域。funkhouser和sequin在多细v层次控制理论中己经址明了例似这样带有预测性的算法，这种算法使得帧到帧的绘制时间的变化变小。但是我们没宥做到那种的程度，我们也没宥象hoppe的渐进网格系统中geomorphs算法那样加入

10、任何做平滑转化的算法作为从一个多细节层次到另一个多细节层次的模型变化的片段。假如 我们的程序在我们求精时对外观做适当改变和对典型观察点上做快速的变化的 时，我们将不能发现缺乏滤波的真实的重耍意义。但是其他应用程序，可能从这 样的平滑转变中受益。尽管屏幕区域对于多细节层次控制来说是最普遍的方案，但是其他具有泊发 性的方案已经被提出用来决定递归的程度。在我们的系统框架里，任何人都能整 合出规则來对卜*面的情况做进一步的递归：轮廓线周围（通过使用每个节点的法 矢），在高曲率的区域里（通过使用法锥面的宽度），屏中央問型区域（这里只 能通过映射位）。上述帧频控制的执行在对模型进行交互操作期间被应用。一旦

11、用户停止移动 鼠标，我们就会通过使极限连续变小，一直小到和显示器一个像素点一样大小的吋候来重绘场景。图一显示的一个样木就是通过qsplat在几个不同精练级别上 绘制。15-象素 cuto 130,712 点 132 ms10-象素 cuto 259,975 点 215 ms5-象素 cuto 1，017，149 点 722 ms1-象素 cuto 14,835,967 点 8308 ms绘制splats: 旦延伸到了叶子节点或者决定中止递归，我们就绘制出一 个splat去表示当前的球。splat的大小是基于当前球的投影的直径，它的颜色 是基于当前每个球的法矢和颜色而从照明角度考虑获得的。spl

12、ats的绘制是通 过激活分解遮挡的z缓冲算法。我们将在3.3节中讨论每一个splat的形状。2.2预处理算法我们的预处理算法是从用三角网格来表示被编码的模型开始的(不面的网 格一般都指的是三角网格)。尽管每个人都能直接从点云模型建立一个qsplat的层次结构，但是直接从网格入手使计算每个节点的法矢变得容易。如果我们不 使用网格的话，我们将不得不通过找每一个点周围小领域范围里的顶点组成的最 小二乘而去计算法矢。从网格入手也使分配的球的大小到相应的输入顶点上(这 些顶点在我们的边界球层次结构中可以变成叶节点)，这样在绘制过程中使得点 与点之间没有空洞。为了保证上述情形，如果每两个顶点由原始网格的一

13、条边连 接，则球的大小必须被选得足够大，使得每两个球在顶点的位置上能够接触到。 我们目前的算法这是一个保守的算法它导致了球过大，但是保证了不会留下 任何空洞。一旦分配了叶球尺寸，我们就用下面的算法去建立剩下的树：buildtree(verticesbegin.end)if (begin = end)return sphere(verticesbegin)elsemidpoint =partitionalonglongestaxis(verticesbegin.end)leftsubtree = buildtree(verticesbegin.midpoint) rightsubtree = b

14、uildtree(verticesmidpoint+1 .end) return boundingsphere(leftsubtree, rightsubtree)算法通过沿着顶点的边界盒子的最长轴对顶点集的分离、两个子树的递归地 计算以及两个子球的边界球的查找建立了剩下的树。当树被建立起來的吋，在内 部节点上的每个顶点的展性(如：法矢和颜色等)被设置成这些屈性在子树屮的 平均值。在递归达到某一个顶点时，我们简单的去创建一个球，这个球的球心就 在这个顶点的位置上。因为整个树的大小依赖每一个节点的分支因素，我们把这 些节点都结合到树中去，使得树的平均分支大约有4个。这样将减少内部节点 的数目，从

15、而减少了树的存储景。预处理的最后一步就象3.1节描述的那样去 量子化每个节点的属性。3设计决定和权衡现在让我们来考虑一些实施qsplat执行程序时做出的决定，使这些决定适 合我们程序的可视化大型数据集扫描。我们描述了如何在量化、存储形式和描述 splat形状吋权衡。splatting的选择是受我们快速绘制和压缩表示法的影响。 3.1节点设计和量化每个节点在边界球层次结构下的输出显示在图2c中。一个节点包含相对于 它父节点的位置和球的尺寸、法矢、法锥ifij的宽度、颜色（可选）、用来存储表 示树的数据结构的空问（比特表示）。我们在3.2节中讨论树的数据结构和存 储节点的设计。节点设计:13 bi

16、cs3 bio)4 biu2 bic16 bid阁二：qsplat文件和节点的设计。（a）树的存储方式是宽度优先（顺序由红线表示）。 （b）父甘点到孩子喈点的连接是通过一个从一组父货点到第一个孩子节点的指针建立。如 果所奋的父节点的兄弟节点都是叶子节点那么这些指针都不出现。所奋指针都是32位的（c）一个量化丫的节点占裾48个比特（不带颜色的只要32个比特）球心位置和半径：每个球的球心位置和半径在边界球m次结构.卜.相对于它们 的父节点被编码。为了节约空间，这些度量的值定在了 13比特。也就是说，球 的半径数值范围和对与它父节点是1/13到13/13,球心和对于它父节点（每 一个x, 丫，z）的

17、屮心的偏移量是它父节点直径的1/13的倍数。量化自顶向下 进行，如此孩了节点球的位置和范围相对其父节点的量化的位置而被输入；因 而，量化错误不向网格传播。为了保证量化过程不引起任何的空洞，量化的半径 总是收敛于代表最近点的值以保证量化球非常接近真实球。需要注意的是不是所有的134可能组合的中心偏移量和半径比是有效的， 因为许多结果孩了节点的结果是不依附它父节点的。事实上，只有7621个可能 的组合是宥效的，这就意味着我们对球心位置和半径所使用的空间只能是13比 特。假设父球的半径是1的话，这个编码的方案给出了对于孩子球的x、y、z 的一个平均量化误差是0.04,对于孩子球半径而言有平均0.15

18、的误差。半径 误差远人于位置误差的原因是半径被球位置的暈化误差首次增加（为了保证景化 球能够接近实际球），于是半径总是收敛于代表最近点的值。我们只要不坚持量 化球不完全接近原始球在半径方面就能够获得比较低的量化误差。但是要是这样 的话，就会引起球不会向量化后那样紧密接触。这样做在绘制的时候会制造出空 洞来通过渐进式的编码來表示像球位置这样的几何量，因此实质上在m次结构的 层次上按比特输出这些几何量。这种方案在m格压缩方面是违背传统方案的。传 统方案依赖对于沿着一些路径和沿着网格边的顶点位置的不同的编码。实际上这 种辰次三角编码和eck的多分辨率分析中小波表示儿何体比较接近。我们每个 节点只需耍13比特空间的方案比stateof-the-art几何压缩方法更有竞争力，而后者是依靠最初量化的顶点位置使得每天顶点平均占用9-15个比特。然 而这不是完全冇效的比较，凶为传统几何压缩方案同样也表示出了网格的连通性 （这个方案我们已经抛弃），而且13比特存储一个节点还乜括球的半径。每个节点的位置和半径在绘制的时候被飞快得解码。由于这个原w，数裾结 构不但在磁盘上表现得紧凑，而且在绘制的时候比在绘制前解压数据的方案需要 更少的闪存空间。法矢：每个节点的法矢存储时