序幕：
這是將 3D 三角形光柵化為體素網格的問答，我被要求解決與制造程序模擬期間材料侵蝕/去除相關的不同問題。這個問題背后的主要思想是如何將這樣的基于掃描線的 2D 三角形光柵化移植到3D 體素中。
所以問題是如何有效地將 3D 三角形光柵化為表示為3D 陣列的均勻體素網格，體素表示為浮點值（如果你喜歡，密度或顏色）。
使用沒有任何額外庫的C 來進行光柵化本身。
uj5u.com熱心網友回復：
所以首先更新演算法：
定義
讓三角形由它的 3 個
int3D 頂點和一種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計算 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 種情況（左、右、兩者），但為此您可能會使用指標，因此不需要每個代碼兩次.. .
此外，如果邊緣可能超出體素網格范圍，則需要添加裁剪。我在 DDA 迭代中使用了簡單的
if條件，但是為了提高速度，最好在此之前剪斷線......使用線條填充三角形
只需通過左/右緩沖區并在它們用線表示的相同索引處連接頂點。這條線本身可能會被簡化，因為我們知道它的長軸不會改變，但是為了簡單起見，我使用了普通的 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 迭代之外移動剪輯也可以大大提高性能。
這里預覽三角形相交圓柱：
在這里預覽使用此三角形光柵化的材料去除：
橙色三角形不是體素，它只是疊加，體素不是直接渲染，而是從體素網格中減去，而不是在影片期間移除材料......
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/526597.html
標籤：C 算法3d体素光栅化
上一篇：為什么復雜度為O(n^2)？
下一篇：陣列中的隨機唯一元素