LEVEL 1:ポリゴン一個

目次
LEVEL 0:点| LEVEL 2:光源一個

LEVEL 1:ポリゴン１個 　３次元空間上の点を描画できたらポリゴンを描くのは簡単です。ポリゴンの頂点をそれぞれスクリーンに投影し、その中身を塗りつぶせばいいだけです。

＃この記事では三角ポリゴンのみを扱うことにします。
＃それ以外のポリゴンでは同一平面上に頂点がなかったり、
＃描画に余計な手間がかかるので。

typedef	struct{
	Vertex	vertex[3];
}Polygon;

typedef	struct{
	int	x;
	int y;
}Vertex2;

typedef	struct{
	Vertex2	vertex[3];
}Triangle;

void DrawPolygon(Polygon* poly, int offsetX, int offsetY){
	int	i;
	Triangle	tri;
	
	for(i = 0; i < 3; i++){
		if(poly->vertex[i].z <= kScreenDistance)
			return;
		
		tri.vertex[i].x = ((vertex.x *kScreenDistance) /vertex.z) +offsetX;
		tri.vertex[i].y = ((vertex.y *kScreenDistance) /vertex.z) +offsetY;
	}
	FillTriangle(&tri);	// 三角形を塗りつぶす関数
}

＃上のソースでは説明を簡単にするため、
＃拡張がしにくいデータ構造になっていますが、ご勘弁を。
＃あと、for文は展開したほうが速いかも。
＃＃プロセッサによるけど。PPCの様にプロセッサキャッシュに
＃＃頼ってるプロセッサでは展開しないほうが
＃＃（サイズが小さいほうが）速いかもしれない
　で、上のソースの肝はFillTriangle関数です。OSでこういった関数が用意されてればそれを使ってもいいのですが、細かい制御がきかないとか高性能すぎるとかいろいろあるので、自分で実装することにしましょう。

LEVEL 1-2:三角形の塗りつぶし 　三角形の塗りつぶしには「最大最小法」と呼ばれる手法を使うことにします。これは、下図のようにポリゴンを描画する範囲のｘ座標の最大値と最小値を求め、その間を水平のラインで結ぶというものです。

三角形の塗りつぶし
#define	kScreenWidth	640
#define	kScreenHeight	480
short	gMinMaxTable[kScreenHight *2];

void FillTriangle(Triangle* tri, UInt8 indexColor){
	SInt16	yArray[3];
	SInt16	maxY, minY;
	int	y;

	yArray[0] = tri->pt[0].y;
	yArray[1] = tri->pt[1].y;
	yArray[2] = tri->pt[2].y;
	
	maxY = MaxSInt16(yArray, 3);	// 三角形のy座標の最大値を求める
	minY = MinSInt16(yArray, 3);	// 三角形のy座標の最小値を求める
	
	// テーブルの初期化
	for(y = minY; y <= maxY; y++){
		gMinMaxTable[y*2] = 0x7fff;	// 最小値として32767を設定
		gMinMaxTable[y*2 +1] = 0x8000;	// 最大値として-32768を設定
	}
	
	// Min-Maxテーブルを設定
	SetMinMax(tri->pt[0], tri->pt[1]);
	SetMinMax(tri->pt[1], tri->pt[2]);
	SetMinMax(tri->pt[2], tri->pt[0]);
	
	// 水平ラインの描画
	minY = (minY > 0)? minY: 0;
	maxY = (maxY < kScreenHeight)? maxY: kScreenHeight -1;
	for(y = minY; y <= maxY; y++){
		if(gMinMaxTable[y*2] < 0)
			gMinMaxTable[y*2] = 0;
		if(gMinMaxTable[y*2 +1] >= kScreenWidth)
			gMinMaxTable[y*2 +1] = kScreenWidth -1;
		if(gMinMaxTable[y*2 +1] < gMinMaxTable[y*2])
			continue;
		Line(gMinMaxTable[y*2], y, gMinMaxTable[y*2 +1], y);
	}
}

　さて、問題はどうやってｘ座標の最大値と最小値を求めるかですが、これにはブレゼンハムのアルゴリズムといわれる直線描画アルゴリズムを使用します。ここで真面目な解説書ならブレゼンハムのアルゴリズムを詳しく解説するところですが（というより、まず最初にブレゼンハムのアルゴリズムを解説することから始める）、この記事はいい加減なので、出来合いのプログラムに手を加えることにします。元となるプログラムは名著、『Ｃ言語によるアルゴリズム大事典第２版』の”グラフィックス”の項にあるプログラムです。
＃ブレゼンハムのアルゴリズムは簡単で、しかも応用がきくので
＃是非身に付けてください。ＣＧ関係の入門書には大抵解説が載っています。

void SetMinMax(Vertex2 pt1, Vertex2 pt2){
	int	dx, dy, s, step;
	
	dx = pt1.h -pt2.x;	if(dx < 0)	dx = -dx;
	dy = pt1.y -pt2.y;	if(dy < 0)	dy = -dy;
	
	if(dx > dy){
		if(pt1.x > pt2.x){
			step = (pt1.y > pt2.y)? 1: -1;
			s = pt1.x;
			pt1.x = pt2.x;
			pt2.x = s;
			pt1.y = pt2.y;
		}else{
			step = (pt1.y < pt2.y)? 1: -1;
		}
		
		if(pt1.y > 0 && pt1.y < kMaxHeight){
			if(pt1.x < gMinMaxTable[pt1.y*2])
				gMinMaxTable[pt1.y*2] = pt1.x;
			if(pt1.x > gMinMaxTable[pt1.y*2 +1])
				gMinMaxTable[pt1.y*2 +1] = pt1.x;
		}
		
		s = dx >>1;
		while(++pt1.x <= pt2.x){
			if((s -= dy) < 0){
				s += dx;
				pt1.y += step;
			}
			
			if(pt1.y > 0 && pt1.y < kMaxHeight){
				if(pt1.x < gMinMaxTable[pt1.y*2])
					gMinMaxTable[pt1.y*2] = pt1.x;
				if(pt1.x > gMinMaxTable[pt1.y*2 +1])
					gMinMaxTable[pt1.y*2 +1] = pt1.x;
			}
		}
	}else{
		if(pt1.y > pt2.y){
			step = (pt1.x > pt2.x)? 1: -1;
			s = pt1.y;
			pt1.y = pt2.y;
			pt2.y = s;
			pt1.x = pt2.x;
		}else{
			step = (pt1.x < pt2.x)? 1: -1;
		}
		
		if(pt1.y > 0 && pt1.y < kMaxHeight){
			if(pt1.x < gMinMaxTable[pt1.y*2])
				gMinMaxTable[pt1.y*2] = pt1.x;
			if(pt1.x > gMinMaxTable[pt1.y*2 +1])
				gMinMaxTable[pt1.y*2 +1] = pt1.x;
		}
		
		s = dy >>1;
		while(++pt1.y <= pt2.y){
			if((s -= dx) < 0){
				s += dy;
				pt1.x += step;
			}
			
			if(pt1.y > 0 && pt1.y < kMaxHeight){
				if(pt1.x < gMinMaxTable[pt1.y*2])
					gMinMaxTable[pt1.y*2] = pt1.x;
				if(pt1.x > gMinMaxTable[pt1.y*2 +1])
					gMinMaxTable[pt1.y*2 +1] = pt1.x;
			}
		}
	}
}

　これで、ポリゴン一個を描画することができました。

目次
LEVEL 0:点| LEVEL 2:光源一個