home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Collection of Hack-Phreak Scene Programs
/
cleanhpvac.zip
/
cleanhpvac
/
ZED3DSRC.ZIP
/
DRAWPOLY.C
< prev
next >
Wrap
C/C++ Source or Header
|
1995-06-19
|
7KB
|
381 lines
#include <drawpoly.h>
#include <stdlib.h>
#include <stdio.h>
/*
* Note: the screen coordinate system is as follows:
*
* O------------>x+
* |
* |
* |
* |
* |
* |
* |
* \/y+
*
*/
void init_edges(polygon *poly, outbuffer *out)
{
long a;
edge *e,*f;
long A,B,C,D;
e=poly->edgetable; /* e will be current edge */
f=&e[poly->numedges-1]; /* previous edge */
poly->nextremove=0x7fffffff; /* initialize poly->nextremove */
/* start loop */
for(a=0;a<poly->numedges;a++)
{
/* transform from projection space to buffer space */
e->x1=proj2bufx(e->x1);
e->y1=proj2bufy(e->y1);
/* connect last edge to current edge */
f->y2=e->y1;
f->x2=e->x1;
f=e; /* go to next edge */
e++;
}
}
void sort_edges(polygon *poly, outbuffer *out)
{
long a,b,c,x,y,z,counter;
edge *e, *f;
e=poly->edgetable;
poly->inactive.next=0; /* empty inactive edge list */
for(counter=0;counter<poly->numedges;e++,counter++)
{
/* ok, for each edge... */
/* ...sort endpoints */
if(e->y1==e->y2)
{
/* RAAAAH! The dreaded edge parallel to the scanline, kill it! */
continue;
}
if(e->y1>e->y2)
{
/* we should switch point 1 and 2 */
b=e->x1;
c=e->y1;
e->x1=e->x2;
e->y1=e->y2;
e->x2=b;
e->y2=c;
}
/* else, endpoints sorted ok */
/* clip with top and bottom of screen */
if(e->y1>out->maxy)
{
continue;
}
if(e->y2<-out->maxy)
{
continue;
}
if(e->y1<-out->maxy)
{
c=e->x1;
e->x1=c+(e->x2-c)*(-out->maxy-e->y1)/(e->y2-e->y1);
e->y1=-out->maxy;
if(e->y2>out->maxy)
{
e->x2=c+(e->x2-c)*(out->maxy-e->y1)/(e->y2-e->y1);
e->y2=out->maxy;
}
else if(e->y1==e->y2)
{
continue;
}
}
else if(e->y2>out->maxy)
{
e->x2=(e->x2-e->x1)*(out->maxy-e->y1)/(e->y2-e->y1)+e->x1;
e->y2=out->maxy;
if(e->y1==e->y2)
{
continue;
}
}
/* ok now, calculate slope info */
x=e->x2-e->x1;
y=e->y2-e->y1;
skipit:
if(y<0)
{
x=-x;
y=-y;
}
e->increment=x/y;
e->numerator=x%y;
e->denominator=y;
if(x<0)
{
/* make sure we have a positive fraction as a remainder */
e->numerator+=y;
e->increment-=1;
}
e->intercept=e->x1+out->maxx; /* initial intercept value */
e->run=0; /* clear run */
/* ok now, perform insertion sort based on first scanline */
f=&poly->inactive;
while((f->next)&&(f->next->y1<e->y1))
f=f->next;
/* ok insert after f */
e->next=f->next;
f->next=e;
}
/* ok inactive list is all nice and tidy now */
}
outbuffer *allocbuf(long maxx, long maxy)
{
outbuffer *b;
long s,a;
/* allocate buffer */
b=malloc(sizeof(outbuffer));
if(!b) /* if malloc error */
return 0;
/* initialize buffer struct */
b->maxx=maxx;
b->maxy=maxy;
b->width=(maxx<<1)+2;
b->height=(maxy<<1)+1;
/* now, we want to allocate width*(height+1) elements for both zbuffer
and buffer */
s=(b->height+1)*b->width; /* allocate s elements */
b->buffer=malloc(s*sizeof(pixel));
if(b->buffer==0)
{
destroybuf(b);
return 0;
}
return b;
}
void destroybuf(outbuffer *out)
{
if(out)
{
if(out->buffer)
free(out->buffer);
out->buffer=0;
free(out);
}
}
void update_lists(polygon *poly, long scanline)
{
edge *e,*f,*g;
long l;
if(scanline>=poly->nextremove)
/* should we remove edges? */
{
l=0x7fffffff; /* yes, recalculate nextremove and remove edges */
e=&poly->active;
f=e->next;
while(f) /* so long as there are still edges to be examined... */
{
if(f->y2<=scanline)
{
f=f->next; /* remove edge */
e->next=f;
}
else
{
/* keep edge, test for nextremove */
if(e->y2<l)
l=e->y2; /* will be nextremove */
e=f;
f=f->next;
}
}
poly->nextremove=l; /* store l into nextremove */
}
while(g=poly->inactive.next,(g)&&(g->y1==scanline))
{
/* as long as we need to insert new edges */
/* recalculate nextsremove if necessary */
if(poly->nextremove>g->y2)
{
poly->nextremove=g->y2;
}
e=&poly->active;
f=e->next;
while(f) /* insertion sort, most negative slope first */
{
if(f->intercept>=g->intercept)
{
if(f->intercept>g->intercept)
{
break;
}
else if(f->increment>=g->increment)
{
if(f->increment>g->increment)
{
break;
}
else if(f->numerator*g->denominator>
g->numerator*f->denominator)
{
break;
}
}
}
e=f;
f=f->next;
}
/* insert g after e */
poly->inactive.next=g->next;
g->next=f;
e->next=g;
}
}
void update_intercept(polygon *poly)
{
edge *e;
e=poly->active.next;
while(e)
{
/* add integer part of fraction to current intercept value */
e->intercept+=e->increment;
/* add fractional part to running total */
e->run+=e->numerator;
/* is the running total at least one? */
if(e->run>=e->denominator)
{
/* yes, decrease running total by one */
e->run-=e->denominator;
/* increase intercept value by one */
e->intercept++;
}
/* next edge */
e=e->next;
}
}
void draw_spans(polygon *poly, outbuffer *out, long delta)
{
edge *e;
long a,b,x;
/* start with first span */
e=poly->active.next;
while(e)
{
/* get the two endpoints of the span */
a=e->intercept;
e=e->next;
b=e->intercept;
e=e->next;
if(b<0)
continue;
if(a>=out->width)
continue;
if(a<0)
a=0;
if(b>=out->width)
b=out->width-1;
/* blit span */
a+=delta;
b+=delta;
for(x=a;x<b;x++)
{
out->buffer[x]=poly->color;
}
}
}
void drawpolygon(polygon *poly, outbuffer *out)
{
long scanline,delta,mode,a;
init_edges(poly,out);
sort_edges(poly,out);
if(poly->inactive.next)
{
/* initialize scanline to first scanline */
scanline=poly->inactive.next->y1;
/* calculate delta */
delta=mulwidth(scanline+out->maxy);
poly->active.next=0;
/* loop until finished */
update_lists(poly,scanline);
while(poly->active.next)
{
update_intercept(poly);
draw_spans(poly,out,delta);
/* go to next scanline */
scanline++;
delta+=out->width;
update_lists(poly,scanline);
}
}
}