0引言
基于DirectX开发的海图是运行在硬件抽象层上，既可以充分利用系统硬件的加速功能，又能隐藏硬件的设备特性。通过编写与设备无关的高效代码，DirectX能以较高的效率来缩短海图频繁操作时实时刷新时间。本文利用Direct3D采用Graham凸多边形算法绘制半透明式的海图区域，避免了依次填充多边形顶点缓冲区引起的三角形重复绘制和区域缺失等问题，使在电子海图［1］操作时支持用户更自由灵活地添加区域。
1问题描述
在计算机图形学中，任何复杂的几何模型可以看成由无数个三角形无缝连接形成的，因此在Direct3D中采用“三角扇”的方式进行海图区域绘制。
在编辑海图区域时，比如鼠标依次随机点下5个点，形成点链表，而绘制“三角形扇”的特点是其所有三角形共享一个顶点，系统使用顶点2、3、1画第一个三角形，3、4、1画第2个三角形，4、5、1画第3个三角形，如图1所示。
在编辑第5个点时，发现第3个三角形与第1个和第2个有重绘的区域，颜色绘制不均匀，并且该5个点并不能构成一个完整的区域。为解决区域缺失问题，经过分析验证，选用Graham算法可较好地解决上述问题。
2Graham算法
凸包定义:当多边形的顶点按顺时针排列时，如果多边形的内部区域总在任意边的右侧，则称该多边形为凸多边形，简称凸包或凸壳。Graham算法是依据凸多边形的各个顶点必在多边形的任意一条边的同一侧，并利用平面上任意3点所构成的回路是左转还是右转的判断法来求平面点集的凸包。
点a=(xa，ya)，b=(xb，yb)，c=(xc，yc)是平面上的任意三点:
当D为正时，a，b，c构成一个逆时针方向的回路，即a，b，c是左转的，如图2所示，该点为凸点;当D为负时，a，b，c构成一个顺时针方向的回路，即a，b，c是右转的，如图3所示，该点为凹点;当D为零时，此三点共线
多边形顶点按顺时针排列，可以避免三角形之间的重绘，而凸多边形的算法又可以解决区域缺失问题。
3软件处理流程
海图区域绘制流程图见图4，具体步骤如下:
第一步:输入n个像素点，形成点链表，判断是否构成多边形;
第二步:查找基点。首先，在平面上集S中寻找y坐标最小的点。如果有两个以上的点，其y坐标都是最小的，就选择最右边的一点，把它称为基点p0;
第三步:计算出各点与基点构成的向量，按各向量与x轴之间的夹角的升序对该向量进行排序，再删除相同的向量，利用向量三角形计算公式得到首尾依次相连的向量;
第四步:依次删除不在凸包上的向量。外积判断旋转方向，如果叉积小于0，删除前一个向量后，更新当前向量，与前面的向量首尾相连;如果叉积大于0，向量保持不变，继续循环;
第五步:在海图中渲染区域。
4场景渲染及实现效果
顶点缓冲区中的顶点格式可以包含顶点坐标、颜色、法线方向、纹理坐标等属性。D3DFVF_CUSTOMVEＲTEX将作为参数传递给顶点缓冲区创建函数CreateVertexBuffer()，将顶点格式通知Direct3D渲染引擎［3］。
顶点缓冲区(VertexBuffer)是Direct3D用来保存顶点数据的内存缓冲区，可以对顶点缓冲区中的顶点数据进行诸如坐标变换、光照等操作，最后打开Alpha通道，将顶点缓冲区中的顶点构成海图区域显示输出至屏幕上，其效果如图5所示
LPDIＲECT3DVEＲTEXBUFFEＲ9m_pVB=NULL;//创建顶点缓冲
if(FAILED(pDevice-＞CreateVertexBuffer((MAXANCHOＲ)*sizeof(CUSTOMVEＲTEX)，0，D3DFVF_CUSTOMVEＲTEX，D3DPOOL_MANAGED，＆m_pVB，NULL)))
//渲染
//Alpha通道打开
pDevice-＞SetＲenderState(D3DＲS_ALPHABLENDENABLE，TＲUE);
//多边形区域填充模式—面模式pDevice-＞SetＲenderState(D3DＲS_FILLMODE，D3DFILL_SOLID);
//着色模式—平面着色
pDevice-＞SetＲenderState(D3DＲS_SHADEMODE，D3DSHADE_FLAT);
pDevice-＞SetStreamSource(0，m_pVBBeamPol，0，sizeof(CUSTOMVEＲTEX));
pDevice-＞SetFVF(D3DFVF_CUSTOMVEＲTEX);
pDevice-＞DrawPrimitive(D3DPT_TＲIANGLEFAN，0，Num-2);
//Alpha通道关闭
pDevice-＞SetＲenderState(D3DＲS_ALPHABLENDENABLE，FALSE)
5结束语
本文给出了基于Direct3D的电子海图区域绘制方法，采用Graham凸多边形算法绘制半透明式的海图区域，解决了海图绘制中的关键技术。软件实现效果证明了本文提出的方法是有效可行的，在海图绘制中具有重要的应用价值。
