入門四叉木の例

概要: 
      四叉樹の読書ノート
     ソース:http://www.pudn.com/downloads343/sourcecode/windows/opengl/detail1500968.html
 
本文:
      まず四叉木構造

typedef struct _QNode_{

	unsigned int	*m_tri_indexes;				//       
	
	unsigned int	m_num_triangles;			//           ，   0

	Vector3	        m_min, m_max;		                 //X Z       

	struct _QNode_	*m_children[4];				//       


}QNode;

基礎地形データの作成:
    Row*Colのメッシュを作成するには、(Row-1)*(Col-1)有効な3 D頂点、(Row-1)*(Col-1)を含むことは間違いありません. * 2つの三角形1つのメッシュは2つの三角形で表され、これらの三角形を表すには (Row-1) * (Col-1)  * 2*3個のインデックスで表されます.
   なお、本例では、図に示すように、三角形インデックス頂点の格納順序を採用している.
             三角形インデックスシーケンスは、1つのメッシュを例に右上隅三角形(i,j),(i+1,j+1),(i+1,j+0),
左下隅三角形(i,j+1),(i+1,j+1),(i,j)インデックスシーケンスは連続三角形(最初の頂点をマーク)を格納し,
順番に類推.....
ノードツリーの作成
 
1四叉木は上から下にかけて作られ、ルートノードから始まり、頂点のX,Zを遍歴することで、地形全体の大きさをルートノードに割り当てます.
 
2、ルートノードはボックス幅が高く、ボックスを囲む開始位置に応じて4つのサブノードに分割する.サブノードのボックスを囲む対応する位置に含まれる三角パッチの数を一度に判断して分割を継続するか否かを決定し、本例の分割三角パッチ数は500個である
 
マスター:サブノードに実際の三角パッチを追加するたびに、メッシュ全体を巡回する必要があります.効率を向上させるために、すでにアーカイブされている三角頂点を保存するようにマークされ、頂点の巡回中に巡回した頂点を事前にフィルタします.
頂点インデックスはよく判断されます.元の頂点インデックスは、最初の頂点で三角パッチを決定します.インデックスは、ある頂点がボックスを囲んでいることを知っていれば、後ろに2つのインデックスが連続して三角パッチを構成する3つのインデックスです.
 
これで頂点は四叉木にコンパイルされます
レンダーに入る
まずルートノードに入ります.
1現在の視点(POV)がノードの範囲内にあるかどうかを判断します.
2現在の視点からノードまでの距離が最小視距離を超えているかどうかを判断し、そうであればレンダリングを終了します.
ここでは、視点からノード(平面がボックスを囲む距離)を判断する方法について説明します.
:平面でボックスを囲む4本の線を計算し、視点から線までの距離を順次判断し、最短点を取り、
最短距離は、ボックスの中心平面を囲むビューポイントの投影ではありませんか?
3 4つの頂点を囲む方向と視点(POV)方向の角度が82度を超える場合は、レンダーを終了します.
レンダリング技術点:
点から線までの最短距離判断

void QuadTree::ClosestPointOnLine(Vector3 *start, Vector3 *end, Vector3 *point, Vector3 *result)
{
    Vector3  c,                          // vector from a->p
            ev,                         // vector from a->b
            pv;                         // projection of a->p onto a->b

    float   d,                          // length of vector from a->b (distance from start to end of line)
            t;                          // amount of c that projects onto ev

    // Get vector from point to start of line
	c.x = point->x - start->x;
	//c.y = point->y - start->y;			//quick speedup. Quadtrees ignore Y!
	c.z = point->z - start->z;

	
    // Get edge vector
	ev.x = end->x - start->x;
	//ev.y = end->y - start->y;				//quick speedup. Quadtrees ignore Y!
	ev.z = end->z - start->z;

    

    // find length of ev
	d = sqrtf(ev.x*ev.x + ev.z*ev.z);		//quick speedup. Quadtrees ignore Y!
    
    // Normalise ev
    ev.x /= d;
    //ev.y /= d;							//quick speedup. Quadtrees ignore Y!
    ev.z /= d;

    // Calculate projection of vector from start to point (c) onto line (ev)
	t = (ev.x*c.x) + (ev.z*c.z);			//quick speedup. Quadtrees ignore Y!
    

    // Check that projection amount (t) is within range 0 < t < d
    // n.b. 0 = start of line, d = length of line
    if (t < 0)
    {
        // closest point is start of line
        *result = *start;
        return;
    }

    if (t > d)
    {
        // closest point is end of line
        *result = *end;
        return;
    }

    // Closest point is somewhere on the line
    // Calculate projected vector using amount & normalised edge vector
	pv.x = ev.x * t;
	//pv.y = ev.y * t;						//quick speedup. Quadtrees ignore Y!
	pv.z = ev.z * t;

	

    // Closest point on line is start + projected vector
	result->x = start->x + pv.x;
	//result->y = start->y + pv.y;			//quick speedup. Quadtrees ignore Y!
	result->y = 0.0f;
	result->z = start->z + pv.z;
}

ノード視距離の角度判断

bool QuadTree::NodeIsBehind(QNode *node, Vector3 *pos, Vector3 *at)
{
	//Calculate the angle from at, to node corners.

	Vector3 points[4], v;


	points[0].x = node->m_min.x;
	points[0].z = node->m_min.z;

	points[1].x = node->m_max.x;
	points[1].z = node->m_min.z;

	points[2].x = node->m_min.x;
	points[2].z = node->m_max.z;

	points[3].x = node->m_max.x;
	points[3].z = node->m_max.z;



	for(int i=0; i<4; i++)
	{
		v.x = points[i].x - pos->x;
		v.z = points[i].z - pos->z;

		//normalize.
		float mag = (v.x * v.x) + (v.z * v.z);
		mag = 1.0f / sqrtf(mag);

		v.x *= mag;
		v.z *= mag;

		//do dot product.
		float dot = (v.x * at->x) + (v.z * at->z);

		float angle = (float) acos(dot);

		angle *= 180.0f / 3.14592f;

		if(angle < 82.0f)
		{
			return false;
		}
	}

	return true;

}

視点(POV)からノードがボックスを囲むまでの距離

float QuadTree::DistFromPoint(QNode *node, Vector3 *pos)
{//This function calcs the distance between pos, and the node, at the closest point, checks all 4 lines aroun
 //bounding box of node.

	Vector3 v, points[4], p;
	float distance[4], ret_dist;
	int i;


	//Get the 4 points of the bounding box.
	points[0].x = node->m_min.x;			points[0].z = node->m_min.z;
	points[1].x = node->m_max.x;			points[1].z = node->m_max.z;

	points[2].x = node->m_min.x;			points[2].z = node->m_max.z;
	points[3].x = node->m_max.x;			points[3].z = node->m_min.z;


	// speedup hacks here, by ignoring Y.
	ClosestPointOnLine(&points[0], &points[3], pos, &p);
	v.x = p.x - pos->x;
	v.z = p.z - pos->z;
	distance[0] = (v.x * v.x) + (v.z * v.z);

	ClosestPointOnLine(&points[0], &points[2], pos, &p);
	v.x = p.x - pos->x;
	v.z = p.z - pos->z;
	distance[1] = (v.x * v.x) + (v.z * v.z);

	ClosestPointOnLine(&points[1], &points[3], pos, &p);
	v.x = p.x - pos->x;
	v.z = p.z - pos->z;
	distance[2] = (v.x * v.x) + (v.z * v.z);

	ClosestPointOnLine(&points[2], &points[1], pos, &p);
	v.x = p.x - pos->x;
	v.z = p.z - pos->z;
	distance[3] = (v.x * v.x) + (v.z * v.z);


	ret_dist = distance[0];

	for(i=1; i<4; i++)
	{
		if(distance[i] < ret_dist)
		{
			ret_dist = distance[i];
		}
		
	}

	ret_dist = sqrtf(ret_dist);			//Square root it.
	/*printf("
 distance to camera = %f ", ret_dist);*/
	return ret_dist;
}

主に何をしましたか.
1頂点データ、三角データを四叉木構造で整理
2視点と四叉木の囲い箱によるデータフィルタリング、最適化ロード
 
欠点:
1、LODなし
2,スクリーニング判定が単純すぎるのは,主にノード包囲ボックスと視距の距離判定,特にノードが視距範囲内であるか否かの判定に現れる.
3、データは一度にメモリにロードされ、ビッグデータに対して黙ってすべての頂点をメモリに入れることができます.