An idea regarding vertex reuse on negative sides of the block

[goodsign]

I've accidentally stumbled upon these lines in your code:

// TODO Some re-use opportunities are missed on negative sides of the block,
// but I don't really know how to fix it...
// You can check by "shaking" every vertex randomly in a shader based on its index,
// you will see vertices touching the -X, -Y or -Z sides of the block aren't connected

So I just wanted to share my findings as I was both able to solve it and more-or-less can explain why it's impossible in the way described in the paper.

I'm not sure whether that's even worth pursuing, just wanted to share, maybe will be valuable, worst case — it won't 😆

---

In the paper the edge reuse indexing goes like this:

So the 51 edge (for example) has 1. Same as 11. In order for you to utilize 100% reuse opportunities — this can't work, because imagine you are in the deck #0 (k == 0) — your 51 needs to reuse from 41 and your 11 needs to reuse from 81. You can visually put two cubes with the same j and k in a row an it becomes obvious.

But they both will have reuse index 1, so it makes it impossible. I believe this is done in the paper just in a simplified manner or that was an early work. But given you anyway use a whole nibble to store these reuse indices — actually you do not use any more space or lose anything if you index the edges separately, for example like this:

In order to do a remap — you need to change the transvoxel tables for the primary mesher. A simple script would do (I'm playing in Javascript, but still):

// For each edge in the tables:
const edgeMap = {
    '02': 0,
    '13': 3,
    '46': 6,
    '57': 9,

    '01': 1,
    '23': 4,
    '45': 7,
    '67': 10,

    '04': 2,
    '15': 5,
    '26': 8,
    '37': 11
  }

  const remapCode = `${this.endpointIndexes[0]}${this.endpointIndexes[1]}`
  const newIndex = edgeMap[remapCode]
  this.hex = (this.hex & 0xF0FF) | (newIndex << 8);

Then, given edges 0, 1, 2 are not reusable, when you create a new index, you just store it in cellStorage.indexes[edgeCode - 3]. When you want to retrieve it — just refer to whatever indexing you used. Myself I was too lazy to figure out some kind of fancy bitwise shift operations, so I literally just listed all possible combinations:

_reuseEdgeIndex(edgeCode, reuseDirection) {
    if (edgeCode >= 9) {
      return null
    }

    if (edgeCode == 0) {
      // 0bZYX
      if (reuseDirection == 0b001) {
        return 3
      } else if (reuseDirection == 0b100) {
        return 6
      } else if (reuseDirection == 0b101) {
        return 9
      }
    }

    if (edgeCode == 1) {
      // 0bZYX
      if (reuseDirection == 0b010) {
        return 4
      } else if (reuseDirection == 0b100) {
        return 7
      } else if (reuseDirection == 0b110) {
        return 10
      }
    }

    if (edgeCode == 2) {
      // 0bZYX
      if (reuseDirection == 0b001) {
        return 5
      } else if (reuseDirection == 0b010) {
        return 8
      } else if (reuseDirection == 0b011) {
        return 11
      }
    }

    if (edgeCode == 3) {
      return 9
    }

    if (edgeCode == 4) {
      return 10
    }

    if (edgeCode == 5) {
      return 11
    }

    if (edgeCode == 6) {
      return 9
    }
    if (edgeCode == 7) {
      return 10
    }

    if (edgeCode == 8) {
      return 11
    }

    return null
  }
}

Maybe there is some clever way to do this, but I wanted to move forward & this one should solve it + it's fast enough, didn't affect any benchmarks. Optimized it a bit in style of:

_reuseEdgeIndex(edgeCode, reuseDirection) {
    if (edgeCode >= 9) return null;
    if (edgeCode <= 2) {
      const index = (edgeCode << 3) | reuseDirection;
      return REUSE_EDGE_LOOKUP[index];
    }
    return SIMPLE_LOOKUP[edgeCode];
  }
}

// Lookup table for edge codes 0-2
const REUSE_EDGE_LOOKUP = new Int8Array(24);  // 3 edge codes * 8 possible reuse directions
REUSE_EDGE_LOOKUP.fill(-1);  // -1 represents null
REUSE_EDGE_LOOKUP[0b000001] = 3;  REUSE_EDGE_LOOKUP[0b000100] = 6;  REUSE_EDGE_LOOKUP[0b000101] = 9;
REUSE_EDGE_LOOKUP[0b001010] = 4;  REUSE_EDGE_LOOKUP[0b001100] = 7;  REUSE_EDGE_LOOKUP[0b001110] = 10;
REUSE_EDGE_LOOKUP[0b010001] = 5;  REUSE_EDGE_LOOKUP[0b010010] = 8;  REUSE_EDGE_LOOKUP[0b010011] = 11;

// Simple lookup for edge codes 3-8
const SIMPLE_LOOKUP = [null, null, null, 9, 10, 11, 9, 10, 11];

, but kept idea the same.

Now I have 100% vertex reuse in every case except edges 81, 82, 83.

And btw, when I did this, I found out that handling corner cases differently is literally not needed at all, I was able to drop the corners from cellStorage as well as all the logic that differentiates the corners from non-corners altogether, because in such indexing scheme like above — corner indexing/reuse becomes kinda subset of edge, because every corner is anyway lying on some edge just with t == 0 or u == 0 and every edge now has a separate reuse index; In the end, with new indexing I threw away the whole corner logic and ended up with a super small loop for geometry:

It has a 100% full reuse for edge/corner cases, so if I shake vertices, you might see that only cracks are between chunks themselves (also I shake transitional cells — you might see a bit of more cracks there):

So in the end it is simpler / a lot shorter code; Didn't seem to affect performance, although given I'm in Javascript, profiling it doesn't make a lot of sense, need to rewrite to C++ first 😆 New modified tables are of same size too.

I understand it's anyway an unnecessary risk to implement any of it in current library (great job btw — it is amazing!). But just accidentally stumbled upon this comment and decided to share.

I'm learning gamedev right now; Started with terrain systems — so studying the paper. If you'd like to chat at any point — let me know what would be the preferrable way to do it. I do not have a lot to share that you could benefit from except for maybe this one finding.

But I'd love to hear about your experience with materials though — as I'm now learning this topic and a bit struggling, as I feel the approach in the paper won't work if I'd wanna blend between more complex materials, imagine grass (with geometry shader between vertex/fragment), etc.

[Zireael07]

Net hiccup? You posted the same comment like 6 times

[Zylann]

Thanks for posting this. I would need more time to understand that solution more in detail. For now I consider this is not an important issue so I'm not planning to fix that, but if someone finds a way to do it with no side-effects then a PR is welcome.