本篇是創建3D圖形引擎（2）的續篇，3D圖形引擎的代碼以創建游戲內核中編寫的代碼為基礎進行開發。
高級三維引擎的開發
在每幀中繪制所有的多邊形是非常低效的，為了提高處理的速度，可以僅渲染那些位于視野內的多邊形，同時應避免掃描場景中的每個多邊形來確定哪些多邊形是可見的。
如果不每幀進行搜索，又如何知道哪些多邊形是位于視野內呢？解決的方法就是將一個三維模型分解為一些較小的塊（稱為節點nodes），其容納較少的多邊形。然后將節點排列到一個特定的結構中（一棵樹），以便進行快速搜
索，并確定哪個節點是可見的，然后渲染這些可見的節點，
通過使用視錐，可以找出哪些節點是可見的。取代搜索數千個多邊形，通過搜索一個小小的節點集合，就能決定怎樣進行繪制。節點樹引擎適用于任何的網格模型，并將它拆分為節點，以便快速渲染網格模型（網格模型代表了游戲的層次）。
NodeTree引擎的介紹
NodeTree引擎非常通用，因為它可以在兩種不同的模式下操作（對于節點的拆分）：四叉樹（quadtree）和八叉樹（octree）模式。四叉樹模式將世界（及隨后的節點）一次拆分為4個節點，這種模式最適合y軸變化不大的層次網格模型（即觀察點的高度并沒有太大的變化）。而八叉樹將世界（及隨后的節點）一次拆分為8個節點，使用這種模式，大型三維網格模型中的觀察點可以被移動到世界中的任意位置。如下圖所示：
使用哪一種拆分模式由自己決定，考慮自己的網格模型，是否要搜索一座城堡，或者進入一個洞穴，或在風景中漫游？如果網格模型在高度上并沒有太大的變化（例如風景），四叉樹模式最好。如果網格模型的每一條軸線都要擴展開來（例如一個擁有許多層次的城堡），則適合使用八叉樹模式。
世界（它被表示為包含了所有多邊形的一個立方體）可以不斷地被拆分為更小的、尺寸大小相同的節點。四叉樹在二維空間中將節點進行拆分（使用x軸和z軸），而八叉樹在三維空間中將節點進行拆分（使用所有的軸線）。一個節點代表了一組多邊形，同時也代表了三維空間中的一個區域。每個節點可以包含另外的節點，而每個其后的節點也可以成為一個更小節點的父節點。通常，三維世界被認為是根節點（root
node，最頂層的節點，其他所有的節點都屬于它）。對于節點和樹，有一些技巧，通過確定哪些多邊形被包含在一個節點的三維空間里，可以將它們進行分組，然后從根節點開始，可以快速遍歷樹中的每個節點。
創建節點和樹
創建節點并構造樹形結構，需要先對網格模型中的每個多邊形進行檢查，只需做一次檢查而已，所以它不會成為影響渲染速度的一個因素。這樣做的目的是決定如何對樹中的節點進行安排。網格模型中的每個多邊形被包圍在一個盒子里（稱為框界盒子，如下圖所示）。這個盒子代表了多邊形在任何方向上的范圍，只要多邊形的盒子被包圍在一個節點的三維空間里（完全或部分的），那么該多邊形就屬于這個節點，一個多邊形可以屬于多個節點，因為多邊形的范圍可能會穿過許多節點。
將多邊形分組為節點時，需注意多邊形所在的空間是否很大，或者在一個很大的空間中是否有太多的多邊形，如果是就需要將節點拆分為更多的子節點，然后再次搜索多邊形列表，將新的節點放入計算，繼續這個處理過程，直到所有的多邊形的分組足夠小，并且每個包含的多邊形樹也足夠少。為了優化樹形結構，放棄所有那些沒有包含多邊形的節點，刪除空的節點可以節省內存，同時可以加快樹形結構的搜索。
如下圖所示，可以將根節點拆分為4個較小的節點（使之成為一個四叉樹的節點），然后檢測每個節點，并不斷地拆分其中較大的節點，跳過空節點以便加快處理速度，最后得到一個完美的樹形結構以
方便以后搜索。
搜索及繪制樹
如果構成三維空間節點的那8個頂點中的任一個（可以被看作是立方體的拐角）位于視錐內，或者如果視錐自身是被包含在一個節點里，那么該節點就被認為是位于視野之內的。在確定了一個節點是可見的之后，對它的子節點（如果有的話）執行同樣的檢測，如果一個節點并不包含子節點，則檢測當前節點是否包含了沒有被繪制的多邊形。當一個節點中的多邊形被繪制后，它們被標識為已被繪制，并返回父節點，同時搜索其余的子節點。在處理過程中可以看到，較高層次的節點連同它們的子節點一起被拋棄，以這種方式，就可以在渲染過程中刪除數千的多邊形，從而節省時間。如果一個節點被完全地包含在視錐里，那
就可以不用再搜索節點的任何子節點，因為他們也完全被包含在視錐里了。
當使用Direct3D和樹形結構時，會發現一個網格模型可以包含多重的材質，但轉換材質會是開銷很大的操作（特別當每個材質使用了不同的紋理時），因此要謹慎處理。那么如何繪制所有可見的多邊形，又不用一次又一次地轉換材質呢（即使材質已經被使用了）？這就是材質分組的作用。材質分組（material
group）就是多邊形的集合，根據它們所指定的材質被分組到一起。因為一個網格模型可以包含多重材質，所以在一個指定的時間中，僅渲染那些屬于指定材質的多邊形分組。以這種方式，僅需要設置一次所使用的材質（以及隨后的紋理，如果存在的話），渲染使用材質的多邊形，并繼續處理下一個材質。
盡管材質分組的使用聽起來合乎邏輯，但多邊形根據材質進行分組使其很難處理NodeTree信息，不對樹形結構進行搜索就不知道哪些多邊形將被繪制。所以必須搜索樹形結構，并構造需要被渲染的多邊形列表。完成搜索后，僅檢測那些屬于材質的多邊形列表，并使用它們。材質分組并沒有什么影響，只是要那些被繪制的多邊形更有次序。
創建NedeTree類
定義：
typedef unsigned long ulong;
typedef unsigned short ushort;
typedef unsigned char uchar;
typedef char* char_ptr;
typedef const char* pcstr;
typedef unsigned long* ulong_ptr;
typedef unsigned short* ushort_ptr;
// enumerate the two types of tree structures
enum TREE_TYPES { QUADTREE = 0, OCTREE };
//=====================================================================================
// This calss encapsulate how to divide world space.
//=====================================================================================
typedef class NODE_TREE_MESH
{
private:
// The VERTEX_INFO structure is a custom vertex structure than contains only the 3D coordinates.
// This is used to retrieve coordinate information from a mesh's vertex buffer.
typedef struct VERTEX
{
float x, y, z;
} *VERTEX_PTR;
// The POLYGON_INFO structure maintains a material group index,
// the time it was last drawn (so youo don't redraw it many times over per frame),
// and the three vertices used to render the polygon (which you'll read on later).
typedef struct POLYGON
{
ulong mg_index; // material group index
ulong render_timer;
ushort vertex_index_0;
ushort vertex_index_1;
ushort vertex_index_2;
POLYGON()
{
memset(this, 0, sizeof(*this));
}
} *POLYGON_PTR;
// The node structure keeps count of the number of polygons in its 3D space, polygon index list,
// the 3D coordinates of the node (as well as the radius, which is the distance from the center to
// one edge making the node a perfect cube), and pointers to the child nodes.
typedef struct NODE
{
float x_pos, y_pos, z_pos; // center coordinate of node
float diameter; // radius of node
ulong num_polys; // number of polygons in node
ulong_ptr poly_index_list; // polygon index list
NODE* child_nodes[8]; // child nodes information 4 = quad, 8 = oct.
// constructor used to clear out variables
NODE()
{
memset(this, 0, sizeof(*this));
}
// destructor to clear child nodes and variables
~NODE()
{
delete[] poly_index_list;
poly_index_list = NULL;
// delete child nodes
for(short i = 0; i < 8; i++)
{
delete child_nodes[i];
child_nodes[i] = NULL;
}
}
} *NODE_PTR;
// The material group structure uses IDirect3DIndexBuffer9 to store polygons vertex index
// that need to be rendered in a single frame, also it maintains the number of polygons in
// a material group and how many polygons to draw each frame.
typedef struct MATERIAL_GROUP
{
ulong num_polys; // number of polygons in group
ulong num_polys_to_draw; // number of polygons to draw
IDirect3DIndexBuffer9* index_buffer;
ushort_ptr index_ptr;
// clear out member data
MATERIAL_GROUP()
{
memset(this, 0, sizeof(*this));
}
// free index buffer
~MATERIAL_GROUP()
{
if(index_buffer)
index_buffer->Release();
index_buffer = NULL;
}
} *MATERIAL_GROUP_PTR;
private:
int m_tree_type; // type of nodetree (QUADTREE or OCTREE)
GRAPHICS_PTR m_graphics; // parent graphics object
FRUSTUM_PTR m_frustum; // viewing frustum
float m_world_cube_diameter; // diameter of world cube
float m_node_max_diameter; // maximum node diameter
NODE_PTR m_root_node; // node list
ulong m_num_mg; // number of material group
MATERIAL_GROUP_PTR m_mg_list; // material group list
ulong m_max_polys_per_node; // maximum number of polygons per node allow
ulong m_num_polys; // number of polygons in scene
POLYGON_PTR m_poly_list; // list of polygons
ulong m_render_timer; // current draw timer
S_MESH_PTR m_root_mesh; // pointer to root mesh
char_ptr m_vertex_ptr; // pointer to mesh vertices
ulong m_vertex_fvf; // mesh vertex FVF
ulong m_num_bytes_per_vertex; // num bytes per vertex
private:
void _sort_node(NODE_PTR node,
float x_pos, float y_pos, float z_pos,
float diameter);
void _add_node(NODE_PTR node);
BOOL _polygon_containe_in_node(POLYGON_PTR poly,
float x_pos, float y_pos, float z_pos,
float diameter);
ulong _count_polygons_in_node(float x_pos, float y_pos, float z_pos,
float diameter);
public:
NODE_TREE_MESH();
~NODE_TREE_MESH();
BOOL create(GRAPHICS_PTR graphics, MESH_PTR mesh,
int tree_type = OCTREE, float node_max_diameter = 256.0f, long max_polys_per_node = 32);
void free();
BOOL render(FRUSTUM_PTR frustum = NULL, float z_dist = 0.0f);
float get_closest_height(float x_pos, float y_pos, float z_pos);
float get_closest_height_below(float x_pos, float y_pos, float z_pos);
float get_closest_height_above(float x_pos, float y_pos, float z_pos);
BOOL is_ray_intersect_mesh(float x_start, float y_start, float z_start,
float x_end, float y_end, float z_end,
float* distance);
} *NODE_TREE_MESH_PTR;
實現：
//------------------------------------------------------------------------------
// Groups the polygons into nodes and splits the nodes into child nodes as needed.
//------------------------------------------------------------------------------
void NODE_TREE_MESH::_sort_node(NODE_PTR node,
float x_pos, float y_pos, float z_pos,
float diameter)
{
// error checking
if(node == NULL)
return;
// store node coordinates and size
node->x_pos = x_pos;
node->y_pos = (m_tree_type == QUADTREE) ? 0.0f : y_pos;
node->z_pos = z_pos;
node->diameter = diameter;
ulong num_polys_in_node;
// see if there are any polygons in the node
if((num_polys_in_node = _count_polygons_in_node(x_pos, y_pos, z_pos, diameter)) == 0)
return;
// split node if diameter > m_node_max_diameter and too many polygons
if(diameter > m_node_max_diameter && num_polys_in_node > m_max_polys_per_node)
{
ulong divide_node_num = (m_tree_type == QUADTREE) ? 4 : 8;
for(ulong i = 0; i < divide_node_num; i++)
{
float x_off = (((i % 2) < 1) ? -1.0f : 1.0f) * (diameter / 4);
float z_off = (((i % 4) < 2) ? -1.0f : 1.0f) * (diameter / 4);
float y_off = (((i % 8) < 4) ? -1.0f : 1.0f) * (diameter / 4);
// see if any polygons in new node boudning box
if(_count_polygons_in_node(x_pos + x_off, y_pos + y_off, z_pos + z_off, diameter / 2))
{
node->child_nodes[i] = new NODE; // create new child node
// sort the polygons with the new child node
_sort_node(node->child_nodes[i], x_pos + x_off, y_pos + y_off, z_pos + z_off, diameter / 2);
}
}
return;
}
// allocate space for vertex index
node->num_polys = num_polys_in_node;
node->poly_index_list = new ulong[num_polys_in_node];
// scan through polygon list, storing polygon index and assiging them.
ulong poly_index = 0;
for(ulong i = 0; i < m_num_polys; i++)
{
// add polygon to node list if contained in 3D space
if(_polygon_containe_in_node(&m_poly_list[i], x_pos, y_pos, z_pos, diameter))
node->poly_index_list[poly_index++] = i;
}
}
//------------------------------------------------------------------------------
// Check whether polygon is in node.
//------------------------------------------------------------------------------
BOOL NODE_TREE_MESH::_polygon_containe_in_node(POLYGON_PTR poly,
float x_pos, float y_pos, float z_pos,
float diameter)
{
// get the polygon's vertices
VERTEX_PTR vertex[3];
vertex[0] = (VERTEX_PTR) &m_vertex_ptr[m_num_bytes_per_vertex * poly->vertex_index_0];
vertex[1] = (VERTEX_PTR) &m_vertex_ptr[m_num_bytes_per_vertex * poly->vertex_index_1];
vertex[2] = (VERTEX_PTR) &m_vertex_ptr[m_num_bytes_per_vertex * poly->vertex_index_2];
float x_min, x_max, y_min, y_max, z_min, z_max;
// check against x axis of specified 3D space
x_min = min(vertex[0]->x, min(vertex[1]->x, vertex[2]->x));
x_max = max(vertex[0]->x, max(vertex[1]->x, vertex[2]->x));
if(x_max < (x_pos - diameter / 2))
return FALSE;
if(x_min > (x_pos + diameter / 2))
return FALSE;
// check against y axis of specified 3D space (only if octree tree type)
if(m_tree_type == OCTREE)
{
y_min = min(vertex[0]->y, min(vertex[1]->y, vertex[2]->y));
y_max = max(vertex[0]->y, max(vertex[1]->y, vertex[2]->y));
if(y_max < (y_pos - diameter / 2))
return FALSE;
if(y_min > (y_pos + diameter / 2))
return FALSE;
}
// check against z axis of specified 3D space
z_min = min(vertex[0]->z, min(vertex[1]->z, vertex[2]->z));
z_max = max(vertex[0]->z, max(vertex[1]->z, vertex[2]->z));
if(z_max < (z_pos - diameter / 2))
return FALSE;
if(z_min > (z_pos + diameter / 2))
return FALSE;
return TRUE;
}
//------------------------------------------------------------------------------
// Count the number of polygons in node.
//------------------------------------------------------------------------------
ulong NODE_TREE_MESH::_count_polygons_in_node(float x_pos, float y_pos, float z_pos,
float diameter)
{
// return if no polygons to process
if(m_num_polys == 0)
return 0;
// go through every polygon and keep count of those contained in the specified 3D space.
ulong poly_num_in_node = 0;
for(ulong i = 0; i < m_num_polys; i++)
{
if(_polygon_containe_in_node(&m_poly_list[i], x_pos, y_pos, z_pos, diameter))
poly_num_in_node++;
}
return poly_num_in_node;
}
//------------------------------------------------------------------------------
// Adds a node into the list of nodes to draw.
//------------------------------------------------------------------------------
void NODE_TREE_MESH::_add_node(NODE_PTR node)
{
if(node == NULL)
return;
// perform frustum check based on tree type
float y_pos;
if(m_tree_type == QUADTREE)
y_pos = 0.0f;
else
y_pos = node->y_pos;
float node_radius = node->diameter / 2;
BOOL is_completely_contained = FALSE;
if(! m_frustum->is_rectangle_in(node->x_pos, y_pos, node->z_pos,
node_radius, node_radius, node_radius,
&is_completely_contained))
{
return;
}
if(! is_completely_contained)
{
// scan child nodes
short num = 0;
ulong child_nodes_num = (m_tree_type == QUADTREE) ? 4 : 8;
for(ulong i = 0; i < child_nodes_num; i++)
{
if(node->child_nodes[i])
{
num++;
_add_node(node->child_nodes[i]);
}
}
// do not need to go on if there was child nodes in this node
if(num != 0)
return;
}
// add contained polygons (if any)
if(node->num_polys != 0)
{
for(ulong i = 0; i < node->num_polys; i++)
{
ulong poly_index = node->poly_index_list[i];
// get pointer to polygon
POLYGON_PTR poly = &m_poly_list[poly_index];
// only draw if not done already
if(poly->render_timer != m_render_timer)
{
poly->render_timer = m_render_timer;
// get material group index of polygon
ulong mg_index = poly->mg_index;
// make sure group is okay and material is not transparent
if(mg_index < m_num_mg && m_root_mesh->m_materials[mg_index].Diffuse.a != 0.0f)
{
// copy polygon's vertex indices into index buffer
*m_mg_list[mg_index].index_ptr++ = poly->vertex_index_0;
*m_mg_list[mg_index].index_ptr++ = poly->vertex_index_1;
*m_mg_list[mg_index].index_ptr++ = poly->vertex_index_2;
// increase count of polygons to draw in group
m_mg_list[mg_index].num_polys_to_draw++;
}
}
}
}
}
//------------------------------------------------------------------------------
// Constructor, initialize member data.
//------------------------------------------------------------------------------
NODE_TREE_MESH::NODE_TREE_MESH()
{
memset(this, 0, sizeof(*this));
m_tree_type = OCTREE;
}
//------------------------------------------------------------------------------
// Destructor, release allocated memory.
//------------------------------------------------------------------------------
NODE_TREE_MESH::~NODE_TREE_MESH()
{
free();
}
//------------------------------------------------------------------------------
// Release allocated memory.
//------------------------------------------------------------------------------
void NODE_TREE_MESH::free()
{
delete m_root_node;
m_root_node = NULL;
m_num_polys = 0;
delete[] m_poly_list;
m_poly_list = NULL;
m_num_mg = 0;
delete[] m_mg_list;
m_mg_list = NULL;
m_graphics = NULL;
}
//------------------------------------------------------------------------------
// Create a node-tree mesh from a source MESH object and free old node-tree mesh,
// specifying the maximum number of polygons in an area than the specific size
// which forcing node splits.
//------------------------------------------------------------------------------
BOOL NODE_TREE_MESH::create(GRAPHICS_PTR graphics, MESH_PTR mesh,
int tree_type, float node_max_diameter, long max_polys_per_node)
{
// free a prior mesh
free();
// error checking
if((m_graphics = graphics) == NULL)
return FALSE;
if(mesh == NULL || mesh->get_root_mesh()->m_num_materials == 0)
return FALSE;
// get mesh information
m_root_mesh = mesh->get_root_mesh();
ID3DXMesh* d3d_mesh = m_root_mesh->m_mesh;
m_vertex_fvf = d3d_mesh->GetFVF();
m_num_bytes_per_vertex = D3DXGetFVFVertexSize(m_vertex_fvf);
m_num_polys = d3d_mesh->GetNumFaces();
m_max_polys_per_node = max_polys_per_node;
// create the polygon list and group
m_poly_list = new POLYGON[m_num_polys];
m_num_mg = m_root_mesh->m_num_materials;
m_mg_list = new MATERIAL_GROUP[m_num_mg];
ushort_ptr index_ptr;
ulong_ptr attr_list;
// lock the index and attribute buffers
d3d_mesh->LockIndexBuffer(D3DLOCK_READONLY, (void**)&index_ptr);
d3d_mesh->LockAttributeBuffer(D3DLOCK_READONLY, &attr_list);
// load polygon information into structures
for(ulong i = 0; i < m_num_polys; i++)
{
ulong mg_index = attr_list[i]; // material group index
m_poly_list[i].vertex_index_0 = *index_ptr++;
m_poly_list[i].vertex_index_1 = *index_ptr++;
m_poly_list[i].vertex_index_2 = *index_ptr++;
m_poly_list[i].mg_index = mg_index;
m_poly_list[i].render_timer = 0;
m_mg_list[mg_index].num_polys++;
}
// unlock buffers
d3d_mesh->UnlockAttributeBuffer();
d3d_mesh->UnlockIndexBuffer();
// build the group vertex index buffers
for(ulong i = 0; i < m_num_mg; i++)
{
if(m_mg_list[i].num_polys != 0)
{
UINT index_buffer_length = m_mg_list[i].num_polys * 3 * sizeof(ushort);
m_graphics->get_device_com()->CreateIndexBuffer(index_buffer_length, D3DUSAGE_WRITEONLY,
D3DFMT_INDEX16, D3DPOOL_MANAGED, &m_mg_list[i].index_buffer, NULL);
}
}
// get the size of the bounding cube
float max_x, max_y, max_z;
max_x = (float) max(fabs(m_root_mesh->m_min.x), fabs(m_root_mesh->m_max.x));
max_y = (float) max(fabs(m_root_mesh->m_min.y), fabs(m_root_mesh->m_max.y));
max_z = (float) max(fabs(m_root_mesh->m_min.z), fabs(m_root_mesh->m_max.z));
m_world_cube_diameter = max(max_x, max(max_y, max_z)) * 2.0f;
m_node_max_diameter = node_max_diameter;
// create the root node
m_root_node = new NODE;
// sort polygons into nodes
d3d_mesh->LockVertexBuffer(D3DLOCK_READONLY, (void**)&m_vertex_ptr);
_sort_node(m_root_node, 0.0f, 0.0f, 0.0f, m_world_cube_diameter);
d3d_mesh->UnlockVertexBuffer();
m_render_timer = 0;
return TRUE;
}
//------------------------------------------------------------------------------
// Render the current view using view transformation and overloaded distance of view.
// Also specify to use a pre-calculate frustum or force a calculation of own frustum.
//------------------------------------------------------------------------------
BOOL NODE_TREE_MESH::render(FRUSTUM_PTR frustum, float z_dist)
{
// error checking
if(m_graphics == NULL || m_root_node == NULL || m_num_polys == 0)
return FALSE;
// construct the viewing frustum (if none passed)
if((m_frustum = frustum) == NULL)
{
FRUSTUM view_frustum; // local viewing frustumn
view_frustum.construct(m_graphics, z_dist);
m_frustum = &view_frustum;
}
IDirect3DDevice9* d3d_device = m_graphics->get_device_com();
D3DXMATRIX matrix; // matrix used for calculations
// set the world transformation matrix to identity,
// so that level mesh is rendered around the origin it was disigned.
D3DXMatrixIdentity(&matrix);
d3d_device->SetTransform(D3DTS_WORLD, &matrix);
// lock material group index buffer
for(ulong i = 0; i < m_num_mg; i++)
{
if(m_mg_list[i].num_polys != 0)
{
UINT total_vert_index_size = m_mg_list[i].num_polys * 3 * sizeof(ushort);
m_mg_list[i].index_buffer->Lock(0, total_vert_index_size, (void**) &m_mg_list[i].index_ptr, 0);
}
m_mg_list[i].num_polys_to_draw = 0;
}
// increase render frame timer
m_render_timer++;
// add polygons to be drawn into material group list
_add_node(m_root_node);
IDirect3DVertexBuffer9* vertex_buffer = NULL;
// get vertex buffer pointer
m_root_mesh->m_mesh->GetVertexBuffer(&vertex_buffer);
// set vertex shader and source
d3d_device->SetStreamSource(0, vertex_buffer, 0, m_num_bytes_per_vertex);
d3d_device->SetFVF(m_vertex_fvf);
UINT num_vertices = m_root_mesh->m_mesh->GetNumVertices();
// unlock vertex buffers and draw
for(ulong i = 0; i < m_num_mg; i++)
{
if(m_mg_list[i].num_polys != 0)
m_mg_list[i].index_buffer->Unlock();
if(m_mg_list[i].num_polys_to_draw != 0)
{
UINT num_polys_to_draw = m_mg_list[i].num_polys_to_draw;
d3d_device->SetMaterial(&m_root_mesh->m_materials[i]);
d3d_device->SetTexture(0, m_root_mesh->m_textures[i]);
d3d_device->SetIndices(m_mg_list[i].index_buffer);
d3d_device->DrawIndexedPrimitive(D3DPT_TRIANGLELIST, 0, 0, num_vertices, 0, num_polys_to_draw);
}
}
// release vertex buffer
if(vertex_buffer)
vertex_buffer->Release();
return TRUE;
}