2/26/2009

02-26-09 - Tech Image Series 4

This is a video I just made based on the earlier post on removing triangles from images .

Lena Triangle Removal video on Youtube.

BTW logarithmic speed everything FTW.

Kudos : fraps just fucking works, wow. (well, the onscreen FPS display crashes my app with a kernel fault, but once I turned that off it just worked, yay). I compressed the video with VirtualDub and xvid and that was surprisingly easy too.

WTFs : Youtube's new video player is the suck. No I don't want to add speech bubbles. What I would like is to be able to scrub the framerate slider and have it actually stop where I click instead of jumping around bizarrely making it impossible for me to pick out frames.

Lots of the frames at the end get a cool art-deco look ; it reminds me of the opening title graphics for Poirot.


On a semi-related note : while I was fiddling with this stuff I got sick of the retarded vert snapper I have in Galaxy and just switched to a hash-based snapper. Galaxy used to have a sort-axis based vert snapper using the dominant axis to make a linear order then just searching neighbors in that order. That works perfectly fine for most meshes (eg. bunny, horse, etc.) but it turns into N^2 hell for some degenerate cases (such as regular grids, aka images!).

Now I know many other people have blogged about this exact topic before, it's not anything new. I was just thinking about why I did the sort originally. There were two factors, one real and one foolish.

The foolish one was the standard young programmer's fallacy that "the STL is slow" and "big heavy structures are slow". Retarded.

The real one was that the sort uses almost zero extra memory, and hash_map is in fact really fat and memory wasteful. When I wrote Galaxy I had something like 256 M of RAM and I was trying to work on 1M+ poly meshes which meant I was always right on the brink of running out of memory, so I did try hard in some spots to keep memory use low (though I also retardedly wasted memory in other spots). Anyhoo, that need is largely gone now so hash_map it up !

Here is the only actually interesting bit of the code. For each vertex you have to look up 8 hash cells (cells are an integer quantization of the vert position). Verts you snap to could be in your cell or a neighbors, but you only need to look in neighbors that are on the side that you are off-center of your cell :


for(int search=0;search<8;search++)
{
    gVec3i searchv = iv;
    if ( search & 1 ) searchv.x += (orig.x >= ivCenter.x) ? 1 : -1;
    if ( search & 2 ) searchv.y += (orig.y >= ivCenter.y) ? 1 : -1;    
    if ( search & 4 ) searchv.z += (orig.z >= ivCenter.z) ? 1 : -1;

    t_hash::const_iterator it = verthash.find(searchv);
    ...

And actually it's less than that - if you are not within the snap distance of a side of your cell you don't need to look in that direction at all. I set cellCenterNoSnap = cellHalfWidth - snapDist then do :

for(int search=0;search<8;search++)
{
    gVec3i searchv = iv;
    if ( search & 1 ) 
    {
        float d = orig[0] - ivCenter[0];
        if ( d > cellCenterNoSnap ) searchv[0] ++;
        else if ( d < -cellCenterNoSnap ) searchv[0] --;
        else continue; // near center, no neighbor check needed
    }
    if ( search & 2 ) 
    {
        float d = orig[1] - ivCenter[1];
        if ( d > cellCenterNoSnap ) searchv[1] ++;
        else if ( d < -cellCenterNoSnap ) searchv[1] --;
        else continue; // near center, no neighbor check needed
    }
    if ( search & 4 ) 
    {
        float d = orig[2] - ivCenter[2];
        if ( d > cellCenterNoSnap ) searchv[2] ++;
        else if ( d < -cellCenterNoSnap ) searchv[2] --;
        else continue; // near center, no neighbor check needed
    }

    t_hash::const_iterator it = verthash.find(searchv);
    ...

Anyway, this all just screams at me that we are now into the age of O(N). The multiplier in front matters less and less as we continue to ever larger workloads. If your O(N) is not optimal you will lose. Then you can worry about the constant turn in front of the big-O, but hell you probably won't need to do that either.

1 comment:

cbloom said...

http://i629.photobucket.com/albums/uu19/THEKID_photo_01/1237468591371.png?t=1237474016

old rants