{
  "name": "IncrSAP",
  "main": {
    "name": "IncrSAP",
    "namespace": "sofa::component::collision::detection::algorithm",
    "module": "Sofa.Component.Collision.Detection.Algorithm",
    "include": "sofa/component/collision/detection/algorithm/IncrSAP.h",
    "doc": "Collision detection using incremental sweep and prune.\n\nImplementation of incremental sweep and prune. i.e. collision primitives are stored and updated\nwhich should speed up the collision detection compared to the DirectSAP.",
    "inherits": [
      "BroadPhaseDetection",
      "NarrowPhaseDetection"
    ],
    "templates": [],
    "data_fields": [],
    "links": [],
    "methods": [
      {
        "name": "init",
        "return_type": "void",
        "params": [],
        "is_virtual": true,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "reinit",
        "return_type": "void",
        "params": [],
        "is_virtual": true,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "addCollisionModel",
        "return_type": "void",
        "params": [
          {
            "name": "cm",
            "type": "core::CollisionModel *"
          }
        ],
        "is_virtual": true,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "addCollisionPair",
        "return_type": "void",
        "params": [
          {
            "name": "",
            "type": "const std::pair<core::CollisionModel *, core::CollisionModel *> &"
          }
        ],
        "is_virtual": true,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "addCollisionPairs",
        "return_type": "void",
        "params": [
          {
            "name": "",
            "type": "const int &"
          }
        ],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "beginNarrowPhase",
        "return_type": "void",
        "params": [],
        "is_virtual": true,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "needsDeepBoundingTree",
        "return_type": "bool",
        "params": [],
        "is_virtual": true,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "showEndPoints",
        "return_type": "void",
        "params": [],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      },
      {
        "name": "showBoxes",
        "return_type": "void",
        "params": [],
        "is_virtual": false,
        "is_pure_virtual": false,
        "is_static": false,
        "access": "public"
      }
    ]
  },
  "desc": {
    "name": "IncrSAP",
    "description": "Implementation of incremental sweep and prune (ISAP) collision detection algorithm in SOFA physics engine.",
    "parameters": [
      {
        "name": "box",
        "type": "vector<Vec3>",
        "description": "Bounding box to ignore objects outside this volume during collision detection. If empty, all objects are considered."
      },
      {
        "name": "alarmDist",
        "type": "float",
        "description": "Threshold distance for detecting potential collisions between objects. Used to determine if boxes are moving significantly between frames."
      }
    ],
    "details": "The IncrSAP component is a specialized collision detection algorithm designed for the SOFA physics engine. It implements an incremental version of the Sweep and Prune (ISAP) method, which is particularly efficient for dynamic scenes with many objects that move between simulation steps.\n\n**Key Features: **\n- **Incremental Updates:** Instead of recalculating all collisions from scratch each frame, IncrSAP only updates the bounding boxes (AABBs) and collision tests for objects that have moved significantly. This makes it more efficient than traditional SAP methods in dynamic environments.\n- **Bounding Box Management:** It maintains a list of ISAPBox objects representing the current state of each object's AABB and its previous position, enabling efficient tracking of movement.\n- **EndPointLists:** The algorithm uses lists of EndPointIDs to keep track of minimum and maximum positions along each axis for all boxes. These endpoints are updated incrementally as objects move.\n- **Collision Detection:** IncrSAP detects collisions by comparing the endpoints in its lists, only checking pairs that could potentially be colliding based on their positions.\n\n**Usage: **\nThis component is particularly useful when dealing with large numbers of dynamic objects where full recalculation would be computationally expensive. It can significantly reduce the number of collision tests needed per frame by focusing updates and checks on moving objects only.",
    "example": "Example configuration in SOFA scene description file (XML format):\n```xml\n<IncrSAP name='collisionDetector'>\n    <box value='{{-10, -10, -10}, {10, 10, 10}}' />\n    <alarmDist value='0.5'/>\n</IncrSAP>\n```",
    "limitations": [
      "Requires objects to be represented by axis-aligned bounding boxes (AABBs).",
      "May become less efficient in highly dynamic scenes with many small objects moving rapidly.",
      "Does not support complex shapes directly; all geometry is approximated using AABBs."
    ]
  },
  "maths": {
    "maths": "### Governing Equations and Operators\n\nThe `IncrSAP` component in the SOFA framework is not directly involved with the governing equations or operators such as mass matrix \\(M\\), stiffness matrix \\(K\\), internal force \\(\bm{f}_{int}\\), or residual \\(\bm{R}\\). Instead, it focuses on collision detection and management. It does not contribute to the direct calculation of forces or displacements.\n\n### Constitutive or Kinematic Laws Involved\n\nThe `IncrSAP` component itself does not define any specific constitutive laws (strain measures, stress tensors, hyperelastic potentials) or kinematic laws directly related to material behavior. Its primary role is to determine whether two collision models intersect and manage the corresponding contact pairs.\n\n### Role in the Global FEM Pipeline\n\n- **Assembly**: The `IncrSAP` component does not participate directly in assembly of global operators like mass matrix, stiffness matrix, or internal forces. Instead, it focuses on identifying potential contacts between different parts (collision models) in a simulation scene and updating these contacts over time.\n\n- **Time Integration**: It is not involved with the actual integration step (e.g., Backward Euler). However, its operations are synchronized with each time step to ensure accurate collision detection during the entire simulation.\n\n- **Nonlinear Solve**: `IncrSAP` does not solve any nonlinear system directly but rather provides a list of colliding pairs that can be used as constraints in the overall nonlinear solution process. These contact constraints may later contribute to the nonlinear residual and Jacobian.\n\n- **Linear Solve**: It is not directly involved in the linear solver operations, such as Krylov methods or direct factorizations, but it contributes by identifying which elements (collision models) are in contact, which can influence how these solvers handle contact constraints.\n\n### Numerical Methods and Discretization Choices\n\n- **Incremental Sweep-and-Prune (ISAP)**: This component uses an incremental sweep-and-prune algorithm to efficiently detect collisions between bounding volumes. ISAP stores the end points of each object's axis-aligned bounding box (AABB) on a 1D line for each dimension.\n\n- **Bounding Volume Hierarchy**: It maintains lists of `EndPointID` structures that store the minimum and maximum values of these bounding boxes along different axes, which helps in determining potential collisions efficiently by comparing these end points.\n\n### Fitting into Variational / Lagrangian Mechanics Framework\n\nThe `IncrSAP` component fits indirectly into the broader variational/Lagrangian mechanics framework. By providing accurate and efficient collision detection, it ensures that contact forces between deformable bodies are correctly modeled in subsequent stages of the simulation pipeline.\n\nThese contact forces can be seen as additional constraints or boundary conditions in the Lagrangian formulation, contributing to the overall dynamics of the system governed by variational principles. The component’s role is thus crucial for maintaining physical consistency and accuracy in simulations involving deformable objects with complex interactions."
  },
  "summary": {
    "abstract": "The `IncrSAP` component implements incremental sweep-and-prune (ISAP) for efficient collision detection between objects in SOFA simulations, managing both broad-phase and narrow-phase stages.",
    "sheet": "# IncrSAP\n\n## Overview\n\nThe `IncrSAP` component is a collision detection algorithm that uses the Incremental Sweep-and-Prune (ISAP) method to efficiently manage collisions between objects in SOFA simulations. It inherits from `BroadPhaseDetection` and `NarrowPhaseDetection`, indicating its role in both broad-phase and narrow-phase collision detection stages.\n\n## Dependencies and Connections\n\nThe `IncrSAP` component typically requires other components such as `CollisionModel` to define the objects that need collision detection. It fits into the scene graph by managing potential collisions between these models, updating them efficiently over time. The broad-phase detection identifies pairs of objects that might be colliding, while the narrow-phase detection confirms actual intersections.\n\n## Practical Notes\n\nThe incremental nature of ISAP helps in speeding up collision detection compared to direct methods like DirectSAP. However, it requires careful management of bounding volumes and their updates over time steps. Practitioners should ensure that the bounding volumes are appropriately defined for each object to maintain numerical stability and accuracy."
  }
}