三维网页中的三角形填充算法

文章来源 —— 绿睿科技： 车牌识别 三维网页 网页游戏
2009.02
三维图形通常的数据结构是三角形面片， 所以绘制三维图形本质上就是绘制多个三角形的面片。 这项工作在通常情况下，是由显卡完成的。 但是具体到三维网页的开发环境， 往往无法访问显卡，需要软件实现。 本文将重点描述三角形面片的填充算法。
名称：三角形填充
输入：三角形的三个顶点的二维坐标
输出：三角形内部所有点的坐标
算法：
1、对输入的三个顶点，按y坐标关键之排序。 得到新序列的三个顶点：up middle和down。
2、确定y轴方向上的起点start_y：选取up.y和0的最大值； 确定y轴方向上的终点end_y：选取down.y和height-1的最小值值。 注意，必须根据0和height-1对扫描边界进行选择。 否则会出现死循环。
3、y从start_y到middle.y循环， 根据直线up middle和up down确定x的两个端点。 同样地，x的起始点要受0和width-1的约束。 对每一个x,y进行填充。
4、y从middle.y到end_y循环， x的两个端点是靠middle down和up down确定的。
5、结束。
代码：
void C3DWindow::Triangle(int x0,int y0,unsigned char red0, unsigned char green0,unsigned char blue0, double z0,int x1,int y1,unsigned char red1, unsigned char green1,unsigned char blue1, double z1,int x2,int y2,unsigned char red2, unsigned char green2,unsigned char blue2, double z2)
{
   STrianglePoint point[3];
 
   point[0].x=x0;
   point[0].y=y0;
   point[0].red=red0;
   point[0].green=green0;
   point[0].blue=blue0;
   point[0].z=z0;
 
   point[1].x=x1;
   point[1].y=y1;
   point[1].red=red1;
   point[1].green=green1;
   point[1].blue=blue1;
   point[1].z=z1;
 
   point[2].x=x2;
   point[2].y=y2;
   point[2].red=red2;
   point[2].green=green2;
   point[2].blue=blue2;
   point[2].z=z2;
 
   int up,middle,down;
   {
     //bubble sort
     int index[3];
     index[0]=0;
     index[1]=1;
     index[2]=2;
     int outer;
     for(outer=0;outer<3;outer++)
     {
       int inner;
       for(inner=outer+1;inner<3;inner++)
       {
         if(point[index[outer]].y>point[index[inner]].y)
         {
           int temple;
           temple=index[outer];
           index[outer]=index[inner];
           index[inner]=temple;
         }
       }
     }
     up=index[0];
     middle=index[1];
     down=index[2];
   }
  
   int start_y;
   start_y=point[up].y;
   if(start_y<0)
     start_y=0;
   if(start_y>=m_height)
     start_y=m_height-1;
   int middle_y;
   middle_y=point[middle].y;
   if(middle_y<0)
     middle_y=0;
   if(middle_y>=m_height)
     middle_y=m_height-1;
   int end_y;
   end_y=point[down].y;
   if(end_y<0)
     end_y=0;
   if(end_y>=m_height)
     end_y=m_height-1;
 
   int y;
   for(y=start_y;y<=end_y;y++)
   {
     STrianglePoint point_horizontal_0,point_horizontal_1;
     if(y<middle_y)
     {
       TriangleY(point_horizontal_0,point[up],point[down],y);
       TriangleY(point_horizontal_1,point[up],point[middle],y);
     }
     else
     {
       TriangleY(point_horizontal_0,point[down],point[up],y);
       TriangleY(point_horizontal_1,point[down],point[middle],y);
     }
     HorizontalLine(point_horizontal_0,point_horizontal_1);
   }
}