图形学第三章答案.doc

第三章答案3.1 修改Bresenham算法，使之可绘制具有实线、虚线和点线等各种线型的直线，并且要求从键盘输入两端点坐标，就能在显示器屏幕上画出对应直线。答案：（略）3.2 圆弧生成算法中，Bresenham算法比正负法更合理的原因？答案：设圆的半径为R，圆心在原点，则对于正负法，决定下一点走向的判别式为，判别准则为：时，下一步取当前点的正右方的点；时，下一步取当前点正下方的点。即若当前点在圆内，则下一步向圆外走；若当前点在圆外，则下一步向圆内走。而对于Bresenham算法，判别式为 判别准则为： 时，下一步取当前点的正右方的点；时，下一步取当前点的正下方的点。这说明Bresenham算法在候选的两个像素中，总是选定离圆弧最近的像素为圆弧的一个近似点，因此，Bresenham算法比正负法决定的像素更合理。3.3 假设圆的中心不在原点，试编写算法对整个圆进行扫描转换。答案：假设圆的方程为：，先用正负法、Bresenham算法和圆的多边形迫近法这三种方法中的任一种生成圆心在原点的圆，再分别将x，y的坐标值加上a，b，得到的平移后的圆即所求的结果。3.4 多边形的顶点和点阵表示各有什么优缺点？答案：顶点表示是用多边形的顶点序列来描述多边形。该表示几何意义强、占内存少、几何变换方便；但它不能直观地说明哪些像素在多边形内，故不能直接用于面着色。点阵表示用位于多边形内的像素的集合来描述多边形。该方法虽然没有多边形的几何信息，但便于用帧缓存表示图形，可直接用于面着色。3.5 在多边形的扫描线算法中，是如何处理奇点的？答案：为使每一条扫描线与多边形P的边界的交点个数始终为偶数，规定当奇点是多边形P的极值点时，该点按两个交点计算，否则按一个交点计算。在实际计算过程中，可采用如下方法处理非极值点：若是非极值点，则将，两边中位于扫描线上方的那条边在处截去一个单位长，这样就可以保证扫描线只和，中的一边相交，只有一个交点。3.6 任意给定五边形的五个顶点坐标，利用多边形填充的扫描线算法，编写程序生成一个实心五边形。答案：（略）3.7 简述边缘填充算法和边界标志算法的基本思想、步骤以及优缺点。边缘填充算法：基本思想：在光栅图形中，如某区域已着上值为M的某种颜色，则对区域作偶数次求补运算后，该区域的颜色不变；作奇数次求补运算后，该区域的颜色则变成值为的颜色。步骤：对多边形P的每一非水平边（i=0,1,n）上的各像素做向右求补运算，当相对于所有边的求补运算都完成后，多边形的扫描转换也随之完成。优缺点：和扫描线算法比较，边缘填充算法的数据结构和程序结构都简单得多，但是它在执行时需对帧缓存中的大批元素反复赋值，故速度有所下降，另外如果区域内原来有其它的颜色，也不能保证最后区域内的颜色就是多边形的颜色，所以该算法对单值图像比较有用。边界标志算法：基本思想：首先用一种特殊的颜色在帧缓存中将多边形的边界（水平边的部分边界除外）勾画出来，然后再把位于多边形内的各个区段着上所需的颜色。步骤：1）以值为boundary_color 的特殊颜色勾画多边形P的边界。 2）逐条处理扫描线对多边形着色。优缺点：与边缘填充算法相比，本算法避免了对帧缓存中的大量元素的多次赋值，但需逐条扫描线地对帧缓存中的元素进行搜索和比较。本算法适合于硬件化。3.8 简述区域的两种表示方法。答案：在光栅图形中，区域可采用内点表示和边界表示两种表示形式。把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。它将区域内的所有像素填充成同一种颜色（常称为原色），而区域边界上的像素则不能填这种颜色。把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。它将区域边界上的像素都着上同一种颜色（常称为边界色），而区域内的像素则不能着这种颜色。3.9 简述四连通区域和八连通区域的概念以及两者之间的关系。答案：四连通的区域是指从该区域内一点出发，通过上、下、左、右四种运动的组合，在不越出区域的前提下，可到达区域内的任一点。八连通的区域是指从该区域内一点出发，通过沿水平方向、垂直方向和对角线方向的八种运动的组合，在不越出区域的前提下，可到达区域内的任一点。四连通区域的边界为八连通区域，而八连通区域的边界为四连通区域。3.10 请简要叙述扫描线种子填充算法的基本思想及其用堆栈实现的步骤。答案：基本思想：从给定的种子点开始，先填充种子点所在扫描线上的位于给定区域内的一个区间，然后确定与这一区间相邻的上下两条扫描线上需要填充的区间，从这些区间上各取一个种子点并依次保存下来，作为下次填充的种子点，反复进行这个过程，直到所保存的各区间都填充完毕。借助于堆栈，该算法可由以下四个步骤实现。（1）将堆栈置空，并将给定的种子点（x, y）压入堆栈。（2）若堆栈为空，算法结束；否则取栈顶元素（x, y）作为种子点。（3）从种子点（x, y）出发，沿纵坐标为y的当前扫描线向左右两个方向用新的颜色逐个像素地填充，直到边界。设区间两边界的横坐标分别为和。（4）以区间为搜索范围，检查与当前扫描线相邻的上下两条扫描线上的像素，若存在非边界、未填充的像素，则把相应小区间中最右边的点作为种子点压入堆栈，转入（2）。3.11 解释走样和反走样的概念，以及反走样的几种表现形式。答案：图形信号是连续的，而它们在光栅显示器上对应的图形则是由一系列相同亮度的离散像素组成。用离散的像素表示连续的直线或多边形的边界必然会引起图形的失真，即光滑的线段变成了阶梯的形状，这种现象就称为走样。用于减轻或消除这种效果的技术就称为反走样。