Navigating through Triangle Meshes Implemented as Linear Quadtrees

icos_indexer.js

'use strict'
/*
 * Adapted from: https://github.com/rpsirois/icosindexer
 * Who aadapted it from: Lee, Michael and Samet, Hanan. (April 2000).
 *     Navigating through Triangle Meshes Implemented as Linear Quadtrees.
 *     ACM Transactions on Graphics, Vol. 19, No. 2.
 *     Retrieved from https://pdfs.semanticscholar.org/a5c8/8b53174405e5ff512ff5ffa8a56df3c8e2df.pdf
 *
 * Authors:
 * - [Robert Sirois](https://github.com/rpsirois)
 * - [Brandon Brown](https://github.com/RB-bro)
 * - [Shane Holloway](https://github.com/shanewholloway)
 *
 */

const STOPTAB = {
  '0': [ false, false, true  ],
  '1': [ false, true,  false ],
  '2': [ true,  true,  true  ],
  '3': [ true,  false, false ],
}

/*
       /\\        \\--------------/
      /  \\        \\  1  /\\  3 /
     /  0 \\        \\   /  \\  /
    /------\\        \\ /  2 \\/
   /\\  2 / \\        \\------/
  /  \\  /   \\        \\  0 /
 /  1 \\/  3  \\        \\  /
/--------------\\        \\/
*/

const NEXTTAB = {
  '0': '312',
  '1': '021',
  '2': '130',
  '3': '203',
}

/*
  /\\    /\\    /\\    /\\    /\\
 /  \\  /  \\  /  \\  /  \\  /  \\
/  A \\/  B \\/  C \\/  D \\/  E \\
-----------------------------------
\\  F /\\  G /\\  H /\\  I /\\  J /\\
 \\  /  \\  /  \\  /  \\  /  \\  /  \\
  \\/  K \\/  L \\/  M \\/  N \\/  O \\
   ------------------------------------
    \\  P /\\  Q /\\  R /\\  S /\\  T /
     \\  /  \\  /  \\  /  \\  /  \\  /
      \\/    \\/    \\/    \\/    \\/

*/

const NEXTTOP = {
  A: 'EBF', B: 'ACG', C: 'BDH', D: 'CEI', E: 'DAJ',
  F: 'OKA', G: 'KLB', H: 'LMC', I: 'MND', J: 'NOE',
  K: 'FGP', L: 'GHQ', M: 'HIR', N: 'IJS', O: 'JFT',
  P: 'TQK', Q: 'PRL', R: 'QSM', S: 'RTN', T: 'SPO',
}

// special case for nodes 0-4 and 15-19
const REFLTOP = {
  '0': [ '0', '0', '2' ],
  '1': [ '3', null, '1' ],
  '2': [ null, null, '0' ],
  '3': [ null, '1', '3' ]
}
const TOPNEIGHBOR = {
  A: REFLTOP, B: REFLTOP, C: REFLTOP, D: REFLTOP, E: REFLTOP,
  F: NEXTTAB, G: NEXTTAB, H: NEXTTAB, I: NEXTTAB, J: NEXTTAB,
  K: NEXTTAB, L: NEXTTAB, M: NEXTTAB, N: NEXTTAB, O: NEXTTAB,
  P: REFLTOP, Q: REFLTOP, R: REFLTOP, S: REFLTOP, T: REFLTOP,
}

function find_neighbor(direction, code) {
  code = Array.from(code)
  let initDepth = code.length - 1
  let depth = initDepth
  let childType = code[depth]

  // Algorithm 1: get nearest common ancestor (nca)
  while ((depth > 0) && !STOPTAB[childType][direction])
    childType = code[--depth]

  // Algorithm 2: set path and to child in nca and its type
  if (depth > 0)
    code[depth] = NEXTTAB[childType][direction]
  else code[0] = NEXTTOP[childType][direction]

  // Algorithm 3: path from step 2 to neighbor
  let tab = depth <= 0 ? TOPNEIGHBOR[childType] : NEXTTAB
  while (depth++ < initDepth) {
    childType = code[depth]
    code[depth] = tab[childType][direction]
  }

  return code.join('')
}



if (module === require.main) {
  const assert = require('assert')

  assert.equal(find_neighbor(0, 'K222'), 'K221')
  assert.equal(find_neighbor(1, 'K222'), 'K223')
  assert.equal(find_neighbor(2, 'K222'), 'K220')
  assert.equal(find_neighbor(1, 'E033'), 'A011')


  const mirror = (direction, code) => {
    let destination = find_neighbor(direction,  code)
    let secondDestination = [1,0,2].map(reverseDirection =>
       find_neighbor(reverseDirection, destination))
    return secondDestination.indexOf(code) }

  const testLevel = level =>
    level.map(code =>
      [0,1,2].map(direction =>
        assert.equal(mirror(direction, code), direction)))

  const _childLevel = Object.keys(STOPTAB)
  const nLevels = (n, testEach) => {
    if (n <= 1) return Object.keys(NEXTTOP)
    let curLevel = nLevels(n-1)
      .reduce((l,tl) => l.concat(_childLevel.map(sl => tl+sl)), [])

    if (testEach) testLevel(curLevel)
    //console.log(curLevel.length)
    return curLevel }

  const lastLevel = nLevels(6)
  testLevel(lastLevel)
  console.log(lastLevel)
}

Now in JSY mode! https://gist.github.com/rpsirois/3b34a5a94527b7a6ebd7ff183275a986