基于Voronoi图的快速可见性计算

摘要

在虚拟场景漫游时,观察者走到每一点都需要尽可能快得确定哪些对象是可见的,因此设计合适的可见性计算方法不仅能实现快速绘制,还能节省存储空间和内存空间。二维情况下,就是确定观察者在多边形内任一点,在一定视觉范围内能看见哪些边以及边上的哪些部分。
　　 本文研究背景是山东大学虚拟考古博物馆漫游系统,该系统采用Voronoi图作为统一的数据结构,展厅的设计、路径规划等都使用该结构。本文主要基于该数据结构研究和设计了快速可见性计算方法。
　　 本文算法共分为潜在可见集计算和可见性实时计算两个阶段。算法的核心部分为潜在可见集计算阶段,主要是利用采样点和点的可见性计算方法获得观察区域的潜在可见性集合。在潜在可见集计算阶段中,首先生成虚拟博物馆平面结构图的Voronoi剖分,接着细分复杂的Voronoi区域,获得更加合适的观察单元,然后对每个观察单元的边界边进行自适应地点采样,计算每个采样点处的精确可见性集合,并由这些点的可见性集合合并为该观察单元的潜在可见性集合(PVS)。在可见性实时计算阶段中,首先获得视点所在的观察单元,然后使用该观察单元的PVS直接计算该视点的可见边,以此实现三维室内场景的实时漫游。当视点连续移动时,根据Voronoi图的邻近性可以快速确定新的观察单元。
　　 本文算法的工作与贡献主要是提出了一种基于Voronoi图的可见性计算方法,该方法利用点的可见性算法计算区域可见信息,给出了启发式的自适应采样方法和各点处的可见性集合合并策略,以获得更加紧凑的PVS。该方法与虚拟博物馆漫游系统中的展厅布展、路径规划等操作共同使用统一的数据结构,而没有引进额外的数据结构,极大的节省了本系统的内存消耗。
　　 本文算法利用了采样可见性计算的思想,并不保证PVS中包含所有的可见物体。但是通过细分视点空间和对观察单元边界边的自适应点采样,尽可能使可见物体都包含在PVS中。

目录

文摘

英文文摘

TABLE OF CONTENTS

第一章 绪论

1.1 研究背景及意义

1.2 本文工作

1.3 本文缀织方法

第二章 相关知识

2.1 Voronoi图相关知识

2.2 基于Voronoi图的虚拟博物馆场景表示模型

2.3 本章小结

第三章 潜在可见集计算

3.1 概述

3.2 视点空间细分

3.3 区域可见集计算

3.4 PVS压缩存储

3.5 本章小结

第四章 可见性实时计算

4.1 获得观察单元

4.2 计算实时可见性

4.3 算法分析

4.3.1 观察单元和PVS

4.3.2 算法复杂性

4.4 本章小结

第五章 总结和展望

参考文献

致谢

攻读学位期间发表的学术论文目录

攻读学位期间参与的科研项目

学位论文评阅及答辩情况表