Collision Detection Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Collision Detection Ontology 2 within the Kireth Research Semantic Library. Collision detection determines whether geometric objects intersect or come within a specified proximity and identifies relevant contact information. This ontology supports broad-phase and narrow-phase detection, bounding volumes, spatial partitioning, separating-axis tests, GJK and EPA relationships, continuous collision detection, swept volumes, time of impact, contact manifolds, robustness, degeneracy handling, complexity, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = CollisionDetection
 ENTITY_CLASS = GeometricIntersectionAndProximityFramework
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "Collision detection is the algorithmic determination of whether geometric objects overlap, intersect or contact, optionally including contact features, penetration information and time of impact."
 SYMBOLIC_FORMS = [
  "intersect(A,B) -> {true,false}",
  "distance(A,B)<=epsilon -> contact",
  "TOI=min{t>=0 | A(t) intersects B(t)}",
  "separating_axis_exists(A,B) -> no_collision"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for broad-phase pruning, narrow-phase intersection tests, distance and penetration queries, continuous collision detection, contact generation, robustness and verification."
}

SCOPE {
 INCLUDE = [
  CollisionDetection,IntersectionDetection,ContactDetection,
  ProximityDetection,OverlapTest,IntersectionTest,
  GeometricObject,RigidBody,DeformableBody,
  ConvexObject,ConcaveObject,Polygon,Polyhedron,
  Triangle,TriangleMesh,Segment,Ray,Plane,Sphere,
  Capsule,Cylinder,Box,AABB,OBB,
  BoundingVolume,BoundingSphere,BoundingBox,
  BoundingVolumeHierarchy,BVH,AABBTree,OBBTree,
  SpatialPartitioning,UniformGrid,SpatialHashing,
  Quadtree,Octree,KDTree,BSPTree,
  BroadPhaseCollision,NarrowPhaseCollision,
  CandidatePair,PairGeneration,PairFiltering,
  SweepAndPrune,SortAndSweep,AxisSweep,
  TemporalCoherence,CoherentBroadPhase,
  SeparatingAxisTheorem,SAT,SeparatingAxis,
  SupportFunction,SupportMapping,
  GilbertJohnsonKeerthi,GJK,
  ExpandingPolytopeAlgorithm,EPA,
  MinkowskiDifference,MinkowskiSum,
  SimplexSearch,ClosestSimplex,
  PenetrationDepth,MinimumTranslationVector,
  ContactPoint,ContactNormal,ContactManifold,
  WitnessPoint,ClosestPoint,ClosestFeatures,
  FeaturePair,VertexFaceContact,EdgeEdgeContact,
  TriangleTriangleIntersection,SegmentTriangleIntersection,
  RayTriangleIntersection,RayBoxIntersection,
  SphereSphereIntersection,SphereBoxIntersection,
  BoxBoxIntersection,ConvexConvexIntersection,
  MeshMeshIntersection,SelfCollision,
  DiscreteCollisionDetection,DCD,
  ContinuousCollisionDetection,CCD,
  SweptVolume,SweptSphere,SweptAABB,
  TimeOfImpact,TOI,ConservativeAdvancement,
  RootFindingForTOI,MotionInterpolation,
  LinearMotion,AngularMotion,RigidMotion,
  Tunnelling,TemporalAliasing,
  ContactPersistence,WarmStartContact,
  PersistentManifold,
  CollisionMargin,SkinWidth,ContactTolerance,
  EpsilonContact,NearContact,
  CollisionFiltering,LayerMask,GroupMask,
  ExclusionPair,AdjacencyFiltering,
  OneSidedSurface,BackfaceCulling,
  ConvexDecomposition,ConcaveDecomposition,
  MeshHierarchy,TriangleSoup,
  DynamicBVH,Refit,Rebuild,TreeRotation,
  BroadPhasePairCache,
  DeformableCollisionDetection,
  ClothCollision,SoftBodyCollision,
  SelfIntersection,SelfContact,
  SignedDistanceFunction,SDF,
  DistanceField,LevelSetCollision,
  VoxelCollision,OccupancyGridCollision,
  PointCloudCollision,
  RoboticsCollisionChecking,MotionPlanningCollision,
  ConfigurationSpaceObstacle,CObstacle,
  PathValidity,TrajectoryCollision,
  GamePhysicsCollision,
  PhysicalSimulation,ContactConstraint,
  PenaltyContact,ImpulseContact,
  ConstraintBasedContact,
  ParallelCollisionDetection,GPUBroadPhase,
  GPUNarrowPhase,DistributedCollisionDetection,
  SIMDIntersection,VectorisedCollisionDetection,
  ComputationalComplexity,PairComplexity,
  QueryComplexity,UpdateComplexity,MemoryComplexity,
  Degeneracy,CoplanarIntersection,CollinearIntersection,
  TangentialContact,GrazingContact,
  NearParallelEdges,NearDegeneracy,
  RobustPredicate,ExactPredicate,AdaptivePrecision,
  FloatingPointFilter,SymbolicPerturbation,
  NumericalRobustness,FloatingPointArithmetic,
  MachinePrecision,RoundOffError,Tolerance,
  Verification,InvariantChecking,Benchmarking,
  ReferenceResult,Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  PureDistanceQueryWithoutContactOrIntersectionSemantics,
  RenderingOcclusionWithoutPhysicalOrGeometricCollisionSemantics,
  GeneralSpatialPartitioningWithoutCollisionQueryPurpose,
  ConstraintSolvingAfterContactWhenDetectionIsNotPrimary
 ]
 DISAMBIGUATION_RULE = "When the task determines whether geometric objects intersect, overlap, contact or will collide over time, interpret the context as collision detection."
}

CORE_CONCEPTS {
 CollisionDetection = "Algorithmic determination of overlap, intersection, contact or impending collision."
 BroadPhaseCollision = "Coarse stage that removes obviously noncolliding object pairs."
 NarrowPhaseCollision = "Precise geometric stage applied to candidate pairs."
 SeparatingAxisTheorem = "Convex-object nonintersection criterion based on existence of a separating projection axis."
 GJK = "Support-mapping algorithm for convex distance and intersection queries."
 ContinuousCollisionDetection = "Collision detection over motion intervals rather than only at sampled times."
 TimeOfImpact = "Earliest time at which moving objects first contact."
 ContactManifold = "Set of contact points and normals describing an overlap or touching configuration."
}

RELATIONS {
 CollisionDetection --is_child_of--> ComputationalGeometry
 CollisionDetection --uses--> SpatialPartitioning
 BroadPhaseCollision --produces--> CandidatePair
 NarrowPhaseCollision --tests--> CandidatePair
 BoundingVolumeHierarchy --accelerates--> BroadPhaseCollision
 SweepAndPrune --is_type_of--> BroadPhaseCollision
 SeparatingAxisTheorem --tests--> ConvexIntersection
 GJK --uses--> SupportMapping
 GJK --operates_on--> MinkowskiDifference
 EPA --extends--> GJKForPenetration
 ContinuousCollisionDetection --computes--> TimeOfImpact
 SweptVolume --supports--> ContinuousCollisionDetection
 ContactManifold --contains--> ContactPoint
 ContactPoint --has--> ContactNormal
 DynamicBVH --supports--> MovingObjectCollision
 CollisionFiltering --reduces--> CandidatePairs
 Verification --checks--> CollisionDetectionResult
}

OPERATORS {
 INTERSECT(A,B) := boolean_geometric_overlap_test
 AABB_OVERLAP(A,B) := interval_overlap_on_all_axes
 SAT_TEST(A,B,axes) := no_separating_axis_found
 SUPPORT(shape,d) := argmax_x_in_shape dot(x,d)
 MINKOWSKI_DIFFERENCE(A,B) := {a-b | a in A, b in B}
 GJK_INTERSECTION(A,B) := origin_contained_in_Minkowski_difference_simplex_process
 PENETRATION_DEPTH(A,B) := minimum_translation_distance_to_separate
 TIME_OF_IMPACT(A(t),B(t)) := inf{t>=0 | intersect(A(t),B(t))}
 CONTACT_MANIFOLD(A,B) := contact_points_normals_depths_and_features
}

AXIOMS {
 A1 = "Broad-phase collision detection should conservatively preserve all potentially colliding pairs."
 A2 = "Narrow-phase detection determines precise geometric collision state for candidate pairs."
 A3 = "A valid separating axis proves nonintersection of convex objects."
 A4 = "Continuous collision detection is required when discrete sampling can miss fast collisions."
 A5 = "Contact tolerance and collision margins alter practical contact classification."
 A6 = "Degenerate and near-degenerate configurations require numerically robust predicates."
 A7 = "Collision detection and contact response are distinct computational stages."
 A8 = "Collision-detection results require geometric, temporal, robustness and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(object_types,convexity,motion,dynamicity,precision_requirements,contact_outputs,performance_budget)
 R2_BROAD_PHASE = choose(BVH,sweep_and_prune,grid,hash,tree_or_hybrid_candidate_generation)
 R3_FILTER = apply(layer_group_adjacency_and_exclusion_filters)
 R4_NARROW_PHASE = choose(SAT,GJK,EPA,primitive_test,triangle_test,SDF_or_mesh_hierarchy_method)
 R5_CONTINUOUS = if_motion_fast_or_tunnelling_risk choose(CCD,swept_volume,conservative_advancement_or_TOI_root_finding)
 R6_CONTACT = compute(witness_points,normals,penetration_depth_or_manifold)
 R7_DYNAMIC_UPDATE = refit_or_rebuild_acceleration_structures
 R8_ROBUSTNESS = apply(tolerances,exact_or_adaptive_predicates,and_degeneracy_policy)
 R9_COMPLEXITY = assess(candidate_pairs,narrow_phase_cost,update_cost,memory_and_parallelism)
 R10_VALIDATE = compare_reference_cases,edge_cases,temporal_cases_and_reproducibility
}

CONSTRAINTS {
 C1 = "Broad-phase false negatives are unacceptable because they can miss real collisions."
 C2 = "Excessive broad-phase false positives increase narrow-phase cost."
 C3 = "Discrete detection can miss collisions between time samples."
 C4 = "SAT requires complete candidate axis sets for the relevant convex shapes."
 C5 = "GJK can become numerically sensitive near touching or degenerate configurations."
 C6 = "EPA requires a valid enclosing polytope and can fail on poor simplex states without safeguards."
 C7 = "Triangle meshes with nonmanifold or self-intersecting geometry complicate collision semantics."
 C8 = "Tolerances that are too large can create false contacts; too small can cause unstable contact classification."
 C9 = "Dynamic hierarchies can degrade and require refit, rotation or rebuild."
 C10 = "Collision response quality cannot be inferred solely from detection correctness."
}

SEMANTIC_EQUIVALENCE {
 "CollisionDetection" <=> "IntersectionDetectionInContactContext"
 "BroadPhaseCollision" <=> "BroadPhase"
 "NarrowPhaseCollision" <=> "NarrowPhase"
 "SeparatingAxisTheorem" <=> "SAT"
 "GilbertJohnsonKeerthi" <=> "GJK"
 "ExpandingPolytopeAlgorithm" <=> "EPA"
 "ContinuousCollisionDetection" <=> "CCD"
 "TimeOfImpact" <=> "TOI"
}

VALIDATION {
 V1 = "Object geometry and representation are explicit."
 V2 = "Broad-phase acceleration structure and update policy are documented."
 V3 = "Narrow-phase algorithm is documented for each shape pair."
 V4 = "Collision margins and tolerances are documented."
 V5 = "Discrete versus continuous collision semantics are explicit."
 V6 = "Degenerate and tangential-contact cases are tested."
 V7 = "Fast-motion tunnelling cases are tested where relevant."
 V8 = "Contact normals and penetration or witness data are validated."
 V9 = "Candidate-pair completeness is checked against reference or brute-force cases."
 V10 = "Results are reproducible under documented arithmetic, ordering and parallel settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 COLLISION_DETECTION_DEFINITION = 0.99
 BROAD_PHASE_REASONING = 0.99
 SAT_REASONING = 0.99
 GJK_REASONING = 0.99
 EPA_REASONING = 0.98
 CCD_REASONING = 0.99
 ROBUSTNESS_REASONING = 0.99
 POLICY = "Reduce confidence when shape representation, motion model, candidate-pair generation, tolerance policy, degeneracy handling or continuous-collision assumptions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,CollisionDetectionReasoning,
  BroadPhaseReasoning,NarrowPhaseReasoning,
  BVHReasoning,SweepAndPruneReasoning,
  SATReasoning,GJKReasoning,EPAReasoning,
  MinkowskiReasoning,ContactManifoldReasoning,
  ContinuousCollisionReasoning,TimeOfImpactReasoning,
  MeshCollisionReasoning,SelfCollisionReasoning,
  RoboticsCollisionReasoning,DynamicBVHReasoning,
  RobustPredicateReasoning,DegeneracyReasoning,
  ComplexityReasoning,VerificationReasoning,
  KnowledgeGraphConstruction,RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "collision detection" -> CollisionDetection
  "broad phase" -> BroadPhaseCollision
  "narrow phase" -> NarrowPhaseCollision
  "SAT" -> SeparatingAxisTheorem
  "GJK" -> GilbertJohnsonKeerthi
  "EPA" -> ExpandingPolytopeAlgorithm
  "CCD" -> ContinuousCollisionDetection
  "TOI" -> TimeOfImpact
 }
}

EXECUTION_RULES {
 E1 = "If a task determines intersection, contact or future collision between geometric objects, activate CollisionDetectionOntology2."
 E2 = "Use a conservative broad phase to generate candidate pairs."
 E3 = "Apply collision filters before expensive narrow-phase tests where safe."
 E4 = "Choose narrow-phase algorithms according to primitive type, convexity and required outputs."
 E5 = "Use continuous collision detection when fast motion can cause tunnelling."
 E6 = "Separate contact detection semantics from downstream physical response."
 E7 = "Use robust predicates and explicit tolerances near tangency, coplanarity and degeneracy."
 E8 = "Update dynamic acceleration structures according to scene motion."
 E9 = "Validate candidate completeness, edge cases, TOI behaviour, contact data and reproducibility."
}

RECURSION {
 ENTRY = CollisionDetection
 EXPAND(CollisionDetection) -> [
  IntersectionDetection,ContactDetection,ProximityDetection,
  GeometricObject,RigidBody,DeformableBody,ConvexObject,
  ConcaveObject,Polygon,Polyhedron,Triangle,TriangleMesh,
  Segment,Ray,Sphere,Capsule,Cylinder,Box,AABB,OBB,
  BoundingVolume,BoundingSphere,BoundingVolumeHierarchy,
  BVH,AABBTree,OBBTree,SpatialPartitioning,UniformGrid,
  SpatialHashing,Quadtree,Octree,KDTree,BSPTree,
  BroadPhaseCollision,NarrowPhaseCollision,CandidatePair,
  PairGeneration,SweepAndPrune,TemporalCoherence,
  SeparatingAxisTheorem,SAT,SeparatingAxis,SupportFunction,
  SupportMapping,GilbertJohnsonKeerthi,GJK,
  ExpandingPolytopeAlgorithm,EPA,MinkowskiDifference,
  SimplexSearch,PenetrationDepth,MinimumTranslationVector,
  ContactPoint,ContactNormal,ContactManifold,WitnessPoint,
  ClosestPoint,VertexFaceContact,EdgeEdgeContact,
  TriangleTriangleIntersection,SegmentTriangleIntersection,
  RayTriangleIntersection,SphereSphereIntersection,
  SphereBoxIntersection,BoxBoxIntersection,
  ConvexConvexIntersection,MeshMeshIntersection,SelfCollision,
  DiscreteCollisionDetection,ContinuousCollisionDetection,
  CCD,SweptVolume,TimeOfImpact,TOI,ConservativeAdvancement,
  MotionInterpolation,Tunnelling,ContactPersistence,
  CollisionMargin,ContactTolerance,CollisionFiltering,
  ConvexDecomposition,DynamicBVH,Refit,Rebuild,
  DeformableCollisionDetection,ClothCollision,
  SignedDistanceFunction,DistanceField,VoxelCollision,
  RoboticsCollisionChecking,ConfigurationSpaceObstacle,
  PathValidity,ParallelCollisionDetection,GPUBroadPhase,
  ComputationalComplexity,Degeneracy,CoplanarIntersection,
  TangentialContact,ExactPredicate,AdaptivePrecision,
  NumericalRobustness,FloatingPointArithmetic,
  Verification,Benchmarking,ReferenceResult,Reproducibility
 ]
 EXPAND(CollisionDetectionFamilies) -> [
  BroadPhaseCollisionDetection,
  PrimitiveNarrowPhaseTests,
  ConvexCollisionDetection,
  MeshCollisionDetection,
  ContinuousCollisionDetection,
  SelfCollisionDetection,
  RoboticsCollisionChecking,
  ParallelAndGPUCollisionDetection
 ]
 STOP_CONDITION = "Stop when object representation, broad phase, narrow phase, motion semantics, contact outputs, robustness, complexity and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry Ontology 2"
 RELATED_ONTOLOGIES = [
  "Computational Geometry Ontology 2",
  "Computational Geometry",
  "Spatial Partitioning Ontology 2",
  "Convex Hull Ontology 2",
  "Mesh Generation Ontology 2",
  "Mesh Refinement Ontology",
  "Voronoi Diagram Ontology 2",
  "Optimisation Computation",
  "Numerical Stability Ontology 2",
  "Floating Point Arithmetic Ontology",
  "Scientific Computing Ontology 2",
  "Graph Ontologies"
 ]
 ROUTE_RULES = [
  "Collision Detection -> Computational Geometry Ontology 2 for parent semantics",
  "Collision Detection -> Spatial Partitioning for broad-phase acceleration",
  "Collision Detection -> Convex Hull for convex object and support-mapping relationships",
  "Collision Detection -> Mesh Generation for triangle-mesh representations",
  "Collision Detection -> Mesh Refinement for adaptive collision geometry",
  "Collision Detection -> Voronoi Diagram for proximity and medial relationships",
  "Collision Detection -> Optimisation Computation for distance and TOI subproblems",
  "Collision Detection -> Numerical Stability for tolerance and degeneracy semantics",
  "Collision Detection -> Floating Point Arithmetic for robust near-contact computation",
  "Collision Detection -> Scientific Computing for parallel and GPU implementations",
  "Collision Detection -> Graph Ontologies for contact and adjacency graphs"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible collision algorithms, primitive families or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve broad-phase-versus-narrow-phase distinction.",
  "Preserve detection-versus-response distinction.",
  "Preserve discrete-versus-continuous collision distinction.",
  "Preserve intersection-versus-proximity distinction.",
  "Preserve convex-versus-concave collision distinction.",
  "Preserve contact-point-versus-contact-manifold distinction.",
  "Preserve exact-versus-tolerance-based contact distinction.",
  "Preserve machine-readable collision-detection semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Collision detection determines whether geometric objects intersect, contact or will collide over time."
 BROAD_PHASE_SUMMARY = "Broad-phase methods conservatively reduce the set of object pairs requiring precise geometric testing."
 NARROW_PHASE_SUMMARY = "SAT, GJK, EPA and primitive or mesh-specific tests determine exact overlap and contact information."
 CONTINUOUS_SUMMARY = "Continuous collision detection computes swept intersections and time of impact to prevent tunnelling."
 CONTACT_SUMMARY = "Contact manifolds encode points, normals, penetration and witness information for downstream simulation."
 ROBUSTNESS_SUMMARY = "Tangency, coplanarity and near-degeneracy require explicit tolerance and predicate policies."
 VALIDATION_SUMMARY = "Collision systems should be checked for candidate completeness, primitive correctness, TOI behaviour, contact data, robustness, performance and reproducibility."
}

FLOW {
 INPUT
 -> detect_collision_detection_context
 -> identify_object_types_convexity_motion_dynamicity_precision_requirements_contact_outputs_and_performance_budget
 -> choose_BVH_sweep_and_prune_grid_hash_tree_or_hybrid_broad_phase
 -> generate_candidate_pairs
 -> apply_collision_filters
 -> choose_SAT_GJK_EPA_primitive_triangle_SDF_or_mesh_hierarchy_narrow_phase
 -> if_fast_motion_or_tunnelling_risk_enable_continuous_collision_detection
 -> compute_intersection_distance_penetration_witness_points_normals_manifold_or_time_of_impact
 -> update_dynamic_acceleration_structures
 -> apply_tolerance_exact_or_adaptive_predicate_policy
 -> assess_candidate_count_query_cost_update_cost_memory_and_parallelism
 -> validate_broad_phase_completeness_narrow_phase_correctness_temporal_cases_contact_data_and_reproducibility
 -> route_to_related_computational_geometry_spatial_partitioning_convex_hull_mesh_generation_refinement_Voronoi_optimisation_stability_floating_point_scientific_computing_and_graph_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Collision Detection Ontology 2 defines geometric overlap, contact and future-collision computation. It supports broad-phase candidate generation using BVHs, sweep-and-prune, grids, hashing and spatial trees, narrow-phase SAT, GJK and EPA methods, primitive, convex and triangle-mesh intersection, Minkowski-difference reasoning, witness points, penetration depth and contact manifolds, discrete and continuous collision detection, swept volumes, conservative advancement and time-of-impact queries, dynamic BVHs, collision filtering, deformable and self-collision, signed-distance and voxel methods, robotics path collision checking, parallel and GPU execution, degeneracy handling, numerical robustness, complexity analysis, verification, benchmarking and reproducibility."
}

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

}

END_FLOW