greed/CODE/R_SPANS.C
2014-12-12 00:00:00 +00:00

652 lines
17 KiB
C

/***************************************************************************/
/* */
/* */
/* Raven 3D Engine */
/* Copyright (C) 1996 by Softdisk Publishing */
/* */
/* Original Design: */
/* John Carmack of id Software */
/* */
/* Enhancements by: */
/* Robert Morgan of Channel 7............................Main Engine Code */
/* Todd Lewis of Softdisk Publishing......Tools,Utilities,Special Effects */
/* John Bianca of Softdisk Publishing..............Low-level Optimization */
/* Carlos Hasan..........................................Music/Sound Code */
/* */
/* */
/***************************************************************************/
#include <STDLIB.H>
#include "d_global.h"
#include "r_refdef.h"
#include "d_video.h"
#include "d_misc.h"
#include "r_public.h"
/**** VARIABLES ****/
/*a scaled object is just encoded like a span */
unsigned spantags[MAXSPANS];
unsigned *starttaglist_p, *endtaglist_p; // set by SortSpans
span_t spans[MAXSPANS];
int spansx[MAXSPANS];
int spanx;
fixed_t pointz, afrac, hfrac;
int numspans;
span_t *span_p;
/**** FUNCTIONS ****/
#define QUICKSORT_CUTOFF 16
#define SWAP(a,b) \
{ \
temp=a; \
a=b; \
b=temp; \
}
void MedianOfThree(unsigned *data,unsigned count)
{
unsigned temp;
if (count>=3)
{
unsigned *beg=data;
unsigned *mid=data + (count/2);
unsigned *end=data + (count-1);
if (*beg>*mid)
{
if (*mid>*end)
SWAP(*beg,*mid)
else if (*beg>*end)
SWAP(*beg,*end)
}
else if (*mid>*end)
{
if (*beg>*end)
SWAP(*beg,*end)
}
else
SWAP(*beg,*mid);
}
}
int Partition(unsigned *data,unsigned count)
{
unsigned part=data[0];
int i=-1;
int j=count;
unsigned temp;
while (i<j)
{
while (part>data[--j]);
while (data[++i]>part);
if (i>=j)
break;
SWAP(data[i],data[j]);
}
return j+1;
}
void QuickSortHelper(unsigned *data,unsigned count)
{
int left=0;
int part;
if (count>QUICKSORT_CUTOFF)
{
while (count>1)
{
MedianOfThree(data+left,count);
part=Partition(data+left,count);
QuickSortHelper(data+left,part);
left+=part;
count-=part;
}
}
}
void InsertionSort(unsigned *data,unsigned count)
{
int i, j;
unsigned t;
for (i=1;i<count;i++)
{
if (data[i]>data[i-1])
{
t=data[i];
for (j=i;j && t>data[j-1];j--)
data[j]=data[j-1];
data[j]=t;
}
}
}
/*************************************************************************/
void DrawDoorPost(void)
{
fixed_t top, bottom; // precise y coordinates for post
int topy, bottomy; // pixel y coordinates for post
fixed_t fracadjust; // the amount to prestep for the top pixel
fixed_t scale;
int light;
scale=FIXEDMUL(pointz,ISCALE);
sp_source=span_p->picture;
if (span_p->shadow==0)
{
light=(pointz>>FRACBITS)+span_p->light;
if (light>MAXZLIGHT) return;
else if (light<0) light=0;
sp_colormap=zcolormap[light];
}
else if (span_p->shadow==1) sp_colormap=colormaps+(wallglow<<8);
else if (span_p->shadow==2) sp_colormap=colormaps+(wallflicker1<<8);
else if (span_p->shadow==3) sp_colormap=colormaps+(wallflicker2<<8);
else if (span_p->shadow==4) sp_colormap=colormaps+(wallflicker3<<8);
else if (span_p->shadow>=5 && span_p->shadow<=8)
{
if (wallcycle==span_p->shadow-5) sp_colormap=colormaps;
else
{
light=(pointz>>FRACBITS)+span_p->light;
if (light>MAXZLIGHT) light=MAXZLIGHT;
else if (light<0) light=0;
sp_colormap=zcolormap[light];
}
}
else if (span_p->shadow==9)
{
light=(pointz>>FRACBITS)+span_p->light+wallflicker4;
if (light>MAXZLIGHT) light=MAXZLIGHT;
else if (light<0) light=0;
sp_colormap=zcolormap[light];
}
sp_fracstep=FIXEDMUL(pointz,ISCALE);
top=FIXEDDIV(span_p->y,scale);
topy=top>>FRACBITS;
fracadjust=top&(FRACUNIT-1);
sp_frac=FIXEDMUL(fracadjust,sp_fracstep);
topy=CENTERY-topy;
sp_loopvalue=256<<FRACBITS;
if (topy<scrollmin)
{
sp_frac+=(scrollmin-topy)*scale;
while (sp_frac>sp_loopvalue) sp_frac-=sp_loopvalue;
topy=scrollmin;
}
bottom=FIXEDDIV(span_p->yh,scale);
bottomy= bottom>=((CENTERY+scrollmin)<<FRACBITS) ?
scrollmax-1 : CENTERY+(bottom>>FRACBITS);
if (bottomy<=scrollmin || topy>=scrollmax) return;
sp_count=bottomy-topy+1;
sp_dest=viewylookup[bottomy-scrollmin]+spanx;
if (span_p->spantype==sp_maskeddoor) ScaleMaskedPost();
else ScalePost();
}
void ScaleTransPost()
{
pixel_t color;
sp_dest-=windowWidth*(sp_count-1); // go to the top
--sp_loopvalue;
while (--sp_count)
{
color=sp_source[sp_frac>>FRACBITS];
if (color)
*sp_dest=*(translookup[sp_colormap[color]-1]+*sp_dest);
sp_dest+=windowWidth;
sp_frac+=sp_fracstep;
sp_frac&=sp_loopvalue;
}
}
void DrawSprite(void)
{
fixed_t leftx, scale, xfrac, fracstep;
fixed_t shapebottom, topheight, bottomheight;
int post, x, topy, bottomy, light, shadow, height, bitshift;
special_t specialtype;
scalepic_t *pic;
byte *collumn;
scaleobj_t *sp;
/********* floor shadows ***********/
specialtype=(special_t)(span_p->shadow>>8);
shadow=span_p->shadow&255;
if (specialtype==st_maxlight) sp_colormap=colormaps;
else if (specialtype==st_transparent) sp_colormap=colormaps;
else if (shadow==0)
{
light=(pointz>>FRACBITS)+span_p->light;
if (light>MAXZLIGHT) return;
else if (light<0) light=0;
sp_colormap=zcolormap[light];
}
else if (span_p->shadow==1) sp_colormap=colormaps+(wallglow<<8);
else if (span_p->shadow==2) sp_colormap=colormaps+(wallflicker1<<8);
else if (span_p->shadow==3) sp_colormap=colormaps+(wallflicker2<<8);
else if (span_p->shadow==4) sp_colormap=colormaps+(wallflicker3<<8);
else if (span_p->shadow>=5 && span_p->shadow<=8)
{
if (wallcycle==span_p->shadow-5) sp_colormap=colormaps;
else
{
light=(pointz>>FRACBITS)+span_p->light;
if (light>MAXZLIGHT) light=MAXZLIGHT;
else if (light<0) light=0;
sp_colormap=zcolormap[light];
}
}
else if (shadow==9)
{
light=(pointz>>FRACBITS)+span_p->light+wallflicker4;
if (light>MAXZLIGHT) light=MAXZLIGHT;
else if (light<0) light=0;
sp_colormap=zcolormap[light];
}
pic=(scalepic_t *)span_p->picture;
sp=(scaleobj_t *)span_p->structure;
bitshift=FRACBITS-sp->scale;
shapebottom=span_p->y;
// project the x and height
scale=FIXEDDIV(SCALE,pointz);
fracstep=FIXEDMUL(pointz,ISCALE)<<sp->scale;
sp_fracstep=fracstep;
leftx=span_p->x2;
leftx-=pic->leftoffset<<bitshift;
x=CENTERX+(FIXEDMUL(leftx,scale)>>FRACBITS);
// step through the shape, drawing posts where visible
xfrac=0;
if (x<0)
{
xfrac-=fracstep * x;
x=0;
}
sp_loopvalue=(256<<FRACBITS);
height=pic->collumnofs[1]-pic->collumnofs[0];
for (; x<windowWidth; x++)
{
post=xfrac>>FRACBITS;
if (post>=pic->width)
return; // shape finished drawing
xfrac+=fracstep;
if (pointz>=wallz[x] && (pointz>=wallz[x]+TILEUNIT || (specialtype!=st_noclip && specialtype!=st_transparent)))
continue;
// If the offset of the columns is zero then there is no data for the post
if (pic->collumnofs[post]==0)
continue;
collumn=(byte *)pic+pic->collumnofs[post];
topheight=shapebottom+(*collumn<<bitshift);
bottomheight=shapebottom+(*(collumn+1)<<bitshift);
collumn+=2;
// scale a post
bottomy=CENTERY - (FIXEDMUL(bottomheight,scale)>>FRACBITS);
if (bottomy<scrollmin)
continue;
if (bottomy>=scrollmax)
bottomy=scrollmax-1;
topy=CENTERY-(FIXEDMUL(topheight,scale)>>FRACBITS);
if (topy<scrollmin)
{
sp_frac=(scrollmin-topy)*sp_fracstep;
topy=scrollmin;
}
else
sp_frac=0;
if (topy>=scrollmax)
continue;
sp_count=bottomy-topy+1;
sp_dest=viewylookup[bottomy-scrollmin]+x;
sp_source=collumn;
if (specialtype==st_transparent)
ScaleTransPost();
else
ScaleMaskedPost();
}
}
void DrawSpans(void)
/* Spans farther than MAXZ away should NOT have been entered into the list */
{
unsigned *spantag_p, tag;
int spannum;
int x2;
fixed_t lastz; // the pointz for which xystep is valid
fixed_t length;
fixed_t zerocosine, zerosine;
fixed_t zeroxfrac, zeroyfrac;
fixed_t xf2, yf2; // endpoint texture for sloping spans
int angle;
int light;
int px, py, h1, x1, center, y1, x;
fixed_t a, w;
pixel_t color;
// set up backdrop stuff
w=windowWidth/2;
center=viewangle&255;
// set up for drawing
starttaglist_p=spantags;
if (numspans)
{
QuickSortHelper(starttaglist_p,numspans);
InsertionSort(starttaglist_p,numspans);
}
endtaglist_p=starttaglist_p+numspans;
spantag_p=starttaglist_p;
angle=viewfineangle+pixelangle[0];
angle&=TANANGLES *4-1;
zerocosine=cosines[angle];
zerosine=sines[angle];
// draw from back to front
x2=-1;
lastz=-1;
// draw everything else
while (spantag_p!=endtaglist_p)
{
tag=*spantag_p++;
pointz=tag>>ZTOFRAC;
spannum=tag&SPANMASK;
span_p=&spans[spannum];
spanx=spansx[spannum];
switch (span_p->spantype)
{
case sp_flat:
case sp_flatsky:
// floor / ceiling span
if (pointz!=lastz)
{
lastz=pointz;
mr_xstep=FIXEDMUL(pointz, xscale);
mr_ystep=FIXEDMUL(pointz, yscale);
// calculate starting texture point
length=FIXEDDIV(pointz, pixelcosine[0]);
zeroxfrac=mr_xfrac=viewx+FIXEDMUL(length, zerocosine);
zeroyfrac=mr_yfrac=viewy-FIXEDMUL(length, zerosine);
x2=0;
}
if (spanx!=x2)
{
mr_xfrac=zeroxfrac+mr_xstep *spanx;
mr_yfrac=zeroyfrac+mr_ystep *spanx;
}
/* floor shadows */
if (span_p->shadow==0)
{
light=(pointz>>FRACBITS)+span_p->light;
if (light>MAXZLIGHT) break;
else if (light<0) light=0;
mr_colormap=zcolormap[light];
}
else if (span_p->shadow==9)
{
light=(pointz>>FRACBITS)+span_p->light+wallflicker4;
if (light>MAXZLIGHT) break;
else if (light<0) light=0;
mr_colormap=zcolormap[light];
}
else mr_colormap=(byte *)span_p->shadow;
y1=span_p->y-scrollmin;
if ((unsigned)y1>=200) break;
mr_dest=viewylookup[y1]+spanx;
mr_picture=span_p->picture;
x2=span_p->x2;
if ((unsigned)x2>320) break;
mr_count=x2-spanx;
MapRow();
if (span_p->spantype==sp_flatsky)
{
py=span_p->y-scrollmin;
px=spanx;
mr_count=span_p->x2-spanx;
mr_dest=viewylookup[py]+px;
if (windowHeight!=64) py=span_p->y+64;
h1=(hfrac*py)>>FRACBITS;
if (px<=w)
{
a=((TANANGLES/2)<<FRACBITS) + afrac*(w-px);
while (px<=w && mr_count>0)
{
x=backtangents[a>>FRACBITS];
x2=center - x + windowWidth - 257;
x2&=255;
if (*mr_dest==255) *mr_dest=*(backdroplookup[h1]+x2);
a-=afrac;
px++;
mr_count--;
mr_dest++;
}
}
if (px>w)
{
a=((TANANGLES/2)<<FRACBITS) + afrac*(px-w);
while (mr_count>0)
{
x1=center + backtangents[a>>FRACBITS];
x1&=255;
if (*mr_dest==255) *mr_dest=*(backdroplookup[h1]+x1);
a+=afrac;
px++;
mr_count--;
mr_dest++;
}
}
}
break;
case sp_sky:
py=span_p->y-scrollmin;
if ((unsigned)py>=200) break;
px=spanx;
if ((unsigned)span_p->x2>320) break;
mr_count=span_p->x2-spanx;
mr_dest=viewylookup[py]+px;
if (windowHeight!=64) py=span_p->y+64;
h1=(hfrac*py)>>FRACBITS;
if (px<=w)
{
a=((TANANGLES/2)<<FRACBITS) + afrac*(w-px);
while (px<=w && mr_count>0)
{
x=backtangents[a>>FRACBITS];
x2=center - x + windowWidth - 257;
x2&=255;
*mr_dest=*(backdroplookup[h1]+x2);
a-=afrac;
px++;
mr_count--;
mr_dest++;
}
}
if (px>w)
{
a=((TANANGLES/2)<<FRACBITS) + afrac*(px-w);
while (mr_count>0)
{
x1=center + backtangents[a>>FRACBITS];
x1&=255;
*mr_dest=*(backdroplookup[h1]+x1);
a+=afrac;
px++;
mr_count--;
mr_dest++;
}
}
break;
case sp_step:
x=span_p->x2;
sp_dest=tpwalls_dest[x];
sp_source=span_p->picture;
sp_colormap=tpwalls_colormap[x];
sp_frac=span_p->y;
sp_fracstep=span_p->yh;
sp_count=tpwalls_count[x];
sp_loopvalue=(fixed_t)span_p->light<<FRACBITS;
ScalePost();
break;
case sp_shape:
DrawSprite();
break;
case sp_slope:
case sp_slopesky:
// sloping floor / ceiling span
lastz=-1; // we are going to get out of order here, so
if (span_p->shadow==0)
{
light=(pointz>>FRACBITS)+span_p->light;
if (light>MAXZLIGHT) break;
else if (light<0) light=0;
mr_colormap=zcolormap[light];
}
else if (span_p->shadow==9)
{
light=(pointz>>FRACBITS)+span_p->light+wallflicker4;
if (light>MAXZLIGHT) break;
else if (light<0) light=0;
mr_colormap=zcolormap[light];
}
else mr_colormap=(byte *)span_p->shadow;
x2=span_p->x2;
y1=span_p->y-scrollmin;
if ((unsigned)y1>=200) break;
if ((unsigned)x2>320) break;
mr_dest=viewylookup[y1]+spanx;
mr_picture=span_p->picture;
mr_count=x2-spanx;
// calculate starting texture point
length=FIXEDDIV(pointz, pixelcosine[spanx]);
angle=viewfineangle+pixelangle[spanx];
angle&=TANANGLES *4-1;
mr_xfrac=viewx+FIXEDMUL(length, cosines[angle]);
mr_yfrac=viewy-FIXEDMUL(length, sines[angle]);
// calculate ending texture point
// (yh is pointz2 for ending point)
length=FIXEDDIV(span_p->yh, pixelcosine[x2]);
angle=viewfineangle+pixelangle[x2];
angle&=TANANGLES *4-1;
xf2=viewx+FIXEDMUL(length, cosines[angle]);
yf2=viewy-FIXEDMUL(length, sines[angle]);
mr_xstep=(xf2-mr_xfrac)/mr_count;
mr_ystep=(yf2-mr_yfrac)/mr_count;
MapRow();
if (span_p->spantype==sp_slopesky)
{
py=span_p->y-scrollmin;
px=spanx;
mr_count=span_p->x2-spanx;
mr_dest=viewylookup[py]+px;
if (windowHeight!=64) py=span_p->y+64;
h1=(hfrac*py)>>FRACBITS;
if (px<=w)
{
a=((TANANGLES/2)<<FRACBITS) + afrac*(w-px);
while (px<=w && mr_count>0)
{
x=backtangents[a>>FRACBITS];
x2=center - x + windowWidth - 257;
x2&=255;
if (*mr_dest==255) *mr_dest=*(backdroplookup[h1]+x2);
a-=afrac;
px++;
mr_count--;
mr_dest++;
}
}
if (px>w)
{
a=((TANANGLES/2)<<FRACBITS) + afrac*(px-w);
while (mr_count>0)
{
x1=center + backtangents[a>>FRACBITS];
x1&=255;
if (*mr_dest==255) *mr_dest=*(backdroplookup[h1]+x1);
a+=afrac;
px++;
mr_count--;
mr_dest++;
}
}
}
break;
case sp_door:
case sp_maskeddoor:
DrawDoorPost();
break;
case sp_transparentwall:
x=span_p->x2;
sp_dest=tpwalls_dest[x];
sp_source=span_p->picture;
sp_colormap=tpwalls_colormap[x];
sp_frac=span_p->y;
sp_fracstep=span_p->yh;
sp_count=tpwalls_count[x];
sp_loopvalue=(fixed_t)span_p->light<<FRACBITS;
ScaleMaskedPost();
break;
case sp_inviswall:
x=span_p->x2;
sp_dest=tpwalls_dest[x];
sp_source=span_p->picture;
sp_colormap=tpwalls_colormap[x];
sp_frac=span_p->y;
sp_fracstep=span_p->yh;
sp_count=tpwalls_count[x];
sp_loopvalue=(fixed_t)span_p->light<<FRACBITS;
sp_dest-=windowWidth*(sp_count-1); // go to the top
--sp_loopvalue;
while (sp_count--)
{
color=sp_source[sp_frac>>FRACBITS];
if (color)
*sp_dest=*(translookup[sp_colormap[color]-1]+*sp_dest);
sp_dest+=windowWidth;
sp_frac+=sp_fracstep;
sp_frac&=sp_loopvalue;
}
break;
}
}
}