Methods

{
  "name": "RayTraceNarrowPhase",
  "namespace": "sofa::component::collision::detection::algorithm",
  "module": "Sofa.Component.Collision.Detection.Algorithm",
  "include": "sofa/component/collision/detection/algorithm/RayTraceNarrowPhase.h",
  "doc": "Narrow phase of the collision detection using TriangleOctreeModel\n\nIt is a Ray Trace based collision detection algorithm\n  For each point in one object, we trace a ray following the opposite of the point's normal\n  up to find a triangle in the other object. Both triangles are tested to evaluate if they are in\n  colliding state. It must be used with a TriangleOctreeModel,as an octree is used to traverse the object.",
  "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": "findPairsVolume",
      "return_type": "void",
      "params": [
        {
          "name": "cm1",
          "type": "collision::geometry::CubeCollisionModel *"
        },
        {
          "name": "cm2",
          "type": "collision::geometry::CubeCollisionModel *"
        }
      ],
      "is_virtual": false,
      "is_pure_virtual": false,
      "is_static": false,
      "access": "public"
    }
  ],
  "description": "The `RayTraceNarrowPhase` is a collision detection algorithm in the SOFA framework, specifically designed for narrow phase collision detection using TriangleOctreeModel objects. It implements ray-tracing to determine collisions between triangles from two different objects. For each point on one object, it traces a ray opposite to the normal of that point until it finds an intersecting triangle on the other object. Both triangles are then evaluated to confirm if they are in collision state. This component inherits from `NarrowPhaseDetection` and must be used with TriangleOctreeModel as it relies on octrees for efficient traversal of the object geometry.\n\nIt interacts with other SOFA components through its API, particularly by overriding methods such as `addCollisionPair`, which takes a pair of collision models to add for collision detection. It also includes a method `findPairsVolume` that handles the actual ray-tracing and collision evaluation between two CubeCollisionModel objects. This component is designed to work within the SOFA ecosystem for detailed interactive medical simulations where precise collision handling is crucial.",
  "maths": "The `RayTraceNarrowPhase` is a collision detection algorithm designed for narrow phase collision detection in the SOFA framework. It specifically operates on TriangleOctreeModel objects and employs ray-tracing techniques to determine collisions between triangles from two different objects.\n\n### Governing Equations and Operators\n\n- **Collision Detection:** The `RayTraceNarrowPhase` does not directly contribute to any of the classical FEM operators such as mass matrix $M$, stiffness matrix $K$, internal force $f_{int}$, or residual $R$. Instead, it is a geometric algorithm that determines if two objects are in collision by detecting intersections between their constituent triangles.\n\n### Constitutive and Kinematic Laws Involved\n\n- **Ray Tracing:** The component uses ray-tracing to determine if a ray originating from one triangle intersects with another triangle. This involves calculating the intersection of a ray defined by an origin point $P$ and a direction vector $\boldsymbol{d}$ with the surface of a triangle.\n  - Ray equation: \\( \boldsymbol{r}(t) = P + t\boldsymbol{d} \\), where $t > 0$ is a parameter.\n\n- **Triangle Intersection:** For each point on one object, a ray is traced opposite to the normal of that point. The intersection with a triangle from the other object is determined using standard geometric methods such as barycentric coordinates and plane equations for triangles.\n\n### Role in the Global FEM Pipeline\n\nThe `RayTraceNarrowPhase` operates outside the traditional FEM pipeline stages (such as assembly, time integration, nonlinear solve, linear solve) but plays a critical role in ensuring accurate collision handling. It fits into the broader simulation architecture by:\n- **Assembly Phase:** While not directly involved in assembling mass or stiffness matrices, it contributes to collision detection which is crucial for enforcing constraints and interactions between objects.\n\n### Numerical Methods and Discretization Choices\n\n- **Octree Traversal:** The algorithm uses octrees (a tree data structure where each internal node has up to eight children) to efficiently traverse the object geometry. This speeds up the process of finding intersecting triangles by reducing the number of triangles that need to be checked.\n  - Octree construction: For both objects, an octree is built if it does not already exist.\n\n- **Ray Tracing:** The ray-tracing method involves checking for intersections between rays and triangles. This uses methods such as Moller-Trumbore algorithm or similar for efficient intersection testing.\n\n### Integration into the Variational / Lagrangian Mechanics Framework\n\nThe `RayTraceNarrowPhase` is not directly tied to variational mechanics or Lagrangian formulation, but it provides necessary geometric information that can be used in enforcing constraints and handling contact forces. It fits within the broader framework by ensuring accurate collision detection, which is essential for physically consistent simulations.\n\n### Summary\nThe `RayTraceNarrowPhase` component implements a ray-tracing algorithm to detect collisions between triangles from two objects using octree traversal for efficient geometric queries. This ensures precise and fast collision handling in interactive medical simulations within the SOFA framework.",
  "abstract": "The `RayTraceNarrowPhase` component performs narrow phase collision detection using ray-tracing to determine intersections between triangles from two objects, relying on TriangleOctreeModel for efficient geometry traversal.",
  "sheet": "# RayTraceNarrowPhase\n\n**Overview:**\n\nThe `RayTraceNarrowPhase` is a collision detection algorithm that implements the narrow phase of collision detection in SOFA. It uses ray-tracing to determine collisions between triangles from two different objects, specifically requiring TriangleOctreeModel for efficient traversal and intersection testing.\n\n**Mathematical Model:*\n\n*Collision Detection:* The `RayTraceNarrowPhase` employs ray-tracing to detect intersections between a ray originating from one triangle and another triangle. For each point on an object, a ray is traced opposite to the normal of that point until it intersects with a triangle in the other object.\n\n- *Ray Equation:* \\(\\mathbf{r}(t) = P + t\\mathbf{d}\\), where \\(P\\) is the origin point and \\(\\mathbf{d}\\) is the direction vector, with \\(t > 0\\).\n\n*Triangle Intersection:* The intersection between a ray and a triangle is determined using standard geometric methods such as barycentric coordinates. For a given ray defined by \\(P + t\\mathbf{d}\\), the intersection point on the triangle is found if it lies within the bounds of the triangle.\n\n**Dependencies and Connections:**\n\nThe `RayTraceNarrowPhase` must be used with TriangleOctreeModel for efficient traversal of object geometry. It fits into the broader SOFA simulation architecture by providing precise collision detection between objects, which is crucial for enforcing constraints and handling interactions in interactive medical simulations."
}