image thumbnail

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

version 1.5.0.0 (2.7 MB) by Thomas
Fast mesh-mesh intersection based on ray-tri solution. Octree partitioning gives large speed-up.

974 Downloads

Updated 16 Feb 2015

View License

% 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

Cite As

Thomas (2021). Fast mesh-mesh intersection using ray-tri intersection with octree spatial partitioning. (https://www.mathworks.com/matlabcentral/fileexchange/49160-fast-mesh-mesh-intersection-using-ray-tri-intersection-with-octree-spatial-partitioning), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2013a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!