Extracting height data from ADT

[DrThum]

Hello,

After 2 weeks scratching my head, I finally decided to ask here for some help. I'm currently working on a new WoW emulator*, and I need to create maps for the server. I like to understand what I'm doing, so I didn't simply copy/paste code from TrinityCore or any other existing emu. At the moment, I am working with a 2.4.3 client, mainly because that's the version I know the most (I have been working on a 2.4.3 fork of TrinityCore for the last 4 years) and also because things were much simpler back then. Here's what I did so far, I hope that someone can show me the errors that I have made.

Btw, my main source was this page: ADT/v18 - WoWDev and I use StormLib to browse the MPQ files.
I think I got the adt parsing right, because I got every chunk where they were supposed to be. I used the offsets in the MCIN chunk to read each MCNK chunk.

This is the struct I used to store the MCNK header:

struct MCNKHeader
{
    uint32 flags; // 0x1 = has MCSH, 0x2 = impassible, 0x4 = River, 0x8 = Ocean, 0x10 = Magma, 0x20 = Slime, 0x40 = has MCCV
    uint32 indexX;
    uint32 indexY;
    uint32 nLayers; // UNUSED
    uint32 nDoodadRefs; // UNUSED
    // From here, xxxPtr are offsets to various sub-chunks, relative from the beginning of this MCNK chunk
    uint32 mcvtPtr; // Height values
    uint32 mcnrPtr; // UNUSED: Normal vectors for vertex shading
    uint32 mclyPtr; // UNUSED: Texture layers definitions
    uint32 mcrfPtr; // UNUSED: Related to doodads
    uint32 mcalPtr; // UNUSED: Alpha maps for additional texture layers
    uint32 sizeAlpha; // UNUSED: Size of the MCAL sub-chunk
    uint32 mcshPtr; // UNUSED: Static shadows on the terrain
    uint32 sizeShadow; // UNUSED
    uint32 areaId;
    uint32 nMapObjRefs;
    uint32 holes;
    uint16 s1; // UNUSED
    uint16 s2; // UNUSED
    uint32 d1; // UNUSED
    uint32 d2; // UNUSED
    uint32 d3; // UNUSED
    uint32 predTex; // UNUSED
    uint32 nEffectDoodad; // UNUSED
    uint32 mcsePtr; // UNUSED: Sound emitters
    uint32 nSndEmitters; // UNUSED
    uint32 mclqPtr; // Liquid levels
    uint32 sizeLiquid; // Size of the MCLQ sub-chunk
    float  zpos; // Z-position (of what?)
    float  xpos; // X-position (of what?)
    float  ypos; // Y-position (of what?)
    uint32 textureId; // UNUSED: Related to vertex shading
    uint32 props; // UNUSED: Looks like an array of colors
    uint32 effectId; // UNUSED
};

Then, I jump to the MCVT subchunk, and read height data with the following code:

float baseY = header->ypos;
float* cur = (float*) _chunkData; // _chunkData points to the beginning of the array containing 145 floats, aka the beginning of the MCVT subchunk
    for (uint8 j = 0; j < 17; j++) {
        for (uint8 i = 0; i < ((j % 2) ? 8 : 9); i++) {
            float h = *cur;
            cur++;
            float z = h + baseY;
            if (j % 2) {
                if (isHole(header->holes, i, j))
                    cell.h8x8[i][j/2] = -1000.0f; // TODO: Really what we want?
                else
                    cell.h8x8[i][j/2] = z;
            }
            else {
                if (isHole(header->holes, i, j))
                    cell.h9x9[i][j/2] = -1000.0f; // TODO: Really what we want?
                else
                    cell.h9x9[i][j/2] = z;
            }
        }
    }

The next step is to write all that in the .map file:

void ADTFile::write(const char* filename)
{
    std::ofstream out(filename, std::ios::out | std::ios::binary);
    out.write("MORPHEUS_MAP", 12);
    
    for (uint16 c = 0; c < 256; c++) {
        Cell cell = cells[c];
        for (uint8 i = 0; i < 9; i++) {
            for (uint8 j = 0; j < 9; j++) {
                out.write(reinterpret_cast<char *>(&cell.h9x9[i][j]), sizeof(float));
                //printf("Writing %f\n", cell.h9x9[i][j]);
            }
        }
        
        for (uint8 i = 0; i < 8; i++) {
            for (uint8 j = 0; j < 8; j++)
                out.write(reinterpret_cast<char *>(&cell.h8x8[i][j]), sizeof(float));
        }
    }
    
    out.flush();
    out.close();
}

Now, let's see the emu part, where I used this data. I implemented 3 classes : Map, CellBlock, and Cell. A map contains 64x64 CellBlocks, a CellBlock contains 16x16 Cells, and each Cell has a 9x9 and a 8x8 float arrays (which I called h9x9 and h8x8 respectively, and are called m_V9 and m_V8 in Trinity). I started my tests with Kalimdor (map 1) and do the following:

- Load CellBlocks

for (uint16 c = 0; c < 256; c++) {
        float h9x9[9][9];
        memset(&h9x9[0][0], 0, sizeof(float) * 9 * 9);
        for (uint8 i = 0; i < 9; i++) {
            for (uint8 j = 0; j < 9; j++)
                in.read(reinterpret_cast<char *>(&h9x9[i][j]), sizeof(float));
        }
        cells[c].copy9x9From(&h9x9[0][0]); // cells is a Cell[256]
        // copy9x9From and copy8x8From simply do memcpy from the data read in the file to the corresponding float arrays in the Cell class

        float h8x8[8][8];
        memset(&h8x8[0][0], 0, sizeof(float) * 8 * 8);
        for (uint8 i = 0; i < 8; i++) {
            for (uint8 j = 0; j < 8; j++)
                in.read(reinterpret_cast<char *>(&h8x8[i][j]), sizeof(float));
        }
        cells[c].copy8x8From(&h8x8[0][0]);
    }

- Calculate the height on a given position (I tested with Tauren starting coordinates, X = -2917.580078, Y = -257.980011, map = 1), first in the map:

#define CELLBLOCK_SIZE          533.333333f
#define CELLS_PER_BLOCK_SIDE    16
#define CELL_SIZE               (CELLBLOCK_SIZE / CELLS_PER_BLOCK_SIDE)
#define CELLCHUNK_SIZE          (CELL_SIZE / 8)

float Map::getHeight(float x, float y)
{
    x = std::abs(x) + 32 * CELLBLOCK_SIZE;
    y = std::abs(y) + 32 * CELLBLOCK_SIZE;
    
    uint32 blockX = x / CELLBLOCK_SIZE;
    uint32 blockY = y / CELLBLOCK_SIZE;
    
    // I am able to get the same block as TC with the 2 following lines but I still don't get the same height in the end
    /*blockX = 63 - blockX;
    blockY = 63 - blockY;*/
    
    printf("Block: %u, %u\n", blockX, blockY);
    
    float offsetBlockX = fmod(x, CELLBLOCK_SIZE);
    float offsetBlockY = fmod(y, CELLBLOCK_SIZE);
    
    /*offsetBlockX = CELLBLOCK_SIZE - offsetBlockX;
    offsetBlockY = CELLBLOCK_SIZE - offsetBlockY;*/
    
    printf("Offset in block: %f, %f\n", offsetBlockX, offsetBlockY);
    
    blocks[blockX][blockY].getHeight(offsetBlockX, offsetBlockY);
}

- Then, in the right block:

float CellBlock::getHeight(float x, float y) const
{
    printf("X: %f, Y: %f\n", x, y);
    
    uint32 cellX = x / CELL_SIZE;
    uint32 cellY = y / CELL_SIZE;
    
    /*cellX = 15 - cellX;
    cellY = 15 - cellY;*/
    
    printf("Cell %u, %u (= %uth)\n", cellX, cellY, (cellX * 16 + cellY));
    
    const Cell* cell = &cells[cellX * 16 + cellY];
    
    float offsetCellX = fmod(x, CELL_SIZE);
    float offsetCellY = fmod(y, CELL_SIZE);
    
    /*offsetCellX = CELL_SIZE - offsetCellX;
    offsetCellY = CELL_SIZE - offsetCellY;*/
    
    printf("Offset in cell: %f, %f\n", offsetCellX, offsetCellY);
    
    return cell->getHeight(offsetCellX, offsetCellY);
}

- And finally, in the right Cell (this code is taken from Trinity)

float Cell::getHeight(float x, float y) const
{
    // +--------------> X
    // | h1-------h2     Coordinates is:
    // | | \  1  / |     h1 0,0
    // | |  \   /  |     h2 0,1
    // | | 2  h5 3 |     h3 1,0
    // | |  /   \  |     h4 1,1
    // | | /  4  \ |     h5 1/2,1/2
    // | h3-------h4
    // V Y
    // 
    // h1, h2, h3 and h4 are in h9x9
    // h5 is in h8x8
    
    float a, b, c;
    printf("x: %f y: %f\n", x, y);
    uint32 chunkX = x / CELLCHUNK_SIZE;
    uint32 chunkY = y / CELLCHUNK_SIZE;
    
    /*chunkX = 8 - chunkX;
    chunkY = 8 - chunkY;*/
    
    printf("Chunks: x %u y %u\n", chunkX, chunkY);
    float deltaX = fmod(x, CELLCHUNK_SIZE) / CELLCHUNK_SIZE;
    float deltaY = fmod(y, CELLCHUNK_SIZE) / CELLCHUNK_SIZE;
    printf("Delta x %f y %f\n", deltaX, deltaY);
    if ((deltaX + deltaY) < 1.0f) { // Triangle 1 or 2
        if (deltaX > deltaY) {
            // Triangle 1
            float h1 = h9x9[chunkY][chunkX];
            float h2 = h9x9[chunkY + 1][chunkX];
            float h5 = 2 * h8x8[chunkY][chunkX];
            a = h2 - h1;
            b = h5 - h1 - h2;
            c = h1;
        }
        else {
            // Triangle 2
            float h1 = h9x9[chunkY][chunkX];
            float h3 = h9x9[chunkY][chunkX + 1];
            float h5 = 2 * h8x8[chunkY][chunkX];
            a = h5 - h1 - h3;
            b = h3 - h1;
            c = h1;
        }
    }
    else { // Triangle 3 or 4
        if (deltaX > deltaY)
        {
            // Triangle 3
            float h2 = h9x9[chunkY + 1][chunkX];
            float h4 = h9x9[chunkY + 1][chunkX + 1];
            float h5 = 2 * h8x8[chunkY][chunkX];
            a = h2 + h4 - h5;
            b = h4 - h2;
            c = h5 - h4;
        }
        else {
            // Triangle 4
            float h3 = h9x9[chunkY][chunkX + 1];
            float h4 = h9x9[chunkY + 1][chunkX + 1];
            float h5 = 2 * h8x8[chunkY][chunkX];
            a = h4 - h3;
            b = h3 + h4 - h5;
            c = h5 - h4;
        }
    }
    
    printf("a: %f, b: %f, c: %f, x: %f, y: %f\n", a, b, c, x, y);
    return a * x + b * y + c;
}

My problem is that I don't get the same height as Trinity, and not even the same CellBlock (which is called Grid in TC). I guess that my math is off somewhere, but I can't figure out where my mistake is. Don't hesitate to ask for more details if needed.

Thanks!


* For those interested, the project is open source and can be browsed here