[转帖]创建3D图形引擎

鼯鼠

使用单一的网格模型虽然可以同时渲染整个层次，但却意味着那些没有被看到的部分在通过渲染管道时会被裁剪掉，也就是说这样做会浪费时间。不要沮丧，因为使用一个单独的网格模型进行层次的渲染仍然有一些非常好的方法。比如说，在游戏世界中包括了单独的地牢，每个地牢包含不同的房间，所有的房间通过走廊连接到一起。其实，每个房间和走廊就是一个单独的网格模型，所要做的就是在游戏的处理过程中加载以及释放那些代表地牢房间的网格模型。


我们首先定义一些成员变量来存储数据。

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->class APP : public APPLICATION
{
private:
    GRAPHICS        _graphics;
    CAMERA          _camera;

    INPUT           _input;
    INPUT_DEVICE    _keyboard;
    INPUT_DEVICE    _mouse;    
    MESH            _room_meshes[2];
    OBJECT          _room_objects[8];

    float           _x_pos, _z_pos;
}
初始化窗口：


Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->    APP()
    {
        _width  = 640;
        _height = 480;

        _style = WS_BORDER | WS_CAPTION | WS_MINIMIZEBOX | WS_SYSMENU;

        strcpy(_class_name, "mesh level class");
        strcpy(_caption, "mesh level demo");
    }
加载网格模型：


Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->    BOOL init()
    {
        // initialize graphics and set display mode
        _graphics.init();
        _graphics.set_mode(get_hwnd(), TRUE, TRUE);
        _graphics.set_perspective(D3DX_PI / 4, 1.3333f, 1.0f, 10000.0f);

        // initialize input and input device
        _input.init(get_hwnd(), get_inst());
        _keyboard.create(&_input, KEYBOARD);
        _mouse.create(&_input, MOUSE, TRUE);

        // load the room meshes
        _room_meshes[0].load(&_graphics, "..\\Data\\Corridor.x", "..\\Data\\");
        _room_meshes[1].load(&_graphics, "..\\Data\\Room.x", "..\\Data\\");    

        // setup the room objects
        _room_objects[0].create(&_graphics, &_room_meshes[1]);
        _room_objects[1].create(&_graphics, &_room_meshes[0]);  
        _room_objects[2].create(&_graphics, &_room_meshes[1]);
        _room_objects[3].create(&_graphics, &_room_meshes[0]);
        _room_objects[4].create(&_graphics, &_room_meshes[0]);
        _room_objects[5].create(&_graphics, &_room_meshes[1]);
        _room_objects[6].create(&_graphics, &_room_meshes[0]);
        _room_objects[7].create(&_graphics, &_room_meshes[1]);

        // place room object in specified position
        _room_objects[0].move(-2000.0f, 0.0f,  2000.0f);
        _room_objects[1].move(    0.0f, 0.0f,  2000.0f);  
        _room_objects[2].move( 2000.0f, 0.0f,  2000.0f);
        _room_objects[3].move(-2000.0f, 0.0f,     0.0f);
        _room_objects[4].move( 2000.0f, 0.0f,     0.0f);
        _room_objects[5].move(-2000.0f, 0.0f, -2000.0f);
        _room_objects[6].move(    0.0f, 0.0f, -2000.0f);
        _room_objects[7].move( 2000.0f, 0.0f, -2000.0f);

        // rotate room object into proper orientation
        _room_objects[1].rotate(0.0f,  1.57f, 0.0f);
        _room_objects[2].rotate(0.0f,  1.57f, 0.0f);
        _room_objects[5].rotate(0.0f, -1.57f, 0.0f);
        _room_objects[6].rotate(0.0f, -1.57f, 0.0f);
        _room_objects[7].rotate(0.0f,  3.14f, 0.0f);

        // position view in a room
        _x_pos = -2000.0f;
        _z_pos = -2000.0f;

        return TRUE;
    }  这里加载了两个网格模型corridor.x 和room.x，一个是走廊，一个是房间。
走廊：

房间：

鼯鼠

游戏中的每个走廊和房间都使用了一个OBJECT对象，其与网格模型依次相关联。
我们接着来看看如何渲染这些网格模型。

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->    BOOL frame()
    {
        static DWORD time_now = timeGetTime();

        // calculate elapsed time (plus speed boost)
        ulong time_elapsed = (timeGetTime() - time_now) * 2;

        time_now = timeGetTime();

        // read input device data
        _keyboard.read();
        _mouse.read();

        // process input and update everything, ESC quits program.
        if(_keyboard.get_key_state(KEY_ESC))
            return FALSE;

        float x_move = 0.0f;
        float z_move = 0.0f;

        // ok, now let me explain next codes.
        //
        // _camera.get_y_rotation():
        //      get camera vector in xoz plane.
        //
        // sin(_camera.get_y_rotation()):
        //      get x-coordinate of camera vector.
        //
        // cos(_camera.get_y_rotation()):
        //      get z-coordinate of camera vector.

        // move viewpoint forward
        if(_keyboard.get_key_state(KEY_UP))
        {
            x_move = (float) sin(_camera.get_y_rotation()) * time_elapsed;
            z_move = (float) cos(_camera.get_y_rotation()) * time_elapsed;
        }

        // move viewpoint backward
        if(_keyboard.get_key_state(KEY_DOWN))
        {
            x_move = -(float) sin(_camera.get_y_rotation()) * time_elapsed;
            z_move = -(float) cos(_camera.get_y_rotation()) * time_elapsed;
        }

        // translate camera left-right movement into up-down movement.
        //
        // _camera.get_y_rotation() - 1.57f:
        //      rotate camera 90 degree anticlockwise.
        //
        // sin(_camera.get_y_rotation() - 1.57f):
        //      get x-coordinate of camera vector after camera rotation.
        //
        // cos(_camera.get_y_rotation() - 1.57f):
        //     get z-coordinate of camera vector after camera rotation. 
        
        // move viewpoint left
        if(_keyboard.get_key_state(KEY_LEFT))
        {
            x_move = (float) sin(_camera.get_y_rotation() - 1.57f) * time_elapsed;
            z_move = (float) cos(_camera.get_y_rotation() - 1.57f) * time_elapsed;
        }

        // _camera.get_y_rotation() + 1.57f:
        //      rotate camera 90 degree clockwise.
        //
        // sin(_camera.get_y_rotation() + 1.57f):
        //      get x-coordinate of camera vector after camera rotation.
        //
        // cos(_camera.get_y_rotation() + 1.57f):
        //      get z-coordinate of camera vector after camera rotation.

        // move viewpoint right
        if(_keyboard.get_key_state(KEY_RIGHT))
        {
            x_move = (float) sin(_camera.get_y_rotation() + 1.57f) * time_elapsed;
            z_move = (float) cos(_camera.get_y_rotation() + 1.57f) * time_elapsed;
        }

        // update view coordinates
        _x_pos += x_move;
        _z_pos += z_move;

        // position camera and rotate based on mouse position

        _camera.move(_x_pos, 400.0f, _z_pos);

        // _mouse.get_y_delta():
        //      get mouse's relative x movement coordinate.
        //
        // _mouse.get_x_delta():
        //      get mouse's relative y movement coordinate.

        _camera.rotate_rel(_mouse.get_y_delta() / 200.0f, _mouse.get_x_delta() / 200.0f, 0.0f);

        // set camera
        _graphics.set_camera(&_camera);

        // render everything
        _graphics.clear(D3DCOLOR_RGBA(0, 64, 128, 255));

        // begin render now
        if(_graphics.begin_scene())
        {
            // render each room
            for(short i = 0; i < 8; i++)
                _room_objects.render();

            _graphics.end_scene();
        }

        _graphics.display();

        return TRUE;
    }
用上下左右键控制相机的位置，用鼠标控制相机的朝向。 截图：

鼯鼠

视锥的介绍
视锥（viewing frustum）是6个平面的集合，它从观察点向外扩展，以确定某个多边形是否能够被观察到。
首先，可以将视锥看作是一个以观察者开始扩展的金字塔，如下图所示：

这个金字塔代表了观察范围（field of view，FOV），位于观察范围内的物体是可见的，而位于观察范围外的物体则是不可见的。
三维图形引擎的每个物体都是由3D点（称为顶点）构成的，每个视锥包含6个面（前、后、左、右、上、下）。通过一些数学计算，可以确定哪些顶点位于视锥内，哪些顶点位于视锥外。位于视锥内的顶点被渲染，而位于视锥外的顶点则不被渲染。同样，当渲染多边形时，只有那些在视锥内的顶点才被渲染。
 
平面与裁剪
视锥的6个侧面被称为剪切平面（clipping plane），Direct3D使用了一个名为D3DXPLANE的特定对象去包含平面数据，D3DXPLANE包含了4个变量：a、b、c、d，它们都是浮点型数据。
定义好一个平面后，为它指定一个特定的方向，并将它从原点移到相应的位置。事实上，一个平面就是由一条法线以及它与原点的距离进行定义的，如下图所示，它演示了一个平面在三维空间中的方位。

不需要指定X、Y、Z的具体数值，你只要使用变量A、B、C，同时还有一个数值D来确定平面离原点的距离。为了定义一个平面，将A、B、C设置为法向量的值，这样就可以使用一个平面去检测指定的点位于平面的前面或者后面。
 
为了计算视锥的6个平面，可以将当前的观察变换矩阵和投影矩阵组合起来，然后使用组合矩阵直接计算每个平面的A、B、C、D。
 
平面可见性检测
为了检测一个顶点位于平面的前方或后方，可以利用点积来计算，通过调用D3DXPlaneCoord函数来实现。
Computes the dot product of a plane and a 3D vector. The w parameter of the vector is assumed to be 1.
FLOAT D3DXPlaneDotCoord(
CONST D3DXPLANE * pP,
CONST D3DXVECTOR3 * pV
); Parameters pP [in] Pointer to a source D3DXPLANE structure. pV [in] Pointer to a source D3DXVECTOR3 structure. Return Values The dot product of the plane and 3D vector.
Remarks Given a plane (a, b, c, d) and a 3D vector (x, y, z) the return value of this function is a*x + b*y + c*z + d*1. The D3DXPlaneDotCoord function is useful for determining the plane's relationship with a coordinate in 3D space.
 
完整视锥的检测
对于立方体和长方体，需检测所有的拐角顶点。如果所有的顶点都位于任一平面之后，那么立方体或长方体就位于视锥之外（因而也在视野之外）。如果有任一顶点位于视锥之内，或者说位于任一平面前（也就是说不是所有的顶点都位于任一平面后），那就意味着立方体或者长方体是可见的。至于球体，只要它与每个平面的距离等于或大于球形的平面，那么它就是可见的。
 
FRUSTUM类
因为每次使用视锥所涉及的数学运算都是一样的，所以完全可以创建一个类，让它处理好数学方面的问题，包括创建视锥以及使用视锥去检测一个物体是否可见等。

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->//==============================================================================
// This class encapsulate for frustum, judge whether other object is in frustum.
//==============================================================================
typedef class FRUSTUM
{
public:
    // Construct the six planes from current view and projection. 
    // Can override the default depth value.
    BOOL construct(GRAPHICS_PTR graphics, float z_distance = 0.0f);

    // The following functions check a single point, cube, rectangle, and sphere if 
    // contained in the frustum. A return value of TRUE means visible, FALSE not visible.
    // When checking cubes or rectangles, you can supply a BOOL variable that determines 
    // if all the points are in the frustum.

    BOOL check_point(float x_pos, float y_pos, float z_pos);

    BOOL check_cube(float x_center, float y_center, float z_center,
                    float radius,
                    BOOL* completely_contained = NULL);

    BOOL check_rectangle(float x_center, float y_center, float z_center,
                         float x_radius, float y_radius, float z_radius,
                         BOOL* completely_contained = NULL);

    BOOL check_sphere(float x_center, float y_center, float z_center,
                      float radius);
    
private:
    D3DXPLANE _planes[6];       // the frustum planes
} *FRUSTUM_PTR;
每当观察或投影矩阵发生变化时，请调用construct去构造6个测试平面，如果仅希望最接近的物体能被看到，则可以为远端剪切平面指定一个新的距离值。


Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->//----------------------------------------------------------------------------
// Construct frustum.
//----------------------------------------------------------------------------
BOOL FRUSTUM::construct(GRAPHICS_PTR graphics, float z_distance)
{
    D3DXMATRIX matrix, mat_view, mat_proj;

    // error checking
    if(graphics == NULL)
        return FALSE;

    // calculate FOV data
    graphics->get_device_com()->GetTransform(D3DTS_PROJECTION, &mat_proj);

    if(! float_equal(z_distance, 0.0f))
    {
        // Calculate new projection matrix based on distance provided.
        //
        // projection matrix is:
        // 
        // | xScale     0          0               0 |
        // | 0        yScale       0               0 |
        // | 0          0       zf/(zf-zn)         1 |
        // | 0          0       -zn*zf/(zf-zn)     0 |
        //
        // where:
        //      yScale = cot(fovY/2)
        //      xScale = yScale / aspect ratio

        float z_min = -mat_proj._43 / mat_proj._33;
        float q = z_distance / (z_distance - z_min);

        mat_proj._33 = q;
        mat_proj._43 = -q * z_min;
    }

    graphics->get_device_com()->GetTransform(D3DTS_VIEW, &mat_view);
    D3DXMatrixMultiply(&matrix, &mat_view, &mat_proj);

    // calculate the planes
    _planes[0].a = matrix._14 + matrix._13; // Near
    _planes[0].b = matrix._24 + matrix._23;
    _planes[0].c = matrix._34 + matrix._33;
    _planes[0].d = matrix._44 + matrix._43;
    D3DXPlaneNormalize(&_planes[0], &_planes[0]);

    _planes[1].a = matrix._14 - matrix._13; // Far
    _planes[1].b = matrix._24 - matrix._23;
    _planes[1].c = matrix._34 - matrix._33;
    _planes[1].d = matrix._44 - matrix._43;
    D3DXPlaneNormalize(&_planes[1], &_planes[1]);

    _planes[2].a = matrix._14 + matrix._11; // Left
    _planes[2].b = matrix._24 + matrix._21;
    _planes[2].c = matrix._34 + matrix._31;
    _planes[2].d = matrix._44 + matrix._41;
    D3DXPlaneNormalize(&_planes[2], &_planes[2]);

    _planes[3].a = matrix._14 - matrix._11; // Right
    _planes[3].b = matrix._24 - matrix._21;
    _planes[3].c = matrix._34 - matrix._31;
    _planes[3].d = matrix._44 - matrix._41;
    D3DXPlaneNormalize(&_planes[3], &_planes[3]);

    _planes[4].a = matrix._14 - matrix._12; // Top
    _planes[4].b = matrix._24 - matrix._22;
    _planes[4].c = matrix._34 - matrix._32;
    _planes[4].d = matrix._44 - matrix._42;
    D3DXPlaneNormalize(&_planes[4], &_planes[4]);

    _planes[5].a = matrix._14 + matrix._12; // Bottom
    _planes[5].b = matrix._24 + matrix._22;
    _planes[5].c = matrix._34 + matrix._32;
    _planes[5].d = matrix._44 + matrix._42;
    D3DXPlaneNormalize(&_planes[5], &_planes[5]);

    return TRUE;
}
使用check系列函数判断物体在视锥内是否可见。

鼯鼠

//----------------------------------------------------------------------------
// Check one point whether in frustum.
//----------------------------------------------------------------------------
BOOL FRUSTUM::check_point(float x_pos, float y_pos, float z_pos)
{
    // make sure point is in frustum
    for(short i = 0; i < 6; i++)
    {
        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_pos, y_pos, z_pos)) < 0.0f)
            return FALSE;
    }

    return TRUE;
}

//----------------------------------------------------------------------------
// Check whether a cube in frustum, if total cube in frustum then 
// completely_contained will be set TRUE.
//----------------------------------------------------------------------------
BOOL FRUSTUM::check_cube(float x_center, float y_center, float z_center, 
                         float radius, 
                         BOOL* completely_contained)
{
    DWORD num_points_in_frustum = 0;

    // count the number of points inside the frustum
    for(short i = 0; i < 6; i++)
    {
        DWORD count = 8;
        BOOL in_all_planes = TRUE;

        // test all eight points against plane

        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_center - radius, y_center - radius, z_center - radius)) < 0.0f)
        {
            in_all_planes = FALSE;
            count--;
        }

        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_center + radius, y_center - radius, z_center - radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_center - radius, y_center + radius, z_center - radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_center + radius, y_center + radius, z_center - radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_center - radius, y_center - radius, z_center + radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_center + radius, y_center - radius, z_center + radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_center - radius, y_center + radius, z_center + radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_center + radius, y_center + radius, z_center + radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        // if none contained, return FALSE.
        if(count == 0)
            return FALSE;

        // update counter if they were all in front of plane.
        if(in_all_planes)
            ++num_points_in_frustum;
    }

    // store BOOL flag if completely contained
    if(completely_contained)
        *completely_contained = (num_points_in_frustum == 6);

    return TRUE;
}

//----------------------------------------------------------------------------
// Check whether a rectangle is in frustum, if total in then completely_contained
// will be set TRUE.
//----------------------------------------------------------------------------
BOOL FRUSTUM::check_rectangle(float x_center, float y_center, float z_center, 
                              float x_radius, float y_radius, float z_radius, 
                              BOOL* completely_contained)
{
    DWORD num_points_in_frustum = 0;

    // count the number of points inside the frustum
    for(short i = 0; i < 6; i++) 
    {
        DWORD count = 8;
        BOOL  in_all_planes = TRUE;
        
        // Test all eight points against plane

        if(D3DXPlaneDotCoord(&_planes, 
            &D3DXVECTOR3(x_center - x_radius, y_center - y_radius, z_center - z_radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, 
            &D3DXVECTOR3(x_center + x_radius, y_center - y_radius, z_center - z_radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, 
            &D3DXVECTOR3(x_center - x_radius, y_center + y_radius, z_center - z_radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, 
            &D3DXVECTOR3(x_center + x_radius, y_center + y_radius, z_center - z_radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, 
            &D3DXVECTOR3(x_center - x_radius, y_center - y_radius, z_center + z_radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, 
            &D3DXVECTOR3(x_center + x_radius, y_center - y_radius, z_center + z_radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, 
            &D3DXVECTOR3(x_center - x_radius, y_center + y_radius, z_center + z_radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        if(D3DXPlaneDotCoord(&_planes, 
            &D3DXVECTOR3(x_center + x_radius, y_center + y_radius, z_center + z_radius)) < 0.0f) 
        {
          in_all_planes = FALSE;
          count--;
        }

        // If none contained, return FALSE
        if(count == 0)
          return FALSE;

        // Update counter if they were all in front of plane
        if(in_all_planes)
            ++num_points_in_frustum;
    }

    // Store BOOL flag if completely contained
    if(completely_contained)
        *completely_contained = (num_points_in_frustum == 6);

    return TRUE;
}

//----------------------------------------------------------------------------
// Check whether a sphere is in frustum. 
//----------------------------------------------------------------------------
BOOL FRUSTUM::check_sphere(float x_center, float y_center, float z_center, 
                           float radius)
{
    // make sure radius is in frustum
    for(short i = 0; i < 6; i++)
    {
        if(D3DXPlaneDotCoord(&_planes, &D3DXVECTOR3(x_center, y_center, z_center)) < -radius)
            return FALSE;
    }

    return TRUE;
}

鼯鼠

测试代码：


Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/************************************************************************************
PURPOSE:
    frustum test.
************************************************************************************/

#include "core_global.h"
#include "frustum.h"

#define MAX_OBJECTS 256

class APP : public APPLICATION
{
public:
    APP()
    {
        _width  = 640;
        _height = 480;
        
        APPLICATION::_x_pos = (get_screen_width()  - _width) / 2;
        APPLICATION::_y_pos = (get_screen_height() - _height) / 4;

        _style = WS_BORDER | WS_CAPTION | WS_MINIMIZEBOX | WS_SYSMENU;

        strcpy(_class_name, "object clipping class");
        strcpy(_caption, "object clipping demo");
    }

    BOOL init()
    {
        // initialize graphics and set display mode
        _graphics.init();
        _graphics.set_mode(get_hwnd(), TRUE, TRUE);
        _graphics.set_perspective(D3DX_PI / 4, 1.3333f, 1.0f, 10000.0f);

        // create a font
        _font.create(&_graphics, "Arial", 16, TRUE, FALSE);

        // initialize input and input device
        _input.init(get_hwnd(), get_inst());        
        _mouse.create(&_input, MOUSE, TRUE);

        // load mesh
        if(! _mesh.load(&_graphics, "..\\Data\\Yodan.x", "..\\Data\\"))
            return FALSE;

        for(short i = 0; i < MAX_OBJECTS; i++)
        {
            _objects.create(&_graphics, &_mesh);

            _objects.move((float) (rand() % 4000) - 2000.0f, 0.0f, (float) (rand() % 4000) - 2000.0f);
        }

        return TRUE;
    }

    BOOL frame()
    {
        // read mouse data        
        _mouse.read();

        // position camera and rotate based on mouse position

        _camera.move(0.0f, 100.0f, 0.0f);

        // _mouse.get_y_delta():
        //      get mouse's relative x movement coordinate.
        //
        // _mouse.get_x_delta():
        //      get mouse's relative y movement coordinate.

        _camera.rotate_rel(_mouse.get_y_delta() / 200.0f, _mouse.get_x_delta() / 200.0f, 0.0f);

        // set camera
        _graphics.set_camera(&_camera);
        
        // render everything
        _graphics.clear(D3DCOLOR_RGBA(0, 64, 128, 255));               

        // begin render now
        if(_graphics.begin_scene())
        {
            FRUSTUM frustum;
            frustum.construct(&_graphics); 

            long num_drawn = 0;

            // render each object in frustums
            for(short i = 0; i < MAX_OBJECTS; i++)
            {
                float radius;
                
                _objects.get_bounds(NULL, NULL, NULL, NULL, NULL, NULL, &radius);

                if(frustum.check_sphere(_objects.get_x_pos(), _objects.get_y_pos(), _objects.get_z_pos(),
                                        radius))
                {
                    _objects.render();
                    num_drawn++;
                }                
            }

            char stats[128];

            // display statistics
            sprintf(stats, "%lu of 256 objects drawn.", num_drawn);
            _font.print(stats, 0, 0, 400, 100);
                
            _graphics.end_scene();
        }

        _graphics.display();

        return TRUE;
    }

    BOOL shutdown()
    {
        return TRUE;
    }

private:  
    GRAPHICS        _graphics;
    CAMERA          _camera;
    FONT            _font;

    INPUT           _input;
    INPUT_DEVICE    _mouse;    

    MESH            _mesh;
    OBJECT          _objects[MAX_OBJECTS];
};

int WINAPI WinMain(HINSTANCE inst, HINSTANCE, LPSTR cmd_line, int cmd_show)
{
    APP app;

    return app.run();
}
截图：

鼯鼠

高级三维引擎的开发
在每帧中绘制所有的多边形是非常低效的，为了提高处理的速度，可以仅渲染那些位于视野内的多边形，同时应避免扫描场景中的每个多边形来确定哪些多边形是可见的。如果不每帧进行搜索，又如何知道哪些多边形是位于视野内呢？解决的方法就是将一个三维模型分解为一些较小的块（称为节点nodes），其容纳较少的多边形。然后将节点排列到一个特定的结构中（一棵树），以便进行快速搜索，并确定哪个节点是可见的，然后渲染这些可见的节点，通过使用视锥，可以找出哪些节点是可见的。取代搜索数千个多边形，通过搜索一个小小的节点集合，就能决定怎样进行绘制。节点树引擎适用于任何的网格模型，并将它拆分为节点，以便快速渲染网格模型（网格模型代表了游戏的层次）。
 
NodeTree引擎的介绍
NodeTree引擎非常通用，因为它可以在两种不同的模式下操作（对于节点的拆分）：四叉树（quadtree）和八叉树（octree）模式。四叉树模式将世界（及随后的节点）一次拆分为4个节点，这种模式最适合y轴变化不大的层次网格模型（即观察点的高度并没有太大的变化）。而八叉树将世界（及随后的节点）一次拆分为8个节点，使用这种模式，大型三维网格模型中的观察点可以被移动到世界中的任意位置。如下图所示：

使用哪一种拆分模式由自己决定，考虑自己的网格模型，是否要搜索一座城堡，或者进入一个洞穴，或在风景中漫游？如果网格模型在高度上并没有太大的变化（例如风景），四叉树模式最好。如果网格模型的每一条轴线都要扩展开来（例如一个拥有许多层次的城堡），则适合使用八叉树模式。
世界（它被表示为包含了所有多边形的一个立方体）可以不断地被拆分为更小的、尺寸大小相同的节点。四叉树在二维空间中将节点进行拆分（使用x轴和z轴），而八叉树在三维空间中将节点进行拆分（使用所有的轴线）。一个节点代表了一组多边形，同时也代表了三维空间中的一个区域。每个节点可以包含另外的节点，而每个其后的节点也可以成为一个更小节点的父节点。通常，三维世界被认为是根节点（root node，最顶层的节点，其他所有的节点都属于它）。对于节点和树，有一些技巧，通过确定哪些多边形被包含在一个节点的三维空间里，可以将它们进行分组，然后从根节点开始，可以快速遍历树中的每个节点。
 
创建节点和树
创建节点并构造树形结构，需要先对网格模型中的每个多边形进行检查，只需做一次检查而已，所以它不会成为影响渲染速度的一个因素。这样做的目的是决定如何对树中的节点进行安排。网格模型中的每个多边形被包围在一个盒子里（称为框界盒子，如下图所示）。这个盒子代表了多边形在任何方向上的范围，只要多边形的盒子被包围在一个节点的三维空间里（完全或部分的），那么该多边形就属于这个节点，一个多边形可以属于多个节点，因为多边形的范围可能会穿过许多节点。

将多边形分组为节点时，需注意多边形所在的空间是否很大，或者在一个很大的空间中是否有太多的多边形，如果是就需要将节点拆分为更多的子节点，然后再次搜索多边形列表，将新的节点放入计算，继续这个处理过程，直到所有的多边形的分组足够小，并且每个包含的多边形树也足够少。为了优化树形结构，放弃所有那些没有包含多边形的节点，删除空的节点可以节省内存，同时可以加快树形结构的搜索。
如下图所示，可以将根节点拆分为4个较小的节点（使之成为一个四叉树的节点），然后检测每个节点，并不断地拆分其中较大的节点，跳过空节点以便加快处理速度，最后得到一个完美的树形结构以方便以后搜索。

 
搜索及绘制树
如果构成三维空间节点的那8个顶点中的任一个（可以被看作是立方体的拐角）位于视锥内，或者如果视锥自身是被包含在一个节点里，那么该节点就被认为是位于视野之内的。在确定了一个节点是可见的之后，对它的子节点（如果有的话）执行同样的检测，如果一个节点并不包含子节点，则检测当前节点是否包含了没有被绘制的多边形。当一个节点中的多边形被绘制后，它们被标识为已被绘制，并返回父节点，同时搜索其余的子节点。在处理过程中可以看到，较高层次的节点连同它们的子节点一起被抛弃，以这种方式，就可以在渲染过程中删除数千的多边形，从而节省时间。如果一个节点被完全地包含在视锥里，那就可以不用再搜索节点的任何子节点，因为他们也完全被包含在视锥里了。
当使用Direct3D和树形结构时，会发现一个网格模型可以包含多重的材质，但转换材质会是开销很大的操作（特别当每个材质使用了不同的纹理时），因此要谨慎处理。那么如何绘制所有可见的多边形，又不用一次又一次地转换材质呢（即使材质已经被使用了）？这就是材质分组的作用。材质分组（material group）就是多边形的集合，根据它们所指定的材质被分组到一起。因为一个网格模型可以包含多重材质，所以在一个指定的时间中，仅渲染那些属于指定材质的多边形分组。以这种方式，仅需要设置一次所使用的材质（以及随后的纹理，如果存在的话），渲染使用材质的多边形，并继续处理下一个材质。
尽管材质分组的使用听起来合乎逻辑，但多边形根据材质进行分组使其很难处理NodeTree信息，不对树形结构进行搜索就不知道哪些多边形将被绘制。所以必须搜索树形结构，并构造需要被渲染的多边形列表。完成搜索后，仅检测那些属于材质的多边形列表，并使用它们。材质分组并没有什么影响，只是要那些被绘制的多边形更有次序。
 
创建NedeTree类
定义：

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->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 OLYGON_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 OLYGON
    {
        ulong   mg_index;           // material group index
        ulong   render_timer;

        ushort  vertex_index_0;
        ushort  vertex_index_1;
        ushort  vertex_index_2;

        OLYGON()
        {
            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;
                child_nodes = 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
    OLYGON_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;

鼯鼠

实现：
Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->//------------------------------------------------------------------------------
// 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 = new NODE;    // create new child node

                // sort the polygons with the new child node
                _sort_node(node->child_nodes, 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, 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, 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)
            {
                num++;
                _add_node(node->child_nodes);
            }
        }

        // 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;

            // get pointer to polygon
            OLYGON_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 OLYGON[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;  // material group index

        m_poly_list.vertex_index_0 = *index_ptr++;
        m_poly_list.vertex_index_1 = *index_ptr++;
        m_poly_list.vertex_index_2 = *index_ptr++;
        m_poly_list.mg_index       = mg_index;
        m_poly_list.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.num_polys != 0)
        {
            UINT index_buffer_length = m_mg_list.num_polys * 3 * sizeof(ushort);

            m_graphics->get_device_com()->CreateIndexBuffer(index_buffer_length, D3DUSAGE_WRITEONLY,
                D3DFMT_INDEX16, D3DPOOL_MANAGED, &m_mg_list.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.num_polys != 0)
        {
            UINT total_vert_index_size = m_mg_list.num_polys * 3 * sizeof(ushort);

            m_mg_list.index_buffer->Lock(0, total_vert_index_size, (void**) &m_mg_list.index_ptr, 0);
        }       

        m_mg_list.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.num_polys != 0)
            m_mg_list.index_buffer->Unlock();

        if(m_mg_list.num_polys_to_draw != 0)
        {
            UINT num_polys_to_draw = m_mg_list.num_polys_to_draw;

            d3d_device->SetMaterial(&m_root_mesh->m_materials);
            d3d_device->SetTexture(0, m_root_mesh->m_textures);
            d3d_device->SetIndices(m_mg_list.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;
}

鼯鼠

将三维物体添加到世界中
盲目地绘制成千的物体而没有执行任何的剪切，是导致在图形-渲染通道中时间延迟的一个主要原因。需要再次使用视锥以快速确定哪些物体位于视野中，为了确定哪些物体是可见的，可将每个三维物体包围到一个可见的球体中，称之为框界球体（bounding sphere）。
下图演示了框界球体和视锥的运用，它展示了一个场景，其中有三个物体和一个视锥，每个网格模型都有一个可见的框界球体围绕着它。当一个球体位于构成视锥的6个平面前时，它就被认为是可见的。可以看出仅两个位于视锥中的物体是可见的，而另一个物体完全位于视锥外，绘制时能完全跳过那个位于视锥之外的物体。为了实现这一点，必须计算每个物体的框界球体，然后检测球体是否位于视锥之内。

 
网格模型的碰撞
为了检测一个多边形是否堵塞了节点之间的路径，可以在两个节点发射一条想象中的射线，以检测它们是否与一个平面相交。如下图所示：

有一个功能函数负责执行交集的测试，以确保射线与平面的相交点位于多边形内，并给出那个相交点的确切坐标，同时显示从射线的开始点到相交点的距离长度，它是一个非常有用的功能函数。
Determines if a ray intersects with a mesh.
HRESULT D3DXIntersect(
LPD3DXBASEMESH pMesh,
CONST D3DXVECTOR3 * pRayPos,
CONST D3DXVECTOR3 * pRayDir,
BOOL * pHit,
DWORD * pFaceIndex,
FLOAT * pU,
FLOAT * pV,
FLOAT * pDist,
LPD3DXBUFFER * ppAllHits,
DWORD * pCountOfHits
); Parameters pMesh [in] Pointer to an ID3DXBaseMesh interface, representing the mesh to be tested. pRayPos [in] Pointer to a D3DXVECTOR3 structure, specifying the point where the ray begins. pRayDir [in] Pointer to a D3DXVECTOR3 structure, specifying the direction of the ray. pHit [out] Pointer to a BOOL. If the ray intersects a triangular face on the mesh, this value will be set to TRUE. Otherwise, this value is set to FALSE. pFaceIndex [out] Pointer to an index value of the face closest to the ray origin, if pHit is TRUE. pU [out] Pointer to a barycentric hit coordinate, U. pV [out] Pointer to a barycentric hit coordinate, V. pDist [out] Pointer to a ray intersection parameter distance. ppAllHits [out] Pointer to an ID3DXBuffer object, containing an array of D3DXINTERSECTINFO structures. pCountOfHits [out] Pointer to a DWORD that contains the number of entries in the ppAllHits array. Return Values If the function succeeds, the return value is D3D_OK. If the function fails, the return value can be: E_OUTOFMEMORY.
Remarks The D3DXIntersect function provides a way to understand points in and around a triangle, independent of where the triangle is actually located. This function returns the resulting point by using the following equation: V1 + U(V2 - V1) + V(V3 - V1).
Any point in the plane V1V2V3 can be represented by the barycentric coordinate (U,V). The parameter U controls how much V2 gets weighted into the result, and the parameter V controls how much V3 gets weighted into the result. Lastly, the value of [1 - (U + V)] controls how much V1 gets weighted into the result.
Barycentric coordinates are a form of general coordinates. In this context, using barycentric coordinates represents a change in coordinate systems. What holds true for Cartesian coordinates holds true for barycentric coordinates.
Barycentric coordinates define a point inside a triangle in terms of the triangle's vertices. For a more in-depth description of barycentric coordinates, see Mathworld's Barycentric Coordinates Description.
我们编写一个函数来检测一条线段是否与一个网格中的三角形面相交。

鼯鼠

//------------------------------------------------------------------------------
// Check if a polygon blocks path from start to end.
//------------------------------------------------------------------------------
BOOL is_ray_intersect_mesh(LPD3DXBASEMESH mesh,
                           float x_start, float y_start, float z_start,
                           float x_end, float y_end, float z_end,
                           float* distance)
{
    float x_diff, y_diff, z_diff;

    x_diff = x_end - x_start;
    y_diff = y_end - y_start;
    z_diff = z_end - z_start;

    D3DXVECTOR3 ray_pos(x_start, y_start, z_start);

    D3DXVECTOR3 ray_dir;
    D3DXVec3Normalize(&ray_dir, &D3DXVECTOR3(x_diff, y_diff, z_diff));

    BOOL is_hit;
    float u, v, dist;
    DWORD face_index;

    // determins if a ray intersects with a mesh
    D3DXIntersect(mesh, &ray_pos, &ray_dir, &is_hit, &face_index, &u, &v, &dist, NULL, NULL);

    if(is_hit)
    {
        float ray_length = (float) sqrt(x_diff * x_diff + y_diff * y_diff + z_diff * z_diff);

        if(dist > ray_length)
            return FALSE;
        else
        {
            if(distance != NULL)
                *distance = dist;
        }
    }

    return TRUE;
}
在一个多边形层次中运用碰撞检测的另一个好处就是可以使物体随着其下多边形变化的高度而变化。换句话说，可以使物体永远在多边形上移动，这样就能在一个三维建模软件里绘制层次，而不用定义哪些区域是物体可以“行走”的，因为多边形就是那些区域，这使得四叉树和八叉树网格模型的处理更加容易。 可通过下面这三个函数来执行物体与多边形的相交测试：

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->//------------------------------------------------------------------------------
// Get closest height above or below point.
//------------------------------------------------------------------------------
float get_closest_height(LPD3DXBASEMESH mesh, float x_pos, float y_pos, float z_pos)
{
    float y_above, y_below;

    y_above = get_closest_height_above(mesh, x_pos, y_pos, z_pos);
    y_below = get_closest_height_below(mesh, x_pos, y_pos, z_pos);

    if(fabs(y_above - y_pos) < fabs(y_below - y_pos))
        return y_above;

    return y_below;
}

//------------------------------------------------------------------------------
// Get closet height below point.
//------------------------------------------------------------------------------
float get_closest_height_below(LPD3DXBASEMESH mesh, float x_pos, float y_pos, float z_pos)
{
    BOOL is_hit;
    float u, v, dist;
    DWORD face_index;

    D3DXVECTOR3 ray_pos(x_pos, y_pos, z_pos);
    D3DXVECTOR3 ray_dir(0.0f, -1.0f, 0.0f);

    D3DXIntersect(mesh, &ray_pos, &ray_dir, &is_hit, &face_index, &u, &v, &dist, NULL, NULL);

    if(is_hit)
        return y_pos - dist;

    return y_pos;
}

//------------------------------------------------------------------------------
// Get closet height above point.
//------------------------------------------------------------------------------
float get_closest_height_above(LPD3DXBASEMESH mesh, float x_pos, float y_pos, float z_pos)
{
    BOOL is_hit;
    float u, v, dist;
    DWORD face_index;

    D3DXVECTOR3 ray_pos(x_pos, y_pos, z_pos);
    D3DXVECTOR3 ray_dir(0.0f, 1.0f, 0.0f);

    D3DXIntersect(mesh, &ray_pos, &ray_dir, &is_hit, &face_index, &u, &v, &dist, NULL, NULL);

    if(is_hit)
        return y_pos + dist;

    return y_pos;
}
为了方便，在NODE_TREE_MESH类中继续封装这些函数：


Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->//------------------------------------------------------------------------------
// Get closest height above or below point.
//------------------------------------------------------------------------------
float NODE_TREE_MESH::get_closest_height(float x_pos, float y_pos, float z_pos)
{
    return ::get_closest_height(m_root_mesh->m_mesh, x_pos, y_pos, z_pos);
}

//------------------------------------------------------------------------------
// Get closest height below point.
//------------------------------------------------------------------------------
float NODE_TREE_MESH::get_closest_height_below(float x_pos, float y_pos, float z_pos)
{
    return ::get_closest_height_below(m_root_mesh->m_mesh, x_pos, y_pos, z_pos);
}

//------------------------------------------------------------------------------
// Get closest height above point.
//------------------------------------------------------------------------------
float NODE_TREE_MESH::get_closest_height_above(float x_pos, float y_pos, float z_pos)
{
    return ::get_closest_height_above(m_root_mesh->m_mesh, x_pos, y_pos, z_pos);
}

//------------------------------------------------------------------------------
// Check if a polygon blocks path from start to end.
//------------------------------------------------------------------------------
BOOL NODE_TREE_MESH::is_ray_intersect_mesh(float x_start, float y_start, float z_start,
                                     float x_end, float y_end, float z_end,
                                     float* distance)
{
    return ::is_ray_intersect_mesh(m_root_mesh->m_mesh, 
                             x_start, y_start, z_start,
                             x_end, y_end, z_end,
                             distance);
}
  当网格模型发生碰撞时
除了检测物体网格模型与构造世界的网格模型之间的碰撞，还需要知道较小网格模型碰撞的情况。举个例子，如果不希望角色穿透其他的角色，就需要结合物体和物体之间（object-to-object）的碰撞检测。进行操作前需要了解一些事情，包括框界球体使用的知识。如下图所示，其显示了两个怪物，它们都有长长的尾巴，那些尾巴影响了网格模型的框界球体的整体尺寸，为了包围住整个网格模型（包括尾巴），球体将会很大。如果将这两个怪物移动到下图所示的位置，会看到这两个框界球体相交，但怪物并没有那么靠近。

尽管有许多办法解决大型框界球体问题，但有一种快速执行的方法。取代使用网格模型的框界球体，而是为每个网格模型计算自己的框界球体半径，通过计算框界球体的半径，可以快速调节它以覆盖网格模型确实需要的空间。
我们编写一个函数来检测两个框界球体是否相交：

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->//------------------------------------------------------------------------------
// Check if two spheres intersect.
//------------------------------------------------------------------------------
BOOL is_tow_sphere_intersect(float x_center_1, float y_center_1, float z_center_1,
                             float radius1,
                             float x_center_2, float y_center_2, float z_center_2,
                             float radius2)
{
    float x_diff, y_diff, z_diff, dist;
    
    // calculate distance between two sphere center]
    
    x_diff = fabs(x_center_2 - x_center_1);
    y_diff = fabs(y_center_2 - y_center_1);
    z_diff = fabs(z_center_2 - z_center_1);

    dist = (float) sqrt(x_diff * x_diff + y_diff * y_diff + z_diff * z_diff); 

    // if two spheres intersect, retuen TRUE.
    if(dist <= radius1 + radius2)
        return TRUE;

    return FALSE;
}
 

鼯鼠

天框的使用
天框（sky box）是一种围绕观察者进行纹理映射的三维立方体的图形技术，渲染一个天框时，观察点总是定于中心位置，以便用户始终能够看到方框内部纹理映射的表面，这种技术能够制造出一种世界围绕用户的效果，如下图所示：

天框是非常容易是实现，只需一个立方体网格模型（其表面朝向里面）即可，通过一个顶点缓冲区存储立方体网格模型会非常不错。至于纹理，可以使用多达6个的纹理，每个表面一个纹理。网格模型并不需要很大，仅20.0单元大小的立方体就行了。纹理大小应该为256 x 256或者更高，较小的纹理将出现拉伸而且不生动。
 
创建一个天框类
SKY_BOX负责控制天框的每个方面，从创建渲染盒子所使用的顶点缓冲区，到渲染时所使用的纹理。
定义：

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->enum SKY_BOX_SIDES  { TOP = 0, BOTTOM, LEFT, RIGHT, FRONT, BACK };

//=====================================================================================
// This calss encapsulate how to make sky box.
//=====================================================================================
typedef class SKY_BOX
{
private:
    typedef struct SKY_BOX_VERTEX
    {
        float x, y, z;
        float u, v;
    } *SKY_BOX_VERTEX_PTR;

    #define SKY_BOX_FVF (D3DFVF_XYZ | D3DFVF_TEX1)

private:
    GRAPHICS_PTR    m_graphics;         // parent GRAPHICS object
    TEXTURE         m_textures[6];      // face texture (0 - 5)
    VERTEX_BUFFER   m_vertex_buffer;    // mesh vertex buffer
    WORLD_POSITION  m_pos;              // sky box position

public:
    SKY_BOX();
    ~SKY_BOX();

    BOOL create(GRAPHICS_PTR graphics);
    void free();

    BOOL load_texture(short side, pcstr filename, D3DCOLOR transparent = 0, D3DFORMAT format = D3DFMT_UNKNOWN);

    void rotate(float x_rot, float y_rot, float z_rot);
    void rotate_rel(float x_rot, float y_rot, float z_rot);

    BOOL render(CAMERA_PTR camera, BOOL alpha_blend = FALSE);
} *SKY_BOX_PTR;
实现:


Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->//----------------------------------------------------------------------------------
// Constructor, initialize member data.
//----------------------------------------------------------------------------------
SKY_BOX::SKY_BOX()
{
    m_graphics = NULL;
}

//----------------------------------------------------------------------------------
// Destructor, release allocated resource.
//----------------------------------------------------------------------------------
SKY_BOX::~SKY_BOX()
{
    free();
}

//----------------------------------------------------------------------------------
// Release allocated resource.
//----------------------------------------------------------------------------------
void SKY_BOX::free()
{
    m_graphics = NULL;

    for(short i = 0; i < 6; i++)
        m_textures.free();

    m_vertex_buffer.free();
}

//----------------------------------------------------------------------------------
// Create a sky box class object.
//----------------------------------------------------------------------------------
BOOL SKY_BOX::create(GRAPHICS_PTR graphics)
{
    SKY_BOX_VERTEX verts[24] = {
        { -10.0f,  10.0f, -10.0f, 0.0f, 0.0f },  // Top
        {  10.0f,  10.0f, -10.0f, 1.0f, 0.0f },
        { -10.0f,  10.0f,  10.0f, 0.0f, 1.0f },
        {  10.0f,  10.0f,  10.0f, 1.0f, 1.0f },

        { -10.0f, -10.0f,  10.0f, 0.0f, 0.0f },  // Bottom
        {  10.0f, -10.0f,  10.0f, 1.0f, 0.0f },
        { -10.0f, -10.0f, -10.0f, 0.0f, 1.0f },
        {  10.0f, -10.0f, -10.0f, 1.0f, 1.0f },

        { -10.0f,  10.0f, -10.0f, 0.0f, 0.0f },  // Left
        { -10.0f,  10.0f,  10.0f, 1.0f, 0.0f },
        { -10.0f, -10.0f, -10.0f, 0.0f, 1.0f },
        { -10.0f, -10.0f,  10.0f, 1.0f, 1.0f },

        {  10.0f,  10.0f,  10.0f, 0.0f, 0.0f },  // Right
        {  10.0f,  10.0f, -10.0f, 1.0f, 0.0f },
        {  10.0f, -10.0f,  10.0f, 0.0f, 1.0f },
        {  10.0f, -10.0f, -10.0f, 1.0f, 1.0f },

        { -10.0f,  10.0f,  10.0f, 0.0f, 0.0f },  // Front
        {  10.0f,  10.0f,  10.0f, 1.0f, 0.0f },
        { -10.0f, -10.0f,  10.0f, 0.0f, 1.0f },
        {  10.0f, -10.0f,  10.0f, 1.0f, 1.0f },
        
        {  10.0f,  10.0f, -10.0f, 0.0f, 0.0f },  // Back
        { -10.0f,  10.0f, -10.0f, 1.0f, 0.0f },
        {  10.0f, -10.0f, -10.0f, 0.0f, 1.0f },
        { -10.0f, -10.0f, -10.0f, 1.0f, 1.0f },
    };

    free();     // free a prior sky box

    // error checking
    if((m_graphics = graphics) == NULL)
        return FALSE;

    // create the vertex buffer (and copy over sky box vertices)
    if(m_vertex_buffer.create(m_graphics, 24, sizeof(SKY_BOX_VERTEX), SKY_BOX_FVF))
        m_vertex_buffer.set(0, 24, (void*)verts);

    // rotate the sky box into default orientation
    rotate(0.0f, 0.0f, 0.0f);

    return TRUE;
}

鼯鼠

//----------------------------------------------------------------------------------
// Set a specific side's texture map, allow for transparent and storage format changes.
//----------------------------------------------------------------------------------
BOOL SKY_BOX::load_texture(short side, pcstr filename, D3DCOLOR transparent, D3DFORMAT format)
{
    // error checking
    if(m_graphics == NULL || side < 0 || side > 5)
        return FALSE;

    m_textures[side].free();    // free prior texture

    return m_textures[side].load(m_graphics, filename, transparent, format);
}

//----------------------------------------------------------------------------------
// Rotate box to an absolute rotation.
//----------------------------------------------------------------------------------
void SKY_BOX::rotate(float x_rot, float y_rot, float z_rot)
{
    m_pos.rotate(x_rot, y_rot, z_rot);
}

//----------------------------------------------------------------------------------
// Rotate box to an relative rotation.
//----------------------------------------------------------------------------------
void SKY_BOX::rotate_rel(float x_rot, float y_rot, float z_rot)
{
    m_pos.rotate_rel(x_rot, y_rot, z_rot);
}

//----------------------------------------------------------------------------------
// Render the sky box (using optional alpha-blending) and using current view 
// transformation from Camera.
//----------------------------------------------------------------------------------
BOOL SKY_BOX::render(CAMERA_PTR camera, BOOL alpha_blend)
{
    // error checking
    if(m_graphics == NULL || camera == NULL)
        return FALSE;

    // position sky box around viewer
    m_pos.move(camera->get_x_pos(), camera->get_y_pos(), camera->get_z_pos());
    m_graphics->set_world_position(&m_pos);

    // enable alpha testing and alpha blending

    m_graphics->enable_alpha_blending(TRUE);

    if(alpha_blend)
        m_graphics->enable_alpha_blending(TRUE, D3DBLEND_SRCCOLOR, D3DBLEND_DESTCOLOR);

    // draw each layer
    for(short i = 0; i < 6; i++)
    {
        if(m_textures.is_loaded())
        {
            m_graphics->set_texture(0, &m_textures);
            m_vertex_buffer.render(i * 4, 2, D3DPT_TRIANGLESTRIP);
        }
    }

    // disable alpha testing and alpha blending

    m_graphics->enable_alpha_blending(FALSE);

    if(alpha_blend)
        m_graphics->enable_alpha_blending(FALSE);

    return TRUE;
}
测试代码：


Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/************************************************************************************
PURPOSE:
     node tree mesh test.
************************************************************************************/

#include "core_global.h"
#include "frustum.h"
#include "node_tree.h"
#include "sky_box.h"

class APP : public APPLICATION
{
public:
    APP()
    {
        _width  = 640;
        _height = 480;
        
        APPLICATION::_x_pos = (get_screen_width()  - _width) / 2;
        APPLICATION::_y_pos = (get_screen_height() - _height) / 4;

        _style = WS_BORDER | WS_CAPTION | WS_MINIMIZEBOX | WS_SYSMENU;

        strcpy(_class_name, "node tree class");
        strcpy(_caption, "node tree demo");
    }

    BOOL init()
    {
        // initialize graphics and set display mode
        _graphics.init();
        _graphics.set_mode(get_hwnd(), TRUE, TRUE);
        _graphics.set_perspective(D3DX_PI / 4, 1.3333f, 1.0f, 10000.0f);

        show_mouse(TRUE);
    
        // enable lighting and setup light

        _graphics.enable_lighting(TRUE);
        _graphics.set_ambient_light(24, 24, 24);
        _graphics.enable_light(0, TRUE);
        
        _light.set_attenuation_0(0.4f);
        _light.set_range(1000.0f);

        // initialize input and input device
        _input.init(get_hwnd(), get_inst());
        _keyboard.create(&_input, KEYBOARD);
        _mouse.create(&_input, MOUSE, TRUE);

        // load the mesh and create a nodetree mesh from it

        if(! _mesh.load(&_graphics, "..\\Data\\Level.x", "..\\Data\\"))
            return FALSE;

        _node_tree_mesh.create(&_graphics, &_mesh, QUADTREE);

        // position view at origin
        _x_pos = _y_pos = _z_pos = 0.0f;

        // setup sky box
        _sky_box.create(&_graphics);

        for(short i = 0; i < 6; i++)
            _sky_box.load_texture(i, "..\\data\\stars.bmp");

        // initialize the sound system to play with
        _sound.init(get_hwnd());
        _sound_data.load_wav("..\\data\\cricket.wav");

        for(short i = 0; i < 3; i++)
            _sound_channel.create(&_sound, &_sound_data);

        return TRUE;
    }

    BOOL frame()
    {
        static DWORD time_now = timeGetTime();

        // play a random cricket sound
        for(short i = 0; i< 3; i++)
        {
            if(!_sound_channel.is_playing() && rand()%256 < 16)
                _sound_channel.play(&_sound_data, 10);
        }

        // calculate elapsed time (plus speed boost)
        ulong time_elapsed = timeGetTime() - time_now;
        time_now = timeGetTime();

        // read keyboard and mouse data        
        _keyboard.read();
        _mouse.read();

        // process input and update everything, ESC quits program.

        if(_keyboard.get_key_state(KEY_ESC))
            return FALSE;

        float x_move, z_move;

        // process movement
        x_move = z_move = 0.0f;

        if(_keyboard.get_key_state(KEY_UP) || _keyboard.get_key_state(KEY_W))
        {
            x_move = (float) sin(_camera.get_y_rotation()) * time_elapsed;
            z_move = (float) cos(_camera.get_y_rotation()) * time_elapsed;
        }
        
        if(_keyboard.get_key_state(KEY_DOWN) || _keyboard.get_key_state(KEY_S))
        {
            x_move = (float) -sin(_camera.get_y_rotation()) * time_elapsed;
            z_move = (float) -cos(_camera.get_y_rotation()) * time_elapsed;
        }

        if(_keyboard.get_key_state(KEY_LEFT) || _keyboard.get_key_state(KEY_A))
        {
            x_move = (float) sin(_camera.get_y_rotation() - 1.57f) * time_elapsed;
            z_move = (float) cos(_camera.get_y_rotation() - 1.57f) * time_elapsed;
        }

        if(_keyboard.get_key_state(KEY_RIGHT) || _keyboard.get_key_state(KEY_D))
        {
            x_move = (float) sin(_camera.get_y_rotation() + 1.57f) * time_elapsed;
            z_move = (float) cos(_camera.get_y_rotation() + 1.57f) * time_elapsed;
        }

        // check for height changes (can step up to 64 units)
        float height = _node_tree_mesh.get_closest_height_below(_x_pos, _y_pos + _above_floor, _z_pos);

        if(_y_pos > height)
        {
            // dropping
            if((_y_pos -= (float)time_elapsed) < height)
                _y_pos = height;
            else
                x_move = z_move = 0.0f;
        }
        else
        {
            // climbing
            _y_pos = height;
        }

        float dist;