neo/tools/compilers/dmap/tritools.cpp

   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/precompiled.h"
  30 #pragma hdrstop
  31
  32 #include "dmap.h"
  33
  34 /*
  35
  36   All triangle list functions should behave reasonably with NULL lists.
  37
  38 */
  39
  40 /*
  41 ===============
  42 AllocTri
  43 ===============
  44 */
  45 mapTri_t        *AllocTri( void ) {
  46         mapTri_t        *tri;
  47
  48         tri = (mapTri_t *)Mem_Alloc( sizeof( *tri ) );
  49         memset( tri, 0, sizeof( *tri ) );
  50         return tri;
  51 }
  52
  53 /*
  54 ===============
  55 FreeTri
  56 ===============
  57 */
  58 void            FreeTri( mapTri_t *tri ) {
  59         Mem_Free( tri );
  60 }
  61
  62
  63 /*
  64 ===============
  65 MergeTriLists
  66
  67 This does not copy any tris, it just relinks them
  68 ===============
  69 */
  70 mapTri_t        *MergeTriLists( mapTri_t *a, mapTri_t *b ) {
  71         mapTri_t        **prev;
  72
  73         prev = &a;
  74         while ( *prev ) {
  75                 prev = &(*prev)->next;
  76         }
  77
  78         *prev = b;
  79
  80         return a;
  81 }
  82
  83
  84 /*
  85 ===============
  86 FreeTriList
  87 ===============
  88 */
  89 void FreeTriList( mapTri_t *a ) {
  90         mapTri_t        *next;
  91
  92         for ( ; a ; a = next ) {
  93                 next = a->next;
  94                 Mem_Free( a );
  95         }
  96 }
  97
  98 /*
  99 ===============
 100 CopyTriList
 101 ===============
 102 */
 103 mapTri_t        *CopyTriList( const mapTri_t *a ) {
 104         mapTri_t        *testList;
 105         const mapTri_t  *tri;
 106
 107         testList = NULL;
 108         for ( tri = a ; tri ; tri = tri->next ) {
 109                 mapTri_t        *copy;
 110
 111                 copy = CopyMapTri( tri );
 112                 copy ->next = testList;
 113                 testList = copy;
 114         }
 115
 116         return testList;
 117 }
 118
 119
 120 /*
 121 =============
 122 CountTriList
 123 =============
 124 */
 125 int     CountTriList( const mapTri_t *tri ) {
 126         int             c;
 127
 128         c = 0;
 129         while ( tri ) {
 130                 c++;
 131                 tri = tri->next;
 132         }
 133
 134         return c;
 135 }
 136
 137
 138 /*
 139 ===============
 140 CopyMapTri
 141 ===============
 142 */
 143 mapTri_t        *CopyMapTri( const mapTri_t *tri ) {
 144         mapTri_t                *t;
 145
 146         t = (mapTri_t *)Mem_Alloc( sizeof( *t ) );
 147         *t = *tri;
 148
 149         return t;
 150 }
 151
 152 /*
 153 ===============
 154 MapTriArea
 155 ===============
 156 */
 157 float MapTriArea( const mapTri_t *tri ) {
 158         return idWinding::TriangleArea( tri->v[0].xyz, tri->v[1].xyz, tri->v[2].xyz );
 159 }
 160
 161 /*
 162 ===============
 163 RemoveBadTris
 164
 165 Return a new list with any zero or negative area triangles removed
 166 ===============
 167 */
 168 mapTri_t        *RemoveBadTris( const mapTri_t *list ) {
 169         mapTri_t        *newList;
 170         mapTri_t        *copy;
 171         const mapTri_t  *tri;
 172
 173         newList = NULL;
 174
 175         for ( tri = list ; tri ; tri = tri->next ) {
 176                 if ( MapTriArea( tri ) > 0 ) {
 177                         copy = CopyMapTri( tri );
 178                         copy->next = newList;
 179                         newList = copy;
 180                 }
 181         }
 182
 183         return newList;
 184 }
 185
 186 /*
 187 ================
 188 BoundTriList
 189 ================
 190 */
 191 void BoundTriList( const mapTri_t *list, idBounds &b ) {
 192         b.Clear();
 193         for ( ; list ; list = list->next ) {
 194                 b.AddPoint( list->v[0].xyz );
 195                 b.AddPoint( list->v[1].xyz );
 196                 b.AddPoint( list->v[2].xyz );
 197         }
 198 }
 199
 200 /*
 201 ================
 202 DrawTri
 203 ================
 204 */
 205 void DrawTri( const mapTri_t *tri ) {
 206         idWinding w;
 207
 208         w.SetNumPoints( 3 );
 209         VectorCopy( tri->v[0].xyz, w[0] );
 210         VectorCopy( tri->v[1].xyz, w[1] );
 211         VectorCopy( tri->v[2].xyz, w[2] );
 212         DrawWinding( &w );
 213 }
 214
 215
 216 /*
 217 ================
 218 FlipTriList
 219
 220 Swaps the vertex order
 221 ================
 222 */
 223 void    FlipTriList( mapTri_t *tris ) {
 224         mapTri_t        *tri;
 225
 226         for ( tri = tris ; tri ; tri = tri->next ) {
 227                 idDrawVert      v;
 228                 const struct hashVert_s *hv;
 229                 struct optVertex_s      *ov;
 230
 231                 v = tri->v[0];
 232                 tri->v[0] = tri->v[2];
 233                 tri->v[2] = v;
 234
 235                 hv = tri->hashVert[0];
 236                 tri->hashVert[0] = tri->hashVert[2];
 237                 tri->hashVert[2] = hv;
 238
 239                 ov = tri->optVert[0];
 240                 tri->optVert[0] = tri->optVert[2];
 241                 tri->optVert[2] = ov;
 242         }
 243 }
 244
 245 /*
 246 ================
 247 WindingForTri
 248 ================
 249 */
 250 idWinding *WindingForTri( const mapTri_t *tri ) {
 251         idWinding       *w;
 252
 253         w = new idWinding( 3 );
 254         w->SetNumPoints( 3 );
 255         VectorCopy( tri->v[0].xyz, (*w)[0] );
 256         VectorCopy( tri->v[1].xyz, (*w)[1] );
 257         VectorCopy( tri->v[2].xyz, (*w)[2] );
 258
 259         return w;
 260 }
 261
 262 /*
 263 ================
 264 TriVertsFromOriginal
 265
 266 Regenerate the texcoords and colors on a fragmented tri from the plane equations
 267 ================
 268 */
 269 void            TriVertsFromOriginal( mapTri_t *tri, const mapTri_t *original ) {
 270         int             i, j;
 271         float   denom;
 272
 273         denom = idWinding::TriangleArea( original->v[0].xyz, original->v[1].xyz, original->v[2].xyz );
 274         if ( denom == 0 ) {
 275                 return;         // original was degenerate, so it doesn't matter
 276         }
 277
 278         for ( i = 0 ; i < 3 ; i++ ) {
 279                 float   a, b, c;
 280
 281                 // find the barycentric coordinates
 282                 a = idWinding::TriangleArea( tri->v[i].xyz, original->v[1].xyz, original->v[2].xyz ) / denom;
 283                 b = idWinding::TriangleArea( tri->v[i].xyz, original->v[2].xyz, original->v[0].xyz ) / denom;
 284                 c = idWinding::TriangleArea( tri->v[i].xyz, original->v[0].xyz, original->v[1].xyz ) / denom;
 285
 286                 // regenerate the interpolated values
 287                 tri->v[i].st[0] = a * original->v[0].st[0]
 288                          + b * original->v[1].st[0] + c * original->v[2].st[0];
 289                 tri->v[i].st[1] = a * original->v[0].st[1]
 290                          + b * original->v[1].st[1] + c * original->v[2].st[1];
 291
 292                 for ( j = 0 ; j < 3 ; j++ ) {
 293                         tri->v[i].normal[j] = a * original->v[0].normal[j]
 294                                  + b * original->v[1].normal[j] + c * original->v[2].normal[j];
 295                 }
 296                 tri->v[i].normal.Normalize();
 297         }
 298 }
 299
 300 /*
 301 ================
 302 WindingToTriList
 303
 304 Generates a new list of triangles with proper texcoords from a winding
 305 created by clipping the originalTri
 306
 307 OriginalTri can be NULL if you don't care about texCoords
 308 ================
 309 */
 310 mapTri_t *WindingToTriList( const idWinding *w, const mapTri_t *originalTri ) {
 311         mapTri_t        *tri;
 312         mapTri_t        *triList;
 313         int                     i, j;
 314         const idVec3    *vec;
 315
 316         if ( !w ) {
 317                 return NULL;
 318         }
 319
 320         triList = NULL;
 321         for ( i = 2 ; i < w->GetNumPoints() ; i++ ) {
 322                 tri = AllocTri();
 323                 if ( !originalTri ) {
 324                         memset( tri, 0, sizeof( *tri ) );
 325                 } else {
 326                         *tri = *originalTri;
 327                 }
 328                 tri->next = triList;
 329                 triList = tri;
 330
 331                 for ( j = 0 ; j < 3 ; j++ ) {
 332                         if ( j == 0 ) {
 333                                 vec = &((*w)[0]).ToVec3();
 334                         } else if ( j == 1 ) {
 335                                 vec = &((*w)[i-1]).ToVec3();
 336                         } else {
 337                                 vec = &((*w)[i]).ToVec3();
 338                         }
 339
 340                         VectorCopy( *vec, tri->v[j].xyz );
 341                 }
 342                 if ( originalTri ) {
 343                         TriVertsFromOriginal( tri, originalTri );
 344                 }
 345         }
 346
 347         return triList;
 348 }
 349
 350
 351 /*
 352 ==================
 353 ClipTriList
 354 ==================
 355 */
 356 void    ClipTriList( const mapTri_t *list, const idPlane &plane, float epsilon,
 357                                                 mapTri_t **front, mapTri_t **back ) {
 358         const mapTri_t *tri;
 359         mapTri_t                *newList;
 360         idWinding               *w, *frontW, *backW;
 361
 362         *front = NULL;
 363         *back = NULL;
 364
 365         for ( tri = list ; tri ; tri = tri->next ) {
 366                 w = WindingForTri( tri );
 367                 w->Split( plane, epsilon, &frontW, &backW );
 368
 369                 newList = WindingToTriList( frontW, tri );
 370                 *front = MergeTriLists( *front, newList );
 371
 372                 newList = WindingToTriList( backW, tri );
 373                 *back = MergeTriLists( *back, newList );
 374
 375                 delete w;
 376         }
 377
 378 }
 379
 380 /*
 381 ==================
 382 PlaneForTri
 383 ==================
 384 */
 385 void    PlaneForTri( const mapTri_t *tri, idPlane &plane ) {
 386         plane.FromPoints( tri->v[0].xyz, tri->v[1].xyz, tri->v[2].xyz );
 387 }