c++ - 3D 三角形光栅化为体素网格

标签 c++ algorithm 3d voxel rasterizing

序言:

这是将 3D 三角形光栅化涵盖到体素网格中的问答，我被要求解决与 material erosion/removal 相关的不同问题。在制造过程模拟中。这个问题背后的主要思想是如何移植基于扫描线的 2D 三角形光栅化，如 this转化为 3D 体素。

所以问题是如何有效地将3D三角形光栅化为均匀体素网格表示为3D数组，体素表示为浮点值(密度或颜色(如果您愿意)。

使用C++，无需任何额外的库来进行光栅化本身。

最佳答案

所以首先更新算法:

  1. 定义

    让三角形由其 3 个 int 3D 顶点和一个 float 颜色给出:

    void triangle(int x0,int y0,int z0,int x1,int y1,int z1,int x2,int y2,int z2,float c);

    目标体素网格是这样的 3D 数组:

    float map[vxs][vys][vzs];

    其中vxs,vys,vzs是网格的分辨率。扫描线算法需要左右缓冲区，但是在 3D 中我们不能使用单轴，所以我选择了主轴(具有输入三角形 AABB BBOX 最大边的轴)，因此缓冲区大小 vsz 应该为 3 个分辨率中的最大值。由于它只是一维数组，因此内存消耗不大，所以为了方便起见，我选择了它:

    const int vsz=vxs|vys|vzs;
int lx[vsz],ly[vsz],lz[vsz]; // left buffers for filling
int rx[vsz],ry[vsz],rz[vsz]; // right buffers for filling

  2. 计算 AABB 并选择主轴

     int X0,Y0,Z0,X1,Y1,Z1,dx,dy,dz;
 // BBOX
            X0=x0;            X1=x0;
 if (X0>x1) X0=x1; if (X1<x1) X1=x1;
 if (X0>x2) X0=x2; if (X1<x2) X1=x2;
            Y0=y0;            Y1=y0;
 if (Y0>y1) Y0=y1; if (Y1<y1) Y1=y1;
 if (Y0>y2) Y0=y2; if (Y1<y2) Y1=y2;
            Z0=z0;            Z1=z0;
 if (Z0>z1) Z0=z1; if (Z1<z1) Z1=z1;
 if (Z0>z2) Z0=z2; if (Z1<z2) Z1=z2;
 dx=X1-X0;
 dy=Y1-Y0;
 dz=Z1-Z0;

    现在从 dx,dy,dz 的值(最大的一个)中选择长轴。例如，如果dx最大，那么从现在开始左右缓冲区索引将是x坐标。

  3. 将三角形边缘光栅化到左/右缓冲区

    现在要选择边缘是否应该进入左侧缓冲区或右侧缓冲区，我们可以使用主要坐标差的符号。因此，选择第一个，然后按主坐标对边顶点进行排序(以避免连接三角形上出现孔洞)。

    对于边缘(线)的光栅化，只需使用 integer version of DDA algortihm它很容易移植到更高的维度，并且在现代 CPU 上比 Bresenham 更快。

    现在，我们只需将其渲染到左/右缓冲区中，而不是将线的体素 (x,y,z) 渲染到 map 中。因此，如果长轴是 x 并且目标缓冲区保留，则它将是:

    ly[x]=y;
lz[x]=z;

    由于有 3 个可能的主轴，我们需要该函数的 3 个版本...目标缓冲区也有 3 种情况(左、右、两者)，但为此您可以使用指针，因此不需要每个代码两次...

    此外，如果边缘可能超出体素网格范围，则需要添加剪切。我在 DDA 迭代中使用了简单的 if 条件，但是为了提高速度，最好在此之前剪辑该行...

  4. 用线条填充三角形

    只需遍历左/右缓冲区并在它们用线表示的相同索引处连接顶点。线条本身可能会被简化，因为我们知道主轴不会改变，但为了简单起见，我使用了普通的 3D DDA 线条(与 #3 相同，只是直接渲染到 map 中，而不是左/右缓冲区)。

将所有内容放在一起:

// voxel grid resolution
const int vxs=100;
const int vys=100;
const int vzs=100;
// helper buffers size should be max(vxs,vys,vzs)
const int vsz=vxs|vys|vzs;
float map[vxs][vys][vzs];       // voxel space map
int lx[vsz],ly[vsz],lz[vsz];    // left buffers for filling
int rx[vsz],ry[vsz],rz[vsz];    // right buffers for filling

void line(int x0,int y0,int z0,int x1,int y1,int z1,float c) // rencer line
    {
    int i,n,cx,cy,cz,sx,sy,sz;
    // line DDA parameters
    x1-=x0; sx=0; if (x1>0) sx=+1; if (x1<0) { sx=-1; x1=-x1; } if (x1) x1++;           n=x1;
    y1-=y0; sy=0; if (y1>0) sy=+1; if (y1<0) { sy=-1; y1=-y1; } if (y1) y1++; if (n<y1) n=y1;
    z1-=z0; sz=0; if (z1>0) sz=+1; if (z1<0) { sz=-1; z1=-z1; } if (z1) z1++; if (n<z1) n=z1;
    // single pixel (not a line)
    if (!n)
        {
        if ((x0>=0)&&(x0<vxs)&&(y0>=0)&&(y0<vys)&&(z0>=0)&&(z0<vzs)) map[x0][y0][z0]=c;
        return;
        }
    // ND DDA algo i is parameter
    for (cx=cy=cz=n,i=0;i<n;i++)
        {
        if ((x0>=0)&&(x0<vxs)&&(y0>=0)&&(y0<vys)&&(z0>=0)&&(z0<vzs)) map[x0][y0][z0]=c;
        cx-=x1; if (cx<=0){ cx+=n; x0+=sx; }
        cy-=y1; if (cy<=0){ cy+=n; y0+=sy; }
        cz-=z1; if (cz<=0){ cz+=n; z0+=sz; }
        }
    }

void _plinex(int x0,int y0,int z0,int x1,int y1,int z1) // helper edge render
    {
    int i,n,cx,cy,cz,sx,sy,sz,*by,*bz;
    // target buffer & order points by x
    if (x1>=x0)
        {
        i=x0; x0=x1; x0=i;
        i=y0; y0=y1; y0=i;
        i=z0; z0=z1; z0=i; by=ly; bz=lz;
        } else {           by=ry; bz=rz; }
    // line DDA parameters
    x1-=x0; sx=0; if (x1>0) sx=+1; if (x1<0) { sx=-1; x1=-x1; } if (x1) x1++;           n=x1;
    y1-=y0; sy=0; if (y1>0) sy=+1; if (y1<0) { sy=-1; y1=-y1; } if (y1) y1++; if (n<y1) n=y1;
    z1-=z0; sz=0; if (z1>0) sz=+1; if (z1<0) { sz=-1; z1=-z1; } if (z1) z1++; if (n<z1) n=z1;
    // single pixel (not a line)
    if (!n)
        {
        if ((x0>=0)&&(x0<vxs))
            {
            ly[x0]=y0; lz[x0]=z0;
            ry[x0]=y0; rz[x0]=z0;
            }
        return;
        }
    // ND DDA algo i is parameter
    for (cx=cy=cz=n,i=0;i<n;i++)
        {
        if ((x0>=0)&&(x0<vxs)){ by[x0]=y0; bz[x0]=z0; }
        cx-=x1; if (cx<=0){ cx+=n; x0+=sx; }
        cy-=y1; if (cy<=0){ cy+=n; y0+=sy; }
        cz-=z1; if (cz<=0){ cz+=n; z0+=sz; }
        }
    }

void _pliney(int x0,int y0,int z0,int x1,int y1,int z1) // helper edge render
    {
    int i,n,cx,cy,cz,sx,sy,sz,*bx,*bz;
    // target buffer & order points by y
    if (y1>=y0)
        {
        i=x0; x0=x1; x0=i;
        i=y0; y0=y1; y0=i;
        i=z0; z0=z1; z0=i; bx=lx; bz=lz;
        } else {           bx=rx; bz=rz; }
    // line DDA parameters
    x1-=x0; sx=0; if (x1>0) sx=+1; if (x1<0) { sx=-1; x1=-x1; } if (x1) x1++;           n=x1;
    y1-=y0; sy=0; if (y1>0) sy=+1; if (y1<0) { sy=-1; y1=-y1; } if (y1) y1++; if (n<y1) n=y1;
    z1-=z0; sz=0; if (z1>0) sz=+1; if (z1<0) { sz=-1; z1=-z1; } if (z1) z1++; if (n<z1) n=z1;
    // single pixel (not a line)
    if (!n)
        {
        if ((y0>=0)&&(y0<vys))
            {
            lx[y0]=x0; lz[y0]=z0;
            rx[y0]=x0; rz[y0]=z0;
            }
        return;
        }
    // ND DDA algo i is parameter
    for (cx=cy=cz=n,i=0;i<n;i++)
        {
        if ((y0>=0)&&(y0<vys)){ bx[y0]=x0; bz[y0]=z0; }
        cx-=x1; if (cx<=0){ cx+=n; x0+=sx; }
        cy-=y1; if (cy<=0){ cy+=n; y0+=sy; }
        cz-=z1; if (cz<=0){ cz+=n; z0+=sz; }
        }
    }

void _plinez(int x0,int y0,int z0,int x1,int y1,int z1) // helper edge render
    {
    int i,n,cx,cy,cz,sx,sy,sz,*bx,*by;
    // target buffer & order points by z
    if (z1>=z0)
        {
        i=x0; x0=x1; x0=i;
        i=y0; y0=y1; y0=i;
        i=z0; z0=z1; z0=i; bx=lx; by=ly;
        } else {           bx=rx; by=ry; }
    // line DDA parameters
    x1-=x0; sx=0; if (x1>0) sx=+1; if (x1<0) { sx=-1; x1=-x1; } if (x1) x1++;           n=x1;
    y1-=y0; sy=0; if (y1>0) sy=+1; if (y1<0) { sy=-1; y1=-y1; } if (y1) y1++; if (n<y1) n=y1;
    z1-=z0; sz=0; if (z1>0) sz=+1; if (z1<0) { sz=-1; z1=-z1; } if (z1) z1++; if (n<z1) n=z1;
    // single pixel (not a line)
    if (!n)
        {
        if ((z0>=0)&&(z0<vzs))
            {
            lx[z0]=x0; ly[z0]=y0;
            rx[z0]=x0; ry[z0]=y0;
            }
        return;
        }
    // ND DDA algo i is parameter
    for (cx=cy=cz=n,i=0;i<n;i++)
        {
        if ((z0>=0)&&(z0<vzs)){ bx[z0]=x0; by[z0]=y0; }
        cx-=x1; if (cx<=0){ cx+=n; x0+=sx; }
        cy-=y1; if (cy<=0){ cy+=n; y0+=sy; }
        cz-=z1; if (cz<=0){ cz+=n; z0+=sz; }
        }
    }

void triangle(int x0,int y0,int z0,int x1,int y1,int z1,int x2,int y2,int z2,float c) // render triangle
    {
    int X0,Y0,Z0,X1,Y1,Z1,dx,dy,dz,x,y,z;
    // BBOX
               X0=x0;            X1=x0;
    if (X0>x1) X0=x1; if (X1<x1) X1=x1;
    if (X0>x2) X0=x2; if (X1<x2) X1=x2;
               Y0=y0;            Y1=y0;
    if (Y0>y1) Y0=y1; if (Y1<y1) Y1=y1;
    if (Y0>y2) Y0=y2; if (Y1<y2) Y1=y2;
               Z0=z0;            Z1=z0;
    if (Z0>z1) Z0=z1; if (Z1<z1) Z1=z1;
    if (Z0>z2) Z0=z2; if (Z1<z2) Z1=z2;
    dx=X1-X0;
    dy=Y1-Y0;
    dz=Z1-Z0;
         if ((dx>=dy)&&(dx>=dz))    // x is major axis
        {
        // render circumference into left/right buffers
        _plinex(x0,y0,z0,x1,y1,z1);
        _plinex(x1,y1,z1,x2,y2,z2);
        _plinex(x2,y2,z2,x0,y0,z0);
        // fill the triangle
        if (X0<0) X0=0; if (X1>=vxs) X1=vxs-1;
        for (x=X0;x<=X1;x++)
            {
            y0=ly[x]; z0=lz[x];
            y1=ry[x]; z1=rz[x];
            line(x,y0,z0,x,y1,z1,c);
            }
        }
    else if ((dy>=dx)&&(dy>=dz))    // y is major axis
        {
        // render circumference into left/right buffers
        _pliney(x0,y0,z0,x1,y1,z1);
        _pliney(x1,y1,z1,x2,y2,z2);
        _pliney(x2,y2,z2,x0,y0,z0);
        // fill the triangle
        if (Y0<0) Y0=0; if (Y1>=vys) Y1=vys-1;
        for (y=Y0;y<=Y1;y++)
            {
            x0=lx[y]; z0=lz[y];
            x1=rx[y]; z1=rz[y];
            line(x0,y,z0,x1,y,z1,c);
            }
        }
    else if ((dz>=dx)&&(dz>=dy))    // z is major axis
        {
        // render circumference into left/right buffers
        _plinez(x0,y0,z0,x1,y1,z1);
        _plinez(x1,y1,z1,x2,y2,z2);
        _plinez(x2,y2,z2,x0,y0,z0);
        // fill the triangle
        if (Z0<0) Z0=0; if (Z1>=vzs) Z1=vzs-1;
        for (z=Z0;z<=Z1;z++)
            {
            x0=lx[z]; y0=ly[z];
            x1=rx[z]; y1=ry[z];
            line(x0,y0,z,x1,y1,z,c);
            }
        }
    }

边缘函数_pline可以加速，如果你意识到长轴与迭代轴i相同，你可以减少一次计算。此外，这 3 个化身可以合并为一个(只需重新排序被调用参数的 x,y,z 顺序并传递左/右缓冲区指针。将剪辑移到 DDA 迭代之外应该会提高性能也相当不错。

此处预览三角形相交圆柱体:

preview1

此处预览使用此三角形光栅化的 Material 去除:

preview2

橙色三角形不是体素一，它只是叠加，体素一不是直接渲染的，而是从体素网格中减去，而不是在动画过程中删除 Material ......

关于c++ - 3D 三角形光栅化为体素网格，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/74251620/

上一篇：python - Postgres : psycopg2. 错误。InvalidTextRepresentation: bool 类型的输入语法无效

下一篇：linux - 在 SSH 到另一台服务器后抑制输出

相关文章：

swift - SceneKit—— fatal error : unexpectedly found nil while unwrapping an Optional value when getting child node

c# - 处理奇数场偏移

algorithm - 模块化算术难题 codeforces

c++ - 共享指针上的原子操作，C++ 版本

数组中组合索引的算法

ruby - 在JSON文件中实现搜索操作的高效方式

c++ - FBO分离纹理

wpf - 如何将 Viewport3D 导出​​为 2d 图像文件？

c++ - 使用 CMake 构建 cpp-netlib

c++ - 从符号尾数和指数构造 float

©2024 IT工具网  联系我们