hw_bsp.c

The source code of Doom legacy for windows

// Emacs style mode select   -*- C++ -*- 
//-----------------------------------------------------------------------------
//
// $Id: hw_bsp.c,v 1.14 2001/05/01 20:38:34 hurdler Exp $
//
// Copyright (C) 1998-2000 by DooM Legacy Team.
//
// 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.
//
//
// $Log: hw_bsp.c,v $
// Revision 1.14  2001/05/01 20:38:34  hurdler
// some fix/hack for the beta release
//
// Revision 1.13  2001/04/16 15:16:26  hurdler
// minor changes
//
// Revision 1.12  2000/10/04 16:21:57  hurdler
// small clean-up
//
// Revision 1.11  2000/10/02 18:25:46  bpereira
// no message
//
// Revision 1.10  2000/08/11 19:11:57  metzgermeister
// *** empty log message ***
//
// Revision 1.9  2000/08/10 14:16:25  hurdler
// no message
//
// Revision 1.8  2000/08/03 17:57:42  bpereira
// no message
//
// Revision 1.7  2000/08/03 17:32:31  metzgermeister
// *** empty log message ***
//
// Revision 1.6  2000/03/13 21:41:40  linuxcub
// Removed my socalled "fix". The answer lies elsewhere :-( [e-mail]
//
// Revision 1.5  2000/03/12 23:01:29  linuxcub
// I really hope this doesn't break anything important. I'd like
// to hear from anyone, especially Linux/opengl users. Try
// running E4M7 from "ultimate doom", at least my patch improves
// that level, although other levels still render incorrectly.
// Erling Jacobsen, [e-mail]
//
// Revision 1.4  2000/03/06 18:44:00  hurdler
// hack for the polypoolsize problem
//
// Revision 1.3  2000/03/06 15:24:24  hurdler
// remove polypoolsize limit
//
// Revision 1.2  2000/02/27 00:42:11  hurdler
// fix CR+LF problem
//
// Revision 1.1.1.1  2000/02/22 20:32:33  hurdler
// Initial import into CVS (v1.29 pr3)
//
//
// DESCRIPTION:
//      convert Doom map
//
//-----------------------------------------------------------------------------


#include "hw_glob.h"
#include "../r_local.h"
#include "../z_zone.h"

// --------------------------------------------------------------------------
// This is global data for planes rendering
// --------------------------------------------------------------------------

extrasubsector_t*   extrasubsectors = NULL;

// newsubsectors are subsectors without segs, added for the plane polygons
#define NEWSUBSECTORS       50
int                 totsubsectors;
int                 addsubsector;

typedef struct { 
    float x;
    float y;
    float dx;
    float dy;
} fdivline_t;

// ==========================================================================
//                                    FLOOR & CEILING CONVEX POLYS GENERATION
// ==========================================================================

//debug counters
static int nobackpoly=0;
static int skipcut=0;
static int totalsubsecpolys=0;

// --------------------------------------------------------------------------
// Polygon fast alloc / free
// --------------------------------------------------------------------------
//hurdler: quick fix for those who wants to play with larger wad
#include "../m_argv.h"

#define ZPLANALLOC
#ifndef ZPLANALLOC
//#define POLYPOOLSIZE   1024000    // may be much over what is needed
//                                  //TODO: check out how much is used
static int POLYPOOLSIZE=1024000;

static byte*    gr_polypool=NULL;
static byte*    gr_ppcurrent;
static int      gr_ppfree;
#endif

// only between levels, clear poly pool
static void HWR_ClearPolys (void)
{
#ifndef ZPLANALLOC
    gr_ppcurrent = gr_polypool;
    gr_ppfree = POLYPOOLSIZE;
#endif
}


// allocate  pool for fast alloc of polys
void HWR_InitPolyPool (void)
{
#ifndef ZPLANALLOC
    int pnum;

    //hurdler: quick fix for those who wants to play with larger wad
    if ( (pnum=M_CheckParm("-polypoolsize")) )
        POLYPOOLSIZE = atoi(myargv[pnum+1])*1024; // (in kb)

    CONS_Printf ("HWR_InitPolyPool() : allocating %d bytes\n", POLYPOOLSIZE);
    gr_polypool = (byte*) malloc (POLYPOOLSIZE);
    if (!gr_polypool)
        I_Error ("HWR_InitPolyPool() : couldn't malloc polypool\n");
    HWR_ClearPolys ();
#endif
}

void HWR_FreePolyPool (void)
{
#ifndef ZPLANALLOC
    if (gr_polypool)
        free (gr_polypool);
    gr_polypool = NULL;
#endif
}

static poly_t* HWR_AllocPoly (int numpts)
{
    poly_t*     p;
    int         size;

    size = sizeof(poly_t) + sizeof(polyvertex_t) * numpts;
#ifdef ZPLANALLOC
    p = Z_Malloc(size, PU_HWRPLANE, NULL);
#else
#ifdef PARANOIA
    if(!gr_polypool)
        I_Error("Used gr_polypool without init !\n");
    if(!gr_ppcurrent)
        I_Error("gr_ppcurrent == NULL !!!\n");
#endif

    if (gr_ppfree < size)
        I_Error ("allocpoly() : no more memory %d bytes left, %d bytes needed\n\n%s\n", 
                  gr_ppfree, size, "You can try the param -polypoolsize 2048 (or higher if needed)");

    p = (poly_t*)gr_ppcurrent;
    gr_ppcurrent += size;
    gr_ppfree -= size;
#endif
    p->numpts = numpts;    
    return p;
}

static polyvertex_t* HWR_AllocVertex (void)
{
    polyvertex_t* p;
    int          size;

    size =  sizeof(polyvertex_t);
#ifdef ZPLANALLOC
    p = Z_Malloc(size, PU_HWRPLANE, NULL);
#else
    if (gr_ppfree < size)
        I_Error ("allocvertex() : no more memory %d bytes left, %d bytes needed\n\n%s\n", 
                  gr_ppfree, size, "You can try the param -polypoolsize 2048 (or higher if needed)");

    p = (polyvertex_t*)gr_ppcurrent;
    gr_ppcurrent += size;
    gr_ppfree -= size;
#endif
    return p;
}


//TODO: polygons should be freed in reverse order for efficiency,
// for now don't free because it doenst' free in reverse order
static void HWR_FreePoly (poly_t* poly)
{
#ifdef ZPLANALLOC
    Z_Free(poly);
#else
    int         size;
    
    size = sizeof(poly_t) + sizeof(polyvertex_t) * poly->numpts;
    memset(poly,0,size);
    //mempoly -= polysize;
#endif
}


// Return interception along bsp line,
// with the polygon segment
//
static float  bspfrac;
static polyvertex_t* fracdivline (fdivline_t* bsp, polyvertex_t* v1, polyvertex_t* v2)
{
static polyvertex_t  pt;
    double      frac;
    double      num;
    double      den;
    double      v1x,v1y,v1dx,v1dy;
    double      v2x,v2y,v2dx,v2dy;

    // a segment of a polygon
    v1x  = v1->x;
    v1y  = v1->y;
    v1dx = v2->x - v1->x;
    v1dy = v2->y - v1->y;

    // the bsp partition line
    v2x  = bsp->x;
    v2y  = bsp->y;
    v2dx = bsp->dx;
    v2dy = bsp->dy;

    den = v2dy*v1dx - v2dx*v1dy;
    if (den == 0)
        return NULL;       // parallel

    // first check the frac along the polygon segment,
    // (do not accept hit with the extensions)
    num = (v2x - v1x)*v2dy + (v1y - v2y)*v2dx;
    frac = num / den;
    if (frac<0 || frac>1)
        return NULL;

    // now get the frac along the BSP line
    // which is useful to determine what is left, what is right
    num = (v2x - v1x)*v1dy + (v1y - v2y)*v1dx;
    frac = num / den;
  bspfrac = frac;


    // find the interception point along the partition line
    pt.x = v2x + v2dx*frac;
    pt.y = v2y + v2dy*frac;

    return &pt;
}

//Hurdler: it's not used anymore
static boolean NearVertice (polyvertex_t* p1, polyvertex_t* p2)
{
#if 1
    float diff;
    diff = p2->x - p1->x;
    if (diff < -1.5f || diff > 1.5f)
       return false;
    diff = p2->y - p1->y;
    if (diff < -1.5f || diff > 1.5f)
       return false;
#else       
    if (p1->x != p2->x)
        return false;
    if (p1->y != p2->y)
        return false;
#endif
    // p1 and p2 are considered the same vertex
    return true;
}

// if two vertice coords have a x and/or y difference
// of less or equal than 1 FRACUNIT, they are considered the same
// point. Note: hardcoded value, 1.0f could be anything else.
static boolean SameVertice (polyvertex_t* p1, polyvertex_t* p2)
{
#if 0
    float diff;
    diff = p2->x - p1->x;
    if (diff < -1.5f || diff > 1.5f)
       return false;
    diff = p2->y - p1->y;
    if (diff < -1.5f || diff > 1.5f)
       return false;
#else       
    if (p1->x != p2->x)
        return false;
    if (p1->y != p2->y)
        return false;
#endif
    // p1 and p2 are considered the same vertex
    return true;
}


// split a _CONVEX_ polygon in two convex polygons
// outputs:
//   frontpoly : polygon on right side of bsp line
//   backpoly  : polygon on left side
//
static void SplitPoly (fdivline_t* bsp,         //splitting parametric line
                poly_t* poly,                   //the convex poly we split
                poly_t** frontpoly,             //return one poly here
                poly_t** backpoly)              //return the other here
{
    int     i,j;
    polyvertex_t *pv;

    int          ps,pe;
    int          nptfront,nptback;
    polyvertex_t vs;
    polyvertex_t ve;
    polyvertex_t lastpv;
    float        fracs = 0.0,frace = 0.0;   //used to tell which poly is on
                                // the front side of the bsp partition line
    int         psonline, peonline;

    ps = pe = -1;
    psonline = peonline = 0;

    for (i=0; i<poly->numpts; i++)
    {
        j=i+1;
        if (j==poly->numpts) j=0;

        // start & end points
        pv = fracdivline (bsp, &poly->pts[i], &poly->pts[j]);

        if (pv)
        {
            if (ps<0) {
                // first point
                ps = i;
                vs = *pv;
                fracs = bspfrac;
            }
            else {
                //the partition line traverse a junction between two segments
                // or the two points are so close, they can be considered as one
                // thus, don't accept, since split 2 must be another vertex
                if (SameVertice(pv, &lastpv))
                {