The easiest way, according to the comp.graphics faq, is to take the rotation transformation and invert it. Then you just iterate over the destination image, apply this inverse transformation and find which source pixel to copy there.
A much nicer way comes from the observation that the rotation matrix:
R(T) = { { cos(T), -sin(T) }, { sin(T), cos(T) } }
is formed my multiplying three matrices, namely:
R(T) = M1(T) * M2(T) * M3(T)
where
M1(T) = { { 1, -tan(T/2) },
{ 0, 1 } }
M2(T) = { { 1, 0 },
{ sin(T), 1 } }
M3(T) = { { 1, -tan(T/2) },
{ 0, 1 } }
Each transformation can be performed in a separate pass, and because these transformations are either row-preserving or column-preserving, anti-aliasing is quite easy.
| Another fast approach is to perform first a column-preserving roation, | and then a row-preserving rotation. For an image W pixels wide and | H pixels high, this requires W+H BitBlt operations in comparison to | the brute-force rotation, which uses W*H SetPixel operations (and a | lot of multiplying).
Reference:
Paeth, A. W., "A Fast Algorithm for General Raster Rotation", Proceedings Graphics Interface '89, Canadian Information Processing Society, 1986, 77-81 [Note - e-mail copies of this paper are no longer available]
[Gems I]
[Gems I] pp. 287-293, "A Simple Method for Color Quantization: Octree Quantization"
B. Kurz. Optimal Color Quantization for Color Displays. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 1983, pp. 217-224.
[Gems II] pp. 116-125, "Efficient Inverse Color Map Computation"
This describes an efficient technique to map actual colors to a reduced color map, selected by some other technique described in the other papers.
[Gems II] pp. 126-133, "Efficient Statistical Computations for Optimal Color Quantization"
Xiaolin Wu. Color Quantization by Dynamic Programming and Principal Analysis. ACM Transactions on Graphics, Vol. 11, No. 4, October 1992, pp 348-372.
"A Fast Algorithm for the Restoration of Images Based on Chain Codes Description and Its Applications", L.W. Chang & K.L. Leu, Computer Vision, Graphics, and Image Processing, vol.50, pp296-307 (1990)
"An Introductory Course in Computer Graphics" by Richard Kingslake, (2nd edition) published by Chartwell-Bratt ISBN 0-86238-284-X
[Gems I] [Foley] [Hearn]
A simple method is to put the bitmap through the filter:
-1 -1 -1 -1 8 -1 -1 -1 -1
This will highlight changes in contrast. Then any part of the picture where the absolute filtered value is higher than some threshold is an "edge".
A more appropriate edge detector for noisy images is described by Van Vliet et al. "A nonlinear Laplace operator as edge detector in noisy images", in Computer Vision, Graphics, and image processing 45, pp. 167-195, 1989.
Sharpening of bitmaps can be done by the following algorithm:
I_enh(x,y) = I_fuz(x,y)-k*Laplace(I_fuz(x,y))
or in words: An image can be sharpened by subtracting a positive fraction k of the Laplace from the fuzzy image.
The Laplace is the kernal:
1 1 1
1 -8 1
1 1 1
The following library implements Fast Gaussian Blurs:
MAGIC: An Object-Oriented Library for Image Analysis by David Eberly
The library source code and the documentation (in Latex) are at http://www.magic-software.com/ The code compiles on Unix systems using g++ and on PCs using Microsoft Windows 3.1 and Borland C++. The fast Gaussian blurring is based on a finite difference method for solving s u_s = s^2 \nabla^2 u where s is the standard deviation of the Gaussian (t = s^2/2). It takes advantage of geometrically increasing steps in s (rather than linearly increasing steps in t), thus getting to a larger "time" rapidly, but still retaining stability. Section 4.5 of the documentation contains the algorithm description and implementation.
A bitmap is a sampled image, a special case of a digital signal, and suffers from two limitations common to all digital signals. First, it cannot provide details at fine enough spacing to exactly reproduce every continuous image, nor even more detailed sampled images. And second, each sample approximates the infinitely fine variability of ideal values with a discrete set of ranges encoded in a small number of bits---sometimes just one bit per pixel. Many times bitmaps have another limitation imposed: The values canot be negative. The resolution limitation is perhaps most important.
The ideal way to enlarge a bitmap is to work from the original continuous image, magnifying and resampling it. The standard way to do it in practice is to (conceptually) reconstruct a continuous image from the bitmap, and magnify and resample that instead. This will not give the same results, since details of the original have already been lost, but it is the best approach possible given an already sampled image. More details are provided below.
Both sharpening and fuzzing are examples of filtering. Even more specifically, they can be both be accomplished with filters which are linear and shift invariant. A crude way to sharpen along a row (or column) is to set output pixel B[n] to the difference of input pixels, A[n]-A[n-1]. A similarly crude way to fuzz is to set B[n] to the average of input pixels, 1/2*A[n]+1/2*A[n-1]. In each case the output is a weighted sum of input pixels, a "convolution". One important characteristic of such filters is that a sinusoid going in produces a sinusoid coming out, one of the same frequency. Thus the Fourier transform, which decomposes a signal into sinusoids of various frequencies, is the key to analysis of these filters. The simplest (and most efficient) way to handle the two dimensions of images is to operate on first the rows then the columns (or vice versa). Fourier transforms and many filters allow this separation.
A filter is linear if it satisfies two simple relations between the input and output: scaling the input by a factor scales the output by the same factor, and the sum of two inputs gives the sum of the two outputs. A filter is shift invariant if shifting the input up, down, left, or right merely shifts the output the same way. When a filter is both linear and shift invariant, it can be implemented as a convolution, a weighted sum. If you find the output of the filter when the input is a single pixel with value one in a sea of zeros, you will know all the weights. This output is the impulse response of the filter. The Fourier transform of the impulse response gives the frequency response of the filter. The pattern of weights read off from the impulse response gives the filter kernel, which will usually be displayed (for image filters) as a 2D stencil array, and it is almost always symmetric around the center. For example, the following filter, approximating a Laplacian (and used for detecting edges), is centered on the negative value.
1/6 4/6 1/6
4/6 -20/6 4/6
1/6 4/6 1/6
Ideal blurring is uniform in all directions, in other words it has circular symmetry. Gaussian blurs are popular, but the obvious code is slow for wide blurs. A cheap alternative is the following filter (written for rows, but then applied to the columns as well). B[i][j] = ((A[i][j]*2+A[i][j-1]+A[i][j+1])*4 +A[i][j-1]+A[i][j+1]-A[i][j-3]-A[i][j+3])/16 For sharpening, subtract the results from the original image, which is equivalent to using the following. B[i][j] = ((A[i][j]*2-A[i][j-1]-A[i][j+1])*4 -A[i][j-1]-A[i][j+1]+A[i][j-3]+A[i][j+3])/16 Credit for this filter goes to Ken Turkowski and Steve Gabriel.
Reconstruction is impossible without some assumptions, and because of the importance of sinusoids in filtering it is traditional to assume the continuous image is made of sinusoids mixed together. That makes more sense for sounds, where signal processing began, than it does for images, especially computer images of character shapes, sharp surface features, and halftoned shading. As pointed out above, often image values cannot be negative, unlike sinusoids. Also, real world images contain noise. The best noise suppressors (and edge detectors) are, ironically, nonlinear filters.
The simplest way to double the size of an image is to use each of the original pixels twice in its row and in its column. For much better results, try this instead. Put zeros between the original pixels, then use the blurring filter given a moment ago. But you might want to divide by 8 instead of 16 (since the zeros will dim the image otherwise). To instead shrink the image by half (in both vertical and horizontal), first apply the filter (dividing by 16), then throw away every other pixel. Notice that there are obvious optimizations involving arithmetic with powers of two, zeros which are in known locations, and pixels which will be discarded.
Paul S. Heckbert, "Survey of Texture Mapping", IEEE Computer Graphics and Applications V6, #11, Nov. 1986, pp 56-67 revised from Graphics Interface '86 version
Eric A. Bier and Kenneth R. Sloan, Jr., "Two-Part Texture Mappings", IEEE Computer Graphics and Applications V6 #9, Sept. 1986, pp 40-53 (projection parameterizations)
[Currently empty entry.]
ftp://oak.oakland.edu/SimTel/msdos/graphics See also James Murray's graphics file formats FAQ: http://www.ora.com/centers/gff/gff-faq/index.htm
See [Anderson], Chapter 3, page 59 - 90.
The easiest way is to render each line separately into an edge buffer. This buffer is a structure which looks like this (in C):
struct { int xmin, xmax; } edgebuffer[YDIM];
There is one entry for each scan line on the screen, and each entry is to be interpreted as a horizontal line to be drawn from xmin to xmax.
Since most people who ask this question are trying to write fast games on the PC, I'll tell you where to find code. Look at:
ftp::/ftp.uwp.edu/pub/msdos/demos/programming/source ftp::/ftp.luth.se/pub/msdos/demos (Sweden) ftp::/NCTUCCCA.edu.tw:/PC/uwp/demos http://www.wit.com:/mirrors/uwp/pub/msdos/demos ftp::/ftp.cdrom.com:/demos
See: ftp://gondwana.ecr.mu.oz.au/pub/siggraph92_C23.shar.gz ftp://ftp.cis.ohio-state.edu/pub/siggraph92/siggraph92_C23.shar
In it there are implementations of Perlin's noise and turbulence functions, (By the man himself) as well as Lewis' sparse convolution noise function (by D. Peachey) There is also some of other stuff in there (Musgrave's Earth texture functions, and some stuff on animating gases by Ebert).
SPD (Standard Procedural Databases) package: ftp://avalon.chinalake.navy.mil/utils/SPD/SPD33f4.tar.Z ftp://avalon.chinalake.navy.mil/utils/SPD/spd33f4.zip. Now moved to http://www.viewpoint.com/
References:
[Ebert] Noise, Hypertexture, Antialiasing and Gesture, (Ken Perlin) in Chapter 6, (p.193-), The disk accompanying the book is available from ftp://archive.cs.umbc.edu/pub/texture.
For more info on this text/code see: http://www.cs.umbc.edu/ ebert/book/book.html
For examples from a current course based on this book, see: http://www.seas.gwu.edu/graphics/ProcTexCourse/
[Watt:Animation] Three-dimensional Nocie, Chapter 7.2.1 Simulating turbulance, Chapter 7.2.2
For fractal mountains, trees and sea-shells:
SPD (Standard Procedural Databases) package: ftp://avalon.chinalake.navy.mil/utils/SPD/SPD33f4.tar.Z ftp://avalon.chinalake.navy.mil/utils/SPD/spd33f4.zip. Now moved to http://www.viewpoint.com/
Reaction-Diffusion Algorithms: For an illustartion of the parameter space of a reaction diffusion system, check out the Xmorphia page at http://www.ccsf.caltech.edu/ismap/image.html
References:
[Ebert] Entire book devoted to this subject, with RenderMan(TM) and C code.
[Watt:Animation] Procedural texture mapping and modelling, Chapter 7
"Generating Textures on Arbitrary Surfaces Using Reaction-Diffusion" Greg Turk, Computer Graphics, Vol. 25, No. 4, pp. 289-298 July 1991 (SIGGRAPH '91) http://www.cs.unc.edu:80/ turk/reaction_diffusion/reaction_diffusion.html
A list of procedural texture synthesis related web pages http://www.threedgraphics.com/pixelloom/tex_synth.html
References: [Watt:3D] pp. 313-354 [Foley] pp. 563-603
"GIF" is an acronymn for "Graphics Interchange Format." Despite the hard "G" in "Graphics," GIF is pronounced "JIF." Although we don't have a direct quote from the official CompuServe specification released June 1987, here is a quote from related CompuServe documentation, for CompuShow, a DOS-based image viewer used shortly thereafter: "The GIF (Graphics Interchange Format), pronounced "JIF", was designed by CompuServe ..." We also have a report that the principal author of the GIF spec, Bob Berry, pronounced it "JIF." Anyone with more definitive evidence should contact the FAQ maintainer.