Spatial Module

spatial

DEPRECATED!!!! This module provides a kD-tree implementation but specialized to 3D. The reason why it is deprecated is that scipy.spatial contains a very flexible KDTree class that is much more generic and obviates the need for GEL's KDTree. Going forward, the KDTree may be removed from PyGEL but not from the C++ GEL API.

I3DTree

kD tree specialized for 3D keys and integer values. This tree data structure is useful for storing 3D points and associated integer values - typically indices. There is also a more general kd tree in scipy.spatial if this one does not suit your needs.

Source code in pygel3d/spatial.py

class I3DTree:
    """ kD tree specialized for 3D keys and integer values.
    This tree data structure is useful for storing 3D points and
    associated integer values - typically indices. There is also
    a more general kd tree in scipy.spatial if this one does not
    suit your needs. """
    def __init__(self):
        self.obj = lib_py_gel.I3DTree_new()
    def __del__(self):
        lib_py_gel.I3DTree_delete(self.obj)
    def insert(self,p: ArrayLike, v: int):
        """ Insert v at 3D point given by p. Insert should be called before
        calling build. """
        lib_py_gel.I3DTree_insert(self.obj, p[0],p[1],p[2],v)
    def build(self):
        """ Build the tree. This function call makes the tree searchable. It is
        assumed that all calls to insert come before calling this function."""
        lib_py_gel.I3DTree_build(self.obj)
    def closest_point(self, p: ArrayLike, r: float) -> tuple[list[float], int]|None:
        """ Search for point closest to p within a max radius r.
        This function should only be called after build. """
        key = (ct.c_double * 3)()
        val = ct.c_size_t()
        n = lib_py_gel.I3DTree_closest_point(self.obj, p[0],p[1],p[2],r,ct.byref(key),ct.byref(val))
        if n==1:
            return ([key[0],key[1],key[2]],val.value)
        return None
    def in_sphere(self, p: ArrayLike, r: float) -> tuple[Vec3dVector, IntVector]:
        """ Retrieve all points within a radius r of p.
        This function should only be called after build. """
        keys = Vec3dVector()
        vals = IntVector()
        n = lib_py_gel.I3DTree_in_sphere(self.obj, p[0],p[1],p[2],r,keys.obj,vals.obj)
        return (keys,vals)

insert

insert(p: ArrayLike, v: int)

Insert v at 3D point given by p. Insert should be called before calling build.

Source code in pygel3d/spatial.py

def insert(self,p: ArrayLike, v: int):
    """ Insert v at 3D point given by p. Insert should be called before
    calling build. """
    lib_py_gel.I3DTree_insert(self.obj, p[0],p[1],p[2],v)

build

build()

Build the tree. This function call makes the tree searchable. It is assumed that all calls to insert come before calling this function.

Source code in pygel3d/spatial.py

def build(self):
    """ Build the tree. This function call makes the tree searchable. It is
    assumed that all calls to insert come before calling this function."""
    lib_py_gel.I3DTree_build(self.obj)

closest_point

closest_point(p: ArrayLike, r: float) -> tuple[list[float], int] | None

Search for point closest to p within a max radius r. This function should only be called after build.

Source code in pygel3d/spatial.py

def closest_point(self, p: ArrayLike, r: float) -> tuple[list[float], int]|None:
    """ Search for point closest to p within a max radius r.
    This function should only be called after build. """
    key = (ct.c_double * 3)()
    val = ct.c_size_t()
    n = lib_py_gel.I3DTree_closest_point(self.obj, p[0],p[1],p[2],r,ct.byref(key),ct.byref(val))
    if n==1:
        return ([key[0],key[1],key[2]],val.value)
    return None

in_sphere

in_sphere(p: ArrayLike, r: float) -> tuple[Vec3dVector, IntVector]

Retrieve all points within a radius r of p. This function should only be called after build.

Source code in pygel3d/spatial.py

def in_sphere(self, p: ArrayLike, r: float) -> tuple[Vec3dVector, IntVector]:
    """ Retrieve all points within a radius r of p.
    This function should only be called after build. """
    keys = Vec3dVector()
    vals = IntVector()
    n = lib_py_gel.I3DTree_in_sphere(self.obj, p[0],p[1],p[2],r,keys.obj,vals.obj)
    return (keys,vals)

The spatial module provides spatial data structures for efficient geometric queries.

I3DTree Class

The I3DTree class is a kD-tree specialized for mapping 3D points to integers (typically array indices).

Creating a Tree

from pygel3d import I3DTree
import numpy as np

# Create tree
tree = I3DTree()

# Insert points with associated indices
points = np.random.rand(1000, 3)
for i, point in enumerate(points):
    tree.insert(point, i)

Tree Operations

Insertion

• tree.insert(point, value) - Insert a point with an associated integer value

Queries

• tree.closest_point(query_point) - Find nearest point, returns associated value
• tree.in_sphere(center, radius) - Find all points within radius

Information

• tree.size() - Number of points in tree

MeshDistance Class

The MeshDistance class enables efficient distance computations to triangle meshes.

Creating a Distance Object

from pygel3d import MeshDistance
import pygel3d.hmesh as hmesh

# Load mesh
m = hmesh.load("model.obj")

# Create distance object
dist = MeshDistance(m)

Distance Queries

Point Queries

• dist.signed_distance(point) - Signed distance to mesh (negative inside)
• dist.distance(point) - Unsigned distance to mesh
• dist.ray_inside_test(point, direction) - Test if ray from point hits mesh

Information

• Returns scalar distance values
• Signed distance uses mesh orientation (closed meshes only)

Example Usage

k-Nearest Neighbors

from pygel3d import I3DTree
import numpy as np

# Generate random points
points = np.random.rand(1000, 3) * 10

# Build tree
tree = I3DTree()
for i, p in enumerate(points):
    tree.insert(p, i)

# Find nearest point to query
query = [5.0, 5.0, 5.0]
nearest_idx = tree.closest_point(query)
nearest_point = points[nearest_idx]

print(f"Nearest point to {query}: {nearest_point}")
print(f"Index: {nearest_idx}")

Points in Sphere

from pygel3d import I3DTree
import numpy as np

# Build tree
tree = I3DTree()
points = np.random.rand(1000, 3) * 10
for i, p in enumerate(points):
    tree.insert(p, i)

# Find all points within radius
center = [5.0, 5.0, 5.0]
radius = 2.0
indices = tree.in_sphere(center, radius)

print(f"Found {len(indices)} points within radius {radius}")

Distance Field Computation

from pygel3d import MeshDistance
import pygel3d.hmesh as hmesh
import numpy as np

# Load mesh
m = hmesh.load("bunny.obj")

# Create distance object
dist = MeshDistance(m)

# Create grid
grid_size = 50
x = np.linspace(-1, 1, grid_size)
y = np.linspace(-1, 1, grid_size)
z = np.linspace(-1, 1, grid_size)

# Compute distance field
distances = np.zeros((grid_size, grid_size, grid_size))
for i, xi in enumerate(x):
    for j, yj in enumerate(y):
        for k, zk in enumerate(z):
            point = [xi, yj, zk]
            distances[i, j, k] = dist.signed_distance(point)

print(f"Distance field shape: {distances.shape}")
print(f"Min distance: {distances.min()}")
print(f"Max distance: {distances.max()}")

Inside/Outside Testing

from pygel3d import MeshDistance
import pygel3d.hmesh as hmesh

# Load closed mesh
m = hmesh.load("sphere.obj")
dist = MeshDistance(m)

# Test points
test_points = [
    [0, 0, 0],      # Inside
    [10, 10, 10],   # Outside
    [0.5, 0.5, 0.5] # Near surface
]

for point in test_points:
    d = dist.signed_distance(point)
    status = "inside" if d < 0 else "outside"
    print(f"Point {point}: {status} (distance: {abs(d):.4f})")

Performance Tips

• Tree Construction: Build the tree once and reuse for multiple queries
• Batch Queries: Use vectorized operations when possible
• Mesh Simplification: For distance queries, simpler meshes are faster
• Precision: Consider using lower precision for large-scale computations