用点测试法求出两个四面体的交点

Question

我是Matlab编程的新手。我使用EIDORS和Netgen创建了两个四面体网格模型。然后，我需要使用Matlab创建一个基于四面体元素之间的交集的地图。因此，为了找到交点，我尝试使用点测试方法。请参阅链接。http://steve.hollasch.net/cgindex/geometry/ptintet.html

让我们假设模型1和模型2。

首先，我从两个模型中提取顶点并创建矩阵。

然后，我使用点测试方法来计算模型之间的交集。

对于模型1，我有3000++四面体元素，而模型2，我有8000++四面体元素。

为了计算交集，我逐个循环以确定两个模型之间的哪个元素有交集，然后我通过将model2的元素编号索引到model1的元素编号来创建矩阵。

但是，对于少数元素似乎为零，这是不可能的，因为来自模型1的所有元素都应该至少与来自模型2的一些元素相交。

因此，最终我希望得到一个矩阵，它由（model1的元素数x model2的元素数组成，它与model1中的相应元素相交）。能帮我解决这个问题吗？请参阅我的代码。

function [elemno,deter0,deter1,deter2,deter3,deter4] = checkp(filename1,filename2);
%/* to check whether the vertices of a layered model''s element are inside the
% tetrahedron of the generic model
%after the model is created using netgen and eidors, there will be a struct    type 
%named model_parameters.
%model_parameters.vtx refers to the vertices which consists of (nodes x   vertices %(x,y,z))
%model_parameters.simp refers to the elements which consists (numberofelements x nodes) nodes are linked to the vertices.*/
filename1 = [filename1 '.mat'];
filename2 =[filename2 '.mat'];
first = load(filename1);
second =load(filename2);
vtx = first.model_parameters.vtx;
simp = first.model_parameters.simp;
[simpr,simpc] = size(simp);
vtx2 = second.model_parameters.vtx;
simp2= second.model_parameters.simp;
[simpr2,simpc2] = size(simp2);

%//extracting the vertices of the elements from the simplices(element)
for loop1 = 1 : simpr
    elemx(loop1,1) = vtx(simp(loop1,1),1);      
    elemx(loop1,2) = vtx(simp(loop1,2),1);
    elemx(loop1,3) = vtx(simp(loop1,3),1);
    elemx(loop1,4) = vtx(simp(loop1,4),1);
    elemy(loop1,1) = vtx(simp(loop1,1),2);
    elemy(loop1,2) = vtx(simp(loop1,2),2);
    elemy(loop1,3) = vtx(simp(loop1,3),2);
    elemy(loop1,4) = vtx(simp(loop1,4),2);
    elemz(loop1,1) = vtx(simp(loop1,1),3);
    elemz(loop1,2) = vtx(simp(loop1,2),3);
    elemz(loop1,3) = vtx(simp(loop1,3),3);
    elemz(loop1,4) = vtx(simp(loop1,4),3);
end
for loop2 = 1:simpr2
    elemx2(loop2,1) = vtx2(simp2(loop2,1),1);
    elemx2(loop2,2) = vtx2(simp2(loop2,2),1);
    elemx2(loop2,3) = vtx2(simp2(loop2,3),1);
    elemx2(loop2,4) = vtx2(simp2(loop2,4),1);
    elemy2(loop2,1) = vtx2(simp2(loop2,1),2);
    elemy2(loop2,2) = vtx2(simp2(loop2,2),2);
    elemy2(loop2,3) = vtx2(simp2(loop2,3),2);
    elemy2(loop2,4) = vtx2(simp2(loop2,4),2);
    elemz2(loop2,1) = vtx2(simp2(loop2,1),3);
    elemz2(loop2,2) = vtx2(simp2(loop2,2),3);
    elemz2(loop2,3) = vtx2(simp2(loop2,3),3);
    elemz2(loop2,4) = vtx2(simp2(loop2,4),3);
end
%//point test calculation
r =[1;1;1;1];
for a = 1:simpr
    m=1;
    for b=1:simpr2  
        for n = 1:4
            p = [elemx2(b,n),elemy2(b,n),elemz2(b,n)];
            n1=[elemx(a,1),elemy(a,1),elemz(a,1)];
            n2=[elemx(a,2),elemy(a,2),elemz(a,2)];
            n3=[elemx(a,3),elemy(a,3),elemz(a,3)];
            n4=[elemx(a,4),elemy(a,4),elemz(a,4)];
            d0 =[n1;n2;n3;n4];
            d0 =[d0 r];
            d1 =[p;n2;n3;n4];
            d1 =[d1 r];
            d2 =[n1;p;n3;n4];
            d2 =[d2 r];
            d3 =[n1;n2;p;n4];
            d3 =[d3 r];
            d4 =[n1;n2;n3;p];
            d4 =[d4 r];
            deter0 = sign(det(d0));
            deter1 = sign(det(d1));
            deter2 = sign(det(d2));
            deter3 = sign(det(d3));
            deter4 = sign(det(d4));
            if isequal(deter0,deter1,deter2,deter3,deter4)
                elemno(a,m) = b;   
                m=m+1;
                break;
            else
                continue;
            end
        end
    end
end

Answer 1

注意，两个四面体的所有顶点都可以位于彼此之外，但这些四面体确实相交，因此点测试不是可靠的方法。

可能的稳健和快速的方法是分离轴的方法。

我使用2D版本来快速选择包含许多（10^4和10^6）凸多边形的两个集合之间的相交对，但3D版本看起来也足够简单。