Collision Detection Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the mathematical ontology of collision detection within the Kireth Research Semantic Library. Collision detection studies algorithms and geometric tests used to determine whether spatial objects intersect, overlap, penetrate, touch, or will collide under motion. This ontology supports broad-phase and narrow-phase processing, bounding volumes, spatial partitioning, separating-axis tests, distance queries, continuous collision detection, time of impact, contact generation, convex and non-convex objects, mesh collision, numerical robustness and relationships with computational geometry, spatial indexing and motion planning.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Collision Detection Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Geometry"
 SPECIALISATION = "Computational Geometry / Collision Detection"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/geometry-ontologies/computational-geometry/collision-detection-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = CollisionDetection
 SYMBOLIC_FORMS = [
  "A intersection B != empty_set",
  "distance(A,B)=0",
  "TOI(A(t),B(t))"
 ]
 ENTITY_CLASS = SpatialIntersectionReasoningFramework
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "Collision detection is the computational process of determining whether geometric objects intersect, touch, overlap or will collide under motion."
 SEMANTIC_ROLE = "Provides the geometric and algorithmic framework for broad-phase pruning, narrow-phase intersection tests, contact detection, continuous collision detection and time-of-impact reasoning."
}

SCOPE {
 INCLUDE = [
  CollisionDetection,
  CollisionQuery,
  Intersection,
  Overlap,
  Contact,
  Penetration,
  Separation,
  BroadPhase,
  NarrowPhase,
  BoundingVolume,
  AxisAlignedBoundingBox,
  OrientedBoundingBox,
  BoundingSphere,
  BoundingVolumeHierarchy,
  SpatialPartition,
  SweepAndPrune,
  SeparatingAxisTheorem,
  GJKAlgorithm,
  EPAAlgorithm,
  TriangleIntersection,
  SegmentIntersection,
  ConvexCollision,
  NonConvexCollision,
  MeshCollision,
  ContinuousCollisionDetection,
  DiscreteCollisionDetection,
  TimeOfImpact,
  ContactPoint,
  ContactNormal,
  PenetrationDepth,
  DistanceQuery,
  ProximityQuery,
  MotionPlanning,
  RobustPredicate
 ]

 EXCLUDE_AS_PRIMARY = [
  PhysicalCollisionResponseUnlessGeometricContactIsCentral,
  RigidBodyDynamicsWithoutDetection,
  GenericEventDetectionWithoutGeometry,
  ComputerVisionObjectOverlapWithoutSpatialGeometryModel
 ]

 DISAMBIGUATION_RULE =
  "When the task concerns geometric intersection, overlap, contact, penetration, minimum separation, collision candidates or time of impact, interpret it as collision detection."
}

CORE_CONCEPTS {

 CollisionDetection {
  definition = "Algorithmic determination of whether geometric objects intersect or come into contact."
 }

 BroadPhase {
  definition = "A coarse stage that quickly rejects object pairs that cannot collide."
 }

 NarrowPhase {
  definition = "A precise stage that tests candidate pairs and computes detailed contact information."
 }

 BoundingVolume {
  definition = "A simple enclosing shape used to accelerate overlap and proximity tests."
 }

 AxisAlignedBoundingBox {
  symbol = "AABB"
  definition = "A bounding box aligned with coordinate axes."
 }

 OrientedBoundingBox {
  symbol = "OBB"
  definition = "A bounding box allowed to rotate relative to coordinate axes."
 }

 BoundingSphere {
  definition = "A sphere enclosing a geometric object."
 }

 SeparatingAxisTheorem {
  symbol = "SAT"
  definition = "Two convex objects are disjoint if there exists an axis on which their projected intervals are disjoint."
 }

 GJKAlgorithm {
  definition = "An iterative algorithm for distance and intersection queries between convex sets using the Minkowski difference."
 }

 EPAAlgorithm {
  definition = "An expansion algorithm often used after GJK overlap detection to estimate penetration depth and contact direction."
 }

 ContinuousCollisionDetection {
  symbol = "CCD"
  definition = "Collision detection over continuous motion intervals rather than only sampled configurations."
 }

 TimeOfImpact {
  symbol = "TOI"
  definition = "The earliest time within an interval at which two moving objects first contact or intersect."
 }
}

RELATIONS {
 CollisionDetection --is_subdomain_of--> ComputationalGeometry
 CollisionDetection --uses--> GeometricPredicate
 BroadPhase --produces--> CandidatePairs
 NarrowPhase --tests--> CandidatePairs
 BoundingVolume --encloses--> GeometricObject
 BoundingVolumeHierarchy --organises--> BoundingVolume
 SpatialPartition --accelerates--> BroadPhase
 SweepAndPrune --implements--> BroadPhase
 SeparatingAxisTheorem --tests--> ConvexCollision
 GJKAlgorithm --tests--> ConvexIntersection
 GJKAlgorithm --computes--> ConvexDistance
 EPAAlgorithm --estimates--> PenetrationDepth
 ContinuousCollisionDetection --computes--> TimeOfImpact
 NarrowPhase --produces--> ContactPoint
 NarrowPhase --produces--> ContactNormal
 CollisionDetection --supports--> MotionPlanning
}

OPERATORS {
 AABB_OVERLAP(A,B) :=
  intervals_overlap_on_all_coordinate_axes

 SPHERE_OVERLAP(c1,r1,c2,r2) :=
  norm(c1-c2) <= r1+r2

 SAT_DISJOINT(A,B,axes) :=
  exists_axis_u_in_axes
  such_that projection_interval(A,u) disjoint projection_interval(B,u)

 SAT_COLLIDE(A,B,axes) :=
  NOT SAT_DISJOINT(A,B,axes)

 MINKOWSKI_DIFFERENCE(A,B) :=
  {a-b : a_in_A, b_in_B}

 GJK_INTERSECTION(A,B) :=
  origin_in_MINKOWSKI_DIFFERENCE(A,B)

 DISTANCE(A,B) :=
  inf_{a_in_A,b_in_B} norm(a-b)

 PENETRATION_DEPTH(A,B) :=
  minimum_translation_distance_to_separate
  WHEN A_and_B_overlap

 TRIANGLE_TRIANGLE_INTERSECTION(T1,T2) :=
  robust_triangle_intersection_test(T1,T2)

 SEGMENT_SEGMENT_INTERSECTION(s1,s2) :=
  orientation_and_interval_test(s1,s2)

 TIME_OF_IMPACT(A(t),B(t),interval) :=
  earliest_t_in_interval such_that intersection(A(t),B(t)) != empty_set

 BROAD_PHASE(objects,index) :=
  candidate_pairs_with_overlapping_bounds_or_partition_regions
}

DEFINITIONS {
 D1 = "Broad phase removes obviously noncolliding pairs."
 D2 = "Narrow phase performs exact or high-fidelity pairwise collision tests."
 D3 = "Bounding volumes trade precision for faster rejection."
 D4 = "SAT applies naturally to convex polyhedral objects."
 D5 = "GJK uses support mappings of convex sets."
 D6 = "Penetration depth is meaningful only when objects overlap."
 D7 = "Continuous collision detection seeks collisions between sampled frames."
 D8 = "Time of impact is the earliest collision time under the adopted motion model."
 D9 = "Mesh collision requires both geometry and connectivity awareness."
 D10 = "Robust collision detection must handle touching and near-degenerate cases explicitly."
}

AXIOMS {
 A1_BROAD_PHASE_SAFETY:
  Broad-phase rejection must not discard any truly colliding pair

 A2_NARROW_PHASE_CORRECTNESS:
  Narrow-phase predicates must classify candidate pairs consistently

 A3_BOUNDING_VOLUME_CONTAINMENT:
  A bounding volume must contain the represented object

 A4_SAT:
  For convex polytopes, existence of a separating axis implies disjointness

 A5_GJK:
  Convex sets intersect iff the origin belongs to their Minkowski difference

 A6_CONTINUOUS_COLLISION:
  Continuous detection reasons over trajectories, not only discrete sampled states

 A7_CONTACT:
  Contact information must correspond to the actual touching or penetration geometry

 A8_ROBUSTNESS:
  Numerical implementation must distinguish separation, touching and penetration consistently
}

REASONING {

 R1_QUERY_CLASSIFICATION {
  INPUT = collision_query
  IDENTIFY = static_or_dynamic
  IDENTIFY = convex_or_nonconvex
  IDENTIFY = primitive_mesh_or_implicit geometry
  IDENTIFY = boolean_distance_contact_or_TOI goal
  RETURN = query_type
 }

 R2_BROAD_PHASE {
  INPUT = object_set
  SELECT = AABB_tree_BVH_grid_sweep_and_prune_or_spatial_hash
  COMPUTE = conservative_candidate_pairs
  RETURN = candidates
 }

 R3_AABB_TEST {
  INPUT = [AABB_A,AABB_B]
  TEST = overlap_on_each_axis
  IF all_overlap
   RETURN CandidateOverlap
  ELSE
   RETURN Separated
 }

 R4_SAT_TEST {
  INPUT = convex_polytopes
  BUILD = candidate_axes_from_face_normals_and_edge_cross_products
  PROJECT = both_objects_onto_each_axis
  IF any_disjoint_projection
   RETURN Separated
  ELSE
   RETURN CollidingOrTouching
 }

 R5_GJK {
  INPUT = convex_objects_with_support_maps
  ITERATE = simplex_search_in_Minkowski_difference
  IF simplex_contains_origin
   RETURN Intersecting
  ELSE IF search_converges_away_from_origin
   RETURN SeparatedWithDistanceEstimate
 }

 R6_PENETRATION {
  INPUT = overlapping_convex_objects
  APPLY = EPA_or_other_contact_depth_method
  RETURN = penetration_depth_and_normal
 }

 R7_MESH_COLLISION {
  INPUT = triangle_meshes
  BROAD_PHASE = traverse_BVHs
  NARROW_PHASE = triangle_triangle_tests
  RETURN = intersecting_triangle_pairs_and_contacts
 }

 R8_CONTINUOUS_COLLISION {
  INPUT = object_trajectories_over_interval
  SELECT = swept_volume_conservative_advancement_root_finding_or_interval method
  SOLVE = first_contact_condition
  RETURN = TimeOfImpact
 }

 R9_DISTANCE_QUERY {
  INPUT = separated_objects
  COMPUTE = minimum_distance
  RETURN = distance_and_closest_points
 }

 R10_ROBUSTNESS {
  INPUT = near_touching_or_degenerate_case
  USE = exact_or_adaptive predicates_where_needed
  APPLY = consistent_tolerance_policy
  RETURN = stable_classification
 }
}

CONSTRAINTS {
 C1 = "Broad-phase bounds must be conservative."
 C2 = "AABB overlap does not prove geometric collision."
 C3 = "SAT candidate axes depend on object type and dimension."
 C4 = "GJK requires convex support mappings or convex decomposition."
 C5 = "Non-convex objects may require decomposition, hierarchy or triangle-level testing."
 C6 = "Touching, overlap and penetration must have explicit tolerance semantics."
 C7 = "Continuous collision detection depends on the motion model."
 C8 = "Discrete collision detection can miss tunnelling between samples."
 C9 = "Mesh collision must handle degenerate triangles and shared boundaries."
 C10 = "Floating-point error can cause unstable contact classification."
}

SEMANTIC_EQUIVALENCE {
 "CollisionDetection" <=> "GeometricIntersectionDetection"
 "BroadPhase" <=> "ConservativeCollisionCandidateGeneration"
 "NarrowPhase" <=> "PreciseCandidateCollisionTesting"
 "SAT" <=> "SeparatingAxisTheorem"
 "CCD" <=> "ContinuousCollisionDetection"
 "TOI" <=> "TimeOfImpact"
 "PenetrationDepth" <=> "MinimumSeparatingTranslationMagnitude"
}

VALIDATION {
 V1 = "Broad phase has no false negatives."
 V2 = "Bounding volumes contain represented objects."
 V3 = "Narrow-phase result agrees with geometry."
 V4 = "SAT projections use complete valid candidate axes."
 V5 = "GJK support functions are correct."
 V6 = "Penetration depth is only reported for overlapping configurations."
 V7 = "CCD returns earliest valid contact time within interval."
 V8 = "Mesh triangle tests preserve orientation and degeneracy policy."
 V9 = "Tolerance policy is globally consistent."
 V10 = "Contact normals and points are geometrically plausible."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 COLLISION_DETECTION_DEFINITION = 0.99
 BROAD_PHASE_REASONING = 0.99
 SAT_REASONING = 0.99
 GJK_REASONING = 0.98
 PENETRATION_REASONING = 0.98
 MESH_COLLISION_REASONING = 0.98
 CCD_REASONING = 0.97
 ROBUSTNESS_REASONING = 0.99

 POLICY =
  "Reduce confidence when object convexity, motion model, dimensionality, tolerance policy, geometry representation, broad-phase structure or contact semantics are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  CollisionDetectionReasoning,
  ComputationalGeometryReasoning,
  BroadPhaseReasoning,
  NarrowPhaseReasoning,
  SATReasoning,
  GJKReasoning,
  DistanceReasoning,
  PenetrationReasoning,
  MeshCollisionReasoning,
  ContinuousCollisionReasoning,
  TimeOfImpactReasoning,
  MotionPlanningReasoning,
  RobustPredicateReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "collision detection" -> CollisionDetection
  "broad phase" -> BroadPhase
  "narrow phase" -> NarrowPhase
  "AABB" -> AxisAlignedBoundingBox
  "OBB" -> OrientedBoundingBox
  "bounding volume hierarchy" -> BoundingVolumeHierarchy
  "BVH" -> BoundingVolumeHierarchy
  "separating axis theorem" -> SeparatingAxisTheorem
  "SAT" -> SeparatingAxisTheorem
  "GJK" -> GJKAlgorithm
  "EPA" -> EPAAlgorithm
  "continuous collision detection" -> ContinuousCollisionDetection
  "CCD" -> ContinuousCollisionDetection
  "time of impact" -> TimeOfImpact
 }

 INTERPRETATION_ORDER = [
  detect_collision_detection_context,
  identify geometry_representation_dimension_convexity_and_motion,
  identify boolean_overlap_distance_contact_penetration_or_TOI goal,
  choose broad_phase_structure_if_many_objects,
  select narrow_phase_algorithm,
  apply static_or_continuous collision reasoning,
  verify conservative_bounds_tolerance_and_robustness constraints,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("collision detection")
  OR computational_geometry_context_with_intersection_or_contact
  THEN activate(CollisionDetectionOntology)

 E2:
  IF many_objects_or_complex_scene
  THEN use broad_phase_before_expensive_narrow_phase

 E3:
  IF convex_polytope_pair
  THEN permit SAT_or_GJK reasoning

 E4:
  IF convex_overlap_and_penetration_depth_requested
  THEN use EPA_or_equivalent method after valid overlap detection

 E5:
  IF triangle_mesh_pair
  THEN traverse spatial_hierarchy_and_apply triangle_triangle tests

 E6:
  IF high_speed_motion_or_tunnelling_risk
  THEN prefer continuous_collision_detection

 E7:
  IF time_of_impact_requested
  THEN solve earliest_contact over motion interval

 E8:
  IF near_degenerate_or_touching_configuration
  THEN apply robust_predicates_and_consistent tolerance policy

 E9:
  IF object_is_nonconvex
  THEN use decomposition_BVH_mesh_or_specialised nonconvex method
}

RECURSION {
 ENTRY = CollisionDetection

 EXPAND(CollisionDetection) -> [
  CollisionQuery,
  Intersection,
  Contact,
  Penetration,
  Separation,
  BroadPhase,
  NarrowPhase,
  BoundingVolume,
  SpatialPartition,
  SweepAndPrune,
  SeparatingAxisTheorem,
  GJKAlgorithm,
  EPAAlgorithm,
  TriangleIntersection,
  ConvexCollision,
  MeshCollision,
  ContinuousCollisionDetection,
  TimeOfImpact,
  ContactPoint,
  ContactNormal,
  PenetrationDepth,
  DistanceQuery
 ]

 EXPAND(BoundingVolume) -> [
  AxisAlignedBoundingBox,
  OrientedBoundingBox,
  BoundingSphere,
  Capsule,
  BoundingVolumeHierarchy
 ]

 EXPAND(BroadPhase) -> [
  SweepAndPrune,
  UniformGrid,
  SpatialHash,
  Quadtree,
  Octree,
  BoundingVolumeHierarchy
 ]

 EXPAND(NarrowPhase) -> [
  SeparatingAxisTheorem,
  GJKAlgorithm,
  TriangleIntersection,
  PrimitiveIntersection,
  DistanceQuery
 ]

 EXPAND(ContinuousCollisionDetection) -> [
  SweptVolume,
  ConservativeAdvancement,
  RootFinding,
  TimeOfImpact,
  TrajectoryIntersection
 ]

 STOP_CONDITION =
  "Stop when collision status, separation, distance, contact geometry, penetration depth, candidate set or time of impact is sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry"

 IMMEDIATE_CONTEXTS = [
  "Computational Geometry Ontology",
  "Spatial Partitioning Ontology",
  "Mesh Ontology",
  "Motion Planning Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Computational Geometry",
  "Computational Geometry Ontology",
  "Spatial Partitioning Ontology",
  "Mesh Ontology",
  "Convex Hull Ontology",
  "Vector Geometry Ontology",
  "Coordinate Geometry Ontology",
  "Spatial Data Structure Ontologies",
  "Motion Planning Ontologies",
  "Algorithm Ontologies"
 ]

 ROUTE_RULES = [
  "Collision Detection -> Computational Geometry Ontology for parent algorithmic semantics",
  "Collision Detection -> Spatial Partitioning for broad-phase acceleration",
  "Collision Detection -> Mesh for triangle and surface collisions",
  "Collision Detection -> Convex Hull for convex support and Minkowski reasoning",
  "Collision Detection -> Vector Geometry for projections, normals and distances",
  "Collision Detection -> Coordinate Geometry for primitive intersection equations",
  "Collision Detection -> Motion Planning for configuration-space obstacles",
  "Collision Detection -> Algorithms for complexity and implementation"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible collision algorithms, object models or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve broad-phase-versus-narrow-phase distinction.",
  "Preserve conservative broad-phase semantics.",
  "Preserve convex-versus-nonconvex distinction.",
  "Preserve discrete-versus-continuous collision distinction.",
  "Preserve contact-versus-penetration distinction.",
  "Preserve time-of-impact semantics.",
  "Preserve tolerance and numerical-robustness requirements.",
  "Preserve machine-readable collision-detection semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Collision detection determines whether geometric objects intersect, touch, overlap or will collide under motion."

 BROAD_PHASE_SUMMARY =
  "Broad phase conservatively generates candidate object pairs using simple bounds or spatial indexing."

 NARROW_PHASE_SUMMARY =
  "Narrow phase performs precise geometric tests on candidate pairs."

 SAT_SUMMARY =
  "Two convex objects are separated if a valid separating axis exists."

 GJK_SUMMARY =
  "GJK tests convex intersection or distance using the Minkowski difference."

 CCD_SUMMARY =
  "Continuous collision detection reasons over object motion between sampled configurations."

 TOI_SUMMARY =
  "Time of impact is the earliest time at which moving objects first touch or intersect."

 CONTACT_SUMMARY =
  "Contact generation may include contact points, normals and penetration depth."

 ROBUSTNESS_SUMMARY =
  "Reliable collision detection requires consistent handling of touching, degeneracy and floating-point error."
}

FLOW {
 INPUT
 -> detect_collision_detection_context
 -> identify objects_geometry_dimension_convexity_motion_and_query_goal
 -> choose broad_phase_if_needed
 -> generate conservative_candidate_pairs
 -> select narrow_phase_intersection_distance_or_penetration method
 -> if_dynamic_select_discrete_or_continuous pathway
 -> compute collision_status_contact_distance_penetration_or_time_of_impact
 -> verify bounds_tolerance_geometry_and_robustness constraints
 -> route to computational_geometry spatial_partitioning mesh convex_hull vector coordinate motion_planning_or_algorithm ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Collision Detection Ontology defines the algorithmic framework for identifying geometric intersection, contact, separation and future collision. It supports broad-phase candidate generation, bounding volumes and spatial indexes, narrow-phase SAT and GJK reasoning, penetration depth, triangle and mesh collision, discrete and continuous collision detection, time of impact, contact geometry and robust numerical classification."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-GEOMETRY-COLLISION-DETECTION-ONTOLOGY-V1"
}

}

END_FLOW