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,
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_samplesrotations 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 minimizesmeasure_typeis returned. The result is an approximation whose quality improves withnum_samples; it is not guaranteed to be the globally optimal OBB.Two further candidates are appended by default.
include_axis_alignedadds 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 (withmax_search_pointsthe 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_pcaadds 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 bynum_samplesalone. Both extras are cheap relative tonum_samplescandidates.After the initial search the best
num_refine_startsorientations from distinct basins are each refined bynum_refine_iterationsrounds 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 largernum_samplesat a fraction of the cost. The orientation search scores every point by default. For a very large point set,max_search_pointscaps 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
OBBMeasureTypemember:OBBMeasureType.VOLUMEminimizes the box volume;OBBMeasureType.SURFACE_AREAminimizes the box surface area;OBBMeasureType.MEAN_WIDTHminimizes 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. Whenpointsis 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
0together withnum_spin_samples=0to 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
0to 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.transformis awarp.arrayofwarp.transformmapping the box’s local frame (axis-aligned and centered at the origin) into world space,extentsis awarp.arrayofwarp.vec3of the box’s full side lengths, andmeasureis awarp.arrayoffloat32holding the achieved value ofmeasure_type. Read an element withtransform.numpy()[0](which synchronizes) when a host-side value is needed.- Return type:
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_pcaenabled 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. Passinclude_pca=Falsefor a bitwise reproducible result.- Raises:
ValueError – If
num_samples,num_refine_startsornum_refine_samplesis not a positive integer, ifnum_spin_samplesornum_refine_iterationsis negative, ifmax_search_pointsis not positive, ifpointsis empty, or if the search needs too much scratch memory.- Parameters:
points (warp.array[warp.vec3])
measure_type (OBBMeasureType)
num_samples (int)
include_axis_aligned (bool)
include_pca (bool)
max_search_points (int | None)
num_refine_starts (int)
num_refine_iterations (int)
num_refine_samples (int)
num_spin_samples (int)
device (DeviceLike | None)
- Return type: