Mesh (self)intersection algorithm?

Archive Blender Development
#1

Dear all,

I have been trying to search the forum, search the internet, read the code, and read the documentation to determine what algorithm Blender uses for calculating the (self)intersection of selected mesh components in an object. In the Python API I am using bpy.ops.mesh.intersect.

This is a very useful features for, e.g., calculating the CNC cutting or welding curve for tubular structures. I have not found anything that can clarify this for me, so my next step is to dig into the code and understand it. Could someone provide me some pointers into the code or, even better, to some documentation about the implemented algorithm? I would be very grateful for any help here.

#2

You can find the C code in the function edbm_intersect_exec in blender/source/blender/editors/mesh/editmesh_intersect.c :slight_smile:

1 Like
#3

@s.barbieri I suppose the actual, functional code is in the function BM_mesh_intersect, which starts at https://developer.blender.org/diffusion/B/browse/master/source/blender/bmesh/tools/bmesh_intersect.c;45c11c1a1bd07cca255abdb1923e69f0242c36fd$984

But this is quite hard for me to read. Do you know who wrote the code, or do you know if the implemented algorithm is described in some particular book or paper? I accept that I may have to read and understand the code. It would just save a h… of a lot of time knowing the principle first :slight_smile:

#4

Mostly written by Campbell Barton

1 Like
#5

@Samir_Osman Great. I will try getting in touch with him.

#6

Campbell Barton (@ideasman42) could you be helpful with telling me what algorithm is used in your implementation for calculating the mesh intersection? From inspecting the code, it seems that the non-BVH-Tree algorithm is the full tri-tri calculation, as in [1]. Is that so? In case of the use of the BVH-Tree, do you have some reference to the algorithm?

[1] S. H. Lo. Automatic mesh generation over intersecting
surfaces. International Journal for Numerical Methods
in Engineering, 38(6):943–954, 1995. ISSN 1097-0207.
doi: 10.1002/nme.1620380605.