warp.geometry.oriented_bounding_box#

warp.geometry.oriented_bounding_box(
points,
measure_type=OBBMeasureType.VOLUME,
num_samples=4096,
*,
include_axis_aligned=True,
include_pca=True,
max_search_points=None,
num_refine_starts=_OBB_REFINE_STARTS,
num_refine_iterations=_OBB_REFINE_ITERATIONS,
num_refine_samples=_OBB_REFINE_SAMPLES,
num_spin_samples=_OBB_SPIN_SAMPLES,
device=None,
)[source]#

Approximate an oriented bounding box (OBB) of a point set by sampling orientations.

Candidate orientations are drawn from a Super-Fibonacci spiral, which spreads num_samples rotations near-uniformly over SO(3) (Alexa, “Super-Fibonacci Spirals: Fast, Low-Discrepancy Sampling of SO(3)”, CVPR 2022). For each orientation the axis-aligned bounding box of the rotated points is evaluated, and the orientation whose box minimizes measure_type is returned. The result is an approximation whose quality improves with num_samples; it is not guaranteed to be the globally optimal OBB.

Two further candidates are appended by default. include_axis_aligned adds the identity rotation, which the spiral never contains exactly and which guarantees the result is no worse than the axis-aligned bounding box when every point is scored (with max_search_points the candidates are compared on the subsample only, so a box that wins there can be larger than the axis-aligned box over all points). include_pca adds the principal axes of the point set, obtained from the eigenvectors of its covariance matrix. The spiral resolves orientation only to roughly its sample spacing, and on a strongly elongated shape a few degrees of error costs a large amount of volume, so the principal axes are often a much better answer there than any sampled rotation. For a near-isotropic point set the covariance eigenvectors are close to degenerate and that candidate carries little information, leaving accuracy governed by num_samples alone. Both extras are cheap relative to num_samples candidates.

After the initial search the best num_refine_starts orientations from distinct basins are each refined by num_refine_iterations rounds of coarse-to-fine local search: each round scores a batch of orientations in a shrinking angular neighborhood of the current best of that start and keeps any improvement. Three spin rounds then rotate each start about each of its box axes, which converges onto a face-flush box that the isotropic rounds reach only slowly. The best refined orientation is returned. Because the spiral resolves orientation only to its sample spacing, this reaches the quality of a much larger num_samples at a fraction of the cost. The orientation search scores every point by default. For a very large point set, max_search_points caps the search at a strided subsample, which bounds its cost but can change which orientation is chosen; the returned box is always re-measured over every point, so it stays exact and encloses all of them.

The cost of the search is proportional to the number of points. A bounding box is determined by the convex hull of the points, so replacing a very large input with its convex hull vertices, or with any other subset that is known to contain every hull vertex, leaves the box for every orientation unchanged and lowers the cost in proportion to the number of points removed. Unlike max_search_points, this does not change which orientation is searched. The PCA candidate is the one exception, since it comes from the covariance of whichever points are given.

To fit many point sets at once, see oriented_bounding_boxes().

Parameters:
  • points (warp.array[warp.vec3]) – Array of point positions of type warp.vec3.

  • measure_type (OBBMeasureType) – Quantity to minimize, as an OBBMeasureType member: OBBMeasureType.VOLUME minimizes the box volume; OBBMeasureType.SURFACE_AREA minimizes the box surface area; OBBMeasureType.MEAN_WIDTH minimizes the box mean width, half the sum of its side lengths.

  • num_samples (int) – Number of candidate orientations to sample from the spiral. Larger values give a tighter box at higher cost.

  • include_axis_aligned (bool) – Whether to also evaluate the identity rotation.

  • include_pca (bool) – Whether to also evaluate the principal axes of points.

  • max_search_points (int | None) – Upper bound on how many points are used to score candidate orientations, or None (the default) to score over every point. When points is larger than a given cap, candidates are scored over a deterministic strided subsample of about that size, which bounds the cost of the search but can change which orientation is chosen. The winning orientation’s box is recomputed over the full point set, so the returned box is exact and encloses every point either way. For very large inputs, prefer filtering the points as described above, which does not change the search.

  • num_refine_starts (int) – Number of distinct candidate orientations that are refined, each from a different basin of the search space. Refining several avoids committing to a sampled orientation that is not near the best one.

  • num_refine_iterations (int) – Number of coarse-to-fine refinement rounds after the initial search. Pass 0 together with num_spin_samples=0 to return the best sampled orientation directly.

  • num_refine_samples (int) – Number of orientations probed per refinement round around each start.

  • num_spin_samples (int) – Number of angles probed about each of the box’s three axes in each of three final spin rounds (coarse to fine) around each start. Spinning about an axis keeps a box face that is flush with a face of the point set’s convex hull flush, so this settles the box onto the best such position. Pass 0 to skip the spin rounds.

  • device (DeviceLike | None) – Device on which to run. Defaults to the device of points.

Returns:

A tuple (transform, extents, measure) of length-1 device arrays, left on the device so the whole search is capturable in a CUDA graph. transform is a warp.array of warp.transform mapping the box’s local frame (axis-aligned and centered at the origin) into world space, extents is a warp.array of warp.vec3 of the box’s full side lengths, and measure is a warp.array of float32 holding the achieved value of measure_type. Read an element with transform.numpy()[0] (which synchronizes) when a host-side value is needed.

Return type:

tuple[wp.array, wp.array, wp.array]

Note

The search, refinement, and winner selection all run on the device, so this function does not synchronize and can be captured in a CUDA graph. Refinement is deterministic (its neighborhood is generated without host randomness).

With include_pca enabled the covariance matrix is accumulated with floating-point atomics, so the principal axes – and therefore the result, when they win – can vary in the last bits between runs. Pass include_pca=False for a bitwise reproducible result.

Raises:

ValueError – If num_samples, num_refine_starts or num_refine_samples is not a positive integer, if num_spin_samples or num_refine_iterations is negative, if max_search_points is not positive, if points is empty, or if the search needs too much scratch memory.

Parameters:
Return type:

tuple[wp.array, wp.array, wp.array]