Floodfill Author Message
Chris
Member

 Post: #1 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 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.
09-09-2010 12:41 PM
Esenthel