Floodfill
Hi all,
I've spent the last few hours trying to code a flood fill on an IMAGE_3D, I'm trying to avoid linear scanline floodfills - don't particularly want to be using geometry/physics raycasting on this one. Initially I used a recursive function, but this instantly dies from stack overflow on voxel dimensions larger than 170^3. Stupid idea, moving on:
So I made this:
Code:
void Voxelizer::floodfill(VecI &vox) {
Meml<VecI> queue;
if ( voxDraw.color3D(vox.x, vox.y , vox.z ).a != 0) return; // 0 = target colour (no vox) 255 = replacement colour (vox)
VecI &head = queue.New();
head = vox; // yeah don't need to do this, but testing other stuff..
while (queue.elms()) {
VecI n = queue[0];
if ( voxDraw.color3D(n.x, n.y , n.z ).a != 255) voxDraw.color3DF(n.x, n.y, n.z, Vec4(getPosFromVoxel(n), 255));
queue.removeFirst();
if ( voxDraw.color3D(n.x+1, n.y , n.z ).a != 255) { voxDraw.color3DF(n.x+1, n.y, n.z, Vec4(0,0,0, 255)); VecI &t = queue.New(); t=n; t.x+=1; }
if ( voxDraw.color3D(n.x-1, n.y , n.z ).a != 255) { voxDraw.color3DF(n.x-1, n.y, n.z, Vec4(0,0,0, 255)); VecI &t = queue.New(); t=n; t.x-=1; }
//if ( voxDraw.color3D(n.x , n.y+1, n.z ).a != 255) { voxDraw.color3DF(n.x, n.y+1, n.z, Vec4(0,0,0, 255)); VecI &t = queue.New(); t=n; t.y+=1; }
//if ( voxDraw.color3D(n.x , n.y-1, n.z ).a != 255) { voxDraw.color3DF(n.x, n.y-1, n.z, Vec4(0,0,0, 255)); VecI &t = queue.New(); t=n; t.y-=1; }
if ( voxDraw.color3D(n.x , n.y , n.z+1).a != 255) { voxDraw.color3DF(n.x, n.y, n.z+1, Vec4(0,0,0, 255)); VecI &t = queue.New(); t=n; t.z+=1; }
if ( voxDraw.color3D(n.x , n.y , n.z-1).a != 255) { voxDraw.color3DF(n.x, n.y, n.z-1, Vec4(0,0,0, 255)); VecI &t = queue.New(); t=n; t.z-=1; }
}
}
- it works completely in low voxel densities, but notice I commented out the y-dimension. If I uncomment it, my memory fills up at an alarming rate - if I don't press Ctrl+Alt+Delete and force quit the process quickly enough, my entire computer locks out... fun!
But why the freeze and memory jump? I'm not using the stack, just a huge queue. - it works perfectly, uses hardly any memory, then it just dies on me. I tried optimizing the queue (e.g. to search west/east as mentioned in "floodfill" wikipedia - bad reference I know) - but actually the same thing happens.
I think this is the weirdest problem i've ever had to deal with for a long time.
Any suggestions? Meanwhile I'll keep playing with ideas.
|
