This CGAL python binding example is great to show how to get the closest point on a triangle soup using an AABB tree. Unfortunately it only returns the single closest point on the closest triangle.
I'm looking for a function where i can feed a query point(s), an array of triangles, and then get a closest point per triangles as a return.
The only way i found to do this is by iterating over the triangles one at a time, make an AABB_tree_Triangle_3_soup for each, and query... This feels very inefficient, especially since the example clearly can deal with the array of triangles at once.
To help illustrate, here's an image of what i'm looking for:
The red dot is the query point, each blue dot are the triangle's vertices, the green dots are the closest points with each line as it's projection.
Here's the code i came up with so far. The code works, but isn't very pretty.
# Imports
import time
import numpy as np
from scipy.spatial import cKDTree
from CGAL.CGAL_Kernel import Point_3
from CGAL.CGAL_Kernel import Triangle_3
from CGAL.CGAL_AABB_tree import AABB_tree_Triangle_3_soup
# Setup the source data
# ---------------------
# Create large numpy array of triangles
N_TRIANGLES = 100000 #100K triangles
np_triangles = np.random.random_sample((N_TRIANGLES,3,3,)) # lets make a random array for this example
# Create a random query point
np_query = np.random.random_sample((3,)) * 100 # lets use a random point for this example
# Convert the data so we can use CGAL
cgal_triangles = []
for p in np_triangles:
a = Point_3(p[0][0],p[0][1],p[0][2])
b = Point_3(p[1][0],p[1][1],p[1][2])
c = Point_3(p[2][0],p[2][1],p[2][2])
cgal_triangles.append(Triangle_3(a,b,c))
cgal_query = Point_3(np_query[0],np_query[1],np_query[2])
# Test begins!
# ------------
# If all i care for is to find THE closest point on all the given triangles to the query point, it's easy:
def simple_closest():
tree = AABB_tree_Triangle_3_soup(cgal_triangles)
cp = tree.closest_point(cgal_query)
return np.array([cp.x(),cp.y(),cp.z()])
simple_closest_result = simple_closest()
# Unfortunately, what i want is a return value for all given triangles, which i could sort in the future for N closest if need be
# The only way i found to do this is to make an AABB tree per triangle, which sounds silly, and is the focus of my question
def all_closest():
cp = []
for t in cgal_triangles:
tree = AABB_tree_Triangle_3_soup([t])
p = tree.closest_point(cgal_query)
cp.append([p.x(),p.y(),p.z()])
return np.array(cp)
all_closest_result = all_closest()
# From here, if i wish to sort the results to get all the points from closest to furthest, i can do that
N = 8 # Lets say i want the 8 closest triangles to the query point
n = max(min(N, N_TRIANGLES), 1) # clamp n <= tri count
def n_closest():
kdTree = cKDTree(all_closest_result)
q = kdTree.query(np_query,k=n)
return all_closest_result[q[1]], q[0], q[1]
n_closest_result = n_closest()
print ''
print 'Does the closest item match: %s'%np.allclose(n_closest_result[0][0],simple_closest_result)
print 'Closest Simple:\n%s'%simple_closest_result
print '%s closest'%n
print n_closest_result[0]
This example shows how i had to iterate over the triangles one at a time. Create an AABB_tree_Triangle_3_soup for each single triangles, and then query. This sounds highly inefficient. Especially when dealing with many many queries, like 100k queries of a list of a million triangles.
So, what i'm looking for is a better way than my iteration method. Hopefully a single command... like:
tree = AABB_tree_Triangle_3_soup(triangles) tree.all_points(query) # returns unsorted closest points tree.all_closest(query,n=56) # returns the 56 closest points
