Scott is the president of Wild Duck, a software publishing and development company in Rohnert Park, California. He is also the author of the animation program Fantavision, and the recently released book Morphing Magic from SAMS. He can be reached at 73710,1055 on CompuServe.
Morphing has become almost as ubiquitous as bubble-gum under theater seats. As the July 1993 issue of Dr. Dobb's Journal illustrated, from autos turning into tigers to bulls into bears, we see examples of morphing everywhere on television and in movies. While the effect is compelling, morphing is useful beyond the magical transformations we've grown used to seeing.
This article examines the history and mathematics behind morphing, and includes three utility programs that allow you to run full-screen animated morphs on your PC.
Morphing is a blend of three separate algorithms: warping, tweening, and dissolving. Warping is the mathematical trick of stretching and squashing an image as if it were painted on rubber. This article discusses an implementation of one of the latest warping routines, based on the method used by Pacific Data Images (PDI) to make the Michael Jackson video "Black or White." The algorithm uses lines to control the warping. Lines make the warping specification much easier than using points, giving the artist a break.
Tweening is short for in-betweening, the interpolation of two images to yield a smooth-flowing animation. Tweening is typically done with points, lines, or polygons. Since this warping algorithm is line oriented, tweening fits right in. By tweening the position of the control lines, you can smoothly warp an image around. With warping and tweening alone, you can create photorealistic animations from single photographs. And it's simple to do. (For more details, see my book Morphing Magic, SAMS, 1993.)
Dissolving, or cross-dissolving, is Hollywood-speak for fading out one scene while fading in the next. In the middle, you have a double exposure. This powerful effect was used in the early Wolfman movies. While poor Lon Chaney, Jr. stuck his head in a vice, makeup people swarmed about, adding hair and putty. After each little change in makeup was completed, another few frames of film were squeezed off. Each short take was cross-dissolved with the previous one to complete the illusion.
When you put all three of these effects together, you end up with morphing. Here's how it works. Let's say you want to morph yourself into a tiger. On the first frame of your self-portrait, you mark the key areas with lines. You might place a control line from one eye to the other, down the nose, and across the lips. These three lines capture the most important aspects of a face. Then, on the tiger's ferocious countenance, you would draw control lines on the same features: eyes, nose, and mouth. That's enough information for the computer to morph the two. To create a single morph in the middle, the control lines are tweened halfway and then the images are warped to follow the new lines. The algorithm warps your face midway to the tiger, and warps the tiger midway to you. This is the fifty-fifty interpolation between the two sets of control lines--the central tween. It is also simply the average of the two sets.
After creating the two warped images, the routine cross-dissolves them, finally producing the morph. If you use more tweens, say ten interpolations between you and the tiger, you can make a smoothly animated sequence of you turning into the tiger. The first frame uses 10 percent of the tiger mixed with 90 percent of you. The second frame has 20 percent of the tiger with 80 percent of you. By the ninth frame, there is 90 percent tiger, and you have faded out to 10 percent.
There are as many ways to warp as there are sort routines. The method employed here is a variation on the PDI line method. As I mentioned before, this approach is friendly to the artist. Other routines use dots to warp the image. These changes are local and act only over a short distance, so you need hundreds of them. Misplacing some of these dots and ruining the warp isn't at all difficult. With the new method, each line represents the string of points that compose it, so a few short lines can stand in for hundreds of points. As you move a control line, the pixels around it are pulled as well.
One of the interesting peculiarities of this algorithm is the global nature of the warping. A single line can specify any combination of scaling, translation, and rotation. This can be a nice effect in itself. Just draw, say, a vertical line, rotate it 90 degrees, and the image will also be rotated. When there are more lines (as there usually are), they will each compete for influence, but the effect will still be global. The downside is that it takes a little longer to perform the warping.
In the algorithm presented here, the influence of the line falls off as 1/distance2. This is just like the influence of gravity, but you can select any variation on this that you desire. This formulation was chosen based largely on speed considerations. A mathematical discussion of the warping algorithm is in the text box entitled, "Warping with Control Lines." The basic warping algorithm is as follows:
The second piece of the morphing trio is tweening. Compared with warping, tweening is a piece of cake. In the simplest case of linear tweening, all you do is interpolate. Linear interpolation is just finding a point on the line connecting two others. Although there are dozens of ways to interpolate, for our purposes linear tweening is just fine. All we do is take the lines describing the source image and tween them into the lines describing the target. For each intermediate tween, we warp the images accordingly.
For speed, divide the distance between the points into as many steps as you desire, say ten. You will have an X and a Y component for the length of these segments, called "deltas." For a regular division of the line, all these deltas will be equal to one-tenth of the line distance, so you only need to calculate it once and then simply add it to the starting point. After ten additions of this delta, you will have arrived at the target point. The deltas are given by the simple equations in Figure 3. Adding a delta in this fashion is fast, but care must be taken to avoid round-off errors.
Now we are at the third and final part of morphing, the dissolve. This is where you combine the two images you are warping and tweening. Mix any two colors just the way you might expect. The color midway between two colors is given by the formulas in Figure 4. On a 24-bit color system, the color you get from this calculation will always be another color you can display. Not so with color-mapped graphics cards. You can easily derive a color that isn't in the puny list of displayable colors called the "palette." The best most VGA cards can offer is 256 colors, which is pretty sad for this application.
To fix this you need to calculate all the colors as if you had 24 bits to play with. Then, you need to create a new palette that uses the 256 most popular colors. The rest of the colors must be forced into the closest color available from those 256. This process is referred to as "palette mapping."
So dissolving, which should be the smallest part of this whole algorithm, suddenly swells into an unsightly carbuncle on this otherwise straightforward code. Those are the basics of morphing. There are many different algorithms for performing this terrific effect, but this should serve as a good jumping-off point for further experimentation.
So that you can experiment, I've included three programs: MORPH.C (Listing Three, page 77), LOAD.C (Listing Four, page 78), and FIX.C (Listing Five, page 78). The header containing the #defines for all three of these utilities is in Listing Two, page 76. MORPH gets the user input and creates the morphing sequence, FIX finds a good palette and LOAD plays the sequence back from memory. All the programs work with PCX files having 256 colors and 320x200 resolution. You can capture your own PCX files with any screen-capture program, or you can find GIF images on CompuServe and convert them with a program such as ZSoft's Paint Shop. Remember to convert the number of colors to 256. If you have access to a scanner, then your troubles are over. You can scan in your own photos and magazine clips and go from there.
When specifying a PCX file, you don't need to type in the file extension. The programs automatically append ".PCX" to the end of each filename, saving you the trouble.
Some of these programs produce a numbered sequence of output files. These are also PCX files. The maximum sequence size is 99. The sequence number, from 1 to 99, is appended to the root name of the file sequence. This takes two characters away from the already-tiny DOS allotment of eight. Therefore, the <OutFile> name must be six characters or less.
Figure 5 shows the syntax used on the command line to call the MORPH program. MORPH first reads the two input files: the source and target PCX images. Then it looks on the disk for any existing control lines that might be associated with the source or target image. If the user okays it, these line files are loaded in. Otherwise, the user creates a new set of control lines from scratch, and these are saved to the disk. Morph metamorphoses between the two in the given number of steps, to make a sequence of files. The files are numbered and can be displayed by the LOAD program. As an example, issuing the command line MORPH JIM BOB will cause MORPH to load the files JIM.PCX and BOB.PCX. It will create the middle tween and display it. No files are created. However, MORPH JIM BOB 7 will load the files JIM.PCX and BOB.PCX, create a sequence of seven frames, and display them. No files are created. Finally, MORPH JIM BOB 7 JIMBOB will also load JIM.PCX and BOB.PCX and create a sequence of seven frames. Each frame is displayed while it is saved to the disk. The files will be named JIMBOB1.PCX, JIMBOB2.PCX, and so on.
Figure 6 shows the syntax used to call the LOAD program. LOAD reads a sequence of PCX files indicated by the given name. It reads as many as it can fit into memory, then it displays them sequentially. You can control the playback rate by pressing a number from 1 (slow) to 9 (fast). To single-step through the pictures, press Spacebar. To continue playback, press Enter. To quit, press Esc. The number of images that can be animated depends on how much free RAM you have. Get rid of your TSRs and use the new memory features of DOS 6.0. The best you can do in 640K is about eight images.
The command-line syntax used to call FIX is in Figure 7. FIX takes a sequence created by MORPH and forces each picture in the sequence to have the same palette. FIX then writes the sequence out under the new name. The command FIX JIM FXJIM reads the sequence JIM1.PCX, JIM2.PCX, and so on, outputting the same number of files named FXJIM1.PCX, FXJIM2.PCX, and so. Also, FIX JIM JIM reads the JIM sequence and writes over the original files. Be careful! Make sure you don't need the originals before you do this.
These programs were all compiled with Microsoft C/C++ 7.0. If you didn't include the graphics library when you installed your compiler, you will need to link that library in at compile time. I've included a makefile, which is available electronically; see "Availability," page 2. The makefile is set up assuming that you haven't installed the graphics library. If you have installed the graphics library, then you'll have to modify this makefile accordingly.
To make the programs work with other C compilers, you will probably need to make some changes to the non-ANSI library calls. In Microsoft C, these library calls are prefixed with the underscore character. The non-ANSI library calls are all in IO.C (available electronically) and LINECALC.C (Listing One).
The most obvious upgrade to this program is the ability to use extended RAM, so you can hold more frames in memory. If you have access to some of the new software on the market that attempts to leap the 640K barrier, use it. If you can work with smaller images, say, quarter-screen, 160x100 resolution, you should be able to quadruple the number of frames that can be held in memory, not to mention speeding up the animation. The display-picture routines you need to change are in Listing Five. Currently, they slam a continuous string of bytes into memory. For smaller screens, you will need to move the image a line at a time.
If you have a true-color card, you don't need the agonizing color-collapsing routines from Listing Six (page 79). Just yank them all out. You will need to save the files in 24-bit color mode, which can present some data problems, so look at the drivers and documentation for your particular graphics card.
With these programs, you can create some amazing morphs. With a video capture board and a computer capable of displaying 30 frames per second, you can output to videotape. Now you can play with some of the same toys they have at Industrial Light and Magic and Pacific Data Images. Have fun!
distance = getSourceLoc(&orig,origline,warp,warpline); weight = 1/(.001+distance*distance); deltaSumX += (orig.x - warp->x) * weight; deltaSumY += (orig.y - warp->y) * weight;
DeltaX = (TargetX - SourceX) / (Tweens + 1) DeltaY = (TargetY - SourceY) / (Tweens + 1)
NewRed = (SourceRed + TargetRed) / 2 NewGreen = (SourceGreen + TargetGreen) / 2 NewBlue = (SourceBlue + TargetBlue) / 2
MORPH <File1> <File2> [<Steps> [<OutFile>]] <File1> is the name of the source PCX file to morph. <File2> is the name of the target PCX file. <Steps> is the optional number of output files. If you don't specify the number of steps in your sequence, the program produces one in-between morph. You must specify <Steps> if you want to output files. <OutFile> is the root name of the optional output files. The value of <Steps> determines the number of files to output. The step number is appended to the root name, so the <OutFile> name must be six characters or less.
LOAD <File> <File> is the root name of a PCX sequence to display.
FIX <InFile> <OutFile> <InFile> is the root name of the PCX sequence to fix. <OutFile> is the root name of the fixed PCX sequence.
A History of Warping
Warping's history reaches back to the '60s space program, when NASA was snapping shots of the earth like an eager tourist. But when it came time to put all the pictures together, NASA discovered that nothing quite lined up correctly because of the different altitudes, angles, times, and optics for each shot. Consequently, researchers at NASA developed algorithms that treated the digitized data as points on a polynomial surface that could be stretched to fit a set of reference points. They called their efforts image registration. Those marvelous Landsat pictures were thus stretched and pulled into a big quilt of pictures blanketing the globe. This was a great start for a little warping routine.
Warping was dusted off in the mid-seventies, when Viking 2 landed on Mars. Unfortunately, Viking came to rest at an angle, with its camera pointing down. The landscape it depicted looked like the Big Valley, with the horizon strongly curved. All the images of Mars were pushed through a warping algorithm that corrected for the odd optics before the public ever saw them.
Warping has found its way into the medical world, too. In a procedure called "digital subtraction angiography," an X-ray of a patient is taken before and after the injection of a dye into the area of interest. By subtracting the first image from the second, everything is removed but the dyed arteries. This uncluttered image is of great value to the diagnostician. Unfortunately, if the patient moves, the effect is wrecked. And, except for tree surgeons, moving patients are the norm. As you might have guessed, warping is the perfect tool to ensure registration.
-- S.A.
Warping with Control Lines
Given point P in the source image, you want to deduce point P' in the target image (see Figure 1). The distance d is the projection of vector AP on the perpendicular, which yields |AP| cos a, where |AP| represents the magnitude of the vector. The dot product of vector AP with the perpendicular to AB (denoted ^AB) is defined in Example 1(a), where |AP| and |AB| are the magnitudes, and the subscripted variables are the x and y components of the vectors. You can see that this solution in terms of components, (APx*^ABx+APy*^ABy), doesn't involve any trigonometry. Example 1(b) solves for d.
The magnitude of the line itself, |AB| is used instead of the magnitude of the perpendicular, |^AB|. The reason is that these two are equal, and you can reuse this number. The vector dot product allows you to calculate the desired values without computing any angles or using any transcendental functions. That makes it both simple and fast. From Figure 1, note that the distance represented by f is the projection of AP on AB itself, |AP| cos b, which is the quantity: (AP_AB)/|AB|. We want the fractional part of line AB, so we divide by the length of AB again as shown in Example 1(c).
Examples 1(b) and 1(c) represent a translation into a new-scaled orthogonal coordinate system based on d and f, instead of x and y. Now you are ready to transfer these two important relationships over to the new line, A'B'. The fractional part, the "f-axis," is simply the fractional part of the new line, A'B': f*A'B' Next, apply the distance to the "d-axis," which is perpendicular to the new line. The unit d-vector is (^A'B')/|A'B'|. So, with the new origin at A', the source pixel P (represented as a vector from the origin) is transformed into the destination pixel P'; see Example 1(d). This algorithm uses the relationship a point has with the original line and applies it to the new line. To be of real use, however, you need more lines. They all have to compete for pixels. As mentioned in the text, this implementation uses a weighting proportional to one over the distance squared.
In the calculation for two control lines, the distance to the point is computed from each line, and a new pixel is calculated as before. But this time there are two lines and therefore two warped pixels, so some further work is needed. As shown in Figure 8, from the original point P to the new points P1' and P2' there are two displacements, D1 and D2; see Example 1(e). The routine calculates the weighted average of the two displacements to arrive at the final position, P'; see Example 1(f). If there are three lines, there are three displacements to average, and so on. Finally, the general equation for calculating with n lines is shown in Example 1(g).
--S.A.
Copyright © 1994, Dr. Dobb's Journal
Example 1(a): Dot product of vector AP with the perpendicular to AB; (b) solving for d; (c) calculating the fractional part of line AB; (d) transforming the source pixel P into the destination pixel P'; (e) determining the displacements D1 and D2; (f) weighted average of the two displacements; (g) solving for the general case using n lines.
Figure 8: Where two lines contribute influence, the warped point is the weighted average of the displacements D1 and D2.
[LISTING ONE]
/****************************************************************
* FILE: linecalc.c
* DESC: Warping calculations and line-handling functions.
* HISTORY: Created 3/11/1993 LAST CHANGED: 5/ 6/1993
* Copyright (c) 1993 by Scott Anderson
****************************************************************/
/* ----------------------INCLUDES----------------------------- */
#include <conio.h>
#include <stdio.h>
#include <io.h>
#include <math.h>
#include <graph.h>
#include <malloc.h>
#include <memory.h>
#include <string.h>
#include "define.h"
/* -----------------------MACROS------------------------------ */
#define PIXEL(p,x,y) (p->pixmap[y * (long) p->wide + x])
#define SQUARE(x) (((long) x)*(x))
/* ----------------------PROTOTYPES--------------------------- */
/**** line routines ****/
int xorLine(int x1, int y1, int x2, int y2);
int getLine(int *argx1, int *argy1, int *argx2, int *argy2);
int findPoint(LINE_LIST *lineList, int * line, int * point, int x, int y);
int movePoint();
/**** warping and morphing routines ****/
int sumLines(PICTURE *picture, COLOR *color, LINE *origline,
POINT *warp, LINE *warpline);
float getSourceLoc(POINT *orig, LINE *origline, POINT *warp, LINE *warpline);
int setLength(LINE *line);
void setupScreen(PICTURE *pic, int editFlag);
/* ----------------------EXTERNALS---------------------------- */
/* set from last picture loaded */
extern int Xmin, Ymin, Xmax, Ymax;
extern int NumLines;
extern LINE SrcLine[MAX_LINES];
extern LINE DstLine[MAX_LINES];
/* ----------------------GLOBAL DATA-------------------------- */
int TargFlag=0;
/******** These are the basic warping calculations **********/
* FUNC: int sumLines(PICTURE *picture, COLOR *color,
* LINE *origline, POINT *warp, LINE *warpline)
* DESC: Sum and weight the contribution of each warping line
*****************************************************************/
int
sumLines(PICTURE *picture, COLOR *color, LINE *origline,
POINT *warp, LINE *warpline)
{
int x, y;
float weight, weightSum;
float distance;
int line;
POINT orig;
int paletteIndex;
float deltaSumX = 0.0;
float deltaSumY = 0.0;
/* if no control lines, get an unwarped pixel */
if (NumLines == 0)
orig = *warp;
else {
weightSum = 0.0;
for (line = 0; line < NumLines; line++, origline++, warpline++) {
distance = getSourceLoc(&orig,origline,warp,warpline);
weight = 1/(.001+distance*distance);
deltaSumX += (orig.x - warp->x) * weight;
deltaSumY += (orig.y - warp->y) * weight;
weightSum += weight;
}
orig.x = warp->x + deltaSumX / weightSum + .5;
orig.y = warp->y + deltaSumY / weightSum + .5;
}
/* clip it to the nearest border pixel */
x = clip(orig.x, Xmin, Xmax);
y = clip(orig.y, Ymin, Ymax);
paletteIndex = PIXEL (picture, x, y);
color->r = picture->pal.c[paletteIndex].r;
color->g = picture->pal.c[paletteIndex].g;
color->b = picture->pal.c[paletteIndex].b;
return (paletteIndex);
}
/*****************************************************************
* FUNC: float getSourceLoc(POINT *orig, LINE *origline,
* POINT *warp, LINE *warpline)
* DESC: For a given line, locate the corresponding warped pixel
*****************************************************************/
float
getSourceLoc(POINT *orig, LINE *origline, POINT *warp, LINE *warpline)
{
float fraction, fdist;
int dx, dy;
float distance;
dx = warp->x - warpline->p[0].x;
dy = warp->y - warpline->p[0].y;
fraction = (dx * (long) warpline->delta_x + dy
* (long) warpline->delta_y) / (float) (warpline->length_square);
fdist = (dx * (long) -warpline->delta_y + dy
* (long) warpline->delta_x) / (float) warpline->length;
if (fraction <= 0 )
distance = sqrt(dx*(long) dx + dy * (long) dy);
else if (fraction >= 1) {
dx = warp->x - warpline->p[1].x;
dy = warp->y - warpline->p[1].y;
distance = sqrt(dx*(long) dx + dy * (long) dy);
}
else if (fdist >= 0)
distance = fdist;
else
distance = -fdist;
orig->x = origline->p[0].x + fraction * origline->delta_x -
fdist * origline->delta_y / (float) origline->length + .5;
orig->y = origline->p[0].y + fraction * origline->delta_y +
fdist * origline->delta_x / (float) origline->length + .5;
return distance;
}
/*****************************************************************
* FUNC: int setLength(LINE *line)
* DESC: Set the deltas, the length and the length squared for a given line.
*****************************************************************/
int
setLength (LINE *line)
{
line->delta_x = line->p[1].x - line->p[0].x;
line->delta_y = line->p[1].y - line->p[0].y;
line->length_square = SQUARE(line->delta_x) + SQUARE(line->delta_y);
line->length = sqrt(line->length_square);
}
/********************* The line routines **********************/
* FUNC: int xorLine(int x1, int y1, int x2, int y2)
* DESC: Draw a line on the screen using the XOR of the screen index.
*****************************************************************/
int
xorLine(int x1, int y1, int x2, int y2)
{
int oldcolor = _getcolor();
_setcolor(WHITE); /* Use white as the xor color */
_setwritemode(_GXOR);
_moveto (x1,y1);
_lineto (x2,y2);
_setcolor(oldcolor); /* restore the old color */
}
/*****************************************************************
* FUNC: int getLine(int *argx1, int *argy1, int *argx2, int*argy2)
* DESC: Input a line on the screen with the mouse.
*****************************************************************/
int
getLine (int *argx1, int *argy1, int *argx2, int *argy2)
{
int x1,y1, x2,y2;
int oldx, oldy;
int input;
/* save the current mode */
short old_mode = _getwritemode();
/* get input until we have a real line, not just a point */
do {
/* wait for button or key press */
while (!(input = mousePos (&x1, &y1)));
if (input & KEYPRESS) {
_setwritemode(old_mode);
return 1;
}
oldx=x1, oldy=y1;
hideMouse();
/* prime the pump with this dot */
xorLine (x1, y1, oldx, oldy);
showMouse();
while (input = mousePos (&x2, &y2)) {
/* rubber band a line while the mouse is dragged */
if (x2 != oldx || y2 != oldy)
{
hideMouse();
xorLine (x1, y1, oldx, oldy);
xorLine (x1, y1, x2, y2);
showMouse();
oldx=x2, oldy=y2;
}
}
} while (x1 == x2 && y1 == y2);
*argx1 = x1, *argy1 = y1;
*argx2 = x2, *argy2 = y2;
_setwritemode(old_mode); /* get out of XOR mode */
return (0);
}
/*****************************************************************
* FUNC: int findPoint(LINE_LIST *lineList,int * line,int * point,int x, int y)
* DESC: loop thru dstline and find point within GRAB_DISTANCE,
* return 1 if found, 0 otherwise.
*****************************************************************/
int
findPoint (LINE_LIST *lineList, int * line, int * point, int x, int y)
{
int l, p;
int minl, minp;
long length;
long minlength = SQUARE(640) + SQUARE(480);
for (l = 0; l < lineList->number; l++) {
for (p = 0; p <= 1; p++) {
length = SQUARE(lineList->line[l].p[p].x - x)
+ SQUARE(lineList->line[l].p[p].y - y);
if (length < minlength) {
minlength = length;
minl = l;
minp = p;
}
}
}
if (minlength > GRAB_DISTANCE)
return 0;
*line = minl;
*point = minp;
return 1;
}
/*****************************************************************
* FUNC: int movePoint(LINE_LIST *lineList)
* DESC: Grab a point and move it. Return 1 when key is pressed, else return 0.
*****************************************************************/
int
movePoint(LINE_LIST *lineList)
{
int stuckx, stucky, movex,movey;
int oldx, oldy;
int input;
int line, point;
/* save the current mode */
short old_mode = _getwritemode();
do {
/* keep getting input until we have a mouse button */
while (!(input = mousePos (&movex, &movey)));
if (input & KEYPRESS) {
_setwritemode(old_mode);
return 1;
}
if (!findPoint(lineList, &line, &point, movex, movey)) {
_setwritemode(old_mode);
return 0;
}
/* establish fixed end point */
stuckx = lineList->line[line].p[1-point].x;
stucky = lineList->line[line].p[1-point].y;
oldx=movex, oldy=movey;
hideMouse();
/* erase the old line */
xorLine (stuckx, stucky,
lineList->line[line].p[point].x,
lineList->line[line].p[point].y);
/* and prime the pump with the new line */
xorLine (stuckx, stucky, oldx, oldy);
showMouse();
while (input = mousePos (&movex, &movey)) {
/* rubber band a line while the mouse is dragged */
if (movex != oldx || movey != oldy) {
hideMouse();
xorLine (stuckx, stucky, oldx, oldy);
xorLine (stuckx, stucky, movex, movey);
showMouse();
oldx=movex, oldy=movey;
}
}
} while (stuckx == movex && stucky == movey);
lineList->line[line].p[point].x = movex;
lineList->line[line].p[point].y = movey;
_setwritemode(old_mode); /* get out of XOR mode */
return (0);
}
/*****************************************************************
* FUNC: void createLines(PICTURE *pic, LINE_LIST *lineList)
* DESC: create a list of line segments for a picture
*****************************************************************/
void
createLines(PICTURE *pic, LINE_LIST *lineList)
{
setupScreen(pic, 0); /* set for enter prompt */
initMouse();
showMouse();
for (lineList->number = 0;lineList->number < MAX_LINES;
lineList->number++) {
if (getLine(&lineList->line[lineList->number].p[0].x,
&lineList->line[lineList->number].p[0].y,
&lineList->line[lineList->number].p[1].x,
&lineList->line[lineList->number].p[1].y))
break;
}
hideMouse();
}
/*****************************************************************
* FUNC: void editLines(PICTURE *pic, LINE_LIST *lineList)
* DESC: move around some existing lines
*****************************************************************/
void
editLines(PICTURE *pic, LINE_LIST *lineList)
{
int segment;
setupScreen(pic, 1); /* set for edit prompt */
initMouse();
for (segment = 0; segment < lineList->number; segment++) {
xorLine(lineList->line[segment].p[0].x, lineList->line[segment].p[0].y,
lineList->line[segment].p[1].x, lineList->line[segment].p[1].y);
}
showMouse();
/* move the endpoints around */
while(!movePoint(lineList));
hideMouse();
}
/*****************************************************************
* FUNC: void setupScreen(PICTURE *pic, int editFlag)
* DESC: Print a message introducing the screen, wait for input,
* then set the graphics mode and display the screen.
*****************************************************************/
void
setupScreen(PICTURE *pic, int editFlag)
{
static char *editMess[2] = {"enter", "edit"};
static char *targMess[2] = {"source", "target"};
setTextMode();
_settextposition(VTAB, HTAB);
printf("When you are ready to %s the control lines", editMess[editFlag]);
_settextposition(VTAB+2, HTAB);
printf("for the %s image, press any key.", targMess[TargFlag]);
waitForKey();
setGraphicsMode();
displayPicture(pic);
}
[LISTING TWO]
/****************************************************************
* FILE: define.h
* DESC: These are the main defines for dissolve, warp, morph, load and fix.
* HISTORY: Created 1/11/1993 LAST CHANGED: 5/ 6/1993
* Copyright (c) 1993 by Scott Anderson
****************************************************************/
/* ----------------------DEFINES------------------------------ */
#define ON 1
#define OFF 0
#define MAX_TWEENS 99 /* Maximum tweens (2 digits) */
/* minus 2 digit tween# appended to end */
#define MAX_NAME_SIZE (8-2)
#define HEADER_LEN 128 /* PCX header length */
/* Number of colors in the palette */
#define COLORS 256
/* bytes in palette (COLORS*3) */
#define PALETTE_SIZE (3*COLORS)
/* Maximum number of morphing lines */
#define MAX_LINES 32
/* max number of pixels wide we handle */
#define MAX_WIDE 320
/* max number of pixels tall we handle */
#define MAX_TALL 200
/* Size of screen buffer */
#define MAX_BYTES (MAX_WIDE*(long) MAX_TALL)
/* Number of components per color (RGB) */
#define COMPS 3
/* largest color component value */
#define MAX_COMP 32
/* the midpoint of the colors - for gray */
#define MID_COMP (MAX_COMP/2)
/* enough to handle about 10 different palettes */
#define MAX_FREQ 1023
#define MAX_FILES 10
/* length of a file name including directory */
#define MAX_PATHLEN 80
#define ENTER 13 /* Keyboard values */
#define ESC 27
#define HTAB 18 /* Position for text messages */
#define VTAB 8
/* The mouse button & keyboard constants */
#define NO_BUTTON 0
#define LEFT_BUTTON 1
#define RIGHT_BUTTON 2
#define KEYPRESS 4
/* the square of min dist for grabbing pt */
#define GRAB_DISTANCE 25
/* Some of the graphics colors */
#define BLACK 0
#define WHITE 255
#define EXT_PCX ".PCX" /* pcx file extension */
/* primary line file holder extension */
#define EXT_LINE1 ".LN1"
#define EXT_LINE2 ".LN2" /* aux file for warp lines */
#define ERROR -1 /* General-purpose error code */
typedef enum {
NO_ERROR, /* first entry means everything is ok */
MEMORY_ERR, /* Not enough memory */
READ_OPEN_ERR, /* Couldn't open file for reading */
READ_ERR, /* Trouble reading the file */
WRITE_OPEN_ERR, /* Couldn't open the file for writing */
WRITE_ERR, /* Couldn't write the file */
MOUSE_ERR, /* No mouse driver found */
WRONG_PCX_FILE, /* PCX file format not supported yet */
READ_CONTENTS_ERR /* error in .LN file */
}
ERR;
/* -----------------------MACROS------------------------------ */
#define MIN(a,b) (((a)<(b)) ? (a) : (b))
#define PIXEL(p,x,y) (p->pixmap[y * (long) p->wide + x])
#define SQUARE(x) (((long) x)*(x))
/* ----------------------TYPEDEFS----------------------------- */
typedef struct {
int x,y; /* the screen coordinates of the point */
}
POINT;
typedef struct {
POINT p[2];
}
LINE_SEGMENT;
typedef struct {
int number; /* number of segments to follow */
LINE_SEGMENT line[MAX_LINES];
char *filename; /* name of file holding the line list */
}
LINE_LIST;
typedef struct {
POINT p[2]; /* the endpoints */
int delta_x, delta_y; /* x & y displacement */
float length; /* the precalculated length of the line */
long length_square; /* the length squared */
}
LINE;
typedef struct {
/* red, green, and blue color components */
unsigned char r, g, b;
}
COLOR;
typedef struct {
COLOR c[COLORS]; /* a 256 entry palette */
}
PALETTE;
typedef struct {
int xmin, ymin; /* the upper left corner */
int xmax, ymax; /* the lower right corner */
int wide, tall; /* the width and height */
int pal_id; /* an ID number for each palette */
PALETTE pal; /* the actual palette is here */
unsigned char far *pixmap; /* a pointer to the pixel map */
}
PICTURE;
typedef struct linko {
struct linko *next;
char *str;
}
LINKED_LIST;
/* ----------------------PROTOTYPES--------------------------- */
/**** file handling routines ****/
extern PICTURE *loadPicture(char *filename);
extern int loadPalette(FILE *fp, PALETTE *palette);
extern int getBlock (unsigned char *byte, int *count, FILE *fp);
extern int mustRead(FILE *fp, char *buf, int n);
extern int saveScreen(PALETTE *pal);
extern int putBlock(unsigned char num, unsigned char color, FILE *fp);
extern int writeByte(unsigned char *byte, FILE *fp);
/**** screen and color routines ****/
extern int defaultPalette(PALETTE *palette);
extern int setPalette(PALETTE *palette);
extern int displayPicture(PICTURE *picture);
extern int displayNoPal(PICTURE *picture);
extern int freePicture(PICTURE *pic);
/**** mouse routines ****/
extern int initMouse();
extern int hideMouse();
extern int showMouse();
extern int mousePos(int *x, int *y);
/**** general purpose routines ****/
extern int clip(int num, int min, int max);
extern int quitCheck();
extern void quit(int err, char *name);
extern int wait(int count);
extern int waitForKey();
extern char lineAsk(char *name);
/* ----------------------GLOBAL DATA-------------------------- */
extern int TargFlag;
extern int Key;
[LISTING THREE]
/****************************************************************
* FILE: morph.c
* DESC: Create a metamorphosing sequence between two given images. This
* program lets you specify two files to morph, then prompts you for
* control lines. It uses the lines to warp the underlying images a step
* at a time, combine them, and optionally save them as numbered PCX files.
* HISTORY: Created 1/13/1993 LAST CHANGED: 5/ 6/1993
* Copyright (c) 1993 by Scott Anderson
****************************************************************/
/* ----------------------INCLUDES----------------------------- */
#include <conio.h>
#include <stdio.h>
#include <io.h>
#include <math.h>
#include <graph.h>
#include <malloc.h>
#include <memory.h>
#include <string.h>
#include "define.h"
/* ----------------------DEFINES------------------------------ */
#define MORPH_TWEENS 1
/* ----------------------PROTOTYPES--------------------------- */
int tweenMorph(PICTURE *src, PICTURE *dst);
/* ----------------------EXTERNALS---------------------------- */
/**** color routines ****/
extern int closestColor(int r, int g, int b, PALETTE *palPtr);
extern void collapseColors(PALETTE *palPtr);
/**** line routines ****/
extern int setLength(LINE *line);
extern int sumLines(PICTURE *picture, COLOR *color,
LINE *origline, POINT *warp, LINE *warpline);
/**** io routines ****/
extern LINE_LIST *loadLines(char *filename, char *extension);
extern void saveLines(char *filename,
LINE_LIST *lineList, char *extension);
/***** variables used to compute intermediate images ****/
/* number of colors in tweened image before reduction*/
extern int Ncolors;
/* r, g, b frequency counter array */
extern unsigned int far Freq[MAX_COMP][MAX_COMP][MAX_COMP];
/* tweened images red, grn, and blu components*/
extern unsigned char far Red[MAX_WIDE][MAX_TALL];
extern unsigned char far Grn[MAX_WIDE][MAX_TALL];
extern unsigned char far Blu[MAX_WIDE][MAX_TALL];
extern PALETTE TweenPal; /* resulting palette */
/**** other variables ****/
extern char *OutFilename;
/* set from last picture loaded */
extern int Xmin, Ymin, Xmax, Ymax;
/* ID of palette currently being displayed */
extern int CurrentPal;
/* ----------------------GLOBAL DATA-------------------------- */
PICTURE *Src; /* source & destination picture pointers */
PICTURE *Dst;
LINE SrcLine[MAX_LINES];
LINE DstLine[MAX_LINES];
int Tweens;
int NumLines;
/*****************************************************************
* FUNC: main (int argc, char *argv[])
* DESC: Read in a filename to load
*****************************************************************/
main (int argc, char *argv[])
{
int segment;
LINE_LIST *lineSrcList;
LINE_LIST *lineDstList;
char answer;
/* load the pcx file if one is given */
if ((3 > argc) || (argc > 5)) {
printf("Usage: morph <source><dest> [<steps> [<output>]]\n\n");
printf("Where: <source> is the source PCX filename\n");
printf(" <dest> is the destination filename\n");
printf(" <steps> is the optional sequence size\n");
printf(" (the max is %d, the default is %d)\n",
MAX_TWEENS, MORPH_TWEENS+2);
printf(" <output> is the optional output filename\n");
printf(" (defaults to no output)\n\n");
printf("Note: The output filename can be at most %d
characters long.\n", MAX_NAME_SIZE);
printf(" The PCX extension is added automatically,
so don't\n");
printf(" include it in the filename.\n");
printf(" Morph only accepts PCX files with %d X %d
resolution\n", MAX_WIDE, MAX_TALL);
printf(" and %d colors.\n", COLORS);
exit(0);
}
if (argc > 3) {
/* subtract two from the series count to get the tweens
* since the starting and ending frame are included. */
Tweens = clip (atoi(argv[3]) - 2, 1, MAX_TWEENS);
if (argc > 4)
OutFilename = argv[4];
}
else
Tweens = MORPH_TWEENS;
printf("Loading the file %s\n", argv[1]);
Src = loadPicture(argv[1]);
if (Src == NULL)
quit(MEMORY_ERR, "");
printf("Loading the file %s\n", argv[2]);
Dst = loadPicture(argv[2]);
if (Dst == NULL)
quit(MEMORY_ERR, "");
lineSrcList = loadLines(argv[1], EXT_LINE1);
if (lineSrcList->number != 0) {
if (lineAsk(argv[1]) == 'N')
createLines(Src, lineSrcList);
else
editLines(Src, lineSrcList);
}
else
createLines(Src, lineSrcList);
TargFlag = 1; /* For the screen intro message */
NumLines = lineSrcList->number;
if (NumLines) {
lineDstList = loadLines(argv[2], EXT_LINE1);
/* inconsistent warp target*/
if (lineDstList->number != NumLines)
lineDstList->number = 0;
if (lineDstList->number) { /* ask what he wants to do */
if (lineAsk(argv[2]) == 'N')
lineDstList->number = 0;
}
if (lineDstList->number == 0) { /* create a warp target */
/* copy the source lines */
lineDstList->number = NumLines;
for (segment = 0; segment < NumLines; segment++)
lineDstList->line[segment] = lineSrcList->line[segment];
}
editLines(Dst, lineDstList);
saveLines(argv[1], lineSrcList, EXT_LINE1);
saveLines(argv[2], lineDstList, EXT_LINE1);
beep();
for (segment = 0; segment < NumLines; segment++) {
DstLine[segment].p[0]=lineDstList->line[segment].p[0];
DstLine[segment].p[1]=lineDstList->line[segment].p[1];
setLength(&DstLine[segment]);
SrcLine[segment].p[0]=lineSrcList->line[segment].p[0];
SrcLine[segment].p[1]=lineSrcList->line[segment].p[1];
setLength(&SrcLine[segment]);
}
}
tweenMorph(Src, Dst);
setTextMode();
}
/*****************************************************************
* FUNC: int tweenMorph(PICTURE *src, PICTURE *dst)
* DESC: calculate a pixel to plot, from the warping function
*****************************************************************/
#define TOTAL_WEIGHT (100) /* Good for up to 99 tweens */
tweenMorph(PICTURE *src, PICTURE *dst)
{
int color;
POINT warp;
int x,y;
COLOR scolor, dcolor;
LINE warpLine[MAX_LINES];
int t, i, p;
int r, g, b;
unsigned int srcweight, srcpaletteindex;
unsigned int dstweight, dstpaletteindex;
displayPicture(src);
saveScreen(&src->pal);
/* src is on screen, now tween to the target */
for (t = 1; t <= Tweens; t++) {
/* Tween the lines used to warp the images */
for (i = 0; i < NumLines; i++) {
for (p = 0; p < 2; p++) {
warpLine[i].p[p].x = SrcLine[i].p[p].x +
((DstLine[i].p[p].x - SrcLine[i].p[p].x) * t)
/(Tweens+1);
warpLine[i].p[p].y = SrcLine[i].p[p].y +
((DstLine[i].p[p].y - SrcLine[i].p[p].y) * t)
/(Tweens+1);
}
setLength(&warpLine[i]);
}
dstweight = t * TOTAL_WEIGHT / (Tweens+1);
srcweight = TOTAL_WEIGHT - dstweight;
/* Zero out the buffers */
initFreq();
/* set background to black */
_fmemset(Red, 0, sizeof Red);
_fmemset(Grn, 0, sizeof Grn);
_fmemset(Blu, 0, sizeof Blu);
/* Go through the screen and get warped source pixels */
for (warp.y = Ymin; warp.y <= Ymax; warp.y++) {
if (quitCheck())
quit(0, "");
for (warp.x = Xmin; warp.x <= Xmax; warp.x++) {
sumLines(src, &scolor, SrcLine, &warp, warpLine);
sumLines(dst, &dcolor, DstLine, &warp, warpLine);
r = (scolor.r * srcweight + dcolor.r * dstweight)
/ TOTAL_WEIGHT;
g = (scolor.g * srcweight + dcolor.g * dstweight)
/ TOTAL_WEIGHT;
b = (scolor.b * srcweight + dcolor.b * dstweight)
/ TOTAL_WEIGHT;
if (Freq[r][g][b] == 0) /* A new color */
Ncolors++;
/* Keep it to one byte */
if (Freq[r][g][b] < MAX_FREQ)
Freq[r][g][b]++;
/* put RGB components into temporary buffer */
Red[warp.x][warp.y] = r;
Grn[warp.x][warp.y] = g;
Blu[warp.x][warp.y] = b;
}
}
collapseColors(&TweenPal);
setPalette(&TweenPal);
for (y = Ymin; y <= Ymax; y++) {
if (quitCheck())
quit(0, "");
for (x = Xmin; x <= Xmax; x++) {
color = closestColor( Red[x][y], Grn[x][y],
Blu[x][y], &TweenPal);
_setcolor (color);
_setpixel (x, y);
}
}
/* no output file name on command line */
if (!OutFilename) {
beep();
waitForKey(); /* so pause to enjoy the pictures */
}
else
saveScreen(&TweenPal);
}
if (OutFilename) { /* save the last pic in this series */
CurrentPal = 0; /* force a new palette */
displayPicture(dst);
saveScreen(&dst->pal);
}
}
[LISTING FOUR]
/****************************************************************
* FILE: load.c
* DESC: This program loads a PCX file or a list of them. It crams as
* many into memory as it can, then it flips quickly through them.
* HISTORY: Created 1/13/1993 LAST CHANGED: 3/20/1993
* Copyright (c) 1993 by Scott Anderson
****************************************************************/
/* ----------------------INCLUDES----------------------------- */
#include <conio.h>
#include <stdio.h>
#include <io.h>
#include <math.h>
#include <graph.h>
#include <string.h>
#include "define.h"
/* ----------------------EXTERNALS---------------------------- */
/* External functions */
extern int quitCheck();
extern LINKED_LIST *rootSequence(int argc, char *argv[]);
/* External variables */
extern int Wait;
extern int Key;
extern int EndWait;
/* ----------------------GLOBAL DATA-------------------------- */
PICTURE *Src[MAX_FILES]; /* source picture pointer */
/*****************************************************************
* FUNC: main (int argc, char *argv[])
* DESC: Display the file or sequence passed on the command line. Read in as
* many files as will fit in memory, then display them in a loop.
*****************************************************************/
main (int argc, char *argv[])
{
int file, fileNum;
int direction;
int i;
LINKED_LIST *pcxList;
LINKED_LIST *pcxListHead;
if (argc == 1) {
printf("Usage: load <name>\n\n");
printf("Where: <name> is the root name of a sequence\n");
exit(23);
}
setGraphicsMode();
file = 1;
pcxListHead = rootSequence(argc, argv);
for (pcxList=pcxListHead; pcxList; pcxList = pcxList->next) {
Src[file] = loadPicture(pcxList->str);
if (Src[file] == NULL)
break;
displayPicture(Src[file++]);
}
fileNum = file - 1;
if (fileNum == 1) /* there's only one file */
waitForKey(); /* so wait for the user to quit */
else if (fileNum > 1) {
file = 1;
direction = 1;
while (!(quitCheck())) {
if ((file += direction) >= fileNum)
direction = -1;
if (file <= 1)
direction = 1;
displayPicture(Src[file]);
if (EndWait && (file == 1 || file == fileNum))
wait(Wait);
}
}
/* Reset to original mode, then quit */
setTextMode();
}
[LISTING FIVE]
/****************************************************************
* FILE: fix.c
* DESC: This program inputs a list of pictures, creates a best
* fit palette, remaps the pictures, and writes them out.
* HISTORY: Created 1/13/1993 LAST CHANGED: 3/10/1993
* Copyright (c) 1993 by Scott Anderson
****************************************************************/
/* ----------------------INCLUDES----------------------------- */
#include <conio.h>
#include <stdio.h>
#include <io.h>
#include <math.h>
#include <graph.h>
#include <malloc.h>
#include <memory.h>
#include <string.h>
#include "define.h"
/* ----------------------EXTERNALS---------------------------- */
extern LINKED_LIST *rootSequence(int argc, char *argv[]);
/**** color routines ****/
extern int closestColor(int r, int g, int b, PALETTE *pal);
extern void collapseColors(PALETTE *palPtr);
extern int mergePalette(PICTURE *pic);
extern int remapPicture(PICTURE *picPtr, PALETTE *palPtr);
/**** line routines ****/
extern int getLine(int *argx1, int *argy1, int *argx2, int *argy2);
extern int movePoint();
extern int setLength(LINE *line);
/**** other variables ****/
extern char *OutFilename;
/* set from last picture loaded */
extern int Xmin, Ymin, Xmax, Ymax;
/* ----------------------GLOBAL DATA-------------------------- */
PICTURE *Src; /* source & destination picture pointers */
/***** variables used to compute intermediate images ****/
/* number of colors in tweened image before reduction*/
extern int Ncolors;
/* r, g, b frequency counter array */
extern unsigned int far Freq[MAX_COMP][MAX_COMP][MAX_COMP];
/* tweened images red, grn, and blu components*/
extern unsigned char far Red[MAX_WIDE][MAX_TALL];
extern unsigned char far Grn[MAX_WIDE][MAX_TALL];
extern unsigned char far Blu[MAX_WIDE][MAX_TALL];
extern PALETTE TweenPal; /* resulting palette */
/*****************************************************************
* FUNC: main (int argc, char *argv[])
* DESC: Read in a list of filenames to load, change their palettes
* to the best-fit palette, and write them out.
*****************************************************************/
main (int argc, char *argv[])
{
int file;
LINKED_LIST *pcxList, *pcxListHead;
/* load the pcx file if one is given */
if (argc < 3) {
printf("Usage: fix <infile> <outfile>\n\n");
printf("Where: <infile> is the input sequence name\n");
printf(" <outfile> is the output sequence name\n");
exit(0);
}
OutFilename = argv[argc-1];
initFreq();
pcxListHead = rootSequence(argc-1, argv);
for (pcxList = pcxListHead; pcxList; pcxList=pcxList->next) {
printf("Loading the file %s\n", pcxList->str);
Src = loadPicture(pcxList->str);
if (Src == NULL)
quit(MEMORY_ERR, "");
mergePalette(Src);
freePicture(Src);
}
collapseColors(&TweenPal);
setGraphicsMode();
setPalette(&TweenPal);
for (pcxList = pcxListHead; pcxList; pcxList=pcxList->next) {
Src = loadPicture(pcxList->str);
if (Src == NULL)
quit(MEMORY_ERR, "");
remapPicture(Src, &TweenPal);
displayNoPal(Src);
saveScreen(&TweenPal);
freePicture(Src);
}
setTextMode();
}
[LISTING SIX]
/****************************************************************
* FILE: color.c
* DESC: This file contains the color routines used by morph, dissolve and fix.
* HISTORY: Created 3/18/1993 LAST CHANGED: 5/ 6/1993
* Copyright (c) 1992 by Scott Anderson
****************************************************************/
#include <stdio.h>
#include <memory.h>
#include "define.h"
/* ----------------------DEFINES------------------------------ */
/* ----------------------TYPEDEFS/STRUCTS--------------------- */
/* ----------------------PROTOTYPES--------------------------- */
int closestColor(int r, int g, int b, PALETTE *palPtr);
void collapseColors(PALETTE *palPtr);
int mergePalette(PICTURE *pic);
int remapPicture(PICTURE *picPtr, PALETTE *palPtr);
int initFreq();
/* ----------------------EXTERNALS---------------------------- */
/* set from last picture loaded */
extern int Xmin, Ymin, Xmax, Ymax;
/* ----------------------GLOBAL DATA-------------------------- */
/* number of colors in tweened image before reduction*/
int Ncolors;
/* r, g, b frequency counter array */
unsigned int far Freq[MAX_COMP][MAX_COMP][MAX_COMP];
/* tweened images red, grn, and blu components*/
unsigned char far Red[MAX_WIDE][MAX_TALL];
unsigned char far Grn[MAX_WIDE][MAX_TALL];
unsigned char far Blu[MAX_WIDE][MAX_TALL];
PALETTE TweenPal; /* resulting palette */
/*****************************************************************
* FUNC: void collapseColors(PALETTE *palPtr)
* DESC: Collapse the colors in the Freq table until
* Ncolors < COLORS, then put it in the given color palette.
*****************************************************************/
void
collapseColors(PALETTE *palPtr)
{
int freqCutoff;
int r, g, b;
int index;
int ncolors;
static int freqCount[MAX_FREQ+1];
memset(freqCount, 0, sizeof freqCount);
for (r = 0; r < MAX_COMP; r++)
for (g = 0; g < MAX_COMP; g++)
for (b = 0; b < MAX_COMP; b++)
freqCount[Freq[r][g][b]]++;
ncolors = 0;
for (freqCutoff = COLORS-1; freqCutoff > 1; freqCutoff--) {
ncolors += freqCount[freqCutoff];
if (ncolors > COLORS) break;
}
/* Collapse color space to 256 colors */
r = g = b = 0;
while (Ncolors >= COLORS) {
for (; r < MAX_COMP; r++, g=0) {
for (; g < MAX_COMP; g++, b=0) {
for (; b < MAX_COMP; b++) {
if (Freq[r][g][b] && Freq[r][g][b]
<= freqCutoff)
goto castOut; /* the ultimate no no */
}
}
}
r = g = b = 0;
freqCutoff++;
continue;
castOut:
Freq[r][g][b] = 0; /* just remove this low freq color */
Ncolors--;
}
/* build a palette out of all the remaining non zero freq's */
index = 0;
for (r = 0; r < MAX_COMP; r++)
for (g = 0; g < MAX_COMP; g++)
for (b = 0; b < MAX_COMP; b++)
/* we have a color we need to map */
if (Freq[r][g][b]) {
palPtr->c[index].r = r;
palPtr->c[index].g = g;
palPtr->c[index].b = b;
/* remember index in palette */
Freq[r][g][b] = index;
index++;
}
}
/*****************************************************************
* FUNC: int closestColor(int r, int g, int b, PALETTE *palPtr)
* DESC: return the palette index of the color closest to rgb.
*****************************************************************/
int
closestColor(int r, int g, int b, PALETTE *palPtr)
{
int index;
int distance;
int min_distance = 3200; /* a big number */
int min_index;
/* The value in Freq is now the index into the color table */
if (Freq[r][g][b]) return Freq[r][g][b];
/* If zero, search for the closest color */
for (index = 1; index < Ncolors; index++) {
/* this is really the distance squared, but it works */
distance = SQUARE (r - palPtr->c[index].r) +
SQUARE (g - palPtr->c[index].g) +
SQUARE (b - palPtr->c[index].b);
if (distance < min_distance) {
min_distance = distance;
min_index = index;
if (distance <= 2) break; /* close enough! */
}
}
/* New index - for future reference */
Freq[r][g][b] = min_index;
return min_index;
}
/*****************************************************************
* FUNC: int mergePalette(PICTURE *picPtr)
* DESC: Merge a palette into Freq count table.
*****************************************************************/
int
mergePalette(PICTURE *picPtr)
{
int r, g, b;
unsigned int pos;
unsigned char index;
PALETTE *palPtr = &picPtr->pal;
unsigned char far *bufPtr = picPtr->pixmap;
for (pos = 0; pos < MAX_BYTES; pos++) {
index = *bufPtr++;
r = palPtr->c[index].r;
g = palPtr->c[index].g;
b = palPtr->c[index].b;
if (Freq[r][g][b] == 0) /* A new color */
Ncolors++;
if (Freq[r][g][b] < MAX_FREQ) /* Keep it managable */
Freq[r][g][b]++;
}
}
/*****************************************************************
* FUNC: int remapPicture(PICTURE *picPtr, PALETTE *palPtr)
* DESC: Remap a picture with a different palette.
*****************************************************************/
int
remapPicture(PICTURE *picPtr, PALETTE *palPtr)
{
int x, y;
int index;
int r, g, b;
unsigned int pos;
unsigned char lookup[COLORS];
unsigned char far *bufPtr;
/* Create the cross-reference lookup table */
for (index = 0; index < COLORS; index++) {
r = picPtr->pal.c[index].r;
g = picPtr->pal.c[index].g;
b = picPtr->pal.c[index].b;
lookup[index] = closestColor(r, g, b, palPtr);
}
/* Save the new palette in the picture's palette */
for (index = 0; index < COLORS; index++) {
picPtr->pal.c[index].r = palPtr->c[index].r;
picPtr->pal.c[index].g = palPtr->c[index].g;
picPtr->pal.c[index].b = palPtr->c[index].b;
}
/* Remap the individual pixels to point to the new colors */
for (bufPtr = picPtr->pixmap, pos = 0; pos < MAX_BYTES;
bufPtr++, pos++)
*bufPtr = lookup[*bufPtr];
}
/*****************************************************************
* FUNC: int initFreq()
* DESC: zero out the frequency color space table
*****************************************************************/
int
initFreq()
{
int bytes = (sizeof Freq) / 2;
_fmemset(Freq, 0, bytes);
/* divide because of element size */
_fmemset(Freq+(bytes/sizeof *Freq), 0, bytes);
/* Guarantee a black color */
Freq[0][0][0] = MAX_FREQ;
/* a grey color */
Freq[MID_COMP-1][MID_COMP-1][MID_COMP-1] = MAX_FREQ;
/* and a white color */
Freq[(long)MAX_COMP-1][MAX_COMP-1][MAX_COMP-1] = MAX_FREQ;
Ncolors = 3;
}