1 files changed, 775 insertions, 0 deletions

diff --git a/apps/plugins/sdl/progs/quake/r_edge.c b/apps/plugins/sdl/progs/quake/r_edge.c
new file mode 100644
index 0000000000..1fff765a3a
--- /dev/null
+++ b/apps/plugins/sdl/progs/quake/r_edge.c
@@ -0,0 +1,775 @@
+/*
+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);
+
+// made static
+//void R_LeadingEdge (edge_t *edge);
+//void R_LeadingEdgeBackwards (edge_t *edge);
+//void R_TrailingEdge (surf_t *surf, edge_t *edge);
+
+
+//=============================================================================
+
+
+/*
+==============
+R_DrawCulledPolys
+==============
+*/
+static inline 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] ; s<surface_p ; s++)
+                {
+                        if (!s->spans)
+                                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 ; v<r_refdef.vrectbottom ; v++)
+        {
+                newedges[v] = removeedges[v] = NULL;
+        }
+}
+
+
+#if     !id386
+
+/*
+==============
+R_InsertNewEdges
+
+Adds the edges in the linked list edgestoadd, adding them to the edges in the
+linked list edgelist.  edgestoadd is assumed to be sorted on u, and non-empty (this is actually newedges[v]).  edgelist is assumed to be sorted on u, with a
+sentinel at the end (actually, this is the active edge table starting at
+edge_head.next).
+==============
+*/
+void R_InsertNewEdges (edge_t *edgestoadd, edge_t *edgelist)
+{
+        edge_t  *next_edge;
+
+        do
+        {
+                next_edge = edgestoadd->next;
+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
+==============
+*/
+static inline 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
+==============
+*/
+static inline 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
+==============
+*/
+static inline 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<bottom ; iv++)
+        {
+                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) ();
+
+        // flush the span list if we can't be sure we have enough spans left for
+        // the next scan
+                if (span_p >= 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] ; s<surface_p ; s++)
+                                s->spans = 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 ();
+}
+
+