1 //------------------------------------------------------------------------ 2 // SEG : Choose the best Seg to use for a node line. 3 //------------------------------------------------------------------------ 4 // 5 // GL-Friendly Node Builder (C) 2000-2007 Andrew Apted 6 // 7 // Based on 'BSP 2.3' by Colin Reed, Lee Killough and others. 8 // 9 // This program is free software; you can redistribute it and/or 10 // modify it under the terms of the GNU General Public License 11 // as published by the Free Software Foundation; either version 2 12 // of the License, or (at your option) any later version. 13 // 14 // This program is distributed in the hope that it will be useful, 15 // but WITHOUT ANY WARRANTY; without even the implied warranty of 16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 // GNU General Public License for more details. 18 // 19 //------------------------------------------------------------------------ 20 21 #ifndef __GLBSP_SEG_H__ 22 #define __GLBSP_SEG_H__ 23 24 #include "structs.h" 25 26 27 #define DEFAULT_FACTOR 11 28 29 #define IFFY_LEN 4.0 30 31 32 // smallest distance between two points before being considered equal 33 #define DIST_EPSILON (1.0 / 128.0) 34 35 // smallest degrees between two angles before being considered equal 36 #define ANG_EPSILON (1.0 / 1024.0) 37 38 39 // an "intersection" remembers the vertex that touches a BSP divider 40 // line (especially a new vertex that is created at a seg split). 41 42 typedef struct intersection_s 43 { 44 // link in list. The intersection list is kept sorted by 45 // along_dist, in ascending order. 46 struct intersection_s *next; 47 struct intersection_s *prev; 48 49 // vertex in question 50 vertex_t *vertex; 51 52 // how far along the partition line the vertex is. Zero is at the 53 // partition seg's start point, positive values move in the same 54 // direction as the partition's direction, and negative values move 55 // in the opposite direction. 56 float_g along_dist; 57 58 // TRUE if this intersection was on a self-referencing linedef 59 boolean_g self_ref; 60 61 // sector on each side of the vertex (along the partition), 62 // or NULL when that direction isn't OPEN. 63 sector_t *before; 64 sector_t *after; 65 } 66 intersection_t; 67 68 69 /* -------- functions ---------------------------- */ 70 71 // scan all the segs in the list, and choose the best seg to use as a 72 // partition line, returning it. If no seg can be used, returns NULL. 73 // The 'depth' parameter is the current depth in the tree, used for 74 // computing the current progress. 75 // 76 seg_t *PickNode(superblock_t *seg_list, int depth, const bbox_t *bbox); 77 78 // compute the boundary of the list of segs 79 void FindLimits(superblock_t *seg_list, bbox_t *bbox); 80 81 // compute the seg private info (psx/y, pex/y, pdx/y, etc). 82 void RecomputeSeg(seg_t *seg); 83 84 // take the given seg 'cur', compare it with the partition line, and 85 // determine it's fate: moving it into either the left or right lists 86 // (perhaps both, when splitting it in two). Handles partners as 87 // well. Updates the intersection list if the seg lies on or crosses 88 // the partition line. 89 // 90 void DivideOneSeg(seg_t *cur, seg_t *part, 91 superblock_t *left_list, superblock_t *right_list, 92 intersection_t ** cut_list); 93 94 // remove all the segs from the list, partitioning them into the left 95 // or right lists based on the given partition line. Adds any 96 // intersections onto the intersection list as it goes. 97 // 98 void SeparateSegs(superblock_t *seg_list, seg_t *part, 99 superblock_t *left_list, superblock_t *right_list, 100 intersection_t ** cut_list); 101 102 // analyse the intersection list, and add any needed minisegs to the 103 // given seg lists (one miniseg on each side). All the intersection 104 // structures will be freed back into a quick-alloc list. 105 // 106 void AddMinisegs(seg_t *part, 107 superblock_t *left_list, superblock_t *right_list, 108 intersection_t *cut_list); 109 110 // free the quick allocation cut list 111 void FreeQuickAllocCuts(void); 112 113 114 #endif /* __GLBSP_SEG_H__ */ 115