23

私は、光線が反復的に通過する葉を与える、優れた光線と八分木の交差アルゴリズムを探しています。まだCUDAに飛び込みたくないので、CPUに実装することを計画しています:)

現時点では、私のボクセルレイキャスターは、XxYxZボクセルの非階層配列に対して3D DDA（Amanatides / Wooバージョン）を実行します。次の図に示すように、空のスペースがたくさんある場合、これはかなりコストがかかることを想像できます（明るい赤=より多くの作業:)）：

ダム3DDDAのワークロード-赤=より多くの作業

このタスクには2種類のアルゴリズムがあることをすでに理解しました。リーフから上に向かって機能するボトムアップと、基本的に深さ優先探索であるトップダウンです。

私はすでに2000年からRevellesのアルゴリズムを見つけました。これは、八分木探索のための効率的なパラメトリックアルゴリズムと呼ばれ、面白そうに見えますが、かなり古いものです。これはトップダウンアルゴリズムです。

最も人気のあるボトムアップアプローチは、K。Sung、レイトレーシング用のDDAオクトリートラバーサルアルゴリズム、Eurographics'91、North Holland-Elsevier、ISBN 0444 89096 3、p。73-85。問題は、ほとんどのDDA Octreeトラバーサルアルゴリズムが、octreeが同じ深さであることを期待していることです。これは、私が望んでいないことです。空のサブツリーは、nullポインターなどである必要があります。

私が読み通したSparseVoxelOctreesに関する最近の文献では、（特にSVOに関するLaineの作業は、GPUで実装されたバージョンのDDA（Amanatides / Wooスタイル）に基づいているようです。

さて、ここに私の質問があります：誰かが基本的な、飾り気のない光線-八分木交差アルゴリズムを実装した経験がありますか？あなたは何をお勧めします？

4

2 に答える 2

13

ちなみに、これは私が最終的に使用したRevellesペーパーの実装です。

#include "octree_traversal.h"

using namespace std;

unsigned char a; // because an unsigned char is 8 bits

int first_node(double tx0, double ty0, double tz0, double txm, double tym, double tzm){
unsigned char answer = 0;   // initialize to 00000000
// select the entry plane and set bits
if(tx0 > ty0){
    if(tx0 > tz0){ // PLANE YZ
        if(tym < tx0) answer|=2;    // set bit at position 1
        if(tzm < tx0) answer|=1;    // set bit at position 0
        return (int) answer;
    }
}
else {
    if(ty0 > tz0){ // PLANE XZ
        if(txm < ty0) answer|=4;    // set bit at position 2
        if(tzm < ty0) answer|=1;    // set bit at position 0
        return (int) answer;
    }
}
// PLANE XY
if(txm < tz0) answer|=4;    // set bit at position 2
if(tym < tz0) answer|=2;    // set bit at position 1
return (int) answer;
}

int new_node(double txm, int x, double tym, int y, double tzm, int z){
if(txm < tym){
    if(txm < tzm){return x;}  // YZ plane
}
else{
    if(tym < tzm){return y;} // XZ plane
}
return z; // XY plane;
}

void proc_subtree (double tx0, double ty0, double tz0, double tx1, double ty1, double tz1, Node* node){
float txm, tym, tzm;
int currNode;

if(tx1 < 0 || ty1 < 0 || tz1 < 0) return;
if(node->terminal){
    cout << "Reached leaf node " << node->debug_ID << endl;
    return;
}
else{ cout << "Reached node " << node->debug_ID << endl;}

txm = 0.5*(tx0 + tx1);
tym = 0.5*(ty0 + ty1);
tzm = 0.5*(tz0 + tz1);

currNode = first_node(tx0,ty0,tz0,txm,tym,tzm);
do{
    switch (currNode)
    {
    case 0: { 
        proc_subtree(tx0,ty0,tz0,txm,tym,tzm,node->children[a]);
        currNode = new_node(txm,4,tym,2,tzm,1);
        break;}
    case 1: { 
        proc_subtree(tx0,ty0,tzm,txm,tym,tz1,node->children[1^a]);
        currNode = new_node(txm,5,tym,3,tz1,8);
        break;}
    case 2: { 
        proc_subtree(tx0,tym,tz0,txm,ty1,tzm,node->children[2^a]);
        currNode = new_node(txm,6,ty1,8,tzm,3);
        break;}
    case 3: { 
        proc_subtree(tx0,tym,tzm,txm,ty1,tz1,node->children[3^a]);
        currNode = new_node(txm,7,ty1,8,tz1,8);
        break;}
    case 4: { 
        proc_subtree(txm,ty0,tz0,tx1,tym,tzm,node->children[4^a]);
        currNode = new_node(tx1,8,tym,6,tzm,5);
        break;}
    case 5: { 
        proc_subtree(txm,ty0,tzm,tx1,tym,tz1,node->children[5^a]);
        currNode = new_node(tx1,8,tym,7,tz1,8);
        break;}
    case 6: { 
        proc_subtree(txm,tym,tz0,tx1,ty1,tzm,node->children[6^a]);
        currNode = new_node(tx1,8,ty1,8,tzm,7);
        break;}
    case 7: { 
        proc_subtree(txm,tym,tzm,tx1,ty1,tz1,node->children[7^a]);
        currNode = 8;
        break;}
    }
} while (currNode<8);
}

void ray_octree_traversal(Octree* octree, Ray ray){
a = 0;

// fixes for rays with negative direction
if(ray.direction[0] < 0){
    ray.origin[0] = octree->center[0] * 2 - ray.origin[0];//camera origin fix
    ray.direction[0] = - ray.direction[0];
    a |= 4 ; //bitwise OR (latest bits are XYZ)
}
if(ray.direction[1] < 0){
    ray.origin[1] = octree->center[1] * 2 - ray.origin[1];
    ray.direction[1] = - ray.direction[1];
    a |= 2 ; 
}
if(ray.direction[2] < 0){
    ray.origin[2] = octree->center[2] * 2 - ray.origin[2];
    ray.direction[2] = - ray.direction[2];
    a |= 1 ; 
}

double divx = 1 / ray.direction[0]; // IEEE stability fix
double divy = 1 / ray.direction[1];
double divz = 1 / ray.direction[2];

double tx0 = (octree->min[0] - ray.origin[0]) * divx;
double tx1 = (octree->max[0] - ray.origin[0]) * divx;
double ty0 = (octree->min[1] - ray.origin[1]) * divy;
double ty1 = (octree->max[1] - ray.origin[1]) * divy;
double tz0 = (octree->min[2] - ray.origin[2]) * divz;
double tz1 = (octree->max[2] - ray.origin[2]) * divz;

if( max(max(tx0,ty0),tz0) < min(min(tx1,ty1),tz1) ){
    proc_subtree(tx0,ty0,tz0,tx1,ty1,tz1,octree->root);
}
}
于 2012-05-09T11:48:24.050 に答える
1

トップダウンは私にとって非常にうまく機能します。octreeの上部はポインタベースである可能性があるため、大きな空のサブボリュームはメモリを消費しません。下部はポインターフリーを実装するのにより効率的です...壁にぶつかる時間計算量はlog2（N）です（これは明らかに最良のケースです）。再帰的な実装は非常に単純なので、コードを最適化する方が簡単です。すべての計算は、整数SSE操作を介して効果的に実装できます。サブボリュームジャンプごとに新しいXYZ座標を計算するには、約x30CPUサイクルかかります。ところで、オクトリートラバーサルのパブリックバージョンは教育にのみ適しています-本当に効果的な実装を習得するには、簡単に数か月かかる場合があります...

ステファン

于 2012-04-20T06:44:49.127 に答える