home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The World of Computer Software
/
World_Of_Computer_Software-02-385-Vol-1of3.iso
/
i
/
iritsm3s.zip
/
poly3d-r
/
scandata.c
< prev
next >
Wrap
C/C++ Source or Header
|
1991-09-08
|
17KB
|
515 lines
/*****************************************************************************
* 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 <stdlib.h>
#endif /* __MSDOS__ */
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <string.h>
#include "program.h"
#include "iritprsr.h"
/* #define DEBUG /* Add some printing to stderr routines. */
#define Z_BUFFER_MIN_Z -32767
static GifPixelType *MaskSubScanLine = NULL;
static GifPixelType *ImageScanLine = NULL;
static GifPixelType *MaskScanLine = NULL;
static int *ZBuffer;
static void InitScanLine(void);
static void ScanOnePolygon(IPPolygonStruct *PPolygon, int Level);
static IPVertexStruct *GetNeighborVrtx(IPPolygonStruct *PPolygon,
IPVertexStruct *V, IPVertexStruct *NotV);
static void UpdateScanLine(int x1, int z1, int x2, int z2,
int Color1, int Color2);
#ifdef DEBUG
void PrintHashTable(void);
void PrintPolygon(IPPolygonStruct *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, OrigScrnXSize, OrigScrnYSize, *ImageSubScanLine,
SubSamplePixelSquare, *MinIntensityIndex, SubSamplePixel,
MinYScan = 0, SubSampleLine = 0, LineCount = 0;
long SaveTime = time(NULL);
IPPolygonStruct *PPolygon, *PPolygonLast;
GifPixelType *OneSubScanLine;
OrigScrnXSize = GlblShadeInfo.ScrnXSize;
OrigScrnYSize = GlblShadeInfo.ScrnYSize;
GlblShadeInfo.ScrnXSize *= GlblShadeInfo.SubSamplePixel;
GlblShadeInfo.ScrnYSize *= GlblShadeInfo.SubSamplePixel;
if (GlblShadeInfo.SubSamplePixel > 1) {
OneSubScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
OrigScrnXSize);
ImageSubScanLine = (int *) MyMalloc(sizeof(int) *
OrigScrnXSize);
ImageSubBGScanLine = (char *) MyMalloc(sizeof(char) *
OrigScrnXSize);
}
ImageScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
GlblShadeInfo.ScrnXSize);
if (GifMask != NULL) {
if (GlblShadeInfo.SubSamplePixel > 1)
MaskSubScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
OrigScrnXSize);
MaskScanLine = (GifPixelType *) MyMalloc(sizeof(GifPixelType) *
GlblShadeInfo.ScrnXSize);
}
ZBuffer = (int *) MyMalloc(sizeof(int) * GlblShadeInfo.ScrnXSize);
MinIntensityIndex = GlblShadeInfo.MinIntensityIndex;
SubSamplePixel = GlblShadeInfo.SubSamplePixel;
SubSamplePixelSquare = SQR(SubSamplePixel);
fprintf(stderr, "\nPass 4, Level [%4d] = ",
OrigScrnYSize);
for (i = 0; i < GlblShadeInfo.ScrnYSize; i++) { /* Scan line i: */
/* First lets scan and delete all polygons below this scan line: */
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) * OrigScrnXSize);
memset(OneSubScanLine, 0,
sizeof(GifPixelType) * OrigScrnXSize);
memset(ImageSubBGScanLine, 0,
sizeof(char) * OrigScrnXSize);
if (GifMask) memset(MaskSubScanLine, 0,
sizeof(GifPixelType) * OrigScrnXSize);
}
for (j = 0; j < GlblShadeInfo.ScrnXSize; j++)
if (ImageScanLine[j] == 0)
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 < OrigScrnXSize; j++) {
/* Instead of Back Ground - add the lowest intensity of */
/* 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,
OrigScrnXSize);
if (GifMask)
EGifPutLine(GifMask, MaskSubScanLine,
OrigScrnXSize);
# endif /* DEBUG_NO_GIF */
SubSampleLine = 0;
}
}
else {
fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);
# ifndef DEBUG_NO_GIF
EGifPutLine(GifFile, ImageScanLine, GlblShadeInfo.ScrnXSize);
if (GifMask)
EGifPutLine(GifMask, MaskScanLine,
GlblShadeInfo.ScrnXSize);
# endif /* DEBUG_NO_GIF */
}
}
fprintf(stderr, ", %ld seconds.", time(NULL) - SaveTime);
GlblShadeInfo.ScrnXSize = OrigScrnXSize;
GlblShadeInfo.ScrnYSize = OrigScrnYSize;
}
/*****************************************************************************
* Reset all buffers to clear state: *
*****************************************************************************/
static void InitScanLine(void)
{
memset(ImageScanLine, 0, sizeof(GifPixelType) * GlblShadeInfo.ScrnXSize);
if (MaskScanLine)
memset(MaskScanLine, 0, sizeof(GifPixelType) * GlblShadeInfo.ScrnXSize);
/* Set all Zbuffer to Z_BUFFER_MIN_Z. Can be done in a regular loop as: */
/* for (i = 0; i < ScrnXSize; i++) ZBuffer[i] = Z_BUFFER_MIN_Z; */
/* As memset allows setting of only one byte, the minimum we can set */
/* here is -32640 which is 0x8080, so we do that instead: */
memset(ZBuffer, 0x80, sizeof(int) * GlblShadeInfo.ScrnXSize);
}
/*****************************************************************************
* 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(IPPolygonStruct *PPolygon, int Level)
{
int x1, z1, x2, z2, Color1, Color2;
RealType t1, t2, *Coord1, *Coord2;
IPVertexStruct *V;
PolygonScanConvertStruct
*PScan = (PolygonScanConvertStruct *) PPolygon -> PAux;
/* Stage 1 - verify that both boundaries are in range: */
if (PScan -> Bndry1.MaxEdgeY < Level) {
V = PScan -> Bndry1.VMinY;
PScan -> Bndry1.VMinY = PScan -> Bndry1.VMaxY;
PScan -> Bndry1.VMaxY =
GetNeighborVrtx(PPolygon, PScan -> Bndry1.VMaxY, V);
PScan -> Bndry1.MaxEdgeY =
(int) PScan -> Bndry1.VMaxY -> Coord[1];
}
if (PScan -> Bndry2.MaxEdgeY < Level) {
V = PScan -> Bndry2.VMinY;
PScan -> Bndry2.VMinY = PScan -> Bndry2.VMaxY;
PScan -> Bndry2.VMaxY =
GetNeighborVrtx(PPolygon, PScan -> Bndry2.VMaxY, V);
PScan -> Bndry2.MaxEdgeY =
(int) PScan -> 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 = PScan -> Bndry1.VMinY -> Coord;
Coord2 = PScan -> 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 = PScan -> Bndry2.VMinY -> Coord;
Coord2 = PScan -> 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 (GlblShadeInfo.Gouraud) {
/* Need to interpolate the colors as well: */
Color1 = (int) (PScan -> Bndry1.VMinY -> Color * t1 +
PScan -> Bndry1.VMaxY -> Color * (1.0 - t1));
Color2 = (int) (PScan -> Bndry2.VMinY -> Color * t2 +
PScan -> 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, PScan -> Bndry1.VMinY -> Color,
PScan -> Bndry1.VMinY -> Color);
}
}
/*****************************************************************************
* Returns the other neighbor of vertex V in polygon PPolygon which is not *
* the neighbor NotV. *
*****************************************************************************/
static IPVertexStruct *GetNeighborVrtx(IPPolygonStruct *PPolygon,
IPVertexStruct *V, IPVertexStruct *NotV)
{
int i;
IPVertexStruct *List2,
*List = PPolygon -> PVertex;
/* Find index of vertex V. */
for (i = 0; List != V; i++, List = List -> Pnext);
if (i == 0) {
/* The vertex is first - its neighbors are second and last in list. */
if (PPolygon -> PVertex -> Pnext == NotV) {
/* We need the last one: */
for (List2 = PPolygon -> PVertex;
List2 -> Pnext != NULL;
List2 = List2 -> Pnext);
return List2;
}
else
return PPolygon -> PVertex -> Pnext;
}
else if (List -> Pnext == NULL) {
/* The vertex is last - its neighbors are first and second from last.*/
if (PPolygon -> PVertex == NotV) {
/* We need the second from last: */
for (List2 = PPolygon -> PVertex;
List2 -> Pnext != List;
List2 = List2 -> Pnext);
return List2;
}
else
return PPolygon -> PVertex;
}
else {
if (List -> Pnext == NotV) {
for (List2 = PPolygon -> PVertex;
List2 -> Pnext != List;
List2 = List2 -> Pnext);
return List2;
}
else
return List -> Pnext;
}
}
/*****************************************************************************
* 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;
RealType 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 >= GlblShadeInfo.ScrnXSize) {
/* Update upper limit to GlblShadeInfo.ScrnXSize - 1: */
if (x2 == x1) return;
t = (x2 - (GlblShadeInfo.ScrnXSize - 1)) / (x2 - x1);
x2 = GlblShadeInfo.ScrnXSize - 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 (GlblShadeInfo.Gouraud) {
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 (GlblShadeInfo.Gouraud) {
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 (GlblShadeInfo.Gouraud) {
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;
IPPolygonStruct *PPolygon;
for (i = 0; i < GlblShadeInfo.ScrnYSize; i++)
if (PolyHashTable[i] != NULL) {
fprintf(stderr,
"\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(IPPolygonStruct *PPolygon)
{
int i;
IPVertexStruct *VList = PPolygon -> PVertex;
for ( ; VList != NULL; VList = VList -> Pnext) {
fprintf(stderr, "\t%12f %12f %12f (Color = %d).\n",
PList -> Coord[0],
PList -> Coord[1],
PList -> Coord[2],
PList -> Color);
}
}
/*****************************************************************************
* Routine to print content of Image Scan Line buffer: *
*****************************************************************************/
void PrintImageScanLine(void)
{
int i;
for (i = 0; i < GlblShadeInfo.ScrnXSize; i++) {
if (i % 26 == 0) fprintf(stderr, "\n");
fprintf(stderr, "%02x ", ImageScanLine[i]);
}
}
#endif /* DEBUG */