图形学算法（伪代码）.txt

图形学算法（伪代码）

//bresenham 圆
void MyCircle(CDC* pDC, int x0, int y0, int r)
{   int d, x, y ;

    d = 1-r;
    x = 0;  y = r;
    CirclePoint( pDC, x0, y0, x, y ) ;
    while( y>x )
    { if( d<=0 ) d += 2*x+3; 
        else { d += 2*(x-y);  y--; }
      x++;
      CirclePoint( pDC, x0, y0, x, y ) ;}
}

void CirclePoint( CDC* pDC, int x0, int y0, int x, int y)
{   
        pDC->SetPixel( pDC, x0+x, y0+y ) ;
        pDC->SetPixel( pDC, x0+y, y0+x ) ;
        pDC->SetPixel( pDC, x0-y, y0+x ) ;
        pDC->SetPixel( pDC, x0-x, y0+y ) ;
        pDC->SetPixel( pDC, x0+y, y0-x ) ;
        pDC->SetPixel( pDC, x0+x, y0-y ) ;
        pDC->SetPixel( pDC, x0-x, y0-y ) ;
        pDC->SetPixel( pDC, x0-y, y0-x ) ;
}
-----------------------------------------------------------------------
//bresenham 直线
void MyLine( CDC* pDC, int x1, int y1, int x2, int y2, COLORREF color )
{
  int x, y, e, a, b ;

  a = x2 - x1 ;
  b = y2 - y1 ;
  e = 2 * b - a ;
  x = x1 ; y = y1 ;
  MySetPixel( pDC, x, y, color ) ;
  while( (x != x2) || ( y != y2 ))
   { if ( e >= 0 ) 
        { y ++ ; e -= 2 * a ; }
         x ++ ;  
         e += 2 * b ; }
     pDC->SetPixel( x, y, color ) ; 
        }
}
-----------------------------------------------------------------------
//四连通点填充 （边界）
void MyFloodFill( CDC* pDC, int x, int y, COLORREF color, COLORREF BoundColor )
{
        pDC->SetPixel(x,y,color);
        if ( pDC->GetPixel(x-1,y) != BoundColor )
                MyFloodFill( pDC, x-1, y, color, BoundColor ) ;
        if ( pDC->GetPixel(x+1,y) != BoundColor )
                MyFloodFill( pDC, x+1, y, color, BoundColor ) ;
        if ( pDC->GetPixel(x,y+1) != BoundColor )
                MyFloodFill( pDC, x, y+1, color, BoundColor ) ;
        if ( pDC->GetPixel(x,y-1) != BoundColor )
                MyFloodFill( pDC, x, y-1, color, BoundColor ) ;
}
-----------------------------------------------------------------------
//四连通点填充 （内部）
void MyFloodFill( CDC* pDC, int x, int y, COLORREF color, COLORREF OldColor )
{
        pDC->SetPixel(x,y,color);
        if ( pDC->GetPixel(x-1,y) == OldColor )
                MyFloodFill( pDC, x-1, y, color, OldColor ) ;
        if ( pDC->GetPixel(x+1,y) == OldColor )
                MyFloodFill( pDC, x+1, y, color, OldColor ) ;
        if ( pDC->GetPixel(x,y+1) == OldColor )
                MyFloodFill( pDC, x, y+1, color, OldColor ) ;
        if ( pDC->GetPixel(x,y-1) == OldColor )
                MyFloodFill( pDC, x, y-1, color, OldColor ) ;
}
-----------------------------------------------------------------------
//bezier 分裂
void BezierSplit( CDC * pDC, double px[], double py[], int n, int k)
{
  double qx[MAX], qy[MAX] ;
  register i, j ;

  for( i = 0 ; i <= n ; i++ )
   { qx[i] = px[0] ;
     qy[i] = py[0] ;
     for( j = 0 ; j < n-i ; j++ )
      {         px[j] =(px[j] + px[j+1]) / 2. ;
                 py[j] =(py[j] + py[j+1]) / 2. ; } }
  if ( k > 1 )
   { BezierSplit( pDC, qx, qy, n, k-1) ;
         BezierSplit( pDC, px, py, n, k-1) ; }
  else
   { DrawLine( pDC, qx, qy, n ) ;
         DrawLine( pDC, px, py, n ) ; }
}

void DrawLine(CDC * pDC, double px[], double py[], int n)
{ register i ;

  pDC->MoveTo((int)px[0], (int)py[0]) ;
  for( i = 1 ; i <= n ; i++ )
    pDC->LineTo((int)px[i], (int)py[i]) ;
}
-----------------------------------------------------------------------
//逐点 Bezier
void BezierPoint( CDC * pDC,  double px[], double py[], int n, int count)
{
  double qx[MAX], qy[MAX], u ;
  register i, j, k ;

  pDC->MoveTo((int)px[0], (int)py[0]) ;
  for( k = 1 ; k < count ; k++ )
   { u = (double)k / (double)count ;
     for( i = 0 ; i <= n ; i++ )
      { qx[i] = px[i] ;
                qy[i] = py[i] ; }
     for( i = 0 ; i < n ; i++ )
       for( j = 0 ; j < n-i ; j++ )
                { qx[j] = (1.-u) * qx[j] + u * qx[j+1] ;
                  qy[j] =(1.-u) * qy[j] + u * qy[j+1];}
     pDC->LineTo((int)qx[0], (int)qy[0]) ; }
  pDC->LineTo((int)px[i], (int)py[i]) ;
}
-----------------------------------------------------------------------
//二次B样条
void Bspline2( CDC * pDC, double px[], double py[], int n, int count)
{ double mar2[4][4] = {{0.5, -1., 0.5, 0.}, {-1., 1., 0., 0.},
                      {0.5, 0.5, 0., 0.} , { 0., 0., 0., 0.}} ;
  register i ;

  pDC->MoveTo((int) ceil((px[0]+px[1])/2.), (int) ceil((py[0]+py[1])/2.)) ;
  for( i = 0 ; i <= n - 2 ; )
   { BsplinePoint( pDC, mar2, 2, px, py, i++, count ) ;
     pDC->LineTo((int) ceil((px[i]+px[i+1])/2.), (int) ceil((py[i]+py[i+1])/2.))
; }
     pDC->SelectObject(oldpen);
}

void BsplinePoint( CDC * pDC,  double mar[][4], int k, double px[], double py[],
                   int m, int count )
{ double t, u, x, y, sx, sy ;
  register i, j, l ;

  for( l = 1 ; l < count ; l++ )
   { t = (double)l / (double)count ;
     u = 1. ; x = y = 0. ;
     for( i = k ; i >= 0 ; i-- )
      { sx = sy = 0. ;
           for( j = 0 ; j <= k ; j++ )
           { sx += mar[i][j] * px[m+j] ;
             sy += mar[i][j] * py[m+j] ; }
           x += u * sx ; y += u * sy ;
           u *= t ; }
       pDC->LineTo((int)x, (int)y) ; }
}
-----------------------------------------------------------------------
//三次B样条
void Bspline3(CDC* pDC,double px[], double py[], int n, int count)
{  double mar3[4][4] = {
          {-0.166667, 0.5, -0.5, 0.166667},
          {0.5, -1., 0.5, 0.},
           {-0.5, 0., 0.5, 0.} , 
          { 0.166667, 0.666667, 0.166667, 0.}  } ;
  register i ;

  pDC->MoveTo((px[0]+4.*px[1]+px[2])/6., 
                (py[0]+4.*py[1]+py[2])/6.);
  for( i = 0 ; i <= n - 3 ; )
   { BsplinePoint(pDC, mar3, 3, px, py, i++, count ) ;
     pDC->LineTo((int)((px[i]+4.*px[i+1]+px[i+2])/6.),
                (int) (py[i]+4.*py[i+1]+py[i+2])/6.)) ; }
}

void BsplinePoint( CDC * pDC,  double mar[][4], int k, double px[], double py[],
                   int m, int count )
{
  double t, u, x, y, sx, sy ;
  register i, j, l ;

  for( l = 1 ; l < count ; l++ )
   { t = (double)l / (double)count ;
     u = 1. ; x = y = 0. ;
     for( i = k ; i >= 0 ; i-- )
      { sx = sy = 0. ;
                for( j = 0 ; j <= k ; j++ )
                { sx += mar[i][j] * px[m+j] ;
              sy += mar[i][j] * py[m+j] ; }
                x += u * sx ; y += u * sy ;
                u *= t ; }
     pDC->LineTo((int)x, (int)y) ; }
}

-----------------------------------------------------------------------
//线填充Etable
void SortXrank( PETable ETable[], int Xrank[], int k )
{//冒泡排序
  int i, j, tmp ;
  for( i=0; i<k; i++ )
     for( j = 0; j<k-i; j++ )
       if (ETable[Xrank[j]]->x > ETable[Xrank[j+1]]->x )
        { tmp = Xrank[j] ; Xrank[j] = Xrank[j+1] ;
           Xrank[j+1] = tmp ; }
}

void AddETable( PETable ETable[], int i, int n )
{
  if ( i == -1 ) i = n ;
  switch( ETable[i]->flag )
      { case 0 :
          ETable[i]->flag = 1 ;
          break ;
        case 1 :
          ETable[i]->flag = -1 ;
          break ;
      }
}

PETable RequestETable(int x0, int y0, int x, int y)
{//生成一个表
  PETable p ;

  p = new ETable ;
  if ( y >= y0 )
   { p->x = (float)x0 ;
         p->dx = (float)(x-x0)/(float)(y-y0) ; } 
  else
   { p->x = (float)x ;
         p->dx = (float)(x0-x)/(float)(y0-y) ; }
  p->flag = 0 ;
  return(p) ;
}

void MyFillPolygon( CDC* pDC, float p[][2], int n, int color)
{
//p为点数组，n条边，n个顶点
  PETable ETable[10] ;
  int Yrank[10], Xrank[10], flag[10] ;
  int i, j, k, tmp ;
  int x0, y0, x, y ;

  //画多变形
  DrawPolygon( pDC, p, n, color ) ;
  //排序顶点，Yrank[]为顶点下标
  for( i=0; i<=n; i++ )
    Yrank[i] = i ;
  for( i=0; i<n; i++ )
   for( j = 0; j<n-i; j++ )
     if ( p[Yrank[j]][1] > p[Yrank[j+1]][1] ) //按y值冒泡排序
          { tmp = Yrank[j] ; Yrank[j] = Yrank[j+1] ;
            Yrank[j+1] = tmp ; }
  //初始化ET表
  x0 = (int)p[0][0]; y0 = (int)p[0][1] ;
  for( i=1; i<=n; i++ )
   { x = (int)p[i][0] ; y = (int)p[i][1] ;
     ETable[i-1] = RequestETable(x0, y0, x, y) ;
     x0 = x ; y0 = y ;
   }
  x = (int)p[0][0]; y = (int)p[0][1] ;//最后一条边
  ETable[n] = RequestETable(x0, y0, x, y) ;


  //遍历填色
  i = 0 ;
  y = p[Yrank[0]][1] ;
  while( i < n )
   { //引进二边表
     do
      { AddETable( ETable, Yrank[i], n ) ;
        AddETable( ETable, Yrank[i]-1, n ) ;
        i++ ;
      } while( p[Yrank[i]][1] == p[Yrank[i-1]][1] ) ;
     //计算x新值
     k = 0 ;
     for( j=0; j<=n; j++ )
       if (ETable[j]->flag == 1)
                { ETable[j]->x += ETable[j]->dx ;
                  Xrank[k++] = j ; 
                }
     k-- ;
     SortXrank( ETable, Xrank, k ) ;  //排序新x值
         //重复画线填色
     for( ; y <= p[Yrank[i]][1]; y++ )
      { for( j = 0 ; j <= k ; j+=2 )
                { vline( pDC, (int)(ETable[Xrank[j]]->x+1.5),(int)(ETable[Xrank[j+1]]->x+0.5), y, color ) ;
                        ETable[Xrank[j]]->x += ETable[Xrank[j]]->dx ;
                        ETable[Xrank[j+1]]->x +=ETable[Xrank[j+1]]->dx;
       }}}
}
////////////////////////////////////////////////////////////////////////
(1)将顶点按y值升序排列 Ri
(2)置初值：y=y[R[0]]
(3)For(i=0;i<=N;i++)
        {引进p[R[i]]的两边，L，R
        如果边在AET表中删除，不在加入
        重新对AET排序，否则先比较x，x相等，比较dx
        for(;y<y[R[i+1]];y++)
        {
                遍历AET表(j=0;j<k;j++)
                do{
                        Lineto(x[i,j],y)
                        遍历AET表
                        x[i]=do[i]直到结束
}