题目：基于体数据的非真实感绘制的研究与实现

非真实感绘制(Non-Photorealistic Rendering, NPR)是指计算机图形技术和绘画艺术相结合的研究领域，它着眼于突出场景的重要信息，使人获得更直观和更深刻的印象。目前针对体数据的非真实感绘制研究相对缺乏，传统方法大部分是对体数据提取等值面，构建三维网格，在该网格上进行非真实感绘制，该方法的内存，时间成本会随着数据规模的增大而增多，并存在着等值面遮挡问题。

本论文结合当前GPU强大的可编程图形流水线以及通用并行计算能力，提出了一种直接在体数据中提取三维特征线并矢量化，进行非真实感绘制的方法，并取得了以下成果：

（1）给出并实现了一种对体数据进行直接三维特征线提取方法。本文提出并实现了一种基于能量最小化约束的二维特征线向三维特征线映射的方法，该方法不需要借助等值面的提取过程。首先，从多个视点对体数据进行直接体绘制，采用的是基于GPU的光线投射算法，获得多个二维渲染结果。其次，对它们利用轮廓线检测算法，提取二维特征线。最后，根据能量最小化约束，把二维特征线映射为三维特征线，同时借助动态规划思想在GPU上求解，加快了计算效率。

（2）给出并实现了一种基于标量场和矢量场的对三维特征线聚类的方法。在初步得到的候选三维特征线，在一定程度上较为杂乱无序 ，需要进一步聚类。首先，本文定义了反映三维特征线几何拓扑信息的曲线密度场，曲线方向场。曲线密度场是标量场，反映了三维特征线在空间中的分布；曲线方向场是矢量场，反映了三维特征线在空间中的方向信息。其次，针对标量场或矢量场的引导信息，通过引入最小二乘解思想并迭代求解，对场内的离散点，进行聚类成点集并求解方向，点集及其方向能够更加准确的反应出三维特征线的分布和方向信息。

（3）给出并实现了一种特征线拟合并矢量化算法。在对三维特征线聚类后，需要对聚类结果进行特征线拟合。首先，本文为聚类结果引入图(Graph)数据结构，图中的节点为各个聚类结果，边的权重为两个聚类点集之间的距离；其次，为该图求解对应的多颗最小生成树结构，从而达到特征线拟合的目的；最后，在此基础上利用贝塞尔曲线进一步拟合，生成更加光滑的矢量化曲线。