WoWmapview的World类

WoWmapview的World类处了负责显示和生成minimap外，主要的功能还是生成和显示map（top level map）。

如何显示Sky

WoWmapview中的World::initDisplay会初始化Skies类，Skies会从World\\Maps\\%s（如Azeroth)\\lights.lit中提取信息。LIT files have stored lighting-information until some patch. Today, lightning is stored in the following .DBCs:

1. Light.dbc
2. LightFloatBand.dbc
3. LightIntBand.dbc
4. LightParams.dbc
5. LightSkybox.dbc

WoWmapview中的代码还是使用废弃的LIT。

如何显示低精度地形

通过对WoWmapview中的World::initLowresTerrain的代码分析，得到如下内容：

1. WDL files contain a low-resolution heightmap for a world。解析WDL，其中的WDL包括了MAOF chunk 和 MapAreaLow array，通过解析这些数据得到1map = 64x64maptile，1maptile = 17x17+16x16 heightmap点（16bit）。如：World\Maps\Azeroth\Azeroth.wdl包括了top level map：Azeroth的64x64个tile的所有的heightmap数据。当然，Azeroth有些tile是无效的，假如所有tile都有效的情况下，那么WDL的heightmap数据就有：64x64x（17x17+16x16）*2个字节，那么WDL的heightmap就有((64 x 64 x ((17 x 17) + (16 x 16)) * 2) / 1024) / 1024 = 4.2578125M字节，也就是最大低精度地形数据是4M多。
2. WoWmapview中对WDL的处理是对每一个tile都建立一个OpenGL的显示列表，这样，就有64x64个显示列表（当然，无效的tile就没有显示列表了），在要显示某个tile的时候，执行该tile对应的显示列表就可以了。

如何显示Tile

通过对WoWmapview中的World::enterTile和World::loadTile的代码分析，得到如下内容：

1. 活动的是3x3 maptiles（1600x1600），实现了Cache机制，Cache中有16个tile slot，最多保存16个tile的数据。
2. World::loadTile首先是从Cache中取tile，如果命中（表示需要加载的tile已经在Cache的tile slot中），那么返回，否则构建MapTile去加载指定（xTile，yTile）的Tile，每个tile都对应一个ADT文件。
   
   如World::loadTile(33, 40)会构建MapTile（33，40，"World\\Maps\\Azeroth\\Azeroth_33_40.adt”）。
3. A map tile is split up into 16x16 = 256 map chunks. (not the same as file chunks, although each map chunk will have its own file chunk :) ) So there will be a few initial data chunks to specify textures, objects, models, etc. followed by 256 MCNK (mapchunk) chunks :) Each MCNK chunk has a small header of its own, and additional chunks within its data block, following the same id-size-data format.
4. 一个maptile的size是（1600/3=533.33m）。
5. MapTile类负责解析ADT中的Tile数据。1个tile 有16x16 map chunks，
   
   所以ADT中包含16x16=256个chunk数据。一个map chunk的size是（533.33/16=33.33m）。 ADT中的MCIN保存了这256个chunk的索引，真正的chunk数据在MCNK中。每个tile都包含了该tile内使用的
   1. BLP贴图（引用外部）(ADT中的MTEX）（贴图size为256x256）
   2. M2模型（引用外部）(ADT中的MMDX）
   3. WMO（world map objects）(ADT中的MWMO)，保存在ADT的MWMO中。 List of filenames for WMOs (world map objects) that appear in this map tile. A contiguous block of zero-terminated strings.
   4. M2模型实例(ADT中的MDDF），所谓M2模型实例就是相同模型在tile内不同摆放位置、大小、角度的说明信息，在wow引擎中的术语是doodad，翻译为小品，即可以随意摆放的小东西，
   5. WMO实例（ADT中的MODF），wmo实例的概念和M2模型实例的概念类似。为了节省文件尺寸，模式实例、wmo实例是通过index模型、wmo的方式保存的，同顶点索引类似。
   6. 256个MCNK。每个chunk都有ADT中的一个MCNK描述。
6. 下面是Chunk Vertex的分布图
   （Highres Chunk） （Lowres Chunk）
   （Vertex） 
7. MapChunk原点的计算是：The MCNK header中的/*0x068*/ Vec3f position的X,Z 指定了chunk的左上角坐标，但这个坐标系的原点（0，0）是在World的中央，所以经过如下调整
   1. zbase = zbase*-1.0f + ZEROPOINT;  // #define ZEROPOINT (32.0f * (TILESIZE)) 整个World是64x64tiles
   2. xbase = xbase*-1.0f + ZEROPOINT; // #define ZEROPOINT (32.0f * (TILESIZE))
8. MapChunk的hole。The MCNK header中的/*0x03C*/ UINT32 holes;holes是32bits的，低16bits作为标示，标示意义如下：
   1. 0x1 MCSH chunk available （控制chunk的shadow map是否开启）
   2. 0x2 Impassable?
   3. 0x4 River
   4. 0x8 Ocean
   5. 0x10 Magma （岩浆）
   6. 0x20 Slime? （泥）
   7. 0x40 MCCV chunk available
   8. 0x8000 Unknown, but heavily used in TBC.
9. MapChunk中的点的坐标计算：知道了MapChunk原点后，根据MCVT就可以得到每个点的(X,Y,Z)世界坐标。
10. WotLK中MH2O代替了MCLQ用于水体绘制，所以在WotLK后版本，不能根据MCLQ去渲染水。
    
11. WoWmapview中的Tile按照quadtree来组织的。MapNode::setup组织quadtree，quadtree的叶子节点就是一个chunk。MapNode::draw显示quadtree。每个chunk采用2级Index buffer的静态LOD，一个高精度的Index buffer和一个低精度的Index buffer。这种方法称为Interlocking方法，可以参考“Simplified Terrain Using Interlocking Tiles”，在游戏编程精髓，第2册。
12. WoWmapview通过ModelManager管理M2模型，通过WMOManager管理WMO，通过MapTile类中的std::vector<ModelInstance> modelis管理M2模型实例，通过MapTile类中的std::vector<WMOInstance> wmois管理WMO实例。

如何显示Chunk（Chunk是WOW中的渲染单元）

1个tile 有16x16 map chunks，Each map chunk has 9x9 （2的3次方+1）vertices, and in between them 8x8 （2的3次方）additional vertices, several texture layers, normal vectors, a shadow map, etc.

WoWmapview使用类MapChunk中的MapChunk::init来解析MCNK。

每个chunk由一下要素构成:

1. 9x9＋8x8个地形顶点高度和法线
2. 1到4个texture layer（由MCLY描述），这些texture layer（base texture）有2种类型，一种该层texture单纯是diffuse map，这个时候地形混合需要alpha map；另外一种类型texture是diffuse map+specular map，这个时候不需要使用alpha map，wow通过文件名后缀加_s表示带有specular map, 如某个地形贴图PlaguedEarthcreep01.blp带有specular map的文件对应就是PlaguedEarthcreep01_s.map。 PlaguedEarthcreep01.blp。WOW的地形贴图采用texture splatting技术，base texture重复（X方向上重复8次，Y方向也重复8次）拼缀覆盖整个chunk。
3. holes
4. 水面
5. Alpha map（除去第一个texture layer，每个texture layer都有alpha map，alpha map指定用于控制地表贴图的混合比例，尺寸64x64，由MCAL描述） ，整个64x64的alpha map要覆盖整个拥有9x9＋8x8个地形顶点的Chunk。
6. 一层shadow map（由MCSH描述，Shadow尺寸64x64，是按bit（0或1）而非byte保存，所以需要8x64个字节表示64x64的shadow）组成。整个64x64的shadow map要覆盖整个拥有9x9＋8x8个地形顶点的Chunk。

采用PS来渲染地形正好可以是1个pass解决。把3个alpha map和一个shadow map可以组成一个texture。

研究MapChunk::draw的流程：

1. 对chunk进行frustum剔除，frustum外的chunk不会进行绘制。（注：frustum在每次World::draw的时候都会更新）
2. 如太远则调用MapChunk::drawNoDetail显示lowres chunk，就完成了绘制。WoWmapview是在Chunk中按距离实现地形的静态LOD，通过静态修改Index Buffer的方法，提供2级Index Buffer（lowres 和 highres）来实现静态LOD。
   1. 每个Chunk的vertex数目是9x9＋8x8=145，而Index Buffer却根据如下情况不同：
      1. 在Chunk没包含hole的情况下，lowres 的Chunk地形的Vertex Index是有8*18 + 7*2=158个Index，highres的Chunk地形的Vertex Index是16*18 + 7*2 + 8*2=318。
      2. 在Chunk包含hole的情况下（参考MapChunk::initStrip），Index buffer就只是包含非hole的vertex index。
   2. 距离的计算是相机的世界坐标到Chunk中心点的距离然后减去chunk的边界球的半径，代码参考如下
      1. float mydist = (gWorld->camera - vcenter).length() - r; 
      2. r = (vmax - vmin).length() * 0.5f; （MapChunk::init中）
3. 如不太远则继续。
   1. 对于固定流水线的渲染，采用mutiple pass渲染。
      1. 调用drawPass渲染第一层texture layer（1 pass）。
      2. 采用Alpha map混合其他的texture layer（1..3pass）。
      3. 最后贴上shadow map(1pass)。

void MapChunk::draw()
{
    if (!gWorld->frustum.intersects(vmin,vmax))
        return;
    float mydist = (gWorld->camera - vcenter).length() - r;
    //if (mydist > gWorld->mapdrawdistance2) return;
    if (mydist > gWorld->culldistance)
    {
        if (gWorld->uselowlod)
            this->drawNoDetail();
        return;
    }
    visible = true;

    if (nTextures==0)
        return;

    if (!hasholes)
    {
        bool highres = gWorld->drawhighres;
        if (highres)
        {
            highres = mydist < gWorld->highresdistance2;
        }
        if (highres)
        {
            strip = gWorld->mapstrip2;
            striplen = stripsize2;
        } else
        {
            strip = gWorld->mapstrip;
            striplen = stripsize;
        }
    }

    // setup vertex buffers
    glBindBufferARB(GL_ARRAY_BUFFER_ARB, vertices);
    glVertexPointer(3, GL_FLOAT, 0, 0);
    glBindBufferARB(GL_ARRAY_BUFFER_ARB, normals);
    glNormalPointer(GL_FLOAT, 0, 0);
    // ASSUME: texture coordinates set up already

    if (supportShaders && gWorld->useshaders)
    {
        // SHADER-BASED

        // TODO: figure out texture animation for shaders
        // (modifying the texture matrix for only an individual texture layer)

        // setup textures
        /*
        unit 0 - base texture layer
        unit 1 - shadow map and alpha layers
        unit 2 - texture layer 1
        unit 3 - texture layer 2
        unit 4 - texture layer 3
        */
        // base layer
        glActiveTextureARB(GL_TEXTURE0_ARB);
        glBindTexture(GL_TEXTURE_2D, textures[0]);
        // shadow map
        // TODO: handle case when there is no shadowmap?
        glActiveTextureARB(GL_TEXTURE1_ARB);
        glBindTexture(GL_TEXTURE_2D, blend);
        // blended layers
        for (int i=1; i<nTextures; i++)
        {
            int tex = GL_TEXTURE2_ARB + i - 1;
            glActiveTextureARB(tex);
            glBindTexture(GL_TEXTURE_2D, textures[i]);
        }
        glActiveTextureARB( GL_TEXTURE0_ARB );

        terrainShaders[nTextures-1]->bind();
        // setup shadow color as local parameter:
        Vec3D shc = gWorld->skies->colorSet[SHADOW_COLOR] * 0.3f;
        glProgramLocalParameter4fARB(GL_FRAGMENT_PROGRAM_ARB, 0, shc.x,shc.y,shc.z,1);

        glDrawElements(GL_TRIANGLE_STRIP, striplen, GL_UNSIGNED_SHORT, strip);
        terrainShaders[nTextures-1]->unbind();

    }
    else
    {
        // FIXED-FUNCTION

        // first pass: base texture
        glActiveTextureARB(GL_TEXTURE0_ARB);  // 选择TEXTURE0为设置目标
        glEnable(GL_TEXTURE_2D); // 激活TEXTURE0单元
        glBindTexture(GL_TEXTURE_2D, textures[0]); 为TEXTURE0单元绑定texture纹理图像

        glActiveTextureARB(GL_TEXTURE1_ARB);// 选择TEXTURE1为设置目标
        glDisable(GL_TEXTURE_2D); // 关闭禁用TEXTURE1单元

        glDisable(GL_BLEND);
        drawPass(animated[0]);
        glEnable(GL_BLEND);

        if (nTextures>1)
        {
            //glDepthFunc(GL_EQUAL); // GL_LEQUAL is fine too...?
            glDepthMask(GL_FALSE);
        }

        // additional passes: if required
        for (int i=0; i<nTextures-1; i++)
        {
            glActiveTextureARB(GL_TEXTURE0_ARB);
            glEnable(GL_TEXTURE_2D);
            glBindTexture(GL_TEXTURE_2D, textures[i+1]);
            // this time, use blending:
            glActiveTextureARB(GL_TEXTURE1_ARB);
            glEnable(GL_TEXTURE_2D);
            glBindTexture(GL_TEXTURE_2D, alphamaps[i]);

            // if we loaded a texture with specular maps, setup the texenv
            // to replace our alpha channel instead of modulating it
            if (supportShaders) glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_REPLACE);
            drawPass(animated[i+1]);
            // back to normal
            if (supportShaders) glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_MODULATE);

        }

        if (nTextures>1)
        {
            //glDepthFunc(GL_LEQUAL);
            glDepthMask(GL_TRUE);
        }

        // shadow map
        glActiveTextureARB(GL_TEXTURE0_ARB);
        glDisable(GL_TEXTURE_2D);
        glDisable(GL_LIGHTING);

        Vec3D shc = gWorld->skies->colorSet[SHADOW_COLOR] * 0.3f;
        //glColor4f(0,0,0,1);
        glColor4f(shc.x,shc.y,shc.z,1);

        glActiveTextureARB(GL_TEXTURE1_ARB);
        glBindTexture(GL_TEXTURE_2D, shadow);
        glEnable(GL_TEXTURE_2D);

        drawPass(0);

        glEnable(GL_LIGHTING);
        glColor4f(1,1,1,1);
    }

    /*
    //////////////////////////////////
    // debugging tile flags:
    GLfloat tcols[8][4] = {    {1,1,1,1},
        {1,0,0,1}, {1, 0.5f, 0, 1}, {1, 1, 0, 1},
        {0,1,0,1}, {0,1,1,1}, {0,0,1,1}, {0.8f, 0, 1,1}
    };
    glPushMatrix();
    glDisable(GL_CULL_FACE);
    glDisable(GL_TEXTURE_2D);
    glTranslatef(xbase, ybase, zbase);
    for (int i=0; i<8; i++) {
        int v = 1 << (7-i);
        for (int j=0; j<4; j++) {
            if (animated[j] & v) {
                glBegin(GL_TRIANGLES);
                glColor4fv(tcols[i]);

                glVertex3f(i*2.0f, 2.0f, j*2.0f);
                glVertex3f(i*2.0f+1.0f, 2.0f, j*2.0f);
                glVertex3f(i*2.0f+0.5f, 4.0f, j*2.0f);

                glEnd();
            }
        }
    }
    glEnable(GL_TEXTURE_2D);
    glEnable(GL_CULL_FACE);
    glColor4f(1,1,1,1);
    glPopMatrix();
    */
}

void MapChunk::drawPass(int anim)
{
    if (anim) {
        glActiveTextureARB(GL_TEXTURE0_ARB); // 选择TEXTURE0为设置目标
        glMatrixMode(GL_TEXTURE); // Setting the matrix mode to GL_TEXTURE means that any subsequent transformation calls will be applied to texture coordinates, rather than vertex coordinates
        glPushMatrix();

        // note: this is ad hoc and probably completely wrong
        int spd = (anim & 0x08) | ((anim & 0x10) >> 2) | ((anim & 0x20) >> 4) | ((anim & 0x40) >> 6);
        int dir = anim & 0x07;
        const float texanimxtab[8] = {0, 1, 1, 1, 0, -1, -1, -1};
        const float texanimytab[8] = {1, 1, 0, -1, -1, -1, 0, 1};
        float fdx = -texanimxtab[dir], fdy = texanimytab[dir];

        int animspd = (int)(200.0f * detail_size);
        float f = ( ((int)(gWorld->animtime*(spd/15.0f))) % animspd) / (float)animspd;
        glTranslatef(f*fdx,f*fdy,0);
    }

    glDrawElements(GL_TRIANGLE_STRIP, striplen, GL_UNSIGNED_SHORT, strip);

    if (anim) {
        glPopMatrix();
        glMatrixMode(GL_MODELVIEW);
        glActiveTextureARB(GL_TEXTURE1_ARB);
    }
}

void MapChunk::drawNoDetail()
{
    glActiveTextureARB(GL_TEXTURE1_ARB);  // 选择TEXTURE1为设置目标
    glDisable(GL_TEXTURE_2D);// 禁用TEXTURE1单元
    glActiveTextureARB(GL_TEXTURE0_ARB);// 选择TEXTURE0为设置目标
    glDisable(GL_TEXTURE_2D);// 关闭禁用TEXTURE1单元

    glDisable(GL_LIGHTING);// 禁用光照

    glColor3fv(gWorld->skies->colorSet[FOG_COLOR]);
    //glColor3f(1,0,0);
    //glDisable(GL_FOG);

    // low detail version
    glBindBufferARB(GL_ARRAY_BUFFER_ARB, vertices);
    glVertexPointer(3, GL_FLOAT, 0, 0);
    glDisableClientState(GL_NORMAL_ARRAY); // 关闭禁用NORMAL Array
    glDrawElements(GL_TRIANGLE_STRIP, stripsize, GL_UNSIGNED_SHORT, gWorld->mapstrip);
    glEnableClientState(GL_NORMAL_ARRAY);

    glColor4f(1,1,1,1);
    //glEnable(GL_FOG);

    glEnable(GL_LIGHTING);
    glActiveTextureARB(GL_TEXTURE1_ARB);
    glEnable(GL_TEXTURE_2D);
    glActiveTextureARB(GL_TEXTURE0_ARB);
    glEnable(GL_TEXTURE_2D);
}

如何绘制 world map objects(WMO) 

每个tile都包含了该tile内使用的WMO，保存在ADT的MWMO中。 MWMO是List of filenames for WMOs (world map objects) that appear in this map tile. A contiguous block of zero-terminated strings. WMO文件的扩展名为wmo，如World\Wmo\Kalimdor\Builders\NightElf2Story\DsNightElf2Story.wmo。

一个.wmo文件，会构建一个WMO对象，并把该WMO对象放入WMOManager进行管理。WMO::WMO会解析.wmo文件。 参考：wmo(wow map object) research。

如何绘制 World

World::draw的流程：

1. 重置WMOInstance和M2的动画
2. 设置相机和frustum
3. 调用各个chunk的MapChunk::draw

WOW场景管理的总结

1. 场景管理采用QuadTree+Portal+BSP，实现室内外场景融合。
2. Terrain按照Tile划分。
3. Tile按照Chunk划分，Tile按照QuadTree管理，Chunk可重用。
4. Chunk采用Interlocking方法。Interlocking参考Greg Snook‘s Simplified Terrain Using Interlocking Tiles (在Game Programming GEM 2中的文章）

额外补充Simplified Terrain Using Interlocking Tiles

注：Simplified Terrain Using Interlocking Tiles文章中的的Tile概念不是WOW的Tile的概念，而是类似于WOW的Chunk概念。下面的文字中提及的Tile是指Simplified Terrain Using Interlocking Tiles文章中的的Tile概念。

在文章中：

1. 每个Tile可能包含独有的一个Vertex Buffer，但Index Buffer可以跨Tile重用。
2. 采用联锁处理T型裂缝（body+link）

增补：

参考：

1. Virtual Terrain Project
2. http://www.landscapemodeling.org/
3. http://www.vterrain.org/LOD/Papers/
4. http://www.verycd.com/topics/63344/
5. http://www.verycd.com/topics/36450/

参考：

1. Brute force meshing
2. Fault Formation fractal terrain generation
3. Midpoint Displacement fractal terrain generation
4. Perlin Noise
5. Simple Texture Mapping
6. Procedural texture generation （如Height-based texture generation 多张尺寸和Heightmap相同的纹理按照高度分布进行混合产生单张纹理）
7. Height-based lighting
8. Applying a lightmap to terrain
9. Slope-lighting algorithm
10. Terrain Tutorial
11. SOAR by Peter Lindstrom and Valerio Pascucci
12. Boer’s Geometrical MipMapping（geomipmapping ）CLOD algorithm (Geomorphing)(Crack-proofing)(按patch进行frustum culling)
13. Rottger’s Real-Time Generation of Continuous Levels of Detail for Height Fields
14. Greg Snook‘s Simplified Terrain Using Interlocking Tiles (在Game Programming GEM 2中的文章）
15. Duchaineau’s ROAM algorithm
16. Seamus McNally's improvement to the ROAM algorithm (Real-Time Dynamic Level of Detail Terrain Rendering with ROAM)
17. View-dependent refinement of progressive meshes
18. Terrain LOD: Runtime Regular-Grid Algorithms
19. Hierarchical Visibility in Terrains
20. Chunked LOD: Rendering Massive Terrains using Chunked Level of Detail Control （参考：Real Time 3D Terrain Engines Using C++ and Dx9的170页）
21. Far Cry and Half Life2 Engine scene technique 和 Half Life2 Displacement Terrain System
22. Breaking the Walls: Scene Partitioning and Portal Creation
23. Terrain rendering using GPU-based geometry clipmaps
24. 新游戏中出现的基于BSP场景分割技术
25. 3D地形多层纹理混合加阴影渲染方法
26. Building a 3D Portal Engine
27. Core Techniques and Algorithms in Game Programming
28. http://www.devmaster.net/articles/bsp-trees/
29. http://www.karkza.org/ftp/programming/misc/bsp.htm
30. http://www.devmaster.net/articles/bsp-trees-physics/
31. WoW文件结构类
32. http://www.wowwiki.com/Portal:Main
33. Automatic Portal Generation 自动Portal 生成
34. Binary Space Partioning Trees and Polygon Removal in Real Time 3D Rendering
35. 关于场景管理
36. http://wowdev.org/
37. Texture Splatting in Direct3D 理解起来好过于Terrain Texture Compositing by Blending in the Frame-Buffer，但是对Splatting的理解有少许问题，哈哈，所以，还是要好好研究Terrain Texture Compositing by Blending in the Frame-Buffer
38. Fun with Textures