Game Spatial Queries

Game Spatial Queries

Use this skill to turn game picking, collision, containment, and distance questions into small geometric systems with explicit constraints and failure cases.

Primary source: Geometry for Programmers by Oleksandr Kaleniuk (https://www.manning.com/books/geometry-for-programmers), transformed and paraphrased, especially chapters 3, 4, and 9. Additional source: "Fast, Minimum Storage Ray-Triangle Intersection" by Tomas Moller and Ben Trumbore (https://dl.acm.org/doi/10.1145/1198555.1198746).

Core Workflow

1. State the query as a predicate or measured value: hit/miss, inside/outside, closest distance, signed side, intersection point, or parameter value.
2. Move into the simplest local basis when possible. Triangle, segment, plane, and object-local bases often reduce the query to bounds checks.
3. Derive parameters first, then apply constraints. Keep constraints visible in code instead of burying them in one large expression.
4. Identify denominator, orientation, or length values that signal degeneracy.
5. Choose a numeric policy: exact integer predicate, scale-aware epsilon, inclusive boundary, exclusive boundary, or conservative fallback.
6. Test hit, miss, boundary, parallel, degenerate, and near-degenerate cases.
7. Add a debug visualization when the query affects gameplay feel.

Query Patterns

Ray Against Triangle

Model the ray as R = P + t*d with t >= 0. Model triangle points as S = A + u*AB + v*AC with u >= 0, v >= 0, and u + v <= 1.

Solve R = S, then:

• Reject when the shared denominator is zero or too small for the numeric policy.
• Reject when t < 0.
• Reject when u < 0, v < 0, or u + v > 1.
• Return hit distance t, barycentric-like parameters u and v, and the hit point when needed.