开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 游戏 > 查看源码
BUILDBSP.C
资源名称：Visual_C++GameDevelop.rar　[点击查看]
上传用户：sycq158
上传日期：2008-10-22
资源大小：15361k
文件大小：20k
源码类别：

游戏

开发平台：

Visual C++

BUILDBSP.C：源码内容
  1. #include "idbsp.h"
  2. #include "ray.h"
  3. #include "globals.h"
  4. #include <mem.h>
  6. #define _STEVE_FIX_
  7. #define MAX(a,b) ( (a) > (b) ? (a) : (b) )
  8. #define MIN(a,b) ( (a) < (b) ? (a) : (b) )
  10. void * MyRealloc(void * ptr, long old_size, long new_size);
  12. /*
  13.  I assume that a grid 8 is used for the maps, so a point will be considered
  14.  on a line if it is within 8 pixels of it.  The accounts for floating error.
  15. */
  17. int             cuts;                   /* number of new lines generated by BSP process */
  19. /*
  20. ==================
  21. =
  22. = DivlineFromWorldline
  23. =
  24. ==================
  25. */
  27. void    DivlineFromWorldline (divline_t *d, line_t *w)
  28. {
  29. d->pt = w->p1;
  30. d->dx = w->p2.x - w->p1.x;
  31. d->dy = w->p2.y - w->p1.y;
  32. }
  34. /*
  35. ==================
  36. =
  37. = LineFromPoints
  38. =
  39. ==================
  40. */
  42. void    LineFromPoints(line_t * line, pvector2 source, pvector2 dest)
  43. {
  44. memset(line, 0, sizeof(line_t));
  45. line->p1.x=source->x;          
  46. line->p1.y=source->y;
  47. line->p2.x=dest->x;
  48. line->p2.y=dest->y;
  49. }
  51. #define FLOAT_ERROR 4.4722
  53. /*
  54. ==================
  55. =
  56. = PointOnSide
  57. =
  58. = Returns side 0 (front), 1 (back), or -1 (colinear)
  59. ==================
  60. */
  62. #ifdef _STEVE_FIX_
  63. int     PointOnSide (NXPoint *p, divline_t *l)
  64. {
  65.   float dist;
  67.   if (!l->dx)
  68.   {
  69.  if (p->x > l->pt.x-2 && p->x < l->pt.x+2)
  70. return -1;
  71.  if (p->x < l->pt.x)
  72. return l->dy > 0;
  73.  return l->dy < 0;
  74.   }
  75.   if (!l->dy)
  76.   {
  77.  if (p->y > l->pt.y-2 && p->y < l->pt.y+2)
  78. return -1;
  79.  if (p->y < l->pt.y)
  80. return l->dx < 0;
  81.  return l->dx > 0;
  82.   }
  85.   dist = l->dx * (p->y - l->pt.y) - l->dy * (p->x - l->pt.x);
  87. if (dist < FLOAT_ERROR && dist > -FLOAT_ERROR)
  88.  return(-1);
  89.  else if (dist < -FLOAT_ERROR)
  90.  return(0);
  91. else
  92.  return(1);
  93. }
  94. #else
  95. int     PointOnSide (NXPoint *p, divline_t *l)
  96. {
  97. float   dx,dy;
  98. float   left, right;
  99. float   a,b,c,d;
  102. if (!l->dx)
  103. {
  104. if (p->x > l->pt.x-2 && p->x < l->pt.x+2)
  105. return -1;
  106. if (p->x < l->pt.x)
  107. return l->dy > 0;
  108. return l->dy < 0;
  109. }
  110. if (!l->dy)
  111. {
  112. if (p->y > l->pt.y-2 && p->y < l->pt.y+2)
  113. return -1;
  114. if (p->y < l->pt.y)
  115. return l->dx < 0;
  116. return l->dx > 0;
  117. }
  119. dx = l->pt.x - p->x;
  120. dy = l->pt.y - p->y;
  121. a = l->dx*l->dx + l->dy*l->dy;
  122. b = 2*(l->dx*dx + l->dy*dy);
  123. c = dx*dx+dy*dy - 2*2;          /* 2 unit radius */
  124. d = b*b - 4*a*c;
  125. if (d>0)
  126. return -1;               /* within four pixels of line */
  129. dx = p->x - l->pt.x;
  130. dy = p->y - l->pt.y;
  132. left = l->dy * dx;
  133. right = dy * l->dx;
  135. if ( fabs (left-right) < 0.5 )  /* allow slop */
  136. return -1;              /* on line */
  137. if (right < left)
  138. return 0;               /* front side */
  139. return 1;                       /* back side */
  140. }
  141. #endif
  143. /*
  144. =============
  145. =
  146. = sign
  147. =
  148. = Returns -1, 0, or 1, based on the input sign
  149. =
  150. ==============
  151. */
  153. int sign (float i)
  154. {
  155. if (i<0)
  156. return -1;
  157. else if (i>0)
  158. return 1;
  159. return 0;
  160. }
  162. /*
  163. ==================
  164. =
  165. = LineOnSide
  166. =
  167. = Returns side 0 / 1, or -2 if line must be split
  168. = If the line is colinear, it will be placed on the front side if
  169. = it is going the same direction as the dividing line
  170. ==================
  171. */
  173. #ifdef _STEVE_FIX_
  174. int LineOnSide (line_t *wl, divline_t *bl)
  175. #else
  176. boolean LineOnSide (line_t *wl, divline_t *bl)
  177. #endif
  179. {
  180. int             s1,s2;
  181. float   dx, dy;
  183. s1 = PointOnSide (&wl->p1, bl);
  184. s2 = PointOnSide (&wl->p2, bl);
  186. if (s1 == s2)
  187. {
  188. if (s1 == -1)
  189. {       /* colinear, so see if the directions are the same */
  190. dx = wl->p2.x - wl->p1.x;
  191. dy = wl->p2.y - wl->p1.y;
  192. if (sign(dx) == sign (bl->dx) && sign(dy) == sign(bl->dy) )
  193. return 0;
  194. return 1;
  195. }
  196. return s1;
  197. }
  198. if (s1 == -1)
  199. return s2;
  200. if (s2 == -1)
  201. return s1;
  203. return -2;
  204. }
  206. /*
  207. ===============
  208. =
  209. = InterceptVector
  210. =
  211. = Returns the fractional intercept point along first vector
  212. ===============
  213. */
  215. float InterceptVector (divline_t *v2, divline_t *v1)
  216. {
  217. #if 0
  219. v1.x + f1*v1.xs = v2.x + f2*v2.xs       (parametric x coordinates)
  220. f1*v1.xs = v2.x - v1.x + f2*v2.xs
  221. f1 = (v2.x - v1.x +f2*v2.xs) / v1.xs
  223. v1.y + f1*v1.ys = v2.y + f2*v2.ys       (parametric y coordinates)
  224. f1 = (v2.y - v1.y + f2*v2.ys) / v1.ys
  226. f1 = (v2.x - v1.x +f2*v2.xs) / v1.xs = (v2.y - v1.y + f2*v2.ys) / v1.ys
  227. v1.ys*v2.x - v1.ys*v1.x + v1.ys*v2.xs*f2 = v1.xs*v2.y - v1.xs*v1.y + v1.xs*v2.ys*f2
  228. (v1.ys*v2.xs - v1.xs*v2.ys)*f2 = -v1.ys*v2.x + v1.ys*v1.x + v1.xs*v2.y - v1.xs*v1.y
  229. = v1.ys*(v1.x-v2.x) + v1.xs*(v2.y-v1.y)
  231. f2 = (v1.ys*(v1.x-v2.x) + v1.xs*(v2.y-v1.y)) / (v1.ys*v2.xs - v1.xs*v2.ys)
  232. #endif
  235. float   frac, num, den;
  238. den = v1->dy*v2->dx - v1->dx*v2->dy;
  239. if (den == 0)
  240. Error ("InterceptVector: parallel");
  241. num = (v1->pt.x - v2->pt.x)*v1->dy + (v2->pt.y - v1->pt.y)*v1->dx;
  242. frac = num / den;
  244. if (frac <= 0.0 || frac >= 1.0)
  245. Error ("InterceptVector: intersection outside line");
  247. return frac;
  248. }
  251. /*
  252. ==================
  253. =
  254. = CutLine
  255. =
  256. = Truncates the given worldline to the front side of the divline
  257. = and returns the cut off back side in a newly allocated worldline
  258. ==================
  259. */
  261. float round (float x)
  262. {
  263. if (x>0)
  264. {
  265. if (x - (int)x < 0.1)
  266. return (int)x;
  267. else if (x - (int)x > 0.9)
  268. return (int)x+1;
  269. else
  270. return x;
  271. }
  273. if ((int)x - x < 0.1)
  274. return (int)x;
  275. else if ((int)x - x > 0.9)
  276. return  (int)x - 1;
  277. return x;
  278. }
  280. line_t  *CutLine (line_t *wl, divline_t *bl)
  281. {
  282. int                     side;
  283. line_t          *new_p;
  284. divline_t       wld;
  285. float           frac;
  286. NXPoint         intr;
  287. int                     offset;
  289. cuts++;
  290. DivlineFromWorldline (&wld, wl);
  291. new_p = (line_t *)Alloc_Mem (sizeof(line_t));
  292. memset (new_p,0,sizeof(*new_p));
  293. *new_p = *wl;
  295. frac = InterceptVector (&wld, bl);
  297. #ifdef _STEVE_FIX_
  298. intr.x = wld.pt.x + (wld.dx*frac);
  299. intr.y = wld.pt.y + (wld.dy*frac);
  300. offset = wl->offset + (frac*sqrt(wld.dx*wld.dx+wld.dy*wld.dy));
  301. #else
  302. intr.x = wld.pt.x + round(wld.dx*frac);
  303. intr.y = wld.pt.y + round(wld.dy*frac);
  304. offset = wl->offset + round(frac*sqrt(wld.dx*wld.dx+wld.dy*wld.dy));
  305. #endif        
  306. side = PointOnSide (&wl->p1, bl);
  307. if (side == 0)
  308. {       /* line starts on front side */
  309. wl->p2 = intr;
  310. new_p->p1 = intr;
  311. new_p->offset = offset;
  312. }
  313. else
  314. {       /* line starts on back side */
  315. wl->p1 = intr;
  316. wl->offset = offset;
  317. new_p->p2 = intr;
  318. }
  320. return new_p;
  321. }
  323. /*
  324. ================
  325. =
  326. = EvaluateSplit
  327. =
  328. = Returns a number grading the quality of a split along the givent line
  329. = for the current list of lines.  Evaluation is halted as soon as it is
  330. = determined that a better split already exists
  331. =
  332. = A split is good if it divides the lines evenly without cutting many lines
  333. = A horizontal or vertical split is better than a sloping split
  334. =
  335. = The LOWER the returned value, the better.  If the split line does not divide
  336. = any of the lines at all, MAXINT will be returned
  337. ================
  338. */
  340. /*int EvaluateSplit (id lines_i, line_t *spliton, int bestgrade)
  341. */
  342. int EvaluateSplit(STORAGE *lines_i, line_t *spliton, int bestgrade)
  343. {
  344. int                             i,c,side;
  345. line_t                  *line_p;
  346. divline_t               divline;
  347. int                             frontcount, backcount, max, new;
  348. int                             grade;
  349. worldline_t             *wl;
  351. /*      wl = [linestore_i elementAt: spliton->linedef];
  352. */
  353. wl = (worldline_t *)linestore_i->data + spliton->linedef;
  355. #if 0
  356. if (wl->special == BSPSLIDEENDSPECIAL)
  357. return MAXINT;  /* NEVER split on this, because it moves */
  358. #endif
  359. DivlineFromWorldline (&divline, spliton);
  361. frontcount = backcount = 0;
  362. /*      c = [lines_i count];
  363. */
  364. c = lines_i->count;
  365. grade = 0;
  367. for (i=0 ; i<c ; i++)
  368. {
  369. /*              line_p = [lines_i elementAt:i];
  370. */
  371. line_p = (line_t *)lines_i->data + i;
  372. if (line_p == spliton)
  373. side = 0;
  374. else
  375. side = LineOnSide (line_p, &divline);
  376. switch (side)
  377. {
  378. case 0:
  379. frontcount++;
  380. break;
  381. case 1:
  382. backcount++;
  383. break;
  384. case -2:
  385. /*                      wl = [linestore_i elementAt: line_p->linedef];
  386. */
  387. wl = (worldline_t *)linestore_i->data + line_p->linedef;
  389. #if 0
  390. if (wl->special == BSPSLIDESIDESPECIAL)
  391. return MAXINT;  /* NEVER split this line, because it slides */
  392. #endif
  393. frontcount++;
  394. backcount++;
  395. break;
  396. }
  398. max = MAX(frontcount,backcount);
  399. new = (frontcount+backcount) - c;
  400. grade = max+new*8;
  401. if (grade > bestgrade)
  402. return grade;           /* might as well stop now */
  403. }
  405. if (frontcount == 0 || backcount == 0)
  406. return INT_MAX;                 /* line does not partition at all */
  408. return grade;
  409. }
  412. /*
  413. ================
  414. =
  415. = ExecuteSplit
  416. =
  417. = Actually splits the line list as EvaluateLines predicted
  418. ================
  419. */
  420. /*
  421. void ExecuteSplit (id lines_i, line_t *spliton
  422. , id frontlist_i, id backlist_i)
  423. */
  424. void ExecuteSplit(STORAGE *lines_i, line_t *spliton,
  425.   STORAGE *frontlist_i, STORAGE *backlist_i)
  426. {
  427. int                             i,c,side;
  428. line_t                  *line_p, *newline_p;
  429. divline_t               divline;
  431. DivlineFromWorldline (&divline, spliton);
  433. /*      c = [lines_i count];
  434. */
  435. c = lines_i->count;
  437. for (i=0 ; i<c ; i++)
  438. {
  439. /*              line_p = [lines_i elementAt:i];
  440. */
  441. line_p = (line_t *)lines_i->data + i;
  442. if (line_p == spliton)
  443. side = 0;
  444. else
  445. side = LineOnSide (line_p, &divline);
  446. switch (side)
  447. {
  448. case 0:
  449. /*                      [frontlist_i addElement: line_p];
  450. */
  451. memcpy((line_t *)frontlist_i->data + frontlist_i->count, line_p, sizeof(line_t));
  452. frontlist_i->count += 1;
  453. frontlist_i->data = (line_t *)MyRealloc(frontlist_i->data,
  454. sizeof(line_t) * (frontlist_i->count), sizeof(line_t) * (frontlist_i->count + 1));
  455. break;
  456. case 1:
  457. /*                      [backlist_i addElement: line_p];
  458. */
  459. memcpy((line_t *)backlist_i->data + backlist_i->count, line_p, sizeof(line_t));
  460. backlist_i->count += 1;
  461. backlist_i->data = (line_t *)MyRealloc(backlist_i->data,
  462. sizeof(line_t) * (backlist_i->count), sizeof(line_t) * (backlist_i->count + 1));
  463. break;
  464. case -2:
  465. newline_p = CutLine (line_p, &divline);
  466. /*                      [frontlist_i addElement: line_p];
  467. [backlist_i addElement: newline_p];
  468. */
  469. memcpy((line_t *)frontlist_i->data + frontlist_i->count, line_p, sizeof(line_t));
  470. frontlist_i->count += 1;
  471. frontlist_i->data = (line_t *)MyRealloc(frontlist_i->data,
  472. sizeof(line_t) * (frontlist_i->count), sizeof(line_t) * (frontlist_i->count + 1));
  474. memcpy((line_t *)backlist_i->data + backlist_i->count, newline_p, sizeof(line_t));
  475. backlist_i->count += 1;
  476. backlist_i->data = (line_t *)MyRealloc(backlist_i->data,
  477. sizeof(line_t) * (backlist_i->count), sizeof(line_t) * (backlist_i->count + 1));
  479. break;
  480. default:
  481. Error ("ExecuteSplit: bad side");
  482. }
  483. }
  484. }
  486. /*
  487. ================
  488. =
  489. = SplitCutBoxes
  490. =
  491. = Cuts a box in half along a line ****MADE BY MATT****
  492. ================
  493. */
  495. void SplitCutBoxes(STORAGE * cutbox_i, line_t * spliton, 
  496. STORAGE * frontlist_i, STORAGE * backlist_i) {
  498. divline_t divline;
  499. short point_count, cur_point, cur_side; 
  500. pvector2 cur_vec, next_vec; 
  501. vector2 new_vec;
  502. line_t cur_line;
  503. line_t * newline_p;
  505. DivlineFromWorldline(&divline, spliton);
  506. point_count=cutbox_i->count;
  507. cur_vec=(pvector2)cutbox_i->data+point_count-1;
  509. for (cur_point=0; cur_point<point_count; cur_point++) {
  510. next_vec=(pvector2)cutbox_i->data+cur_point;   
  512. LineFromPoints(&cur_line, cur_vec, next_vec);
  513. cur_side=LineOnSide(&cur_line, &divline); 
  515. switch (cur_side) {
  516. case 0:
  518. if (PointOnSide(&(cur_line.p2), &divline)==-1) {
  519. memcpy((pvector2)backlist_i->data+backlist_i->count, next_vec, sizeof(vector2));
  520. backlist_i->count++;
  521. backlist_i->data=(pvector2)MyRealloc(backlist_i->data, 
  522. sizeof(vector2) *(backlist_i->count),sizeof(vector2) *(backlist_i->count+1));
  523. }
  525. memcpy((pvector2)frontlist_i->data+frontlist_i->count, next_vec, sizeof(vector2));          
  526. frontlist_i->count++;                                                        
  527. frontlist_i->data=(pvector2)MyRealloc(frontlist_i->data, 
  528. sizeof(vector2) *(frontlist_i->count), sizeof(vector2) *(frontlist_i->count+1));
  529. break;
  531. case 1:
  533. if (PointOnSide(&(cur_line.p2), &divline)==-1) {
  534. memcpy((pvector2)frontlist_i->data+frontlist_i->count, next_vec, sizeof(vector2));
  535. frontlist_i->count++;
  536. frontlist_i->data=(pvector2)MyRealloc(frontlist_i->data, 
  537. sizeof(vector2) *(frontlist_i->count), sizeof(vector2) *(frontlist_i->count+1));
  538. }
  540. memcpy((pvector2)backlist_i->data+backlist_i->count, next_vec, sizeof(vector2));
  541. backlist_i->count++;
  542. backlist_i->data=(pvector2)MyRealloc(backlist_i->data, 
  543. sizeof(vector2) *(backlist_i->count), sizeof(vector2) *(backlist_i->count+1));
  544. break;
  546. case -2:   
  547. newline_p=CutLine(&cur_line, &divline);
  549. if ((newline_p->p2.x==next_vec->x) && (newline_p->p2.y==next_vec->y)) {     
  550. new_vec.x=newline_p->p1.x;
  551. new_vec.y=newline_p->p1.y;
  552. } else {                                                             
  553. new_vec.x=newline_p->p2.x;
  554. new_vec.y=newline_p->p2.y;
  555. }
  557. memcpy((pvector2)frontlist_i->data+frontlist_i->count, &new_vec, sizeof(vector2));
  558. frontlist_i->count++;
  559. frontlist_i->data=(pvector2)MyRealloc(frontlist_i->data, 
  560. sizeof(vector2) *(frontlist_i->count), sizeof(vector2) *(frontlist_i->count+1));
  562. memcpy((pvector2)backlist_i->data+backlist_i->count, &new_vec, sizeof(vector2));
  563. backlist_i->count++;
  564. backlist_i->data=(pvector2)MyRealloc(backlist_i->data, 
  565. sizeof(vector2) *(backlist_i->count), sizeof(vector2) *(backlist_i->count+1));
  566.  
  567. if ((newline_p->p2.x==next_vec->x) && (newline_p->p2.y==next_vec->y)) {
  568.  memcpy((pvector2)backlist_i->data+backlist_i->count, next_vec, sizeof(vector2));
  569.  backlist_i->count++;
  570.  backlist_i->data=(pvector2)MyRealloc(backlist_i->data, 
  571.  sizeof(vector2) *(backlist_i->count), sizeof(vector2) *(backlist_i->count+1));
  572. } else {
  573.  memcpy((pvector2)frontlist_i->data+frontlist_i->count, next_vec, sizeof(vector2));
  574.  frontlist_i->count++;
  575.  frontlist_i->data=(pvector2)MyRealloc(frontlist_i->data, 
  576.  sizeof(vector2) *(frontlist_i->count), sizeof(vector2) *(frontlist_i->count+1));
  577. }
  578. break;
  580. default:
  581.   Error("Bad Cut Box!");
  582.   break;
  583. }
  584. cur_vec=next_vec;
  585. }
  586. }
  588. /*                              
  589. ================
  590. =
  591. = BSPList
  592. =
  593. = Takes a storage of lines and recursively partitions the list
  594. = Returns a bspnode_t
  595. ================
  596. */
  598. /* float        gray = NX_WHITE; */
  599. float gray = 0;                                                            
  601. /* bspnode_t *BSPList (id lines_i)
  602. */
  603. bspnode_t *BSPList(STORAGE *lines_i, STORAGE * cutbox_i)
  604. {
  605. /*      id                              frontlist_i, backlist_i;
  606. */
  607. STORAGE *frontlist_i, *backlist_i;
  608. STORAGE *cutbacklist_i, *cutfrontlist_i;
  609. int                             i,c, step;
  610. line_t                  *line_p, *bestline_p;
  611. int                             v, bestv;
  612. bspnode_t               *node_p;
  613. /*
  614. if (draw)
  615. PSsetgray (gray);
  616. gray = 1.0 - gray;
  617. */
  619. node_p = (bspnode_t *)Alloc_Mem (sizeof(*node_p));
  620. memset (node_p, 0, sizeof(*node_p));
  622. /*
  623.  find the best line to partition on
  624. */
  626. /*      c = [lines_i count];
  627. */
  629. c = lines_i->count;
  630. bestv = INT_MAX;
  631. bestline_p = NULL;
  632. step = (c/40)+1;                /* set this to 1 for an exhaustive search */
  633. research:
  634. for (i=0 ; i<c ; i+=step)
  635. {
  636. /*              line_p = [lines_i elementAt:i];
  637. */
  638. line_p = (line_t *)lines_i->data + i;
  639. v = EvaluateSplit (lines_i, line_p, bestv);
  640. if (v<bestv)
  641. {
  642. bestv = v;
  643. bestline_p = line_p;
  644. }
  645. }
  647. /*
  648.  if none of the lines should be split, the remaining lines
  649.  are convex, and form a terminal node
  650. */
  651. /*
  652. printf ("bestv:%in",bestv);
  653. */
  654. if (bestv == INT_MAX)
  655. {
  656. if (step > 1)
  657. {       /* possible to get here with non convex area if BSPSLIDE specials
  658.  caused rejections */
  659. step = 1;
  660. goto research;
  661. }
  662. node_p->lines_i = lines_i;
  663. node_p->cutbox_i= cutbox_i;
  664. return node_p;
  665. }
  667. /*
  668.  divide the line list into two nodes along the best split line
  669. */
  670. DivlineFromWorldline (&node_p->divline, bestline_p);
  671. /*
  672. frontlist_i =
  673. [[Storage alloc]
  674. initCount:              0
  675. elementSize:    sizeof(line_t)
  676. description:    NULL];
  677. backlist_i =
  678. [[Storage alloc]
  679. initCount:              0
  680. elementSize:    sizeof(line_t)
  681. description:    NULL];
  682. */
  683. frontlist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  684. frontlist_i->count = 0;
  685. frontlist_i->size = sizeof(line_t);
  686. frontlist_i->data = (line_t *)SafeMalloc(sizeof(line_t));
  688. backlist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  689. backlist_i->count = 0;
  690. backlist_i->size = sizeof(line_t);
  691. backlist_i->data = (line_t *)SafeMalloc(sizeof(line_t));
  693. ExecuteSplit (lines_i, bestline_p, frontlist_i, backlist_i);
  695. cutfrontlist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  696. cutfrontlist_i->count = 0;
  697. cutfrontlist_i->size = sizeof(vector2);
  698. cutfrontlist_i->data = (pvector2)SafeMalloc(sizeof(vector2));
  700. cutbacklist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  701. cutbacklist_i->count = 0;
  702. cutbacklist_i->size = sizeof(vector2);
  703. cutbacklist_i->data = (pvector2)SafeMalloc(sizeof(vector2));
  705. SplitCutBoxes(cutbox_i, bestline_p, cutfrontlist_i, cutbacklist_i);
  707. /*
  708.  recursively divide the lists
  709. */
  710. node_p->side[0] = BSPList (frontlist_i, cutfrontlist_i);
  711. node_p->side[1] = BSPList (backlist_i, cutbacklist_i);
  713. return node_p;
  714. }
  718. /*
  719. =====================
  720. =
  721. = MakeSegs
  722. =
  723. =====================
  724. */
  726. STORAGE *initialcutbox_i;
  728. void MakeInitialCutBox() {
  729. pvector2 v1,v2,v3,v4;                                                      
  730. long min_x, min_y, max_x, max_y;
  731. pvector2 cur_vec;
  732. short counter;
  734. // Get min and max points of world be looping through vectors
  736. min_x=max_x=Vector_List[0].x;
  737. min_y=max_y=Vector_List[0].y;
  739. for (counter=1; counter < Number_Of_Vectors; counter++) {
  740. cur_vec=Vector_List+counter;
  741. if (cur_vec->x < min_x)
  742. min_x=cur_vec->x;
  743. if (cur_vec->y < min_y)
  744. min_y=cur_vec->y;
  745. if (cur_vec->x > max_x)
  746. max_x=cur_vec->x;
  747. if (cur_vec->y > max_y)
  748. max_y=cur_vec->y;
  749. }
  751. initialcutbox_i=(STORAGE *)SafeMalloc(sizeof(STORAGE));
  752. initialcutbox_i->count=4;
  753. initialcutbox_i->size=4*sizeof(vector2);
  754. initialcutbox_i->data=(pvector2)SafeMalloc(4 * sizeof(vector2));
  756. v1=(pvector2)initialcutbox_i->data+0;
  757. v2=(pvector2)initialcutbox_i->data+1;
  758. v3=(pvector2)initialcutbox_i->data+2;
  759. v4=(pvector2)initialcutbox_i->data+3;
  761. v1->x=min_x;
  762. v1->y=min_y;
  763. v2->x=min_x;
  764. v2->y=max_y;
  765. v3->x=max_x;
  766. v3->y=max_y;
  767. v4->x=max_x;
  768. v4->y=min_y;
  770. }
  772. /* id segstore_i;
  773. */
  774. STORAGE *segstore_i;
  776. void MakeSegs (void)
  777. {
  778. int                             i, count;
  779. worldline_t             *wl;
  780. /* line_t   li;
  781. */
  782. line_t                  *li;
  784. /*
  785. segstore_i =
  786. [[Storage alloc]
  787. initCount:              0
  788. elementSize:    sizeof(line_t)
  789. description:    NULL];
  790. */
  791. segstore_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
  792. segstore_i->data = (line_t *)SafeMalloc(sizeof(line_t));
  793. segstore_i->count = 0;
  794. segstore_i->size = sizeof(line_t);
  796. /*
  797. count = [linestore_i count];
  798. wl = [linestore_i elementAt:0];
  799. */
  800. count = linestore_i->count;
  801. wl = linestore_i->data;
  803. li = segstore_i->data;
  805. for (i= 0 ; i<count ; i++, wl++)
  806. {
  807. li->p1 = wl->p1;
  808. li->p2 = wl->p2;
  809. li->linedef = i;
  810. li->side = 0;
  811. li->offset = 0;
  812. li->grouped = false;
  814. /*              [segstore_i addElement: &li];
  815. */
  816. segstore_i->count += 1;
  817. segstore_i->data = (line_t *)MyRealloc(segstore_i->data,
  818. sizeof(line_t) * (segstore_i->count), sizeof(line_t) * (segstore_i->count + 1));
  819. li = (line_t *)segstore_i->data + segstore_i->count;
  821. if (wl->flags & ML_TWOSIDED)
  822. {
  823. li->p1 = wl->p2;
  824. li->p2 = wl->p1;
  825. li->linedef = i;
  826. li->side = 1;
  827. li->offset = 0;
  828. li->grouped = false;
  829. /*                      [segstore_i addElement: &li];
  830. */
  831. segstore_i->count += 1;
  832. segstore_i->data = (line_t *)MyRealloc(segstore_i->data,
  833. sizeof(line_t) * (segstore_i->count), sizeof(line_t) * (segstore_i->count + 1));
  834. li = (line_t *)segstore_i->data + segstore_i->count;
  835. }
  836. }
  837. }
  840. /*
  841. =====================
  842. =
  843. = BuildBSP
  844. =
  845. =====================
  846. */
  848. bspnode_t       *startnode;
  850. void BuildBSP (void)
  851. {
  852. MakeSegs ();
  853.   MakeInitialCutBox();
  854. cuts = 0;
  855. startnode = BSPList (segstore_i, initialcutbox_i);
  856. }