Pascal Editor Spatial Grid Manager: Collision Detection and Placement Architecture

The Pascal Editor spatial grid manager uses a multi-layered hash-based coordinate system to enforce collision-free placement of architectural elements while maintaining interactive 3-D editing performance through O(1) cell operations and parametric wall representations.

The pascalorg/editor repository implements this spatial grid manager in the @pascal-app/core package, providing a framework-agnostic engine for validating item placement across floors, walls, and ceilings. This system ensures that furniture, structural elements, and fixtures never intersect illegally while supporting real-time drag-and-drop interactions in the React-based editor interface.

Architecture Overview

The spatial grid manager partitions the editor's 3-D space into specialized data structures optimized for different surface types. This layered approach allows precise collision detection without checking every object in the scene.

Floor and Ceiling Grids

The floor grid and ceiling grid both utilize the SpatialGrid class defined in packages/core/src/hooks/spatial-grid/spatial-grid.ts. These grids implement a 2-D spatial hash where each cell key follows the string format "x,z". When an item is inserted, its axis-aligned bounding box (AABB) is mapped to a set of cell keys, enabling constant-time insertion and retrieval. The ceiling grid reuses the same SpatialGrid implementation but keys cells by ceilingId to isolate different ceiling planes.

Wall Grid Representation

Walls employ a specialized WallSpatialGrid in packages/core/src/hooks/spatial-grid/wall-spatial-grid.ts. Rather than 2-D coordinates, this grid uses a 1-D parametric space where t = localX / wallLength (ranging from 0 to 1) combined with a vertical Y-range. This representation handles "wall-side" versus "wall" attachment types through the checkSideConflict() method, which ensures that side-mounted items only block their designated face while full-wall items obstruct both sides.

Slab Management

Slab polygons—which raise floor elevations—are managed through helper functions (pointInPolygon, itemOverlapsPolygon, wallOverlapsPolygon) inside packages/core/src/hooks/spatial-grid/spatial-grid-manager.ts. These functions use ray-casting algorithms to determine if points fall within slab boundaries or if line segments intersect polygon edges, respecting hole polygons where items should be ignored.

Manager Facade

The SpatialGridManager class orchestrates all four subsystems. It maintains dictionaries tracking walls, slabs, ceilings, and item-to-grid mappings while exposing public query APIs including canPlaceOnFloor(), canPlaceOnWall(), canPlaceOnCeiling(), and getSlabElevationForItem().

Collision Detection Mechanisms

The manager validates placements through surface-specific geometric tests that minimize computational overhead.

Floor and Ceiling Validation

When checking floor or ceiling placement via canPlaceOnFloor(), the candidate item's rotated footprint is converted to an AABB. The SpatialGrid.getItemCells() method calculates intersecting cell keys from the AABB limits, then the manager checks those cells for stored itemIds that are not in the caller-provided ignoreIds set. If any conflicting IDs are found, the placement is invalid.

Wall Collision Detection

Wall placement queries in canPlaceOnWall() project items onto the wall's parametric t space and vertical Y-range. Overlap detection uses an epsilon of 0.001 m to allow items to sit exactly adjacent without registering as collisions. The system auto-adjusts Y-positions when necessary, returning the adjusted value through the adjustedY and wasAdjusted response properties.

Slab Intersection Testing

For slab conflicts, the manager employs pointInPolygon with ray-casting to test item footprints against slab polygons. The getSlabElevationForItem() method returns the highest elevation found across all overlapping slabs, while wallOverlapsPolygon uses segmentIntersectsPolygon to detect when wall lines cross slab boundaries.

Lifecycle and State Management

The spatial grid manager maintains consistency through explicit lifecycle hooks that synchronize the spatial index with the scene graph.

Node Creation and Updates

When users add items, handleNodeCreated() populates the appropriate grid based on the attachment type (floor, wall, or ceiling) and updates internal maps for walls, slabs, and ceilings. For position changes, handleNodeUpdated() removes the old placement from the wall or ceiling grid before re-inserting the item with its new transform coordinates.

Deletion and Cleanup Operations

The handleNodeDeleted() method removes items from all grids, clears associated slab and ceiling maps, and—crucially for walls—returns the IDs of any attached items through the removedItemIds array. This allows the calling code in packages/editor/src/hooks/use-grid-events.ts to purge dependent objects from the scene graph when a wall is demolished.

Performance Optimizations

The implementation employs several micro-optimizations to sustain interactive frame rates during complex architectural editing.

Epsilon Nudges for Edge Cases: When points lie exactly on polygon edges, pointInPolygon can produce ambiguous results. The manager nudges test points by 1e-6 m before ray-casting to ensure consistent "inside" determinations.

Exclusive Upper Bounds: In SpatialGrid.getItemCells(), the calculation subtracts a tiny epsilon from maxX and maxZ coordinates. This prevents items that merely touch at borders from sharing a cell, eliminating false collision positives between adjacent but non-overlapping objects.

Parametric Wall Representation: By reducing wall items to 1-D intervals plus Y-ranges, collision checks scale with the number of items on that specific wall rather than the total scene object count, improving complexity from O(total items) to O(items on wall).

Package Integration

The spatial grid manager bridges the editor's core engine with its user interface through clean architectural boundaries.

The @pascal-app/core package contains the manager with zero UI or Three.js dependencies, allowing the @pascal-app/viewer package to query placement validity without importing editor-specific code. Conversely, apps/editor consumes the manager through the useGridEvents hook, which translates mouse drag-and-drop events into calls like spatialGridManager.canPlaceOnFloor() to enable or disable drop previews in real time.

Implementation Examples

Checking Floor Placement Validity

import { spatialGridManager } from '@pascal-app/core';

const pos: [number, number, number] = [2.3, 0, 4.7];
const dim: [number, number, number] = [1.0, 0.8, 0.5];
const rot: [number, number, number] = [0, Math.PI / 2, 0];

const result = spatialGridManager.canPlaceOnFloor('lvl-01', pos, dim, rot, ['item-123']);
if (result.valid) {
  spatialGridManager.handleNodeCreated(newItemNode, 'lvl-01');
} else {
  console.warn('Collision with:', result.conflictIds);
}

Source: SpatialGridManager.canPlaceOnFloor — packages/core/src/hooks/spatial-grid/spatial-grid-manager.ts

Validating Wall Placement with Auto-Adjustment

import { spatialGridManager } from '@pascal-app/core';

const { valid, conflictIds, adjustedY, wasAdjusted } =
  spatialGridManager.canPlaceOnWall(
    'lvl-01',
    'wall-57',
    1.2,                          // localX from wall start
    0.0,                          // desired bottom height
    [0.6, 2.2, 0.3],             // width, height, depth
    'wall-side',
    'front',
    []                           // ignoreIds
  );

if (valid) {
  const finalY = wasAdjusted ? adjustedY : 0.0;
  // Create item at [localX, finalY, 0] in wall-local space
}

Source: SpatialGridManager.canPlaceOnWall — packages/core/src/hooks/spatial-grid/spatial-grid-manager.ts

Querying Slab Elevation

import { spatialGridManager } from '@pascal-app/core';

const elevation = spatialGridManager.getSlabElevationForItem(
  'lvl-01',
  [3.0, 0, 5.0],
  [1.2, 0.8, 0.6],
  [0, Math.PI / 4, 0]
);

if (elevation > 0) {
  console.log(`Item sits on a slab at ${elevation.toFixed(2)} m`);
}

Source: SpatialGridManager.getSlabElevationForItem — packages/core/src/hooks/spatial-grid/spatial-grid-manager.ts

Cleaning Up Wall Dependencies

const removedItemIds = spatialGridManager.handleNodeDeleted(
  wallId,
  'wall',
  'lvl-01'
);

removedItemIds.forEach(id => scene.removeNode(id));

Source: SpatialGridManager.handleNodeDeleted — packages/core/src/hooks/spatial-grid/spatial-grid-manager.ts

Summary

• The spatial grid manager in packages/core/src/hooks/spatial-grid/spatial-grid-manager.ts coordinates four specialized subsystems: floor/ceiling grids, wall grids, and slab managers.
• Collision detection uses O(1) hash-based cell lookups for floors and ceilings, parametric 1-D intervals for walls, and ray-casting for slab polygons.
• Lifecycle hooks (handleNodeCreated, handleNodeUpdated, handleNodeDeleted) maintain index consistency while returning dependent item IDs for cleanup.
• Performance optimizations include epsilon nudging for edge cases, exclusive upper bounds to prevent border collisions, and parametric wall representations that limit query scope.
• The architecture separates core logic from UI concerns, allowing both the editor (apps/editor) and viewer packages to query placement through the same API.

Frequently Asked Questions

How does the spatial grid manager distinguish between wall-side and wall attachment types?

The WallSpatialGrid class in packages/core/src/hooks/spatial-grid/wall-spatial-grid.ts tracks attachment metadata during insertion. When checkSideConflict() evaluates potential collisions, it allows "wall-side" items to coexist with other items on the opposite face, while "wall" type items register as blockers for both sides of the wall surface.

What is the time complexity for placement queries in large scenes?

Floor and ceiling queries operate in near-constant time O(cells covered by AABB) regardless of total scene object count, due to the hash-based SpatialGrid implementation. Wall queries scale linearly with O(items on that wall) rather than O(total items), making the system responsive even with thousands of architectural elements.

How does the manager handle items spanning multiple slab polygons?

The getSlabElevationForItem() method iterates through all slabs in the specified level, testing the item's footprint against each polygon using pointInPolygon. It returns the highest elevation found among overlapping slabs, effectively placing the item on the uppermost surface while respecting hole polygons that exclude areas from consideration.

Can the spatial grid system be used independently of the Pascal Editor UI?

Yes. The @pascal-app/core package containing SpatialGridManager has no dependencies on React, Three.js, or other UI libraries. The viewer package and external scripts can import the manager directly to validate placements programmatically without loading the editor interface.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}