hw_bsp.c

The source code of Doom legacy for windows

        M_ClearBox(bbox);
        poly=extrasubsectors[bspnum&~NF_SUBSECTOR].planepoly;
 
        for (i=0, pt=poly->pts; i<poly->numpts; i++,pt++)
             M_AddToBox (bbox, (fixed_t)(pt->x * FRACUNIT), (fixed_t)(pt->y * FRACUNIT));
#endif
        return;
    }

    bsp = &nodes[bspnum];
    SearchDivline(bsp,&fdivline);
    SplitPoly (&fdivline, poly, &frontpoly, &backpoly);
    poly = NULL;

    //debug
    if (!backpoly)
        nobackpoly++;

    // Recursively divide front space.
#ifndef BP_FIX_BBOX
    // REMOVED TEMPORARY : IT SHOULD COMPLETE BBOX ONLY WITH SUBSECTOR 'CUTOUT' POLY
    if (frontpoly) {
        // Correct front bbox so it includes the space occupied by the convex polygon
        // (in software rendere it only needed to cover the space occupied by segs)
        for (i=0, pt=frontpoly->pts; i<frontpoly->numpts; i++,pt++)
            M_AddToBox (bsp->bbox[0], (fixed_t)(pt->x * FRACUNIT), (fixed_t)(pt->y * FRACUNIT));
    }
    else
        I_Error ("WalkBSPNode: no front poly ?");
#endif
    WalkBSPNode (bsp->children[0], frontpoly, &bsp->children[0],bsp->bbox[0]);
#ifdef BP_FIX_BBOX
    // copy child bbox
    memcpy(bbox, bsp->bbox[0], 4*sizeof(fixed_t));
#endif
    // Recursively divide back space.
    if (backpoly) {
        // Correct back bbox to include floor/ceiling convex polygon
#ifndef BP_FIX_BBOX
        for (i=0, pt=backpoly->pts; i<backpoly->numpts; i++,pt++)
            M_AddToBox (bsp->bbox[1], (fixed_t)(pt->x * FRACUNIT), (fixed_t)(pt->y * FRACUNIT));
#endif

        WalkBSPNode (bsp->children[1], backpoly, &bsp->children[1],bsp->bbox[1]);

#ifdef BP_FIX_BBOX        
        // enlarge bbox with seconde child
        M_AddToBox (bbox, bsp->bbox[1][BOXLEFT  ],
                          bsp->bbox[1][BOXTOP   ]);
        M_AddToBox (bbox, bsp->bbox[1][BOXRIGHT ],
                          bsp->bbox[1][BOXBOTTOM]);
#endif
    }
}


//FIXME: use Z_MAlloc() STATIC ?
void HWR_FreeExtraSubsectors (void)
{
    if (extrasubsectors)
        free(extrasubsectors);
}

#define MAXDIST   (1.5f)
// BP: can't move vertex : DON'T change polygone geometry ! (convex)
//#define MOVEVERTEX
boolean PointInSeg(polyvertex_t* a,polyvertex_t* v1,polyvertex_t* v2)
{
    register float ax,ay,bx,by,cx,cy,d,norm;
    register polyvertex_t* p;
    
    // check bbox of the seg first
    if( v1->x>v2->x )
    {
        p=v1;
        v1=v2;
        v2=p;
    }
    if(a->x<v1->x-MAXDIST || a->x>v2->x+MAXDIST)
        return false;

    if( v1->y>v2->y )
    {
        p=v1;
        v1=v2;
        v2=p;
    }
    if(a->y<v1->y-MAXDIST || a->y>v2->y+MAXDIST)
        return false;

    // v1 = origine
    ax= v2->x-v1->x;
    ay= v2->y-v1->y;
    norm = sqrt(ax*ax+ay*ay);
    ax/=norm;
    ay/=norm;
    bx=a->x-v1->x;
    by=a->y-v1->y;
    //d = a.b
    d =ax*bx+ay*by;
    // bound of the seg
    if(d<0 || d>norm)
        return false;
    //c=d.1a-b
    cx=ax*d-bx;
    cy=ay*d-by;
#ifdef MOVEVERTEX
    if(cx*cx+cy*cy<=MAXDIST*MAXDIST)
    {
        // ajust a little the point position
        a->x=ax*d+v1->x;
        a->y=ay*d+v1->y;
        // anyway the correction is not enouth
        return true;
    }
    return false;
#else
    return cx*cx+cy*cy<=MAXDIST*MAXDIST;
#endif
}

int numsplitpoly;

void SearchSegInBSP(int bspnum,polyvertex_t *p,poly_t *poly)
{
    poly_t  *q;
    int     j,k;

    if (bspnum & NF_SUBSECTOR)
    {
        if( bspnum!=-1 )
        {
            bspnum&=~NF_SUBSECTOR;
            q = extrasubsectors[bspnum].planepoly;
            if( poly==q || !q)
                return;
            for(j=0;j<q->numpts;j++)
            {
                k=j+1;
                if( k==q->numpts ) k=0;
                if( !SameVertice(p,&q->pts[j]) && 
                    !SameVertice(p,&q->pts[k]) &&
                    PointInSeg(p,&q->pts[j],&q->pts[k]) )
                {
                    poly_t *newpoly=HWR_AllocPoly(q->numpts+1);
                    int n;

                    for(n=0;n<=j;n++)
                        newpoly->pts[n]=q->pts[n];
                    newpoly->pts[k]=*p;
                    for(n=k+1;n<newpoly->numpts;n++)
                        newpoly->pts[n]=q->pts[n-1];
                    numsplitpoly++;
                    extrasubsectors[bspnum].planepoly = newpoly;
                    HWR_FreePoly(q);
                    return;
                }
            }
        }
        return;
    }

    if((nodes[bspnum].bbox[0][BOXBOTTOM]*crapmul-MAXDIST<=p->y) &&
       (nodes[bspnum].bbox[0][BOXTOP   ]*crapmul+MAXDIST>=p->y) &&
       (nodes[bspnum].bbox[0][BOXLEFT  ]*crapmul-MAXDIST<=p->x) &&
       (nodes[bspnum].bbox[0][BOXRIGHT ]*crapmul+MAXDIST>=p->x) )
        SearchSegInBSP(nodes[bspnum].children[0],p,poly);

    if((nodes[bspnum].bbox[1][BOXBOTTOM]*crapmul-MAXDIST<=p->y) &&
       (nodes[bspnum].bbox[1][BOXTOP   ]*crapmul+MAXDIST>=p->y) &&
       (nodes[bspnum].bbox[1][BOXLEFT  ]*crapmul-MAXDIST<=p->x) &&
       (nodes[bspnum].bbox[1][BOXRIGHT ]*crapmul+MAXDIST>=p->x) )
        SearchSegInBSP(nodes[bspnum].children[1],p,poly);
}

// search for T-intersection problem
// BP : It can be mush more faster doing this at the same time of the splitpoly
// but we must use a different structure : polygone pointing on segs 
// segs pointing on polygone and on vertex (too mush complicated, well not 
// realy but i am soo lasy), the methode discibed is also better for segs presition
extern consvar_t cv_grsolvetjoin;
int SolveTProblem (void)
{
    poly_t  *p;
    int     i,l;

    if (cv_grsolvetjoin.value == 0)
        return 0;

    numsplitpoly=0;

    for(l=0;l<addsubsector;l++ )
    {
        p = extrasubsectors[l].planepoly;
        if( p )
        for(i=0;i<p->numpts;i++)
            SearchSegInBSP(numnodes-1,&p->pts[i],p);
    }
    //CONS_Printf("numsplitpoly %d\n", numsplitpoly);
    return numsplitpoly;
}

#define NEARDIST (0.75f) 
#define MYMAX    (10000000000000.0f)

/*  Ajust true segs (from the segs lump) to be exactely the same as 
 *  plane polygone segs
 *  This also convert fixed_t point of segs in float (in moste case 
 *  it share the same vertice
 */
void AjustSegs(void)
{
    int i,j,count;
    seg_t* lseg;
    poly_t *p;
    int v1found=0,v2found=0;
    float nearv1,nearv2;

    for(i=0;i<numsubsectors;i++)
    {
        count = subsectors[i].numlines;
        lseg = &segs[subsectors[i].firstline];
        p = extrasubsectors[i].planepoly;
        if(!p)
            continue;
        for(;count--;lseg++)        
        {
            float distv1,distv2,tmp;
            nearv1=nearv2=MYMAX;
            for(j=0;j<p->numpts;j++)
            {
                distv1 = p->pts[j].x - ((float)lseg->v1->x)*crapmul; 
                tmp    = p->pts[j].y - ((float)lseg->v1->y)*crapmul;
                distv1 = distv1*distv1+tmp*tmp;
                if( distv1 <= nearv1 )
                {
                    v1found=j;
                    nearv1 = distv1;
                }
                // the same with v2
                distv2 = p->pts[j].x - ((float)lseg->v2->x)*crapmul; 
                tmp    = p->pts[j].y - ((float)lseg->v2->y)*crapmul;
                distv2 = distv2*distv2+tmp*tmp;
                if( distv2 <= nearv2 )
                {
                    v2found=j;
                    nearv2 = distv2;
                }
            }
            if( nearv1<=NEARDIST*NEARDIST )
                // share vertice with segs
                lseg->v1 = (vertex_t *)&(p->pts[v1found]);
            else
            {
                // BP: here we can do better, using PointInSeg and compute
                // the right point position also split a polygone side to
                // solve a T-intersection, but too mush work

                // convert fixed vertex to float vertex
                polyvertex_t *p=HWR_AllocVertex();
                p->x=lseg->v1->x*crapmul;
                p->y=lseg->v1->y*crapmul;
                lseg->v1 = (vertex_t *)p;
            }
            if( nearv2<=NEARDIST*NEARDIST )
                lseg->v2 = (vertex_t *)&(p->pts[v2found]);
            else
            {
                polyvertex_t *p=HWR_AllocVertex();
                p->x=lseg->v2->x*crapmul;
                p->y=lseg->v2->y*crapmul;
                lseg->v2 = (vertex_t *)p;
            }

            // recompute length 
            {
                float x,y;
                x=((polyvertex_t *)lseg->v2)->x-((polyvertex_t *)lseg->v1)->x+0.5*crapmul;
                y=((polyvertex_t *)lseg->v2)->y-((polyvertex_t *)lseg->v1)->y+0.5*crapmul;
                lseg->length = sqrt(x*x+y*y)*FRACUNIT;
                // BP: debug see this kind of segs
                //if (nearv2>NEARDIST*NEARDIST || nearv1>NEARDIST*NEARDIST)
                //    lseg->length=1;
            }
        }
    }
}

// call this routine after the BSP of a Doom wad file is loaded,
// and it will generate all the convex polys for the hardware renderer
void HWR_CreatePlanePolygons (int bspnum)
{
    poly_t*       rootp;
    polyvertex_t* rootpv;

    int     i;

    fixed_t     rootbbox[4];

    //CONS_Printf ("HWR_CreatePlanePolygons()\n");

    HWR_ClearPolys ();
    
    // find min/max boundaries of map
    //CONS_Printf ("Looking for boundaries of map...\n");
    M_ClearBox(rootbbox);
    for (i=0;i<numvertexes;i++)
        M_AddToBox(rootbbox,vertexes[i].x,vertexes[i].y);

    //CONS_Printf ("Generating subsector polygons... %d subsectors\n", numsubsectors);

    HWR_FreeExtraSubsectors ();
    // allocate extra data for each subsector present in map
    totsubsectors = numsubsectors + NEWSUBSECTORS;
    extrasubsectors = (extrasubsector_t*)malloc (sizeof(extrasubsector_t) * totsubsectors);
    if (!extrasubsectors)
        I_Error ("couldn't malloc extrasubsectors totsubsectors %d\n", totsubsectors);
    // set all data in to 0 or NULL !!!
    memset (extrasubsectors,0,sizeof(extrasubsector_t) * totsubsectors);

    // allocate table for back to front drawing of subsectors
    /*gr_drawsubsectors = (short*)malloc (sizeof(*gr_drawsubsectors) * totsubsectors);
    if (!gr_drawsubsectors)
        I_Error ("couldn't malloc gr_drawsubsectors\n");*/

    // number of the first new subsector that might be added
    addsubsector = numsubsectors;

    // construct the initial convex poly that encloses the full map
    rootp  = HWR_AllocPoly (4);
    rootpv = rootp->pts;

    rootpv->x = (float)rootbbox[BOXLEFT  ] * crapmul;
    rootpv->y = (float)rootbbox[BOXBOTTOM] * crapmul;  //lr
    rootpv++;
    rootpv->x = (float)rootbbox[BOXLEFT  ] * crapmul;
    rootpv->y = (float)rootbbox[BOXTOP   ] * crapmul;  //ur
    rootpv++;
    rootpv->x = (float)rootbbox[BOXRIGHT ] * crapmul;
    rootpv->y = (float)rootbbox[BOXTOP   ] * crapmul;  //ul
    rootpv++;
    rootpv->x = (float)rootbbox[BOXRIGHT ] * crapmul;
    rootpv->y = (float)rootbbox[BOXBOTTOM] * crapmul;  //ll
    rootpv++;

    WalkBSPNode (bspnum, rootp, NULL,rootbbox);

    i=SolveTProblem ();
    //CONS_Printf("%d point div a polygone line\n",i);
    AjustSegs();

    //debug debug..
    //if (nobackpoly)
    //    CONS_Printf ("no back polygon %d times\n",nobackpoly);
                             //"(should happen only with the deep water trick)"

    //if (skipcut)
    //    CONS_Printf ("%d cuts were skipped because of only one point\n",skipcut);


    //CONS_Printf ("done : %d total subsector convex polygons\n", totalsubsecpolys);
}