📄
字号:
style='color:red'>消除隐藏面</span></a>算法的基本思想</span></span><span lang=EN-US
style='font-size:12.0pt;font-family:宋体'><o:p></o:p></span></p>
</td>
</tr>
</table>
<p class=MsoNormal><span style='font-size:13.5pt;font-family:隶书;color:purple'>内容简介<span
lang=EN-US><o:p></o:p></span></span></p>
<p style='margin-top:9.0pt;line-height:130%'><span style='font-size:10.0pt;
font-family:仿宋_GB2312;mso-hansi-font-family:"Times New Roman"'>光栅显示器上显示的图形，称之为<span
style='color:maroon'>光栅图形</span>。光栅显示器可以看作是一个象素矩阵，在光栅显示器上显示的任何一个图形，实际上都是一些具有一种或多种颜色和灰度象素的集合。由于对一个具体的光栅显示器来说，象素个数是有限的，象素的颜色和灰度等级也是有限的，象素是有大小的，所以光栅图形只是近似的实际图形。如何使光栅图形最完美地逼近实际图形，便是光栅图形学要研究的内容。以后，我们提到“显示器”时，如未特别声明，均指光栅显示器。</span></p>
<p style='margin-top:9.0pt;line-height:130%'><span lang=EN-US style='font-size:
10.0pt;mso-ascii-font-family:仿宋_GB2312;mso-fareast-font-family:仿宋_GB2312'> </span><span
lang=EN-US style='font-size:10.0pt;font-family:仿宋_GB2312'> 确定最佳逼近图形的象素集合，并用指定的颜色和灰度设置象素的过程称为<span
style='color:maroon'>图形的扫描转换</span>或<span style='color:maroon'>光栅化</span>。</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>对于一维图形，在不考虑线宽时，用一个象素宽的直线或曲线来显示图形。二维图形的光栅化必须确定区域对应的象素集，将各个象素设置成指定的颜色和灰度，也称</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312'>之为<span lang=EN-US
style='color:red'><a
href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/CG_Txt_2_017.htm#1"><span
style='color:red'>区域填充</span></a></span>。</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>任何图形光栅化后，显示在屏幕上的一个窗口里，超出窗口的部分不予显示。确定一个图形的哪些部分在窗口内，必须显示；哪些部分落在窗口之外，不予显示，这需要对图形</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312'>进行<span lang=EN-US
style='color:red'><a
href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/CG_Txt_2_024.htm"><span
style='color:red'>裁剪</span></a></span>。</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>裁剪通常在扫描转换之前进行，从而可以对图形不可见部分不必进行扫描转换。在光栅图形中，非水平和垂直的直线用象素集合表示时，会呈锯齿状，这种现象称之</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312'>为<span lang=EN-US
style='color:red'><a
href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/CG_Txt_2_031.htm"><span
style='color:red'>走样</span></a></span></span><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;mso-fareast-font-family:宋体'>(aliasing)</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312'>；</span><span style='font-size:
10.0pt;font-family:仿宋_GB2312;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>用于减少或消除走样的技术称为</span><span lang=EN-US
style='font-size:10.0pt;font-family:仿宋_GB2312;color:red'><a
href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/CG_Txt_2_031.htm"><span
style='color:red'>反走样</span></a></span><span lang=EN-US style='font-size:10.0pt;
font-family:仿宋_GB2312'>(antialiasing)。</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>提高显示器的空间分辨率可以减轻走样问题，但这是以提高设备成本为代价的。实际上，当显示器象素可以用多亮度（或灰度）显示时，可以通过调整图形上各象素的亮度来减轻走样问题。</span></p>
<p style='line-height:130%'><span lang=EN-US style='font-size:10.0pt;
mso-ascii-font-family:仿宋_GB2312;mso-fareast-font-family:仿宋_GB2312'> </span><span
lang=EN-US style='font-size:10.0pt;font-family:仿宋_GB2312'> </span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>图形反映的是现实世界中的物体，大多数物体是不透明的，如果从某一个角度观察物体，则物体的某些部分便不可见，即被隐藏起来了。如果在该物体的图形中，不把隐藏的线或面删除，容易导致对图形的错误理解。为了使计算机图形能够真实地反映这一现象，必须把隐藏的部分从图形中消除，习惯上称作</span><span
lang=EN-US style='font-size:10.0pt;font-family:仿宋_GB2312;color:red'><a
href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/CG_Txt_2_037.htm#2"><span
style='color:red'>消除隐藏线</span></a></span><span style='font-size:10.0pt;
font-family:仿宋_GB2312'>和<span lang=EN-US style='color:red'><a
href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/CG_Txt_2_038.htm#1"><span
style='color:red'>隐藏面</span></a></span>，或简称为<span lang=EN-US style='color:red'><a
href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/CG_Txt_2_035.htm"><span
style='color:red'>消隐</span></a></span>。</span></p>
<p style='line-height:130%'><span lang=EN-US style='font-size:10.0pt;
mso-ascii-font-family:仿宋_GB2312;mso-fareast-font-family:仿宋_GB2312'> </span><span
lang=EN-US style='font-size:10.0pt;font-family:仿宋_GB2312'> 本章将主要介绍光栅图形学的基本算法。</span></p>
<p align=center style='text-align:center'><b><span lang=EN-US style='font-size:
18.0pt;color:green'>2.1</span><span lang=EN-US style='color:green'> </span></b><b><span
style='font-size:18.0pt;font-family:仿宋_GB2312;color:green'>直线段的扫描转换算法</span></b></p>
<p style='line-height:150%'><span lang=EN-US> </span><span
style='font-family:楷体_GB2312'>数学上的直线是没有宽度、由无数个点构成的集合，显然，光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个象素中，确定最佳逼近该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作，这个过程称为用显示器绘制直线或<span
style='color:maroon'>直线的扫描转换</span>。 </span></p>
<p style='line-height:150%'><span lang=EN-US style='mso-ascii-font-family:楷体_GB2312;
mso-fareast-font-family:楷体_GB2312'> </span><span lang=EN-US
style='font-family:楷体_GB2312'> 由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。本节我们介绍一个象素宽直线绘制的三个常用算法：数值微分法（DDA）、中点画线法和Bresenham算法。</span></p>
<p><b><span lang=EN-US style='font-size:10.0pt;font-family:幼圆;color:gray'><a
href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/#2"><span
style='text-decoration:none;text-underline:none'><!--[if gte vml 1]><v:shape
id="_x0000_i1044" type="#_x0000_t75" alt="" href="#2" style='width:21pt;
height:37.5pt' o:button="t">
<v:imagedata src="./第二章%20光栅图形学.files/image002.gif" o:href="http://learn.bitsde.com/hep/jisuanjituxing/material/CG_Gif_pub_021.gif"/>
</v:shape><![endif]--><![if !vml]><img border=0 width=28 height=50
src="./第二章%20光栅图形学.files/image002.gif" v:shapes="_x0000_i1044"><![endif]></span></a></span><span
lang=EN-US><a
href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/CG_Txt_2_007.htm"><span
style='font-family:幼圆;color:gray'>数值微分(DDA)法</span></a><o:p></o:p></span></b></p>
<p style='line-height:200%'>设过端点<i><span lang=EN-US style='font-family:"Times New Roman"'>P</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>0</span></sub><span
lang=EN-US>(</span><i><span lang=EN-US style='font-family:"Times New Roman"'>x</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>0</span><span lang=EN-US> </span></sub><span
lang=EN-US>,</span><i><span lang=EN-US style='font-family:"Times New Roman"'>y</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>0</span></sub><span
lang=EN-US>)、</span><i><span lang=EN-US style='font-family:"Times New Roman"'>P</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span></sub><span
lang=EN-US>(</span><i><span lang=EN-US style='font-family:"Times New Roman"'>x</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span><span lang=EN-US> </span></sub><span
lang=EN-US>,</span><i><span lang=EN-US style='font-family:"Times New Roman"'>y</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span></sub><span
lang=EN-US>)的直线段为</span><i><span lang=EN-US style='font-family:"Times New Roman"'>L</span></i><span
lang=EN-US>(</span><i><span lang=EN-US style='font-family:"Times New Roman"'>P</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>0</span><span lang=EN-US> </span></sub><span
lang=EN-US>,</span><i><span lang=EN-US style='font-family:"Times New Roman"'>P</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span></sub><span
lang=EN-US>)，则直线段</span><i><span lang=EN-US style='font-family:"Times New Roman"'>L</span></i>的斜率<span
lang=EN-US><!--[if gte vml 1]><v:shape id="_x0000_i1045" type="#_x0000_t75"
alt="" style='width:405pt;height:34.5pt'>
<v:imagedata src="./第二章%20光栅图形学.files/image003.gif" o:href="http://learn.bitsde.com/hep/jisuanjituxing/Chapter2/CG_Gif_2_201.gif"/>
</v:shape><![endif]--><![if !vml]><img border=0 width=540 height=46
src="./第二章%20光栅图形学.files/image003.gif" v:shapes="_x0000_i1045"><![endif]>
</span><i><span lang=EN-US style='font-family:"Times New Roman"'>L</span></i>的起点<i><span
lang=EN-US style='font-family:"Times New Roman"'>P</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>0</span></sub>的横坐标<i><span
lang=EN-US style='font-family:"Times New Roman"'>x</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>0</span></sub>向<i><span
lang=EN-US style='font-family:"Times New Roman"'>L</span></i>的终点<i><span
lang=EN-US style='font-family:"Times New Roman"'>P</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span></sub>的横坐标<i><span
lang=EN-US style='font-family:"Times New Roman"'>x</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span></sub>步进，取步长<span
lang=EN-US>=1(个象素)，用</span><i><span lang=EN-US style='font-family:"Times New Roman"'>L</span></i>的直线方程<i><span
lang=EN-US style='font-family:"Times New Roman"'>y=kx+b</span></i>计算相应的<i><span
lang=EN-US style='font-family:"Times New Roman"'>y</span></i>坐标，并取象素点<span
lang=EN-US>(</span><i><span lang=EN-US style='font-family:"Times New Roman"'>x</span></i><span
lang=EN-US>,round(</span><i><span lang=EN-US style='font-family:"Times New Roman"'>y</span></i><span
lang=EN-US>))作为当前点的坐标。因为： </span></p>
<p style='line-height:200%'><span lang=EN-US> </span><i><span
lang=EN-US style='font-family:"Times New Roman"'>y<sub>i+</sub></span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span></sub><span
lang=EN-US> = </span><i><span lang=EN-US style='font-family:"Times New Roman"'>kx<sub>i+</sub></span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span></sub><i><span
lang=EN-US style='font-family:"Times New Roman"'>+b</span></i></p>
<p style='line-height:200%'><span lang=EN-US>
= </span><i><span lang=EN-US style='font-family:"Times New Roman"'>k</span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span></sub><i><span
lang=EN-US style='font-family:"Times New Roman"'>x<sub>i</sub></span></i><span
lang=EN-US>+</span><i><span lang=EN-US style='font-family:"Times New Roman"'>b</span></i><span
lang=EN-US>+</span><i><span lang=EN-US style='font-family:"Times New Roman"'>k</span></i><span
lang=EN-US style='font-family:Symbol'>D</span><i><span lang=EN-US
style='font-family:"Times New Roman"'>x</span></i></p>
<p style='line-height:200%'><span lang=EN-US>
= </span><i><span lang=EN-US style='font-family:"Times New Roman"'>y<sub>i</sub></span></i><span
lang=EN-US>+</span><i><span lang=EN-US style='font-family:"Times New Roman"'>k</span></i><span
lang=EN-US style='font-family:Symbol'>D</span><i><span lang=EN-US
style='font-family:"Times New Roman"'>x</span></i></p>
<p style='line-height:200%'><span lang=EN-US> 所以，当</span><span
lang=EN-US style='font-family:Symbol'>D</span><i><span lang=EN-US
style='font-family:"Times New Roman"'>x =</span></i><span lang=EN-US
style='font-family:"Times New Roman"'>1</span><span lang=EN-US>; </span><i><span
lang=EN-US style='font-family:"Times New Roman"'>y<sub>i+</sub></span></i><sub><span
lang=EN-US style='font-family:"Times New Roman"'>1</span><span lang=EN-US> </span></sub><span
lang=EN-US>= </span><i><span lang=EN-US style='font-family:"Times New Roman"'>y<sub>i</sub></span></i><span
lang=EN-US>+</span><i><span lang=EN-US style='font-family:"Times New Roman"'>k</span></i>。也就是说，当<i><span
lang=EN-US style='font-family:"Times New Roman"'>x</span></i>每递增<span
lang=EN-US>1，</span><i><span lang=EN-US style='font-family:"Times New Roman"'>y</span></i>递增<i><span
lang=EN-US style='font-family:"Times New Roman"'>k</span></i><span lang=EN-US>(即直线斜率)。根据这个原理，我们可以写出DDA画线算法程序。</span></p>
<p style='line-height:200%'><span lang=EN-US style='color:navy'><!--[if gte vml 1]><v:shape
id="_x0000_i1046" type="#_x0000_t75" alt="" style='width:10.5pt;height:10.5pt'>
<v:imagedata src="./第二章%20光栅图形学.files/image004.gif" o:href="http://learn.bitsde.com/hep/jisuanjituxing/material/CG_Gif_pub_031.gif"/>
</v:shape><![endif]--><![if !vml]><img border=0 width=14 height=14
src="./第二章%20光栅图形学.files/image004.gif" v:shapes="_x0000_i1046"><![endif]>DDA画线算法程序</span></p>
<p style='margin-top:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:
0cm'><span lang=EN-US style='font-size:10.0pt;color:purple'>void DDALine(int
x0,int y0,int x1,int y1,int color)</span></p>
<p style='margin-top:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:
0cm'><span lang=EN-US style='font-size:10.0pt;color:purple'>{ int x；</span></p>
<p style='margin-top:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:
0cm'><span lang=EN-US style='font-size:10.0pt;color:purple'> float dx,
dy, y, k；</span></p>
<p style='margin-top:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:
0cm'><span lang=EN-US style='font-size:10.0pt;color:purple'> dx = x1-x0；
dy=y1-y0；</span></p>
<p style='margin-top:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:
0cm'><span lang=EN-US style='font-size:10.0pt;color:purple'> k=dy/dx,；y=y0；</span></p>
<p style='margin-top:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:
0cm'><span lang=EN-US style='font-size:10.0pt;color:purple'> for (x=x0；x<
x1；x++)</span></p>
<p style='margin-top:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:
0cm'><span lang=EN-US style='font-size:10.0pt;color:purple'> { drawpixel
(x, int(y+0.5), color);</span></p>
<p style='margin-top:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:
0cm'><span lang=EN-US style='font-size:10.0pt;color:purple'>
y=y+k;</span></p>
<p style='margin-top:6.0pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:
0cm'><span lang=EN-US style='font-size:10.0pt;color:purple'> }</span><span
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -