雷 - 八叉树路口算法 [英] Ray - Octree intersection algorithms
问题描述
我正在寻找一个良好的光线,八叉树交集算法,它带给我的光线穿过一个迭代的方式叶子。我打算在CPU上实现它,因为我不想深入CUDA只是尚未:)
I'm looking for a good ray-octree intersection algorithm, which gives me the leafs the ray passes through in an iterative way. I'm planning on implementing it on the CPU, since I do not want to dive into CUDA just yet :)
目前,我的体素raycaster少了点3D DDA(Amanatides /佑版)上XxYxZ体素的非分层阵列。你可以想像,这是pretty的成本时,有一个很大的空白,这表现在下面的图片(亮红色=更多的工作:)):
At the moment, my Voxel raycaster just does 3D DDA (Amanatides/Woo version) on a non-hierarchic array of XxYxZ voxels. You can imagine that this is pretty costly when there's a lot of empty space, as demonstrated in the following picture (brighter red = more work :) ):
我已经想通了,有两种类型的完成这个任务的算法:自下而上,它从叶子的作品回来向上,和自上而下 ,这是basicly深度优先搜索。
I've already figured out that there are two kinds of algorithms for this task: bottom-up, which works from the leafs back upwards, and top-down, which is basicly depth-first search.
我已经找到Revelles算法从2000年,所谓的 一个高效参数算法八叉树遍历 的,这看起来很有趣,但很老。这是一个顶向下的算法。
I've already found Revelles' algorithm from 2000, called An efficient parametric algorithm for octree traversal, which looks interesting, but is quite old. This is a top-down algorithm.
最流行的自下而上的方法似乎是的 K。宋,A DDA八叉树遍历算法进行光线追踪,Eurographics'91,北荷兰 - 爱思唯尔,书号0444 89096 3,P。 73-85 的问题是,大多数DDA八叉树的遍历算法,预计八叉树是相等的深度,这是我不希望 - 。空子树应该只是一个空指针或类似的东西。
The most popular bottom-up approach seems to be K. Sung, A DDA Octree Traversal Algorithm for Ray Tracing, Eurographics'91, North Holland-Elsevier, ISBN 0444 89096 3, p. 73-85. Problem is that most DDA Octree traversal algorithms expect the octree to be of equal depth, which I do not want - empty subtrees should just be a null pointer or something similar.
在最近的文献中有关疏体素八叉树我已经成功地阅读,(最显着的莱恩对SVO的的工作,他们似乎都基于某种DDA(Amanatides /胡的风格)。
In the more recent literature about Sparse Voxel Octrees I've managed to read through, (most notably Laine's work on SVO's, they all seem to be based on some kind of GPU-implemented version of DDA (Amanatides/Woo style).
现在,这里是我的问题:没有任何人有实施基本的经验,没有多余的装饰线,八叉树交集算法?你有什么建议?
Now, here's my question: does anybody have any experience implementing a basic, no-frills ray-octree intersection algorithm? What would you recommend?
推荐答案
有关的记录,这是我实现Revelles论文我最终使用:
For the record, this is my implementation of the Revelles paper I ended up using:
#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->size[0] - ray.origin[0];
ray.direction[0] = - ray.direction[0];
a |= 4 ; //bitwise OR (latest bits are XYZ)
}
if(ray.direction[1] < 0){
ray.origin[1] = octree->size[1] - ray.origin[1];
ray.direction[1] = - ray.direction[1];
a |= 2 ;
}
if(ray.direction[2] < 0){
ray.origin[2] = octree->size[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);
}
}
这篇关于雷 - 八叉树路口算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!