采用八叉树和OSG分页结点的海量点云三维可视化

针对现有海量点云可视化方法存在索引构建时间长、内存占用大等问题，研究一种八叉树索引结合OSG分页结点的快速可视化方法，可在占用较小内存的基础上快速建立点云索引并实时调度。采用八叉树索引结构对海量点云进行数据组织，建立各层级的八叉树结点并以文件映射的方式分块保存，对结点文件重组织转换为支持OSG渲染引擎的多分辨率点云数据。采用基于OSG分页结点的实时调度技术，对海量点云进行高质量可视化。与目前两款主流的点云数据处理商业软件进行实验对比分析，结果表明所提方法具有索引建立速度快、内存占用小等优点，同时可视化交互更加流畅，适用于各种配置计算机下海量点云数据的调度管理与实时可视化。     

一种基于自然数线性八叉树的优化构造算法

本文提出了一种基于自然数线性八叉树的优化构造算法。该算法以活动结点表为中间辅助结构，在图像输入过程中直接生成基于Ｎ码的八叉树叶结点．与常规构造算法相比，新提出的优化构造算法省去了Ｎ码的计算及合并过程，从而具有较高的时空效率．     

基于块段模型的三维GIS混合数据结构模型研究*

为了有效地表示三维GIS空间实体,在地质块段模型的基础上,提出了基于八叉树和四面体格网的混合数据结构模型(block octree tetrahedron,BOT模型).采用BOT模型生成算法对块段模型进行重新分割,八叉树作整体描述,四面体格网作局部精确描述,并以不同的灰度值表示不同的单元块属性.同时,为节省存储空间,提出了线性BOT编码技术.实验结果表明,BOT模型充分发挥了八叉树和四面体格网的优点,可以在不增加存储空间的前提下实现对三维目标更高效、更精确的表达.     

视点相关的真实感三维风景区模拟研究与实现*

提出采用八叉树组织真实山体数据,根据视点距离采用不同的细节层次LOD表示山体各部分,并结合视觉剪裁和帧间相关性进一步减少绘制的山体,达到加速三维地形的绘制和漫游的目的。使用混合纹理映射、阴影渲染技术,并加入山谷中的水面模拟,生成具有真实感的大规模三维风景场景。实验结果表明该方法有效地减少了算法复杂度,易实现碰撞检测,大大提高了绘制效率,在PC机上能实时地生成高分辨率、具有真实感的场景,完全满足VR交互要求。     

Path planning in complex 3D environments using a probabilistic roadmap method

This paper presents a 3D path planning algorithm for an unmanned aerial vehicle （UAV） in complex environments. In this algorithm, the environments are divided into voxels by octree algorithm. In order to satisfy the safety requirement of the UAV, free space is represented by free voxels, which have enough space margin for the UAV to pass through. A bounding box array is created in the whole 3D space to evaluate the free voxel connectivity. The probabilistic roadmap method （PRM） is improved by random sampling in the bounding box array to ensure a more efficient distribution of roadmap nodes in 3D space. According to the connectivity evaluation, the roadmap is used to plan a feasible path by using A＊ algorithm. Experimental results indicate that the proposed algorithm is valid in complex 3D environments.     

八叉树搜索算法在计算机辅助手术中的应用

讨论基于八叉树的空间搜索与求交算法,包括基于八叉树的单元格分配及求交运算2个步骤。该算法可有效应用于计算机辅助手术,实现解剖标志点的空间定位、距离测量、骨厚测量、三维模型间的干涉与距离检测等。其运算效率较高,具有良好的通用性和扩展性,适用于各类计算机辅助手术规划与手术导航软件。     

Surface mesh regeneration considering curvatures

This work describes an automatic algorithm for unstructured mesh regeneration on arbitrarily shaped three-dimensional surfaces. The arbitrary surface may be: a triangulated mesh, a set of points, or an analytical surface (such as a collection of NURBS patches). To be generic, the algorithm works directly in Cartesian coordinates, as opposed to generating the mesh in parametric space, which might not be available in all the cases. In addition, the algorithm requires the implementation of three generic functions that abstractly represent the supporting surface. The first, given a point location, returns the desired characteristic size of a triangular element at this position. The second method, given the current edge in the boundary-contraction algorithm, locates the ideal apex point that forms a triangle with this edge. And the third method, given a point in space and a projection direction, returns the closest point on the geometrical supporting surface. This work also describes the implementation of these three methods to re-mesh an existing triangulated mesh that might present regions of high curvature. In this implementation, the only information about the surface geometry is a set of triangles. In order to test the efficiency of the proposed algorithm of surface mesh generation and implementation of the three abstract methods, results of performance and quality of generated triangular element examples are presented.     

基于自适应延迟切割的三角网格布尔运算优化

规则化的布尔运算被广泛应用在三维建模系统中.近年来,随着图形硬件的发展,基于三角网格的规则化布尔算法由于输出结果能直接被图形硬件处理,表现出了明显的优势.但是传统的算法由于采用CSG树局部评估策略,使得面片在相交测试中反复被切割,并且由于面片分类在切割后的模型之间直接进行,导致算法无法在保证鲁棒性的同时实现高性能.为了避免这些问题,本文呈现了一种CSG树全局评估算法来统一执行单次和连续布尔运算.算法由两部分组成：自适应的延迟切割和全局化面片分类.在自适应的延迟切割阶段,算法通过仔细处理多个三角面片相交导致的各种情况使得延迟切割被扩展到整个CSG树来避免由于面片的反复切割带来的数值误差累积并利用自适应的八叉树使得相交测试能在线性时间内完成.在全局化面片分类阶段,算法通过分治法使得分类始终在切割后的面片和原始输入模型之间进行来保证分类的精度;通过结合组分类策略和自适应的八叉树来进一步优化了分类性能。实验结果表明,本文提出的算法无论是在执行单次或连续布尔运算时都能在保证鲁棒性同时性能优于其他的算法,因此本文算法可广泛应用于交互式建模系统中,如数字雕刻、计算机辅助设计和制造（CAD/CAM）等.     

基于最优化分块的大规模数据体绘制加速方法

GPU加速体绘制已成为体可视化领域的研究热点,然而超出显存的大规模数据无法直接载入,成为GPU应用的瓶颈。分块技术能够在保证图像质量的条件下解决该问题,但分块数据的频繁加载和访问明显降低了绘制速度。针对上述问题,通过建立最优化分块模型得到了大规模数据的最优分块,并通过构造节点编号纹理和改进距离模板设计的方法进一步提高了基于八叉树的分块体绘制算法的绘制速度。实验结果表明,该方法加速效果明显。     

基于扩展“变球法”的颜色量化分析

 系统阐述了各种颜色量化方法，提出了利用改进了的“变球法”颜色量化算法进行颜色量化，满足了在纹织CAD设计中，设计人员因为工艺或者设计的需要，保留原图片上几种特定的颜色的要求。“变球法”从人的视觉的适应性角度出发，保证了所选代表色的合理性，一定程度上改良了纹织CAD的工艺，较好满足了工艺或设计的要求和需要。仿真结果表明，运用该算法的颜色量化效果好，误差小，基本接近原图。实际生产中的误差也得到了很好的控制，保证了其准确性。