Creating a spatial hash table corresponding to https://www.carmencincotti.com/2022-10-31/spatial-hash-maps-part-one/

hashTableCreate.ts

  /**
   * Create the spatial hash table data structure - based off of
   * https://github.com/matthias-research/pages/blob/master/tenMinutePhysics/11-hashing.pdf
   * 
   * Theory:
   * https://www.carmencincotti.com/2022-10-31/spatial-hash-maps-part-one/
   *
   * Scroll down to Creating the Data Structure Slide
   */
  create(pos: Float32Array) {
    const numObjects = Math.min(pos.length / 3, this.particleMap.length);

    // Init arrays with 0. Our job is to fill these in.
    this.cellCount.fill(0);
    this.particleMap.fill(0);

    // Step 1: Count
    // Hash and iterate integer at index in arraycellCount 
    for (let i = 0; i < numObjects; i++) {
      const h = this.hashPos(pos, i);
      this.cellCount[h]++;
    }

    // Step 2: Partial sums
    // Mutate cellCount array to contain partial sum of all elements before current index
    let start = 0;
    for (let i = 0; i < this.tableSize; i++) {
      start += this.cellCount[i];
      this.cellCount[i] = start;
    }
    this.cellCount[this.tableSize] = start; // guard by adding an additional element at the end

    // Step 3: Fill in objects ids
    // Now finally fill in the particle array, particleMap
    for (let i = 0; i < numObjects; i++) {
      const h = this.hashPos(pos, i);
      this.cellCount[h]--;
      this.particleMap[this.cellCount[h]] = i;
    }
  }