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.

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.

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.

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.

>> 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?

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...

>> 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.

Part of my point in suggesting CxImage is that you'll have the source for some near Photoshop quality rotation algorithms in source code.

Rotate the box, scan convert the box. Same as what any 3D video card will be doing for quads.

Use meshes instead of multiple independant polygons. Most hardware has routines built in that make sure convergent edges look convergent, i.e. no gaps.

Quote:

---

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).

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. :p

Below is a comparison (pared down, due to CBoard size limits) of an image rotated through 56 degrees, with and without the filter.

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.