Polygon indices parsing

On this page I'll try to describe how indices parsing is done and what current issues are.

Only research for South Park and Seeds of Evil are being done ATM, Dinosaur Hunter is somewhat different and still is TODO.

We have a single vertex buffer per model variation, this makes up the vertices for one whole model. We get the indices data per surface, a surface is a part of the mesh with a specific material. There might be multiple surfaces with the same material.

The indices data appears to be a 16bit stream, we have 3 different types of 16bit values, the type depends on some MSB bits.

• When bit index 15 is set, the other 15 bits are 3 indices. So 5 bits per index gives us a maximum of 31 (32 different values). These games where build for the N64, so looking at the N64 development docs we can see that the gSPVertex macro accepts up to 32 vertices per call and it has to be called multiple times for more vertices. So that seems to checkout.
• When bit index 14 is set, the first 8?bits appear to be the boneId. It only occurs on models with bones and the values seems to match. Meshes with bones always set this before the new block indicator (see next bit, index 13).
• When bit index 13 is set, this appears to indicate a new block of vertices to process, all streams start with this after potential boneId. General there are multiple of these per surface.
  • First 5 bits LSB appear to be the vertices count, adding all these equals the total vertices in the vertex buffer. When we get a count of 0, we assume it's 32 to make use of all the potential vertices processed by this block.

  • Second 5 bits (indexes 5-9) are either set to 0, 11 or 22. These seem to indicate that we might want to reuse vertices from the previous block, or maybe even the next or the last block, how this exactly works is unknown and the current issue. For all "block-types" the following indices may be larger then the current vertices count.

    • For "block-type" 0 the maximum amount of vertices count observed is 32.
    • For "block-type" 11 the maximum amount of vertices count observed is 11.
    • For "block-type" 22 the maximum amount of vertices count observed is 10.

    Which seems to indicate to me somehow that they divide the 32 vertices buffer they give to gSPVertex by 3 parts (11 + 11 + 10)? This to connect vertices from previous and maybe next batch?

So we need to keep track of a vertex start offset in order to normalize the indices to real indices inside the vertex buffer.

The given indices from bit 15 might be larger then the given vertices count from bit 13, for all "block-types" and even when it's the first block (when the vertex start offset is still 0). So how to handle these out of bounds indices?

Summing the problem: I don't know how to adjust the indices to real indices inside the vertex buffer when they are out of current vertex count bounds.

Some notes:

• The maximum amount of vertices per surface is 150 for some reason (checked on Seeds of Evil and South Park). We cannot divide 150 by 32, but 150 - (4 * 32) = 22, there is the magic 22 again..

tools/debug_indices.c

debug_indices.c

I've added a simple debug program that prints out the polygon data for further debugging.

Some South Park models that are of interest because they are relatively simple and all the math operations on the polygon data I've checked seem to be different somehow, when a formula works on one model, an other will usual break..

• 172 (animated turkey)
• 121 (animated airplane)
• 323 (static park bench)
• 193 (static half moon)
• 303 (static school building)

Example data on the animated turkey

Notes:

• surface 0: first block seems to load 28 verts but only creates polygons for 26 of them. Indexes 26 and 27 seem to be unused.
• surface 0: second block has unk set to 22.
• surface 0: third block only loads 11 verts, but the used indices are 0-10 (11 verts) and 25-28 (4 verts). So 4 verts are reused?
• what is going on with surface 3? Starts with empty block?

$ bin/debug_indices files/win32.dat 172
T2FS::INFO::Found schema ./schema/win32.json
total verts: 140
 
sufrace: 0
  <set boneID> 1
  [new block] 00 28
    surface: 00  i: 004  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 00  b: 01  c: 02
    surface: 00  i: 006  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 00  b: 03  c: 01
    surface: 00  i: 008  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 05  b: 00  c: 04
    surface: 00  i: 010  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 01  b: 04  c: 02
    surface: 00  i: 012  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 04  b: 01  c: 05
    surface: 00  i: 014  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 00  b: 05  c: 03
    surface: 00  i: 016  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 06  b: 07  c: 08
    surface: 00  i: 018  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 09  b: 06  c: 08
    surface: 00  i: 020  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 11  b: 12  c: 13
    surface: 00  i: 022  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 15  b: 16  c: 17
    surface: 00  i: 024  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 19  b: 20  c: 21
    surface: 00  i: 026  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 24  b: 19  c: 25
    surface: 00  i: 028  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 17  b: 18  c: 15
    surface: 00  i: 030  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 10  b: 08  c: 07
    surface: 00  i: 032  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 22  b: 23  c: 19
    surface: 00  i: 034  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 19  b: 21  c: 22
    surface: 00  i: 036  offset: 0000  unk: 00  verts: 28  boneId: 01  a: 13  b: 14  c: 11
  <set boneID> 3
  [new block] 22 07
    surface: 00  i: 042  offset: 0028  unk: 22  verts: 07  boneId: 03  a: 22  b: 02  c: 24
    surface: 00  i: 044  offset: 0028  unk: 22  verts: 07  boneId: 03  a: 02  b: 23  c: 24
    surface: 00  i: 046  offset: 0028  unk: 22  verts: 07  boneId: 03  a: 22  b: 04  c: 00
    surface: 00  i: 048  offset: 0028  unk: 22  verts: 07  boneId: 03  a: 04  b: 22  c: 23
    surface: 00  i: 050  offset: 0028  unk: 22  verts: 07  boneId: 03  a: 23  b: 02  c: 04
    surface: 00  i: 052  offset: 0028  unk: 22  verts: 07  boneId: 03  a: 22  b: 00  c: 02
  <set boneID> 4
  [new block] 00 11
    surface: 00  i: 058  offset: 0035  unk: 00  verts: 11  boneId: 04  a: 06  b: 07  c: 08
    surface: 00  i: 060  offset: 0035  unk: 00  verts: 11  boneId: 04  a: 01  b: 05  c: 04
    surface: 00  i: 062  offset: 0035  unk: 00  verts: 11  boneId: 04  a: 02  b: 01  c: 04
    surface: 00  i: 064  offset: 0035  unk: 00  verts: 11  boneId: 04  a: 25  b: 26  c: 00
    surface: 00  i: 066  offset: 0035  unk: 00  verts: 11  boneId: 04  a: 02  b: 27  c: 01
    surface: 00  i: 068  offset: 0035  unk: 00  verts: 11  boneId: 04  a: 25  b: 00  c: 03
    surface: 00  i: 070  offset: 0035  unk: 00  verts: 11  boneId: 04  a: 01  b: 27  c: 28
    surface: 00  i: 072  offset: 0035  unk: 00  verts: 11  boneId: 04  a: 06  b: 08  c: 09
    surface: 00  i: 074  offset: 0035  unk: 00  verts: 11  boneId: 04  a: 09  b: 08  c: 10
  [new block] 00 03
    surface: 00  i: 078  offset: 0046  unk: 00  verts: 03  boneId: 04  a: 00  b: 01  c: 02
  <set boneID> 5
  [new block] 00 11
    surface: 00  i: 084  offset: 0049  unk: 00  verts: 11  boneId: 05  a: 01  b: 02  c: 03
    surface: 00  i: 086  offset: 0049  unk: 00  verts: 11  boneId: 05  a: 04  b: 01  c: 03
    surface: 00  i: 088  offset: 0049  unk: 00  verts: 11  boneId: 05  a: 05  b: 01  c: 04
    surface: 00  i: 090  offset: 0049  unk: 00  verts: 11  boneId: 05  a: 07  b: 08  c: 09
    surface: 00  i: 092  offset: 0049  unk: 00  verts: 11  boneId: 05  a: 06  b: 05  c: 04
    surface: 00  i: 094  offset: 0049  unk: 00  verts: 11  boneId: 05  a: 11  b: 14  c: 00
    surface: 00  i: 096  offset: 0049  unk: 00  verts: 11  boneId: 05  a: 02  b: 05  c: 06
    surface: 00  i: 098  offset: 0049  unk: 00  verts: 11  boneId: 05  a: 03  b: 02  c: 06
  <set boneID> 1
  [new block] 11 04
    surface: 00  i: 104  offset: 0060  unk: 11  verts: 04  boneId: 01  a: 10  b: 11  c: 12
  <set boneID> 6
  [new block] 00 10
    surface: 00  i: 110  offset: 0064  unk: 00  verts: 10  boneId: 06  a: 01  b: 02  c: 03
    surface: 00  i: 112  offset: 0064  unk: 00  verts: 10  boneId: 06  a: 04  b: 05  c: 06
    surface: 00  i: 114  offset: 0064  unk: 00  verts: 10  boneId: 06  a: 07  b: 05  c: 04
    surface: 00  i: 116  offset: 0064  unk: 00  verts: 10  boneId: 06  a: 08  b: 07  c: 04
    surface: 00  i: 118  offset: 0064  unk: 00  verts: 10  boneId: 06  a: 09  b: 07  c: 08
    surface: 00  i: 120  offset: 0064  unk: 00  verts: 10  boneId: 06  a: 06  b: 09  c: 08
    surface: 00  i: 122  offset: 0064  unk: 00  verts: 10  boneId: 06  a: 05  b: 09  c: 06
    surface: 00  i: 124  offset: 0064  unk: 00  verts: 10  boneId: 06  a: 00  b: 13  c: 14
end surface 0: processed verts: 74
 
sufrace: 1
  <set boneID> 1
  [new block] 00 10
    surface: 01  i: 004  offset: 0074  unk: 00  verts: 10  boneId: 01  a: 00  b: 01  c: 02
  <set boneID> 6
  [new block] 11 03
    surface: 01  i: 010  offset: 0084  unk: 11  verts: 03  boneId: 06  a: 11  b: 03  c: 04
    surface: 01  i: 012  offset: 0084  unk: 11  verts: 03  boneId: 06  a: 05  b: 06  c: 12
    surface: 01  i: 014  offset: 0084  unk: 11  verts: 03  boneId: 06  a: 08  b: 13  c: 09
  <set boneID> 5
  [new block] 22 02
    surface: 01  i: 020  offset: 0087  unk: 22  verts: 02  boneId: 05  a: 03  b: 22  c: 04
    surface: 01  i: 022  offset: 0087  unk: 22  verts: 02  boneId: 05  a: 07  b: 05  c: 23
  <set boneID> 4
  [new block] 00 10
    surface: 01  i: 028  offset: 0089  unk: 00  verts: 10  boneId: 04  a: 00  b: 01  c: 02
    surface: 01  i: 030  offset: 0089  unk: 00  verts: 10  boneId: 04  a: 03  b: 04  c: 05
  <set boneID> 3
  [new block] 11 03
    surface: 01  i: 036  offset: 0099  unk: 11  verts: 03  boneId: 03  a: 11  b: 07  c: 13
    surface: 01  i: 038  offset: 0099  unk: 11  verts: 03  boneId: 03  a: 06  b: 07  c: 11
    surface: 01  i: 040  offset: 0099  unk: 11  verts: 03  boneId: 03  a: 08  b: 12  c: 09
end surface 1: processed verts: 28
 
sufrace: 2
  <set boneID> 4
  [new block] 00 12
    surface: 02  i: 004  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 00  b: 01  c: 02
    surface: 02  i: 006  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 00  b: 05  c: 04
    surface: 02  i: 008  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 02  b: 01  c: 03
    surface: 02  i: 010  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 04  b: 06  c: 01
    surface: 02  i: 012  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 08  b: 00  c: 09
    surface: 02  i: 014  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 08  b: 09  c: 10
    surface: 02  i: 016  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 00  b: 07  c: 05
    surface: 02  i: 018  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 00  b: 08  c: 07
    surface: 02  i: 020  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 01  b: 00  c: 04
    surface: 02  i: 022  offset: 0102  unk: 00  verts: 12  boneId: 04  a: 08  b: 11  c: 07
end surface 2: processed verts: 12
 
sufrace: 3
  <set boneID> 1
  [new block] 00 04
  <set boneID> 2
  [new block] 11 02
    surface: 03  i: 008  offset: 0118  unk: 11  verts: 02  boneId: 02  a: 03  b: 12  c: 11
    surface: 03  i: 010  offset: 0118  unk: 11  verts: 02  boneId: 02  a: 11  b: 02  c: 03
  <set boneID> 7
  [new block] 22 02
    surface: 03  i: 016  offset: 0120  unk: 22  verts: 02  boneId: 07  a: 22  b: 23  c: 01
    surface: 03  i: 018  offset: 0120  unk: 22  verts: 02  boneId: 07  a: 00  b: 22  c: 01
end surface 3: processed verts: 8
 
sufrace: 4
  <set boneID> 1
  [new block] 00 05
    surface: 04  i: 004  offset: 0122  unk: 00  verts: 05  boneId: 01  a: 00  b: 01  c: 02
    surface: 04  i: 006  offset: 0122  unk: 00  verts: 05  boneId: 01  a: 03  b: 04  c: 00
    surface: 04  i: 008  offset: 0122  unk: 00  verts: 05  boneId: 01  a: 00  b: 02  c: 03
end surface 4: processed verts: 5
 
sufrace: 5
  <set boneID> 1
  [new block] 00 05
    surface: 05  i: 004  offset: 0127  unk: 00  verts: 05  boneId: 01  a: 00  b: 01  c: 02
    surface: 05  i: 006  offset: 0127  unk: 00  verts: 05  boneId: 01  a: 02  b: 01  c: 03
    surface: 05  i: 008  offset: 0127  unk: 00  verts: 05  boneId: 01  a: 02  b: 04  c: 00
end surface 5: processed verts: 5
 
sufrace: 6
  <set boneID> 4
  [new block] 00 08
    surface: 06  i: 004  offset: 0132  unk: 00  verts: 08  boneId: 04  a: 00  b: 01  c: 02
    surface: 06  i: 006  offset: 0132  unk: 00  verts: 08  boneId: 04  a: 01  b: 00  c: 03
    surface: 06  i: 008  offset: 0132  unk: 00  verts: 08  boneId: 04  a: 00  b: 04  c: 03
    surface: 06  i: 010  offset: 0132  unk: 00  verts: 08  boneId: 04  a: 02  b: 04  c: 00
    surface: 06  i: 012  offset: 0132  unk: 00  verts: 08  boneId: 04  a: 05  b: 06  c: 07
end surface 6: processed verts: 8
 
processed verts: 140

Some pseudo code how it's done now (incorrect)

uint32_t
get_real_vert_index(uint8_t index, uint32_t vertOffset, uint32_t prevVertOffset,
                    uint8_t blockType, uint8_t vertCount)
{
  if (blockType == 0) {
 
    // out of bounds
    if (index >= vertCount) {
      // South Park 193 first surface really likes this
      // South Park 323 doesn't like it..
      //return prevVertOffset + index;
 
      // South Park 229 is not good with this ..
      // South Park 585 and 193 are good with this
      return vertOffset - (32 - index);
    }
 
    // normal (this is good)
    else {
      return vertOffset + index;
    }
 
  }
  else
  if (blockType == 11) {
 
    // index range:  0 - 10
    if (index < 11) {
      // TODO here it goes wrong on some models
      // Lookat South Park 269 surface 5
      return vertOffset - (11 - index);
    }
 
    // index range: 11 - 21
    else
    if (index <= 21) {
      // This is probably OK
      return vertOffset + (index - 11);
    }
 
    // index range: 22 - 31
    else {
      // Wrong
      return prevVertOffset + index;
    }
 
  }
  else
  if (blockType =  22) {
 
    if (index <= 11) {
      //return prevVertOffset + index;
 
      // South Park model 193 likes this (surface 2)
      //return = vertOffset + index + 1;
 
      // Nope not good on 193
      //return vertOffset - (32 - index);
 
      // Does some good, but not on all ..
      return prevVertOffset + index;
    }
 
    else
    if (index < 22) {
      // Good on 323 and 585
      return prevVertOffset + (index - 11);
    }
 
    else {
      // This is probably OK
      return vertOffset + (index - 22);
    }
  }
 
  // error ..
  return (uint32_t)-1;
}
 
 
uint32_t prevVertOffset = 0;
uint32_t vertOffset = 0;
uint8_t vertCount = 0;
uint8_t blockType = 0;
uint8_t boneId = 0;
for (uint16_t value in indicesData) {
    // Indices
    if (value & 0x8000) {
      uint8_t a = (value & 0x7C00) >> 10; // 0b01111100 00000000
      uint8_t b = (value & 0x03E0) >> 5;  // 0b00000011 11100000
      uint8_t c = (value & 0x001F);       // 0b00000000 00011111
 
      uint32_t realA = get_real_vert_index(a, vertOffset, prevVertOffset, blockType, vertCount);
      uint32_t realB = get_real_vert_index(b, vertOffset, prevVertOffset, blockType, vertCount);
      uint32_t realC = get_real_vert_index(c, vertOffset, prevVertOffset, blockType, vertCount);
 
      // .. here we should be able to draw a valid polygon with the
      // vertex buffer, realA, realB and realC.
      someCall(realA, realB, realC, boneId);
    }
    // New bone identifier
    else
    if (value & 0x4000) {
      boneId = value & 0xFF;
    }
    // New indices block
    else
    if (value & 0x2000) {
      prevVertOffset = vertOffset;
      vertOffset += vertCount;
      vertCount = value & 0x1F;          // 0b0000000000011111
      blockType = (value & 0x03E0) >> 5; // 0b0000001111100000
 
      if (vertCount == 0) {
        vertCount = 32;
      }
    }
 }

Some useful resources

• s_t2fsDataVertex
• https://ultra64.ca/files/documentation/online-manuals/man/n64man/gsp/gSPVertex.html
• https://ultra64.ca/files/documentation/online-manuals/man/n64man/gsp/gSP1Triangle.html
• https://ultra64.ca/files/documentation/online-manuals/man/n64man/gsp/gSP2Triangles.html
• https://www.moria.us/blog/2020/11/n64-part17-loading-models