0

Axes Aligned Bounding Boxes (AABB) のセットとスペース パーティション (ここでは 8 つのパーティション) の間の交差を見つけるために、私は最初に次の Matlab コードを作成しました。それ自体で読めると思います。さらに、さらに明確にするためにいくつかのコメントを追加しました。

function [A,B] = AABBPart(bbx,it)                                     % bbx: aabb, it: iteration
global F
IT = it+1;
n = size(bbx,1);
F = cell(n,it);
A = Part([min(bbx(:,1:3)),max(bbx(:,4:6))],it,0);                     % recursive partitioning
B = F;                                                                % matlab does not allow
    function s = Part(bx,it,J)                                        %   output to be global
        s = {};
        if it < 1; return; end
        s = cell(8,1);
        p = bx(1:3);
        q = bx(4:6);
        h = 0.5*(p+q);
        prt = [p,h;...                                                % 8 sub-parts (octa)
            h(1),p(2:3),q(1),h(2:3);...
            p(1),h(2),p(3),h(1),q(2),h(3);...
            h(1:2),p(3),q(1:2),h(3);...
            p(1:2),h(1),h(1:2),q(3);...
            h(1),p(2),h(3),q(1),h(2),q(3);...
            p(1),h(2:3),h(1),q(2:3);...
            h,q];
        for j=1:8                                                     % check for each sub-part
            k = 0;
            t = zeros(0,1);
            for i=1:n
                if all(bbx(i,1:3) <= prt(j,4:6)) && ...               % interscetion test for
                        all(prt(j,1:3) <= bbx(i,4:6))                 %   every aabb and sub-parts
                    k = k+1;
                    t(k) = i;
                end
            end
            if ~isempty(t)
                s{j,1} = [t; Part(prt(j,:),it-1,j)];                  % recursive call
                for i=1:numel(t)                                      % collecting the results
                    if isempty(F{t(i),IT-it})
                        F{t(i),IT-it} = [-J,j];
                    else
                        F{t(i),IT-it} = [F{t(i),IT-it}; [-J,j]];
                    end
                end
            end
        end
    end
end

懸念：

  • 私のテストでは、1000 以上のセットアップに対して、たとえば 10 程度の交点が欠落しているようです。コード内の問題箇所を見つけていただけると助かります。

  • 使用感も気になりますglobal F。私はそれを取り除くことを好みます。

  • 速度の点で他のより良い解決策があれば、愛されます。

コードが完成していることに注意してください。そして、次の設定で簡単に試すことができます。

n = 10000;                        % in the original application, n would be millions
bbx = rand(n,6);
it = 3;
[A,B] = AABBPart(bbx,it);
4

0 に答える 0