How to query spatial hash tables https://www.carmencincotti.com/2022-11-07/spatial-hash-maps-part-two/

hashTableQuery.ts

/**
   * Query for items in hash table
   * After execution, check results in:
   *    - queryIds - particle ids found in query
   *    - querySize - number of particles found
   * 
   * Theory:
   * https://www.carmencincotti.com/2022-11-07/spatial-hash-maps-part-two/
   */
  query(pos: Float32Array, nr: number, maxDist: number) {
    const x0 = this.intCoord(pos[3 * nr] - maxDist);
    const y0 = this.intCoord(pos[3 * nr + 1] - maxDist);
    const z0 = this.intCoord(pos[3 * nr + 2] - maxDist);

    const x1 = this.intCoord(pos[3 * nr] + maxDist);
    const y1 = this.intCoord(pos[3 * nr + 1] + maxDist);
    const z1 = this.intCoord(pos[3 * nr + 2] + maxDist);

    this.querySize = 0;

    for (let xi = x0; xi <= x1; xi++) {
      for (let yi = y0; yi <= y1; yi++) {
        for (let zi = z0; zi <= z1; zi++) {
          const h = this.hashCoords(xi, yi, zi);

          // Looking for a difference between two, like in slides
          const start = this.cellCount[h];
          const end = this.cellCount[h + 1];

          // If there is a difference, this cell has particles !
          // Save to queryIds
          for (let i = start; i < end; i++) {
            this.queryIds[this.querySize] = this.particleMap[i];
            this.querySize++;
          }
        }
      }
    }
  }


  /**
   * queryAll is responsible for looping through all particles, calling query() for each, and storing/updating 
   * the adjacent particles lists. 
   * 
   * Theory:
   * https://www.carmencincotti.com/2022-11-07/spatial-hash-maps-part-two/
   */
  queryAll(pos: Float32Array, maxDist: number) {
    // Keep track of all adjacent id's by indexing into
    // this.adjIds
    let idx = 0;

    // We only need this number to compare with dist2
    // We do not use square root to save ourselves
    // from the expensive calculation.
    const maxDist2 = maxDist * maxDist;

    for (let i = 0; i < this.maxNumObjects; i++) {
      const id0 = i;
      this.firstAdjId[id0] = idx;

      // Query for all particles within maxDist from this particle
      this.query(pos, id0, maxDist);

      // If particles found in query, register them in adjIds
      for (let j = 0; j < this.querySize; j++) {
        const id1 = this.queryIds[j];

        // Skip if id1 > id0, to ensure we only execute the following code once
        // Skip if id1 == id0 since a particle can't be adjacent to itself
        if (id1 >= id0) continue;

        // Calculate distance-squared between two particles
        // We do not use square root to save ourselves
        // from the expensive calculation. We just want
        // to compare with maxDist2
        const dist2 = vecDistSquared(pos, id0, pos, id1);

        if (dist2 > maxDist2) continue;

        // Because each particle can have n adjacencies,
        // we need to make sure we are ready to grow the array at a moments notice
        // Since we're saving all adjacencies in a single dense array
        if (idx >= this.adjIds.length) {
          const newIds = new Int32Array(2 * idx); // dynamic array
          newIds.set(this.adjIds);
          this.adjIds = newIds;
        }
        this.adjIds[idx++] = id1;
      }
    }

    // Manually set the last extra space with current idx
    this.firstAdjId[this.maxNumObjects] = idx;
  }
}