1 #ifndef _RENDER_VISIBILITY_TREE_CLASS_ 2 #define _RENDER_VISIBILITY_TREE_CLASS_ 3 /* 4 5 Copyright (C) 1991-2001 and beyond by Bungie Studios, Inc. 6 and the "Aleph One" developers. 7 8 This program is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3 of the License, or 11 (at your option) any later version. 12 13 This program is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 This license is contained in the file "COPYING", 19 which is included with this source code; it is available online at 20 http://www.gnu.org/licenses/gpl.html 21 22 Rendering Visibility-Tree Class 23 by Loren Petrich, 24 August 6, 2000 25 26 Defines a class for doing rendering visibility; from render.c 27 28 Made [view_data *view] a member and removed it as an argument 29 30 Sep. 11, 2000 (Loren Petrich): 31 Made POINTER_DATA more general -- byte *, so one can do pointer arithmetic on it correctly. 32 33 Sep. 15, 2000 (Loren Petrich): 34 Fixed stale-pointer bug in cast_render_ray() by using index instead of pointer to parent node 35 36 Oct 13, 2000 37 LP: replaced GrowableLists and ResizableLists with STL vectors 38 */ 39 40 #include <deque> 41 #include <vector> 42 #include "map.h" 43 #include "render.h" 44 45 46 // Made pointers more general 47 typedef byte *POINTER_DATA; 48 #define POINTER_CAST(x) ((POINTER_DATA)(x)) 49 50 51 // LP addition: typecast for cross-products, since these can be large 52 typedef double CROSSPROD_TYPE; 53 54 55 // Macros 56 #define WRAP_LOW(n,max) ((n)?((n)-1):(max)) 57 #define WRAP_HIGH(n,max) (((n)==(max))?0:((n)+1)) 58 59 60 // LP: put here since it also used in build_base_node_list() 61 enum /* next_polygon_along_line() states */ 62 { 63 _looking_for_first_nonzero_vertex, 64 _looking_clockwise_for_right_vertex, 65 _looking_counterclockwise_for_left_vertex, 66 _looking_for_next_nonzero_vertex 67 }; 68 69 70 /* ---------- clipping data */ 71 72 enum /* �_clip_data flags */ 73 { 74 _clip_left= 0x0001, 75 _clip_right= 0x0002, 76 _clip_up= 0x0004, 77 _clip_down= 0x0008 78 }; 79 80 enum /* left and right sides of screen */ 81 { 82 indexLEFT_SIDE_OF_SCREEN, 83 indexRIGHT_SIDE_OF_SCREEN, 84 NUMBER_OF_INITIAL_ENDPOINT_CLIPS 85 }; 86 87 enum /* top and bottom sides of screen */ 88 { 89 indexTOP_AND_BOTTOM_OF_SCREEN, 90 NUMBER_OF_INITIAL_LINE_CLIPS 91 }; 92 93 struct line_clip_data 94 { 95 uint16 flags; 96 short x0, x1; /* clipping bounds */ 97 98 // LP change: made more long-distance friendly 99 long_vector2d top_vector, bottom_vector; 100 short top_y, bottom_y; /* screen-space */ 101 }; 102 103 struct endpoint_clip_data 104 { 105 uint16 flags; 106 short x; /* screen-space */ 107 108 // LP change: made into a long vector for long views 109 long_vector2d vector; 110 }; 111 112 struct clipping_window_data 113 { 114 // LP change: split into two sets of vectors: left-right and top-bottom 115 long_vector2d left, right; 116 long_vector2d top, bottom; 117 short x0, x1, y0, y1; 118 119 struct clipping_window_data *next_window; 120 }; 121 122 123 /* ---------- nodes */ 124 125 #define MAXIMUM_CLIPPING_ENDPOINTS_PER_NODE 4 126 #define MAXIMUM_CLIPPING_LINES_PER_NODE (MAXIMUM_VERTICES_PER_POLYGON-2) 127 128 struct node_data 129 { 130 uint16 flags; 131 short polygon_index; 132 133 /* clipping effects all children (and was caused by crossing from parent) */ 134 short clipping_endpoint_count; 135 short clipping_endpoints[MAXIMUM_CLIPPING_ENDPOINTS_PER_NODE]; 136 short clipping_line_count; 137 short clipping_lines[MAXIMUM_CLIPPING_LINES_PER_NODE]; 138 139 node_data *parent; /* a pointer to our parent node (NULL for the root) */ 140 node_data **reference; /* a pointer to the pointer which references us (NULL for the root) */ 141 node_data *siblings; /* pointer to the next sibling */ 142 node_data *children; /* pointer to the head of the child array */ 143 144 // LP addition: this is inspired by Rhys Hill's tree structures; 145 // this is for membership in a polygon-sort tree. 146 // As constructed, its root will be the first node in the list, the viewpoint node. 147 node_data *PS_Greater; // To nodes with higher polygon indices 148 node_data *PS_Less; // To nodes with lower polygon indices 149 node_data *PS_Shared; // To other nodes at the same polygon 150 }; 151 152 153 class RenderVisTreeClass 154 { 155 // Auxiliary data and routines: 156 157 // Polygon queue now a growable list; its working size is maintained separately 158 vector<short> PolygonQueue; 159 size_t polygon_queue_size; 160 161 /* translates from map indexes to clip indexes, only valid if appropriate render flag is set */ 162 vector<size_t> line_clip_indexes; 163 164 // Turned preprocessor macro into function 165 void PUSH_POLYGON_INDEX(short polygon_index); 166 167 void initialize_polygon_queue(); 168 169 void initialize_render_tree(); 170 171 void initialize_clip_data(); 172 173 uint16 next_polygon_along_line(short *polygon_index, world_point2d *origin, long_vector2d *_vector, 174 short *clipping_endpoint_index, short *clipping_line_index, short bias); 175 176 // LP: referring to parent node by index instead of by pointer, to avoid stale-pointer bug 177 void cast_render_ray(long_vector2d *_vector, short endpoint_index, 178 node_data* parent, short bias); 179 180 uint16 decide_where_vertex_leads(short *polygon_index, short *line_index, short *side_index, short endpoint_index_in_polygon_list, 181 world_point2d *origin, long_vector2d *_vector, uint16 clip_flags, short bias); 182 183 void calculate_line_clipping_information(short line_index, uint16 clip_flags); 184 185 short calculate_endpoint_clipping_information(short endpoint_index, uint16 clip_flags); 186 187 void ResetEndpointClips(void); 188 189 void ResetLineClips(); 190 191 public: 192 193 /* gives screen x-coordinates for a map endpoint (only valid if _endpoint_is_visible) */ 194 vector<short> endpoint_x_coordinates; 195 196 /* every time we find a unique endpoint which clips something, we build one of these for it */ 197 // LP addition: growable list 198 // Length changed in calculate_endpoint_clipping_information() and ResetEndpointClips() 199 vector<endpoint_clip_data> EndpointClips; 200 201 /* every time we find a unique line which clips something, we build one of these for it (notice 202 the translation table from line_indexes on the map to line_clip_indexes in our table for when 203 we cross the same clip line again */ 204 // LP addition: growable list 205 // Length changed in calculate_line_clipping_information() and ResetLineClips() 206 vector<line_clip_data> LineClips; 207 208 // Growable list of clipping windows 209 // Length changed in build_clipping_windows(), initialize_clip_data(), 210 // and build_aggregate_render_object_clipping_window(); 211 // keep sorted-node clipping-window pointers in sync with render-object ones 212 vector<clipping_window_data> ClippingWindows; 213 214 // Growable list of node_data values 215 // Length changed in cast_render_ray() and initialize_render_tree() 216 typedef std::deque<node_data> NodeList; 217 NodeList Nodes; 218 219 // Pointer to view 220 view_data *view; 221 222 // If true, the render tree will disable exploration 223 // polygons (for the M1-style exploration goal). 224 bool mark_as_explored; 225 226 // If true (default), the render tree will fill out 227 // the automap. 228 bool add_to_automap; 229 230 // Resizes all the objects defined inside; 231 // the resizing is lazy 232 void Resize(size_t NumEndpoints, size_t NumLines); 233 234 // Builds the visibility tree 235 void build_render_tree(); 236 237 // Inits everything 238 RenderVisTreeClass(); 239 }; 240 241 242 #endif 243