Category : C Source Code
Archive : POLY3DRS.ZIP
Filename : SCANDATA.C
Output of file : SCANDATA.C contained in archive : POLY3DRS.ZIP
* Routines to scan convert the input (polygons), which is sorted into *
* global hash table PolyHashTable according to polygons Ymin. *
* *
* Written by: Gershon Elber Ver 2.0, Mar. 1990 *
*****************************************************************************/
#ifdef __MSDOS__
#include
#endif /* __MSDOS__ */
#include
#include
#include
#include
#include "program.h"
#include "parser.h"
#include "gif_lib.h"
/* #define DEBUG /* Add some printing to stderr routines. */
#define Z_BUFFER_MIN_Z -32767
static PixelType *MaskSubScanLine = NULL;
static PixelType *ImageScanLine = NULL;
static PixelType *MaskScanLine = NULL;
static int *ZBuffer;
static void InitScanLine(void);
static void ScanOnePolygon(PolygonStruct *PPolygon, int Level);
static VertexStruct *GetNeighborVrtx(PolygonStruct *PPolygon, VertexStruct *V,
VertexStruct *NotV);
static void UpdateScanLine(int x1, int z1, int x2, int z2,
int Color1, int Color2);
#ifdef DEBUG
void PrintHashTable(void);
void PrintPolygon(PolygonStruct *PPolygon);
void PrintImageScanLine(void);
#endif DEBUG
/*****************************************************************************
* Routine to scan convert all polygons in PolyHashTable. *
* The real images goes to GifFile, while GifMask (if not NULL) will have a *
* booleam mask, where image was created. *
*****************************************************************************/
void ScanConvertData(GifFileType *GifFile, GifFileType *GifMask)
{
char *ImageSubBGScanLine;
int i, j, k, OrigScreenXSize, OrigScreenYSize, *ImageSubScanLine,
SubSamplePixelSquare, *MinIntensityIndex, SubSamplePixel,
MinYScan = 0, SubSampleLine = 0, LineCount = 0;
long SaveTime = time(NULL);
PolygonStruct *PPolygon, *PPolygonLast;
PixelType *OneSubScanLine;
OrigScreenXSize = ScreenXSize;
OrigScreenYSize = ScreenYSize;
ScreenXSize *= ShadingInfo.SubSamplePixel;
ScreenYSize *= ShadingInfo.SubSamplePixel;
if (ShadingInfo.SubSamplePixel > 1) {
OneSubScanLine = (PixelType *) MyMalloc(sizeof(PixelType) *
OrigScreenXSize);
ImageSubScanLine = (int *) MyMalloc(sizeof(int) * OrigScreenXSize);
ImageSubBGScanLine = (char *) MyMalloc(sizeof(char) * OrigScreenXSize);
}
ImageScanLine = (PixelType *) MyMalloc(sizeof(PixelType) * ScreenXSize);
if (GifMask != NULL) {
if (ShadingInfo.SubSamplePixel > 1)
MaskSubScanLine = (PixelType *) MyMalloc(sizeof(PixelType) *
OrigScreenXSize);
MaskScanLine = (PixelType *) MyMalloc(sizeof(PixelType) * ScreenXSize);
}
ZBuffer = (int *) MyMalloc(sizeof(int) * ScreenXSize);
MinIntensityIndex = ShadingInfo.MinIntensityIndex;
SubSamplePixel = ShadingInfo.SubSamplePixel;
SubSamplePixelSquare = SQR(SubSamplePixel);
fprintf(stderr, "\nPass 4, Level [%4d] = ", OrigScreenYSize);
for (i=0; i
for (j=MinYScan; j<=i; j++) {
PPolygon = PPolygonLast = PolyHashTable[j];
while (PPolygon) {
if (PPolygon -> Ymax < i) { /* Delete this polygon. */
/* If it is first one, update the hash table also. Note */
/* we dont free the polygon as, we are not going to */
/* allocate anything any more, so why bather. */
if (PPolygon == PolyHashTable[j])
PolyHashTable[j] = PPolygonLast = PPolygon =
PPolygon -> Pnext;
else PPolygonLast -> Pnext = PPolygon = PPolygon -> Pnext;
}
else {
PPolygonLast = PPolygon;
PPolygon = PPolygon -> Pnext;
}
}
/* If this level is empty - advance the minimum level to scan: */
if (j == MinYScan && PolyHashTable[j] == NULL) MinYScan++;
}
/* New do the scan conversion of the active polygons: */
InitScanLine();
for (j=MinYScan; j<=i; j++) {
PPolygon = PPolygonLast = PolyHashTable[j];
while (PPolygon) {
ScanOnePolygon(PPolygon, i);
PPolygonLast = PPolygon;
PPolygon = PPolygon -> Pnext;
}
}
if (SubSamplePixel > 1) {
if (SubSampleLine == 0) { /* Reset the sub sumpling buffers. */
memset(ImageSubScanLine, 0,
sizeof(int) * OrigScreenXSize);
memset(OneSubScanLine, 0,
sizeof(PixelType) * OrigScreenXSize);
memset(ImageSubBGScanLine, 0,
sizeof(char) * OrigScreenXSize);
if (GifMask) memset(MaskSubScanLine, 0,
sizeof(PixelType) * OrigScreenXSize);
}
for (j=0; j
ImageSubBGScanLine[j / SubSamplePixel]++;
else {
k = j / SubSamplePixel;
ImageSubScanLine[k] += ImageScanLine[j];
OneSubScanLine[k] = ImageScanLine[j];
if (GifMask) MaskSubScanLine[k] = MaskScanLine[j] != 0 ||
MaskSubScanLine[k];
}
SubSampleLine++;
if (SubSampleLine == SubSamplePixel) {
for (j=0; j
/* This color. Note we still may have problems if two */
/* colors are averaged to a color index in between... */
if (ImageSubScanLine[j] > 0)
ImageSubScanLine[j] += ImageSubBGScanLine[j] *
MinIntensityIndex[OneSubScanLine[j]];
OneSubScanLine[j] = ImageSubScanLine[j] /
SubSamplePixelSquare;
}
fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);
# ifndef DEBUG_NO_GIF
EGifPutLine(GifFile, OneSubScanLine, OrigScreenXSize);
if (GifMask)
EGifPutLine(GifMask, MaskSubScanLine, OrigScreenXSize);
# endif DEBUG_NO_GIF
SubSampleLine = 0;
}
}
else {
fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);
# ifndef DEBUG_NO_GIF
EGifPutLine(GifFile, ImageScanLine, ScreenXSize);
if (GifMask)
EGifPutLine(GifMask, MaskScanLine, ScreenXSize);
# endif DEBUG_NO_GIF
}
}
fprintf(stderr, ", %ld seconds.", time(NULL) - SaveTime);
ScreenXSize = OrigScreenXSize;
ScreenYSize = OrigScreenYSize;
}
/*****************************************************************************
* Reset all buffers to clear state: *
*****************************************************************************/
static void InitScanLine(void)
{
memset(ImageScanLine, 0, sizeof(PixelType) * ScreenXSize);
if (MaskScanLine) memset(MaskScanLine, 0, sizeof(PixelType) * ScreenXSize);
/* Set all Zbuffer to Z_BUFFER_MIN_Z. Can be done in a regular loop as: */
/* for (i=0; i
/* here is -32640 which is 0x8080, so we do that instead: */
memset(ZBuffer, 0x80, sizeof(int) * ScreenXSize);
}
/*****************************************************************************
* Scan convert one polygon: *
* 1. If one of the left/right boundaries is found to be below current level *
* that boundary edge is updated. *
* 2. Interpolate the Color and Z value of the intersection of scan line with *
* the boundaries and call UpdateScanLine to update the buffers. *
*****************************************************************************/
static void ScanOnePolygon(PolygonStruct *PPolygon, int Level)
{
int x1, z1, x2, z2, Color1, Color2;
float t1, t2, *Coord1, *Coord2;
VertexStruct *V;
/* Stage 1 - verify that both boundaries are in range: */
if (PPolygon -> Bndry1.MaxEdgeY < Level) {
V = PPolygon -> Bndry1.VMinY;
PPolygon -> Bndry1.VMinY = PPolygon -> Bndry1.VMaxY;
PPolygon -> Bndry1.VMaxY =
GetNeighborVrtx(PPolygon, PPolygon -> Bndry1.VMaxY, V);
PPolygon -> Bndry1.MaxEdgeY =
(int) PPolygon -> Bndry1.VMaxY -> Coord[1];
}
if (PPolygon -> Bndry2.MaxEdgeY < Level) {
V = PPolygon -> Bndry2.VMinY;
PPolygon -> Bndry2.VMinY = PPolygon -> Bndry2.VMaxY;
PPolygon -> Bndry2.VMaxY =
GetNeighborVrtx(PPolygon, PPolygon -> Bndry2.VMaxY, V);
PPolygon -> Bndry2.MaxEdgeY =
(int) PPolygon -> Bndry2.VMaxY -> Coord[1];
}
/* Stage 2 - evaluate the interpolated X & Z for this line and call */
/* UpdateScanLine with them. Note we could do it using some sort of DDA */
/* (integer arithmetic) but as UpdateScanLine is much more expensive */
/* we will gain almost nothing in speed, doing that. */
/* Also as this polygon assumed to intersect with the scan line using */
/* integer arithmetic, it might not be so, when we actuallt evaluate it. */
/* We simply quit if that is the case. */
Coord1 = PPolygon -> Bndry1.VMinY -> Coord;
Coord2 = PPolygon -> Bndry1.VMaxY -> Coord;
if (ABS(Coord2[1] - Coord1[1]) == 0.0)
t1 = 0.5;
else t1 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
if (t1 < 0.0 || t1 > 1.0) return;
x1 = Coord1[0] * t1 + Coord2[0] * (1.0 - t1);
z1 = Coord1[2] * t1 + Coord2[2] * (1.0 - t1);
Coord1 = PPolygon -> Bndry2.VMinY -> Coord;
Coord2 = PPolygon -> Bndry2.VMaxY -> Coord;
if (ABS(Coord2[1] - Coord1[1]) == 0.0)
t2 = 0.5;
else t2 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
if (t2 < 0.0 || t2 > 1.0) return;
x2 = Coord1[0] * t2 + Coord2[0] * (1.0 - t2);
z2 = Coord1[2] * t2 + Coord2[2] * (1.0 - t2);
if (GouraudFlag) {
/* Need to interpolate the colors as well: */
Color1 = (int) (PPolygon -> Bndry1.VMinY -> Color * t1 +
PPolygon -> Bndry1.VMaxY -> Color * (1.0 - t1));
Color2 = (int) (PPolygon -> Bndry2.VMinY -> Color * t2 +
PPolygon -> Bndry2.VMaxY -> Color * (1.0 - t2));
UpdateScanLine(x1, z1, x2, z2, Color1, Color2);
}
else {
/* Flat shading - all vertices has same intensity - pick one: */
UpdateScanLine(x1, z1, x2, z2, PPolygon -> Bndry1.VMinY -> Color,
PPolygon -> Bndry1.VMinY -> Color);
}
}
/*****************************************************************************
* Returns the other neighbor of vertex V in polygon PPolygon which is not *
* the neighbor NotV. *
*****************************************************************************/
static VertexStruct *GetNeighborVrtx(PolygonStruct *PPolygon, VertexStruct *V,
VertexStruct *NotV)
{
struct VertexStruct *List = PPolygon -> PVertex, *ListLast;
if (List == V) {
/* The vertex is first - its neighbors are second and last in list. */
if (List -> Pnext == NotV) {
/* We need the last one: */
while (List -> Pnext != NULL) List = List -> Pnext;
return List;
}
else return List -> Pnext;
}
ListLast = List;
List = List -> Pnext;
while (List != NULL) {
if (List == V) {
if (ListLast == NotV) {
/* We need the next vertex instead of last one: */
if (List -> Pnext == NULL)
return PPolygon -> PVertex;
else return List -> Pnext;
}
else return ListLast;
}
ListLast = List;
List = List -> Pnext;
}
return List; /* Should never be here - make warnings silent. */
}
/*****************************************************************************
* Update the scan line itself by linearly interplate the two end points for *
* all internal points of scan line if closer than old data. *
*****************************************************************************/
static void UpdateScanLine(int x1, int z1, int x2, int z2,
int Color1, int Color2)
{
int i, Dx, Dz, Dc, Az, Ac, x, z, Color;
float t;
if (x2 < x1) {
i = x2; x2 = x1; x1 = i;
i = z2; z2 = z1; z1 = i;
i = Color2; Color2 = Color1; Color1 = i;
}
if (x1 < 0) {
/* Update lower limit to zero: */
if (x2 == x1) return;
t = -x1 / (x2 - x1);
x1 = 0;
z1 = (int) (z1 * (1.0 - t) + z2 * t);
Color1 = (int) (Color1 * (1.0 - t) + Color2 * t);
}
if (x2 >= ScreenXSize) {
/* Update upper limit to ScreenXSize - 1: */
if (x2 == x1) return;
t = (x2 - (ScreenXSize - 1)) / (x2 - x1);
x2 = ScreenXSize - 1;
z2 = (int) (z1 * t + z2 * (1.0 - t));
Color2 = (int) (Color1 * t + Color2 * (1.0 - t));
}
Dx = x2 - x1;
x = x1;
Dz = z2 - z1;
Az = -Dx; /* DDA accumulator of Z interpolation. */
z = z1;
Color = Color1;
if (GouraudFlag) {
Dc = Color2 - Color1; /* Needed if Gouraud shading is in use. */
Ac = -Dx; /* DDA accumulator of Color interpolation. */
}
/* We are going to execute the loop once but might be stack forever in */
/* one of the internal interplation loops, so make it non zero: */
if (Dx == 0) Dx = 999;
if (Dz > 0) {
while (x <= x2) {
/* Update buffers iff is closer to view point: */
if (ZBuffer[x] < z) {
ZBuffer[x] = z;
ImageScanLine[x] = Color;
if (MaskScanLine != NULL) MaskScanLine[x] = 1;
}
else
if (ZBuffer[x] == z) {
/* This case is hard to solve, and it may create high */
/* intensity lines on polygon boundaries. To prevent from */
/* that, update iff new color intensity is less than old on. */
if (ImageScanLine[x] < Color) ImageScanLine[x] = Color;
if (MaskScanLine != NULL) MaskScanLine[x] = 1;
}
Az += Dz;
x++;
while (Az > 0) {
z++;
Az -= Dx;
}
if (GouraudFlag) {
if (Dc > 0) {
Ac += Dc;
while (Ac > 0) {
Color++;
Ac -= Dx;
}
}
else { /* Dc < 0 */
Ac -= Dc;
while (Ac > 0) {
Color--;
Ac -= Dx;
}
}
}
}
}
else { /* Dz < 0 */
while (x <= x2) {
/* Update buffers iff is closer to view point: */
if (ZBuffer[x] < z) {
ZBuffer[x] = z;
ImageScanLine[x] = Color;
if (MaskScanLine != NULL) MaskScanLine[x] = 1;
}
else
if (ZBuffer[x] == z) {
/* This case is hard to solve, and it may create high */
/* intensity lines on polygon boundaries. To prevent from */
/* that, update iff new color intensity is less than old on. */
if (ImageScanLine[x] < Color) ImageScanLine[x] = Color;
if (MaskScanLine != NULL) MaskScanLine[x] = 1;
}
Az -= Dz;
x++;
while (Az > 0) {
z--;
Az -= Dx;
}
if (GouraudFlag) {
if (Dc > 0) {
Ac += Dc;
while (Ac > 0) {
Color++;
Ac -= Dx;
}
}
else { /* Dc < 0 */
Ac -= Dc;
while (Ac > 0) {
Color--;
Ac -= Dx;
}
}
}
}
}
}
#ifdef DEBUG
/*****************************************************************************
* Routine to print the content of a given edge: *
*****************************************************************************/
void PrintHashTable(void)
{
int i;
PolygonStruct *PPolygon;
for (i=0; i
"\n***************** HashTable entry %d *****************\n", i);
PPolygon = PolyHashTable[i];
while (PPolygon) {
fprintf(stderr, "\t+++++++ Polygon:\n");
PrintPolygon(PPolygon);
PPolygon = PPolygon -> Pnext;
}
}
}
/*****************************************************************************
* Routine to print the content of a given edge: *
*****************************************************************************/
void PrintPolygon(PolygonStruct *PPolygon)
{
struct VertexStruct *PList = PPolygon -> PVertex;
while (PList) {
fprintf(stderr, "\t%12f %12f %12f (Color = %d)\n",
PList -> Coord[0],
PList -> Coord[1],
PList -> Coord[2],
PList -> Color);
PList = PList -> Pnext;
}
}
/*****************************************************************************
* Routine to print content of Image Scan Line buffer: *
*****************************************************************************/
void PrintImageScanLine(void)
{
int i;
for (i=0; i
fprintf(stderr, "%02x ", ImageScanLine[i]);
}
}
#endif DEBUG
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/