八叉树

八叉树

关注
发信
关注(28)粉丝(399)

c++ - 八叉树生成在最后一步出错

注意:此问题已经从其原始格式进行了彻底编辑

我正在尝试通过实现结合了体素化的八叉树数据结构来创建对数射线跟踪器，以实现快速射线跟踪。

目前，我在光线碰撞检测方面遇到问题。

预期输出应为体素化的斯坦福巨龙及其法线贴图。

当前的问题是某些区域是透明的:

全龙:

c++ - 八叉树生成在最后一步出错-LMLPHP

透明区域:

c++ - 八叉树生成在最后一步出错-LMLPHP

从这些图像中可以清楚地看出几何形状是正确的，但是碰撞检查是错误的。

此过程涉及2个片段着色器:

体素化器片段着色器:

#version 430

in vec3 f_pos;
in vec3 f_norm;
in vec2 f_uv;

out vec4 f_color;
struct Voxel
{
    vec4 position;
    vec4 normal;
    vec4 color;
};

struct Node
{
    int children[8];
};

layout(std430, binding = 0) buffer voxel_buffer
{
    Voxel voxels[];
};
layout(std430, binding = 1) buffer buffer_index
{
    uint index;
};
layout(std430, binding = 2) buffer tree_buffer
{
    Node tree[];
};
layout(std430, binding = 3) buffer tree_index
{
    uint t_index;
};

out vec4 fragment_color;

uniform int voxel_resolution;
uniform int cube_dim;

int getVIndex(vec3 position, int level)
{
    float size = cube_dim / pow(2,level);

    int bit2 = int(position.x > size);
    int bit1 = int(position.y > size);
    int bit0 = int(position.z > size);

    return 4*bit2 + 2*bit1 + bit0;
}

void main()
{

    uint m_index = atomicAdd(index, 1);

    voxels[m_index].position = vec4(f_pos*cube_dim,1);
    voxels[m_index].normal = vec4(f_norm,1);
    voxels[m_index].color = vec4(f_norm,1);

    int max_level = int(log2(voxel_resolution));
    int node = 0;
    vec3 corner = vec3(-cube_dim);
    int child;

    for(int level=0; level<max_level-1; level++)
    {
        float size = cube_dim / pow(2,level);
        vec3 corners[] =
            {corner,                    corner+vec3(0,0,size),
            corner+vec3(0,size,0),      corner+vec3(0,size,size),
            corner+vec3(size,0,0),      corner+vec3(size,0,size),
            corner+vec3(size,size,0),   corner+vec3(size,size,size)};

        vec3 offsetPos = (vec3(voxels[m_index].position));
       child = getVIndex(offsetPos-corner, level);

        int mrun = 500;
        while ((tree[node].children[child] <= 0) && (mrun > 0)){
            mrun--;
            if( (atomicCompSwap( tree[node].children[child] , 0 , -1) == 0 ))
            {
                tree[node].children[child] = int(atomicAdd(t_index, 1));
            }
        }

        if(mrun < 1)
            discard;

        if(level==max_level-2)
            break;

        node = tree[node].children[child];

        corner = corners[child];
    }

    tree[node].children[child] = int(m_index);

}

我了解逻辑可能不清楚，所以让我解释一下:

我们从3D psoition voxels[m_index].position = vec4(f_pos*cube_dim,1);开始，我们知道存在一个多维数据集，其尺寸为(-cube_dim，-cube_dim，-cube_dim)至(cube_dim，cube_dim，cube_dim)
因此，一个对角线在原点相交且边长为2 * cube_dim的立方体。那已经被划分为边长为2 * cube_dim / voxel_resolution的多个小立方体。基本上，这只是一个立方体，可细分为n次以构成笛卡尔网格。

使用此坐标，我们从大立方体开始，将其细分为8个相等大小的子空间，并检测这些子空间中的哪些构成坐标。

我们这样做直到找到包含该位置的最小框。

光线追踪器
 #version 430

in vec2 f_coord;

out vec4 fragment_color;

struct Voxel
{
    vec4 position;
    vec4 normal;
    vec4 color;
};

struct Node
{
    int children[8];
};

layout(std430, binding = 0) buffer voxel_buffer
{
    Voxel voxels[];
};
layout(std430, binding = 1) buffer buffer_index
{
    uint index;
};
layout(std430, binding = 2) buffer tree_buffer
{
    Node tree[];
};
layout(std430, binding = 3) buffer tree_index
{
    uint t_index;
};

uniform vec3 camera_pos;
uniform float aspect_ratio;
uniform float cube_dim;
uniform int voxel_resolution;

float planeIntersection(vec3 origin, vec3 ray, vec3 pNormal, vec3 pPoint)
{
    pNormal = normalize(pNormal);
    return (dot(pPoint,pNormal)-dot(pNormal,origin))/dot(ray,pNormal);
}

#define EPSILON 0.001
bool inBoxBounds(vec3 corner, float size, vec3 position)
{
    bool inside = true;
    position-=corner;

    for(int i=0; i<3; i++)
    {
        inside = inside && (position[i] > -EPSILON);
        inside = inside && (position[i] < size+EPSILON);
    }

    return inside;
}


float boxIntersection(vec3 origin, vec3 dir, vec3 corner0, float size)
{
    dir = normalize(dir);
    vec3 corner1 = corner0 + vec3(size,size,size);

    vec3 normals[6] =
    { vec3(-1,0,0), vec3(0,-1,0), vec3(0,0,-1), vec3(1,0,0), vec3(0,1,0), vec3(0,0,1) };

    float coeffs[6];

    for(uint i=0; i<3; i++)
        coeffs[i] = planeIntersection(origin, dir, normals[i], corner0);
    for(uint i=3; i<6; i++)
        coeffs[i] = planeIntersection(origin, dir, normals[i], corner1);

    float t = 1.f/0.f;

    for(uint i=0; i<6; i++){
        coeffs[i] = coeffs[i] < 0 ? 1.f/0.f : coeffs[i];
        t = inBoxBounds(corner0,size,origin+dir*coeffs[i]) ? min(coeffs[i],t) : t;
    }

    return t;
}

void sort(float elements[8], int indices[8], vec3 vectors[8])
{
    for(uint i=0; i<8; i++)
    {
        for(uint j=i; j<8; j++)
        {
            if(elements[j] < elements[i])
            {
                float swap = elements[i];
                elements[i] = elements[j];
                elements[j] = swap;

                int iSwap = indices[i];
                indices[i] = indices[j];
                indices[j] = iSwap;

                vec3 vSwap = vectors[i];
                vectors[i] = vectors[j];
                vectors[j] = vSwap;
            }
        }
    }
}

int getVIndex(vec3 position, int level)
{
    float size = cube_dim / pow(2,level);

    int bit2 = int(position.x > size);
    int bit1 = int(position.y > size);
    int bit0 = int(position.z > size);

    return 4*bit2 + 2*bit1 + bit0;
}

#define MAX_TREE_HEIGHT 11
int nodes[8*MAX_TREE_HEIGHT];
int levels[8*MAX_TREE_HEIGHT];
vec3 positions[8*MAX_TREE_HEIGHT];
int sp=0;

void push(int node, int level, vec3 corner)
{
    nodes[sp] = node;
    levels[sp] = level;
    positions[sp] = corner;
    sp++;
}
void main()
{
    vec3 r = vec3(f_coord.x, f_coord.y, 1.f/tan(radians(40)));
    r.y/=aspect_ratio;
    vec3 dir = r;
    r += vec3(0,0,-1.f/tan(radians(40))) + camera_pos;

    fragment_color = vec4(0);
    //int level = 0;
    int max_level = int(log2(voxel_resolution));
    push(0,0,vec3(-cube_dim));
    float tc = 1.f;
    int level=0;
    int node=0;
    do
    {
        sp--;
        node = nodes[sp];
        level = levels[sp];
        vec3 corner = positions[sp];

        float size = cube_dim / pow(2,level);
        vec3 corners[] =
            {corner,                        corner+vec3(0,0,size),
            corner+vec3(0, size,0),         corner+vec3(0,size,size),
            corner+vec3(size,0,0),          corner+vec3(size,0,size),
            corner+vec3(size,size,0),       corner+vec3(size,size,size)};

        float t = boxIntersection(r, dir, corner, size*2);
        if(!isinf(t))
            tc *= 0.9f;

        float coeffs[8];
        for(int child=0; child<8; child++)
        {
            if(tree[node].children[child]>0)
                coeffs[child] = boxIntersection(r, dir, corners[child], size);
            else
                coeffs[child] = 1.f/0.f;
        }
        int indices[8] = {0,1,2,3,4,5,6,7};
        sort(coeffs, indices, corners);

        for(uint i=7; i>=0; i--)
        {
            if(!isinf(coeffs[i]))
            {
                push(tree[node].children[indices[i]],
                    level+1, corners[i]);
            }
        }
    }while(level < (max_level-1) && sp>0);

    if(level==max_level-1)
    {
        fragment_color = abs(voxels[node].normal);
    }

    else
    {
        fragment_color=vec4(tc);
    }

}
}

在这里，我们从最大的多维数据集开始，测试每组8个子级的相交(这8个多维数据集是通过细分一个多维数据集得到的)。每次成功检测到碰撞时，我们都会向下移动树，直到达到描述实际几何形状的最低层次，并以此为基础为场景着色。

调试与问题

重要的部分是有2个缓冲区，一个用于存储除叶子以外的树，另一个用于存储叶子。

因此，在体素化和射线追踪中，都需要对最后一层进行不同的处理。

我注意到的有关透明度的问题如下:
  • 它仅在与笛卡尔网格
    • 对齐的平面上发生
  • 似乎当光线向负方向移动时(向下
    或向左)。 (至少这是我的错，但不是100％
    一定)

    • 我不确定自己在做什么错。

    编辑:

    原始问题似乎已得到解决，但是raytracer仍然存在错误。我已编辑问题以反射(reflect)问题的当前状态。

    最佳答案

    该错误来自排序功能，原因是提及的注释中有某人，尽管原因并非相同。

    发生的事情是，我认为sort函数会修改传递给它的数组，但是它似乎正在复制数据，因此它不返回任何内容。

    换一种说法:

    void sort(float elements[8], int indices[8], vec3 vectors[8])
{
    for(uint i=0; i<8; i++)
    {
        for(uint j=i; j<8; j++)
        {
            if((elements[j] < elements[i]))
            {
                float swap = elements[i];
                elements[i] = elements[j];
                elements[j] = swap;

                int iSwap = indices[i];
                indices[i] = indices[j];
                indices[j] = iSwap;

                vec3 vSwap = vectors[i];
                vectors[i] = vectors[j];
                vectors[j] = vSwap;
            }
        }
    }
}

    不会在元素，索引和 vector 内返回正确的值，因此调用此函数只会浪费计算周期。

    09-20 16:56
    Powered by LMLPHP ©2024 八叉树 0.030502