doom

a minimalistic implementation of doom
git clone git://ssnf.xyz/doom
Log | Files | Refs

r_bsp.c (7515B)


      1 #include "doomdef.h"
      2 
      3 #include "m_bbox.h"
      4 
      5 #include "i_system.h"
      6 
      7 #include "r_main.h"
      8 #include "r_plane.h"
      9 #include "r_things.h"
     10 
     11 
     12 #include "doomstat.h"
     13 #include "r_state.h"
     14 
     15 
     16 
     17 
     18 
     19 seg_t*		curline;
     20 side_t*		sidedef;
     21 line_t*		linedef;
     22 sector_t*	frontsector;
     23 sector_t*	backsector;
     24 
     25 drawseg_t	drawsegs[MAXDRAWSEGS];
     26 drawseg_t*	ds_p;
     27 
     28 
     29 void
     30 R_StoreWallRange
     31 ( int	start,
     32   int	stop );
     33 
     34 
     35 
     36 
     37 
     38 
     39 
     40 void R_ClearDrawSegs (void)
     41 {
     42     ds_p = drawsegs;
     43 }
     44 
     45 
     46 
     47 
     48 
     49 
     50 
     51 
     52 typedef	struct
     53 {
     54     int	first;
     55     int last;
     56     
     57 } cliprange_t;
     58 
     59 
     60 #define MAXSEGS		32
     61 
     62 
     63 cliprange_t*	newend;
     64 cliprange_t	solidsegs[MAXSEGS];
     65 
     66 
     67 
     68 
     69 
     70 
     71 
     72 
     73 
     74 
     75 void
     76 R_ClipSolidWallSegment
     77 ( int			first,
     78   int			last )
     79 {
     80     cliprange_t*	next;
     81     cliprange_t*	start;
     82 
     83     
     84     
     85     start = solidsegs;
     86     while (start->last < first-1)
     87 	start++;
     88 
     89     if (first < start->first)
     90     {
     91 	if (last < start->first-1)
     92 	{
     93 	    
     94 	    
     95 	    R_StoreWallRange (first, last);
     96 	    next = newend;
     97 	    newend++;
     98 	    
     99 	    while (next != start)
    100 	    {
    101 		*next = *(next-1);
    102 		next--;
    103 	    }
    104 	    next->first = first;
    105 	    next->last = last;
    106 	    return;
    107 	}
    108 		
    109 	
    110 	R_StoreWallRange (first, start->first - 1);
    111 	
    112 	start->first = first;	
    113     }
    114 
    115     
    116     if (last <= start->last)
    117 	return;			
    118 		
    119     next = start;
    120     while (last >= (next+1)->first-1)
    121     {
    122 	
    123 	R_StoreWallRange (next->last + 1, (next+1)->first - 1);
    124 	next++;
    125 	
    126 	if (last <= next->last)
    127 	{
    128 	    
    129 	    
    130 	    start->last = next->last;	
    131 	    goto crunch;
    132 	}
    133     }
    134 	
    135     
    136     R_StoreWallRange (next->last + 1, last);
    137     
    138     start->last = last;
    139 	
    140     
    141     
    142   crunch:
    143     if (next == start)
    144     {
    145 	
    146 	return;
    147     }
    148     
    149 
    150     while (next++ != newend)
    151     {
    152 	
    153 	*++start = *next;
    154     }
    155 
    156     newend = start+1;
    157 }
    158 
    159 
    160 
    161 
    162 
    163 
    164 
    165 
    166 
    167 
    168 void
    169 R_ClipPassWallSegment
    170 ( int	first,
    171   int	last )
    172 {
    173     cliprange_t*	start;
    174 
    175     
    176     
    177     start = solidsegs;
    178     while (start->last < first-1)
    179 	start++;
    180 
    181     if (first < start->first)
    182     {
    183 	if (last < start->first-1)
    184 	{
    185 	    
    186 	    R_StoreWallRange (first, last);
    187 	    return;
    188 	}
    189 		
    190 	
    191 	R_StoreWallRange (first, start->first - 1);
    192     }
    193 
    194     
    195     if (last <= start->last)
    196 	return;			
    197 		
    198     while (last >= (start+1)->first-1)
    199     {
    200 	
    201 	R_StoreWallRange (start->last + 1, (start+1)->first - 1);
    202 	start++;
    203 	
    204 	if (last <= start->last)
    205 	    return;
    206     }
    207 	
    208     
    209     R_StoreWallRange (start->last + 1, last);
    210 }
    211 
    212 
    213 
    214 
    215 
    216 
    217 void R_ClearClipSegs (void)
    218 {
    219     solidsegs[0].first = -0x7fffffff;
    220     solidsegs[0].last = -1;
    221     solidsegs[1].first = viewwidth;
    222     solidsegs[1].last = 0x7fffffff;
    223     newend = solidsegs+2;
    224 }
    225 
    226 
    227 
    228 
    229 
    230 
    231 void R_AddLine (seg_t*	line)
    232 {
    233     int			x1;
    234     int			x2;
    235     angle_t		angle1;
    236     angle_t		angle2;
    237     angle_t		span;
    238     angle_t		tspan;
    239     
    240     curline = line;
    241 
    242     
    243     angle1 = R_PointToAngle (line->v1->x, line->v1->y);
    244     angle2 = R_PointToAngle (line->v2->x, line->v2->y);
    245     
    246     
    247     
    248     span = angle1 - angle2;
    249     
    250     
    251     if (span >= ANG180)
    252 	return;		
    253 
    254     
    255     rw_angle1 = angle1;
    256     angle1 -= viewangle;
    257     angle2 -= viewangle;
    258 	
    259     tspan = angle1 + clipangle;
    260     if (tspan > 2*clipangle)
    261     {
    262 	tspan -= 2*clipangle;
    263 
    264 	
    265 	if (tspan >= span)
    266 	    return;
    267 	
    268 	angle1 = clipangle;
    269     }
    270     tspan = clipangle - angle2;
    271     if (tspan > 2*clipangle)
    272     {
    273 	tspan -= 2*clipangle;
    274 
    275 	
    276 	if (tspan >= span)
    277 	    return;	
    278 	angle2 = -clipangle;
    279     }
    280     
    281     
    282     
    283     angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
    284     angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
    285     x1 = viewangletox[angle1];
    286     x2 = viewangletox[angle2];
    287 
    288     
    289     if (x1 == x2)
    290 	return;				
    291 	
    292     backsector = line->backsector;
    293 
    294     
    295     if (!backsector)
    296 	goto clipsolid;		
    297 
    298     
    299     if (backsector->ceilingheight <= frontsector->floorheight
    300 	|| backsector->floorheight >= frontsector->ceilingheight)
    301 	goto clipsolid;		
    302 
    303     
    304     if (backsector->ceilingheight != frontsector->ceilingheight
    305 	|| backsector->floorheight != frontsector->floorheight)
    306 	goto clippass;	
    307 		
    308     
    309     
    310     
    311     
    312     
    313     if (backsector->ceilingpic == frontsector->ceilingpic
    314 	&& backsector->floorpic == frontsector->floorpic
    315 	&& backsector->lightlevel == frontsector->lightlevel
    316 	&& curline->sidedef->midtexture == 0)
    317     {
    318 	return;
    319     }
    320     
    321 				
    322   clippass:
    323     R_ClipPassWallSegment (x1, x2-1);	
    324     return;
    325 		
    326   clipsolid:
    327     R_ClipSolidWallSegment (x1, x2-1);
    328 }
    329 
    330 
    331 
    332 
    333 
    334 
    335 
    336 
    337 int	checkcoord[12][4] =
    338 {
    339     {3,0,2,1},
    340     {3,0,2,0},
    341     {3,1,2,0},
    342     {0},
    343     {2,0,2,1},
    344     {0,0,0,0},
    345     {3,1,3,0},
    346     {0},
    347     {2,0,3,1},
    348     {2,1,3,1},
    349     {2,1,3,0}
    350 };
    351 
    352 
    353 boolean R_CheckBBox (fixed_t*	bspcoord)
    354 {
    355     int			boxx;
    356     int			boxy;
    357     int			boxpos;
    358 
    359     fixed_t		x1;
    360     fixed_t		y1;
    361     fixed_t		x2;
    362     fixed_t		y2;
    363     
    364     angle_t		angle1;
    365     angle_t		angle2;
    366     angle_t		span;
    367     angle_t		tspan;
    368     
    369     cliprange_t*	start;
    370 
    371     int			sx1;
    372     int			sx2;
    373     
    374     
    375     
    376     if (viewx <= bspcoord[BOXLEFT])
    377 	boxx = 0;
    378     else if (viewx < bspcoord[BOXRIGHT])
    379 	boxx = 1;
    380     else
    381 	boxx = 2;
    382 		
    383     if (viewy >= bspcoord[BOXTOP])
    384 	boxy = 0;
    385     else if (viewy > bspcoord[BOXBOTTOM])
    386 	boxy = 1;
    387     else
    388 	boxy = 2;
    389 		
    390     boxpos = (boxy<<2)+boxx;
    391     if (boxpos == 5)
    392 	return true;
    393 	
    394     x1 = bspcoord[checkcoord[boxpos][0]];
    395     y1 = bspcoord[checkcoord[boxpos][1]];
    396     x2 = bspcoord[checkcoord[boxpos][2]];
    397     y2 = bspcoord[checkcoord[boxpos][3]];
    398     
    399     
    400     angle1 = R_PointToAngle (x1, y1) - viewangle;
    401     angle2 = R_PointToAngle (x2, y2) - viewangle;
    402 	
    403     span = angle1 - angle2;
    404 
    405     
    406     if (span >= ANG180)
    407 	return true;
    408     
    409     tspan = angle1 + clipangle;
    410 
    411     if (tspan > 2*clipangle)
    412     {
    413 	tspan -= 2*clipangle;
    414 
    415 	
    416 	if (tspan >= span)
    417 	    return false;	
    418 
    419 	angle1 = clipangle;
    420     }
    421     tspan = clipangle - angle2;
    422     if (tspan > 2*clipangle)
    423     {
    424 	tspan -= 2*clipangle;
    425 
    426 	
    427 	if (tspan >= span)
    428 	    return false;
    429 	
    430 	angle2 = -clipangle;
    431     }
    432 
    433 
    434     
    435     
    436     
    437     angle1 = (angle1+ANG90)>>ANGLETOFINESHIFT;
    438     angle2 = (angle2+ANG90)>>ANGLETOFINESHIFT;
    439     sx1 = viewangletox[angle1];
    440     sx2 = viewangletox[angle2];
    441 
    442     
    443     if (sx1 == sx2)
    444 	return false;			
    445     sx2--;
    446 	
    447     start = solidsegs;
    448     while (start->last < sx2)
    449 	start++;
    450     
    451     if (sx1 >= start->first
    452 	&& sx2 <= start->last)
    453     {
    454 	
    455 	return false;
    456     }
    457 
    458     return true;
    459 }
    460 
    461 
    462 
    463 
    464 
    465 
    466 
    467 
    468 
    469 void R_Subsector (int num)
    470 {
    471     int			count;
    472     seg_t*		line;
    473     subsector_t*	sub;
    474 	
    475 #ifdef RANGECHECK
    476     if (num>=numsubsectors)
    477 	I_Error ("R_Subsector: ss %i with numss = %i",
    478 		 num,
    479 		 numsubsectors);
    480 #endif
    481 
    482     sscount++;
    483     sub = &subsectors[num];
    484     frontsector = sub->sector;
    485     count = sub->numlines;
    486     line = &segs[sub->firstline];
    487 
    488     if (frontsector->floorheight < viewz)
    489     {
    490 	floorplane = R_FindPlane (frontsector->floorheight,
    491 				  frontsector->floorpic,
    492 				  frontsector->lightlevel);
    493     }
    494     else
    495 	floorplane = NULL;
    496     
    497     if (frontsector->ceilingheight > viewz 
    498 	|| frontsector->ceilingpic == skyflatnum)
    499     {
    500 	ceilingplane = R_FindPlane (frontsector->ceilingheight,
    501 				    frontsector->ceilingpic,
    502 				    frontsector->lightlevel);
    503     }
    504     else
    505 	ceilingplane = NULL;
    506 		
    507     R_AddSprites (frontsector);	
    508 
    509     while (count--)
    510     {
    511 	R_AddLine (line);
    512 	line++;
    513     }
    514 }
    515 
    516 
    517 
    518 
    519 
    520 
    521 
    522 
    523 
    524 void R_RenderBSPNode (int bspnum)
    525 {
    526     node_t*	bsp;
    527     int		side;
    528 
    529     
    530     if (bspnum & NF_SUBSECTOR)
    531     {
    532 	if (bspnum == -1)			
    533 	    R_Subsector (0);
    534 	else
    535 	    R_Subsector (bspnum&(~NF_SUBSECTOR));
    536 	return;
    537     }
    538 		
    539     bsp = &nodes[bspnum];
    540     
    541     
    542     side = R_PointOnSide (viewx, viewy, bsp);
    543 
    544     
    545     R_RenderBSPNode (bsp->children[side]); 
    546 
    547     
    548     if (R_CheckBBox (bsp->bbox[side^1]))	
    549 	R_RenderBSPNode (bsp->children[side^1]);
    550 }
    551 
    552