About Store Forum Documentation Contact
Donations:
207$/mo



Post Reply 
Floodfill
Author Message
Chris Offline
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<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.
09-09-2010 12:41 PM
Find all posts by this user Quote this message in a reply
Esenthel Offline
Administrator

Post: #2
RE: Floodfill
when you're checking each neighbour like this
if ( voxDraw.color3D(n.x+1, n.y , n.z ).a != 255)

you don't check if the new coordinates actually belong to the voxDraw image
InRange(n.x+1,voxDraw.x())

if coordinates are out of range, color3D and other color functions return color with 0,0,0,0 components

also color3D is faster than color3DF
and for Vec4 you shouldnt set 255 alpha but 1.0f
09-09-2010 01:28 PM
Find all posts by this user Quote this message in a reply
Chris Offline
Member

Post: #3
RE: Floodfill
I don't believe it, you were right! Rather than crashing, I just had a big black cube appear smile

I assumed it was "watertight", shouldn't have stayed up this late, thank you so much *goes and re-checks previous rasterizer function*
09-09-2010 01:43 PM
Find all posts by this user Quote this message in a reply
Post Reply