2.1.1 生成直线的DDA算法
数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。
一、直线DDA算法描述：
设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得
可通过计算由x方向的增量△x引起y的改变来生成直线：
也可通过计算由y方向的增量△y引起x的改变来生成直线：
式(2－2)至(2－5)是递推的。
二、直线DDA算法思想：
选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大)，取该方向上的增量为一个象素单位(△x=1)，然后利用式(2－1)计算另一个方向的增量(△y=△x·m=m)。通过递推公式(2－2)至(2－5)，把每次计算出的(x i+1，y i+1)经取整后送到显示器输出，则得到扫描转换后的直线。
之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。
另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。
三、直线DDA算法实现：
1、已知直线的两端点坐标：(x1，y1)，(x2，y2)
2、已知画线的颜色：color
3、计算两个方向的变化量：dx=x2－x1
dy=y2－y1
4、求出两个方向最大变化量的绝对值：
steps=max(|dx|，|dy|)
5、计算两个方向的增量(考虑了生成方向)：
xin=dx/steps
yin=dy/steps
6、设置初始象素坐标：x=x1,y=y1
7、用循环实现直线的绘制：
for(i=1；i<=steps；i++)
{ putpixel(x，y，color)；/*在(x，y)处，以color色画点*/
x=x+xin；
y=y+yin；
}
五、直线DDA算法特点：
该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。
//@brief 浮点数转整数的宏
实现代码
#define FloatToInteger(fNum)
((fNum>0)?static_cast
/*!
* @brief DDA画线函数
*
* @param pDC [in]窗口DC
* @param BeginPt [in]直线起点
* @param EndPt [in]直线终点
* @param LineCor [in]直线颜色
* @return 无
*/
void CDrawMsg::DDA_DrawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREF LineCor)
{
l ong YDis = (EndPt.y - BeginPt.y);
l ong XDis = (EndPt.x-BeginPt.x);
l ong MaxStep = max(abs(XDis),abs(YDis)); // 步进的步数
f loat fXUnitLen = 1.0f; // X方向的单位步进
f loat fYUnitLen = 1.0f; // Y方向的单位步进
f YUnitLen = static_cast
f XUnitLen = static_cast
// 设置起点像素颜色
p DC->SetPixel(BeginPt.x,BeginPt.y,LineCor);
f loat x = static_cast
f loat y = static_cast
// 循环步进
f or (lon
g i = 1;i<=MaxStep;i++)
{
x = x + fXUnitLen;
y = y + fYUnitLen;
pDC->SetPixel(FloatToInteger(x),FloatToInteger(y),LineCor);
}
}
2.1.2 生成直线的B resenham算法
从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。
在生成直线的算法中，B resenham算法是最有效的算法之一。B resenham算法是一种基于误差判别式来生成直线的方法。
一、直线Bresenham算法描述：
它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一个象素。
我们首先讨论m=△y/△x，当0≤m≤1且x1 有两种B resenham算法思想，它们各自从不同角度介绍了B resenham算法思想，得出的误差判别式都是一样的。 二、直线B resenham算法思想之一： 由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(x i，y i)，它是直线上点(x i，y i)的最佳近似，并且x i=x i(假设m<1），如下图所示。那么，直线上下一个象素点的可能位置是(x i+1，y i)或(x i+1，y i+1)。 由图中可以知道，在x=x i+1处，直线上点的y值是y=m(x i+1)+b，该点离象素点(x i+1，y i)和象素点(x i+1，y i+1)的距离分别是d1和d2： 这两个距离差是 我们来分析公式(2-10)： (1)当此值为正时，d1>d2，说明直线上理论点离(x i+1，y i+1)象素较近，下一个象素点应取(x i+1，y i+1)。 (2)当此值为负时，d1 (3)当此值为零时，说明直线上理论点离上、下两个象素点的距离相等，取哪个点都行，假设算法规定这种情况下取(x i+1，y i+1)作为下一个象素点。 因此只要利用(d1-d2)的符号就可以决定下一个象素点的选择。为此，我们进一步定义一个新的判别式： 式(2-11)中的△x=(x2-x1)>0，因此p i与(d1-d2)有相同的符号； 这里△y=y2-y1，m=△y/△x；c=2△y+△x(2b-1)。 下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c。 将式(2-11)中的下标i改写成i+1，得到： 将式(2-12)减去(2-11)，并利用x i+1=x i+1，可得： 再假设直线的初始端点恰好是其象素点的坐标，即满足： 由式(2-11)和式(2-14)得到p1的初始值： 这样，我们可利用误差判别变量，得到如下算法表示： 从式(2-16)可以看出，第i+1步的判别变量p i+1仅与第i步的判别变量p i、直线的两个端点坐标分量差△x和△y有关，运算中只含有整数相加和乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。 三、直线B resenham算法思想之二： 由于象素坐标的整数性，数学点(x i，y i)与所取象素点(x i，y ir)间会引起误差(εi)，当x i列上已用象素坐标(x i，y ir)表示直线上的点(x i，y i)，下一直线点B(x i+1，y i+1)，是取象素点C(x i+1，y ir )，还是D(x i＋1，y(i+1)r)呢？ 设A为CD边的中点，正确的选择： 若B点在A点上方，选择D点；否则，选C点。 用误差式描述为： ε(x i+1)=BC-AC=(y i+1-y ir)-0.5 (2－8') 求递推公式： ε(x i+2)=(y i+2-y(i+1)r)-0.5 = y i+1+m-y(i+1)r-0.5 (2－9') 当ε(x i+1)≥0时，选D点，y(i+1)r = y ir+1 ε(x i+2)= y i+1+m-y ir-1-0.5=ε(x i+1)+m-1 (2－10') 当ε(x i+1)﹤0时，选C点，y(i+1)r = y ir ε(x i+2)= y i+1+m－y ir-0.5=ε(x i+1)+m(2－11') 初始时： ε(x s+1)=BC-AC=m-0.5 (2－12') 为了运算中不含实型数，同时不影响不等式的判断，将方程两边同乘一正整数。令方程两边同乘2·Δx，即d=2·Δx·ε，则： 初始时： 递推式： 实现代码 void Bresenhamline (int x0,int y0,int x1, int y1,int color) { int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; i<=dx; i++) { drawpixel (x, y, color); x=x+1，e=e+k; if (e>=0) { y++, e=e-1;} } } 或者将e扩大2dx倍； void Bresenhamline (int x0,int y0,int x1, int y1,int color) { int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-dx, x=x0, y=y0; for (i=0; i<=dx; i++) { drawpixel (x, y, color); x=x+1，e=e+2dy; if (e>=0) { y++, e=e-2dx;} } } 四、直线B resenham算法实现： 条件：0≤m≤1且x1 1、输入线段的两个端点坐标和画线颜色：x1，y1，x2，y2，color； 2、设置象素坐标初值：x=x1，y=y1； 3、设置初始误差判别值：p=2·Δy-Δx； 4、分别计算：Δx=x2-x1、Δy=y2-y1； 5、循环实现直线的生成： for(x=x1；x<=x2；x++) { putpixel(x,y,color) ； if(p>=0) { y=y+1； p=p+2·(Δy-Δx)； } else { p=p+2·Δy； } } 五、直线B resenham算法完善： 现在我们修正(2-16)公式，以适应对任何方向及任何斜率线段的绘制。如下图所示，线段的方向可分为八种，从原点出发射向八个区。由线段按图中所示的区域位置可决定x i+1和y i+1的变换规律。 容易证明：当线段处于①、④、⑧、⑤区时，以|△x|和|△y|代替前面公式中的△x和△y，当线段处于②、③、⑥、⑦区时，将公式中的|△x|和|△y|对换，则上述两公式仍有效。 在线段起点区分线段方向 七、直线B resenham算法特点： 由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。 2.2.2 中点算法生成圆 中点画圆算法在一个方向上取单位间隔，在另一个方向的取值由两种可能取值的中点离圆的远近而定。实际处理中，用决策变量的符号来确定象素点的选择，因此算法效率较高。 一、中点画圆算法描述 设要显示圆的圆心在原点(0，0)，半径为R，起点在(0，R)处，终点在(，)处，顺时针生成八分之一圆，利用对称性扫描转换全部圆。 为了应用中点画圆法，我们定义一个圆函数 任何点(x，y)的相对位置可由圆函数的符号来检测： 如下图所示，图中有两条圆弧A和B，假定当前取点为P i(x i，y i)，如果顺时针生成圆，那么下一点只能取正右方的点E(x i+1，y i)或右下方的点SE(x i+1，y i-1)两者之一。 中点画线算法 假设M是E和SE的中点，即，则： 1、当F(M)<0时，M在圆内(圆弧A)，这说明点E距离圆更近，应取点E作为下一象素点； 2、当F(M)>0时，M在圆外(圆弧B)，表明SE点离圆更近，应取SE点； 3、当F(M)=0时，在E点与SE点之中随便取一个即可，我们约定取SE点。 二、中点画圆算法思想 因此，我们用中点M的圆函数作为决策变量d i，同时用增量法来迭代计算下一个中点M 的决策变量d i+1。 下面分两种情况来讨论在迭代计算中决策变量d i+1的推导。 1、见图（a），若d i<0，则选择E点，接着下一个中点就是，这时新的决策变量为： （a）(d i<0) 中点画线算法 式(2－22)减去(2－21)得： 2、见图（b），若d i≥0，则选择SE点，接着下一个中点就是，这时新的决策变量为： （b）(d i≥0) 中点画线算法 式(2－24)减去(2－21)得： d i+1=d i+2(x i-y i)+5 (2－25) 我们利用递推迭代计算这八分之一圆弧上的每个点，每次迭代需要两步处理：（1）用前一次迭代算出的决策变量的符号来决定本次选择的点。 （2）对本次选择的点，重新递推计算得出新的决策变量的值。 剩下的问题是计算初始决策变量d0，如下图所示。对于初始点(0，R)，顺时针生成八分 之一圆，下一个中点M的坐标是，所以： (2－26 生成圆的初始条件和圆的生成方向 三、中点画圆算法实现 1、输入：圆半径r、圆心(x0，y0)； 2、确定初值：x=0，y=r、d=5/4-r； 3、While(x<=y) { ·利用八分对称性，用规定的颜色color画八个象素点(x，y)； ·若d≥0 { y=y-1； d=d+2(x-y)+5)； } 否则 d=d+2x+3； ·x=x+1； } 五、中点画圆算法完善 在上述算法中，使用了浮点数来表示决策变量d。为了简化算法，摆脱浮点数，在算法中全部使用整数，我们使用e=d-1/4代替d。显然，初值d=5/4-r对应于e=1-r。决策变量d<0对应于e<-1/4。算法中其它与d有关的式子可把d直接换成e。又由于e的初值为整数，且在运算过程中的迭代值也是整数，故e始终是整数，所以e<-1/4等价于e<0。因此，可以写出完全用整数实现的中点画圆算法。 要求：写出用整数实现的中点画圆算法程序，并上机调试，观看运行结果。 六、中点画圆算法程序 2.2.3 正负算法生成圆 正负法是利用平面曲线将平面划分成正负区域，对当前点产生的圆函数进行符号判别，利用负反馈调整以决定下一个点的产生来直接生成圆弧。 一、正负画圆算法描述 设要显示圆的圆心在原点(0，0)，半径为R，初始点的坐标为(0，R)，顺时针生成八分之一圆，令：F(x，y)=x2+y2-R2 则圆的方程为： 当点(x，y)在圆内时，则F(x，y)<0； 当点(x，y)在圆外时，则F(x，y)>0； 当点(x，y)在圆上时，则F(x，y)=0； 二、正负画圆算法思想 现以下图的AB弧为例，来说明正负画圆法(顺时针生成圆)。 假设当前点为P i(x i，y i)，取下一个点P i+1(x i+1，y i+1)的原则是： 1、当F(x i，y i)≤0时：取x i+1= x i+1，y i+1= y i。即向右走一步，从圆内走向圆外。对应图(a)中的从P i到P i+1。 2、当F(x i，y i)>0时：取x i+1= x i，y i+1= y i-1。即向下走一步，从圆外走向圆内。对应图 (b)中的从P i到P i+1。 由于向圆内或向圆外走取决于F(x i，y i)的正负，因此称为正负法。 下面分两种情况求出F(x i，y i)的递推公式： (1) 当F(x i，y i)≤0时，向右走，取x i+1=x i+1，y i+1=y i，则 F(x i+1，y i+1) =F(x i+1，y i) =(x i+1)2+y i2-R2 (2-28) =(x i2+y i2-R2)+2x i+1 = F(x i，y i)+2x i+1 (2) 当F(x i，y i)>0时，向下走，取x i+1=x i，y i+1=y i-1，则 F(x i+1，y i+1) =F(x i，y i-1) =x i2+(y i-1)2-R2 (2-9) =(x i2+y i2-R2)-2y i+1 = F(x i，y i)-2y i+1 初始时，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30) 公式(2-28)、(2-29)和(2-30)就构成正负画圆算法的核心。 给象素坐标(x，y)及F赋初始值后，进入循环画点； 画点后，根据F的符号进行F值的递推和下一个点的获取，直到x>y为止。 同前面介绍的一样，利用圆的八分对称性，循环一次，画八个点。 三、正负画圆算法实现 注意：初值不同、圆的生成方向不同时，当前点和下一个点的获取原则是不同的，见下图。 例如，初始点(R，0)，逆时针生成圆，从图（b）可知： 若当前点P i在圆内，则下一点P i+1(x i，y i+1)，即向上走一步； 若当前点P i在圆外，则下一点P i+1(x i-1，y i)，即向左走一步； (a) 顺时针生成圆(b) 逆时针生成圆 五、正负画圆算法特点 物理意义清楚，程序中只含整数运算，因此算法速度快。 六、正负画圆算法程序 2.3 区域填充 前面介绍的直线和圆都属于线划图，然而，光栅显示的一个重要特点是能进行面着色，区域填充就是在一个闭合区域内填充某种颜色或图案。 区域填充一般分两类：多边形填充和种子填充。 一、多边形填充 1、填充条件 多边形的顶点序列(P i，i=0，1，…，n)、填充色。 2、多边形内点的判别准则 对多边形进行填充，关键是找出多边形内的象素。在顺序给定多边形顶点坐标的情况下，如何判明一个象素点是处于多边形的内部还是外部呢？ 从测试点引出一条伸向无穷远处的射线(假设是水平向右的射线)，因为多边形是闭合的，那么： 若射线与多边形边界的交点个数为奇数时，则该点为内点(例：图中测试点4引出的射线)； 反之，交点个数为偶数时，则该点为外点。(例：测试点2引出的射线)。 多边形内点的判别准则和奇异点 3、奇异点的处理： 上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它们应该是内点，但实际上却是外点。 而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。 多边形内点的判别准则和奇异点 综合以上情况，我们将多边形的顶点分为两大类： (1) 局部极值点：如图中的点P1、P2、P4和P6。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的同一侧。 (2)非极值点：如图中的点P3、P5。对于这些点来说，进入该点的边线和离开该点的边线位于过该点扫描线的两侧。 处理奇异点规则： （1）对于局部极值点，应看成两个点； （2）对于非极值点，应看成一个点。 4、逐点判别算法步骤： (1)求出多边形的最小包围盒：从P i(x i，y i)中求极值，x min、y min、x max、y max。 (2)对包围盒中的每个象素引水平射线进行测试。 (3)求出该射线与多边形每条边的有效交点个数。 (4)如果个数为奇数：该点置为填充色。 (5)否则：该点置为背景色。 逐点判别算法虽然简单，但不可取，原因是速度慢。它割断了各象素之间的联系，孤立地考虑问题，由于要对每个象素进行多次求交运算，求交时要做大量的乘除运算，从而影响了填充速度。 二、种子填充 种子填充是将区域内的一点(种子)赋予给定的颜色，然后将这种颜色扩展到整个区域内的过程。 1、填充条件 区域内一点的坐标即种子坐标、边界色、填充色。 2、连通方式 区域是互相连通着的象素的集合，连通方式可分为四连通和八连通。 四连通：从区域内一点出发，可通过四个方向：上、下、左、右到达该区域内部的任意象素。 八连通：区域内部从一个象素到达另一个象素的移动路径，除了上、下、左、右四个方向外，还允许沿着对角线方向。 注意： （1）八连通区域中，既然区域内的两个象素可以通过对角线相通，那么，区域边界上的象素则不能通过对角线相连，否则填充就会溢出到区域外，因此，八连通区域的边界线必须是四连通的，见下图(a)； （2）而四连通区域，其边界象素是四连通和八连通的都可以，见下图(b)。 (a) 八连通区域四连通边界(b) 四连通区域八连通(或四连通)边界 3、内点(x,y)的检测条件 (1) if(getpixel(x,y)!=边界色&& getpixel(x,y)!=填充色) (2) if(getpixel(x,y)!=背景色) 这两个条件任何一个都可以用来检测象素点(x,y)是不是尚未填充。推荐使用条件(1)进行 象素点检测。 2.3.1 边相关扫描线多边形填充算法 2.3.2 扫描线种子填充算法 2.3.3 边标志填充算法 2.3.4 图案填充 2.3.1 边相关扫描线多边形填充算法 边相关扫描线填充算法属于多边形填充类。它比逐点判别算法速度提高很多，是一种较经典的多边形填充算法。 该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进行处理。 一、边相关扫描线填充算法描述 扫描线的相关性：某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变。见下图(a)。 边的相关性：由于相邻扫描线上的交点是与多边形的边线相关的。对同一条边，前一条扫描线y i与该边的交点为x i，而后一条扫描线y i+1=y i+1与该边的交点则为x i+1=x i+1/m，利用这种相关性可以省去大量的求交运算。见下图(b)所示。 (a) 扫描线的相关性(b) 边的相关性 边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。 1、边表（ET：Edge Table） 用来对除水平边外的所有边进行登记，来建立边的记录。边的记录定义为： 扫描线y 对应的ET表 第一项：某边的最大y值（y max）。注意要进行奇异点处理：对于非极值点应该y max=y max-1。 第二项：某边的最小的y对应的x值。 第三项：某边斜率的倒数:1/m。 第四项：指针。用来指向同一条扫描线相交的其它边，如果其它边不存在，则该项置空。 2、活动边表（AET：Active Edge Table） ET表建立以后，就可以开始扫描转换了。对不同的扫描线，与之相交的边线也是不同的，当对某一条扫描线进行扫描转换时，我们只需要考虑与它相交的那些边线，为此需要建立一个只与当前扫描线相交的边记录链表，称之为活动边表。 二、边相关扫描线填充算法思想 1、根据给出的多边形顶点坐标，建立ET表； 求出顶点坐标中最大y值y max和最小y值y min。 2、初始化AET表指针，使它为空。 3、使用扫描线的y j值作为循环变量，使其初值为y min。 对于循环变量y j的每一整数值，重复作以下事情，直到y j大于y max，或ET表与AET 表都为空为止： (1) 如果ET表中y j桶非空，则将y j桶中的全部记录合并到AET表中。 (2) 对AET表链中的记录按x的大小从小到大排序。 (3) 依次取出AET表各记录中的x i坐标值，两两配对填充，即将每对x i之间的象素填上所要求的颜色。 (4) 如果AET表中某记录的y max=y j，则删除该记录。 (5) 对于仍留在AET表中的每个记录，用x i+1/m代替x i进行修改，这就是该记录的边线与下一条扫描线y j+1的交点。 (6) 使y j加1，以便进入下一轮循环。 裁剪算法详解 在使用计算机处理图形信息时，计算机部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之，哪些落在显示区之外，以便只显示落在显示区的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。 (a)裁剪前 (b) 裁剪后 图1.1 多边形裁剪 1直线段裁剪 直线段裁剪算法比较简单，但非常重要，是复杂图元裁剪的基础。因为复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。常 用的线段裁剪方法有三种：Cohen-Sutherland,中点分割算法和梁友栋－barskey 算法。 1.1 Cohen-Sutherland裁剪 该算法的思想是：对于每条线段P1P2分为三种情况处理。（1）若P1P2完全在窗口，则显示该线段P1P2简称“取”之。（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 为使计算机能够快速判断一条直线段与窗口属何种关系，采用如下编码方法。延长窗口的边，将二维平面分成九个区域。每个区域赋予4位编码CtCbCrCl.其中各位编码的定义如下： 图1.2 多边形裁剪区域编码图5.3线段裁剪 裁剪一条线段时，先求出P1P2所在的区号code1,code2。若code1=0,且code2=0，则线段P1P2在窗口，应取之。若按位与运算code1&code2≠0，则说明两个端点同在窗口的上方、下方、左方或右方。可判断线段完全在窗口外，可弃之。否则，按第三种情况处理。求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。在对另一段重复上述处理。在实现本算法时，不必把线段与每条窗口边界依次求交，只要按顺序检测到端点的编码不为0，才把线段与对应的窗口边界求交。 Cohen-Sutherland裁减算法 #define LEFT 1 #define RIGHT 2 #define BOTTOM 4 CRC算法及C实现 学习体会2008-09-20 15:21:13 阅读161 评论0 字号：大中小订 阅 一、CRC算法原理 CRC校验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。 16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以）后，再除以一个多项式，最后所得到的余数既是 CRC码。 假设数据传输过程中需要发送15位的二进制信息 g=101001110100001，这串二进制码可表示为代数多项式g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1，其中g中第k位的值，对应g(x)中x^k的系数。将g(x)乘以x^m，既将g后加m个0，然后除以m阶多项式h(x)，得到的(m-1)阶余项 r(x)对应的二进制码r就是 CRC编码。 h(x)可以自由选择或者使用国际通行标准，一般按照h(x)的阶数m，将CRC算法称为CRC-m，比如CRC-32、CRC-64等。国际通行标准可 以参看 https://www.doczj.com/doc/5c15114214.html,/wiki/Cyclic_redundancy_check g(x)和h(x)的除运算，可以通过g和h做xor（异或）运算。比如将 11001与10101做xor运算： 明白了xor运算法则后，举一个例子使用CRC-8算法求101001110100001的效验码。CRC-8标准的h(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1，既h是9位的二进制串111010101。 计算机图形学上机实验报告 橡皮筋技术 计算机科学与技术学院 姓名： xxx 完成日期： 2010-12-7 实验：橡皮筋技术 一、实验目的与要求 实验目的：1.学会使用OpenGL，进一步掌握基本图形的绘制方法， 2.理解glut程序框架 3.理解窗口到视区的变换 4.理解OpenGL实现动画的原理 5.学会基于鼠标和键盘实现交互的实现方法 二、实验内容： 利用OpenGL实现折线和矩形的皮筋绘制技术，并采用右键菜单实现功能的选择 实现方法：1.橡皮筋技术的实现采用双缓存技术，绘制图形时分别绘制到两个缓存，交替显示。 2.右键菜单控制选择绘制折线还是绘制矩形，实现方法：通过菜单注册函数创建一个弹出式菜单，然后使用函数加入菜单项，最后使用函数讲菜单与鼠标右键关联起来，GLUT通过为菜单提供一个整数标识符实现对菜单的管理，在main主函数通过标识符用函数指定对应的菜单为当前的菜单。 2. 折线的橡皮筋绘制技术实现：鼠标所在位置确定一个点，移动鼠标时，每次移动时将点的信息保存在数组中，连接当前鼠标所在点和前一个点的直线段。 3.矩形的橡皮筋绘制技术：每个矩形由两个点唯一确定，鼠标当前点为第一个点，移动鼠标确定第二个点的位置，由这两点的坐标绘制出举行的四条边（直线段），矩形即绘制完毕。 三、实验结果 图鼠标右键菜单 图绘制矩形 四、体会 1> 经过这次实验,逐步对opengl软件有了一定的了解,而且对于理论知识有了很好的巩固,并非仅仅会C语言就能编写画图程序,gult程序有自己特殊的框架与实现过程.在这次试验中,虽然没有完全理解其原理,但在一定程度上已经为我们今后的学习应用打下了基础. 2>初步了解了如何在OpenGL实现基本的绘图功能，以及鼠标和键 盘灯交互设备的实现，还有如何由初始生成元绘制分形物体。在这个过 程中遇到了很多问题，程序的调试也是困难重重，通过自己看书思考和 老师、同学的帮助最终完成了程序的调试，在这一过程中加深了对理论 知识的理解，以及理清了理论到实践转换的一点点思路，再一次体会到 理论与实践的结合的重要性，今后要多多提高提高动手能力。 #include 三种常用的CRC16校验算法的C51程序的优化2009-10-10 09:34:17| 分类：技术知识| 标签：|字号大 CRC校验又称为循环冗余校验，是数据通讯中常用的一种校验算法。它可以有效的判别出数据在传输过程中是否发生了错误，从而保障了传输的数据可靠性。 CRC校验有多种方式，如：CRC8、CRC16、CRC32等等。在实际使用中，我们经常使用CRC16校验。CRC16校验也有多种，如：1005多项式、1021多项式（CRC-ITU）等。在这里我们不讨论CRC算法是怎样产生的，而是重点落在几种算法的C51程序的优化上。 计算CRC校验时，最常用的计算方式有三种：查表、计算、查表＋计算。一般来说，查表法最快，但是需要较大的空间存放表格；计算法最慢，但是代码最简洁、占用空间最小；而在既要求速度，空间又比较紧张时常用查表＋计算法。 下面我们分别就这三种方法进行讨论和比较。这里以使用广泛的51单片机为例，分别用查表、计算、查表＋计算三种方法计算1021多项式（CRC-ITU）校验。原始程序都是在网上或杂志上经常能见到的，相信大家也比较熟悉了，甚至就是正在使用或已经使用过的程序。 编译平台采用Keil C51 7.0，使用小内存模式，编译器默认的优化方式。 常用的查表法程序如下，这是网上经常能够看到的程序范例。因为篇幅关系，省略了大部分表格的内容。 code unsigned int Crc1021Table[256] = { 0x0000, 0x1021, 0x2042, 0x3063,... 0x1ef0 }; unsigned int crc0(unsigned char *pData, unsigned char nLength) { unsigned int CRC16 = 0; 实验报告 实验名称：三维分形算法 姓名：陈怡东 学号：09008406 程序使用说明： 程序打开后会呈现出3次分形后的四面体，因为考虑到观察效果的清晰所以就用了3次分形作为演示。 与用户的交互： 1键盘交互：分别按下键盘上的数字键1，2,3,4可以分别改变四面体的4个面的颜色。 按下字母c（不区别大小写）可以改变视图函数，这里循环切换3种视图 函数：glOrtho，glFrustum，gluPerspective，但是改变视图函数后要窗口形状变化后才能显现出来 按下字母键q（不区别大小写）可以退出程序 2鼠标交互：打开后在绘图的区域按下鼠标左键不放便可以拖动图形的视角，这里为了展现图形的3D效果因此固定了其中一点不放，这样就可以看到3D的效果。 鼠标右击则有弹出菜单显示，其中改变颜色则是同时改变4个面的颜色，本程序中运用了8组配色方案。 改变视图函数也是上述的3种函数，这里的效果立刻显现，但是还有很多问题达不到所要的效果，希望老师能帮忙解决一下。 设计思路： 分形算法：把四面体细分成更小的四面体，先找出其6个棱的中点并连接起来，这样就在4个顶点处各有一个小的四面体，原来四面体中剩下的部分应当去掉。仿效二维的生成方法，我们对保留的四个小四面体进行迭代细分。这样细分结束后通过绘制4个三角形来绘制每一个剩下的四面体。 交互的实现：键盘交互，即通过对按键的响应写上响应函数实现对视图和颜色的改变。 鼠标交互：通过对鼠标左右按键的 实现： 该部分只做了必要的介绍，具体实现见代码（附注释） 分形算法：void tetra(GLfloat *a,GLfloat *b,GLfloat *c,GLfloat *d)函数实现的是绘制四面体并且给四个面绘上不同的颜色。以区别开来，函数的实现细节见代码，有注释介绍。 void triangle3(GLfloat *a,GLfloat *b,GLfloat *c)函数用来绘制每个平面细分后的三角形。其中顶点设置为3维坐标glVertex3fv(a); void divide_tetra(GLfloat *a,GLfloat *b,GLfloat *c,GLfloat *d,int m)细分四面体的函数实现。前四个参数为传入点的坐标，最后参数m则是细分次数。先计算六个中点的坐标mid[1][j]=(a[j]+c[j])/2;3次循环则是对x，y，z三个坐标的一次计算，然后再递归调用绘制4个小四面体。 然后是显示回调函数void mydisplay3FX();这跟程序模板差不多不做过多介绍。 分形算法中必要重要的一点是隐藏面的消除。即书上2.10.3介绍的内容。对对象进行排 实验二图形的几何变换的实现算法 班级 08 信计 学号 59 姓名 _____ 分数 _____ 一、 实验目的和要求： 1、 掌握而为图形的基本几何变换，如平移，旋转，缩放，对称，错切变换；＜ 2、 掌握OpenG 冲模型变换函数，实现简单的动画技术。 3、 学习使用OpenGL 生成基本图形。 4、 巩固所学理论知识，加深对二维变换的理解，加深理解利用变换矩阵可 由简单图形得到复杂图形。加深对变换矩阵算法的理解。 编制利用旋转变换绘制齿轮的程序。编程实现变换矩阵算法，绘制给出形体 的三视图。调试程序及分析运行结果。要求每位学生独立完成该实验，并上传实 验报告。 二、 实验原理和内容： .原理： 图像的几何变换包括：图像的空间平移、比例缩放、旋转、仿射变换和图像插值。 图像几何变换的实质：改变像素的空间位置，估算新空间位置上的像素值。 图像几何变换的一般表达式：［u,v ］=［X （x, y ）,Y （x, y ）］，其中，［u,v ］为变换后图像 像素的笛卡尔坐标， ［x, y ］为原始图像中像素的笛卡尔坐标。这样就得到了原始图像与变 换后图像的像素的对应关系。 平移变换：若图像像素点（x, y ）平移到（x x 。，y ■ y 。），则变换函数为 u = X （x, y ） =x 沟， v 二丫（x, y ） = y ■ y 。，写成矩阵表达式为: 比例缩放：若图像坐标 （x,y ）缩放到（S x ，s y ）倍，则变换函数为: S x ,S y 分别为x 和y 坐标的缩放因子，其大于1表示放大, 小于1表示缩小。 旋转变换：将输入图像绕笛卡尔坐标系的原点逆时针旋转 v 角度，则变换后图像坐标为: u COST 内容： :u l :Sx k ；0 其中，x 0和y 0分别为x 和y 的坐标平移量。 其中, CRC算法与实现bhw98 摘要: 本文首先讨论了CRC的代数学算法，然后以常见的CRC-ITU为例，通过硬件电路的实现，引出了比特型算法，最后重点介绍了字节型快速查表算法，给出了相应的C 语言实现。 关键词: CRC, FCS, 生成多项式, 检错重传 引言 CRC的全称为Cyclic Redundancy Check，中文名称为循环冗余校验。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。实际上，除数据通信外，CRC在其它很多领域也是大有用武之地的。例如我们读软盘上的文件，以及解压一个ZIP文件时，偶尔会碰到“Bad CRC”错误，由此它在数据存储方面的应用可略见一斑。 差错控制理论是在代数理论基础上建立起来的。这里我们着眼于介绍CRC的算法与实现，对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理，可以阅读有关资料。 利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。 1 代数学的一般性算法 在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如1100101 表示为 1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即x6+x5+x2+1。 设编码前的原始信息多项式为P(x)，P(x)的最高幂次加1等于k；生成多项式为G(x)，G(x)的最高幂次等于r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。 发送方编码方法：将P(x)乘以xr(即对应的二进制码序列左移r位)，再除以G(x)，所得余式即为R(x)。用公式表示为 T(x)=x r P(x)+R(x) 接收方解码方法：将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说 实验一 实验目的：生成彩色立方体 实验代码：//ColorCube1.java import java.applet.Applet; //可以插入html import java.awt.BorderLayout; //窗口采用BorderLayout方式布局import com.sun.j3d.utils.applet.MainFrame; //application import com.sun.j3d.utils.geometry.ColorCube;//调用生成ColorCube的Utility import com.sun.j3d.utils.geometry.Primitive; import com.sun.j3d.utils.universe.*; //观测位置的设置 import javax.media.j3d.*; //核心类 import javax.vecmath.*; //矢量计算 import com.sun.j3d.utils.behaviors.mouse.*; public class ColorCube1 extends Applet { public BranchGroup createSceneGraph() { BranchGroup objRoot=new BranchGroup(); //BranchGroup的一个对象objRoot（放置背景、灯光）BoundingSphere bounds=new BoundingSphere(new Point3d(0.0,0.0,0.0),100.0);//有效范围 TransformGroup objTrans=new TransformGroup(); objTrans.setCapability(TransformGroup.ALLOW_TRANSFORM_WRITE); objTrans.setCapability(TransformGroup.ALLOW_TRANSFORM_READ); objRoot.addChild(objTrans); MouseRotate behavior = new MouseRotate(); behavior.setTransformGroup(objTrans); objRoot.addChild(behavior); behavior.setSchedulingBounds(bounds); MouseZoom behavior2 = new MouseZoom(); behavior2.setTransformGroup(objTrans); objRoot.addChild(behavior2); behavior2.setSchedulingBounds(bounds); MouseTranslate behavior3 = new MouseTranslate(); behavior3.setTransformGroup(objTrans); objRoot.addChild(behavior3); behavior3.setSchedulingBounds(bounds); 一、bresenham算法画直线 #include } void myinit() { glClearColor(0.8,1.0,1.0,1.0); glColor3f(0.0,0.0,1.0); glPointSize(1.0); glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(0.0,500.0,0.0,500.0); } void main(int argc,char **argv ) { glutInit(&argc,argv); glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB); glutInitWindowSize(500,500); glutInitWindowPosition(200.0,200.0); glutCreateWindow("CG_test_Bresenham_Line example"); glutDisplayFunc(display); myinit(); glutMainLoop(); } 二、中点法绘制椭圆 #include #include glPopMatrix(); glPushMatrix(); glTranslatef(0,0,3.5); glScalef(5,4,1); glutSolidCube(1.0); glPopMatrix(); //leg1 glPushMatrix(); glTranslatef(1.5,1,1.5); Draw_Leg(); glPopMatrix(); //leg2 glPushMatrix(); glTranslatef(-1.5,1,1.5); Draw_Leg(); glPopMatrix(); //leg3 glPushMatrix(); glTranslatef(1.5,-1,1.5); Draw_Leg(); glPopMatrix(); //leg4 glPushMatrix(); glTranslatef(-1.5,-1,1.5); Draw_Leg(); glPopMatrix(); } void updateView(int width,int height) { glViewport(0,0,width,height);//reset the current viewport glMatrixMode(GL_PROJECTION);//select the projection matrix glLoadIdentity();//reset the projection matrix float whRatio=(GLfloat)width/(GLfloat)height; if(bPersp) { //todo when 'p'operation ,hint:use function glupersPective } else glOrtho(-3,3,-3,3,-100,100); glMatrixMode(GL_MODELVIEW);//select the modelview matrix 实验二 直线的生成算法的实现 班级 08信计2班 学号 59 姓名 分数 一、实验目的和要求 1.理解直线生成的基本原理。 2.掌握几种常用的直线生成算法。 3.利用Visual C++实现直线生成的DDA 算法。 二、实验内容 1.了解直线的生成原理，尤其是Bresenham 画线法原理。 2.掌握几种基本的直线生成算法：DDA 画线法、Bresenham 画线法、中点画线法。 3.利用Visual C++实现直线生成的DDA 算法，在屏幕上任意生成一条直线。 三、实验步骤 1.直线的生成原理： （1）DDA 画线法也称数值微分法，是一种增量算法。是一种基于直线的微分方程来生成直线的方法。 （2）中点画线法原理 以下均假定所画直线的斜率[0,1]k ∈，如果在x 方向上的增量为1，则y 方向上的增量只能在01 之间。中点画线法的基本原理是：假设在x 坐标为p x 的各像素点中，与直线最近者已经确定为(,)p p P x y ，用小实心圆表示。那么，下一个与直线最近的像素只能是正右方的1(1,)p p P x y +，或右上方的2(1,1)p p P x y ++，用小空心圆表示。以M 为1P 和2P 的中点，则M 的坐标为(1,0.5)p p x y ++。又假设Q 是理想直线与垂直线1p x x =+的交点。显然，若M 在Q 的下方，则2P 离直线近，应取2P 为下一像素点；若M 在Q 的上方，则1P 离直线近，应取1P 为下一像素点。 （3）B resenham 画线法原理 直线的中点Bresenham 算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的值。 给定理想直线的起点坐标为P0（x0，y0），终点坐标为P1（x1，y1），则直线的隐函数方程为： 0b kx y y)F(x,=--= （3-1） 构造中点偏差判别式d 。 b x k y y x F y x F d i i i i M M -+-+=++==)1(5.0)5.0,1(),( 按字节计算ＣＲＣ unsigned int cal_crc(unsigned char *ptr,unsigned char len) { unsigned int crc; unsigned char da; unsigned int crc_ta[256]={/*CRC余式表*/ 0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7, 0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef, 0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6, 0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de, 0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485, 0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d, 0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4, 0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc, 0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823, 0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b, 0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12, 0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a, 0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41, 0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49, 0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70, 0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78, 0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f, 0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067, 0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e, 0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256, 0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d, 0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405, 0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c, 0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634, 《计算机图形学》课程教学大纲一、课程基本信息 课程代码：110053 课程名称：计算机图形学 英文名称：Computer Graphics 课程类别：专业课 学时：72 学分： 适用对象：信息与计算科学专业本科生 考核方式：考试（平时成绩占总成绩的30%） 先修课程：高级语言程序设计、数据结构、高等代数 二、课程简介 中文简介： 计算机图形学是研究计算机生成、处理和显示图形的学科。它的重要性体现在人们越来越强烈地需要和谐的人机交互环境：图形用户界面已经成为一个软件的重要组成部分，以图形的方式来表示抽象的概念或数据已经成为信息领域的一个重要发展趋势。通过本课程的学习，使学生掌握计算机图形学的基本原理和基本方法，理解图形绘制的基本算法，学会初步图形程序设计。 英文简介： Computer Graphics is the subject which concerned with how computer builds， processes and shows graphics. Its importance has been shown in people’s more and more intensively need for harmony human-machine interface. Graphics user interface has become an important part of software. It is a significant trend to show abstract conception or data in graphics way. Through the learning of this course, students could master Computer Graphics’basic theories and methods，understand graphics basic algorithms and learn how to design basic graphics program. 三、课程性质与教学目的 《计算机图形学》是信息与计算科学专业的一门主要专业课。通过本课程的学习，使学生掌握基本的二、三维的图形的计算机绘制方法，理解光栅图形生成基本算法、几何造型技术、真实感图形生成、图形标准与图形变换等概念和知识。学会图形程序设计的基本方法，为图形算法的设计、图形软件的开发打下基础。 四、教学内容及要求 第一章绪论 (一)目的与要求 1.掌握计算机图形学的基本概念； 2.了解计算机图形学的发展、应用； 3.掌握图形系统的组成。 《计算机图形学实验报告》样例 实验名称：圆周画法的实现 1.实验内容 1.画出圆心坐标为(75,90)和半径为50的红色圆周 2.画出圆心坐标为(‐40,‐80)和半径为60的蓝色圆周 2.程序的基本思路和功能 先用MFC构建界面外观，然后在相应位置分别用Bresenham和DDA编辑画圆的程序然后编译运行。 3.关键代码及说明 void Circle::circleMinPoint(CDC* pDC) { xCenter = (float)(400 + x); yCenter = (float)(300 - y); //绘制圆心 drawCenter(pDC); //r = 50; //设置颜色 color = RGB(red,green,blue); float m_x = 0; float m_y = r; float d = 1.25 - r; circlePoint(m_x,m_y,pDC); while(m_x <= m_y){ if(d<=0){ d = d + 2 * m_x + 3; }else{ d = d + 2 * ( m_x - m_y ) + 5; m_y = m_y - 1; } m_x = m_x + 1; circlePoint(m_x,m_y,pDC); } } void Circle::circleBresenham(CDC* pDC) { //确认圆心坐标 xCenter = (float)(400 + x); yCenter = (float)(300 - y); //绘制圆心 drawCenter(pDC); //r = 50; //设置颜色 color = RGB(red,green,blue); float m_x = 0; float m_y = r; CRC校验实用程序库(一) 在数据存储和数据通讯领域，为了保证数据的正确，就不得不采用检错的手段。在诸多检错手段中，CRC是最著名的一种。CRC的全称是循环冗余校验，其特点是:检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT，ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。 CRC的本质是模-2除法的余数，采用的除数不同，CRC的类型也就不一样。通常，CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式如表1所示。 @@10A08800.GIF;表1.最常用的CRC码及生成多项式@@ 由于CRC在通讯和数据处理软件中经常采用，笔者在实际工作中对其算法进行了研究和比较，总结并编写了一个具有最高效率的CRC通用程序库。该程序采用查表法计算CRC，在速度上优于一般的直接模仿硬件的算法，可以应用于通讯和数据压缩程序。 通常的CRC算法在计算一个数据段的CRC值时，其CRC值是由求解每个数值的CRC值的和对CRC寄存器的值反复更新而得到的。这样，求解CRC的速度较慢。通过对CRC算法的研究，我们发现:一个8位数据 加到16位累加器中去，只有累加器的高8位或低8位与数据相作用，其结果仅有256种可能的组合值。因而，我们可以用查表法来代替反复的运算，这也同样适用于CRC32的计算。本文所提供的程序库中，函数crchware是一般的16位CRC的算法；mk-crctbl用以在内存中建立一个CRC数值表；crcupdate用以查表并更新CRC累加器的值；crcrevhware和crcrevupdate是反序算法的两个函数；BuildCRCTable、CalculateBlockCRC32和UpdateCharac terCRC32用于CRC32的计算。 /*CRC.C——CRC程序库*/ #defineCRCCCITT0x1021 #defineCCITT-REV0x8408 #defineCRC160x8005 #defineCRC16-REV0xA001 #defineCRC32-POLYNOMIAL0xEDB88320L /*以上为CRC除数的定义*/ #defineNIL0 #definecrcupdate(d,a,t)*(a)=(*(a)>8)^(d)]; #definecrcupdate16(d,a,t)*(a)=(*(a)>>8^(t)(*(a)^(d))&0x00ff]) /*以上两个宏可以代替函数crcupdate和crcrevupdate*/ #include #include 2.1.1 生成直线的DDA算法 数值微分法即DDA法(Digital Differential Analyzer)，是一种基于直线的微分方程来生成直线的方法。 一、直线DDA算法描述： 设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得 可通过计算由x方向的增量△x引起y的改变来生成直线： 也可通过计算由y方向的增量△y引起x的改变来生成直线： 式(2－2)至(2－5)是递推的。 二、直线DDA算法思想： 选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大)，取该方向上的增量为一个象素单位(△x=1)，然后利用式(2－1)计算另一个方向的增量(△y=△x·m=m)。通过递推公式(2－2)至(2－5)，把每次计算出的(x i+1，y i+1)经取整后送到显示器输出，则得到扫描转换后的直线。 之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。 另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。 三、直线DDA算法实现： 1、已知直线的两端点坐标：(x1，y1)，(x2，y2) 2、已知画线的颜色：color 3、计算两个方向的变化量：dx=x2－x1 dy=y2－y1 4、求出两个方向最大变化量的绝对值： steps=max(|dx|，|dy|) 5、计算两个方向的增量(考虑了生成方向)： xin=dx/steps yin=dy/steps 6、设置初始象素坐标：x=x1,y=y1 7、用循环实现直线的绘制： for(i=1；i<=steps；i++) { putpixel(x，y，color)；/*在(x，y)处，以color色画点*/ x=x+xin； y=y+yin； } 五、直线DDA算法特点： 该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。 //@brief 浮点数转整数的宏 实现代码 #define FloatToInteger(fNum) ((fNum>0)?static_cast计算机图形学裁剪算法详解
CRC16算法原理
计算机图形学实验--橡皮筋技术(完整代码,准确无误)
计算机图形学真实图形
CRC校验解读
图形学实验一 三维分形(附源代码)
计算机图形学图形的几何变换的实现算法
CRC算法
计算机图形学 实验一：生成彩色立方体(含源代码)
计算机图形学实验C++代码
计算机图形学实验_透视茶壶源代码
计算机图形学 直线的生成算法的实现
16位CRC算法原理及C语言实现
计算机图形学课程教学大纲
计算机图形学 圆周算法的实现
CRC校验实用程序库(一)
计算机图形学常用算法及代码大全
相关主题
文本预览