本篇是创建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;
}