Return to r_bsp.c CVS log

Up to [DOOM] / doom

Annotation of doom/r_bsp.c, revision 1.1

1.1     ! root        1: // R_bsp.c
        !             2: 
        !             3: #include "DoomDef.h"
        !             4: #include "R_local.h"
        !             5: 
        !             6: seg_t          *curline;
        !             7: side_t         *sidedef;
        !             8: line_t         *linedef;
        !             9: sector_t       *frontsector, *backsector;
        !            10: 
        !            11: drawseg_t      drawsegs[MAXDRAWSEGS], *ds_p;
        !            12: 
        !            13: void R_StoreWallRange (int start, int stop);
        !            14: 
        !            15: /*
        !            16: ====================
        !            17: =
        !            18: = R_ClearDrawSegs
        !            19: =
        !            20: ====================
        !            21: */
        !            22: 
        !            23: void R_ClearDrawSegs (void)
        !            24: {
        !            25:        ds_p = drawsegs;
        !            26: }
        !            27: 
        !            28: //=============================================================================
        !            29: 
        !            30: 
        !            31: /*
        !            32: ===============================================================================
        !            33: =
        !            34: = ClipWallSegment
        !            35: =
        !            36: = Clips the given range of columns and includes it in the new clip list
        !            37: ===============================================================================
        !            38: */
        !            39: 
        !            40: typedef        struct
        !            41: {
        !            42:        int     first, last;
        !            43: } cliprange_t;
        !            44: 
        !            45: #define        MAXSEGS 32
        !            46: 
        !            47: cliprange_t    solidsegs[MAXSEGS], *newend;    // newend is one past the last valid seg
        !            48: 
        !            49: 
        !            50: void R_ClipSolidWallSegment (int first, int last)
        !            51: {
        !            52:        cliprange_t     *next, *start;
        !            53: 
        !            54: // find the first range that touches the range (adjacent pixels are touching)
        !            55:        start = solidsegs;
        !            56:        while (start->last < first-1)
        !            57:                start++;
        !            58: 
        !            59:        if (first < start->first)
        !            60:        {
        !            61:                if (last < start->first-1)
        !            62:                {       // post is entirely visible (above start), so insert a new clippost
        !            63:                        R_StoreWallRange (first, last);
        !            64:                        next = newend;
        !            65:                        newend++;
        !            66:                        while (next != start)
        !            67:                        {
        !            68:                                *next = *(next-1);
        !            69:                                next--;
        !            70:                        }
        !            71:                        next->first = first;
        !            72:                        next->last = last;
        !            73:                        return;
        !            74:                }
        !            75:                
        !            76:          // there is a fragment above *start
        !            77:                R_StoreWallRange (first, start->first - 1);
        !            78:                start->first = first;           // adjust the clip size
        !            79:        }
        !            80:        
        !            81:        if (last <= start->last)
        !            82:                return;                 // bottom contained in start
        !            83:                
        !            84:        next = start;
        !            85:        while (last >= (next+1)->first-1)
        !            86:        {
        !            87:                // there is a fragment between two posts
        !            88:                R_StoreWallRange (next->last + 1, (next+1)->first - 1);
        !            89:                next++;
        !            90:                if (last <= next->last)
        !            91:                {       // bottom is contained in next
        !            92:                        start->last = next->last;       // adjust the clip size
        !            93:                        goto crunch;
        !            94:                }
        !            95:        }
        !            96:        
        !            97:        // there is a fragment after *next
        !            98:        R_StoreWallRange (next->last + 1, last);
        !            99:        start->last = last;             // adjust the clip size
        !           100:        
        !           101:        
        !           102: // remove start+1 to next from the clip list,
        !           103: // because start now covers their area
        !           104: crunch:
        !           105:        if (next == start)
        !           106:                return;                 // post just extended past the bottom of one post
        !           107: 
        !           108:        while (next++ != newend)        // remove a post
        !           109:                *++start = *next;
        !           110:        newend = start+1;
        !           111: }
        !           112: 
        !           113: /*
        !           114: ===============================================================================
        !           115: =
        !           116: = R_ClipPassWallSegment
        !           117: =
        !           118: = Clips the given range of columns, but does not includes it in the clip list
        !           119: ===============================================================================
        !           120: */
        !           121: 
        !           122: void R_ClipPassWallSegment (int first, int last)
        !           123: {
        !           124:        cliprange_t      *start;
        !           125: 
        !           126: // find the first range that touches the range (adjacent pixels are touching)
        !           127:        start = solidsegs;
        !           128:        while (start->last < first-1)
        !           129:                start++;
        !           130: 
        !           131:        if (first < start->first)
        !           132:        {
        !           133:                if (last < start->first-1)
        !           134:                {       // post is entirely visible (above start)
        !           135:                        R_StoreWallRange (first, last);
        !           136:                        return;
        !           137:                }
        !           138:                
        !           139:          // there is a fragment above *start
        !           140:                R_StoreWallRange (first, start->first - 1);
        !           141:        }
        !           142:        
        !           143:        if (last <= start->last)
        !           144:                return;                 // bottom contained in start
        !           145:                
        !           146:        while (last >= (start+1)->first-1)
        !           147:        {
        !           148:                // there is a fragment between two posts
        !           149:                R_StoreWallRange (start->last + 1, (start+1)->first - 1);
        !           150:                start++;
        !           151:                if (last <= start->last)
        !           152:                        return;
        !           153:        }
        !           154:        
        !           155:        // there is a fragment after *next
        !           156:        R_StoreWallRange (start->last + 1, last);
        !           157: }
        !           158: 
        !           159: 
        !           160: 
        !           161: /*
        !           162: ====================
        !           163: =
        !           164: = R_ClearClipSegs
        !           165: =
        !           166: ====================
        !           167: */
        !           168: 
        !           169: void R_ClearClipSegs (void)
        !           170: {
        !           171:        solidsegs[0].first = -0x7fffffff;
        !           172:        solidsegs[0].last = -1;
        !           173:        solidsegs[1].first = viewwidth;
        !           174:        solidsegs[1].last = 0x7fffffff;
        !           175:        newend = solidsegs+2;
        !           176: }
        !           177: 
        !           178: 
        !           179: //=============================================================================
        !           180: 
        !           181: /*
        !           182: ======================
        !           183: =
        !           184: = R_AddLine
        !           185: =
        !           186: = Clips the given segment and adds any visible pieces to the line list
        !           187: =
        !           188: ======================
        !           189: */
        !           190: 
        !           191: void R_AddLine (seg_t *line)
        !           192: {
        !           193:        int                     x1, x2;
        !           194:        angle_t         angle1, angle2, span, tspan;
        !           195:        
        !           196: #ifdef __NeXT__
        !           197:        RD_DrawLineCheck (line);
        !           198: #endif         
        !           199:        curline = line;
        !           200: 
        !           201: // OPTIMIZE: quickly reject orthogonal back sides
        !           202: 
        !           203:        angle1 = R_PointToAngle (line->v1->x, line->v1->y);
        !           204:        angle2 = R_PointToAngle (line->v2->x, line->v2->y);
        !           205: 
        !           206: //
        !           207: // clip to view edges
        !           208: // OPTIMIZE: make constant out of 2*clipangle (FIELDOFVIEW)
        !           209:        span = angle1 - angle2;
        !           210:        if (span >= ANG180)
        !           211:                return;         // back side
        !           212: 
        !           213:        rw_angle1 = angle1;             // global angle needed by segcalc
        !           214:        angle1 -= viewangle;
        !           215:        angle2 -= viewangle;
        !           216:        
        !           217:        tspan = angle1 + clipangle;
        !           218:        if (tspan > 2*clipangle)
        !           219:        {
        !           220:                tspan -= 2*clipangle;
        !           221:                if (tspan >= span)
        !           222:                        return; // totally off the left edge
        !           223:                angle1 = clipangle;
        !           224:        }
        !           225:        tspan = clipangle - angle2;
        !           226:        if (tspan > 2*clipangle)
        !           227:        {
        !           228:                tspan -= 2*clipangle;
        !           229:                if (tspan >= span)
        !           230:                        return; // totally off the left edge
        !           231:                angle2 = -clipangle;
        !           232:        }
        !           233: 
        !           234: //
        !           235: // the seg is in the view range, but not necessarily visible
        !           236: //
        !           237:        angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
        !           238:        angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
        !           239:        x1 = viewangletox[angle1];
        !           240:        x2 = viewangletox[angle2];
        !           241:        if (x1 == x2)
        !           242:                return;                         // does not cross a pixel
        !           243:        
        !           244:        backsector = line->backsector;
        !           245: 
        !           246:        if (!backsector)
        !           247:                goto clipsolid;         // single sided line
        !           248:                
        !           249:        if (backsector->ceilingheight <= frontsector->floorheight
        !           250:        || backsector->floorheight >= frontsector->ceilingheight)
        !           251:                goto clipsolid;         // closed door
        !           252:                
        !           253:        if (backsector->ceilingheight != frontsector->ceilingheight
        !           254:        || backsector->floorheight != frontsector->floorheight)
        !           255:                goto clippass;          // window
        !           256:                
        !           257: // reject empty lines used for triggers and special events
        !           258:        if (backsector->ceilingpic == frontsector->ceilingpic
        !           259:        && backsector->floorpic == frontsector->floorpic
        !           260:        && backsector->lightlevel == frontsector->lightlevel
        !           261:        && curline->sidedef->midtexture == 0)
        !           262:                return; 
        !           263:                                
        !           264: clippass:
        !           265:        R_ClipPassWallSegment (x1, x2-1);       
        !           266:        return;
        !           267:                
        !           268: clipsolid:
        !           269:        R_ClipSolidWallSegment (x1, x2-1);
        !           270: }
        !           271: 
        !           272: //============================================================================
        !           273: 
        !           274: 
        !           275: /*
        !           276: ===============================================================================
        !           277: =
        !           278: = R_CheckBBox
        !           279: =
        !           280: = Returns true if some part of the bbox might be visible
        !           281: =
        !           282: ===============================================================================
        !           283: */
        !           284: 
        !           285: int    checkcoord[12][4] = {
        !           286: {3,0, 2,1},
        !           287: {3,0, 2,0},
        !           288: {3,1, 2,0},
        !           289: {0},
        !           290: {2,0, 2,1},
        !           291: {0,0,0,0},
        !           292: {3,1, 3,0},
        !           293: {0},
        !           294: {2,0, 3,1},
        !           295: {2,1, 3,1},
        !           296: {2,1, 3,0} };
        !           297: 
        !           298: 
        !           299: boolean R_CheckBBox (fixed_t *bspcoord)
        !           300: {
        !           301:        int                     boxx, boxy, boxpos;
        !           302:        fixed_t         x1, y1, x2, y2;
        !           303:        angle_t         angle1, angle2, span, tspan;
        !           304:        cliprange_t     *start;
        !           305:        int                     sx1, sx2;
        !           306:        
        !           307: #ifdef __NeXT__
        !           308:        RD_DrawBBox (bspcoord);
        !           309: #endif
        !           310: 
        !           311: // find the corners of the box that define the edges from current viewpoint
        !           312:        if (viewx <= bspcoord[BOXLEFT])
        !           313:                boxx = 0;
        !           314:        else if (viewx < bspcoord[BOXRIGHT])
        !           315:                boxx = 1;
        !           316:        else
        !           317:                boxx = 2;
        !           318:                
        !           319:        if (viewy >= bspcoord[BOXTOP])
        !           320:                boxy = 0;
        !           321:        else if (viewy > bspcoord[BOXBOTTOM])
        !           322:                boxy = 1;
        !           323:        else
        !           324:                boxy = 2;
        !           325:                
        !           326:        boxpos = (boxy<<2)+boxx;
        !           327:        if (boxpos == 5)
        !           328:                return true;
        !           329:        
        !           330:        x1 = bspcoord[checkcoord[boxpos][0]];
        !           331:        y1 = bspcoord[checkcoord[boxpos][1]];
        !           332:        x2 = bspcoord[checkcoord[boxpos][2]];
        !           333:        y2 = bspcoord[checkcoord[boxpos][3]];
        !           334: 
        !           335: 
        !           336: #ifdef __NeXT__
        !           337: //     RD_DisplayLine (x1, y1, x2, y2, 0.1);
        !           338: #endif
        !           339:        
        !           340: //
        !           341: // check clip list for an open space
        !           342: //     
        !           343:        angle1 = R_PointToAngle (x1, y1) - viewangle;
        !           344:        angle2 = R_PointToAngle (x2, y2) - viewangle;
        !           345:        
        !           346:        span = angle1 - angle2;
        !           347:        if (span >= ANG180)
        !           348:                return true;    // sitting on a line
        !           349:        tspan = angle1 + clipangle;
        !           350:        if (tspan > 2*clipangle)
        !           351:        {
        !           352:                tspan -= 2*clipangle;
        !           353:                if (tspan >= span)
        !           354:                        return false;   // totally off the left edge
        !           355:                angle1 = clipangle;
        !           356:        }
        !           357:        tspan = clipangle - angle2;
        !           358:        if (tspan > 2*clipangle)
        !           359:        {
        !           360:                tspan -= 2*clipangle;
        !           361:                if (tspan >= span)
        !           362:                        return false;   // totally off the left edge
        !           363:                angle2 = -clipangle;
        !           364:        }
        !           365: 
        !           366: 
        !           367: // find the first clippost that touches the source post (adjacent pixels are touching)
        !           368:        angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
        !           369:        angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
        !           370:        sx1 = viewangletox[angle1];
        !           371:        sx2 = viewangletox[angle2];
        !           372:        if (sx1 == sx2)
        !           373:                return false;                           // does not cross a pixel
        !           374:        sx2--;
        !           375:        
        !           376:        start = solidsegs;
        !           377:        while (start->last < sx2)
        !           378:                start++;
        !           379:        if (sx1 >= start->first && sx2 <= start->last)
        !           380:                return false;   // the clippost contains the new span
        !           381: 
        !           382:        return true;
        !           383: }
        !           384: 
        !           385: 
        !           386: /*
        !           387: ================
        !           388: =
        !           389: = R_Subsector
        !           390: =
        !           391: = Draw one or more segments
        !           392: ================
        !           393: */
        !           394: 
        !           395: void R_Subsector (int num)
        !           396: {
        !           397:        int                     count;
        !           398:        seg_t           *line;
        !           399:        subsector_t     *sub;
        !           400:        
        !           401: #ifdef RANGECHECK
        !           402:        if (num>=numsubsectors)
        !           403:                I_Error ("R_Subsector: ss %i with numss = %i",num, numsubsectors);
        !           404: #endif
        !           405: 
        !           406:        sscount++;
        !           407:        sub = &subsectors[num];
        !           408:        frontsector = sub->sector;
        !           409:        count = sub->numlines;
        !           410:        line = &segs[sub->firstline];
        !           411: 
        !           412:        if (frontsector->floorheight < viewz)
        !           413:                floorplane = R_FindPlane (frontsector->floorheight,
        !           414:                frontsector->floorpic, frontsector->lightlevel,
        !           415:                frontsector->special);
        !           416:        else
        !           417:                floorplane = NULL;
        !           418:        if (frontsector->ceilingheight > viewz 
        !           419:        || frontsector->ceilingpic == skyflatnum)
        !           420:                ceilingplane = R_FindPlane (frontsector->ceilingheight,
        !           421:                frontsector->ceilingpic, frontsector->lightlevel, 0);
        !           422:        else
        !           423:                ceilingplane = NULL;
        !           424:                
        !           425:        R_AddSprites (frontsector);     
        !           426: 
        !           427:        while (count--)
        !           428:        {
        !           429:                R_AddLine (line);
        !           430:                line++;
        !           431:        }
        !           432: }
        !           433: 
        !           434: 
        !           435: /*
        !           436: ===============================================================================
        !           437: =
        !           438: = RenderBSPNode
        !           439: =
        !           440: ===============================================================================
        !           441: */
        !           442: 
        !           443: void R_RenderBSPNode (int bspnum)
        !           444: {
        !           445:        node_t          *bsp;
        !           446:        int                     side;
        !           447: 
        !           448:        if (bspnum & NF_SUBSECTOR)
        !           449:        {
        !           450:                if (bspnum == -1)                       
        !           451:                        R_Subsector (0);
        !           452:                else
        !           453:                        R_Subsector (bspnum&(~NF_SUBSECTOR));
        !           454:                return;
        !           455:        }
        !           456:                
        !           457:        bsp = &nodes[bspnum];
        !           458:        
        !           459: #ifdef __NeXT__
        !           460:        RD_DrawNodeLine (bsp);
        !           461: #endif
        !           462:        
        !           463: //
        !           464: // decide which side the view point is on
        !           465: //
        !           466:        side = R_PointOnSide (viewx, viewy, bsp);
        !           467: 
        !           468:        R_RenderBSPNode (bsp->children[side]); // recursively divide front space
        !           469:        
        !           470:        if (R_CheckBBox (bsp->bbox[side^1]))    // possibly divide back space
        !           471:                R_RenderBSPNode (bsp->children[side^1]);
        !           472: }
        !           473: 
        !           474: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.