基于射线法的凹多面体消隐算法研究与实现

摘要： 为了在计算机中得到空间图形的立体感显示效果，只能在输出界面显示空间图形中朝向观察者的表面，而其余部分则不被显示。空间立体可采用多边形建模。简单凸多面体的求解较容易，但凹多面体的求解则相对困难。在此利用图形学中的平移、旋转、正平行投影、深度缓存消隐算法、射线法等相关理论，结合可视化的MFC开发平台，研究并实现了一个凹多面体表面的全方位观察，对进一步研究消隐算法及射线法的改进具有较好的参考作用。

关键词： 平行投影； 消隐算法； 射线法； 凹多面体

中图分类号： TN919⁃34； TP391文献标识码： A文章编号： 1004⁃373X（2014）08⁃0129⁃03

Research and implementation of ray method based blanking algorithm for concave polyhedron

WEI Hong⁃chun

（Department of Computer Science， Sichuan University of Arts and Science， Dazhou 635000， China）

Abstract： In order to display three⁃dimensional graphics in the computer， only the surfaces of objects toward the observer are showed in the output interface， but the rests are not displayed. The three⁃dimensional model can be established by polygon. Its easy to solve simple convex polyhedron， but the concave polyhedron is not. In combinstion with visual MFC development platform， the all⁃round observation about the concave polyhedron is studied and implemented by using the theories of translation， rotation and parallel projection， depth buffer blanking algorithm， and ray method in graphics. It's a good reference to further research the improvements of blanking algorithm and ray method.

Keywords： paralell projection； blanking algorithm； ray method； concave polyhedron

0引言

在观察不透明物体时，只能看到物体朝向观察者的表面。当用计算机生成具有立体感的图形时，利用消隐算法可以得到一个确定的、立体感强的投影图。隐线、隐面消除算法与排序算法相关。排序的依据是被显示的点、线、面或体与观察点之间的几何距离。对于简单的凸多面体，可利用平面法线向量与视线向量的关系快速求解，但对于凹多面体，其求解算法较凸多面体复杂得多。本文利用射线法的深度缓存消隐算法和正平行投影的相关理论，研究并实现了一个凹多面体在键盘控制下的全方位显示，对进一步研究消隐算法及射线法的改进具有较好的参考。

1基本理论

在计算机中，复杂立体可以借助三角形、四边形等平面多边形完成建模，若要生成具有立体感的图形，须借助三维图形变换中相关算法，包括平移、旋转、缩放、投影、消隐等。但凹多面体仅这些理论还不够，必须运用计算几何中的其他相关知识，如角度和或射线法判断一个点是否在一个平面多边形内，快速排斥与交叉跨立判断两条线段是否相交等。相关算法理论的简介如下。

1.1消隐方法

（l） 背面消除算法

背面消除算法是隐藏面消除算法中的关键部分。在消隐问题中，最简单的问题是单个凸多面体。此时，利用背面消除即可达到隐面消除的目的。为了确定凸多面体的不可见面，对于每个面进行如下操作：

① 求平面法向量n；

② 求平面的视线向量v；

③ 计算v·n；

④ 根据v·n符号判别该面是否可见。

（2） 深度缓存Z⁃buffer消隐算法

深度缓存（Z⁃buffer）是在图像空间下的消隐算法，包括：帧缓冲器（保存各像素颜色值CB）和z缓冲器zBuffer（保存各像素处物体深度值ZB）。其中z 缓冲器中的单元与帧缓冲器中的单元一一对应。

算法思想：首先用给定深度值初始化z 缓冲器。当改变某个像素的颜色时，先检查当前像素点的深度值是否大于该像素原来的深度值，若大于，说明当前像素点更靠近观察点，则用当前色替换像素原来的颜色；否则说明当前像素点不可见，像素的颜色值不改变。Z⁃buffer 算法的实现步骤如下：

① 初始化ZB和CB，使ZB（i，j）=Zmax，CB（i，j）=背景色。其中，i=1，2，…,m，j=1，2，…，n。

② 对某个多边形，计算它在点（i，j）处的深度值zi，j。

③ 若zij

④ 对每个多边形重复②，③两步后，在CB中存放的就是消隐后的图形[1⁃2]。

1.2射线法判断点与平面多边形的位置

利用射线法判断一个平面点M是否位于一个多边形内部的原理如下：

从点M向左作水平射线，若M在多边形内部，则该射线与多边形的交点为奇数；若M在多边形外部，则交点个数必为偶数（包含0个）。顺序考虑多边形的每条边，便可求出该射线与各边交点的总数。

对于平面多边形的某条边PQ的特殊情况处理：

（1） 若射线穿过顶点P或Q，则会重复计数。处理规则是如果穿过的顶点纵坐标是PQ中较小的则忽略。

（2） 如果PQ为水平线段，则有可能与射线“重合”。处理规则是P点要么在PQ上，要么不在。只需在开始判断一下是否在PQ上[3⁃5]。

2算法设计与实现

在VC 6.0开发平台下，新建一基于MFC的单文档的名为CWhc3DTransform工程，在视图类中添加按键响应函数OnKeyDown（）、判断点是否位于位于多边形内的函数PointInPolygon（）。完成凹多面体深度缓存消隐算法的详细设计如下：

int zBuffer[MAXNUM][MAXNUM]；//深度缓存，外部数组

int cBuffer[MAXNUM][MAXNUM]；//颜色缓存，外部数组

CWhc3DTransformView（）

{//在构造函数中完成凹多边体相关数据的初始化

初始化颜色缓存与对应像素点的深度缓存

初始化凹多面体的各个顶点坐标

初始化凹多面体各个面的颜色

初始化多面体的总面数FN = 8（共8个面）

初始化faceInfo [ ][ ]。//第二维是面编号，faceInfo[i][0]是该面的顶点数，

// faceInfo[i][j]（j>0）是构成该面的顶点序列

用立体各顶点坐标初始化变换后的立体中心到原点的坐标分量

初始化变换后的立方体的坐标分量

将变换后的立方体平移到指定位置

初始化立方体相对于其起始状态的各坐标轴的旋转角

初始化立方体的最大包围盒

}

voidOnDraw（CDC* pDC）{ /*根据在OnKeyDown（）中完成的消隐算法，重新绘制该立体*/

设置背景为白色

用给定颜色绘制立体深度缓存中的像素点

}

voidOnKeyDown（UINT nChar， UINT nRepCnt， UINT nFlags） {//完成指定的变换及消隐

初始化颜色缓存与对应点的深度缓存

用多面体的原始顶点坐标初始化数组resultP

double real_per_degree = 3.1415926/180； //每度所对应的弧度数

计算在键盘相应键控制下，初始状态立方体分别绕坐标轴x，y，z旋转后的角度

生成绕z轴变化的变换阵并计算变换后的顶点坐标

生成绕x轴变化的变换阵并计算变换后的顶点坐标

生成绕y轴变化的变换阵并计算变换后的顶点坐标

将变换后的几何体平移到指定的位置，以方便显示

double zzbufer；//根据（x，y）计算该面上 （x，y）处的z坐标。

重置立方体的最大包围盒为初始值

重新计算立方体的最大包围盒，即最小的（xmin，ymin）和最大的（xmax，ymax）

While（若点（i，j）在最大包围盒中）{

for（k=0；k<总面数FN；k++）{//遍历每个面，面中的第0号元素记录了构成该面的顶点数

if（若（i，j）位于某个面k中）{//点（i，j）在第k个面内

根据该面k的法线向量的z分量

if（若法线向量的z分量> 0）{ /*z>0，该面可见，计算zzbufer坐标*/根据（i，j）计算该面上该点的zzbufer分量，即（i，j，zzbufer）

if（zzbufer > zBuffer[i][j]）

{ /*若（i，j）点处的z坐标>该点处的深度*/

zBuffer[i][j] = （int）zzbufer； //更换（i，j）处的深度值

cBuffer[i][j] = faceColor[k]；//更新颜色缓存（i，j）中的颜色值

}}}} }

RedrawWindow（）；

}

intPointInPolygon（int faceK，double xCoord， double yCoord）{//判断点与多边形的位置关系

/* 从第faceK面上的点（xCoord， yCoord）向左产生一条射线，记录与交点相交的个数counter*/

获取构成第faceK面的顶点数并保存在pointNum中

初始化交点个数counter = 0；

将第faceK面中各顶点转存到数组vertemp

for（i=0；i

p=第i点，q=第（（i+1）% pointNum）点

若点（xCoord， yCoord）在线段pq上，则return 1；

若线段pq是水平的，则continue；

//若处于相交线段的端点，取y坐标大的以避免重复计数

若射线穿过的顶点纵坐标是PQ中较大的，

则counter++；

若射线穿过的顶点纵坐标是QP中较大的，

则counter++；

若（利用快速排斥与交叉跨立实验判断当yCoord不是线段两端点，且线段pq与射线相交时）

counter++；

}

return （counter % 2）； //返回交点的个数是否为奇数

}

通过以上算法，给定的凹多面体可在键盘的上下左右键、Insert键、Delete键的控制下，完成在各种状态下的消隐显示[6]。运算结果如图1~图3所示（部分状态下的显示截图）。

图1 初始状态的消隐

3结语

在计算机中，获得物体的具有立体感的显示效果是一个较复杂的过程，涉及的算法较多，且人们对消隐算法的研究还在继续，以期获取更好显示效果。本文利用平行投影算法、基于射线法的深度缓存消隐算法研究并实现了一个凹多面体的立体显示过程，可以全方位地观察物体在各种位置的消隐状态，获得了较好的演示效果，并且能容易地将此算法改为详细的实现代码，对进一步研究射线法、消隐算法的改进具有较好的参考作用。

图2 施行变换后的消隐（1）

图3 施行变换后的消隐（2）

参考文献

[1] 王汝传，黄海平，林巧民.计算机图形学教程[M].2版.北京：人民邮电出版社，2009.

[2] 和青芳.计算机图形学原理及算法教程（Visual C++版）[M].

2版.北京：清华大学出版社，2010.

[3] 陈瑞卿，周健，虞烈.一种判断点与多边形关系的快速算法[J].西安交通大学学报，2007，41（1）：59⁃63.

[4] 马晨，张毅.一种改进的点与多边形关系的叉乘判别法[J].测绘科学，2013，38（1）：125⁃127.

[5] 李楠，肖克炎.一种改进的点在多边形内外判断算法[J].计算机工程，2012，38（5）：30⁃34.

[6] 卫洪春，彭小利.扫描线多边形区域填充算法研究[J].四川文理学院学报，2012，22（5）：77⁃82.

[7] 李雪，石产田.一种三角形内外点的快速判定方法[J].现代电子技术，2008，31（4）：110⁃112.

[8] 夏俊杰，赵刚.基于MFC的代码编辑器设计方法[J].现代电子技术，2012，35（12）：28⁃30.

// faceInfo[i][j]（j>0）是构成该面的顶点序列

用立体各顶点坐标初始化变换后的立体中心到原点的坐标分量

初始化变换后的立方体的坐标分量

将变换后的立方体平移到指定位置

初始化立方体相对于其起始状态的各坐标轴的旋转角

初始化立方体的最大包围盒

}

voidOnDraw（CDC* pDC）{ /*根据在OnKeyDown（）中完成的消隐算法，重新绘制该立体*/

设置背景为白色

用给定颜色绘制立体深度缓存中的像素点

}

voidOnKeyDown（UINT nChar， UINT nRepCnt， UINT nFlags） {//完成指定的变换及消隐

初始化颜色缓存与对应点的深度缓存

用多面体的原始顶点坐标初始化数组resultP

double real_per_degree = 3.1415926/180； //每度所对应的弧度数

计算在键盘相应键控制下，初始状态立方体分别绕坐标轴x，y，z旋转后的角度

生成绕z轴变化的变换阵并计算变换后的顶点坐标

生成绕x轴变化的变换阵并计算变换后的顶点坐标

生成绕y轴变化的变换阵并计算变换后的顶点坐标

将变换后的几何体平移到指定的位置，以方便显示

double zzbufer；//根据（x，y）计算该面上 （x，y）处的z坐标。

重置立方体的最大包围盒为初始值

重新计算立方体的最大包围盒，即最小的（xmin，ymin）和最大的（xmax，ymax）

While（若点（i，j）在最大包围盒中）{

for（k=0；k<总面数FN；k++）{//遍历每个面，面中的第0号元素记录了构成该面的顶点数

if（若（i，j）位于某个面k中）{//点（i，j）在第k个面内

根据该面k的法线向量的z分量

if（若法线向量的z分量> 0）{ /*z>0，该面可见，计算zzbufer坐标*/根据（i，j）计算该面上该点的zzbufer分量，即（i，j，zzbufer）

if（zzbufer > zBuffer[i][j]）

{ /*若（i，j）点处的z坐标>该点处的深度*/

zBuffer[i][j] = （int）zzbufer； //更换（i，j）处的深度值

cBuffer[i][j] = faceColor[k]；//更新颜色缓存（i，j）中的颜色值

}}}} }

RedrawWindow（）；

}

intPointInPolygon（int faceK，double xCoord， double yCoord）{//判断点与多边形的位置关系

/* 从第faceK面上的点（xCoord， yCoord）向左产生一条射线，记录与交点相交的个数counter*/

获取构成第faceK面的顶点数并保存在pointNum中

初始化交点个数counter = 0；

将第faceK面中各顶点转存到数组vertemp

for（i=0；i

p=第i点，q=第（（i+1）% pointNum）点

若点（xCoord， yCoord）在线段pq上，则return 1；

若线段pq是水平的，则continue；

//若处于相交线段的端点，取y坐标大的以避免重复计数

若射线穿过的顶点纵坐标是PQ中较大的，

则counter++；

若射线穿过的顶点纵坐标是QP中较大的，

则counter++；

若（利用快速排斥与交叉跨立实验判断当yCoord不是线段两端点，且线段pq与射线相交时）

counter++；

}

return （counter % 2）； //返回交点的个数是否为奇数

}

通过以上算法，给定的凹多面体可在键盘的上下左右键、Insert键、Delete键的控制下，完成在各种状态下的消隐显示[6]。运算结果如图1~图3所示（部分状态下的显示截图）。

图1 初始状态的消隐

3结语

在计算机中，获得物体的具有立体感的显示效果是一个较复杂的过程，涉及的算法较多，且人们对消隐算法的研究还在继续，以期获取更好显示效果。本文利用平行投影算法、基于射线法的深度缓存消隐算法研究并实现了一个凹多面体的立体显示过程，可以全方位地观察物体在各种位置的消隐状态，获得了较好的演示效果，并且能容易地将此算法改为详细的实现代码，对进一步研究射线法、消隐算法的改进具有较好的参考作用。

图2 施行变换后的消隐（1）

图3 施行变换后的消隐（2）

参考文献

[1] 王汝传，黄海平，林巧民.计算机图形学教程[M].2版.北京：人民邮电出版社，2009.

[2] 和青芳.计算机图形学原理及算法教程（Visual C++版）[M].

2版.北京：清华大学出版社，2010.

[3] 陈瑞卿，周健，虞烈.一种判断点与多边形关系的快速算法[J].西安交通大学学报，2007，41（1）：59⁃63.

[4] 马晨，张毅.一种改进的点与多边形关系的叉乘判别法[J].测绘科学，2013，38（1）：125⁃127.

[5] 李楠，肖克炎.一种改进的点在多边形内外判断算法[J].计算机工程，2012，38（5）：30⁃34.

[6] 卫洪春，彭小利.扫描线多边形区域填充算法研究[J].四川文理学院学报，2012，22（5）：77⁃82.

[7] 李雪，石产田.一种三角形内外点的快速判定方法[J].现代电子技术，2008，31（4）：110⁃112.

[8] 夏俊杰，赵刚.基于MFC的代码编辑器设计方法[J].现代电子技术，2012，35（12）：28⁃30.

// faceInfo[i][j]（j>0）是构成该面的顶点序列

用立体各顶点坐标初始化变换后的立体中心到原点的坐标分量

初始化变换后的立方体的坐标分量

将变换后的立方体平移到指定位置

初始化立方体相对于其起始状态的各坐标轴的旋转角

初始化立方体的最大包围盒

}

voidOnDraw（CDC* pDC）{ /*根据在OnKeyDown（）中完成的消隐算法，重新绘制该立体*/

设置背景为白色

用给定颜色绘制立体深度缓存中的像素点

}

voidOnKeyDown（UINT nChar， UINT nRepCnt， UINT nFlags） {//完成指定的变换及消隐

初始化颜色缓存与对应点的深度缓存

用多面体的原始顶点坐标初始化数组resultP

double real_per_degree = 3.1415926/180； //每度所对应的弧度数

计算在键盘相应键控制下，初始状态立方体分别绕坐标轴x，y，z旋转后的角度

生成绕z轴变化的变换阵并计算变换后的顶点坐标

生成绕x轴变化的变换阵并计算变换后的顶点坐标

生成绕y轴变化的变换阵并计算变换后的顶点坐标

将变换后的几何体平移到指定的位置，以方便显示

double zzbufer；//根据（x，y）计算该面上 （x，y）处的z坐标。

重置立方体的最大包围盒为初始值

重新计算立方体的最大包围盒，即最小的（xmin，ymin）和最大的（xmax，ymax）

While（若点（i，j）在最大包围盒中）{

for（k=0；k<总面数FN；k++）{//遍历每个面，面中的第0号元素记录了构成该面的顶点数

if（若（i，j）位于某个面k中）{//点（i，j）在第k个面内

根据该面k的法线向量的z分量

if（若法线向量的z分量> 0）{ /*z>0，该面可见，计算zzbufer坐标*/根据（i，j）计算该面上该点的zzbufer分量，即（i，j，zzbufer）

if（zzbufer > zBuffer[i][j]）

{ /*若（i，j）点处的z坐标>该点处的深度*/

zBuffer[i][j] = （int）zzbufer； //更换（i，j）处的深度值

cBuffer[i][j] = faceColor[k]；//更新颜色缓存（i，j）中的颜色值

}}}} }

RedrawWindow（）；

}

intPointInPolygon（int faceK，double xCoord， double yCoord）{//判断点与多边形的位置关系

/* 从第faceK面上的点（xCoord， yCoord）向左产生一条射线，记录与交点相交的个数counter*/

获取构成第faceK面的顶点数并保存在pointNum中

初始化交点个数counter = 0；

将第faceK面中各顶点转存到数组vertemp

for（i=0；i

p=第i点，q=第（（i+1）% pointNum）点

若点（xCoord， yCoord）在线段pq上，则return 1；

若线段pq是水平的，则continue；

//若处于相交线段的端点，取y坐标大的以避免重复计数

若射线穿过的顶点纵坐标是PQ中较大的，

则counter++；

若射线穿过的顶点纵坐标是QP中较大的，

则counter++；

若（利用快速排斥与交叉跨立实验判断当yCoord不是线段两端点，且线段pq与射线相交时）

counter++；

}

return （counter % 2）； //返回交点的个数是否为奇数

}

通过以上算法，给定的凹多面体可在键盘的上下左右键、Insert键、Delete键的控制下，完成在各种状态下的消隐显示[6]。运算结果如图1~图3所示（部分状态下的显示截图）。

图1 初始状态的消隐

3结语

在计算机中，获得物体的具有立体感的显示效果是一个较复杂的过程，涉及的算法较多，且人们对消隐算法的研究还在继续，以期获取更好显示效果。本文利用平行投影算法、基于射线法的深度缓存消隐算法研究并实现了一个凹多面体的立体显示过程，可以全方位地观察物体在各种位置的消隐状态，获得了较好的演示效果，并且能容易地将此算法改为详细的实现代码，对进一步研究射线法、消隐算法的改进具有较好的参考作用。

图2 施行变换后的消隐（1）

图3 施行变换后的消隐（2）

参考文献

[1] 王汝传，黄海平，林巧民.计算机图形学教程[M].2版.北京：人民邮电出版社，2009.

[2] 和青芳.计算机图形学原理及算法教程（Visual C++版）[M].

2版.北京：清华大学出版社，2010.

[3] 陈瑞卿，周健，虞烈.一种判断点与多边形关系的快速算法[J].西安交通大学学报，2007，41（1）：59⁃63.

[4] 马晨，张毅.一种改进的点与多边形关系的叉乘判别法[J].测绘科学，2013，38（1）：125⁃127.

[5] 李楠，肖克炎.一种改进的点在多边形内外判断算法[J].计算机工程，2012，38（5）：30⁃34.

[6] 卫洪春，彭小利.扫描线多边形区域填充算法研究[J].四川文理学院学报，2012，22（5）：77⁃82.

[7] 李雪，石产田.一种三角形内外点的快速判定方法[J].现代电子技术，2008，31（4）：110⁃112.

[8] 夏俊杰，赵刚.基于MFC的代码编辑器设计方法[J].现代电子技术，2012，35（12）：28⁃30.