视点相关的顺序点模型树
View Dependent Sequential Point Trees
-
摘要: 点模型以点的方式对模型进行建模，放弃了模型中拓扑关系的显式表达。与显式表达的面模型相比，点模型更方便处理大规模复杂模型。由于现实中所处理的模型越来越庞大，点模型在近年得到了更多的重视。一般地，点模型以层次化树结构的方式对模型进行由粗至细的多分辨率表示，以方便多分辨率的绘制。 由于点模型中点的数量一般都很庞大，如何快速找到合适的点进行绘制，和如何利用硬件来加速绘制，是提高点模型绘制效率的重要途径，国际上关于这方面的讨论很多。其中，顺序点模型树是目前所知最快的点绘制方法。根据各个点拟合模型时的几何误差，它将树结构中各个层次的点进行单调的顺序排列。这样，它在绘制时可很快确定满足绘制的几何误差要求的点的片段，并且可将该片段中的点顺序地送入 GPU 中进行绘制，以高效发挥 GPU 的作用，达到很高的绘制速度。 但是，顺序点模型树在可见性计算方面很弱，它要逐个点地考察它们是否可见。由于大规模复杂模型中，每次成象时的不可见部分往往占了大部分区域，对这些不可见部分的点数据进行处理，无疑会浪费大量时间。为此，我们提出视点相关的顺序点模型树，将层次化的树结构嵌入点的顺序化线形序列中，并生成两种索引以方便对点数据进行由近及远和由粗至细的处理。具体地说，从根结点开始，我们将点模型树按照广度优先的方式一层结点一层结点地顺序排列；在排列一层结点时，我们引入迭代的 Z 型序列来安排这些结点在序列中的位置，使得空间上邻近的点在序列中的位置也是靠近的；而在每个非叶子结点，还记录它的儿子结点在序列中所处的片段位置。这样，就将层次化的树结构嵌入了点的顺序化线形序列中。两种索引记录两种信息。一是将空间划分成许多区域，为每个区域记录：当视点位于该区域时，各层结点中离该区域最近的结点在队列中的位置。这是为了由近及远地处理点数据。二是考察各个层次结点的几何误差情况，并为每种几何误差记录序列中最先满足该误差要求的层次片段，以便成象时能很快剔除太粗糙的点数据，这对于模型的近距离成象是非常有用的。 这样，绘制时可尽早发现不可见部分的点并将它们成群地隐含剔除，使得送入 GPU 进行绘制的点的数量大大降低，以进一步提高绘制速度。虽然新方法在嵌入点的树结构时会增加一些空间开销，但增加的量不大，并且能很好提高绘制速度。实验表明，新方法能将顺序点模型树的绘制效率提高 20%~64.6% ，并且越近观察模型或模型中的遮挡关系越复杂时，新方法的加速比更高。Abstract: Sequential point trees provide the state-of-the-art technique for rendering point models, by re-arranging hierarchical points sequentially according to geometric errors running on GPU for fast rendering. This paper presents a view dependent method to augment sequential point trees by embedding the hierarchical tree structures inthe sequential list of hierarchical points. By the method, two kinds of indices are constructed to facilitate the points rendering in an order mostly from near to far and from coarse to fine. As a result, invisible points can be culled view-dependently in high efficiency for hardware acceleration, and at the same time, the advantage of sequential point trees could be still fully taken. Therefore, the new method can run much faster than the conventional sequential point trees, and the acceleration can be highly promoted particularly when the objects possess complex occlusion relationship and viewed closely because invisible points would be in a high percentage of the points at finer levels.
下载: