BSP BVH ray tracing for sky occlusion and entity picking #31

New issue

Closed

opened 2026-03-19 04:30:28 +00:00 by kit · 0 comments

kit commented

2026-03-19 04:30:28 +00:00

Owner

Build a BVH (Bounding Volume Hierarchy) from BSP face triangles for accelerated ray tracing. This serves two purposes:

Skylight occlusion — trace from entity toward sun, check if first hit is a sky surface or solid geometry
Entity picker (#10) — trace from camera through mouse position to find intersecting entities

Current state

Leaf sky flags give coarse indoor/outdoor distinction but miss per-entity shadows
The BSP ray trace through the node tree couldn't distinguish sky brushes from solid walls
We need per-face surface classification (sky vs solid) for accurate traces

Implementation

BVH construction (BSP only)

Extract all triangles from BSP meshes (mapGroup + sky3DGroup)
The BVH contains only BSP geometry — no entities. This keeps the BVH static and avoids rebuilding when entities move.
Tag each triangle with its source mesh's texture name (to identify __sky faces)
Build a binary BVH using surface area heuristic (SAH) or midpoint split
~46K triangles on gm_construct — BVH should give O(log n) trace time

Ray-triangle intersection

Möller–Trumbore algorithm for ray-triangle intersection
Return hit distance, hit normal, and whether the hit face is sky-textured

Sky visibility trace

Trace from entity position in the direction opposite to sun normal
If first hit is a __sky triangle → entity is in sunlight (return true)
If first hit is any other triangle → entity is in shadow (return false)
If no hit → entity is in shadow (ray went to infinity without hitting anything)

Entity picker trace (future, layered approach)

The entity picker does NOT use the BVH for entities. Instead it uses a layered approach:

BSP trace — trace against the BVH to get the nearest BSP hit distance (max distance threshold)
Entity AABB filter — test the ray against every entity's axis-aligned bounding box to cheaply filter out entities nowhere near the ray
Entity triangle test — for the remaining candidate entities, test against their actual mesh triangles to find precise intersection
Distance comparison — only return an entity hit if it's closer than the BSP hit

This avoids putting entities in the BVH (which would require rebuilds on movement) while still giving accurate picking. The AABB filter is cheap enough to run against all entities each frame.

Context

BSP mesh data: client/src/bsp/loader.js (mapGroup, sky3DGroup)
Current sky occlusion: client/src/bsp/leaf-lighting.js (leafHasSkyVisibility)
Entity picker issue: #10
Relates to #30 (lightcache system)

Build a BVH (Bounding Volume Hierarchy) from BSP face triangles for accelerated ray tracing. This serves two purposes: 1. **Skylight occlusion** — trace from entity toward sun, check if first hit is a sky surface or solid geometry 2. **Entity picker** (#10) — trace from camera through mouse position to find intersecting entities ## Current state - Leaf sky flags give coarse indoor/outdoor distinction but miss per-entity shadows - The BSP ray trace through the node tree couldn't distinguish sky brushes from solid walls - We need per-face surface classification (sky vs solid) for accurate traces ## Implementation ### BVH construction (BSP only) - Extract all triangles from BSP meshes (mapGroup + sky3DGroup) - **The BVH contains only BSP geometry — no entities.** This keeps the BVH static and avoids rebuilding when entities move. - Tag each triangle with its source mesh's texture name (to identify `__sky` faces) - Build a binary BVH using surface area heuristic (SAH) or midpoint split - ~46K triangles on gm_construct — BVH should give O(log n) trace time ### Ray-triangle intersection - Möller–Trumbore algorithm for ray-triangle intersection - Return hit distance, hit normal, and whether the hit face is sky-textured ### Sky visibility trace - Trace from entity position in the direction opposite to sun normal - If first hit is a `__sky` triangle → entity is in sunlight (return true) - If first hit is any other triangle → entity is in shadow (return false) - If no hit → entity is in shadow (ray went to infinity without hitting anything) ### Entity picker trace (future, layered approach) The entity picker does NOT use the BVH for entities. Instead it uses a layered approach: 1. **BSP trace** — trace against the BVH to get the nearest BSP hit distance (max distance threshold) 2. **Entity AABB filter** — test the ray against every entity's axis-aligned bounding box to cheaply filter out entities nowhere near the ray 3. **Entity triangle test** — for the remaining candidate entities, test against their actual mesh triangles to find precise intersection 4. **Distance comparison** — only return an entity hit if it's closer than the BSP hit This avoids putting entities in the BVH (which would require rebuilds on movement) while still giving accurate picking. The AABB filter is cheap enough to run against all entities each frame. ## Context - BSP mesh data: `client/src/bsp/loader.js` (mapGroup, sky3DGroup) - Current sky occlusion: `client/src/bsp/leaf-lighting.js` (leafHasSkyVisibility) - Entity picker issue: #10 - Relates to #30 (lightcache system)