From a8f828a066773a59fdf646299359d35ae0e845af Mon Sep 17 00:00:00 2001 From: wyatt8740 Date: Mon, 6 Jan 2014 12:02:16 -0500 Subject: Removed accidental upload of copyrighted map files --- WinQuake/r_edge.c | 1548 ++++++++++++++++++++++++++--------------------------- 1 file changed, 774 insertions(+), 774 deletions(-) (limited to 'WinQuake/r_edge.c') diff --git a/WinQuake/r_edge.c b/WinQuake/r_edge.c index d434799..12a201d 100644 --- a/WinQuake/r_edge.c +++ b/WinQuake/r_edge.c @@ -1,774 +1,774 @@ -/* -Copyright (C) 1996-1997 Id Software, Inc. - -This program is free software; you can redistribute it and/or -modify it under the terms of the GNU General Public License -as published by the Free Software Foundation; either version 2 -of the License, or (at your option) any later version. - -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. - -See the GNU General Public License for more details. - -You should have received a copy of the GNU General Public License -along with this program; if not, write to the Free Software -Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - -*/ -// r_edge.c - -#include "quakedef.h" -#include "r_local.h" - -#if 0 -// FIXME -the complex cases add new polys on most lines, so dont optimize for keeping them the same -have multiple free span lists to try to get better coherence? -low depth complexity -- 1 to 3 or so - -this breaks spans at every edge, even hidden ones (bad) - -have a sentinal at both ends? -#endif - - -edge_t *auxedges; -edge_t *r_edges, *edge_p, *edge_max; - -surf_t *surfaces, *surface_p, *surf_max; - -// surfaces are generated in back to front order by the bsp, so if a surf -// pointer is greater than another one, it should be drawn in front -// surfaces[1] is the background, and is used as the active surface stack - -edge_t *newedges[MAXHEIGHT]; -edge_t *removeedges[MAXHEIGHT]; - -espan_t *span_p, *max_span_p; - -int r_currentkey; - -extern int screenwidth; - -int current_iv; - -int edge_head_u_shift20, edge_tail_u_shift20; - -static void (*pdrawfunc)(void); - -edge_t edge_head; -edge_t edge_tail; -edge_t edge_aftertail; -edge_t edge_sentinel; - -float fv; - -void R_GenerateSpans (void); -void R_GenerateSpansBackward (void); - -void R_LeadingEdge (edge_t *edge); -void R_LeadingEdgeBackwards (edge_t *edge); -void R_TrailingEdge (surf_t *surf, edge_t *edge); - - -//============================================================================= - - -/* -============== -R_DrawCulledPolys -============== -*/ -void R_DrawCulledPolys (void) -{ - surf_t *s; - msurface_t *pface; - - currententity = &cl_entities[0]; - - if (r_worldpolysbacktofront) - { - for (s=surface_p-1 ; s>&surfaces[1] ; s--) - { - if (!s->spans) - continue; - - if (!(s->flags & SURF_DRAWBACKGROUND)) - { - pface = (msurface_t *)s->data; - R_RenderPoly (pface, 15); - } - } - } - else - { - for (s = &surfaces[1] ; sspans) - continue; - - if (!(s->flags & SURF_DRAWBACKGROUND)) - { - pface = (msurface_t *)s->data; - R_RenderPoly (pface, 15); - } - } - } -} - - -/* -============== -R_BeginEdgeFrame -============== -*/ -void R_BeginEdgeFrame (void) -{ - int v; - - edge_p = r_edges; - edge_max = &r_edges[r_numallocatededges]; - - surface_p = &surfaces[2]; // background is surface 1, - // surface 0 is a dummy - surfaces[1].spans = NULL; // no background spans yet - surfaces[1].flags = SURF_DRAWBACKGROUND; - -// put the background behind everything in the world - if (r_draworder.value) - { - pdrawfunc = R_GenerateSpansBackward; - surfaces[1].key = 0; - r_currentkey = 1; - } - else - { - pdrawfunc = R_GenerateSpans; - surfaces[1].key = 0x7FFFFFFF; - r_currentkey = 0; - } - -// FIXME: set with memset - for (v=r_refdef.vrect.y ; vnext; -edgesearch: - if (edgelist->u >= edgestoadd->u) - goto addedge; - edgelist=edgelist->next; - if (edgelist->u >= edgestoadd->u) - goto addedge; - edgelist=edgelist->next; - if (edgelist->u >= edgestoadd->u) - goto addedge; - edgelist=edgelist->next; - if (edgelist->u >= edgestoadd->u) - goto addedge; - edgelist=edgelist->next; - goto edgesearch; - - // insert edgestoadd before edgelist -addedge: - edgestoadd->next = edgelist; - edgestoadd->prev = edgelist->prev; - edgelist->prev->next = edgestoadd; - edgelist->prev = edgestoadd; - } while ((edgestoadd = next_edge) != NULL); -} - -#endif // !id386 - - -#if !id386 - -/* -============== -R_RemoveEdges -============== -*/ -void R_RemoveEdges (edge_t *pedge) -{ - - do - { - pedge->next->prev = pedge->prev; - pedge->prev->next = pedge->next; - } while ((pedge = pedge->nextremove) != NULL); -} - -#endif // !id386 - - -#if !id386 - -/* -============== -R_StepActiveU -============== -*/ -void R_StepActiveU (edge_t *pedge) -{ - edge_t *pnext_edge, *pwedge; - - while (1) - { -nextedge: - pedge->u += pedge->u_step; - if (pedge->u < pedge->prev->u) - goto pushback; - pedge = pedge->next; - - pedge->u += pedge->u_step; - if (pedge->u < pedge->prev->u) - goto pushback; - pedge = pedge->next; - - pedge->u += pedge->u_step; - if (pedge->u < pedge->prev->u) - goto pushback; - pedge = pedge->next; - - pedge->u += pedge->u_step; - if (pedge->u < pedge->prev->u) - goto pushback; - pedge = pedge->next; - - goto nextedge; - -pushback: - if (pedge == &edge_aftertail) - return; - - // push it back to keep it sorted - pnext_edge = pedge->next; - - // pull the edge out of the edge list - pedge->next->prev = pedge->prev; - pedge->prev->next = pedge->next; - - // find out where the edge goes in the edge list - pwedge = pedge->prev->prev; - - while (pwedge->u > pedge->u) - { - pwedge = pwedge->prev; - } - - // put the edge back into the edge list - pedge->next = pwedge->next; - pedge->prev = pwedge; - pedge->next->prev = pedge; - pwedge->next = pedge; - - pedge = pnext_edge; - if (pedge == &edge_tail) - return; - } -} - -#endif // !id386 - - -/* -============== -R_CleanupSpan -============== -*/ -void R_CleanupSpan () -{ - surf_t *surf; - int iu; - espan_t *span; - -// now that we've reached the right edge of the screen, we're done with any -// unfinished surfaces, so emit a span for whatever's on top - surf = surfaces[1].next; - iu = edge_tail_u_shift20; - if (iu > surf->last_u) - { - span = span_p++; - span->u = surf->last_u; - span->count = iu - span->u; - span->v = current_iv; - span->pnext = surf->spans; - surf->spans = span; - } - -// reset spanstate for all surfaces in the surface stack - do - { - surf->spanstate = 0; - surf = surf->next; - } while (surf != &surfaces[1]); -} - - -/* -============== -R_LeadingEdgeBackwards -============== -*/ -void R_LeadingEdgeBackwards (edge_t *edge) -{ - espan_t *span; - surf_t *surf, *surf2; - int iu; - -// it's adding a new surface in, so find the correct place - surf = &surfaces[edge->surfs[1]]; - -// don't start a span if this is an inverted span, with the end -// edge preceding the start edge (that is, we've already seen the -// end edge) - if (++surf->spanstate == 1) - { - surf2 = surfaces[1].next; - - if (surf->key > surf2->key) - goto newtop; - - // if it's two surfaces on the same plane, the one that's already - // active is in front, so keep going unless it's a bmodel - if (surf->insubmodel && (surf->key == surf2->key)) - { - // must be two bmodels in the same leaf; don't care, because they'll - // never be farthest anyway - goto newtop; - } - -continue_search: - - do - { - surf2 = surf2->next; - } while (surf->key < surf2->key); - - if (surf->key == surf2->key) - { - // if it's two surfaces on the same plane, the one that's already - // active is in front, so keep going unless it's a bmodel - if (!surf->insubmodel) - goto continue_search; - - // must be two bmodels in the same leaf; don't care which is really - // in front, because they'll never be farthest anyway - } - - goto gotposition; - -newtop: - // emit a span (obscures current top) - iu = edge->u >> 20; - - if (iu > surf2->last_u) - { - span = span_p++; - span->u = surf2->last_u; - span->count = iu - span->u; - span->v = current_iv; - span->pnext = surf2->spans; - surf2->spans = span; - } - - // set last_u on the new span - surf->last_u = iu; - -gotposition: - // insert before surf2 - surf->next = surf2; - surf->prev = surf2->prev; - surf2->prev->next = surf; - surf2->prev = surf; - } -} - - -/* -============== -R_TrailingEdge -============== -*/ -void R_TrailingEdge (surf_t *surf, edge_t *edge) -{ - espan_t *span; - int iu; - -// don't generate a span if this is an inverted span, with the end -// edge preceding the start edge (that is, we haven't seen the -// start edge yet) - if (--surf->spanstate == 0) - { - if (surf->insubmodel) - r_bmodelactive--; - - if (surf == surfaces[1].next) - { - // emit a span (current top going away) - iu = edge->u >> 20; - if (iu > surf->last_u) - { - span = span_p++; - span->u = surf->last_u; - span->count = iu - span->u; - span->v = current_iv; - span->pnext = surf->spans; - surf->spans = span; - } - - // set last_u on the surface below - surf->next->last_u = iu; - } - - surf->prev->next = surf->next; - surf->next->prev = surf->prev; - } -} - - -#if !id386 - -/* -============== -R_LeadingEdge -============== -*/ -void R_LeadingEdge (edge_t *edge) -{ - espan_t *span; - surf_t *surf, *surf2; - int iu; - double fu, newzi, testzi, newzitop, newzibottom; - - if (edge->surfs[1]) - { - // it's adding a new surface in, so find the correct place - surf = &surfaces[edge->surfs[1]]; - - // don't start a span if this is an inverted span, with the end - // edge preceding the start edge (that is, we've already seen the - // end edge) - if (++surf->spanstate == 1) - { - if (surf->insubmodel) - r_bmodelactive++; - - surf2 = surfaces[1].next; - - if (surf->key < surf2->key) - goto newtop; - - // if it's two surfaces on the same plane, the one that's already - // active is in front, so keep going unless it's a bmodel - if (surf->insubmodel && (surf->key == surf2->key)) - { - // must be two bmodels in the same leaf; sort on 1/z - fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000); - newzi = surf->d_ziorigin + fv*surf->d_zistepv + - fu*surf->d_zistepu; - newzibottom = newzi * 0.99; - - testzi = surf2->d_ziorigin + fv*surf2->d_zistepv + - fu*surf2->d_zistepu; - - if (newzibottom >= testzi) - { - goto newtop; - } - - newzitop = newzi * 1.01; - if (newzitop >= testzi) - { - if (surf->d_zistepu >= surf2->d_zistepu) - { - goto newtop; - } - } - } - -continue_search: - - do - { - surf2 = surf2->next; - } while (surf->key > surf2->key); - - if (surf->key == surf2->key) - { - // if it's two surfaces on the same plane, the one that's already - // active is in front, so keep going unless it's a bmodel - if (!surf->insubmodel) - goto continue_search; - - // must be two bmodels in the same leaf; sort on 1/z - fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000); - newzi = surf->d_ziorigin + fv*surf->d_zistepv + - fu*surf->d_zistepu; - newzibottom = newzi * 0.99; - - testzi = surf2->d_ziorigin + fv*surf2->d_zistepv + - fu*surf2->d_zistepu; - - if (newzibottom >= testzi) - { - goto gotposition; - } - - newzitop = newzi * 1.01; - if (newzitop >= testzi) - { - if (surf->d_zistepu >= surf2->d_zistepu) - { - goto gotposition; - } - } - - goto continue_search; - } - - goto gotposition; - -newtop: - // emit a span (obscures current top) - iu = edge->u >> 20; - - if (iu > surf2->last_u) - { - span = span_p++; - span->u = surf2->last_u; - span->count = iu - span->u; - span->v = current_iv; - span->pnext = surf2->spans; - surf2->spans = span; - } - - // set last_u on the new span - surf->last_u = iu; - -gotposition: - // insert before surf2 - surf->next = surf2; - surf->prev = surf2->prev; - surf2->prev->next = surf; - surf2->prev = surf; - } - } -} - - -/* -============== -R_GenerateSpans -============== -*/ -void R_GenerateSpans (void) -{ - edge_t *edge; - surf_t *surf; - - r_bmodelactive = 0; - -// clear active surfaces to just the background surface - surfaces[1].next = surfaces[1].prev = &surfaces[1]; - surfaces[1].last_u = edge_head_u_shift20; - -// generate spans - for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next) - { - if (edge->surfs[0]) - { - // it has a left surface, so a surface is going away for this span - surf = &surfaces[edge->surfs[0]]; - - R_TrailingEdge (surf, edge); - - if (!edge->surfs[1]) - continue; - } - - R_LeadingEdge (edge); - } - - R_CleanupSpan (); -} - -#endif // !id386 - - -/* -============== -R_GenerateSpansBackward -============== -*/ -void R_GenerateSpansBackward (void) -{ - edge_t *edge; - - r_bmodelactive = 0; - -// clear active surfaces to just the background surface - surfaces[1].next = surfaces[1].prev = &surfaces[1]; - surfaces[1].last_u = edge_head_u_shift20; - -// generate spans - for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next) - { - if (edge->surfs[0]) - R_TrailingEdge (&surfaces[edge->surfs[0]], edge); - - if (edge->surfs[1]) - R_LeadingEdgeBackwards (edge); - } - - R_CleanupSpan (); -} - - -/* -============== -R_ScanEdges - -Input: -newedges[] array - this has links to edges, which have links to surfaces - -Output: -Each surface has a linked list of its visible spans -============== -*/ -void R_ScanEdges (void) -{ - int iv, bottom; - byte basespans[MAXSPANS*sizeof(espan_t)+CACHE_SIZE]; - espan_t *basespan_p; - surf_t *s; - - basespan_p = (espan_t *) - ((long)(basespans + CACHE_SIZE - 1) & ~(CACHE_SIZE - 1)); - max_span_p = &basespan_p[MAXSPANS - r_refdef.vrect.width]; - - span_p = basespan_p; - -// clear active edges to just the background edges around the whole screen -// FIXME: most of this only needs to be set up once - edge_head.u = r_refdef.vrect.x << 20; - edge_head_u_shift20 = edge_head.u >> 20; - edge_head.u_step = 0; - edge_head.prev = NULL; - edge_head.next = &edge_tail; - edge_head.surfs[0] = 0; - edge_head.surfs[1] = 1; - - edge_tail.u = (r_refdef.vrectright << 20) + 0xFFFFF; - edge_tail_u_shift20 = edge_tail.u >> 20; - edge_tail.u_step = 0; - edge_tail.prev = &edge_head; - edge_tail.next = &edge_aftertail; - edge_tail.surfs[0] = 1; - edge_tail.surfs[1] = 0; - - edge_aftertail.u = -1; // force a move - edge_aftertail.u_step = 0; - edge_aftertail.next = &edge_sentinel; - edge_aftertail.prev = &edge_tail; - -// FIXME: do we need this now that we clamp x in r_draw.c? - edge_sentinel.u = 2000 << 24; // make sure nothing sorts past this - edge_sentinel.prev = &edge_aftertail; - -// -// process all scan lines -// - bottom = r_refdef.vrectbottom - 1; - - for (iv=r_refdef.vrect.y ; iv= max_span_p) - { - VID_UnlockBuffer (); - S_ExtraUpdate (); // don't let sound get messed up if going slow - VID_LockBuffer (); - - if (r_drawculledpolys) - { - R_DrawCulledPolys (); - } - else - { - D_DrawSurfaces (); - } - - // clear the surface span pointers - for (s = &surfaces[1] ; sspans = NULL; - - span_p = basespan_p; - } - - if (removeedges[iv]) - R_RemoveEdges (removeedges[iv]); - - if (edge_head.next != &edge_tail) - R_StepActiveU (edge_head.next); - } - -// do the last scan (no need to step or sort or remove on the last scan) - - current_iv = iv; - fv = (float)iv; - -// mark that the head (background start) span is pre-included - surfaces[1].spanstate = 1; - - if (newedges[iv]) - R_InsertNewEdges (newedges[iv], edge_head.next); - - (*pdrawfunc) (); - -// draw whatever's left in the span list - if (r_drawculledpolys) - R_DrawCulledPolys (); - else - D_DrawSurfaces (); -} - - +/* +Copyright (C) 1996-1997 Id Software, Inc. + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + +See the GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + +*/ +// r_edge.c + +#include "quakedef.h" +#include "r_local.h" + +#if 0 +// FIXME +the complex cases add new polys on most lines, so dont optimize for keeping them the same +have multiple free span lists to try to get better coherence? +low depth complexity -- 1 to 3 or so + +this breaks spans at every edge, even hidden ones (bad) + +have a sentinal at both ends? +#endif + + +edge_t *auxedges; +edge_t *r_edges, *edge_p, *edge_max; + +surf_t *surfaces, *surface_p, *surf_max; + +// surfaces are generated in back to front order by the bsp, so if a surf +// pointer is greater than another one, it should be drawn in front +// surfaces[1] is the background, and is used as the active surface stack + +edge_t *newedges[MAXHEIGHT]; +edge_t *removeedges[MAXHEIGHT]; + +espan_t *span_p, *max_span_p; + +int r_currentkey; + +extern int screenwidth; + +int current_iv; + +int edge_head_u_shift20, edge_tail_u_shift20; + +static void (*pdrawfunc)(void); + +edge_t edge_head; +edge_t edge_tail; +edge_t edge_aftertail; +edge_t edge_sentinel; + +float fv; + +void R_GenerateSpans (void); +void R_GenerateSpansBackward (void); + +void R_LeadingEdge (edge_t *edge); +void R_LeadingEdgeBackwards (edge_t *edge); +void R_TrailingEdge (surf_t *surf, edge_t *edge); + + +//============================================================================= + + +/* +============== +R_DrawCulledPolys +============== +*/ +void R_DrawCulledPolys (void) +{ + surf_t *s; + msurface_t *pface; + + currententity = &cl_entities[0]; + + if (r_worldpolysbacktofront) + { + for (s=surface_p-1 ; s>&surfaces[1] ; s--) + { + if (!s->spans) + continue; + + if (!(s->flags & SURF_DRAWBACKGROUND)) + { + pface = (msurface_t *)s->data; + R_RenderPoly (pface, 15); + } + } + } + else + { + for (s = &surfaces[1] ; sspans) + continue; + + if (!(s->flags & SURF_DRAWBACKGROUND)) + { + pface = (msurface_t *)s->data; + R_RenderPoly (pface, 15); + } + } + } +} + + +/* +============== +R_BeginEdgeFrame +============== +*/ +void R_BeginEdgeFrame (void) +{ + int v; + + edge_p = r_edges; + edge_max = &r_edges[r_numallocatededges]; + + surface_p = &surfaces[2]; // background is surface 1, + // surface 0 is a dummy + surfaces[1].spans = NULL; // no background spans yet + surfaces[1].flags = SURF_DRAWBACKGROUND; + +// put the background behind everything in the world + if (r_draworder.value) + { + pdrawfunc = R_GenerateSpansBackward; + surfaces[1].key = 0; + r_currentkey = 1; + } + else + { + pdrawfunc = R_GenerateSpans; + surfaces[1].key = 0x7FFFFFFF; + r_currentkey = 0; + } + +// FIXME: set with memset + for (v=r_refdef.vrect.y ; vnext; +edgesearch: + if (edgelist->u >= edgestoadd->u) + goto addedge; + edgelist=edgelist->next; + if (edgelist->u >= edgestoadd->u) + goto addedge; + edgelist=edgelist->next; + if (edgelist->u >= edgestoadd->u) + goto addedge; + edgelist=edgelist->next; + if (edgelist->u >= edgestoadd->u) + goto addedge; + edgelist=edgelist->next; + goto edgesearch; + + // insert edgestoadd before edgelist +addedge: + edgestoadd->next = edgelist; + edgestoadd->prev = edgelist->prev; + edgelist->prev->next = edgestoadd; + edgelist->prev = edgestoadd; + } while ((edgestoadd = next_edge) != NULL); +} + +#endif // !id386 + + +#if !id386 + +/* +============== +R_RemoveEdges +============== +*/ +void R_RemoveEdges (edge_t *pedge) +{ + + do + { + pedge->next->prev = pedge->prev; + pedge->prev->next = pedge->next; + } while ((pedge = pedge->nextremove) != NULL); +} + +#endif // !id386 + + +#if !id386 + +/* +============== +R_StepActiveU +============== +*/ +void R_StepActiveU (edge_t *pedge) +{ + edge_t *pnext_edge, *pwedge; + + while (1) + { +nextedge: + pedge->u += pedge->u_step; + if (pedge->u < pedge->prev->u) + goto pushback; + pedge = pedge->next; + + pedge->u += pedge->u_step; + if (pedge->u < pedge->prev->u) + goto pushback; + pedge = pedge->next; + + pedge->u += pedge->u_step; + if (pedge->u < pedge->prev->u) + goto pushback; + pedge = pedge->next; + + pedge->u += pedge->u_step; + if (pedge->u < pedge->prev->u) + goto pushback; + pedge = pedge->next; + + goto nextedge; + +pushback: + if (pedge == &edge_aftertail) + return; + + // push it back to keep it sorted + pnext_edge = pedge->next; + + // pull the edge out of the edge list + pedge->next->prev = pedge->prev; + pedge->prev->next = pedge->next; + + // find out where the edge goes in the edge list + pwedge = pedge->prev->prev; + + while (pwedge->u > pedge->u) + { + pwedge = pwedge->prev; + } + + // put the edge back into the edge list + pedge->next = pwedge->next; + pedge->prev = pwedge; + pedge->next->prev = pedge; + pwedge->next = pedge; + + pedge = pnext_edge; + if (pedge == &edge_tail) + return; + } +} + +#endif // !id386 + + +/* +============== +R_CleanupSpan +============== +*/ +void R_CleanupSpan () +{ + surf_t *surf; + int iu; + espan_t *span; + +// now that we've reached the right edge of the screen, we're done with any +// unfinished surfaces, so emit a span for whatever's on top + surf = surfaces[1].next; + iu = edge_tail_u_shift20; + if (iu > surf->last_u) + { + span = span_p++; + span->u = surf->last_u; + span->count = iu - span->u; + span->v = current_iv; + span->pnext = surf->spans; + surf->spans = span; + } + +// reset spanstate for all surfaces in the surface stack + do + { + surf->spanstate = 0; + surf = surf->next; + } while (surf != &surfaces[1]); +} + + +/* +============== +R_LeadingEdgeBackwards +============== +*/ +void R_LeadingEdgeBackwards (edge_t *edge) +{ + espan_t *span; + surf_t *surf, *surf2; + int iu; + +// it's adding a new surface in, so find the correct place + surf = &surfaces[edge->surfs[1]]; + +// don't start a span if this is an inverted span, with the end +// edge preceding the start edge (that is, we've already seen the +// end edge) + if (++surf->spanstate == 1) + { + surf2 = surfaces[1].next; + + if (surf->key > surf2->key) + goto newtop; + + // if it's two surfaces on the same plane, the one that's already + // active is in front, so keep going unless it's a bmodel + if (surf->insubmodel && (surf->key == surf2->key)) + { + // must be two bmodels in the same leaf; don't care, because they'll + // never be farthest anyway + goto newtop; + } + +continue_search: + + do + { + surf2 = surf2->next; + } while (surf->key < surf2->key); + + if (surf->key == surf2->key) + { + // if it's two surfaces on the same plane, the one that's already + // active is in front, so keep going unless it's a bmodel + if (!surf->insubmodel) + goto continue_search; + + // must be two bmodels in the same leaf; don't care which is really + // in front, because they'll never be farthest anyway + } + + goto gotposition; + +newtop: + // emit a span (obscures current top) + iu = edge->u >> 20; + + if (iu > surf2->last_u) + { + span = span_p++; + span->u = surf2->last_u; + span->count = iu - span->u; + span->v = current_iv; + span->pnext = surf2->spans; + surf2->spans = span; + } + + // set last_u on the new span + surf->last_u = iu; + +gotposition: + // insert before surf2 + surf->next = surf2; + surf->prev = surf2->prev; + surf2->prev->next = surf; + surf2->prev = surf; + } +} + + +/* +============== +R_TrailingEdge +============== +*/ +void R_TrailingEdge (surf_t *surf, edge_t *edge) +{ + espan_t *span; + int iu; + +// don't generate a span if this is an inverted span, with the end +// edge preceding the start edge (that is, we haven't seen the +// start edge yet) + if (--surf->spanstate == 0) + { + if (surf->insubmodel) + r_bmodelactive--; + + if (surf == surfaces[1].next) + { + // emit a span (current top going away) + iu = edge->u >> 20; + if (iu > surf->last_u) + { + span = span_p++; + span->u = surf->last_u; + span->count = iu - span->u; + span->v = current_iv; + span->pnext = surf->spans; + surf->spans = span; + } + + // set last_u on the surface below + surf->next->last_u = iu; + } + + surf->prev->next = surf->next; + surf->next->prev = surf->prev; + } +} + + +#if !id386 + +/* +============== +R_LeadingEdge +============== +*/ +void R_LeadingEdge (edge_t *edge) +{ + espan_t *span; + surf_t *surf, *surf2; + int iu; + double fu, newzi, testzi, newzitop, newzibottom; + + if (edge->surfs[1]) + { + // it's adding a new surface in, so find the correct place + surf = &surfaces[edge->surfs[1]]; + + // don't start a span if this is an inverted span, with the end + // edge preceding the start edge (that is, we've already seen the + // end edge) + if (++surf->spanstate == 1) + { + if (surf->insubmodel) + r_bmodelactive++; + + surf2 = surfaces[1].next; + + if (surf->key < surf2->key) + goto newtop; + + // if it's two surfaces on the same plane, the one that's already + // active is in front, so keep going unless it's a bmodel + if (surf->insubmodel && (surf->key == surf2->key)) + { + // must be two bmodels in the same leaf; sort on 1/z + fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000); + newzi = surf->d_ziorigin + fv*surf->d_zistepv + + fu*surf->d_zistepu; + newzibottom = newzi * 0.99; + + testzi = surf2->d_ziorigin + fv*surf2->d_zistepv + + fu*surf2->d_zistepu; + + if (newzibottom >= testzi) + { + goto newtop; + } + + newzitop = newzi * 1.01; + if (newzitop >= testzi) + { + if (surf->d_zistepu >= surf2->d_zistepu) + { + goto newtop; + } + } + } + +continue_search: + + do + { + surf2 = surf2->next; + } while (surf->key > surf2->key); + + if (surf->key == surf2->key) + { + // if it's two surfaces on the same plane, the one that's already + // active is in front, so keep going unless it's a bmodel + if (!surf->insubmodel) + goto continue_search; + + // must be two bmodels in the same leaf; sort on 1/z + fu = (float)(edge->u - 0xFFFFF) * (1.0 / 0x100000); + newzi = surf->d_ziorigin + fv*surf->d_zistepv + + fu*surf->d_zistepu; + newzibottom = newzi * 0.99; + + testzi = surf2->d_ziorigin + fv*surf2->d_zistepv + + fu*surf2->d_zistepu; + + if (newzibottom >= testzi) + { + goto gotposition; + } + + newzitop = newzi * 1.01; + if (newzitop >= testzi) + { + if (surf->d_zistepu >= surf2->d_zistepu) + { + goto gotposition; + } + } + + goto continue_search; + } + + goto gotposition; + +newtop: + // emit a span (obscures current top) + iu = edge->u >> 20; + + if (iu > surf2->last_u) + { + span = span_p++; + span->u = surf2->last_u; + span->count = iu - span->u; + span->v = current_iv; + span->pnext = surf2->spans; + surf2->spans = span; + } + + // set last_u on the new span + surf->last_u = iu; + +gotposition: + // insert before surf2 + surf->next = surf2; + surf->prev = surf2->prev; + surf2->prev->next = surf; + surf2->prev = surf; + } + } +} + + +/* +============== +R_GenerateSpans +============== +*/ +void R_GenerateSpans (void) +{ + edge_t *edge; + surf_t *surf; + + r_bmodelactive = 0; + +// clear active surfaces to just the background surface + surfaces[1].next = surfaces[1].prev = &surfaces[1]; + surfaces[1].last_u = edge_head_u_shift20; + +// generate spans + for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next) + { + if (edge->surfs[0]) + { + // it has a left surface, so a surface is going away for this span + surf = &surfaces[edge->surfs[0]]; + + R_TrailingEdge (surf, edge); + + if (!edge->surfs[1]) + continue; + } + + R_LeadingEdge (edge); + } + + R_CleanupSpan (); +} + +#endif // !id386 + + +/* +============== +R_GenerateSpansBackward +============== +*/ +void R_GenerateSpansBackward (void) +{ + edge_t *edge; + + r_bmodelactive = 0; + +// clear active surfaces to just the background surface + surfaces[1].next = surfaces[1].prev = &surfaces[1]; + surfaces[1].last_u = edge_head_u_shift20; + +// generate spans + for (edge=edge_head.next ; edge != &edge_tail; edge=edge->next) + { + if (edge->surfs[0]) + R_TrailingEdge (&surfaces[edge->surfs[0]], edge); + + if (edge->surfs[1]) + R_LeadingEdgeBackwards (edge); + } + + R_CleanupSpan (); +} + + +/* +============== +R_ScanEdges + +Input: +newedges[] array + this has links to edges, which have links to surfaces + +Output: +Each surface has a linked list of its visible spans +============== +*/ +void R_ScanEdges (void) +{ + int iv, bottom; + byte basespans[MAXSPANS*sizeof(espan_t)+CACHE_SIZE]; + espan_t *basespan_p; + surf_t *s; + + basespan_p = (espan_t *) + ((long)(basespans + CACHE_SIZE - 1) & ~(CACHE_SIZE - 1)); + max_span_p = &basespan_p[MAXSPANS - r_refdef.vrect.width]; + + span_p = basespan_p; + +// clear active edges to just the background edges around the whole screen +// FIXME: most of this only needs to be set up once + edge_head.u = r_refdef.vrect.x << 20; + edge_head_u_shift20 = edge_head.u >> 20; + edge_head.u_step = 0; + edge_head.prev = NULL; + edge_head.next = &edge_tail; + edge_head.surfs[0] = 0; + edge_head.surfs[1] = 1; + + edge_tail.u = (r_refdef.vrectright << 20) + 0xFFFFF; + edge_tail_u_shift20 = edge_tail.u >> 20; + edge_tail.u_step = 0; + edge_tail.prev = &edge_head; + edge_tail.next = &edge_aftertail; + edge_tail.surfs[0] = 1; + edge_tail.surfs[1] = 0; + + edge_aftertail.u = -1; // force a move + edge_aftertail.u_step = 0; + edge_aftertail.next = &edge_sentinel; + edge_aftertail.prev = &edge_tail; + +// FIXME: do we need this now that we clamp x in r_draw.c? + edge_sentinel.u = 2000 << 24; // make sure nothing sorts past this + edge_sentinel.prev = &edge_aftertail; + +// +// process all scan lines +// + bottom = r_refdef.vrectbottom - 1; + + for (iv=r_refdef.vrect.y ; iv= max_span_p) + { + VID_UnlockBuffer (); + S_ExtraUpdate (); // don't let sound get messed up if going slow + VID_LockBuffer (); + + if (r_drawculledpolys) + { + R_DrawCulledPolys (); + } + else + { + D_DrawSurfaces (); + } + + // clear the surface span pointers + for (s = &surfaces[1] ; sspans = NULL; + + span_p = basespan_p; + } + + if (removeedges[iv]) + R_RemoveEdges (removeedges[iv]); + + if (edge_head.next != &edge_tail) + R_StepActiveU (edge_head.next); + } + +// do the last scan (no need to step or sort or remove on the last scan) + + current_iv = iv; + fv = (float)iv; + +// mark that the head (background start) span is pre-included + surfaces[1].spanstate = 1; + + if (newedges[iv]) + R_InsertNewEdges (newedges[iv], edge_head.next); + + (*pdrawfunc) (); + +// draw whatever's left in the span list + if (r_drawculledpolys) + R_DrawCulledPolys (); + else + D_DrawSurfaces (); +} + + -- cgit v1.2.3