Skip to content

[broadphase] Improve performance of AABBBroadPhase components #93

@th-skam

Description

@th-skam

TL;DR

  • ✅ Use AABBBroadPhase with TriangleGeometry
  • ❌ Avoid AABBBroadPhase with TetrahedronGeometry
    Reason: bounding boxes are updated every timestep, and with TetrahedronProximity the cost outweighs the benefit.

Profiling Summary

Profiling InsertionAlgorithm::doDetection in NeedleInsertion.py shows where time is spent. The algorithm involves four stages:

  1. Puncture detection - tip (PointProximity vs TriangleGeometry)
  2. Shaft collision - shaft (EdgeGeometry vs TriangleGeometry)
  3. Needle insertion - inside tissue (EdgeProximity vs TetrahedronGeometry)
  4. Reprojection - coupling points (TetrahedronProximity vs EdgeGeometry)

Without AABBBroadPhase

  • The bottleneck is shaft collision, where every needle edge is checked against all surface triangles.
  • Once inside tissue, shaft collision is disabled; spikes come from searching coupling points in tetrahedra. This is relatively cheap since only an EdgeProximity on the shaft is involved compared to shaft collision where all edges are involved.
Image

With AABBBroadPhase in TriangleGeometry

  • Significant speedup: shaft collision is accelerated.
Image

With AABBBroadPhase in TetrahedronGeometry

No benefit: updating tetrahedral bounding boxes each step is more expensive than the proximity search itself.

Image

Sub-issues

Metadata

Metadata

Assignees

Type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions