Calculation of Hausdorff Distance between meshes in Blender

Support Materials and Textures
1

Hi everyone,

So, a bit of a disclaimer, this is my first post here and I don’t know too much about Blender. I am familiar with some basic things, but not too much in regards to coding. Apologies if I am posting this in the wrong section. Feel free to point me to the right place if I erred.

So, I am currently researching neuronal ultrastructure in the brain, and have obtained a stack of images from doing serial-section SEM on a tissue sample. We have loaded them all up for use in FIJI as a large image stack. Long story short, we intend to use FIJI’s TrakEM2 plugin to segment (so, “color in”, across the different layers, so to speak) various structures using AreaLists. Then, we want to create 3D models of these structures (not the entire image stack; just the colored-in structures of interest), and make them easily understandable/viewable in Blender by adjusting size, transparency, smoothing vertices, etc…

We have made significant progress and now have several glial cells (Astrocytes) as segmented area lists with their 3D reconstructions, and we are interested in looking at, for example, the distance between an astrocyte’s mitochondria (a structure inside the cell) and a post-synaptic density (a cluster of proteins at most synapses, a structure outside the astrocyte in question). As the mitochondria can be quite complex, we believe that using Hausdorff Distance to calculate the greatest distance of a post synaptic density’s point to the nearest point on a mitochondria (without getting into the mathematical complexity of Hausdorff Distance) should be the most informative for our calculations. We have already imported many cells and structures from TrakEM2 into Blender with much success, so that in itself isn’t much of an issue.

For reference, here is a simple and informative explanation on Hausdorff Distance: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html

That being said, none of us here have sufficient programming experience to program the distance-calculating functionality, and so we were wondering if anyone here could point us in the right direction, or even tell us if such a thing is possible in Blender.

Thank you so much in advance! I’d be glad to answer any questions that will help solve this problem. :slight_smile:

-Mikey

2

suggest to move this in python forum!

should be possible to write a script addon to do it

got to find the exact algo to write it down then should be easy to use python algo

but how many verts are we talking here?

also are the verts and polygons in same plane or in 3D ?

only problem I have is with this condition

“presumed to be enumerated counterclockwise”

in 3D that might not be possible !
depends on number of faces and location

for very large amount might be faster to do it in numpy or even in C!

tanks
happy bl

3

Hi,

that’s really just a wild guess, but you might want to ask that same questions on the Houdini forums. Houdini has a set of tools for walking geometry that just might be suited for calculating that Hausdorff distance, whatever it is. :slight_smile: Since it has a nodal interface, it’s usually more approachable for people with little coding experience, while leading to the same results.

After reading through the link on Hausdorff distance, it doesn’t seem too difficult to code it, at least the brute force approach (should be better to use sorting especially if your sets are big).

4

Is this what you’re asking in a nutshell? I have two separate mesh objects in blender and I want to calculate the shortest distance between points on both objects?

If so it’s not that difficult, a few lines of python. Of course it kind of depends on how many surface points you want to test per triangle. If you’re looking to test 1000s per triangle and your mesh has 1000s/millions of tris it could take awhile.

5

It’s actually “the maximum distance of a set to the nearest point in the other set” so in essence : the longest of all shortest distances between each point in a set and any other point in the other set.
…if I understand correctly.

6

why don’t you read the algo on given link

and verts must be in CCW
which is not that simple !

happy bl

7

Oh I see, so you’re looking for something like pseudo code:

  1. Pick a random point a on A
  2. Find the shortest distance between a and another point b on B
  3. if distanceab > maxdistance:
    maxdistance = distanceab
8

a bit more then that
need to consider points on edge too !

read the whole algo on given site

happy bl

9

I’m a novice coder, so i cant be of any help here…

But maybe the python code here could help you on your way? - http://stackoverflow.com/questions/30706079/hausdorff-distance-between-3d-grids

(Scroll down to the edited answer)