一种新的线框模型自动隐藏线算法

蒋曙

摘要：为了解决立体几何教学软件中不可见线段的虚线消隐问题，笔者设计了一种新的线框模型自动隐藏线算法：找出立体几何图形中所有线段与面的交点，以及线段与线段在投影平面中的交点，并用这些交点重新分解现有线段，然后再用后向面判别法判断新线段的可见性。经测试证明，此算法完全能实现立体几何图形中不可见线段的虚线消隐。

关键词：线消隐 算法 立体几何

中图分类号：TP391.41 文献标识码：A 文章编号：1007-9416（2016）12-0130-01

在生成真实感图形时，考虑最多的是如何判断从某一个选定的观察位置所能看到的场景中的内容。所谓消隐，是为了获得更好的视觉效果，往往会把不在视线范围的部分（隐藏面或隐藏线）进行消除或以其他方式显示，它包含隐藏面消除和隐藏线消除。在三维造型技术、真实感图形的显示、虑拟场景的显示、以及在地形、地图的绘制中，消隐都起到至关重要的作用。所以研究和实现消隐算法，并根据场景的复杂度和各个不同应用领域的场景来提高消隐算法的速度是很有必要的，它对整个三维图形显示、真实感图形的显示以及各种地形地貌图形的显示是很有意义的。

1 可见面判别算法

根据其处理场景时是直接处理对象定义还是处理它们的投影图像，隐藏面消除算法分为物空间（object-space）算法和像空间（image-space）算法。物空间算法将场景中的各对象和对象的各个组成部件相互进行比较，从而最终判别出哪些面是可见的，常见的物空间算法有后向面判别算法、BSP树算法、深度排序算法、光线投射算法。像空间算法是在平面投影平面上逐点判断各像素所对应的可见面。常见的像空间算法有深度缓存算法（也叫z缓冲器算法）、A缓存算法、扫描线算法、区域细分算法和八叉树算法。

2 线框可见算法

我们常常为了快速显示对象特征而仅用轮廓线形式显示三维场景，生成场景线框图最快的方法是显示对象所有的边。然而，在这样的显示中很难确定对象的前后特征。一种解决办法是应用可见性测试，将隐藏线消除或使用与可见面不同的方式进行显示。常用的可见线判别算法主要是由可见面判别算法移植过来，或者由图形程序接口（如OpenGL）来实现。但是在一些场合下，如果使用上述方式实现可见线判别算法，工作量太大。笔者在开发立体几何教学软件时，就遇到了这样的问题。为了解决问题，设计了一套简单易用的可见线判别算法。其主要原理是将所有边按照一定规则分解成一些子边，然后判断这些子边与所有的面之间的位置关系仅为在平面前、后和平面上三种关系，从而实现了边的可见性判断，并以虚线的方式进行消隐。

3 算法实现

3.1 基本数据结构

本算法是为了解决立体几何图形的线消隐问题，在整个算法过程中主要涉及了构造立体几何图形所必须的三个几何元素：点、边、面，所以，最基本的数据结构也就是点（Point）、线（Edge）、面（Face）和有前面三项构成几何体（Solid），具体如表1-2所示。

立体几何教学软件中的图形都是线框模型，所以实际渲染绘图时，主要绘制顶点、线段，具体过程为先判断所有边的可见性，然后用实线画出可见的边，用虚线画出不可见的边，画出顶点，就得到了所需要的立体图形。

3.2 算法主要流程

第一步：找出边和面的内交点。找出所有边与面的内交点，所谓内交点指的是边与面的交点，且交点位于边的内部，而不在边的端点或者延长线上的交点。如图1所示，边EF与面ABCD相交于点G，且点G在边EF内，所以点G是边EF的一个内交点。

实现方法及要点：（1）必须用投影变换之前的坐标，也就是P_Init或P_View。（2）根据边的两个端点P_Strat（xs，ys，zs）和P_End（xe，ye，ze），建立直线参数方程

第二步：找出所有边与边的内交点。边与边的内交点是指在投影变换之后，根据所有边的在投影平面上的关系，判断边与边是否存在交点，且交点在边的内部。如图2所示，在三维空间中，边EF与边CD是没有交点的，但是在投影平面上，邊EF与边CD有一个内交点I，同样，边EF与边AB有一个内交点H。

实现方法及要点：（1）必须用投影变换之后的坐标，也就是P_Pro。（2）每次求两边交点时，两边参数方程可以表示为：

第三步：根据内交点划分子边。将第一步和第二步中得到的内交点和边原来的两个端点重新划分边，如图2所示，边EF有3个内交点，因此将边EF分解成边EH、边HG、边GI和边IF，一共4条新边。实现方法及要点：把点坐标代入直线参数方程，求出参数，然后根据参数t的大小排序，得到所有内交点之间的顺序关系。

第四步：判断所有子边与面的位置关系。经过第三步重新划分后的边与面之间的位置关系有三种：在平面上、在平面后面、在平面前面。其中，只有在平面前面的这种情况，表明该边是可见的。

实现方法及要点：（1）判断边与面位置关系时，面的一般方程中的参数A、B、C、D必须严格使用从前往后观察平面时逆时针顺序排列的点坐标计算。解决方法为：任意选择面上的三个顶点、、，如果，则这三点是逆时针顺序，否则调整三点顺序为、、。计算向量和的叉积，其结果的三个分量就是平面方程的参数A、B、C，并和其中一个点坐标代入求出。（2）将边的两端点坐标代入，当至少有一个端点代入计算的结果大于0时，表示这个线段不被改平面遮挡，即可见。（3）有时边处在两个平面之间，造成可见性结果冲突的情况，这时只要遍历所有的面，并且边的每一次可见性标判断结果与之前的结果进行逻辑与运算即可解决。

4 结语

本算法可以用于各种平台，不依赖于硬件和图形库函数，用各种计算机语言实现也比较简单，笔者用C#结合OpenGL编程实现了该算法，并且制作了测试程序，其动态虚线消隐的效果完全满足要求。同时，该算法不仅适用于封闭的凸多面体，也适用于不封闭的情况。对于凹多边形情况，只需修改第四步中平面参数求解方式就可解决。

参考文献

[1]彭群生，金小刚，万华根，冯结青，编著.计算机图形学应用基础[M].北京：科学出版社，2009.

[2]D.F.罗杰斯著，梁友栋等译.计算机图形学的算法基础[M].科学出版社，1984.