--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Renderer/Engine/task/CreateSpan.cc	Mon Oct 12 09:39:35 2009 +0900
@@ -0,0 +1,510 @@
+#include "CreateSpan.h"
+#include "viewer_types.h"
+
+static const int SPAN_PACK_LOAD    =  5;
+static const int SPAN_PACK_STORE   =  6;
+static const int POLYGON_PACK_LOAD =  7;
+static const int TILE_ALLOCATE     =  8;
+static const int TILE_LOAD         =  9;
+static const int TILE_STORE        = 10;
+
+static SpanPackPtr spack = NULL;
+static SpanPackPtr send_spack = NULL;
+static int prev_index = 0;
+
+SchedDefineTask(CreateSpan);
+
+static float
+calc(float f1, float f2,int i, float base)
+{
+    float ans;
+    ans = f1/f2*i + base;
+    return ans;
+}
+
+
+/**
+ * TrianglePack から、vMin, vMid, vMax を求める
+ *
+ * @param [triPack] TrianglePack
+ * @param [vMin] [vMid] [vMax]
+ */
+static void
+make_vertex(TrianglePack *triPack,
+	    VertexPackPtr *vMin, VertexPackPtr *vMid, VertexPackPtr *vMax,
+            NormalPackPtr *normal1, NormalPackPtr *normal2, NormalPackPtr *normal3)
+{
+    if (triPack->ver1.y <= triPack->ver2.y) {
+	if (triPack->ver2.y <= triPack->ver3.y) {
+	    *vMin = &triPack->ver1;
+	    *vMid = &triPack->ver2;
+	    *vMax = &triPack->ver3;
+	} else if (triPack->ver3.y <= triPack->ver1.y) {
+	    *vMin = &triPack->ver3;
+	    *vMid = &triPack->ver1;
+	    *vMax = &triPack->ver2;
+	} else {
+	    *vMin = &triPack->ver1;
+	    *vMid = &triPack->ver3;
+	    *vMax = &triPack->ver2;
+	}
+    } else {
+	if (triPack->ver1.y <= triPack->ver3.y) {
+	    *vMin = &triPack->ver2;
+	    *vMid = &triPack->ver1;
+	    *vMax = &triPack->ver3;
+	} else if (triPack->ver3.y <= triPack->ver2.y) {
+	    *vMin = &triPack->ver3;
+	    *vMid = &triPack->ver2;
+	    *vMax = &triPack->ver1;
+	} else {
+	    *vMin = &triPack->ver2;
+	    *vMid = &triPack->ver3;
+	    *vMax = &triPack->ver1;
+	}
+    }
+
+    *normal1 = &triPack->normal1;
+    *normal2 = &triPack->normal2;
+    *normal3 = &triPack->normal3;
+
+}
+
+static void
+make_vMid10(VertexPack *v, VertexPack *vMin,
+	    VertexPack *vMid, VertexPack *vMax)
+{
+    //int d, d1;
+    float d;
+    int d1;
+    
+    d  = vMax->y - vMin->y;
+    d1 = (int)(vMid->y - vMin->y);
+
+    v->tex_x  = calc(vMax->tex_x - vMin->tex_x, d, d1, vMin->tex_x);
+    v->tex_y  = calc(vMax->tex_y - vMin->tex_y, d, d1, vMin->tex_y);
+    v->x      = calc(vMax->x - vMin->x, d, d1, vMin->x);
+    v->y      = vMid->y;
+    v->z      = calc(vMax->z - vMin->z, d, d1, vMin->z);
+}
+
+/**
+ * 与えられた scale から、実際に使うテクスチャの Tapestry を選択する
+ *
+ * テクスチャは、オリジナルのサイズから、可能なかぎり 1/2 で縮小していき、
+ * 下の図の様に連続した領域に入れられる
+ *
+ *   Tapestry (1)
+ * +---+---+---+---+
+ * | 0 | 1 | 2 | 3 |
+ * +---+---+---+---+
+ * | 4 | 5 | 6 | 7 |     (2)
+ * +---+---+---+---+  +---+---+
+ * | 8 | 9 | 10| 11|  | 16| 17|   (3)
+ * +---+---+---+---+  +---+---+  +---+
+ * | 12| 13| 14| 15|  | 18| 19|  | 20|
+ * +---+---+---+---+  +---+---+  +---|
+ *
+ * (1)                                                 (2)             (3)
+ *  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+ *  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | * | * | * | 14| 15| 16| 17| 18| 19| 20|
+ *  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+ *
+ * scale の値から、各 Tapestry の先頭アドレスを返す
+ *
+ * @param[in] tw       Width of texture
+ * @param[in] th       Height of texture
+ * @param[in] scale    テクスチャの縮小率 (= 2^n)
+ * @param[in] addr_top テクスチャの先頭アドレス (上の図での (1)
+ * @return scale に対応する Tapestry のアドレス (上の図での (1) or (2) or(3)
+ */
+static uint32*
+getTapestry(int tw, int th, int scale, uint32 *addr_top)
+{
+    int index = 0;
+
+    for (int s = 1; s < scale; s <<= 1) {
+	index += tw*th;
+	tw >>= 1; /* tw /= 2 */
+	th >>= 1;
+    }
+
+    return addr_top + index;
+}
+
+
+/**
+ * span の width,height と texture の width,height を比べて
+ * span を描画する際に使う texture の比率を求める
+ *
+ * @param[in] width      Width of span
+ * @param[in] height     Height of span
+ * @param[in] tex_width  Width of 1/1 texture that span use
+ * @param[in] tex_height Height of 1/1 texture that span use
+ * @param[in] scale_max  この Span で使う texture の最大縮小率
+ *                   計算結果が scale_max 以上になるのを防ぐ
+ * @return 描画に使う texture の比率
+ *         width と height は 1/scale の画像を使う
+ *
+ */
+static int
+getScale(int width, int height, int tex_width, int tex_height, int scale_max)
+{
+    int base, tex_base;
+    int scale = 1;
+
+    /**
+     * width と height で、長い方を基準に、
+     * texture の scale を決める
+     */
+    if (width > height) {
+	base = width;
+	tex_base = tex_width;
+    } else {
+	base = height;
+	tex_base = tex_height;
+    }
+
+    if (tex_base > base) {
+	int t_scale = tex_base/base;
+	while (t_scale >>= 1) {
+	    scale <<= 1;
+	}
+    }
+
+    return (scale > scale_max) ? scale_max : scale;
+    //return scale_max;
+}
+
+/**
+ * x軸に水平な辺を持つ三角形ポリゴンから、
+ * Span を抜き出す
+ *
+ * @param[in] spackList    triangle から生成された span を格納する List
+ * @param[in] charge_y_top 担当する y の範囲開始地点
+ * @param[in] charge_y_end 担当する y の範囲終了地点
+ * @param[in] tex_addr     triangle が参照するテクスチャの先頭アドレス
+ * @param[in] tex_width    テクスチャの width
+ * @param[in] tex_height   テクスチャの height
+ * @param[in] tex_scale_max  テクスチャの最大縮小率 (2^n)
+ * @param[in] vMin     triangle の座標
+ * @param[in] vMid     triangle の座標。triangle を二つに分けて出来た新しい座標
+ * @param[in] vMid10   triangle の座標
+ * @param[in] length_y  分割する前の Triangle の y の長さ
+ * @param[in] tex_y_len 分割する前の Triangle に貼られている Texture の
+ *                      長さの割合 (0 ... 1)
+ */
+static void
+half_triangle(SchedTask *smanager, SpanPackPtr *spackList,
+			  int charge_y_top, int charge_y_end,
+			  TriangleTexInfoPtr tex_info,
+			  VertexPack *vMin,VertexPack *vMid,VertexPack *vMid10,
+                          NormalPack *normal1, NormalPack *normal2, NormalPack *normal3,
+			  int length_y, float tex_y_len)
+{
+    float tmp_z,tmp_tex1, tmp_tex2 ,tmp_tey1,tmp_tey2;
+    float tmp_xpos,tmp_end,tmp_zpos;
+    float start_z, end_z;
+    float start_tex_x, end_tex_x, start_tex_y, end_tex_y;
+    int x, y, length;
+
+#if 1
+    // これじゃないと
+    // テクスチャの貼りに微妙に隙間が。謎だ
+    int start_y = (int)vMid->y;
+    int end_y   = (int)vMin->y;
+#else
+    float start_y = vMid->y;
+    float end_y   = vMin->y;
+#endif
+    float div_y = start_y - end_y;
+    int k = 0;
+    int l = 1;
+
+    SpanPackPtr tmp_spack;
+
+    /**
+     * 三角形ポリゴンをx軸に水平に二つに分けようとして
+     * ある一辺がすでに水平だった場合、つまり
+     *
+     * |\
+     * | \
+     * |  \
+     * -----
+     *
+     *
+     * 上のようなポリゴンだった場合は、本来なら上の部分の三角形にだけ
+     * half_triangle の処理をするべきだが、現在の処理だと
+     * この half_triangle に「上の部分の三角形」と、
+     * 「『下の部分の三角形と判断してしまった』直線」が来てしまう。
+     * 直線の部分が来ると、calc() で 0 除算とかで、値不定で暴走するので
+     * 現在はこれで代用。
+     * half_triangle 呼ぶ前にこれを判断できれば良いかもしれない。
+     * てかこんなんでいいのかよ。。。
+     */
+#if 1
+    if ((int)div_y == 0) {
+	return;
+    }
+#else
+    if (vMid10->x == vMin->x && vMid10->y == vMin->y) {
+	return;
+    }
+#endif
+
+    if (div_y < 0) {
+	div_y = -div_y;
+	k = 1;
+	l = -1;
+    }
+
+    for (int i = k; i < (int)div_y+1; i++) {
+	y = (int)vMin->y + i*l;
+#if 1
+
+	/**
+	 * 担当 y 範囲内
+	 */
+	if (charge_y_top <= y && y <= charge_y_end) {
+	    // 1..8 を index0, 9..16 を index1 にするために y を -1
+	    int index = (y-1) / split_screen_h;
+
+	    /**
+	     * 違う SpanPack を扱う場合、
+	     * 現在の SpanPack をメインメモリに送り、
+	     * 新しい SpanPack を取ってくる
+	     */
+	    if (index != prev_index) {
+		tmp_spack = spack;
+		spack = send_spack;
+		send_spack = tmp_spack;
+
+		smanager->dma_wait(SPAN_PACK_STORE);
+		smanager->dma_store(send_spack, (uint32)spackList[prev_index],
+				    sizeof(SpanPack), SPAN_PACK_STORE);
+		
+		smanager->dma_load(spack, (uint32)spackList[index],
+				   sizeof(SpanPack), SPAN_PACK_LOAD);
+		prev_index = index;
+		smanager->dma_wait(SPAN_PACK_LOAD);
+	    }
+
+	    /**
+	     * 書き込む SpanPack が満杯だったら
+	     * メインメモリで allocate した領域 (next) を持ってきて
+	     * 現在の spack->next につなぎ、next を次の spack とする。
+	     */
+	    if (spack->info.size >= MAX_SIZE_SPAN) {
+		SpanPackPtr next;
+		
+		smanager->mainMem_alloc(0, sizeof(SpanPack));
+		smanager->mainMem_wait();
+		next = (SpanPackPtr)smanager->mainMem_get(0);
+		
+		spack->next = next;
+
+		tmp_spack = spack;
+		spack = send_spack;
+		send_spack = tmp_spack;
+
+		smanager->dma_wait(SPAN_PACK_STORE);
+		smanager->dma_store(send_spack, (uint32)spackList[index],
+				    sizeof(SpanPack), SPAN_PACK_STORE);
+
+		spackList[index] = next;
+		
+		smanager->dma_load(spack, (uint32)spackList[index],
+				   sizeof(SpanPack), SPAN_PACK_LOAD);
+		smanager->dma_wait(SPAN_PACK_LOAD);
+		spack->init((index+1)*split_screen_h);
+	    }
+	} else {
+	    /**
+	     * 担当範囲外だったら無視
+	     */
+	    continue;
+	}
+	
+	tmp_xpos = calc(vMid10->x - vMin->x ,div_y, i, vMin->x);
+	tmp_end  = calc(vMid->x  - vMin->x ,div_y, i, vMin->x);
+	tmp_z    = calc(vMid10->z - vMin->z ,div_y, i, vMin->z);
+	tmp_zpos = calc(vMid->z  - vMin->z ,div_y, i, vMin->z);
+
+	length = (tmp_xpos > tmp_end)
+	    ? (int)tmp_xpos - (int)tmp_end : (int)tmp_end - (int)tmp_xpos;
+	if (length == 0) {
+	    continue;
+	}
+
+	tmp_tex1 =((i/(div_y)) * vMid10->tex_x) +
+	    ( ((div_y - i)/(div_y)) * vMin->tex_x);
+	tmp_tex2 =( (i/(div_y)) * vMid->tex_x) +
+	    ( ((div_y - i)/(div_y)) * vMin->tex_x);
+
+	tmp_tey1 =( (i/(div_y)) * vMid10->tex_y) +
+	    ( ((div_y - i)/(div_y)) * vMin->tex_y);
+	tmp_tey2 =( (i/(div_y)) * vMid->tex_y) +
+	    ( ((div_y - i)/(div_y)) * vMin->tex_y);
+
+	if (tmp_xpos > tmp_end) {
+	    x = (int)tmp_end;
+	    length = (int)(tmp_xpos)-(int)(tmp_end)+1;
+	    start_z = tmp_zpos;
+	    end_z = tmp_z;
+	    start_tex_x = tmp_tex2;
+	    end_tex_x = tmp_tex1;
+	    start_tex_y = tmp_tey2;
+	    end_tex_y = tmp_tey1;
+	} else {
+	    x = (int)tmp_xpos;
+	    length = (int)(tmp_end)-(int)(tmp_xpos)+1;
+	    start_z = tmp_z;
+	    end_z = tmp_zpos;
+	    start_tex_x = tmp_tex1;
+	    end_tex_x = tmp_tex2;
+	    start_tex_y = tmp_tey1;
+	    end_tex_y = tmp_tey2;
+	}
+
+	smanager->dma_wait(SPAN_PACK_LOAD);
+
+	Span *span = &spack->span[spack->info.size++];
+
+	span->x          = x;
+	span->y          = y;
+	span->length_x   = length;
+	span->start_z    = start_z;
+	span->end_z      = end_z;
+	span->tex_x1     = start_tex_x;
+	span->tex_x2     = end_tex_x;
+	span->tex_y1     = start_tex_y;
+	span->tex_y2     = end_tex_y;
+        /*ここで頂点分法線ベクトルがあったんだけど、
+         * 一つだけ取り出して、spanに一つの法線ベクトルを持たしている
+         *by yutaka
+         */
+        span->normal_x    = normal1->x;
+        span->normal_y    = normal1->y;
+        span->normal_z    = normal1->z;
+
+
+	float tex_x_len = span->tex_x2 - span->tex_x1;
+
+	/**
+	 * tex_x_len, tex_y_len を掛ける理由は
+	 * Changelog の 2008-12-16 を参照
+	 */
+	int scale = getScale(span->length_x, length_y,
+			     (int)(span->tex_width*tex_x_len),
+			     (int)(span->tex_height*tex_y_len),
+			     tex_info->scale_max);
+	//scale = tex_info->scale_max;
+	
+	uint32 *tapestry = getTapestry(tex_info->width,
+				       tex_info->height, scale,
+				       tex_info->addr);
+	span->tex_addr   = tapestry;
+	span->tex_width  = tex_info->width/scale;
+	span->tex_height = tex_info->height/scale;
+    }
+#else
+    
+    /**
+     * ここに SIMD 化した記述をしようとして断念
+     */
+
+#endif
+
+}
+
+
+static int
+run(SchedTask *smanager, void *rbuf, void *wbuf)
+{
+    PolygonPack *pp = (PolygonPack*)smanager->get_input(0);
+    PolygonPack *next_pp = 
+	(PolygonPack*)smanager->allocate(sizeof(PolygonPack));
+    PolygonPack *free_pp = next_pp;
+    PolygonPack *tmp_pp;
+
+    TrianglePackPtr triPack;
+    VertexPackPtr vMin, vMid, vMax;
+    VertexPackPtr vMid10
+	= (VertexPackPtr)smanager->allocate(sizeof(VertexPack));
+    NormalPackPtr normal1,normal2, normal3;
+    SpanPackPtr *spackList = (SpanPackPtr*)smanager->get_input(1);
+    spack = (SpanPackPtr)smanager->get_input(2);
+    send_spack = (SpanPackPtr)smanager->allocate(sizeof(SpanPack));
+    prev_index = smanager->get_param(0);
+
+    // spack と send_spack は swap しながら DMA を繰り返すので
+    // 自分で allocate した send_spack を覚えてないといけない
+    SpanPackPtr free_spack = send_spack;
+
+    int charge_y_top = smanager->get_param(1);
+    int charge_y_end = smanager->get_param(2);
+
+    do {
+	if (pp->next != NULL) {
+	    smanager->dma_load(next_pp, (uint32)pp->next,
+			       sizeof(PolygonPack), POLYGON_PACK_LOAD);
+	} else {
+	    next_pp = NULL;
+	}
+
+	for (int i = 0; i < pp->info.size; i++) {
+	    triPack = &pp->tri[i];
+
+	    TriangleTexInfoPtr tri_tex_info = &triPack->tex_info;
+
+	    make_vertex(triPack, &vMin, &vMid, &vMax, &normal1, &normal2, &normal3);
+	    make_vMid10(vMid10, vMin, vMid, vMax);
+
+	    /**
+	     * ポリゴンを、x軸に水平に分割して二つの三角形を作り、
+	     * それぞれから Span を求める
+	     *
+	     *      vMax
+	     *        |\
+	     *        | \
+	     *        |  \
+	     *        |   \
+	     * vMid10 ------ vMid
+	     *        |   /
+	     *        |  /
+	     *        | /
+	     *        |/
+	     *      vMin
+	     *
+	     * (vMax, vMid, vMin) という triangle を
+	     * (vMax, vMid, vMid10) (vMin, vMid, vMid10) という
+	     * 二つの Triangle に分けている
+	     */
+	    half_triangle(smanager, spackList, charge_y_top, charge_y_end,
+			  tri_tex_info, vMin, vMid, vMid10,
+                          normal1,normal2,normal3,
+			  (int)(vMax->y - vMin->y), vMax->tex_y - vMin->tex_y);
+	    half_triangle(smanager, spackList, charge_y_top, charge_y_end,
+			  tri_tex_info, vMax, vMid, vMid10,
+                          normal1,normal2,normal3,
+			  (int)(vMax->y - vMin->y), vMax->tex_y - vMin->tex_y);
+	}
+
+	smanager->dma_wait(POLYGON_PACK_LOAD);	
+
+	tmp_pp = pp;
+	pp = next_pp;
+	next_pp = tmp_pp;
+    } while (pp);
+
+    smanager->dma_wait(SPAN_PACK_STORE);
+    smanager->dma_store(spack, (uint32)spackList[prev_index],
+			sizeof(SpanPack), SPAN_PACK_STORE);
+    smanager->dma_wait(SPAN_PACK_STORE);
+
+    free(free_pp);
+    free(free_spack);
+    free(vMid10);
+
+    return 0;
+}