# Pascal Editor Spatial Grid Manager: Collision Detection and Placement Architecture

> Explore the Pascal Editor spatial grid manager for efficient collision detection and placement. Learn how its hash-based system ensures O(1) cell operations and interactive 3D editing.

- Repository: [Pascal/editor](https://github.com/pascalorg/editor)
- Tags: architecture
- Published: 2026-03-25

---

**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`](https://github.com/pascalorg/editor/blob/main/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`](https://github.com/pascalorg/editor/blob/main/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`](https://github.com/pascalorg/editor/blob/main/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`](https://github.com/pascalorg/editor/blob/main/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

```typescript
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`](https://github.com/pascalorg/editor/blob/main/packages/core/src/hooks/spatial-grid/spatial-grid-manager.ts)

### Validating Wall Placement with Auto-Adjustment

```typescript
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`](https://github.com/pascalorg/editor/blob/main/packages/core/src/hooks/spatial-grid/spatial-grid-manager.ts)

### Querying Slab Elevation

```typescript
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`](https://github.com/pascalorg/editor/blob/main/packages/core/src/hooks/spatial-grid/spatial-grid-manager.ts)

### Cleaning Up Wall Dependencies

```typescript
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`](https://github.com/pascalorg/editor/blob/main/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`](https://github.com/pascalorg/editor/blob/main/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`](https://github.com/pascalorg/editor/blob/main/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.