newton.geometry.BroadPhaseSAP#

class newton.geometry.BroadPhaseSAP(geom_shape_world, geom_flags=None, sweep_thread_count_multiplier=5, sort_type=SAPSortType.SEGMENTED, tile_block_dim=None, device=None)[source]#

Bases: object

Sweep and Prune (SAP) broad phase collision detection.

This class implements the sweep and prune algorithm for broad phase collision detection. It efficiently finds potentially colliding pairs of objects by sorting their bounding box projections along a fixed axis and checking for overlaps.

__init__(geom_shape_world, geom_flags=None, sweep_thread_count_multiplier=5, sort_type=SAPSortType.SEGMENTED, tile_block_dim=None, device=None)#

Initialize arrays for sweep and prune broad phase collision detection.

Parameters:

  • geom_shape_world – Array of world indices for each geometry (numpy or warp array). Represents which world each geometry belongs to for world-aware collision detection.

  • geom_flags – Optional array of shape flags (numpy or warp array). If provided, only shapes with the COLLIDE_SHAPES flag will be included in collision checks. This efficiently filters out visual-only shapes.

  • sweep_thread_count_multiplier (int) – Multiplier for number of threads used in sweep phase

  • sort_type (SAPSortType) – Type of sorting algorithm to use (SEGMENTED or TILE)

  • tile_block_dim (int | None) – Block dimension for tile-based sorting (optional, auto-calculated if None). If None, will be set to next power of 2 >= max_geoms_per_world, capped at 512. Minimum value is 32 (required by wp.tile_sort). If provided, will be clamped to [32, 1024].

  • device – Device to store the precomputed arrays on. If None, uses CPU for numpy arrays or the device of the input warp array.

launch(geom_lower, geom_upper, geom_cutoffs, geom_collision_group, geom_shape_world, geom_count, candidate_pair, num_candidate_pair, device=None)#

Launch the sweep and prune broad phase collision detection with per-world segmented sort.

This method performs collision detection between geometries using a sweep and prune algorithm along a fixed axis. It processes each world independently using segmented sort, which is more efficient than global sorting when geometries are organized into separate worlds.

Parameters:

  • geom_lower (array(ndim=1, dtype=vec3f)) – Array of lower bounds for each geometry’s AABB

  • geom_upper (array(ndim=1, dtype=vec3f)) – Array of upper bounds for each geometry’s AABB

  • geom_cutoffs (array(ndim=1, dtype=float32)) – Array of cutoff distances for each geometry

  • geom_collision_group (array(ndim=1, dtype=int32)) – Array of collision group IDs for each geometry. Positive values indicate groups that only collide with themselves (and with negative groups). Negative values indicate groups that collide with everything except their negative counterpart. Zero indicates no collisions.

  • geom_shape_world (array(ndim=1, dtype=int32)) – Array of world indices for each geometry. Index -1 indicates global entities that collide with all worlds. Indices 0, 1, 2, … indicate world-specific entities.

  • geom_count (int) – Number of active bounding boxes to check (not used in world-based approach)

  • candidate_pair (array(ndim=1, dtype=vec2i)) – Output array to store overlapping geometry pairs

  • num_candidate_pair (array(ndim=1, dtype=int32)) – Output array to store number of overlapping pairs found

  • device – Device to launch on. If None, uses the device of the input arrays.

The method will populate candidate_pair with the indices of geometry pairs whose AABBs overlap when expanded by their cutoff distances, whose collision groups allow interaction, and whose worlds are compatible (same world or at least one is global). The number of pairs found will be written to num_candidate_pair[0].