Question

请大家帮忙分析下这段代码.(奖励分数50)

void RenderHeightMap(BYTE pHeightMap[])
{
int X = 0, Y = 0; // 地形的网格的位置
int x, y, z;
bool bSwitchSides = false;

// 判断高程数据是否存在
if(!pHeightMap) return;

// 捆绑纹理
glBindTexture(GL_TEXTURE_2D, g_Texture[0]);

// 以三角形面片的形式绘制地形
glBegin( GL_TRIANGLE_STRIP );

// 遍历高程数据中所有行
for ( X = 0; X <= MAP_SIZE; X += STEP_SIZE )
{
// 判断渲染的面
if(bSwitchSides)
{
// 遍历所有列
for ( Y = MAP_SIZE; Y >= 0; Y -= STEP_SIZE )
{
// 获得高程值
x = X;
y = Height(pHeightMap, X, Y );
z = Y;

// 设置当前的纹理坐标
SetTextureCoord( (float)x, (float)z );
glVertex3i(x, y, z);

// 获得高程值
x = X + STEP_SIZE;
y = Height(pHeightMap, X + STEP_SIZE, Y );
z = Y;

// 设置当前的纹理坐标
SetTextureCoord( (float)x, (float)z );
glVertex3i(x, y, z);
}
}
else
{
// 遍历所有的行
for ( Y = 0; Y <= MAP_SIZE; Y += STEP_SIZE )
{
// 获得高程值
x = X + STEP_SIZE;
y = Height(pHeightMap, X + STEP_SIZE, Y );
z = Y;

// 设置纹理坐标
SetTextureCoord( (float)x, (float)z );
glVertex3i(x, y, z);

// 获得高程值
x = X;
y = Height(pHeightMap, X, Y );
z = Y;

// 设置当前的纹理坐标
SetTextureCoord( (float)x, (float)z );
glVertex3i(x, y, z);
}
}

bSwitchSides = !bSwitchSides;
}

// 绘制完成
glEnd();
}

这是用三角形网格画地形例子的一段代码,我不明白这个机制是按什么规律画三角网格的?

Answer 1

一种基于格网的快速等值线充填算法

摘 要:本文提出一种基于格网的等值线跟踪，适用于任意边界分割的快速充填算法
，实现充填的矢量化效果。根据边界线与非封闭等值线间的关系，建立等值线间的拓扑
关系，并以树结构方式存储，以准确快速地实现边界线、非封闭等值线之间的封闭和封
闭等值线间的嵌套。该算法已成功应用于海量多波束地形数据的成图，克服了常用多波
束后处理成图软件栅格充填与等值线之间的失配。
关键词：网格数据；等值线跟踪；拓扑结构；填色
A Fast Algorithm of Color Fill between Contours
Based on Grid Data
WU Zi-yin, GAO Jin-yao
(Key Lab of Submarine GeoSciences,SOA,Hangzhou， Zhejiang,310012)
Abstract:Based on contour tracing for grid data,a fast algorithm of color fi
ll is proposed to cope with random boundaries surrounding data gaps and to r
ealize the vector effect of color fill graph. From the relationship between
boundary lines and unclosed contours,the topologic structure among contours
can be built and stored in a tree structure.Such a topologic structure displ
ays the linking and closing between boundary lines and unclosed contours,the
nesting among closed polygon in the order of tree rings.It is successfully
applied in mapping of huge volume of submarine topographic data observed by
multibeam,and it overcomes the inconsistency between color blocks and contou
rs produced by mapping software for multibeam postprocessing.
Key words:grid data;contour tracing;topologic structure;color fill
1 引 言
等值线充填，就其实质，是等值线间建立拓扑关系〔1～3〕，也就是建立一种树结
构关系，一直是一个比较棘手的问题。尤其在不规则内外边界，任意等值间距的情况下
，很难建立等值线间拓扑关系。在实际应用过程中，笔者发现有很多软件不能很好解决
这个问题，例如：GMT,SeaView,Simard,Elac等。本文将阐述在规则格网情况下，在边界
线的基础上，建立等值线间拓扑关系，最终实现任意边界，任意等值间距情况下的等值
线充填。
2 算法基本原理
等值线跟踪是在已知格网点的基础上，内插出等值线点，然后跟踪等值点，形成封
闭或非封闭等值线〔4～7〕。非封闭等值线的端点必然落在边界线上，而边界线必然是
封闭的，通过跟踪边界线，再把非封闭等值线端点插入边界线，通过边界线建立等值线
间的拓扑关系，在此基础上跟踪出封闭多边形，实现等值线的填充。该算法分为以下几
大步骤：边界线的跟踪，非封闭等值线端点插入边界线中并排序，非封闭等值线建立拓
扑关系，跟踪封闭多边形并排序，等值线的充填。
2.1 边界线的跟踪
要实现边界线的跟踪，首先要找出边界线点。所谓边界线点，就是在某一格网点
的周围至少有一空白格网点或非空的边框点，该点即为边界线点。然后用类似跟踪等值
线的方法即可跟踪出边界线（参见图1）。
图1 边界线跟踪
Fig.1 Tracing boundaries
笔者用三级链表来存储边界线。链表结构如下：
typedef struct BOUNDARYS //边界线数目链表
{
BOUNDARY ��pBoundary;//
某条边界线指针
BOUNDARYS�*p_Next;// 下一条边界线数目链表指针
BOUNDARYS（）
。
pBoundary＝NULL;
p_Next=NULL;
。
} BOUNDARYS;
typedef struct BOUNDARY//边界线链表
{
BOUNDARYPOINT�*pPoint;//某一边界线点指针
BOUNDARY�*p_Next;// 下一边界线点指针
BOUNDARY()
{
pPoint=NULL;
p_Next=NULL;
}
} BOUNDARY;
} BOUNDARY;
typedef struct BOUNDARYPOINT//边界线点链表
{
CONTOUR�*pContour;//某条等值线指针
bool Direction;// 等值线方向
BOUNDARY�*p_Next;// 下一边界线点指针
BOUNDARYPOINT()
{
pContour=NULL;
p_Next=NULL;
}
} BOUNDARYPOINT;
3个链表的关系是: BOUNDARYS→BOUNDARY→BOUNDARYPOINT; BOUNDARYS链表存储所
有的边界线, BOUNDARY链表存储某一条边界线, BOUNDARYPOINT链表存储非封闭等值线端
点。
2.2 非封闭等值线端点插入边界线中并排序
非封闭等值线端点必然落在边界线上，并且是有序排列的，在两个边界线点之间
的等值线端点按等值线值要么从高到低排列，要么从低到高排列（参见图2）。
图2 非封闭等值线与边界线关系
Fig.2 Relationship between unclosed contours and boundaries
笔者把非封闭等值线端点有序地插入BOUNDARYPOINT（边界线点链表）链表中。
2.3 非封闭等值线建立拓扑关系
在非封闭等值线端点插入边界线的基础上，非封闭等值线建立拓扑关系。
为了建立非封闭等值线拓扑关系，必须先建立这样一个等值线树结构：
typedef struct CONTOUR//某条等值线链表
{
float Height;//等值线值
double *X,�*Y;// 等值点坐标值
long Num;// 等值线上的坐标点数目
CONTOURLABEL �*pLabel;//等值线标注值链表指针
RECT ExtRc;//该等值线的最小扩展框;
bool Closed;//等值线是否封闭标识符；
CONTOUR
*pHeadUp,�*pHeadDown,
�*pTrailUp,
*pTrailDown;//与该等值线有拓扑关系的等值线指针
bool
HUp,HDown,TUp,TDown;//标识等值线的方向
CONTOUR()
{
Height=-1;
X=Y=NULL;
Num=-1;
pLabel=NULL;
Closed=false;
p_Next=pHeadUp=pHeadDown=pTrailUp=pTrailDown=NULL;
HUp=HDown=TUp=TDown=true;
}
HEIGHTLIST *p_Next;//下一等值线指针
CONTOURS *p_NextContour;// 下一级等值线指针
}CONTOUR;
与某条非封闭等值线有拓扑关系的等值线最多有4条，即两端点各指向两条等值线，
这些等值线也可能指向它本身。（图3的填色效果表明该拓扑关系的可靠性）
图3 非封闭等值线与边界线建立拓扑关系
Fig.3 Topologic relation between unclosed
contours and boundaries
在“非封闭等值线端点插入边界线中并排序”中已阐述如何把等值线端点插入边界
线中，通过链表BOUNDARYPOINT（边界线点链表），很容易找到与等值线有拓扑关系的等
值线，并把它的指针写入链表CONTOUR（等值线链表）中。
2.4 跟踪封闭多边形并排序
从某一条非封闭等值线出发，沿顺时针或逆时针方向跟踪，必然会返回到这条等值
线， 从而构成封闭多边形，然后把这些封闭多边形按扩展框的大小有序地排列，形成封
闭多边形嵌套系列，即完成封闭区域的跟踪。对于封闭等值线，可做为一封闭区域，在
跟踪好封闭多边形后，一起排序，并加入封闭多边形嵌套链表（图4表明该算法完全可以
建立复杂的拓扑、嵌套关系）。
图4 建立等值树并实现充填算法
Fig.4 Tree structure of contours built for realizing fill algorithm
为了储存跟踪的封闭多边形，笔者建立了一三重链表结构：
typedef struct BLOCKNUM//填充区域系列链表
{
BLOCKS *pBlocks;//某一填充区域系列指针
BLOCKNUM*p_Next;//下一填充区域系列链表
BLOCKS()
{
pBlocks=NULL;
p_Next=NULL;
}
} BLOCKNUM；
typedef struct BLOCKS//填充区域系列链表
{
BLOCK *pBlock;//某一填充区域指针
BLOCKS *p_Next;//下一填充区域系列链表
BLOCKS()
{
pBlock=NULL;
p_Next=NULL;
}
}
typedef struct BLOCK//填充区域链表
{
PEN hPen;//笔型
BRUSH hBrush;//填充图案
CONTOUR *pContour;//等值线指针
bool Direction;//等值线方向:true:正向；false:反向
BLOCK ()
{
pContour=NULL;
Direction=true;
}
};
以上3个链表的关系是：BLOCK→BLOCKS→BLOCKNUM; BLOCK链表用于存储某一封闭多
边形，BLOCKS链表用于存储某一地形单元的封闭多边形系列（例如：海山，凹地），BL
OCKNUM链表用于存储BLOCKS。
2.5 等值线的充填
在“跟踪封闭多边形并排序”中已详细阐述如何从非封闭等值线跟踪出封闭多边形
，并储存在BLOCK（填充区域链表）链表中，同时根据BLOCK链表中CONTOUR（等值线链表
）链表中等值线值，设置封闭多边形的笔型（PEN）、填充图案（BRUSH）、颜色。建立
了非封闭等值线间的拓扑关系（储存在BLOCK中），同时建立了封闭多边形的嵌套关系（
储存在BLOCKS中）,再根据笔型、填充图案、颜色，很容易实现等值线的充填。
3 和其他算法的比较
有很多软件用栅格填充等值线，即在格网的基础上，把格网再细分成若干小格网，
再按格网的值，以矩形色块的方式实现等值线的填充〔8～10〕，例如：GMT, Simard多
波束系统，Elac多波束系统，SeaView等。这种算法比较简单、快捷，但有它本身的缺陷
，只适合小比例尺，格网很密的情况下，在大比例尺，格网稀的情况下会出现锯齿状多
边形边界。而本算法在任意比例尺，任意格网情况下都可非常好的实现等值
线的充填。
锯齿状多边形边界
Fig.5 Zigzag polygon boundaries
“Win Surfer”是微机上应用很普遍的一种绘图软件，功能强大，速度快捷；笔者
把该算法的计算速度与“Win Surfer”软件对比了一下，速度不亚于“Win Surfer”软
件。笔者发现，在格网很密，图面变化很复杂的情况下，“Win Surfer”软件充填算法
会出现一些问题，而本算法适合于任意情况
“WinSurfer”不能实现充填的范例
Fig.6 Graphics produced by “WinSurfer” failed in color fill
本算法实现的充填图
Fig.7 Map of color fill realized by the fill algorithm proposed in this pap
er