Sweep and Prune (SAP) Narrow Phase Detection

Data Fields

Methods

{
  "name": "DirectSAPNarrowPhase",
  "namespace": "sofa::component::collision::detection::algorithm",
  "module": "Sofa.Component.Collision.Detection.Algorithm",
  "include": "sofa/component/collision/detection/algorithm/DirectSAPNarrowPhase.h",
  "doc": "Narrow phase of the collision detection using sweep and prune.\n\nThis class is an implementation of sweep and prune in its \"direct\" version, i.e. at each step\nit sorts all the primitives along an axis (not checking the moving ones) and computes overlapping pairs without\nsaving it. But the memory used to save these primitives is created just once, the first time we add CollisionModels.",
  "inherits": [
    "NarrowPhaseDetection"
  ],
  "templates": [],
  "data_fields": [
    {
      "name": "d_showOnlyInvestigatedBoxes",
      "type": "bool",
      "xmlname": "showOnlyInvestigatedBoxes",
      "help": "Show only boxes which will be sent to narrow phase"
    },
    {
      "name": "d_nbPairs",
      "type": "int",
      "xmlname": "nbPairs",
      "help": "number of pairs of elements sent to narrow phase"
    }
  ],
  "links": [],
  "methods": [
    {
      "name": "beginNarrowPhase",
      "description": "Initializes the narrow phase detection process.",
      "returns": null,
      "parameters": []
    },
    {
      "name": "addCollisionPair",
      "description": "Adds a new collision pair to be processed during the narrow phase.",
      "returns": null,
      "parameters": [
        {
          "name": "cmPair",
          "type": "std::pair<core::CollisionModel*, core::CollisionModel*>"
        }
      ]
    },
    {
      "name": "endNarrowPhase",
      "description": "Finalizes the narrow phase detection process and processes all added collision pairs.",
      "returns": null,
      "parameters": []
    },
    {
      "name": "draw",
      "description": "Renders visual aids for debugging purposes during collision detection.",
      "returns": null,
      "parameters": [
        {
          "name": "visualParams",
          "type": "core::visual::VisualParams*"
        }
      ]
    },
    {
      "name": "reset",
      "description": "Resets the component state to its initial configuration.",
      "returns": null,
      "parameters": []
    }
  ],
  "description": "This component implements the direct version of Sweep and Prune (SAP) collision detection algorithm for narrow phase processing.",
  "parameters": [
    {
      "name": "alarmDistance",
      "type": "float",
      "defaultValue": "",
      "description": "The alarm distance used to determine if two objects may collide."
    },
    {
      "name": "showOnlyInvestigatedBoxes",
      "type": "bool",
      "defaultValue": "false",
      "description": "If true, only displays boxes that are sent for narrow phase processing during collision detection."
    }
  ],
  "inputs": [
    {
      "name": "collisionModels",
      "type": "core::CollisionModel*",
      "description": "The set of collision models to process for collision detection."
    },
    {
      "name": "broadPhaseResult",
      "type": "std::unordered_set<core::CollisionModel*>",
      "description": "The result from the broad phase that determines which pairs of objects could potentially collide."
    }
  ],
  "outputs": [
    {
      "name": "collisionPairs",
      "type": "std::pair<core::CollisionModel*, core::CollisionModel*>",
      "description": "Pairs of collision models that are determined to be in potential contact after narrow phase processing."
    },
    {
      "name": "nbPairs",
      "type": "int",
      "description": "The number of pairs sent for narrow phase processing."
    }
  ],
  "notes": "The DirectSAPNarrowPhase performs efficient collision detection by sorting and pruning potential colliding objects along an axis that maximizes variance among bounding boxes. This approach minimizes the number of pairwise checks needed during narrow phase processing.",
  "maths": "# Sweep and Prune (SAP) Narrow Phase Detection\n\n### Overview\nThe Sweep and Prune (SAP) algorithm is a collision detection method used in physics engines for identifying pairs of potentially colliding objects. The direct version of SAP processes all primitives at each step without saving the results, making it suitable for real-time applications where performance is critical.\n\n### Mathematical Description\n\n#### 1. **Axis Selection**\nThe primary objective of this algorithm is to reduce the number of potential collision pairs by using an axis along which the objects are sparsest (i.e., have the largest variance). This maximizes the likelihood that non-overlapping objects can be quickly eliminated.\n\n- Let \\(A_1, A_2, \\\\.\\.\\., A_n\\) represent the set of axis-aligned bounding boxes (AABBs) in 3D space. Each AABB is defined by its minimum and maximum coordinates along each axis.\n- The variance for an axis can be calculated as:\n  \\[\\text{Var}(X_i) = E[X_i^2] - [E[X_i]]^2, \\\n   \\quad i = x, y, z\\]\n  where \\(E[X_i]\\) and \\(E[X_i^2]\\) are the expected value of coordinates along axis \\(i\\).\n- The greatest variance axis is determined by:\n  \\[k_{\text{max}} = \\\\arg \\\\max_k (\\text{Var}(X_k))\\]\n\n#### 2. **Updating End Points**\nThe algorithm updates the values of end points along the selected axis for all objects.\n- Let \\(p_i^{min}\\) and \\(p_i^{max}\\) denote the minimum and maximum coordinates of object \\(i\\) along the greatest variance axis.\n\n#### 3. **Sorting End Points**\nThe algorithm sorts these end points to identify overlapping AABBs efficiently.\n- The sorting operation is performed on a list of objects based on their \\(p_i^{min}\\) and \\(p_i^{max}\\).\n\n#### 4. **Overlap Detection**\nAfter sorting, the overlap between two adjacent objects can be determined using the following condition:\n\\[ \\\\text{overlap}(A_j, A_k) = (A_j^{max} > A_k^{min}) \\land (A_k^{max} > A_j^{min}), \\\n   \\quad j,k \\\\in [1,n] \\\n   \\quad  j \\\\neq k\n\\]\nwhere \\(j, k\\) are the indices of the two objects being compared.\n\n#### 5. **Filtering and Narrow Phase Processing**\nThe algorithm filters out non-overlapping pairs based on sorted end points and passes overlapping pairs to the narrow phase for detailed collision detection.\n- If a pair is detected as potentially colliding, it is sent to further processing steps such as intersection tests or response calculations.\n\n### Physical Description\nIn physical simulations involving rigid body dynamics or soft tissue mechanics, this algorithm is crucial for efficient collision handling. It reduces computational overhead by minimizing the number of pairs that require detailed geometric intersection checks. This makes real-time physics engines possible by ensuring that only likely colliding objects are analyzed in depth.\n\nThe direct SAP algorithm does not maintain a persistent state across frames; instead, it recalculates and sorts end points at each step, making it suitable for dynamic environments where object positions change frequently.",
  "abstract": "The DirectSAPNarrowPhase component implements a direct version of Sweep and Prune (SAP) for efficient collision pair detection in the narrow phase, sorting objects along an axis with maximum variance.",
  "sheet": "# DirectSAPNarrowPhase\n\n## Overview\nThe `DirectSAPNarrowPhase` is a component that implements the direct version of the Sweep and Prune (SAP) algorithm for narrow phase collision detection. It sorts all primitives along the axis with the greatest variance to efficiently detect overlapping pairs.\n\n## Mathematical Model\n### Axis Selection\nLet \\(A_1, A_2, ..., A_n\\) represent the set of axis-aligned bounding boxes (AABBs). The variance for an axis is calculated as:\n\\[\text{Var}(X_i) = E[X_i^2] - [E[X_i]]^2, \n\\quad i = x, y, z\ngiven \\(E[X_i]\\) and \\(E[X_i^2]\\) are the expected values of coordinates along axis \\(i\\). The greatest variance axis is determined by:\n\\[k_{max} = \\arg \\max_k (\text{Var}(X_k))\\]\n\n### Updating End Points\nThe algorithm updates the minimum and maximum coordinates, denoted as \\(p_i^{min}\\) and \\(p_i^{max}\\), along the selected axis for all objects.\n\n### Sorting End Points\nThe end points are sorted to identify overlapping AABBs efficiently. The overlap between two adjacent objects is determined by:\n\\[ \\text{overlap}(A_j, A_k) = (A_j^{max} > A_k^{min}) \\\n   \\land (A_k^{max} > A_j^{min}),\n\\quad j,k \\in [1,n],\n\\quad  j \\neq k\n\\]\nwhere \\(j, k\\) are the indices of the two objects being compared.\n\n### Filtering and Narrow Phase Processing\nThe algorithm filters out non-overlapping pairs based on sorted end points and passes overlapping pairs to the narrow phase for detailed collision detection. If a pair is detected as potentially colliding, it is sent to further processing steps such as intersection tests or response calculations.\n\n## Parameters and Data\n- **showOnlyInvestigatedBoxes**: `bool` - Show only boxes which will be sent to narrow phase (default: false).\n- **nbPairs**: `int` - Number of pairs of elements sent to narrow phase (default: 0).\n"
}