📄 第二章 基本图形的生成与计算.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.ekany.com/wdg98/cg/contents/chapter2/les211.htm -->
<HTML><HEAD><TITLE>第二章 基本图形的生成与计算</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY><B>
<H1 align=justify><A name="第二章 基本图形的生成与计算"><FONT face=楷体_GB2312 size=6>第二章
基本图形的生成与计算</FONT></A></H1>
<H2 align=justify><A name="2.1 直线的生成算法"><FONT face=楷体_GB2312 size=5>2.1
直线的生成算法</FONT></A></B></H2>
<P align=justify><SPAN style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入数据。画一条从（x1, y1）到（x2,
y2）的直线，实质上是一个发现最佳逼近直线的象素序列，并填入色彩数据的过程。这个过程也称为直线光栅化。本节介绍在光栅显示器上直线光栅化的最常用的两种算法：直线DDA算法和直线Bresenham算法。</FONT></SUP></SPAN><B></P>
<H3 align=justify><A name="2.1.1 直线的DDA算法"><FONT face=楷体_GB2312 size=4>2.1.1
直线的DDA算法</FONT></A></B></H3>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>DDA是数字微分分析式（Digital Differential
Analyzer）的缩写。设直线之起点为（x1，y1），终点为（x2，y2），则斜率m为：</FONT></SPAN></SUP></P>
<P
style="MARGIN-TOP: 0px; FLOAT: none; MARGIN-BOTTOM: 0px; PADDING-BOTTOM: 0px; PADDING-TOP: 0px"
align=center><FONT face=楷体_GB2312 size=6>m</FONT><FONT face=楷体_GB2312 size=3>
</FONT><FONT face=楷体_GB2312 size=6>=</FONT><FONT face=楷体_GB2312 size=3>
</FONT><FONT face=楷体_GB2312 size=3><IMG height=45
src="第二章 基本图形的生成与计算.files/Image80.gif" width=89> </FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>直线中的每一点坐标都可以由前一点坐标变化一个增量（Dx, Dy）而得到，即表示为递归式：</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>xi+1=xi+Dx</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>yi+1=yi+Dy</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>并有关系：Dy = m ·
Dx</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>递归式的初值为直线的起点（x1,
y1），这样，就可以用加法来生成一条直线。具体方法是：</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify> </P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>图2.1.1
直线方向的8个象限</FONT></SPAN></SUP></P>
<P style="MARGIN-LEFT: 0px; TEXT-INDENT: 0px" align=center><FONT face=楷体_GB2312
size=3> <IMG
height=199 alt="2_1_1.gif (3249 bytes)" src="第二章 基本图形的生成与计算.files/2_1_1.gif"
width=259> </FONT></P>
<P align=justify><FONT face=楷体_GB2312
size=3>
图2.1.1</FONT></P>
<P><FONT face=楷体_GB2312 size=4>表2.1.1</FONT></P>
<TABLE cellSpacing=1 cellPadding=7 width=568 border=1>
<TBODY>
<TR>
<TD style="MARGIN-TOP: -1px; MARGIN-BOTTOM: -1px" vAlign=top width="25%">
<P><FONT face=楷体_GB2312 size=3>象限</FONT></P></TD>
<TD style="MARGIN-TOP: -1px; MARGIN-BOTTOM: -1px" vAlign=top
width="25%"><FONT size=3>
<P><FONT face=Arial>|dx|>|dy|?</FONT></FONT></P></TD>
<TD style="MARGIN-TOP: -1px; MARGIN-BOTTOM: -1px" vAlign=top width="25%">
<P><FONT face=Arial><FONT size=2>D </FONT><FONT
size=3>x</FONT></FONT></P></TD>
<TD style="MARGIN-TOP: -1px; MARGIN-BOTTOM: -1px" vAlign=top width="25%">
<P><FONT face=Arial><FONT size=2>D </FONT><FONT
size=3>y</FONT></FONT></P></TD></TR>
<TR>
<TD style="MARGIN-TOP: -1px; MARGIN-BOTTOM: -1px" vAlign=top
width="25%"><FONT size=3>
<P><FONT face=Arial>1a</FONT></P>
<P><FONT face=Arial>1b</FONT></P>
<P><FONT face=Arial>2a</FONT></P>
<P><FONT face=Arial>2b</FONT></P>
<P><FONT face=Arial>3a</FONT></P>
<P><FONT face=Arial>3b</FONT></P>
<P><FONT face=Arial>4a</FONT></P>
<P><FONT face=Arial>4b</FONT></FONT></P></TD>
<TD style="MARGIN-TOP: -1px; MARGIN-BOTTOM: -1px" vAlign=top width="25%">
<P><FONT face=Arial size=2>Ö </FONT></P>
<P><FONT face=Arial size=2>´ </FONT></P>
<P><FONT face=Arial size=2>Ö </FONT></P>
<P><FONT face=Arial size=2>´ </FONT></P>
<P><FONT face=Arial size=2>Ö </FONT></P>
<P><FONT face=Arial size=2>´ </FONT></P>
<P><FONT face=Arial size=2>Ö </FONT></P>
<P><FONT face=Arial size=2>´ </FONT></P></TD>
<TD style="MARGIN-TOP: -1px; MARGIN-BOTTOM: -1px" vAlign=top
width="25%"><FONT size=3>
<P><FONT face=Arial>1</FONT></P>
<P><FONT face=Arial>1/m</FONT></P>
<P><FONT face=Arial>-1</FONT></P>
<P><FONT face=Arial>-1/m</FONT></P>
<P><FONT face=Arial>-1</FONT></P>
<P><FONT face=Arial>-1/m</FONT></P>
<P><FONT face=Arial>1</FONT></P>
<P><FONT face=Arial>1/m</FONT></FONT></P></TD>
<TD style="MARGIN-TOP: -1px; MARGIN-BOTTOM: -1px" vAlign=top
width="25%"><FONT size=3>
<P><FONT face=Arial>m</FONT></P>
<P><FONT face=Arial>1</FONT></P>
<P><FONT face=Arial>m</FONT></P>
<P><FONT face=Arial>1</FONT></P>
<P><FONT face=Arial>-m</FONT></P>
<P><FONT face=Arial>-1</FONT></P>
<P><FONT face=Arial>-m</FONT></P>
<P><FONT face=Arial>-1</FONT></FONT></P></TD></TR></TBODY></TABLE><FONT face=宋体
size=3>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify></FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>按照直线从（x1，y1）到（x2，y2）的方向不同，分为8个象限（图2.1.1）。对于方向在第1a象限内的直线而言，D x=1，D
y=m。对于方向在第1b象限内的直线而言，取值Dy=1，Dx=1/m。各象限中直线生成时Dx,
Dy的取值列在表2.1.1之中。</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>研究表中的数据，可以发现两个规律：</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>1、当|dx|>|dy|时</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>|D x|=1, |D
y|=m；</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>否则：</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>Dx=1/m，|Dy|=1</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> </FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>2、Dx, Dy的符号与dx,
dy的符号相同。</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>这两条规律可以导致程序的简化。由上述方法写成的程序如程序2.1.1所示。其中steps变量的设置，以及D x=dx/steps; D
y=dy/steps等语句，正是利用了上述两条规律，使得程序变得简练。</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。</FONT></SPAN></SUP></P>
<BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE><FONT face=System></FONT>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>dda_line (xa, ya, xb, yb, c)</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int xa, ya, xb, yb, c;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>{</FONT></P>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>float delta_x, delta_y, x, y;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int dx, dy, steps, k;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>dx=xb-xa;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>dy=yb-ya;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>if (abs(dx)>abs(dy)) steps=abs(dx);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>else steps=abs (dy);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>delta_x=(float)dx / (float)steps;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>delta_y=(float)dy / (float)steps;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>x=xa;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>y=ya;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(x, y, c);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>for (k=1; k<=steps; k++)</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>{</FONT></P>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>x+=delta_x;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>y+=delta_y;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(x, y, c);</FONT></P></BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>}</FONT></P></BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> }</FONT><FONT face=宋体></P></FONT>
<BLOCKQUOTE>
<P align=justify><FONT face=楷体_GB2312>程序2.1.1
DDA直线生成程序</FONT></P></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE>
<P><FONT
face=楷体_GB2312> </FONT>
</P>
<P><A href="http://www.ekany.com/wdg98/cg/contents/chapter1/les111.htm"><FONT
face=楷体_GB2312><上一节〉</FONT></A><FONT face=楷体_GB2312> <A
href="http://www.ekany.com/wdg98/cg/contents/chapter2/les212.htm">〈下一节〉</A>
<A
href="http://www.ekany.com/wdg98/cg/tutorial/chapter2/lesson2-1.htm">〈返回〉</A></FONT></P>
<P> </P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -