Distance calculations and neighborhood analysis are essential tools for understanding the shape, structure, and features of meshes and point clouds. This article will use three of the most widely used Python 3D data analysis libraries – Open3D, PyVista, and Vedo to extract distance-based information, visualize it, and show example use cases. As always all code, together with used mesh and point cloud data are provided. Who said that neighborhood analysis for 3D objects should be hard?

Compared to depth maps or voxels, point clouds and meshes represent unstructured data in 3D space. Points are represented by their (X, Y, Z) coordinates and two points that might be close to each other in 3D space can be far away in the array representation. The distance between points is also not equal, meaning that some of them can be closely clumped together or far away from each other. This leads to the fact that understanding the neighborhood of a certain point is not a trivial task, compared to the same problem in images for example.
Distance calculation between points is a vital part of point cloud and mesh analysis, noise detection and removal, local smoothing, and smart decimation models, among others. Distance calculations are also an integral part of 3D deep learning models, both for data pre-processing, as well as part of the training pipeline [7]. Furthermore, classical point cloud geometrical features, rely on neighborhood calculation and PCA analysis of closest points [2, 8].


Especially for very large point clouds and complex meshes, the calculation of distances between all points can become very resource-intensive and costly, if done in a brute force way. The libraries that we will be focusing on in this article use different implementations of KD-trees or Octrees, to partition the 3D space of an object into more manageable and structured quadrants. This way this partitioning can be done once and all subsequent distance queries can be sped up and simplified. As going in-depth into KD-trees and Octrees is beyond the scope of this article, I will highly recommend you watch these YouTube videos before diving into the presented examples – Multidimensional Data KdTree, Quadtrees, and Octrees for Representing Spatial Information, and especially K-d Trees – Computerphile

In this article, we will also briefly touch upon the calculation of the geodesic distance between points in a point cloud. This distance is the shortest path between two points in a connected graph structure, where we count the number of edges that are present between the points. These distances can be used to capture information about the shape and point composition of 3D objects, as well as when working with graph representations of 3D surfaces.
In this article, we will take a closer look at three Python libraries – Open3D, PyVista, and Vedo and their capabilities to generate neighborhood and adjacency analysis of 3D meshes and point clouds. These three libraries have been selected as they provide straightforward to use distance calculation functionality, which can be easily implemented in deep learning and processing pipelines. The libraries are also fully featured and provide methods for analysis and manipulation of both meshes and point clouds. We will be also using the KD-tree implementation provided by SciPy, as it is highly optimized and parallelized, making it useful in the processing of large-scale 3D objects. For installation instructions for the three libraries and examples of how to build interactive visualizations with them, you can look at my previous articles on python libraries below.
Python Libraries for Mesh, Point Cloud, and Data Visualization (Part 1)
To demonstrate the voxelization on both point clouds and meshes, I use two objects. First, a duck statue point cloud in .ply format, which contains the X, Y, and Z coordinates of each point, together with their R, G, and B colors, and finally the Nx, Ny, and Nz normals. The duck statue was created using Structure from Motion photogrammetry and is free to use in commercial, non-commercial, public, and private projects. This object is part of a larger dataset [1] and has been used in the development of methods for noise detection and inspection [2], as well as scale computation [3]. Second, the famous Stanford bunny object in a .ply format is used, as it can be easily obtained and is widely used in mesh analysis research. The bunny can be freely used for non-commercial applications and research, after citing the appropriate given citations [4].
To follow the tutorials, in addition to the used libraries and their dependencies, you will also need NumPy and SciPy. All the code is available at the GitHub repository HERE.
Neighborhood Calculation using Open3D

Open3D is considered the standard for a Python library for 3D visualization, as it contains methods for point cloud, mesh, depth map, and graph analysis and visualization. It can be easily set up and run on Linux, Mac, and Windows, it contains a full branch dedicated to deep learning called Open3D-ML and has built-in methods for 3D reconstruction.
Open3D contains ready-made methods for building an Octree directly from a point cloud or a voxel grid. An Octree is first initialized using open3d.geometry.Octree(max_depth=maximum_depth_of_the_structure)
and then the method name_of_octree.convert_from_pointcloud(name_of_point_cloud)
to generate the octree directly from the point cloud. The method implicitly inherits the color information of the point cloud. Octrees of different depths are shown below, together with the simple code.



Once the Octree is generated it can then be traversed using traverse
and a function that will be processed for each node, together with a possibility for an early stop in case the required information is found. In addition, Octrees have functions for:
- locating to which leaf node a point belongs –
locate_leaf_node()
- inserting new points to specific node –
insert_point()
- finding the root node of the tree –
root_node
Open3D also contains methods for distance calculation based on KD-trees build using FLANN [5], which can also be found with different bindings HERE. A KD-tree is first generated from a point cloud or mesh using the function open3d.geometry.KDTreeFlann(name_of_3d_object)
. Then the tree can be used to search for a number of use cases. First, if the K-nearest neighbors of a specific point are needed the function search_knn_vector_3d
can be called together with the number of neighbors to find. Second, if the neighbors around a point in a specific radius are required the function search_radius_vector_3d
can be called together with the size of the radius to search in. Finally, if we need to limit the number of closest neighbors that are also inside a specific radius, the function search_hybrid_vector_3d
can be called, which combines the criteria of the previous two functions. These functions have also a higher dimensional variant for searching the neighbors for dimensionality above 3 using for example search_knn_vector_xd()
, where the dimension needs to be set manually as an input. The KD-tree itself is precomputed in one go, but the search queries are done for a single point at a time.
To visualize the process of finding the neighbors for the points in a point cloud we will use LineSet()
structure, which takes several nodes and edges and constructs a graph structure. To do this we first load the duck statue point cloud as an Open3D point cloud and subsample it for easier visualization. We use the voxel_down_sample()
built-in function for this. We then calculate the KD-tree of the downsampled point cloud. To better visualize how the distances are calculated we first initialize the visualizer object, change the background to black, and plot only the point cloud. Finally, we register an animation callback function using register_animation_callback()
. This initial setup is shown in the code below.
Once the initial setup is done, the callback function can be called for each update cycle and generate the neighborhood for each point. The function search_knn_vector_3d
is called for each point in the point cloud with the number of k-nearest neighbors needed. The function returns the number of points, the indices of the points, and the points themselves. For generating the line segments were take the found neighbor points, together with an edge array going from the center point to each of the neighbors. As we know that there are only k found neighbors we generate the edge array as the same stack of center and edge indices for each. The created LineSets are added to the main LineSet object and the geometry and renderer are updated. Once all points are traversed the LineSet is reset by calling clear()
. The code for the callback function is given below.
Now that we have seen how we can calculate KD-trees using the built-in functions in Open3D, we will expand this concept. We looked at how to use the distance between the coordinates of the 3D points, but we can also work on other spaces. The duck statue comes with calculated normals and colors per point in the point cloud. We can use these features to build KD-trees the same way and explore the relationships between points in these feature spaces. In addition to building the KD-trees for these features, we will use the functions that come pre-built in SciPy, just to explore alternative ways to generate the data. Building KD-trees is done through the spatial
part of SciPy. To build them we can invoke scipy.spatial.KDTree(chosen_metric)
. Once we have the tree structure, then we can invoke the name_of_tree.query(array_points_to_query, k = number_of_neighbours)
. This is a difference from the Open3D implementation, where we can query the closest points of a single point at a time. This, of course, means that with the SciPy implementation we can use the highly optimized function to pre-compute all distances, which can be useful to speed up later computations. The output of the query function is two arrays – closest point distances and the indices of the closest points for each queried point in the format N x k, where N is the number of the queried points and k is the number of neighbors.
All other functionality is the same as in the previous example, but for a cleaner presentation, we separate each of these steps into a function:
- We downsample the point cloud
- We calculate the KD-tree and edges between the points
- We build a line set and output point cloud for visualization, and finally, create a visualizer object and show everything.
Finally, we can select to calculate the neighborhoods and visualize different feature spaces. Examples of these are shown below with showing the neighborhoods of the coordinates, normals, and colors visualized in coordinate, normal, and color space.


Neighborhood Calculation using PyVista
PyVista is a fully featured library for analysis, manipulation, and visualization of point clouds, meshes, and datasets. It is built on top of VTK and provides simple out-of-the-box functionalities. PyVista can be used to create interactive applications with multiple plots, screens, widgets, and animations. It can be used to generate 3D surfaces, analyze the structure of meshes, remove noise, and transform data.
PyVista contains many ready-made functions for grouping points and vertices, calculating neighborhoods, and finding the closest points. One of the simplest functionalities present in PyVista is using VTK’s connectivity filters to group points and extract connected cells based on distance and connectivity criteria like shared vertices, distances between normal directions, colors, etc. This connectivity can be calculated by calling name_of_3d_object.connectivity()
. This returns a scalar array containing the region id for each point. Additionally, if we add the largest=True
to the connectivity function call, we can directly get only the largest connected region. We can combine these connectivity region ids, with the built-in interactive thresholding functionality in PyVista through add_mesh_threshold(3d_object_name)
, to be able to visualize and extract required regions. The code for this is given below.

In addition to this, PyVista also has a built-in neighborhood and closest point calculation functionality. This is done through the find_closest_point(point_to_query, n = number_of_neighbors)
function, where a single point can be given as input, together with the size of the neighborhood to return. The function returns the indices of the points that are in the neighborhood on the input. This function has the same limitation as to the Open3D one, where only one neighborhood of one point at a time can be calculated. In this needs to be done for a large number of points the SciPy implementation is faster and more optimized. This is also mentioned in the API reference in PyVista.
To demonstrate the find_closest_point
functionality and to give it more context in use cases for PyVista we will animate the rebuilding of the duck statue point cloud, one point neighborhood at a time. This can be used as a base to create decimation functions, neighborhood analysis functions, and many more. We will also package the whole thing neatly in a class so it can be easily called.

To generate the second point cloud and visualize the current point and its neighborhood we utilize the fact that PyVista keeps track of added objects to the plotter by their names. We plot everything as a callback function called on each update interaction. To get a better understanding of how animation callbacks and mesh updating work you can look at the Data Visualization and Voxelization of Meshes articles.

Finally, we can show how we can combine the neighborhood calculation using find_closest_point()
with the possibility of creating widgets and capturing mouse events. We will create an app that can detect the point that the user is clicked on a point cloud and calculate its neighbors. The number of neighbors found will be selected based on a slider widget.
Selecting points is done using the enable_point_picking()
. In this function, we need to give a callback, as well as set up the message that will be displayed on the screen using show_message
input and being able to directly do a left mouse button click using left_clicking=True
.
For setting up the slider widget we use the add_slider_widget
method and we set a callback function, as well as the minimum and maximum values of the slider and the event type. The only thing the callback will do is to get the new value of the slider and then if the point is selected call the function for calculating the closest_points and visualizing them.
Both of these functions are set as callbacks and a simple parameters class is made to keep track of all the shared variables.
Neighborhood and Distance Calculation using Vedo
Vedo is a powerful scientific visualization and analysis library for 3D objects. It has built-in functions for working with point clouds, meshes, and 3D volumes. It can be used to create physics simulations like 2D and 3D object movements, optics simulations, gas and liquid flow simulations, and kinematics among others. It contains a fully featured 2D and 3D plotting interface, with annotations, animations, and interactivity options. It can be used to visualize histograms, graphs, density plots, time series, etc. It is built on top of VTK, the same as PyVista, and can be used on Linux, Mac, and Windows. For more information on installing and configuring Vedo, you can look at my previous article Python Libraries for Mesh, Point Cloud, and Data Visualization (Part 1).
Vedo has out-of-the-box functionality for finding the either all the closest points in a given radius or the k-nearest neighbors, through the function closestPoint()
. It is called on a mesh or point cloud together with the point, whose neighbors need to be found and either a radius or a number of neighbors. Internally, the function calls the VTK vtkPointLocator
object, which is used to quickly locate a point in 3D space, by dividing the region of space around it into rectangular buckets and finding the points that fall in each bucket. The method is considered slower than KD-trees and Octrees, so for larger point clouds, the SciPy implementation is preferred.

To demonstrate how the neighborhood detection works in Vedo, we will create a simple example, in which a user clicks on a mesh to select a vertex and the neighborhood is calculated. We will extend this by showing how this can be used to calculate the average normal of the neighborhood and fit a circle to it. This simple example can be extended for fitting other primitives like spheres or planes and can be used to calculate local neighborhood features, smart denoising, decimation, and hole filling. For these examples, we will be using the Stanford bunny mesh.
We will fit a circle by using the function vedo.fitCircle(neighbourhood_points_array)
and then visualizing it by generating a circle with vedo.Circle()
and normal vector with vedo.Arrow()
. We implement the mouse click callback by calling plot_name.addCallback('LeftButtonPress', name_of_callback_function)
.
Here it needs to be mentioned that for the callback function we first check if there is an object selected using the event['actor']
and then if there is an object, get the selected point with event['picked3d']
. Every time we remove all the old actors representing the center point, neighboring points, circle, and arrow and build the new ones.
Another interesting distance metric that can be directly calculated from Vedo is the geodesic distance. The geodesic distance is the shortest distance or path between points that lay on a manifold or a curved surface of a 3D object. This closely resembles the straight line between points on a plane. The geodesic distance is a piecewise smooth curve that when integrated is the shortest path between given points. Geodesic distances are quite useful for calculating distances between points on a sphere or in spherical space, it is used for measuring the shortest distances between points on Earth. In a simpler perspective, if we compare the geodesic distance to Euclidean distance, geodesic takes into consideration the underlying shape of the surface on which the points are positioned, while Euclidean does not. In Vedo, there is a ready-made function called name_of_mesh.geodesic()
, which computes the distance between two given points on a mesh. The requirement is that the mesh is watertight and does not have any geometric imperfections. The function returns a path object comprised of all the edges between the two points. It uses Dijkstra’s algorithm to find the shortest path, with the implementation based on the one described in [6], as mentioned in VTK’s class description.

We will take advantage of this by creating an interactive geodesic path calculation example, where the user selects two points on a 3D mesh and the path between them is visualized. For this, we will again use the method addCallback('LeftButtonPress')
, together with a list to keep the selected points in, adding and removing them with each new click. The code for this is given below.
Conclusion
Distance and neighborhood calculations for meshes and point clouds can be an extremely powerful tool for analysis of their surfaces, detecting defects, noise, and areas of interest. Calculating local features based on neighborhoods is part of smart 3D object decimation, retopologizing, watermarking and smoothing. Calculating the K-nearest neighbors of each point is an important part of generating graphs from point clouds, voxelization, and surface building. Finally, many deep learning models working on 3D objects require the calculation of point neighborhoods and closest point distances. With this article, we have shown that calculating this information can be done quickly and easily in Python. We have also shown that interactive applications and animations based on distance calculations can be created in Python, without sacrificing usability. We also showed how to calculate KD-trees and Octrees in different depths.
Now that we know how to calculate point neighborhoods, the next step is to extract local features and surface information from them. In the next article, we will look at Python libraries used for feature extraction – both PCA based and geometric.
Python Libraries for Mesh, Point Cloud, and Data Visualization (Part 1)
Python Libraries for Mesh, Point Cloud, and Data Visualization (Part 2)
If you want to read more about extracting features from point clouds and meshes, you can look at some of my articles on 3D surface inspection [8, 9], noise detection [1], and point cloud segmentation [7]. You can find the articles, plus my other research on my Page, and if you see something interesting or just want to chat feel free to drop me a message. Stay tuned for more!
References
- Nikolov, I.; Madsen, C. (2020), "GGG – Rough or Noisy? Metrics for Noise Detection in SfM Reconstructions", Mendeley Data, V2; https://doi.org/10.17632/xtv5y29xvz.2
- Nikolov, I., & Madsen, C. (2020). Rough or Noisy? Metrics for Noise Estimation in SfM Reconstructions. Sensors, 20(19), 5725; https://doi.org/10.3390/s20195725
- Nikolov, I., & Madsen, C. B. (2020). Calculating absolute scale and scale uncertainty for SfM using distance sensor measurements: A lightweight and flexible approach. In Recent Advances in 3D Imaging, Modeling, and Reconstruction (pp. 168–192). IGI global; https://drive.google.com/file/d/10Te6fgmE6nC3t9zRZMYTJaaTEI36gskn/view
- Gardner, A., Tchou, C., Hawkins, T., & Debevec, P. (2003). Linear light source reflectometry. ACM Transactions on Graphics (TOG), 22(3), 749–758; https://dl.acm.org/doi/pdf/10.1145/882262.882342?casa_token=RNdulsy2dEQAAAAA:SXWQGGvMD_3OjN20XvnHK2uyvAKJMEhTBDu-_xWXqjnbNEiki72a41ij8q2Steyfhd8LQZTxvzsjMg
- Muja, M., & Lowe, D. G. (2009). Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP (1), 2(331–340), 2; https://lear.inrialpes.fr/~douze/enseignement/2014-2015/presentation_papers/muja_flann.pdf
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms second edition. The Knuth-Morris-Pratt Algorithm; https://mitpress.mit.edu/books/introduction-algorithms-second-edition
- Haurum, J. B., Allahham, M. M., Lynge, M. S., Henriksen, K. S., Nikolov, I. A., & Moeslund, T. B. (2021, February). Sewer Defect Classification using Synthetic Point Clouds. In VISIGRAPP (5: VISAPP) (pp. 891–900); https://www.scitepress.org/Papers/2021/102079/102079.pdf
- Nikolov, I. A., & Madsen, C. B. (2021). Quantifying Wind Turbine Blade Surface Roughness using Sandpaper Grit Sizes: An Initial Exploration. In 16th International Conference on Computer Vision Theory and Application (pp. 801–808). SCITEPRESS Digital Library; https://doi.org/10.5220/0010283908010808
- Nikolov, I. A., Kruse, E. K., Madsen, C. B., "How image capturing setups influence the quality of SfM reconstructions for wind turbine blade inspection," Proc. SPIE 11525, SPIE Future Sensing Technologies, 115251P (8 November 2020); https://doi.org/10.1117/12.2579974