序幕：
这是将 3D 三角形光栅化为体素网格的问答，我被要求解决与以下相关的不同问题材料侵蚀/去除在制造过程模拟期间。这个问题背后的主要思想是如何移植基于扫描线的 2D 三角形光栅化，例如this转化为 3D 体素。
所以问题是如何高效地光栅化 3D 三角形 into 均匀体素网格表示为3D array体素表示为浮点值（密度或颜色，如果您愿意）。
Using C++无需任何额外的光栅化库。
所以首先更新算法：
定义
让三角形由它的 3 给出int3D 顶点和一个float color:
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];
where 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
计算 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协调。
将三角形边缘栅格化到左/右缓冲区中
现在要选择边缘是否应该进入左侧缓冲区或右侧缓冲区，我们可以使用主要坐标差的符号。因此，选择第一个，然后按主坐标对边顶点进行排序（以避免连接三角形上出现孔）。
对于边缘（线）的光栅化只需使用DDA 算法的整数版本它很容易移植到更高的维度，并且在现代 CPU 上比 Bresenham 更快。
现在不再渲染体素(x,y,z)的线进入map我们只是将其渲染到左/右缓冲区中。所以如果长轴是x剩下的目标缓冲区将是：
ly[x]=y;
lz[x]=z;
由于有 3 个可能的主轴，我们需要该函数的 3 个版本...目标缓冲区也有 3 种情况（左、右、两者），但为此您可以使用指针，因此不需要每个代码两次。 。
另外，如果边缘可能超出体素网格范围，则需要添加剪切。我用的是简单的if然而，为了提高速度，DDA 迭代内的条件最好在此之前剪掉这条线......
用直线填充三角形
只需遍历左/右缓冲区并将顶点连接到它们用线表示的相同索引处即可。线本身可能会被简化，因为我们知道主轴不会改变，但为了简单起见，我使用了普通的 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 迭代之外也会大大提高性能。
这里是三角形相交圆柱体的预览：
这里预览使用三角形光栅化的材料去除：
橙色三角形不是体素一，它只是叠加，体素一不是直接渲染的，而是从体素网格中减去，而不是在动画过程中删除材料......