Fast mesh-mesh intersection using ray-tri intersection with octree spatial partitioning.

Fast mesh-mesh intersection based on ray-tri solution. Octree partitioning gives large speed-up.

% Putative points of intersection between each pair of surfaces are located
% by assuming that each constituent mesh triangle edge represents an
% infinitesimal ray, then solving the ray-triangle intersection problem
% using the Barycentric coordinate based solution presented by Möller and
% Trumbore [1997: vectorized implementation for speed]. Positive
% intersections occur when the intersecting point, p0 lies between the end
% nodes of its corresponding triangle edge (p1, p2), identified when the
% following criterion is satisfied:
% ‖p0 - p1‖ + ‖p0 - p2‖ = ‖p1 - p2‖
% Note: rounding errors do not permit solving of the above criteria
% directly. Dot and cross functions are instead used for constraining
% whether the point is between the triangle edge end nodes.
% Ray tracing becomes prohibitive for meshes greater than a few thousand
% triangles. The reliance on spatial partitioning using octree subdivision
% carries overhead in binning the two input meshes, but is still usually
% MUCH faster than a brute force search for most mesh objects.
% INPUT:
% pointsA: nx3 vertex list for mesh A
% pointsB: nx3 vertex list for mesh B
% facesA: nx3 face list of triangle corner indices for mesh A
% facesB: nx3 face list of triangle corner indices for mesh B
% octs: maximum bin size (single integer)
% OUTPUT
% intersections: nx3 vertex list of intersections between the two meshes
% Note: the octree object is created using the excellent octree.m function of Sven:
% http://www.mathworks.com/matlabcentral/fileexchange/40732-octree-partitioning-3d-points-into-spatial-
% subvolumes

% Test data (testData.mat) containing two meshed intersecting fractal surfaces is provided with the package