 # Ordering Point and Triangles for SSM Landmarking

Recently, while working on a project that required SSM landmarking, I discovered that each time a new instance is created from an SSM, the points and triangles are relabeled. This causes the correspondence point relationship to breakdown. Danielle at Materialise provided me with a script that Julian wrote to order the points and triangles. I made some significant speed improvements and wanted to share both scripts here.

Julian’s script:

``````#Alternative version of the function trimatic.get_triangles where points keep the same order based on the triangles (instead of being sorted according to their Z coordinate as is standard in 3-matic)
#Returns: exacty like trimatic.get_triangles: List with list of points and list of triangles defined by indices in the point list.
#Author: Julien Deckx, Materialise

import numpy as np

def get_triangles_ordered(part, return_triangles = False, keep_free_points = True):
#get original triangles and points
points, triangles = part.get_triangles()
triangles = np.array(triangles)
points = np.array(points)

#get a list of unique point indices from the triangles
triangles_flat = np.ndarray.flatten(triangles)
unique_index_indices = np.unique(triangles_flat, return_index=True)
unique_indices = triangles_flat[np.sort(unique_index_indices)]

#re-order the points according to the unique point indices
points_ordered = points[unique_indices]

#points that are not part of triangles are free points and are added at the bottom of the list
if keep_free_points:
free_point_indices = list(set(range(len(points)))^set(triangles_flat))
np.append(points_ordered, points[free_point_indices], axis=0)

#adapt indices in triangles based on new order. This optional because it's very slow for some reason.
if return_triangles:
triangles_flat_ordered = np.array([list(unique_indices).index(triangles_flat[i]) for i in range(len(triangles_flat))])
triangles_ordered = triangles_flat_ordered.reshape((int(len(triangles_flat_ordered)/3),3))

#convert back to tuple and ints
triangles_ordered = tuple([tuple(map(int, triangles_ordered[i])) for i in range(len(triangles_ordered))])
else:
triangles_ordered = []

#convert back to tuple
points_ordered = tuple(map(tuple, points_ordered))

return points_ordered, triangles_ordered
``````

My optimized script:

``````"""
Alternative version of the function trimatic.get_triangles where points keep the same order based on                the triangles (instead of being sorted according to their Z coordinate as is standard in 3-matic)
Returns: exacty like trimatic.get_triangles: List with list of points and list of triangles defined by indices in the point list.
Author: Julien Deckx, Materialise

Modifed by Nathan Pyle, DJO Surgical. @EntPyle on Materialise Scripting Forum and Github

Changed triangles ordering algorithm for significant speed increase.
Removed option to not calculate new triangle mesh. Not needed with new speed
Added output_tuple as an option so the numpy array is preserved by default.
"""
import numpy as np

def get_triangles_ordered(part, keep_free_points = True, output_tuple=False):
#get original triangles and points
points, triangles = part.get_triangles()
# fastest method is to use pd._lib.to_object_array() instead of np.array
# def make_array_from_tuplelist(tuple_list):
#     return pd._lib.to_object_array(tuple_list).astype(np.float64)
triangles = np.array(triangles)
points = np.array(points)

#get a list of unique point indices from the triangles
triangles_flat = np.ndarray.flatten(triangles)
unique_index_indices = np.unique(triangles_flat, return_index=True)
unique_indices = triangles_flat[np.sort(unique_index_indices)].astype(np.int)  # unique point ids sorted by triangle id

#re-order the points according to the unique point indices
points_ordered = points[unique_indices]  # point coordinates sorted by triangle id

#points that are not part of triangles are free points and are added at the bottom of the list
if keep_free_points:
free_point_indices = list(set(range(len(points)))^set(triangles_flat))
np.append(points_ordered, points[free_point_indices], axis=0)

#adapt indices in triangles based on new order.
map_dict = {value: pos for pos, value in enumerate(unique_indices)}
triangles_ordered = np.vectorize(map_dict.get)(triangles_flat).reshape(triangles.shape)
# Todo triangles_ordered should never change. Compare ssm triangles against these instances as a test

#convert back to tuple
if output_tuple:
points_ordered = tuple(points_ordered.tolist())
triangles_ordered = tuple(triangles_ordered.tolist())

return points_ordered, triangles_ordered``````

Hi Nathan,

Thanks for sharing! I’m glad you could fix the performance issue.

Best regards,

Julien