1 /* 2 =========================================================================== 3 4 Doom 3 GPL Source Code 5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company. 6 7 This file is part of the Doom 3 GPL Source Code ("Doom 3 Source Code"). 8 9 Doom 3 Source Code is free software: you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation, either version 3 of the License, or 12 (at your option) any later version. 13 14 Doom 3 Source Code 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 You should have received a copy of the GNU General Public License 20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>. 21 22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below. 23 24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA. 25 26 =========================================================================== 27 */ 28 29 #include "idlib/containers/PlaneSet.h" 30 #include "idlib/MapFile.h" 31 #include "cm/CollisionModel.h" 32 #include "renderer/tr_local.h" 33 34 typedef struct primitive_s { 35 struct primitive_s *next; 36 37 // only one of these will be non-NULL 38 struct bspbrush_s * brush; 39 struct mapTri_s * tris; 40 } primitive_t; 41 42 43 typedef struct { 44 struct optimizeGroup_s *groups; 45 // we might want to add other fields later 46 } uArea_t; 47 48 typedef struct { 49 idMapEntity * mapEntity; // points into mapFile_t data 50 51 idVec3 origin; 52 primitive_t * primitives; 53 struct tree_s * tree; 54 55 int numAreas; 56 uArea_t * areas; 57 } uEntity_t; 58 59 60 // chains of mapTri_t are the general unit of processing 61 typedef struct mapTri_s { 62 struct mapTri_s * next; 63 64 const idMaterial * material; 65 void * mergeGroup; // we want to avoid merging triangles 66 // from different fixed groups, like guiSurfs and mirrors 67 int planeNum; // not set universally, just in some areas 68 69 idDrawVert v[3]; 70 const struct hashVert_s *hashVert[3]; 71 struct optVertex_s *optVert[3]; 72 } mapTri_t; 73 74 75 typedef struct { 76 int width, height; 77 idDrawVert * verts; 78 } mesh_t; 79 80 81 #define MAX_PATCH_SIZE 32 82 83 #define PLANENUM_LEAF -1 84 85 typedef struct parseMesh_s { 86 struct parseMesh_s *next; 87 mesh_t mesh; 88 const idMaterial * material; 89 } parseMesh_t; 90 91 typedef struct bspface_s { 92 struct bspface_s * next; 93 int planenum; 94 bool portal; // all portals will be selected before 95 // any non-portals 96 bool checked; // used by SelectSplitPlaneNum() 97 idWinding * w; 98 } bspface_t; 99 100 typedef struct { 101 idVec4 v[2]; // the offset value will always be in the 0.0 to 1.0 range 102 } textureVectors_t; 103 104 typedef struct side_s { 105 int planenum; 106 107 const idMaterial * material; 108 textureVectors_t texVec; 109 110 idWinding * winding; // only clipped to the other sides of the brush 111 idWinding * visibleHull; // also clipped to the solid parts of the world 112 } side_t; 113 114 115 typedef struct bspbrush_s { 116 struct bspbrush_s * next; 117 struct bspbrush_s * original; // chopped up brushes will reference the originals 118 119 int entitynum; // editor numbering for messages 120 int brushnum; // editor numbering for messages 121 122 const idMaterial * contentShader; // one face's shader will determine the volume attributes 123 124 int contents; 125 bool opaque; 126 int outputNumber; // set when the brush is written to the file list 127 128 idBounds bounds; 129 int numsides; 130 side_t sides[6]; // variably sized 131 } uBrush_t; 132 133 134 typedef struct drawSurfRef_s { 135 struct drawSurfRef_s * nextRef; 136 int outputNumber; 137 } drawSurfRef_t; 138 139 140 typedef struct node_s { 141 // both leafs and nodes 142 int planenum; // -1 = leaf node 143 struct node_s * parent; 144 idBounds bounds; // valid after portalization 145 146 // nodes only 147 side_t * side; // the side that created the node 148 struct node_s * children[2]; 149 int nodeNumber; // set after pruning 150 151 // leafs only 152 bool opaque; // view can never be inside 153 154 uBrush_t * brushlist; // fragments of all brushes in this leaf 155 // needed for FindSideForPortal 156 157 int area; // determined by flood filling up to areaportals 158 int occupied; // 1 or greater can reach entity 159 uEntity_t * occupant; // for leak file testing 160 161 struct uPortal_s * portals; // also on nodes during construction 162 } node_t; 163 164 165 typedef struct uPortal_s { 166 idPlane plane; 167 node_t *onnode; // NULL = outside box 168 node_t *nodes[2]; // [0] = front side of plane 169 struct uPortal_s *next[2]; 170 idWinding *winding; 171 } uPortal_t; 172 173 // a tree_t is created by FaceBSP() 174 typedef struct tree_s { 175 node_t *headnode; 176 node_t outside_node; 177 idBounds bounds; 178 } tree_t; 179 180 #define MAX_QPATH 256 // max length of a game pathname 181 182 typedef struct { 183 idRenderLightLocal def; 184 char name[MAX_QPATH]; // for naming the shadow volume surface and interactions 185 srfTriangles_t *shadowTris; 186 } mapLight_t; 187 188 #define MAX_GROUP_LIGHTS 16 189 190 typedef struct optimizeGroup_s { 191 struct optimizeGroup_s *nextGroup; 192 193 idBounds bounds; // set in CarveGroupsByLight 194 195 // all of these must match to add a triangle to the triList 196 bool smoothed; // curves will never merge with brushes 197 int planeNum; 198 int areaNum; 199 const idMaterial * material; 200 int numGroupLights; 201 mapLight_t * groupLights[MAX_GROUP_LIGHTS]; // lights effecting this list 202 void * mergeGroup; // if this differs (guiSurfs, mirrors, etc), the 203 // groups will not be combined into model surfaces 204 // after optimization 205 textureVectors_t texVec; 206 207 bool surfaceEmited; 208 209 mapTri_t * triList; 210 mapTri_t * regeneratedTris; // after each island optimization 211 idVec3 axis[2]; // orthogonal to the plane, so optimization can be 2D 212 } optimizeGroup_t; 213 214 // all primitives from the map are added to optimzeGroups, creating new ones as needed 215 // each optimizeGroup is then split into the map areas, creating groups in each area 216 // each optimizeGroup is then divided by each light, creating more groups 217 // the final list of groups is then tjunction fixed against all groups, then optimized internally 218 // multiple optimizeGroups will be merged together into .proc surfaces, but no further optimization 219 // is done on them 220 221 222 //============================================================================= 223 224 // dmap.cpp 225 226 typedef enum { 227 SO_NONE, // 0 228 SO_MERGE_SURFACES, // 1 229 SO_CULL_OCCLUDED, // 2 230 SO_CLIP_OCCLUDERS, // 3 231 SO_CLIP_SILS, // 4 232 SO_SIL_OPTIMIZE // 5 233 } shadowOptLevel_t; 234 235 typedef struct { 236 // mapFileBase will contain the qpath without any extension: "maps/test_box" 237 char mapFileBase[1024]; 238 239 idMapFile *dmapFile; 240 241 idPlaneSet mapPlanes; 242 243 int num_entities; 244 uEntity_t *uEntities; 245 246 int entityNum; 247 248 idList<mapLight_t*> mapLights; 249 250 bool verbose; 251 252 bool glview; 253 bool noOptimize; 254 bool verboseentities; 255 bool noCurves; 256 bool fullCarve; 257 bool noModelBrushes; 258 bool noTJunc; 259 bool nomerge; 260 bool noFlood; 261 bool noClipSides; // don't cut sides by solid leafs, use the entire thing 262 bool noLightCarve; // extra triangle subdivision by light frustums 263 shadowOptLevel_t shadowOptLevel; 264 bool noShadow; // don't create optimized shadow volumes 265 266 idBounds drawBounds; 267 bool drawflag; 268 269 int totalShadowTriangles; 270 int totalShadowVerts; 271 } dmapGlobals_t; 272 273 extern dmapGlobals_t dmapGlobals; 274 275 int FindFloatPlane( const idPlane &plane, bool *fixedDegeneracies = NULL ); 276 277 278 //============================================================================= 279 280 // brush.cpp 281 282 #ifndef CLIP_EPSILON 283 #define CLIP_EPSILON 0.1f 284 #endif 285 286 #define PSIDE_FRONT 1 287 #define PSIDE_BACK 2 288 #define PSIDE_BOTH (PSIDE_FRONT|PSIDE_BACK) 289 #define PSIDE_FACING 4 290 291 int CountBrushList (uBrush_t *brushes); 292 uBrush_t *AllocBrush (int numsides); 293 void FreeBrush (uBrush_t *brushes); 294 void FreeBrushList (uBrush_t *brushes); 295 uBrush_t *CopyBrush (uBrush_t *brush); 296 void DrawBrushList (uBrush_t *brush); 297 void PrintBrush (uBrush_t *brush); 298 bool BoundBrush (uBrush_t *brush); 299 bool CreateBrushWindings (uBrush_t *brush); 300 uBrush_t *BrushFromBounds( const idBounds &bounds ); 301 float BrushVolume (uBrush_t *brush); 302 void WriteBspBrushMap( const char *name, uBrush_t *list ); 303 304 void FilterBrushesIntoTree( uEntity_t *e ); 305 306 void SplitBrush( uBrush_t *brush, int planenum, uBrush_t **front, uBrush_t **back); 307 node_t *AllocNode( void ); 308 309 310 //============================================================================= 311 312 // map.cpp 313 314 bool LoadDMapFile( const char *filename ); 315 void FreeOptimizeGroupList( optimizeGroup_t *groups ); 316 void FreeDMapFile( void ); 317 318 //============================================================================= 319 320 // draw.cpp -- draw debug views either directly, or through glserv.exe 321 322 void Draw_ClearWindow( void ); 323 void DrawWinding( const idWinding *w ); 324 void DrawAuxWinding( const idWinding *w ); 325 326 void DrawLine( idVec3 v1, idVec3 v2, int color ); 327 328 void GLS_BeginScene( void ); 329 void GLS_Winding( const idWinding *w, int code ); 330 void GLS_Triangle( const mapTri_t *tri, int code ); 331 void GLS_EndScene( void ); 332 333 334 335 //============================================================================= 336 337 // portals.cpp 338 339 #define MAX_INTER_AREA_PORTALS 1024 340 341 typedef struct { 342 int area0, area1; 343 side_t *side; 344 } interAreaPortal_t; 345 346 extern interAreaPortal_t interAreaPortals[MAX_INTER_AREA_PORTALS]; 347 extern int numInterAreaPortals; 348 349 bool FloodEntities( tree_t *tree ); 350 void FillOutside( uEntity_t *e ); 351 void FloodAreas( uEntity_t *e ); 352 void MakeTreePortals( tree_t *tree ); 353 void FreePortal( uPortal_t *p ); 354 355 //============================================================================= 356 357 // glfile.cpp -- write a debug file to be viewd with glview.exe 358 359 void OutputWinding( idWinding *w, idFile *glview ); 360 void WriteGLView( tree_t *tree, char *source ); 361 362 //============================================================================= 363 364 // leakfile.cpp 365 366 void LeakFile( tree_t *tree ); 367 368 //============================================================================= 369 370 // facebsp.cpp 371 372 tree_t *AllocTree( void ); 373 374 void FreeTree( tree_t *tree ); 375 376 void FreeTree_r( node_t *node ); 377 void FreeTreePortals_r( node_t *node ); 378 379 380 bspface_t *MakeStructuralBspFaceList( primitive_t *list ); 381 bspface_t *MakeVisibleBspFaceList( primitive_t *list ); 382 tree_t *FaceBSP( bspface_t *list ); 383 384 //============================================================================= 385 386 // surface.cpp 387 388 mapTri_t *CullTrisInOpaqueLeafs( mapTri_t *triList, tree_t *tree ); 389 void ClipSidesByTree( uEntity_t *e ); 390 void SplitTrisToSurfaces( mapTri_t *triList, tree_t *tree ); 391 void PutPrimitivesInAreas( uEntity_t *e ); 392 void Prelight( uEntity_t *e ); 393 394 //============================================================================= 395 396 // tritjunction.cpp 397 398 struct hashVert_s *GetHashVert( idVec3 &v ); 399 void HashTriangles( optimizeGroup_t *groupList ); 400 void FreeTJunctionHash( void ); 401 int CountGroupListTris( const optimizeGroup_t *groupList ); 402 void FixEntityTjunctions( uEntity_t *e ); 403 void FixAreaGroupsTjunctions( optimizeGroup_t *groupList ); 404 void FixGlobalTjunctions( uEntity_t *e ); 405 406 //============================================================================= 407 408 // optimize.cpp -- trianlge mesh reoptimization 409 410 // the shadow volume optimizer call internal optimizer routines, normal triangles 411 // will just be done by OptimizeEntity() 412 413 414 typedef struct optVertex_s { 415 idDrawVert v; 416 idVec3 pv; // projected against planar axis, third value is 0 417 struct optEdge_s *edges; 418 struct optVertex_s *islandLink; 419 bool addedToIsland; 420 bool emited; // when regenerating triangles 421 } optVertex_t; 422 423 typedef struct optEdge_s { 424 optVertex_t *v1, *v2; 425 struct optEdge_s *islandLink; 426 bool addedToIsland; 427 bool created; // not one of the original edges 428 bool combined; // combined from two or more colinear edges 429 struct optTri_s *frontTri, *backTri; 430 struct optEdge_s *v1link, *v2link; 431 } optEdge_t; 432 433 typedef struct optTri_s { 434 struct optTri_s *next; 435 idVec3 midpoint; 436 optVertex_t *v[3]; 437 bool filled; 438 } optTri_t; 439 440 typedef struct { 441 optimizeGroup_t *group; 442 optVertex_t *verts; 443 optEdge_t *edges; 444 optTri_t *tris; 445 } optIsland_t; 446 447 448 void OptimizeEntity( uEntity_t *e ); 449 void OptimizeGroupList( optimizeGroup_t *groupList ); 450 451 //============================================================================= 452 453 // tritools.cpp 454 455 mapTri_t *AllocTri( void ); 456 void FreeTri( mapTri_t *tri ); 457 int CountTriList( const mapTri_t *list ); 458 mapTri_t *MergeTriLists( mapTri_t *a, mapTri_t *b ); 459 mapTri_t *CopyTriList( const mapTri_t *a ); 460 void FreeTriList( mapTri_t *a ); 461 mapTri_t *CopyMapTri( const mapTri_t *tri ); 462 float MapTriArea( const mapTri_t *tri ); 463 mapTri_t *RemoveBadTris( const mapTri_t *tri ); 464 void BoundTriList( const mapTri_t *list, idBounds &b ); 465 void DrawTri( const mapTri_t *tri ); 466 void FlipTriList( mapTri_t *tris ); 467 void TriVertsFromOriginal( mapTri_t *tri, const mapTri_t *original ); 468 void PlaneForTri( const mapTri_t *tri, idPlane &plane ); 469 idWinding *WindingForTri( const mapTri_t *tri ); 470 mapTri_t *WindingToTriList( const idWinding *w, const mapTri_t *originalTri ); 471 void ClipTriList( const mapTri_t *list, const idPlane &plane, float epsilon, mapTri_t **front, mapTri_t **back ); 472 473 //============================================================================= 474 475 // output.cpp 476 477 srfTriangles_t *ShareMapTriVerts( const mapTri_t *tris ); 478 void WriteOutputFile( void ); 479 480 //============================================================================= 481 482 // shadowopt.cpp 483 484 srfTriangles_t *CreateLightShadow( optimizeGroup_t *shadowerGroups, const mapLight_t *light ); 485 void FreeBeamTree( struct beamTree_s *beamTree ); 486 487 void CarveTriByBeamTree( const struct beamTree_s *beamTree, const mapTri_t *tri, mapTri_t **lit, mapTri_t **unLit ); 488