bounds

triwarp.bounds

Bounding boxes: building them, and selecting or cropping with them.

Two halves. The constructors -- aabb, aabb_union, enclosing_diagonal and oriented_bounding_box -- reduce a cloud to a box. The queries -- points_in_aabb, points_in_obb and the crop_points / crop_mesh pair -- run the other way, testing points against a box someone already has. The two halves compose directly: every constructor's return is a query's argument, in that layout, which is why an oriented box is a (rotation, min_bound, max_bound) triple here rather than an object.

enclosing_diagonal is the one entry point here that exists for another module's sake rather than its own: it is the default search radius every mesh query in the package derives from its input's extent.

ITEMS_PER_CANDIDATE_SLICE module-attribute

ITEMS_PER_CANDIDATE_SLICE = 256

CONVEX_PREFILTER_MIN_POINTS module-attribute

CONVEX_PREFILTER_MIN_POINTS = 100000

aabb

aabb(points: array[vec3]) -> tuple[wp.vec3, wp.vec3]

Axis-aligned bounding box of points (component-wise min / max).

The reduction is minmax's wp.vec3 path: one chunked kernel writes both corners into a single six-element buffer, read back once. This wrapper contributes only the empty-input (+inf, -inf) convention, where minmax raises.

Parameters:

Name	Type	Description	Default
points	array[vec3]	(n, 3) positions as wp.vec3.	required

Returns:

Type	Description
tuple[vec3, vec3]	(min_bound, max_bound) with min_bound[i] ≤ p[i] ≤ max_bound[i] for every point p and axis i. If n == 0, min_bound is (+inf, …) and max_bound is (-inf, …).

See Also

aabb_union enclosing_diagonal points_in_aabb The other direction: which points a box already in hand contains. triwarp.reduce.minmax

Source code in triwarp/bounds.py

def aabb(points: wp.array[wp.vec3]) -> tuple[wp.vec3, wp.vec3]:
    """
    Axis-aligned bounding box of ``points`` (component-wise min / max).

    The reduction is [`minmax`][triwarp.reduce.minmax]'s ``wp.vec3`` path: one chunked kernel
    writes both corners into a single six-element buffer, read back once. This wrapper contributes
    only the empty-input ``(+inf, -inf)`` convention, where ``minmax`` raises.

    Parameters
    ----------
    points
        ``(n, 3)`` positions as ``wp.vec3``.

    Returns
    -------
    tuple[wp.vec3, wp.vec3]
        ``(min_bound, max_bound)`` with ``min_bound[i] ≤ p[i] ≤ max_bound[i]`` for every
        point ``p`` and axis ``i``. If ``n == 0``, ``min_bound`` is ``(+inf, …)`` and
        ``max_bound`` is ``(-inf, …)``.

    See Also
    --------
    [`aabb_union`][triwarp.bounds.aabb_union]
    [`enclosing_diagonal`][triwarp.bounds.enclosing_diagonal]
    [`points_in_aabb`][triwarp.bounds.points_in_aabb]
        The other direction: which points a box already in hand contains.
    [`triwarp.reduce.minmax`][triwarp.reduce.minmax]
    """
    if int(points.shape[0]) == 0:
        return (wp.vec3(math.inf, math.inf, math.inf), wp.vec3(-math.inf, -math.inf, -math.inf))
    return tw.reduce.minmax(points)

aabb_union

aabb_union(
    a_min: vec3, a_max: vec3, b_min: vec3, b_max: vec3
) -> tuple[wp.vec3, wp.vec3]

Smallest axis-aligned bounding box enclosing two given boxes.

Parameters:

Name	Type	Description	Default
a_min	vec3	Min/max corners of the first box.	required
a_max	vec3	Min/max corners of the first box.	required
b_min	vec3	Min/max corners of the second box.	required
b_max	vec3	Min/max corners of the second box.	required

Returns:

Type	Description
tuple[vec3, vec3]	(min_bound, max_bound) of the box enclosing both inputs.

See Also

aabb enclosing_diagonal

Source code in triwarp/bounds.py

def aabb_union(
    a_min: wp.vec3, a_max: wp.vec3, b_min: wp.vec3, b_max: wp.vec3
) -> tuple[wp.vec3, wp.vec3]:
    """
    Smallest axis-aligned bounding box enclosing two given boxes.

    Parameters
    ----------
    a_min, a_max
        Min/max corners of the first box.
    b_min, b_max
        Min/max corners of the second box.

    Returns
    -------
    tuple[wp.vec3, wp.vec3]
        ``(min_bound, max_bound)`` of the box enclosing both inputs.

    See Also
    --------
    [`aabb`][triwarp.bounds.aabb]
    [`enclosing_diagonal`][triwarp.bounds.enclosing_diagonal]
    """
    return wp.min(a_min, b_min), wp.max(a_max, b_max)

enclosing_diagonal

enclosing_diagonal(
    points: array[vec3], other: array[vec3] | None = None
) -> float

Diagonal of the axis-aligned box enclosing one or two point sets.

The default search radius for every mesh query in the package: no closest point, ray hit or tangent sphere can be further away than the diagonal of a box containing both the surface and the query points, so it is the smallest bound that is guaranteed not to cut an answer off. Pass other whenever the queries may lie outside the mesh's own box, which is the usual case -- with points alone a query far outside would get a radius too short to reach the surface.

Parameters:

Name	Type	Description	Default
points	array[vec3]	(n,) positions as wp.vec3, typically a mesh's vertices.	required
other	array[vec3] | None	Optional second (m,) set, typically the query points. None or empty measures points alone.	None

Returns:

Type	Description
float	|max_bound - min_bound| of the union box. inf when points is empty, since an empty box has infinite negative extent -- callers guard on the point count first.

Raises:

Type	Description
RuntimeError	If points and other are not all on one device.

See Also

aabb aabb_union

Source code in triwarp/bounds.py

def enclosing_diagonal(points: wp.array[wp.vec3], other: wp.array[wp.vec3] | None = None) -> float:
    """
    Diagonal of the axis-aligned box enclosing one or two point sets.

    The default search radius for every mesh query in the package: no closest point, ray hit or
    tangent sphere can be further away than the diagonal of a box containing both the surface and
    the query points, so it is the smallest bound that is guaranteed not to cut an answer off. Pass
    ``other`` whenever the queries may lie outside the mesh's own box, which is the usual case --
    with ``points`` alone a query far outside would get a radius too short to reach the surface.

    Parameters
    ----------
    points
        ``(n,)`` positions as ``wp.vec3``, typically a mesh's vertices.
    other
        Optional second ``(m,)`` set, typically the query points. ``None`` or empty measures
        ``points`` alone.

    Returns
    -------
    float
        ``|max_bound - min_bound|`` of the union box. ``inf`` when ``points`` is empty, since an
        empty box has infinite negative extent -- callers guard on the point count first.

    Raises
    ------
    RuntimeError
        If ``points`` and ``other`` are not all on one device.

    See Also
    --------
    [`aabb`][triwarp.bounds.aabb]
    [`aabb_union`][triwarp.bounds.aabb_union]
    """
    require_same_device(points=points, other=other)
    lower, upper = aabb(points)
    if other is not None and int(other.shape[0]) > 0:
        other_lower, other_upper = aabb(other)
        lower, upper = aabb_union(lower, upper, other_lower, other_upper)
    return float(wp.length(upper - lower))

points_in_aabb

points_in_aabb(
    points: array[vec3], min_bound: vec3, max_bound: vec3
) -> wp.array[wp.int32]

Return the indices of the points inside an axis-aligned box, boundary included.

The bounded selection primitive, and the one that needs no spatial index at all: every point is tested independently against six planes, so the cost is one pass over the cloud whatever the box holds. A tree would only help if the box were the thing being searched for -- see triwarp.neighbors.query_bvh_box for that direction.

Parameters:

Name	Type	Description	Default
points	array[vec3]	(n,) positions in space as wp.vec3.	required
min_bound	vec3	Opposite corners of the box, as aabb returns them. An empty box (any min_bound[i] > max_bound[i]) selects nothing.	required
max_bound	vec3	Opposite corners of the box, as aabb returns them. An empty box (any min_bound[i] > max_bound[i]) selects nothing.	required

Returns:

Type	Description
array[int32]	Ascending indices into points on points.device. Empty when nothing is inside.

Examples:

inside = tw.bounds.points_in_aabb(pts, wp.vec3(-1.0, -1.0, -1.0), wp.vec3(1.0, 1.0, 1.0))

Notes

Containment is inclusive: a point exactly on a face, edge or corner of the box is selected. A point with a nan coordinate is not selected, and neither is one at an infinity. Both conventions differ from half_space_mask, whose test is strict.

See Also

points_in_aabb_mask The same selection as a boolean mask, for a caller that wants to combine it. points_in_obb The oriented counterpart. crop_points This plus the gather, when the points themselves are wanted. aabb

Source code in triwarp/bounds.py

def points_in_aabb(
    points: wp.array[wp.vec3], min_bound: wp.vec3, max_bound: wp.vec3
) -> wp.array[wp.int32]:
    """
    Return the indices of the points inside an axis-aligned box, boundary included.

    The bounded selection primitive, and the one that needs no spatial index at all: every point is
    tested independently against six planes, so the cost is one pass over the cloud whatever the
    box holds. A tree would only help if the *box* were the thing being searched for -- see
    [`triwarp.neighbors.query_bvh_box`][triwarp.neighbors.query_bvh_box] for that direction.

    Parameters
    ----------
    points
        ``(n,)`` positions in space as ``wp.vec3``.
    min_bound, max_bound
        Opposite corners of the box, as [`aabb`][triwarp.bounds.aabb] returns them. An empty box
        (any ``min_bound[i] > max_bound[i]``) selects nothing.

    Returns
    -------
    wp.array[wp.int32]
        Ascending indices into ``points`` on ``points.device``. Empty when nothing is inside.

    Examples
    --------
    ```python
    inside = tw.bounds.points_in_aabb(pts, wp.vec3(-1.0, -1.0, -1.0), wp.vec3(1.0, 1.0, 1.0))
    ```

    Notes
    -----
    Containment is **inclusive**: a point exactly on a face, edge or corner of the box is selected.
    A point with a ``nan`` coordinate is *not* selected, and neither is one at an infinity. Both
    conventions differ from [`half_space_mask`][triwarp.points.half_space_mask], whose test is
    strict.

    See Also
    --------
    [`points_in_aabb_mask`][triwarp.bounds.points_in_aabb_mask]
        The same selection as a boolean mask, for a caller that wants to combine it.
    [`points_in_obb`][triwarp.bounds.points_in_obb]
        The oriented counterpart.
    [`crop_points`][triwarp.bounds.crop_points]
        This plus the gather, when the points themselves are wanted.
    [`aabb`][triwarp.bounds.aabb]
    """
    return tw.array.flatnonzero(points_in_aabb_mask(points, min_bound, max_bound))

points_in_aabb_mask

points_in_aabb_mask(
    points: array[vec3], min_bound: vec3, max_bound: vec3
) -> wp.array[wp.bool]

Flag the points inside an axis-aligned box, boundary included.

The mask form of points_in_aabb, for a caller that wants to intersect the selection with another predicate before compacting it -- combining masks costs one wp.map where combining index lists costs a set operation.

Parameters:

Name	Type	Description	Default
points	array[vec3]	(n,) positions in space as wp.vec3.	required
min_bound	vec3	Opposite corners of the box, as aabb returns them.	required
max_bound	vec3	Opposite corners of the box, as aabb returns them.	required

Returns:

Type	Description
array[bool]	Length-n mask on points.device. True marks a point to keep, the same sense as triwarp.points.half_space_mask.

See Also

points_in_aabb The index form, and where the boundary and nan conventions are documented. points_in_obb_mask triwarp.array.flatnonzero

Source code in triwarp/bounds.py

def points_in_aabb_mask(
    points: wp.array[wp.vec3], min_bound: wp.vec3, max_bound: wp.vec3
) -> wp.array[wp.bool]:
    """
    Flag the points inside an axis-aligned box, boundary included.

    The mask form of [`points_in_aabb`][triwarp.bounds.points_in_aabb], for a caller that wants to
    intersect the selection with another predicate before compacting it -- combining masks costs
    one ``wp.map`` where combining index lists costs a set operation.

    Parameters
    ----------
    points
        ``(n,)`` positions in space as ``wp.vec3``.
    min_bound, max_bound
        Opposite corners of the box, as [`aabb`][triwarp.bounds.aabb] returns them.

    Returns
    -------
    wp.array[wp.bool]
        Length-``n`` mask on ``points.device``. ``True`` marks a point to **keep**, the same sense
        as [`triwarp.points.half_space_mask`][triwarp.points.half_space_mask].

    See Also
    --------
    [`points_in_aabb`][triwarp.bounds.points_in_aabb]
        The index form, and where the boundary and ``nan`` conventions are documented.
    [`points_in_obb_mask`][triwarp.bounds.points_in_obb_mask]
    [`triwarp.array.flatnonzero`][triwarp.array.flatnonzero]
    """
    out_mask = wp.empty(int(points.shape[0]), dtype=wp.bool, device=points.device)
    if int(points.shape[0]) == 0:
        return out_mask

    wp.map(kernel_predicates.is_in_aabb, points, min_bound, max_bound, out=out_mask)
    return out_mask

points_in_obb

points_in_obb(
    points: array[vec3],
    rotation: mat33,
    min_bound: vec3,
    max_bound: vec3,
) -> wp.array[wp.int32]

Return the indices of the points inside an oriented box, boundary included.

Takes the box exactly as oriented_bounding_box returns it, so the two compose without a transpose or a corner rebuild.

Parameters:

Name	Type	Description	Default
points	array[vec3]	(n,) positions in world space as wp.vec3.	required
rotation	mat33	World-to-box frame as wp.mat33, i.e. its rows are the box axes in world coordinates. A point's box coordinates are rotation * p.	required
min_bound	vec3	Extent of the box along its own axes, in box coordinates.	required
max_bound	vec3	Extent of the box along its own axes, in box coordinates.	required

Returns:

Type	Description
array[int32]	Ascending indices into points on points.device. Empty when nothing is inside.

Examples:

rotation, lower, upper = tw.bounds.oriented_bounding_box(v, 256)
inside = tw.bounds.points_in_obb(v, rotation, lower, upper)

Notes

One rotated point per thread, then the identical six comparisons points_in_aabb makes -- the two share one predicate, so the inclusive boundary and the nan exclusion documented there hold here too, and the two functions cannot drift apart on either. Passing the identity as rotation reproduces the axis-aligned answer exactly.

Being a proper rotation, the frame's inverse is its transpose, so nothing here inverts a matrix; a general affine box would, and is not what this takes.

See Also

points_in_obb_mask points_in_aabb The axis-aligned counterpart, and the shared conventions. oriented_bounding_box Where the (rotation, min_bound, max_bound) triple comes from.

Source code in triwarp/bounds.py

def points_in_obb(
    points: wp.array[wp.vec3], rotation: wp.mat33, min_bound: wp.vec3, max_bound: wp.vec3
) -> wp.array[wp.int32]:
    """
    Return the indices of the points inside an oriented box, boundary included.

    Takes the box exactly as [`oriented_bounding_box`][triwarp.bounds.oriented_bounding_box]
    returns it, so the two compose without a transpose or a corner rebuild.

    Parameters
    ----------
    points
        ``(n,)`` positions in world space as ``wp.vec3``.
    rotation
        World-to-box frame as ``wp.mat33``, i.e. its **rows** are the box axes in world
        coordinates. A point's box coordinates are ``rotation * p``.
    min_bound, max_bound
        Extent of the box along its own axes, in box coordinates.

    Returns
    -------
    wp.array[wp.int32]
        Ascending indices into ``points`` on ``points.device``. Empty when nothing is inside.

    Examples
    --------
    ```python
    rotation, lower, upper = tw.bounds.oriented_bounding_box(v, 256)
    inside = tw.bounds.points_in_obb(v, rotation, lower, upper)
    ```

    Notes
    -----
    One rotated point per thread, then the identical six comparisons
    [`points_in_aabb`][triwarp.bounds.points_in_aabb] makes -- the two share one predicate, so the
    inclusive boundary and the ``nan`` exclusion documented there hold here too, and the two
    functions cannot drift apart on either. Passing the identity as ``rotation`` reproduces the
    axis-aligned answer exactly.

    Being a proper rotation, the frame's inverse is its transpose, so nothing here inverts a
    matrix; a general affine box would, and is not what this takes.

    See Also
    --------
    [`points_in_obb_mask`][triwarp.bounds.points_in_obb_mask]
    [`points_in_aabb`][triwarp.bounds.points_in_aabb]
        The axis-aligned counterpart, and the shared conventions.
    [`oriented_bounding_box`][triwarp.bounds.oriented_bounding_box]
        Where the ``(rotation, min_bound, max_bound)`` triple comes from.
    """
    return tw.array.flatnonzero(points_in_obb_mask(points, rotation, min_bound, max_bound))

points_in_obb_mask

points_in_obb_mask(
    points: array[vec3],
    rotation: mat33,
    min_bound: vec3,
    max_bound: vec3,
) -> wp.array[wp.bool]

Flag the points inside an oriented box, boundary included.

The mask form of points_in_obb; see points_in_aabb_mask for why the mask form exists.

Parameters:

Name	Type	Description	Default
points	array[vec3]	(n,) positions in world space as wp.vec3.	required
rotation	mat33	World-to-box frame as wp.mat33, rows being the box axes (points_in_obb documents the convention).	required
min_bound	vec3	Extent of the box along its own axes, in box coordinates.	required
max_bound	vec3	Extent of the box along its own axes, in box coordinates.	required

Returns:

Type	Description
array[bool]	Length-n mask on points.device. True marks a point to keep.

See Also

points_in_obb The index form, and where the conventions are documented. points_in_aabb_mask

Source code in triwarp/bounds.py

def points_in_obb_mask(
    points: wp.array[wp.vec3], rotation: wp.mat33, min_bound: wp.vec3, max_bound: wp.vec3
) -> wp.array[wp.bool]:
    """
    Flag the points inside an oriented box, boundary included.

    The mask form of [`points_in_obb`][triwarp.bounds.points_in_obb]; see
    [`points_in_aabb_mask`][triwarp.bounds.points_in_aabb_mask] for why the mask form exists.

    Parameters
    ----------
    points
        ``(n,)`` positions in world space as ``wp.vec3``.
    rotation
        World-to-box frame as ``wp.mat33``, rows being the box axes
        ([`points_in_obb`][triwarp.bounds.points_in_obb] documents the convention).
    min_bound, max_bound
        Extent of the box along its own axes, in box coordinates.

    Returns
    -------
    wp.array[wp.bool]
        Length-``n`` mask on ``points.device``. ``True`` marks a point to **keep**.

    See Also
    --------
    [`points_in_obb`][triwarp.bounds.points_in_obb]
        The index form, and where the conventions are documented.
    [`points_in_aabb_mask`][triwarp.bounds.points_in_aabb_mask]
    """
    out_mask = wp.empty(int(points.shape[0]), dtype=wp.bool, device=points.device)
    if int(points.shape[0]) == 0:
        return out_mask

    wp.map(kernel_predicates.is_in_obb, points, rotation, min_bound, max_bound, out=out_mask)
    return out_mask

crop_points

crop_points(
    points: array[vec3],
    min_bound: vec3,
    max_bound: vec3,
    *,
    rotation: mat33 | None = None,
) -> tuple[wp.array[wp.vec3], wp.array[wp.int32]]

Keep the points inside a box, returning the survivors and where they came from.

Parameters:

Name	Type	Description	Default
points	array[vec3]	(n,) positions in world space as wp.vec3.	required
min_bound	vec3	Opposite corners of the box: in world coordinates when rotation is None, in box coordinates otherwise.	required
max_bound	vec3	Opposite corners of the box: in world coordinates when rotation is None, in box coordinates otherwise.	required
rotation	mat33 | None	World-to-box frame as wp.mat33, rows being the box axes. None -- the default -- crops to the axis-aligned box, which is the same test with one transform fewer rather than a different rule; pass the frame oriented_bounding_box returns to crop to an oriented one.	None

Returns:

Name	Type	Description
kept	array[vec3]	The points inside the box, in ascending index order, on points.device.
indices	array[int32]	Their indices in points, so a caller can crop a parallel per-point attribute with triwarp.array.gather instead of re-running the test. This is the second return rather than an option because the compaction has already computed it.

Examples:

kept, indices = tw.bounds.crop_points(pts, wp.vec3(-1.0, -1.0, -1.0), wp.vec3(1.0, 1.0, 1.0))

See Also

crop_mesh The mesh counterpart, which must also decide what to do with a straddling face. points_in_aabb The selection alone, when the points are not needed. triwarp.array.gather

Source code in triwarp/bounds.py

def crop_points(
    points: wp.array[wp.vec3],
    min_bound: wp.vec3,
    max_bound: wp.vec3,
    *,
    rotation: wp.mat33 | None = None,
) -> tuple[wp.array[wp.vec3], wp.array[wp.int32]]:
    """
    Keep the points inside a box, returning the survivors and where they came from.

    Parameters
    ----------
    points
        ``(n,)`` positions in world space as ``wp.vec3``.
    min_bound, max_bound
        Opposite corners of the box: in world coordinates when ``rotation`` is ``None``, in box
        coordinates otherwise.
    rotation
        World-to-box frame as ``wp.mat33``, rows being the box axes. ``None`` -- the default --
        crops to the **axis-aligned** box, which is the same test with one transform fewer rather
        than a different rule; pass the frame
        [`oriented_bounding_box`][triwarp.bounds.oriented_bounding_box] returns to crop to an
        oriented one.

    Returns
    -------
    kept : wp.array[wp.vec3]
        The points inside the box, in ascending index order, on ``points.device``.
    indices : wp.array[wp.int32]
        Their indices in ``points``, so a caller can crop a parallel per-point attribute with
        [`triwarp.array.gather`][triwarp.array.gather] instead of re-running the test. This is the
        second return rather than an option because the compaction has already computed it.

    Examples
    --------
    ```python
    kept, indices = tw.bounds.crop_points(pts, wp.vec3(-1.0, -1.0, -1.0), wp.vec3(1.0, 1.0, 1.0))
    ```

    See Also
    --------
    [`crop_mesh`][triwarp.bounds.crop_mesh]
        The mesh counterpart, which must also decide what to do with a straddling face.
    [`points_in_aabb`][triwarp.bounds.points_in_aabb]
        The selection alone, when the points are not needed.
    [`triwarp.array.gather`][triwarp.array.gather]
    """
    indices = tw.array.flatnonzero(_box_mask(points, min_bound, max_bound, rotation))
    return tw.array.gather(points, indices), indices

crop_mesh

crop_mesh(
    vertices: array[vec3],
    faces: array[int32],
    min_bound: vec3,
    max_bound: vec3,
    *,
    rotation: mat33 | None = None,
) -> tuple[wp.array[wp.vec3], wp.array[wp.int32]]

Keep the faces whose three vertices all lie inside a box, reindexed from zero.

Parameters:

Name	Type	Description	Default
vertices	array[vec3]	(n_vertices,) mesh vertex positions on the target device.	required
faces	array[int32]	Length-3 * n_faces flat triangle index buffer.	required
min_bound	vec3	Opposite corners of the box: in world coordinates when rotation is None, in box coordinates otherwise.	required
max_bound	vec3	Opposite corners of the box: in world coordinates when rotation is None, in box coordinates otherwise.	required
rotation	mat33 | None	World-to-box frame as wp.mat33, rows being the box axes; None crops to the axis-aligned box. Same argument as crop_points's.	None

Returns:

Type	Description
tuple[array[vec3], array[int32]]	Compact (sub_vertices, sub_faces) on vertices.device, carrying only the vertices the kept faces reference.

Raises:

Type	Description
RuntimeError	If vertices and faces are not all on one device.

Examples:

rotation, lower, upper = tw.bounds.oriented_bounding_box(v, 256)
sub_v, sub_f = tw.bounds.crop_mesh(v, f, lower, upper, rotation=rotation)

Notes

A face straddling the box boundary is dropped, not clipped: the result is a subset of the input's triangles, so the crop never introduces a vertex the input did not have and the cut edge is ragged at the triangle scale. That is what makes the operation a selection rather than a boolean -- for a flush cut, intersect the mesh with the box as a solid instead.

To keep the straddling faces instead, take the mask and pass it on directly, which is the face_mode="any" rule:

mask = tw.bounds.points_in_aabb_mask(v, wp.vec3(-1.0, -1.0, 0.0), wp.vec3(1.0, 1.0, 3.0))
sub_v, sub_f = tw.selection.submesh_from_vertex_mask(v, f, mask, face_mode="any")

See Also

crop_points triwarp.selection.submesh_from_vertex_mask The face selection this delegates to, where face_mode is exposed.

Source code in triwarp/bounds.py

def crop_mesh(
    vertices: wp.array[wp.vec3],
    faces: wp.array[wp.int32],
    min_bound: wp.vec3,
    max_bound: wp.vec3,
    *,
    rotation: wp.mat33 | None = None,
) -> tuple[wp.array[wp.vec3], wp.array[wp.int32]]:
    """
    Keep the faces whose three vertices all lie inside a box, reindexed from zero.

    Parameters
    ----------
    vertices
        ``(n_vertices,)`` mesh vertex positions on the target device.
    faces
        Length-``3 * n_faces`` flat triangle index buffer.
    min_bound, max_bound
        Opposite corners of the box: in world coordinates when ``rotation`` is ``None``, in box
        coordinates otherwise.
    rotation
        World-to-box frame as ``wp.mat33``, rows being the box axes; ``None`` crops to the
        axis-aligned box. Same argument as
        [`crop_points`][triwarp.bounds.crop_points]'s.

    Returns
    -------
    tuple[wp.array[wp.vec3], wp.array[wp.int32]]
        Compact ``(sub_vertices, sub_faces)`` on ``vertices.device``, carrying only the vertices
        the kept faces reference.

    Raises
    ------
    RuntimeError
        If ``vertices`` and ``faces`` are not all on one device.

    Examples
    --------
    ```python
    rotation, lower, upper = tw.bounds.oriented_bounding_box(v, 256)
    sub_v, sub_f = tw.bounds.crop_mesh(v, f, lower, upper, rotation=rotation)
    ```

    Notes
    -----
    A face straddling the box boundary is **dropped**, not clipped: the result is a subset of the
    input's triangles, so the crop never introduces a vertex the input did not have and the cut
    edge is ragged at the triangle scale. That is what makes the operation a selection rather than
    a boolean -- for a flush cut, intersect the mesh with the box as a solid instead.

    To keep the straddling faces instead, take the mask and pass it on directly, which is the
    ``face_mode="any"`` rule:

    ```python
    mask = tw.bounds.points_in_aabb_mask(v, wp.vec3(-1.0, -1.0, 0.0), wp.vec3(1.0, 1.0, 3.0))
    sub_v, sub_f = tw.selection.submesh_from_vertex_mask(v, f, mask, face_mode="any")
    ```

    See Also
    --------
    [`crop_points`][triwarp.bounds.crop_points]
    [`triwarp.selection.submesh_from_vertex_mask`][triwarp.selection.submesh_from_vertex_mask]
        The face selection this delegates to, where ``face_mode`` is exposed.
    """
    require_same_device(vertices=vertices, faces=faces)
    vertex_mask = _box_mask(vertices, min_bound, max_bound, rotation)
    return tw.selection.submesh_from_vertex_mask(vertices, faces, vertex_mask, face_mode="all")

oriented_bounding_box

oriented_bounding_box(
    points: array[vec3],
    rotations: int = 4096,
    objective: Literal[
        "volume", "surface_area", "diagonal"
    ] = "volume",
    refine_iterations: int = 8,
) -> tuple[wp.mat33, wp.vec3, wp.vec3]

Smallest bounding box over sampled orientations, sharpened by local refinement, and its frame.

The box is searched, not solved, in two phases. The global phase scores rotations candidate orientations from the Super-Fibonacci spiral [Alexa 2022], a low-discrepancy sampling of SO(3), with the identity appended as the last candidate, scored in parallel. The refinement phase then takes the best-scoring candidates from up to four mutually distant basins and runs refine_iterations trust-region rounds around each: every round scores a low-discrepancy ball of perturbed frames whose angular radius starts at the global grid's covering radius and shrinks by a factor of 0.4 per round, keeping each chain's best. Refinement is monotone (each chain re-scores its own base), so the answer is never worse than the global phase's and never worse than aabb; with refine_iterations=0 and rotations=1 it reproduces the axis-aligned box exactly.

Cost is rotations * len(points) point transforms for the global phase plus refine_iterations * 512 * len(points) for refinement — but past CONVEX_PREFILTER_MIN_POINTS a convex_superset_mask prefilter first drops every point that provably cannot touch the box, so both phases run on the few hull-candidate survivors and the cost stops growing with the cloud (the box is identical: the mask keeps every hull vertex and the extents are order-independent reductions over them).

Parameters:

Name	Type	Description	Default
points	array[vec3]	(n, 3) positions as wp.vec3.	required
rotations	int	Number of global candidates to score, >= 1. The refinement default makes raising this past a few thousand pointless: the global phase only needs to land inside the optimum's basin, and refinement does the rest.	4096
objective	Literal['volume', 'surface_area', 'diagonal']	Which box quantity to minimize: "volume", "surface_area", or "diagonal" (the squared diagonal length, which has the same minimizer as the length).	'volume'
refine_iterations	int	Trust-region rounds after the global phase, >= 0. 0 disables refinement and returns the pure sampled answer.	8

Returns:

Name	Type	Description
rotation	mat33	World-to-box frame, i.e. its rows are the box axes in world coordinates. A world point p has box coordinates rotation * p, and a box corner maps back with wp.transpose(rotation) * corner. rotation is a proper rotation (orthonormal, determinant +1).
	(min_bound, max_bound)	Extent of points along the box axes, in box coordinates -- so the box is {transpose(rotation) * q : min_bound <= q <= max_bound} and its side lengths are max_bound - min_bound. For n == 0 these are (+inf, …) and (-inf, …) and rotation is the identity, matching aabb.

Raises:

Type	Description
ValueError	If rotations < 1, refine_iterations < 0, or objective is not one of the three named above.

Notes

Host traffic: the (rotations, 6) extent table (its objective and argmin are O(rotations) host arithmetic over a buffer far too small to be worth a device pass), the 36 bytes of the winning frame, and one (512, 6) table per refinement round. The refinement frames are generated and composed on the device, so the chains live on the device and the extent tables are the only per-round traffic.

The result is a converged local minimum, not a certified global one. Certifying the true minimum-volume box requires the exact-arithmetic search over the convex hull's face and edge events (O'Rourke's rotating-calipers family), and triwarp deliberately has no exact convex hull. What the sampling-plus-refinement search gives up is the certificate, not the volume: the global phase lands in the optimum's basin whenever the grid's covering radius resolves it, refinement converges within the basin, and the refined default ties or beats hull-based reference methods on volume across a range of test shapes (tilted/stretched icosahedron, cube shell, hemisphere, half torus). A pathological cloud whose optimum basin is narrower than the covering radius of rotations samples can still hide its box from this search; raise rotations if the input is a near-symmetric polyhedron far from any sampled orientation.

Neither hull-based reference is an oracle for the minimum either: on a stretched icosahedron the refined search returns less volume than both, because the hull-face-flush restriction misses optima whose box touches only edges and vertices.

See Also

aabb points_in_obb Takes this triple as returned, to select the points a box contains. trimesh.bounds.oriented_bounds igl.oriented_bounding_box

Source code in triwarp/bounds.py

def oriented_bounding_box(
    points: wp.array[wp.vec3],
    rotations: int = 4096,
    objective: Literal["volume", "surface_area", "diagonal"] = "volume",
    refine_iterations: int = 8,
) -> tuple[wp.mat33, wp.vec3, wp.vec3]:
    """
    Smallest bounding box over sampled orientations, sharpened by local refinement, and its frame.

    The box is searched, not solved, in two phases. The **global phase** scores ``rotations``
    candidate orientations from the **Super-Fibonacci spiral** [Alexa 2022], a low-discrepancy
    sampling of ``SO(3)``, with the identity appended as the last candidate, scored in parallel.
    The **refinement phase** then takes the best-scoring candidates from up to four mutually distant
    basins and runs ``refine_iterations`` trust-region rounds around each: every round scores a
    low-discrepancy ball of perturbed frames whose angular radius starts at the global grid's
    covering radius and shrinks by a factor of 0.4 per round, keeping each chain's best. Refinement
    is monotone (each
    chain re-scores its own base), so the answer is never worse than the global phase's and never
    worse than [`aabb`][triwarp.bounds.aabb]; with ``refine_iterations=0`` and ``rotations=1`` it
    reproduces the axis-aligned box exactly.

    Cost is ``rotations * len(points)`` point transforms for the global phase plus
    ``refine_iterations * 512 * len(points)`` for refinement — but past
    ``CONVEX_PREFILTER_MIN_POINTS`` a
    [`convex_superset_mask`][triwarp.points.convex_superset_mask] prefilter first drops every
    point that provably cannot touch the box, so both phases run on the few hull-candidate
    survivors and the cost stops growing with the cloud (the box is identical: the mask keeps
    every hull vertex and the extents are order-independent reductions over them).

    Parameters
    ----------
    points
        ``(n, 3)`` positions as ``wp.vec3``.
    rotations
        Number of global candidates to score, ``>= 1``. The refinement default makes raising this
        past a few thousand pointless: the global phase only needs to land *inside* the optimum's
        basin, and refinement does the rest.
    objective
        Which box quantity to minimize: ``"volume"``, ``"surface_area"``, or ``"diagonal"`` (the
        squared diagonal length, which has the same minimizer as the length).
    refine_iterations
        Trust-region rounds after the global phase, ``>= 0``. ``0`` disables refinement and returns
        the pure sampled answer.

    Returns
    -------
    rotation : wp.mat33
        World-to-box frame, i.e. its **rows** are the box axes in world coordinates. A world point
        ``p`` has box coordinates ``rotation * p``, and a box corner maps back with
        ``wp.transpose(rotation) * corner``. ``rotation`` is a proper rotation (orthonormal,
        determinant ``+1``).
    min_bound, max_bound
        Extent of ``points`` along the box axes, in box coordinates -- so the box is
        ``{transpose(rotation) * q : min_bound <= q <= max_bound}`` and its side lengths are
        ``max_bound - min_bound``. For ``n == 0`` these are ``(+inf, …)`` and ``(-inf, …)`` and
        ``rotation`` is the identity, matching
        [`aabb`][triwarp.bounds.aabb].

    Raises
    ------
    ValueError
        If ``rotations < 1``, ``refine_iterations < 0``, or ``objective`` is not one of the three
        named above.

    Notes
    -----
    Host traffic: the ``(rotations, 6)`` extent table (its objective and ``argmin`` are
    ``O(rotations)`` host arithmetic over a buffer far too small to be worth a device pass), the
    36 bytes of the winning frame, and one ``(512, 6)`` table per refinement round. The
    refinement frames are generated and composed **on the device**, so the chains live on
    the device and the extent tables are the only per-round traffic.

    **The result is a converged local minimum, not a certified global one.** Certifying the true
    minimum-volume box requires the exact-arithmetic search over the convex hull's face and edge
    events (O'Rourke's rotating-calipers family), and triwarp deliberately has no exact convex hull.
    What the sampling-plus-refinement search gives up is the *certificate*, not the volume: the
    global phase lands in the optimum's basin whenever the grid's covering radius resolves it,
    refinement converges within the basin, and the refined default ties or beats hull-based
    reference methods on volume across a range of test shapes (tilted/stretched icosahedron, cube
    shell, hemisphere, half torus).
    A pathological cloud whose optimum basin is narrower than the covering radius of ``rotations``
    samples can still hide its box from this search; raise ``rotations`` if the input is a
    near-symmetric polyhedron far from any sampled orientation.

    Neither hull-based reference is an oracle for the minimum either: on a stretched icosahedron
    the refined search returns **less** volume than both, because the hull-face-flush restriction
    misses optima whose box touches only edges and vertices.

    See Also
    --------
    [`aabb`][triwarp.bounds.aabb]
    [`points_in_obb`][triwarp.bounds.points_in_obb]
        Takes this triple as returned, to select the points a box contains.
    [`trimesh.bounds.oriented_bounds`][]
    ``igl.oriented_bounding_box``
    """
    if rotations < 1:
        raise ValueError(f"rotations must be >= 1, got {rotations}")
    if refine_iterations < 0:
        raise ValueError(f"refine_iterations must be >= 0, got {refine_iterations}")
    if objective not in ("volume", "surface_area", "diagonal"):
        raise ValueError(
            f'objective must be "volume", "surface_area" or "diagonal", got {objective!r}'
        )

    n = int(points.shape[0])
    if n == 0:
        return (
            wp.mat33(1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0),
            wp.vec3(math.inf, math.inf, math.inf),
            wp.vec3(-math.inf, -math.inf, -math.inf),
        )

    if n >= CONVEX_PREFILTER_MIN_POINTS:
        # Identical box, decided at the threshold above: only hull vertices can touch an
        # enclosing box, the mask keeps all of them, and min/max extents do not care about the
        # discarded interior points.
        mask = tw.points.convex_superset_mask(points)
        points = tw.array.gather(points, tw.array.flatnonzero(mask))
        n = int(points.shape[0])

    device = points.device
    axes = wp.empty(rotations, dtype=wp.mat33, device=device)
    wp.launch(
        kernel_bounds.oriented_box_candidate_axes,
        dim=rotations,
        inputs=[rotations, axes],
        device=device,
    )

    n_slices = max(1, (n + ITEMS_PER_CANDIDATE_SLICE - 1) // ITEMS_PER_CANDIDATE_SLICE)
    lower_np, upper_np = _scored_extents(points, axes, n_slices)
    loss_np = _objective_losses(upper_np - lower_np, objective)
    best = int(loss_np.argmin())

    if refine_iterations == 0:
        # The winning frame alone, 36 bytes through the shared readback scratch, so the pure
        # sampled path stays bit-comparable with the device-generated candidate set.
        rotation_np = read_scalar(axes, best)
        return (wp.mat33(*rotation_np.ravel()), wp.vec3(*lower_np[best]), wp.vec3(*upper_np[best]))

    frame_np, lower_best, upper_best = _refine_box(
        points, rotations, objective, refine_iterations, loss_np, n_slices
    )
    return (wp.mat33(*frame_np.ravel()), wp.vec3(*lower_best), wp.vec3(*upper_best))