trueform

Modules | PY

Spatial

Spatial queries and acceleration structures for efficient geometric processing.

The Spatial module extends core queries to forms with spatial acceleration structures.

Forms

In trueform, Mesh, EdgeMesh, and PointCloud represent forms - geometric objects equipped with spatial acceleration structures. These structures enable efficient queries on large datasets by leveraging the underlying tf::tree spatial hierarchy.

Form	Description	Elements	Dimensions
`PointCloud`	Collection of points	Points	2D, 3D
`EdgeMesh`	Collection of line segments (edges)	Edges (2 verts)	2D, 3D
`Mesh`	Polygonal mesh (triangles or dynamic n-gons)	Faces (triangles or n-gons)	2D, 3D

Spatial Tree Building: The spatial tree is built automatically on first use of any spatial query. For performance-critical applications, you can prebuild the tree using form.build_tree() to avoid the cost during the first query.

PointCloud

Represents a collection of points:

import trueform as tf
import numpy as np

# Create point cloud
points = np.random.rand(100, 3).astype(np.float32)
cloud = tf.PointCloud(points)

# Access properties
print(f"Point cloud has {cloud.size} points in {cloud.dims}D")

# Prebuild spatial tree for performance (optional)
cloud.build_tree()  # Tree is built automatically on first query if not called

Property	Returns	Description
`points`	`ndarray`	Vertex coordinates
`size`	`int`	Number of points
`dims`	`int`	Dimensionality (2 or 3)
`dtype`	`np.dtype`	Data type (`float32` or `float64`)
`transformation`	`ndarray` or `None`	Transformation matrix

EdgeMesh

Represents a mesh of line segments:

# Create edge mesh (polyline or collection of segments)
edges = np.array([[0, 1], [1, 2], [2, 3]], dtype=np.int32)
points = np.array([[0, 0], [1, 0], [1, 1], [0, 1]], dtype=np.float32)
edge_mesh = tf.EdgeMesh(edges, points)

Property	Returns	Description
`edges`	`ndarray`	Edge connectivity (N, 2)
`points`	`ndarray`	Vertex coordinates
`number_of_edges`	`int`	Number of edges
`number_of_points`	`int`	Number of vertices
`dims`	`int`	Dimensionality (2 or 3)
`dtype`	`np.dtype`	Data type (`float32` or `float64`)
`transformation`	`ndarray` or `None`	Transformation matrix

EdgeMesh also provides topology properties. See Topology for details:

Property	Returns	Description
`edge_membership`	`OffsetBlockedArray`	Vertex → edges containing it
`vertex_link`	`OffsetBlockedArray`	Vertex → connected vertices

Mesh

Represents a polygonal mesh. Supports both fixed-size triangles and dynamic n-gons via OffsetBlockedArray:

import trueform as tf
import numpy as np

# Triangle mesh (fixed-size, 3 vertices per face)
faces = np.array([[0, 1, 2], [1, 2, 3]], dtype=np.int32)
points = np.array([[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0]], dtype=np.float32)
mesh = tf.Mesh(faces, points)

print(mesh.is_dynamic)  # False
print(mesh.ngon)        # 3 (triangles)

# Dynamic mesh (variable-sized faces using OffsetBlockedArray)
quads = np.array([[0, 1, 2, 3], [4, 5, 6, 7]], dtype=np.int32)
faces = tf.as_offset_blocked(quads)  # Convert to OffsetBlockedArray
mesh = tf.Mesh(faces, points)

print(mesh.is_dynamic)  # True
print(mesh.ngon)        # None (variable-sized)

Property	Returns	Description
`faces`	`ndarray` or `OffsetBlockedArray`	Face connectivity
`points`	`ndarray`	Vertex coordinates
`number_of_faces`	`int`	Number of faces
`number_of_points`	`int`	Number of vertices
`dims`	`int`	Dimensionality (2 or 3)
`is_dynamic`	`bool`	True if mesh uses variable-sized faces
`ngon`	`int` or `None`	Vertices per face (3 for triangles, None if dynamic)
`dtype`	`np.dtype`	Data type (`float32` or `float64`)
`transformation`	`ndarray` or `None`	Transformation matrix

Mesh also provides topology and geometry properties. See Topology and Geometry for details:

Property	Returns	Description
`face_membership`	`OffsetBlockedArray`	Vertex → faces containing it
`manifold_edge_link`	`ndarray` or `OffsetBlockedArray`	Face edge → adjacent face
`face_link`	`OffsetBlockedArray`	Face → adjacent faces
`vertex_link`	`OffsetBlockedArray`	Vertex → connected vertices
`normals`	`ndarray`	Face normals (3D only)
`point_normals`	`ndarray`	Vertex normals (3D only)

Transformations on Forms

Forms can be equipped with a transformation matrix, enabling queries on moving or transformed geometry without modifying the underlying data or rebuilding acceleration structures.

import numpy as np

# Create a 3D transformation matrix (4x4 homogeneous)
# Translation by (5, 0, 0)
translation = np.eye(4, dtype=np.float32)
translation[:3, 3] = [5, 0, 0]

# Attach transformation when creating the form
mesh = tf.Mesh(faces, points, transformation=translation)

# Or set transformation later
mesh.transformation = translation

# Queries automatically use the transformation
d = tf.distance(mesh, other_mesh)  # Queries mesh in transformed pose

# 2D rotation + translation (3x3 homogeneous)
angle = np.radians(45)
transform_2d = np.array([
    [np.cos(angle), -np.sin(angle), 10],
    [np.sin(angle),  np.cos(angle), 20],
    [0,              0,               1]
], dtype=np.float32)

edge_mesh = tf.EdgeMesh(edges, points_2d, transformation=transform_2d)

All forms support transformations:

PointCloud: Transforms points during spatial queries
EdgeMesh: Transforms edges during spatial queries
Mesh: Transforms faces during spatial queries

The transformation is applied internally during queries—the original data remains unchanged.

Shared Views

All forms support shared_view() to create a new instance that shares the same underlying data (points, faces/edges, and cached structures like the spatial tree) but has its own transformation. This is useful for efficiently querying the same geometry at multiple poses.

# Load mesh and build acceleration structures
mesh = tf.Mesh(faces, points)
mesh.build_tree()
mesh.build_face_membership()
mesh.build_manifold_edge_link()

# Create shared views with different transformations
mesh_a = mesh.shared_view()
mesh_a.transformation = transform_A

mesh_b = mesh.shared_view()
mesh_b.transformation = transform_B

# Both share the same data and tree - only transformation differs
# Queries use the respective transformations
d = tf.distance(mesh_a, mesh_b)
curves = tf.intersection_curves(mesh_a, mesh_b)

Method	Returns	Description
`shared_view()`	Same form type	New instance sharing data, with no transformation

Performance: Shared views avoid duplicating geometry and acceleration structures. Build the tree and topology structures once on the original form, then create shared views for different poses. All views benefit from the cached structures.

Spatial Queries

Queries on primitives extend to forms via tree-accelerated search. All queries support both form vs primitive and form vs form.

Distance and Intersection

Query	Returns
`distance2`	Squared distance
`distance`	Distance
`intersects`	`bool`

Supported primitives: Point, Segment, Line, Ray, Polygon, Plane

import trueform as tf

# Form vs primitive
d2 = tf.distance2(mesh, point)
d = tf.distance(mesh, segment)
hit = tf.intersects(mesh, polygon)

# Form vs form
d2 = tf.distance2(mesh0, mesh1)
collide = tf.intersects(mesh0, mesh1)

Neighbor Search

Generalizes closest_metric_point from Core with tree acceleration, optional search radius, and kNN support.

Form vs primitive returns (element_id, distance_squared, closest_point) or None if radius specified and nothing found.

Form vs form returns ((id0, id1), (distance_squared, pt0, pt1)) or None if radius specified and nothing found.

Supported primitives: Point, Segment, Line, Ray, Polygon, Plane

# Nearest neighbor (always finds one)
idx, dist2, pt = tf.neighbor_search(mesh, point)

# Nearest within radius (may not find any)
result = tf.neighbor_search(mesh, point, radius=1.0)
if result is not None:
    idx, dist2, pt = result

# Form vs form
(id0, id1), (dist2, pt0, pt1) = tf.neighbor_search(mesh0, mesh1)

# Form vs form within radius
result = tf.neighbor_search(mesh0, mesh1, radius=1.0)
if result is not None:
    (id0, id1), (dist2, pt0, pt1) = result

kNN Queries

For k nearest neighbors, pass k parameter:

# Find 10 nearest neighbors
neighbors = tf.neighbor_search(mesh, point, k=10)
for idx, dist2, pt in neighbors:
    # process neighbor (sorted by distance)
    pass

# With radius limit (may find fewer than k)
neighbors = tf.neighbor_search(mesh, point, k=10, radius=5.0)

Ray Casting

Extends ray casting to forms. Returns (element_id, t) or None.

config = (0.0, 100.0)  # (min_t, max_t)

result = tf.ray_cast(ray, mesh, config)
if result is not None:
    face_id, t = result
    hit_point = ray.origin + t * ray.direction

Gathering Primitive IDs

gather_ids collects primitive IDs matching spatial criteria.

Gather Intersecting IDs

Supported primitives: Point, Segment, Line, Ray, Polygon, Plane

# Form vs primitive - returns array of element IDs
ids = tf.gather_intersecting_ids(mesh, polygon)

# Form vs form - returns Nx2 array of ID pairs
pairs = tf.gather_intersecting_ids(mesh0, mesh1)
for id0, id1 in pairs:
    # process intersecting pair
    pass

Gather IDs Within Distance

Supported primitives: Point, Segment, Line, Ray, Polygon, Plane

# Form vs primitive - returns array of element IDs within distance
ids = tf.gather_ids_within_distance(mesh, point, distance=0.5)

# Form vs form - returns Nx2 array of ID pairs
pairs = tf.gather_ids_within_distance(mesh0, mesh1, distance=0.5)

Distance Fields

Compute vectorized distances from many points to a primitive:

# Distance from points to a polygon
query_points = np.random.rand(1000, 3).astype(np.float32)
polygon = tf.Polygon([[0, 0, 0], [1, 0, 0], [0.5, 1, 0]])
distances = tf.distance_field(query_points, polygon)
# Returns array of shape (1000,) with unsigned distances

# Signed distance to a plane (negative inside, positive outside)
plane = tf.Plane(normal=[0, 0, 1], origin=[0, 0, 5])
signed_distances = tf.distance_field(query_points, plane)

# Works with PointCloud input too
cloud = tf.PointCloud(query_points)
distances = tf.distance_field(cloud, plane)

All spatial queries leverage spatial acceleration structures for efficient computation on large datasets. For implementation details, see the C++ Spatial documentation.

Core

Core data structures, primitives, and basic geometric queries.

Topology

Connectivity analysis and component labeling.