Navigating through Triangle Meshes Implemented as Linear Quadtrees

.gitattributes

*.jsy linguist-language=js

README.md

Icosahedron Indexer

Adapted 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

https://pdfs.semanticscholar.org/a5c8/8b53174405e5ff512ff5ffa8a56df3c8e2df.pdf

Thanks shanewholloway for all the assistance.

Usage

jsy-transpile icos_indexer.jsy > icos_indexer.mjs
node icos_indexer.mjs

icos_indexer.jsy

import { fileURLToPath } from 'url'
import process from 'process'
import assert from 'node:assert/strict'
/*
 * Adapted from: https://github.com/rpsirois/icosindexer
 * Who adapted 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
 * Who now adapted is back from https://gist.github.com/shanewholloway/8987507c06583ff5a5f33012fa10ab9d
 *  in order to rewrite it in JSY :) https://jsy-lang.github.io/
 *
 * 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 process.argv[1] === fileURLToPath @ import.meta.url ::
  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