hw_bsp.c

The source code of Doom legacy for windows

                    if (pe<0) {
                        ps = i;
                        psonline = 1;
                    }
                    else {
                        pe = i;
                        peonline = 1;
                    }
                }else{
                    if (pe<0) {
                        pe = i;
                        ve = *pv;
                        frace = bspfrac;
                    }
                    else {
                    // a frac, not same vertice as last one
                    // we already got pt2 so pt 2 is not on the line,
                    // so we probably got back to the start point
                    // which is on the line
                        if (SameVertice(pv, &vs))
                            psonline = 1;
                        break;
                    }
                }
            }

            // remember last point intercept to detect identical points
            lastpv = *pv;
        }
    }

    // no split : the partition line is either parallel and
    // aligned with one of the poly segments, or the line is totally
    // out of the polygon and doesn't traverse it (happens if the bsp
    // is fooled by some trick where the sidedefs don't point to
    // the right sectors)
    if (ps<0)
    {
        //I_Error ("SplitPoly: did not split polygon (%d %d)\n"
        //         "debugpos %d",ps,pe,debugpos);

        // this eventually happens with 'broken' BSP's that accept
        // linedefs where each side point the same sector, that is:
        // the deep water effect with the original Doom

        //TODO: make sure front poly is to front of partition line?

        *frontpoly = poly;
        *backpoly  = NULL;
        return;
    }

    if (ps>=0 && pe<0)
    {
        //I_Error ("SplitPoly: only one point for split line (%d %d)",ps,pe);
        *frontpoly = poly;
        *backpoly  = NULL;
        return;
    }
    if (pe<=ps)
        I_Error ("SplitPoly: invalid splitting line (%d %d)",ps,pe);

    // number of points on each side, _not_ counting those
    // that may lie just one the line
    nptback  = pe - ps - peonline;
    nptfront = poly->numpts - peonline - psonline - nptback;

    if (nptback>0)
       *backpoly = HWR_AllocPoly (2 + nptback);
    else
       *backpoly = NULL;
    if (nptfront)
       *frontpoly = HWR_AllocPoly (2 + nptfront);
    else
       *frontpoly = NULL;

    // generate FRONT poly
    if (*frontpoly)
    {
        pv = (*frontpoly)->pts;
        *pv++ = vs;
        *pv++ = ve;
        i = pe;
        do {
            if (++i == poly->numpts)
               i=0;
            *pv++ = poly->pts[i];
        } while (i!=ps && --nptfront);
    }

    // generate BACK poly
    if (*backpoly)
    {
        pv = (*backpoly)->pts;
        *pv++ = ve;
        *pv++ = vs;
        i = ps;
        do {
            if (++i == poly->numpts)
               i=0;
            *pv++ = poly->pts[i];
        } while (i!=pe && --nptback);
    }

    // make sure frontpoly is the one on the 'right' side
    // of the partition line
    if (fracs>frace)
    {
        poly_t*     swappoly;
        swappoly = *backpoly;
        *backpoly= *frontpoly;
        *frontpoly = swappoly;
    }

    HWR_FreePoly (poly);
}


// use each seg of the poly as a partition line, keep only the
// part of the convex poly to the front of the seg (that is,
// the part inside the sector), the part behind the seg, is
// the void space and is cut out
//
static poly_t* CutOutSubsecPoly (seg_t* lseg, int count, poly_t* poly)
{
    int         i,j;
    
    polyvertex_t *pv;
    
    int          nump=0,ps,pe;
    polyvertex_t vs,ve,p1,p2;
    float        fracs=0.0;
    
    fdivline_t   cutseg;     //x,y,dx,dy as start of node_t struct
    
    poly_t*      temppoly;
    
    // for each seg of the subsector
    for(;count--;lseg++)
    {
        // no need to cut with a two sided line
        //if(lseg->backsector==NULL)
        //    continue;
        //x,y,dx,dy (like a divline)
        p1.x = lseg->v1->x*crapmul;
        p1.y = lseg->v1->y*crapmul;
        p2.x = lseg->v2->x*crapmul;
        p2.y = lseg->v2->y*crapmul;

        cutseg.x = p1.x;
        cutseg.y = p1.y;
        cutseg.dx = p2.x - p1.x;
        cutseg.dy = p2.y - p1.y;
        
        // see if it cuts the convex poly
        ps = -1;
        pe = -1;
        for (i=0; i<poly->numpts; i++)
        {
            j=i+1;
            if (j==poly->numpts)
                j=0;
            
            pv = fracdivline (&cutseg, &poly->pts[i], &poly->pts[j]);
            
            if (pv)
            {
                if (ps<0) {
                    ps = i;
                    vs = *pv;
                    fracs = bspfrac;
                }
                else {
                    //frac 1 on previous segment,
                    //     0 on the next,
                    //the split line goes through one of the convex poly
                    // vertices, happens quite often since the convex
                    // poly is already adjacent to the subsector segs
                    // on most borders
                    if (SameVertice(pv, &vs))
                        continue;
                    
                    if (fracs<=bspfrac) {
                        nump = 2 + poly->numpts - (i-ps);
                        pe = ps;
                        ps = i;
                        ve = *pv;
                    }
                    else {
                        nump = 2 + (i-ps);
                        pe = i;
                        ve = vs;
                        vs = *pv;
                    }
                    //found 2nd point
                    break;
                }
            }
        }
        
        // there was a split
        if (ps>=0)
        {
            //need 2 points
            if (pe>=0)
            {
                // generate FRONT poly
                temppoly = HWR_AllocPoly (nump);
                pv = temppoly->pts;
                *pv++ = vs;
                *pv++ = ve;
                do {
                    if (++ps == poly->numpts)
                        ps=0;
                    *pv++ = poly->pts[ps];
                } while (ps!=pe);
                HWR_FreePoly(poly);
                poly = temppoly;
            }
            //hmmm... maybe we should NOT accept this, but this happens
            // only when the cut is not needed it seems (when the cut
            // line is aligned to one of the borders of the poly, and
            // only some times..)
            else
                skipcut++;
            //    I_Error ("CutOutPoly: only one point for split line (%d %d) %d",ps,pe,debugpos);
        }
    }
    return poly;
}


// At this point, the poly should be convex and the exact
// layout of the subsector, it is not always the case,
// so continue to cut off the poly into smaller parts with
// each seg of the subsector.
//
static void HWR_SubsecPoly (int num, poly_t* poly)
{
    int          count;
    subsector_t* sub;
    seg_t*       lseg;

    sscount++;

    sub = &subsectors[num];
    count = sub->numlines;
    lseg = &segs[sub->firstline];

    if (poly) {
        poly = CutOutSubsecPoly (lseg,count,poly);
        totalsubsecpolys++;
        //extra data for this subsector
        extrasubsectors[num].planepoly = poly;
    }
}

// the bsp divline have not enouth presition 
// search for the segs source of this divline
void SearchDivline(node_t* bsp,fdivline_t *divline)
{
    int i;
    line_t* line=NULL;
    float   nearline=0.0;
    boolean side;

    for(i=0;i<numsegs;i++)
    {
        if( segs[i].v1->x == bsp->x && segs[i].v1->y == bsp->y )
        {
            float dx = (segs[i].v1->x - segs[i].v2->x);
            float dy = (segs[i].v1->y - segs[i].v2->y);
            float tmp=bsp->dy*dx-bsp->dx*dy;
            
            if (abs(tmp)<abs(nearline) || !line)
            {
                line=segs[i].linedef;
                nearline=tmp;
                side=true;
            }
        } 
        else
        if( segs[i].v2->x == bsp->x && segs[i].v2->y == bsp->y )
        {
            float dx = segs[i].v2->x - segs[i].v1->x;
            float dy = segs[i].v2->y - segs[i].v1->y;
            float tmp=bsp->dy*dx - bsp->dx*dy;

            if (abs(tmp)<abs(nearline) || !line)
            {
                line=segs[i].linedef;
                nearline=tmp;
                side=false;
            }
        } 
    }

    if( line && abs(nearline*crapmul*crapmul)<=20 
        && false // FIXME: There are severe problems in some levels without this - we should fix it properly!
        )
    {
        if( devparm )
            CONS_Printf("Found divline %-6.2f\n",nearline*crapmul*crapmul);
        divline->x=line->v1->x*crapmul;
        divline->y=line->v1->y*crapmul;
        divline->dx=(line->v2->x-line->v1->x)*crapmul;
        divline->dy=(line->v2->y-line->v1->y)*crapmul;
        if(bsp->dx*divline->dx<0)
            divline->dx = -divline->dx;
        if(bsp->dy*divline->dy<0)
            divline->dy = -divline->dy;
    }
    else
    {
        if( devparm )
            CONS_Printf("Divline not found %-6.2f\n",nearline*crapmul*crapmul);
        divline->x=bsp->x*crapmul;
        divline->y=bsp->y*crapmul;
        divline->dx=bsp->dx*crapmul;
        divline->dy=bsp->dy*crapmul;
    }
}

//#define BP_FIX_BBOX

// poly : the convex polygon that encloses all child subsectors
static void WalkBSPNode (int bspnum, poly_t* poly, unsigned short* leafnode, fixed_t *bbox)
{
    node_t*     bsp;

    poly_t*     backpoly;
    poly_t*     frontpoly;
    fdivline_t  fdivline;   
    polyvertex_t*   pt;
    int     i;

    // Found a subsector?
    if (bspnum & NF_SUBSECTOR)
    {
        if (bspnum == -1)
        {
            // BP: i think this code is useless and wrong because
            // - bspnum==-1 happens only when numsubsectors == 0
            // - it can't happens in bsp recursive call since bspnum is a int and children is unsigned short
            // - the BSP is complet !! (there just can have subsector without segs) (i am not sure of this point)

            // do we have a valid polygon ?
            if (poly && poly->numpts > 2) {
                CONS_Printf ("Adding a new subsector !!!\n");
                if (addsubsector == numsubsectors + NEWSUBSECTORS)
                    I_Error ("WalkBSPNode : not enough addsubsectors\n");
                else if (addsubsector > 0x7fff)
                    I_Error ("WalkBSPNode : addsubsector > 0x7fff\n");
                *leafnode = (unsigned short)addsubsector | NF_SUBSECTOR;
                extrasubsectors[addsubsector].planepoly = poly;
                addsubsector++;
            }
            
            //add subsectors without segs here?
            //HWR_SubsecPoly (0, NULL);
        }
        else
            HWR_SubsecPoly (bspnum&(~NF_SUBSECTOR), poly);
#ifdef BP_FIX_BBOX