Find the nearest edge

Run RayD's nearest-edge example on a unit square, read the edge records, query the k nearest edges, and differentiate the edge distance.

This tutorial walks through the nearest-edge example that ships with RayD (examples/drjit/basics/nearest_edge_query.py), then extends it with a top-k query and a gradient. You will learn how a mesh's edges are counted, what a nearest-edge result contains, and how the distance responds to the query point.

Run the example#

The scene is the unit square from (0, 0) to (1, 1) at z = 0, split into two triangles along the diagonal. Four query points sit near different edges.

import rayd.drjit as rd
import drjit as dr
 
 
def make_scene() -> tuple[rd.Scene, rd.Mesh]:
    mesh = rd.Mesh(
        dr.cuda.Array3f([0.0, 1.0, 1.0, 0.0], [0.0, 0.0, 1.0, 1.0], [0.0, 0.0, 0.0, 0.0]),
        dr.cuda.Array3i([0, 0], [1, 2], [2, 3]),
    )
    mesh.build()
 
    scene = rd.Scene()
    scene.add_mesh(mesh)
    scene.build()
    return scene, mesh
 
 
def main() -> None:
    scene, mesh = make_scene()
 
    secondary_edges = mesh.secondary_edges()
    boundary_count = sum(bool(v) for v in list(secondary_edges.is_boundary))
 
    queries = dr.cuda.Array3f([0.25, 1.20, -0.15, 0.50], [0.25, 0.50, 0.70, 1.20], [0.10, 0.00, 0.00, 0.00])
    result = scene.nearest_edge(queries)
 
    print("Nearest-edge query example")
    print("secondary_edge_count =", secondary_edges.size())
    print("boundary_edge_count =", boundary_count)
 
    for i, valid in enumerate(list(result.is_valid())):
        if valid:
            edge_point = [float(result.edge_point[axis][i]) for axis in range(3)]
            print(
                f"query[{i}] valid: distance={float(result.distance[i]):.4f}, "
                f"shape_id={int(result.shape_id[i])}, edge_id={int(result.edge_id[i])}, "
                f"boundary={bool(result.is_boundary[i])}, edge_point={edge_point}"
            )
        else:
            print(f"query[{i}] invalid")
 
 
if __name__ == "__main__":
    main()

Output with RayD 0.8.0:

Nearest-edge query example
secondary_edge_count = 5
boundary_edge_count = 4
query[0] valid: distance=0.1000, shape_id=0, edge_id=1, boundary=False, edge_point=[0.25, 0.25, 0.0]
query[1] valid: distance=0.2000, shape_id=0, edge_id=3, boundary=True, edge_point=[1.0, 0.5, 0.0]
query[2] valid: distance=0.1500, shape_id=0, edge_id=2, boundary=True, edge_point=[0.0, 0.699999988079071, 0.0]
query[3] valid: distance=0.2000, shape_id=0, edge_id=4, boundary=True, edge_point=[0.5, 1.0, 0.0]

Read the result#

  1. Count the edges

    mesh.build() extracts the mesh's unique edges. secondary_edges() returns them: four border edges, which have one adjacent face (is_boundary true), and the shared diagonal.

  2. Query 0 is above the diagonal

    The point (0.25, 0.25, 0.1) lies 0.1 above the diagonal from (0, 0) to (1, 1). The closest point on the edge, edge_point, is directly below it. The diagonal is interior, so boundary=False.

  3. Queries 1 to 3 are outside the square

    Each point lies beside one border edge, and the distance is its offset from that edge. edge_point is the projection onto the edge.

edge_id is the edge's index within its mesh. With one mesh it equals global_edge_id. With several meshes, use global_edge_id to index the scene's edge list, for example in set_edge_mask.

Get the k nearest edges#

Add these lines at the end of main() to get the two nearest edges for each query:

top = scene.nearest_edges(queries, 2)
print("distances", top.distances)
print("global ids", top.global_edge_ids)
distances [0.1, 0.269258, 0.2, 0.494975, 0.15, 0.33541, 0.2, 0.494975]
global ids [1, 0, 3, 1, 2, 4, 4, 1]

The result is flat, two entries per query, nearest first: query 0 is 0.1 from edge 1 and 0.269 from edge 0.

Differentiate the distance#

Edge distances are differentiable. Pass AD points to get a NearestPointEdgeAD, and back-propagate:

import drjit.cuda.ad as ad
 
p = ad.Array3f([0.25, 1.20], [0.25, 0.50], [0.10, 0.00])
dr.enable_grad(p)
ne = scene.nearest_edge(p)
dr.backward(dr.sum(ne.distance))
print(dr.grad(p))
[[0, 0, 1],
 [1, 0, 0]]

The gradient of each distance is the unit vector from the closest edge point to the query: straight up for query 0, along +x for query 1, which sits to the right of the x = 1 border.

Next steps#