Back

BVHNarrowPhase

The BVH (Bounding Volume Hierarchy) Narrow Phase is a collision detection algorithm designed for efficient narrow phase collision testing in physics simulations and computer graphics applications. This component focuses on performing the detailed, precise collision tests between pairs of objects that have already been identified as potential colliders by a broad phase algorithm.

abstract
BVHNarrowPhase performs narrow phase collision detection using bounding volume hierarchy (BVH) to efficiently eliminate non-intersecting pairs of elements identified by a broad phase algorithm.
sheet
# BVHNarrowPhase ## Overview BVHNarrowPhase is a component in the SOFA framework for performing narrow phase collision detection. It uses a bounding volume hierarchy (BVH) to rapidly eliminate pairs of elements that are not intersecting, based on the results from a broad phase collision detection algorithm. ## Dependencies and Connections This component typically requires a broad phase collision detection algorithm to provide initial candidate pairs of colliding objects. BVHNarrowPhase processes these pairs using its BVH structure to perform detailed intersection tests. It interacts with `core::CollisionModel` instances and uses methods from the `NarrowPhaseDetection` parent class.
name
BVH Narrow Phase
description
The BVH (Bounding Volume Hierarchy) Narrow Phase is a collision detection algorithm designed for efficient narrow phase collision testing in physics simulations and computer graphics applications. This component focuses on performing the detailed, precise collision tests between pairs of objects that have already been identified as potential colliders by a broad phase algorithm.
parameters
details
  • {'title': 'Functionality', 'content': 'The BVH Narrow Phase utilizes a bounding volume hierarchy to recursively subdivide space into smaller regions, allowing for efficient exclusion of non-colliding object pairs. Once the broad phase identifies potential colliders, this component performs detailed intersection tests between these objects. The algorithm iteratively examines internal and external children of collision elements until it reaches the finest level where actual geometry is tested for intersections.'}
  • {'title': 'Bounding Volume Hierarchy', 'content': 'The BVH structure organizes objects in a tree-like manner with bounding volumes (like AABBs or OBBs) at each node. This hierarchical organization enables quick rejection of large groups of non-colliding objects, reducing the number of detailed intersection tests needed.'}
  • {'title': 'Collision Element Iteration', 'content': 'The algorithm iterates over collision elements at different levels of the hierarchy, checking for potential intersections using coarse intersector methods. When internal children are found, recursive testing continues within these sub-regions; when only external children exist, they are directly compared with the opposing element.'}
  • {'title': 'Final Collision Pair Testing', 'content': 'At the finest level of the hierarchy, actual intersection tests are performed between geometry elements using an intersector method specific to the collision model types involved. These detailed intersections generate precise contact information for further processing by a physics engine or simulation.'}
  • {'title': 'Self Collision Handling', 'content': 'Special handling is provided for self-collision scenarios, where objects need to be tested against themselves. In such cases, each element only needs to test against subsequent elements in the same hierarchy to avoid redundant and self-intersection tests.'}
@context
http://schema.org
@type
SoftwareDocumentation
name
BVH (Bounding Volume Hierarchy) Narrow Phase Collision Detection Algorithm
description
The BVH Narrow Phase is a collision detection algorithm designed for efficient narrow phase collision testing in physics simulations and computer graphics applications. This component performs detailed, precise collision tests between pairs of objects that have already been identified as potential colliders by a broad phase algorithm.
hasPart
  • {'@type': 'SoftwareComponent', 'name': 'Bounding Volume Hierarchy (BVH)', 'description': 'A data structure used to represent the spatial hierarchy of bounding volumes for each object. Each node in the BVH represents either an internal node containing sub-volumes or a leaf node representing actual geometric primitives.', 'physicalConcepts': [{'@type': 'PhysicalQuantity', 'name': 'Bounding Volume', 'description': 'A simple, usually axis-aligned, bounding shape (e.g., box) that encapsulates the geometry of an object. Bounding volumes are used to quickly determine whether two objects might be colliding.'}, {'@type': 'Algorithm', 'name': 'Hierarchical Spatial Partitioning', 'description': 'The process of recursively subdividing space into smaller regions using bounding volumes, creating a tree-like structure that allows for efficient spatial queries and collision testing.'}]}
  • {'@type': 'SoftwareComponent', 'name': 'Narrow Phase Collision Detection', 'description': "Performs detailed intersection tests between pairs of objects identified by the broad phase algorithm. The narrow phase refines the broad phase's coarse-grained potential collisions into precise, geometrically accurate intersections.", 'physicalConcepts': [{'@type': 'Algorithm', 'name': 'Intersection Tests', 'description': "Detailed mathematical algorithms to determine if and how two geometric shapes (e.g., triangles, spheres) intersect. These tests are performed on the smallest elements of each object's BVH."}, {'@type': 'PhysicalQuantity', 'name': 'Collision Pair', 'description': 'A pair of objects that have been identified as potentially colliding by the broad phase and confirmed to be in collision during the narrow phase.'}]}
  • {'@type': 'SoftwareComponent', 'name': 'Bounding Volume Intersections', 'description': 'Tests whether bounding volumes intersect, providing a quick filter for determining if more detailed intersection tests are necessary.', 'physicalConcepts': [{'@type': 'Algorithm', 'name': 'Axis-Aligned Bounding Box (AABB) Intersection Test', 'description': 'An algorithm to check if two axis-aligned bounding boxes overlap. This is one of the simplest and fastest intersection tests.'}, {'@type': 'PhysicalQuantity', 'name': 'Bounding Volume Overlap', 'description': 'When two bounding volumes intersect, indicating that their enclosed objects might also be colliding.'}]}
  • {'@type': 'SoftwareComponent', 'name': 'Recursive Collision Testing', 'description': 'A method for traversing the BVH tree structure to test for collisions between pairs of objects. It recursively descends through internal nodes until reaching leaf nodes representing actual geometric primitives.', 'physicalConcepts': [{'@type': 'Algorithm', 'name': 'Tree Traversal', 'description': 'The process of recursively visiting each node in a tree data structure, starting from the root and moving down to the leaves.'}, {'@type': 'PhysicalQuantity', 'name': 'Collision Depth', 'description': 'Refers to the level of detail at which collision testing is performed. In BVH narrow phase, this involves descending through multiple levels of bounding volumes until reaching primitive shapes.'}]}
mathematicalModels
  • {'@type': 'MathematicalModel', 'name': 'Bounding Volume Intersection Test', 'description': 'A mathematical model for determining if two bounding volumes intersect. This typically involves checking if the minimum and maximum coordinates of the volumes overlap along each axis.', 'formula': 'For two Axis-Aligned Bounding Boxes (AABBs) A and B: \n- Let A_min, A_max be the min and max corners of AABB A.\n- Let B_min, B_max be the min and max corners of AABB B. \n\nThe boxes overlap if for all axes i: \nA_min[i] <= B_max[i] && B_min[i] <= A_max[i]'}
  • {'@type': 'MathematicalModel', 'name': 'Primitive Intersection Test', 'description': 'A mathematical model for determining if two primitive shapes (e.g., triangles, spheres) intersect. This involves solving systems of equations or inequalities to check overlap.', 'formula': "For example, testing intersection between a sphere and a triangle: \n- Define the sphere's center C and radius R.\n- Define the vertices V1, V2, V3 of the triangle.\n\nIntersection occurs if any point on the triangle is within distance R from C or vice versa."}
{
  "name": "BVHNarrowPhase",
  "main": {
    "name": "BVHNarrowPhase",
    "namespace": "sofa::component::collision::detection::algorithm",
    "module": "Sofa.Component.Collision.Detection.Algorithm",
    "include": "sofa/component/collision/detection/algorithm/BVHNarrowPhase.h",
    "doc": "Narrow phase collision detection based on boundary volume hierarchy.\n\nNarrow phase collision detection based on bounding volume hierarchy\nThe algorithm uses the result of a broad phase collision detection. For a pair of\ncollision models, it traverses the hierarchy of bounding volumes in order to rapidly\neliminate pairs of elements which are not in intersection. Finally, the intersection\nmethod is called on the remaining pairs of elements.",
    "inherits": [
      "NarrowPhaseDetection"
    ],
    "templates": [],
    "data_fields": [],
    "links": [],
    "methods": [
      {
        "name": "addCollisionPair",
        "return_type": "void",
        "params": [
          {
            "name": "cmPair",
            "type": "const std::pair<core::CollisionModel *, core::CollisionModel *> &"
          }
        ],
        "is_virtual": true,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "isSelfCollision",
        "return_type": "bool",
        "params": [
          {
            "name": "cm1",
            "type": "core::CollisionModel *"
          },
          {
            "name": "cm2",
            "type": "core::CollisionModel *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": true,
        "access": "protected"
      },
      {
        "name": "initializeExternalCells",
        "return_type": "void",
        "params": [
          {
            "name": "cm1",
            "type": "core::CollisionModel *"
          },
          {
            "name": "cm2",
            "type": "core::CollisionModel *"
          },
          {
            "name": "externalCells",
            "type": "int &"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": true,
        "access": "protected"
      },
      {
        "name": "processExternalCell",
        "return_type": "void",
        "params": [
          {
            "name": "externalCell",
            "type": "const TestPair &"
          },
          {
            "name": "cm1",
            "type": "core::CollisionModel *&"
          },
          {
            "name": "cm2",
            "type": "core::CollisionModel *&"
          },
          {
            "name": "coarseIntersector",
            "type": "core::collision::ElementIntersector *"
          },
          {
            "name": "finest",
            "type": "const FinestCollision &"
          },
          {
            "name": "mirror",
            "type": "MirrorIntersector *"
          },
          {
            "name": "externalCells",
            "type": "int &"
          },
          {
            "name": "outputs",
            "type": "sofa::core::collision::DetectionOutputVector *&"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "protected"
      },
      {
        "name": "processInternalCell",
        "return_type": "void",
        "params": [
          {
            "name": "internalCell",
            "type": "const TestPair &"
          },
          {
            "name": "coarseIntersector",
            "type": "core::collision::ElementIntersector *"
          },
          {
            "name": "finest",
            "type": "const FinestCollision &"
          },
          {
            "name": "externalCells",
            "type": "int &"
          },
          {
            "name": "internalCells",
            "type": "int &"
          },
          {
            "name": "outputs",
            "type": "sofa::core::collision::DetectionOutputVector *&"
          },
          {
            "name": "currentIntersection",
            "type": "const sofa::core::collision::Intersection *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": true,
        "access": "protected"
      },
      {
        "name": "visitCollisionElements",
        "return_type": "void",
        "params": [
          {
            "name": "root",
            "type": "const TestPair &"
          },
          {
            "name": "coarseIntersector",
            "type": "core::collision::ElementIntersector *"
          },
          {
            "name": "finest",
            "type": "const FinestCollision &"
          },
          {
            "name": "externalCells",
            "type": "int &"
          },
          {
            "name": "internalCells",
            "type": "int &"
          },
          {
            "name": "outputs",
            "type": "sofa::core::collision::DetectionOutputVector *&"
          },
          {
            "name": "currentIntersection",
            "type": "const sofa::core::collision::Intersection *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": true,
        "access": "protected"
      },
      {
        "name": "visitExternalChildren",
        "return_type": "void",
        "params": [
          {
            "name": "it1",
            "type": "const core::CollisionElementIterator &"
          },
          {
            "name": "it2",
            "type": "const core::CollisionElementIterator &"
          },
          {
            "name": "coarseIntersector",
            "type": "core::collision::ElementIntersector *"
          },
          {
            "name": "finest",
            "type": "const FinestCollision &"
          },
          {
            "name": "externalCells",
            "type": "int &"
          },
          {
            "name": "outputs",
            "type": "sofa::core::collision::DetectionOutputVector *&"
          },
          {
            "name": "currentIntersection",
            "type": "const sofa::core::collision::Intersection *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": true,
        "access": "protected"
      },
      {
        "name": "finalCollisionPairs",
        "return_type": "void",
        "params": [
          {
            "name": "pair",
            "type": "const TestPair &"
          },
          {
            "name": "selfCollision",
            "type": "bool"
          },
          {
            "name": "intersector",
            "type": "core::collision::ElementIntersector *"
          },
          {
            "name": "outputs",
            "type": "sofa::core::collision::DetectionOutputVector *&"
          },
          {
            "name": "currentIntersection",
            "type": "const sofa::core::collision::Intersection *"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": true,
        "access": "protected"
      }
    ]
  },
  "desc": {
    "name": "BVH Narrow Phase",
    "description": "The BVH (Bounding Volume Hierarchy) Narrow Phase is a collision detection algorithm designed for efficient narrow phase collision testing in physics simulations and computer graphics applications. This component focuses on performing the detailed, precise collision tests between pairs of objects that have already been identified as potential colliders by a broad phase algorithm.",
    "parameters": [],
    "details": [
      {
        "title": "Functionality",
        "content": "The BVH Narrow Phase utilizes a bounding volume hierarchy to recursively subdivide space into smaller regions, allowing for efficient exclusion of non-colliding object pairs. Once the broad phase identifies potential colliders, this component performs detailed intersection tests between these objects. The algorithm iteratively examines internal and external children of collision elements until it reaches the finest level where actual geometry is tested for intersections."
      },
      {
        "title": "Bounding Volume Hierarchy",
        "content": "The BVH structure organizes objects in a tree-like manner with bounding volumes (like AABBs or OBBs) at each node. This hierarchical organization enables quick rejection of large groups of non-colliding objects, reducing the number of detailed intersection tests needed."
      },
      {
        "title": "Collision Element Iteration",
        "content": "The algorithm iterates over collision elements at different levels of the hierarchy, checking for potential intersections using coarse intersector methods. When internal children are found, recursive testing continues within these sub-regions; when only external children exist, they are directly compared with the opposing element."
      },
      {
        "title": "Final Collision Pair Testing",
        "content": "At the finest level of the hierarchy, actual intersection tests are performed between geometry elements using an intersector method specific to the collision model types involved. These detailed intersections generate precise contact information for further processing by a physics engine or simulation."
      },
      {
        "title": "Self Collision Handling",
        "content": "Special handling is provided for self-collision scenarios, where objects need to be tested against themselves. In such cases, each element only needs to test against subsequent elements in the same hierarchy to avoid redundant and self-intersection tests."
      }
    ]
  },
  "maths": {
    "@context": "http://schema.org",
    "@type": "SoftwareDocumentation",
    "name": "BVH (Bounding Volume Hierarchy) Narrow Phase Collision Detection Algorithm",
    "description": "The BVH Narrow Phase is a collision detection algorithm designed for efficient narrow phase collision testing in physics simulations and computer graphics applications. This component performs detailed, precise collision tests between pairs of objects that have already been identified as potential colliders by a broad phase algorithm.",
    "hasPart": [
      {
        "@type": "SoftwareComponent",
        "name": "Bounding Volume Hierarchy (BVH)",
        "description": "A data structure used to represent the spatial hierarchy of bounding volumes for each object. Each node in the BVH represents either an internal node containing sub-volumes or a leaf node representing actual geometric primitives.",
        "physicalConcepts": [
          {
            "@type": "PhysicalQuantity",
            "name": "Bounding Volume",
            "description": "A simple, usually axis-aligned, bounding shape (e.g., box) that encapsulates the geometry of an object. Bounding volumes are used to quickly determine whether two objects might be colliding."
          },
          {
            "@type": "Algorithm",
            "name": "Hierarchical Spatial Partitioning",
            "description": "The process of recursively subdividing space into smaller regions using bounding volumes, creating a tree-like structure that allows for efficient spatial queries and collision testing."
          }
        ]
      },
      {
        "@type": "SoftwareComponent",
        "name": "Narrow Phase Collision Detection",
        "description": "Performs detailed intersection tests between pairs of objects identified by the broad phase algorithm. The narrow phase refines the broad phase's coarse-grained potential collisions into precise, geometrically accurate intersections.",
        "physicalConcepts": [
          {
            "@type": "Algorithm",
            "name": "Intersection Tests",
            "description": "Detailed mathematical algorithms to determine if and how two geometric shapes (e.g., triangles, spheres) intersect. These tests are performed on the smallest elements of each object's BVH."
          },
          {
            "@type": "PhysicalQuantity",
            "name": "Collision Pair",
            "description": "A pair of objects that have been identified as potentially colliding by the broad phase and confirmed to be in collision during the narrow phase."
          }
        ]
      },
      {
        "@type": "SoftwareComponent",
        "name": "Bounding Volume Intersections",
        "description": "Tests whether bounding volumes intersect, providing a quick filter for determining if more detailed intersection tests are necessary.",
        "physicalConcepts": [
          {
            "@type": "Algorithm",
            "name": "Axis-Aligned Bounding Box (AABB) Intersection Test",
            "description": "An algorithm to check if two axis-aligned bounding boxes overlap. This is one of the simplest and fastest intersection tests."
          },
          {
            "@type": "PhysicalQuantity",
            "name": "Bounding Volume Overlap",
            "description": "When two bounding volumes intersect, indicating that their enclosed objects might also be colliding."
          }
        ]
      },
      {
        "@type": "SoftwareComponent",
        "name": "Recursive Collision Testing",
        "description": "A method for traversing the BVH tree structure to test for collisions between pairs of objects. It recursively descends through internal nodes until reaching leaf nodes representing actual geometric primitives.",
        "physicalConcepts": [
          {
            "@type": "Algorithm",
            "name": "Tree Traversal",
            "description": "The process of recursively visiting each node in a tree data structure, starting from the root and moving down to the leaves."
          },
          {
            "@type": "PhysicalQuantity",
            "name": "Collision Depth",
            "description": "Refers to the level of detail at which collision testing is performed. In BVH narrow phase, this involves descending through multiple levels of bounding volumes until reaching primitive shapes."
          }
        ]
      }
    ],
    "mathematicalModels": [
      {
        "@type": "MathematicalModel",
        "name": "Bounding Volume Intersection Test",
        "description": "A mathematical model for determining if two bounding volumes intersect. This typically involves checking if the minimum and maximum coordinates of the volumes overlap along each axis.",
        "formula": "For two Axis-Aligned Bounding Boxes (AABBs) A and B: \n- Let A_min, A_max be the min and max corners of AABB A.\n- Let B_min, B_max be the min and max corners of AABB B. \n\nThe boxes overlap if for all axes i: \nA_min[i] <= B_max[i] && B_min[i] <= A_max[i]"
      },
      {
        "@type": "MathematicalModel",
        "name": "Primitive Intersection Test",
        "description": "A mathematical model for determining if two primitive shapes (e.g., triangles, spheres) intersect. This involves solving systems of equations or inequalities to check overlap.",
        "formula": "For example, testing intersection between a sphere and a triangle: \n- Define the sphere's center C and radius R.\n- Define the vertices V1, V2, V3 of the triangle.\n\nIntersection occurs if any point on the triangle is within distance R from C or vice versa."
      }
    ]
  },
  "summary": {
    "abstract": "BVHNarrowPhase performs narrow phase collision detection using bounding volume hierarchy (BVH) to efficiently eliminate non-intersecting pairs of elements identified by a broad phase algorithm.",
    "sheet": "# BVHNarrowPhase\n\n## Overview\n\nBVHNarrowPhase is a component in the SOFA framework for performing narrow phase collision detection. It uses a bounding volume hierarchy (BVH) to rapidly eliminate pairs of elements that are not intersecting, based on the results from a broad phase collision detection algorithm.\n\n## Dependencies and Connections\n\nThis component typically requires a broad phase collision detection algorithm to provide initial candidate pairs of colliding objects. BVHNarrowPhase processes these pairs using its BVH structure to perform detailed intersection tests. It interacts with `core::CollisionModel` instances and uses methods from the `NarrowPhaseDetection` parent class."
  }
}