CubeCollisionModel
The Cube Collision Model is a hierarchical bounding volume representation used in collision detection for physics simulations and computer graphics applications. It constructs a tree-like structure where each node represents a cuboid (bounding box) that encloses a group of objects or sub-cuboids.
- abstract
- The CubeCollisionModel is a collision detection component representing objects as hierarchical bounding cubes, enabling efficient collision checks through recursive traversal of the tree-like structure.
- sheet
- # CubeCollisionModel ## Overview The CubeCollisionModel is a collision detection component that represents objects as hierarchical bounding cubes. It constructs a tree-like structure where each node represents a cuboid (bounding box) that encloses a group of objects or sub-cuboids, enabling efficient collision checks through recursive traversal. ## Parameters and Data This component does not expose any significant data fields. ## Dependencies and Connections The CubeCollisionModel typically requires other components such as `MechanicalObject` for defining the geometry of the objects to be enclosed by the bounding cubes. It fits into the scene graph as a collision model, often connected to solvers or constraint systems that require accurate collision detection. ## Practical Notes Dynamic updates to the cube structure are necessary when object positions change significantly. The tree may need reconstruction from scratch in such cases, but minor changes can be handled through incremental updates.
- name
- Cube Collision Model
- description
- The Cube Collision Model is a hierarchical bounding volume representation used in collision detection for physics simulations and computer graphics applications. It constructs a tree-like structure where each node represents a cuboid (bounding box) that encloses a group of objects or sub-cuboids.
- parameters
-
- {'name': 'Max Depth', 'description': 'The maximum depth of the bounding volume hierarchy. Higher values result in more levels and smaller, tighter-fitting bounding boxes at the lower levels.', 'type': 'integer', 'default_value': 0, 'min_value': 0}
- features
-
- The model automatically generates a hierarchical structure based on the input geometry or objects to be simulated.
- It supports dynamic updates of the hierarchy when the underlying objects change position or orientation.
- The bounding volumes are cuboids, which are simple and computationally efficient for intersection tests.
- For non-spherical objects, it provides tighter bounds compared to sphere-based models, leading to more accurate collision detection with fewer false positives.
- The hierarchical nature allows for efficient culling of non-colliding branches during the intersection test, improving performance in complex scenes.
- usage
- The Cube Collision Model is particularly useful for applications where precise collision detection between irregularly shaped objects is required. It's commonly used in physics engines for games and simulations to detect collisions between rigid bodies or deformable objects. By controlling the max depth parameter, users can balance between detection accuracy and computational cost.
- example
- In a game engine, you might set up a Cube Collision Model with a max depth of 4 to efficiently detect collisions between complex characters and environment geometry in a large outdoor scene. This would provide more accurate collision responses than simpler bounding volume methods while still being computationally feasible for real-time interaction.
- maths
- # Mathematical and Physical Description of the Cube Collision Model ## Overview The Cube Collision Model is a hierarchical bounding volume representation used in collision detection for physics simulations and computer graphics applications. It constructs a tree-like structure where each node represents a cuboid (bounding box) that encloses a group of objects or sub-cuboids. ## Hierarchical Structure ### Tree Construction 1. **Initialization**: The model starts by constructing the root cube, which encompasses all objects in the simulation space. 2. **Splitting Nodes**: - At each level `i` of the hierarchy, nodes are split along their largest dimension to create two sub-cubes, provided that the number of enclosed objects exceeds a threshold (usually set at 4). - The splitting axis is determined by the longest side of the cuboid. ### Recursive Splitting Process - **Initial Cube**: At level `0`, a single cube `C_0` covers all objects. This root node does not have any children yet. - **Level Transition**: - For each level `i`, the following steps are performed for every cuboid `c_j^i` at that level: - Calculate the number of enclosed objects `ncells` in the interval `[subcells.first.getIndex(), subcells.second.getIndex())`. - If `ncells > 4`, the node is split along its largest dimension (determined by comparing lengths along axes X, Y, and Z). ### Mathematical Formulation #### Splitting Condition - Let `C_j^i` be a cuboid at level `i`. The splitting condition can be expressed as: \[ \text{if } ncells > 4 \] - Calculate the lengths of sides in each dimension for `C_j^i`: \[ l_0 = C_j^i.maxX - C_j^i.minX, \\ l_1 = C_j^i.maxY - C_j^i.minY, \\ l_2 = C_j^i.maxZ - C_j^i.minZ \] - Determine the splitting axis `splitAxis` by: \[ splitAxis = \argmax_k(l_k) \] #### Partitioning and Sorting - Objects within each cuboid are partitioned based on their position along `splitAxis`. The objects are sorted using a stable sort that maintains relative order. - After sorting, the cuboid is split into two sub-cuboids at the median index: \[ C_{j1}^{i+1}, C_{j2}^{i+1} \] ### Cube Representation Each node `C_j^i` in the tree can be represented as a pair of cuboid indices `(subcells.first.getIndex(), subcells.second.getIndex())`, where: - `subcells.first.getIndex()` denotes the starting index for the objects or sub-cuboids within this cube. - `subcells.second.getIndex()` is the ending index (non-inclusive). ### Parent-Child Relationship The parent-child relationship between cuboids is maintained through a list `parentOf`, where: \[ \text{parentOf}[i] = j \quad \Rightarrow \quad C_j^i \text{ is the parent of } C_{j1}^{i+1}, C_{j2}^{i+1} \] ## Collision Detection The tree structure enables efficient collision detection through recursive traversal. The algorithm begins at the root node and recursively checks for potential collisions between sub-cubes, thereby reducing the number of pairwise comparisons. ### Recursive Traversal - **Base Case**: At leaf nodes (nodes with no children), exact object-to-object or object-to-sub-cuboid collision tests are performed. - **Recursive Step**: For internal nodes, if the bounding boxes overlap, their child cuboids are recursively checked for collisions. ## Update and Maintenance The tree structure can be updated dynamically to reflect changes in object positions. This involves recalculating the enclosing cubes and ensuring that the hierarchical constraints (e.g., splitting condition) are satisfied. ### Dynamic Updates - **Reconstruction**: If significant changes occur, the entire tree may need reconstruction from scratch. - **Incremental Updates**: For minor changes, only affected sub-trees are updated while maintaining the overall structure. ## Visualization and Debugging The Cube Collision Model supports visualization by drawing bounding box lines for each cuboid in different levels of transparency. This aids in debugging and visualizing the hierarchical structure during runtime.
{
"name": "CubeCollisionModel",
"main": {
"name": "CubeCollisionModel",
"namespace": "sofa::component::collision::geometry",
"module": "Sofa.Component.Collision.Geometry",
"include": "sofa/component/collision/geometry/CubeCollisionModel.h",
"doc": "Collision model representing a cube.",
"inherits": [
"CollisionModel"
],
"templates": [],
"data_fields": [],
"links": [],
"methods": [
{
"name": "drawCollisionModel",
"return_type": "void",
"params": [
{
"name": "vparams",
"type": "const core::visual::VisualParams *"
}
],
"is_virtual": true,
"is_pure_virtual": false,
"is_static": false,
"access": "protected"
},
{
"name": "resize",
"return_type": "void",
"params": [
{
"name": "size",
"type": "int"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "setParentOf",
"return_type": "void",
"params": [
{
"name": "childIndex",
"type": "int"
},
{
"name": "min",
"type": "const sofa::type::Vec3 &"
},
{
"name": "max",
"type": "const sofa::type::Vec3 &"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "setParentOf",
"return_type": "void",
"params": [
{
"name": "childIndex",
"type": "int"
},
{
"name": "min",
"type": "const sofa::type::Vec3 &"
},
{
"name": "max",
"type": "const sofa::type::Vec3 &"
},
{
"name": "normal",
"type": "const sofa::type::Vec3 &"
},
{
"name": "angle",
"type": "const SReal"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "setLeafCube",
"return_type": "void",
"params": [
{
"name": "cubeIndex",
"type": "int"
},
{
"name": "childIndex",
"type": "int"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "setLeafCube",
"return_type": "void",
"params": [
{
"name": "cubeIndex",
"type": "int"
},
{
"name": "children",
"type": "std::pair<core::CollisionElementIterator, core::CollisionElementIterator>"
},
{
"name": "min",
"type": "const sofa::type::Vec3 &"
},
{
"name": "max",
"type": "const sofa::type::Vec3 &"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "getNumberCells",
"return_type": "int",
"params": [],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "getBoundingTree",
"return_type": "void",
"params": [
{
"name": "bounding",
"type": "int &"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "getLeafIndex",
"return_type": "int",
"params": [
{
"name": "index",
"type": "int"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "getLeafEndIndex",
"return_type": "int",
"params": [
{
"name": "index",
"type": "int"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "getCubeData",
"return_type": "const CubeData &",
"params": [
{
"name": "index",
"type": "int"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "computeBoundingTree",
"return_type": "void",
"params": [
{
"name": "maxDepth",
"type": "int"
}
],
"is_virtual": true,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "getInternalChildren",
"return_type": "std::pair<core::CollisionElementIterator, core::CollisionElementIterator>",
"params": [
{
"name": "index",
"type": "int"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "getExternalChildren",
"return_type": "std::pair<core::CollisionElementIterator, core::CollisionElementIterator>",
"params": [
{
"name": "index",
"type": "int"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "isLeaf",
"return_type": "bool",
"params": [
{
"name": "index",
"type": "int"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "addCube",
"return_type": "int",
"params": [
{
"name": "subcellsBegin",
"type": "Cube"
},
{
"name": "subcellsEnd",
"type": "Cube"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "updateCube",
"return_type": "void",
"params": [
{
"name": "index",
"type": "int"
}
],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
},
{
"name": "updateCubes",
"return_type": "void",
"params": [],
"is_virtual": false,
"is_pure_virtual": false,
"is_static": false,
"access": "public"
}
]
},
"desc": {
"name": "Cube Collision Model",
"description": "The Cube Collision Model is a hierarchical bounding volume representation used in collision detection for physics simulations and computer graphics applications. It constructs a tree-like structure where each node represents a cuboid (bounding box) that encloses a group of objects or sub-cuboids.",
"parameters": [
{
"name": "Max Depth",
"description": "The maximum depth of the bounding volume hierarchy. Higher values result in more levels and smaller, tighter-fitting bounding boxes at the lower levels.",
"type": "integer",
"default_value": 0,
"min_value": 0
}
],
"features": [
"The model automatically generates a hierarchical structure based on the input geometry or objects to be simulated.",
"It supports dynamic updates of the hierarchy when the underlying objects change position or orientation.",
"The bounding volumes are cuboids, which are simple and computationally efficient for intersection tests.",
"For non-spherical objects, it provides tighter bounds compared to sphere-based models, leading to more accurate collision detection with fewer false positives.",
"The hierarchical nature allows for efficient culling of non-colliding branches during the intersection test, improving performance in complex scenes."
],
"usage": "The Cube Collision Model is particularly useful for applications where precise collision detection between irregularly shaped objects is required. It's commonly used in physics engines for games and simulations to detect collisions between rigid bodies or deformable objects. By controlling the max depth parameter, users can balance between detection accuracy and computational cost.",
"example": "In a game engine, you might set up a Cube Collision Model with a max depth of 4 to efficiently detect collisions between complex characters and environment geometry in a large outdoor scene. This would provide more accurate collision responses than simpler bounding volume methods while still being computationally feasible for real-time interaction."
},
"maths": {
"maths": "# Mathematical and Physical Description of the Cube Collision Model\n\n## Overview\nThe Cube Collision Model is a hierarchical bounding volume representation used in collision detection for physics simulations and computer graphics applications. It constructs a tree-like structure where each node represents a cuboid (bounding box) that encloses a group of objects or sub-cuboids.\n\n## Hierarchical Structure\n### Tree Construction\n1. **Initialization**: The model starts by constructing the root cube, which encompasses all objects in the simulation space.\n2. **Splitting Nodes**:\n - At each level `i` of the hierarchy, nodes are split along their largest dimension to create two sub-cubes, provided that the number of enclosed objects exceeds a threshold (usually set at 4).\n - The splitting axis is determined by the longest side of the cuboid.\n\n### Recursive Splitting Process\n- **Initial Cube**: At level `0`, a single cube `C_0` covers all objects. This root node does not have any children yet.\n- **Level Transition**:\n - For each level `i`, the following steps are performed for every cuboid `c_j^i` at that level:\n - Calculate the number of enclosed objects `ncells` in the interval `[subcells.first.getIndex(), subcells.second.getIndex())`.\n - If `ncells > 4`, the node is split along its largest dimension (determined by comparing lengths along axes X, Y, and Z).\n\n### Mathematical Formulation\n#### Splitting Condition\n- Let `C_j^i` be a cuboid at level `i`. The splitting condition can be expressed as:\n\\[ \\text{if } ncells > 4 \\]\n - Calculate the lengths of sides in each dimension for `C_j^i`:\n \\[\n l_0 = C_j^i.maxX - C_j^i.minX, \\\\\n l_1 = C_j^i.maxY - C_j^i.minY, \\\\\n l_2 = C_j^i.maxZ - C_j^i.minZ\n \\]\n - Determine the splitting axis `splitAxis` by:\n \\[\n splitAxis = \\argmax_k(l_k)\n \\]\n#### Partitioning and Sorting\n- Objects within each cuboid are partitioned based on their position along `splitAxis`. The objects are sorted using a stable sort that maintains relative order.\n- After sorting, the cuboid is split into two sub-cuboids at the median index:\n\\[\n C_{j1}^{i+1}, C_{j2}^{i+1}\n\\]\n\n### Cube Representation\nEach node `C_j^i` in the tree can be represented as a pair of cuboid indices `(subcells.first.getIndex(), subcells.second.getIndex())`, where:\n- `subcells.first.getIndex()` denotes the starting index for the objects or sub-cuboids within this cube.\n- `subcells.second.getIndex()` is the ending index (non-inclusive).\n\n### Parent-Child Relationship\nThe parent-child relationship between cuboids is maintained through a list `parentOf`, where:\n\\[\n \\text{parentOf}[i] = j \\quad \\Rightarrow \\quad C_j^i \\text{ is the parent of } C_{j1}^{i+1}, C_{j2}^{i+1}\n\\]\n\n## Collision Detection\nThe tree structure enables efficient collision detection through recursive traversal. The algorithm begins at the root node and recursively checks for potential collisions between sub-cubes, thereby reducing the number of pairwise comparisons.\n\n### Recursive Traversal\n- **Base Case**: At leaf nodes (nodes with no children), exact object-to-object or object-to-sub-cuboid collision tests are performed.\n- **Recursive Step**: For internal nodes, if the bounding boxes overlap, their child cuboids are recursively checked for collisions.\n\n## Update and Maintenance\nThe tree structure can be updated dynamically to reflect changes in object positions. This involves recalculating the enclosing cubes and ensuring that the hierarchical constraints (e.g., splitting condition) are satisfied.\n\n### Dynamic Updates\n- **Reconstruction**: If significant changes occur, the entire tree may need reconstruction from scratch.\n- **Incremental Updates**: For minor changes, only affected sub-trees are updated while maintaining the overall structure.\n\n## Visualization and Debugging\nThe Cube Collision Model supports visualization by drawing bounding box lines for each cuboid in different levels of transparency. This aids in debugging and visualizing the hierarchical structure during runtime."
},
"summary": {
"abstract": "The CubeCollisionModel is a collision detection component representing objects as hierarchical bounding cubes, enabling efficient collision checks through recursive traversal of the tree-like structure.",
"sheet": "# CubeCollisionModel\n\n## Overview\nThe CubeCollisionModel is a collision detection component that represents objects as hierarchical bounding cubes. It constructs a tree-like structure where each node represents a cuboid (bounding box) that encloses a group of objects or sub-cuboids, enabling efficient collision checks through recursive traversal.\n\n## Parameters and Data\nThis component does not expose any significant data fields.\n\n## Dependencies and Connections\nThe CubeCollisionModel typically requires other components such as `MechanicalObject` for defining the geometry of the objects to be enclosed by the bounding cubes. It fits into the scene graph as a collision model, often connected to solvers or constraint systems that require accurate collision detection.\n\n## Practical Notes\nDynamic updates to the cube structure are necessary when object positions change significantly. The tree may need reconstruction from scratch in such cases, but minor changes can be handled through incremental updates."
}
}