Thread: Eliminating gaps in rotated images?

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Eliminating gaps in rotated images?

    So it seems that rotating an image at anything other than multiples of 90 degree angles produces 'gaps' (at least going from 0 - 360). I've spent an hour or so thinking of ways to compensate for it, but I can't really imagine anything other than a really complicated heuristic. Also, are there any angles (perhaps smaller than 1 degree) that can be used to prevent this? Google hasn't been very helpful, either, since I really don't know the technical term is for this problem.

    Any help would be appreciated!

    EDIT:

    Now that I think of it, this a similar problem to alaising; ie, any line drawn at any angle other than modulo 90 degrees on a display is going to appear 'stepped'. So I could probably perform a 'nearest neighbor' type calculation whenever the X or Y coordinate changes.
    Last edited by Sebastiani; 05-20-2009 at 11:00 AM.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  2. #2
    Registered User
    Join Date
    May 2007
    Posts
    147
    There's not enough context in your point for me to reply beyond generality.

    Gaps can be a result of the means by which a model is created. I note that in 3D OpenGL, I generally see no gaps in my own models generated from 3D studio Max or logic.

    When skinning objects, what would be gaps are essentially handled by a texturing technique.

    Since this is somewhat standard knowledge level stuff, it suggest to me that you want to pick up one of the 'classic' texts on the subject of making 3D applications/graphics engines. In typical professional work a graphics engine will be used that takes care of the OpenGL/DirectX specifics rather cleanly, so the level of inquiry you're making suggests either a game engine, rather than application, is what you're making, or you're writing directly to the API from your application code, which is widely recognized as a poor design choice.

    Texts from David Eberly are rather thorough, but there are a great many on the subject. I sounds to me like you are approach or at the point where you will go only so much farther in your project without such reading, and although you may find many answers here and other forums, it will be much, much faster for you if study one of these texts.

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    This isn't for a 3d engine or anything, just mundane image manipulation (processing bitmaps) as part of a simple painting program. But yes, I guess a texture mapper deals with this sort of problem, so I'll look into how one would be implemented.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  4. #4
    Registered User
    Join Date
    May 2007
    Posts
    147
    Sorry, in the context of "game programming" - I didn't read carefully the operative word "image" - I was thinking 3D rotation of solids.


    Yes, image rotation is a pain, but is an anti-aliasing problem, an alignment problem, and if this is a realtime solution you're making, a performance issue.

    Are you processing the image rotation yourself?

    There's an image library called CxImage you might find useful for that. It's for "paint" style programming and has a rather substantial collection of filters and convolutions. It's not longer in development, but reached a "version 5.99" as I recall - rather easy to use.

    There's also a free online library from Adobe, though it's not quite a simple to deploy at first.

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> Are you processing the image rotation yourself?

    Yes, just rotating it pixel-by-pixel.

    >> Yes, image rotation is a pain, but is an anti-aliasing problem, an alignment problem, and if this is a realtime solution you're making, a performance issue.

    Yep, I did eventually find some stuff relating to alaising, and it looks like bilinear interpolation might be the way to go.

    >> There's an image library[...]

    I'm trying to avoid that route, if possible. This appears to be the only transform I'll be having any issues with this particular project (for now, anyway), so I might as well bite the bullet and tackle the problem 'manually' to keep things simple.

    EDIT:
    OK, so I can see how to use BI once I have the pixel to be processed, but I still don't understand how to *detect* the positions of the gaps (inside the rectangle and along the edges) to begin with?
    Last edited by Sebastiani; 05-20-2009 at 05:47 PM.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  6. #6
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    How do you do the rotation? Is it something like:
    "Here's pixel 0,0 of the original. Where does this pixel end up? (equation, get an x,y, and plot at that point) Here's pixel 1,0 of the original..."

    If you're doing something like that, I could see gaps forming. Why not get a bounding box for the rotated image, and then work backwards? (ie, here's 0,0 of the rotated image, which pixel does this correspond to on the original?) You'll still have to choose between nearest-neighbor and some sort of interpolation, but that's another decision...
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> How do you do the rotation? Is it something like: [...] If you're doing something like that, I could see gaps forming

    Right. At first, it hadn't even occured to me that rotating the image would lead to gaps, so I was just rotating each pixel as I iterated through the image, thinking I would get full coverage.

    >> Why not get a bounding box for the rotated image, and then work backwards?

    Aha! I think you're onto something there.

    Come to think of it, I can't see how it *wouldn't* work. I'll give it a go. Thanks.
    Last edited by Sebastiani; 05-20-2009 at 08:03 PM. Reason: spelilng
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  8. #8
    Registered User
    Join Date
    May 2007
    Posts
    147
    Part of my point in suggesting CxImage is that you'll have the source for some near Photoshop quality rotation algorithms in source code.

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Rotate the box, scan convert the box. Same as what any 3D video card will be doing for quads.

  10. #10
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Use meshes instead of multiple independant polygons. Most hardware has routines built in that make sure convergent edges look convergent, i.e. no gaps.

  11. #11
    Registered User
    Join Date
    May 2007
    Posts
    147
    Most hardware has routines built in that make sure convergent edges look convergent
    Quite true, but that would imply using either DirectX or OpenGL (which is a good idea), but the OP is writing this convolution in code, indicating it is performed on a bitmap in RAM, and may not target display only - might be saved to a file for all I can tell.

    However, this point should be considered. In OpenGL, for example, if you display your bitmap as a texture on a 2D rectangle, you can supply a rotation matrix to OpenGL and let it do all this for you (quite well, I might add).

  12. #12
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Well, it worked. There are still some kinks to work out (the edges especially may need additional filtering), but overall I think the results look pretty good. I even rotated the image through every angle (from 0 to 359 degrees) just to be sure, and it does indeed retain a smooth appearance.

    Bilinear interpolation isn't perfect, of course, but most of the other filters that I've looked at that supposedly do a better job at it (such as sinc) are either too computationally expensive or else just too complicated to grok (without a P.H.D., at least).

    Thanks to everyone for your input. And CactusHugger...I think I owe you a beer.

    Below is a comparison (pared down, due to CBoard size limits) of an image rotated through 56 degrees, with and without the filter.
    Last edited by Sebastiani; 05-21-2009 at 09:57 AM.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    You cannot perform an affine transform by mapping INPUT points to OUTPUT points -- you will have gaps.

    You must map OUTPUT points to INPUT points, and make some kind of decision how to select the source pixel from the transformed source point -- either nearest neighbor or some form of interpolation.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. mirroring website with images on external host
    By cyberfish in forum Tech Board
    Replies: 1
    Last Post: 09-08-2008, 06:50 PM
  2. CBitmap + big images = bad?
    By dug in forum Windows Programming
    Replies: 18
    Last Post: 06-28-2003, 11:53 PM
  3. Images
    By gvector1 in forum C++ Programming
    Replies: 7
    Last Post: 02-25-2003, 09:59 AM
  4. STL, Queues And Images
    By simly01 in forum C++ Programming
    Replies: 3
    Last Post: 06-24-2002, 12:31 PM
  5. A simple question on Images....
    By LonelyPlanetWa in forum C Programming
    Replies: 7
    Last Post: 05-20-2002, 07:34 AM