cad系统的图形与算法.doc

图形生成与处理是CAD技术的关键技术之一。目前许多商用软件系统均提供了直线。圆弧以及其它一些基本图形的生成，曲面和实体的描述，各种图形的处理（包括图形窗口管理、图形的裁剪、图形的变换）等功能。 2．l 线段的生成原理??? Bresenham在1965年提出一种有效的直线算法。应用光栅扫描显示设备，Bresenham算法在过程LINE中解决的主要问题是：避免y作四舍五人成一个整数所花费的时间；采用斜率m为直线生成的误差判断数；同时在算法中避免实数运算。Bresenham算法之所以有吸引力是由于它只用整数计算。因为不用实型变量，就不需要四舍五人。为简化起见，我们假设直线的斜率在0到1 间。此算法用了一个决策变量di在每一步di都与图2.1中的 S与t的差成正比。该图描述的是第 i步的情况，这时 已经选定了像素只Pi-1，使它距离实际要画的直线最近。在第i步要决定下一个像素应当是T还是Si。如果S＜t，则Si比较靠近所 需要的直线，应当选Si；否则，n比较靠近直线，应当选Ti。 要画的直线是从（0，0）到（x1，y1），现在直线方程是y=（dy/dx）*x参照图2．1，可以用（r， q）表示Pi-1的坐标，那么Si=(r十l, q）， Ti＝（ r＋l， q＋l）。可以写出： s=dy/dx（r＋ l）－ q t=q十 l- dy/dx（r＋ l） 因此s-t＝ 2dy/dx（r＋l）－ 2q－ l 当s-t＜0时，选Si0对上式作一些处理，我们有 dx（s－ t）＝ 2（r· dy· q· dx）＋ 2dy－ d0 现在dx为正，因此我们可以用d＜（S－t）＜0选择。定义di： di＝ 2（r· dy－ q· dx）＋ Zdy－ d0 令r＝xi-1；及q=yi-1，这样 di=2xi－ldy－2yi－ldx十2dy－dx 将每一个下标加1，则 di+1=2xidy-2yidx+2dy-dx 从di＋l中减去di，我们得到 di十l－di＝ 2dy（xi－xi-l）－2dx（yi－yi-1） 我们知道xi－xi-1＝1。重新写上式，可得 dx十l=di＋2dy－2dx（yi－yi-1） 如果di＞0，则选Ti，因而yi=yi+1＋l，同时di＋l＝di +2（dy－dx） 如果di＜0，则选Si，因而yi=yi-1，同时di＋1＝ di＋ 2dy 这样迭代的方法是，由前一个di，计算出di＋1，并对Si及T进行选择。初始值di可以计算出来，此时i＝ l，并已知(x0，y0）＝（0，0）。那么 di＝ 2dy－ dx 这几式计算所需要的运算量是最小的，它只包括加法、减法和移位（乘2），无需进行费时的乘法运算。 2．2．1 曲线与曲面的特性 ??? 在介绍曲线、曲面的数学表示之前，首先了解一下曲线和曲面的一些重要特性。（l）曲线和曲面的控制点以及节点 可以控制曲线形状的各个点称之为控制点，如果控制点位于曲线或曲面之上又称其为节点。（2）多值性 一条曲线或曲面往往不是一个坐标的单值函数，如图2．2所示。一般不希望给定的函数带有多值性。（3）几何不变性 在不同的坐标系中度量控制点时，所生成的几何形状必须保持不变。这种性质也称为坐标轴的无关性。例如，稍后将要介绍的贝塞尔曲线的形状仅仅与其特征多边形的各顶点（控制点）有关。因此，它不依赖于坐标系 的选择。（4）全局或局部控制 设计者在一个已存在的曲线或曲面上修改某个控制点时，曲线或曲面只在控制点附近的区域改变形状，也可能整个形状都被改变，如图2．3所示。我们通常称前一种情况为局部控制能力，后者为全局控制能力。（5）缩小变化特性 有些数学表示往往不是平滑而是放大由控制点所描绘的曲线中的细小不规则处。另有一些则正好相反，它总是平滑所给定的控制点。如图2．4所示，图中（a）在曲线上产生高阶振荡，而（b）则使曲线失去圆滑性。这两种情况在工程上都不理想，如果用（a）这种情况所形成的几何形状来做数控加工的话，很可能会出现载刀的情况（铣刀轨迹跌落），造成机床和工件的损坏，或者可能产生过切现象（Undercut），得不到理想的加工形状 。（6）连续性的阶 实际应用的几何形体往往是由多个曲面片或曲线来模拟构造的。为了保证设计者的要求，这些曲线和曲面在连续处要保证有一定的连续性。零阶连续性记作d，指两条曲线简单地相交，这种情况造成交点处有一明显的拐角，如图 2．5所示。一阶连续性记作 C1，要求曲线在交点相切； 阶连续性记作0，要求曲率相等。2．2．2 曲线和曲面的参数表示??? 在三维空间的一条曲线可以表述为曲面F和曲面C的交线： F（X，Y，Z）=0，G（x，Y，Z）＝0 ??? 如果将其表示成参数U的函数，则一条曲线可写成： x=X（u）