neo/idlib/geometry/Surface_Polytope.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 "../precompiled.h"
  30 #pragma hdrstop
  31
  32 #define POLYTOPE_VERTEX_EPSILON         0.1f
  33
  34
  35 /*
  36 ====================
  37 idSurface_Polytope::FromPlanes
  38 ====================
  39 */
  40 void idSurface_Polytope::FromPlanes( const idPlane *planes, const int numPlanes ) {
  41         int i, j, k, *windingVerts;
  42         idFixedWinding w;
  43         idDrawVert newVert;
  44
  45         windingVerts = (int *) _alloca( MAX_POINTS_ON_WINDING * sizeof( int ) );
  46         memset( &newVert, 0, sizeof( newVert ) );
  47
  48         for ( i = 0; i < numPlanes; i++ ) {
  49
  50                 w.BaseForPlane( planes[i] );
  51
  52                 for ( j = 0; j < numPlanes; j++ ) {
  53                         if ( j == i ) {
  54                                 continue;
  55                         }
  56                         if ( !w.ClipInPlace( -planes[j], ON_EPSILON, true ) ) {
  57                                 break;
  58                         }
  59                 }
  60                 if ( !w.GetNumPoints() ) {
  61                         continue;
  62                 }
  63
  64                 for ( j = 0; j < w.GetNumPoints(); j++ ) {
  65                         for ( k = 0; k < verts.Num(); j++ ) {
  66                                 if ( verts[k].xyz.Compare( w[j].ToVec3(), POLYTOPE_VERTEX_EPSILON ) ) {
  67                                         break;
  68                                 }
  69                         }
  70                         if ( k >= verts.Num() ) {
  71                                 newVert.xyz = w[j].ToVec3();
  72                                 k = verts.Append( newVert );
  73                         }
  74                         windingVerts[j] = k;
  75                 }
  76
  77                 for ( j = 2; j < w.GetNumPoints(); j++ ) {
  78                         indexes.Append( windingVerts[0] );
  79                         indexes.Append( windingVerts[j-1] );
  80                         indexes.Append( windingVerts[j] );
  81                 }
  82         }
  83
  84         GenerateEdgeIndexes();
  85 }
  86
  87 /*
  88 ====================
  89 idSurface_Polytope::SetupTetrahedron
  90 ====================
  91 */
  92 void idSurface_Polytope::SetupTetrahedron( const idBounds &bounds ) {
  93         idVec3 center, scale;
  94         float c1, c2, c3;
  95
  96         c1 = 0.4714045207f;
  97         c2 = 0.8164965809f;
  98         c3 = -0.3333333333f;
  99
 100         center = bounds.GetCenter();
 101         scale = bounds[1] - center;
 102
 103         verts.SetNum( 4 );
 104         verts[0].xyz = center + idVec3( 0.0f, 0.0f, scale.z );
 105         verts[1].xyz = center + idVec3( 2.0f * c1 * scale.x, 0.0f, c3 * scale.z );
 106         verts[2].xyz = center + idVec3( -c1 * scale.x, c2 * scale.y, c3 * scale.z );
 107         verts[3].xyz = center + idVec3( -c1 * scale.x, -c2 * scale.y, c3 * scale.z );
 108
 109         indexes.SetNum( 4*3 );
 110         indexes[0*3+0] = 0;
 111         indexes[0*3+1] = 1;
 112         indexes[0*3+2] = 2;
 113         indexes[1*3+0] = 0;
 114         indexes[1*3+1] = 2;
 115         indexes[1*3+2] = 3;
 116         indexes[2*3+0] = 0;
 117         indexes[2*3+1] = 3;
 118         indexes[2*3+2] = 1;
 119         indexes[3*3+0] = 1;
 120         indexes[3*3+1] = 3;
 121         indexes[3*3+2] = 2;
 122
 123         GenerateEdgeIndexes();
 124 }
 125
 126 /*
 127 ====================
 128 idSurface_Polytope::SetupHexahedron
 129 ====================
 130 */
 131 void idSurface_Polytope::SetupHexahedron( const idBounds &bounds ) {
 132         idVec3 center, scale;
 133
 134         center = bounds.GetCenter();
 135         scale = bounds[1] - center;
 136
 137         verts.SetNum( 8 );
 138         verts[0].xyz = center + idVec3( -scale.x, -scale.y, -scale.z );
 139         verts[1].xyz = center + idVec3(  scale.x, -scale.y, -scale.z );
 140         verts[2].xyz = center + idVec3(  scale.x,  scale.y, -scale.z );
 141         verts[3].xyz = center + idVec3( -scale.x,  scale.y, -scale.z );
 142         verts[4].xyz = center + idVec3( -scale.x, -scale.y,  scale.z );
 143         verts[5].xyz = center + idVec3(  scale.x, -scale.y,  scale.z );
 144         verts[6].xyz = center + idVec3(  scale.x,  scale.y,  scale.z );
 145         verts[7].xyz = center + idVec3( -scale.x,  scale.y,  scale.z );
 146
 147         indexes.SetNum( 12*3 );
 148         indexes[ 0*3+0] = 0;
 149         indexes[ 0*3+1] = 3;
 150         indexes[ 0*3+2] = 2;
 151         indexes[ 1*3+0] = 0;
 152         indexes[ 1*3+1] = 2;
 153         indexes[ 1*3+2] = 1;
 154         indexes[ 2*3+0] = 0;
 155         indexes[ 2*3+1] = 1;
 156         indexes[ 2*3+2] = 5;
 157         indexes[ 3*3+0] = 0;
 158         indexes[ 3*3+1] = 5;
 159         indexes[ 3*3+2] = 4;
 160         indexes[ 4*3+0] = 0;
 161         indexes[ 4*3+1] = 4;
 162         indexes[ 4*3+2] = 7;
 163         indexes[ 5*3+0] = 0;
 164         indexes[ 5*3+1] = 7;
 165         indexes[ 5*3+2] = 3;
 166         indexes[ 6*3+0] = 6;
 167         indexes[ 6*3+1] = 5;
 168         indexes[ 6*3+2] = 1;
 169         indexes[ 7*3+0] = 6;
 170         indexes[ 7*3+1] = 1;
 171         indexes[ 7*3+2] = 2;
 172         indexes[ 8*3+0] = 6;
 173         indexes[ 8*3+1] = 2;
 174         indexes[ 8*3+2] = 3;
 175         indexes[ 9*3+0] = 6;
 176         indexes[ 9*3+1] = 3;
 177         indexes[ 9*3+2] = 7;
 178         indexes[10*3+0] = 6;
 179         indexes[10*3+1] = 7;
 180         indexes[10*3+2] = 4;
 181         indexes[11*3+0] = 6;
 182         indexes[11*3+1] = 4;
 183         indexes[11*3+2] = 5;
 184
 185         GenerateEdgeIndexes();
 186 }
 187
 188 /*
 189 ====================
 190 idSurface_Polytope::SetupOctahedron
 191 ====================
 192 */
 193 void idSurface_Polytope::SetupOctahedron( const idBounds &bounds ) {
 194         idVec3 center, scale;
 195
 196         center = bounds.GetCenter();
 197         scale = bounds[1] - center;
 198
 199         verts.SetNum( 6 );
 200         verts[0].xyz = center + idVec3(  scale.x, 0.0f, 0.0f );
 201         verts[1].xyz = center + idVec3( -scale.x, 0.0f, 0.0f );
 202         verts[2].xyz = center + idVec3( 0.0f,  scale.y, 0.0f );
 203         verts[3].xyz = center + idVec3( 0.0f, -scale.y, 0.0f );
 204         verts[4].xyz = center + idVec3( 0.0f, 0.0f,  scale.z );
 205         verts[5].xyz = center + idVec3( 0.0f, 0.0f, -scale.z );
 206
 207         indexes.SetNum( 8*3 );
 208         indexes[0*3+0] = 4;
 209         indexes[0*3+1] = 0;
 210         indexes[0*3+2] = 2;
 211         indexes[1*3+0] = 4;
 212         indexes[1*3+1] = 2;
 213         indexes[1*3+2] = 1;
 214         indexes[2*3+0] = 4;
 215         indexes[2*3+1] = 1;
 216         indexes[2*3+2] = 3;
 217         indexes[3*3+0] = 4;
 218         indexes[3*3+1] = 3;
 219         indexes[3*3+2] = 0;
 220         indexes[4*3+0] = 5;
 221         indexes[4*3+1] = 2;
 222         indexes[4*3+2] = 0;
 223         indexes[5*3+0] = 5;
 224         indexes[5*3+1] = 1;
 225         indexes[5*3+2] = 2;
 226         indexes[6*3+0] = 5;
 227         indexes[6*3+1] = 3;
 228         indexes[6*3+2] = 1;
 229         indexes[7*3+0] = 5;
 230         indexes[7*3+1] = 0;
 231         indexes[7*3+2] = 3;
 232
 233         GenerateEdgeIndexes();
 234 }
 235
 236 /*
 237 ====================
 238 idSurface_Polytope::SetupDodecahedron
 239 ====================
 240 */
 241 void idSurface_Polytope::SetupDodecahedron( const idBounds &bounds ) {
 242 }
 243
 244 /*
 245 ====================
 246 idSurface_Polytope::SetupIcosahedron
 247 ====================
 248 */
 249 void idSurface_Polytope::SetupIcosahedron( const idBounds &bounds ) {
 250 }
 251
 252 /*
 253 ====================
 254 idSurface_Polytope::SetupCylinder
 255 ====================
 256 */
 257 void idSurface_Polytope::SetupCylinder( const idBounds &bounds, const int numSides ) {
 258 }
 259
 260 /*
 261 ====================
 262 idSurface_Polytope::SetupCone
 263 ====================
 264 */
 265 void idSurface_Polytope::SetupCone( const idBounds &bounds, const int numSides ) {
 266 }
 267
 268 /*
 269 ====================
 270 idSurface_Polytope::SplitPolytope
 271 ====================
 272 */
 273 int idSurface_Polytope::SplitPolytope( const idPlane &plane, const float epsilon, idSurface_Polytope **front, idSurface_Polytope **back ) const {
 274         int side, i, j, s, v0, v1, v2, edgeNum;
 275         idSurface *surface[2];
 276         idSurface_Polytope *polytopeSurfaces[2], *surf;
 277         int *onPlaneEdges[2];
 278
 279         onPlaneEdges[0] = (int *) _alloca( indexes.Num() / 3 * sizeof( int ) );
 280         onPlaneEdges[1] = (int *) _alloca( indexes.Num() / 3 * sizeof( int ) );
 281
 282         side = Split( plane, epsilon, &surface[0], &surface[1], onPlaneEdges[0], onPlaneEdges[1] );
 283
 284         *front = polytopeSurfaces[0] = new idSurface_Polytope;
 285         *back = polytopeSurfaces[1] = new idSurface_Polytope;
 286
 287         for ( s = 0; s < 2; s++ ) {
 288                 if ( surface[s] ) {
 289                         polytopeSurfaces[s] = new idSurface_Polytope;
 290                         polytopeSurfaces[s]->SwapTriangles( *surface[s] );
 291                         delete surface[s];
 292                         surface[s] = NULL;
 293                 }
 294         }
 295
 296         *front = polytopeSurfaces[0];
 297         *back = polytopeSurfaces[1];
 298
 299         if ( side != SIDE_CROSS ) {
 300                 return side;
 301         }
 302
 303         // add triangles to close off the front and back polytope
 304         for ( s = 0; s < 2; s++ ) {
 305
 306                 surf = polytopeSurfaces[s];
 307
 308                 edgeNum = surf->edgeIndexes[onPlaneEdges[s][0]];
 309                 v0 = surf->edges[abs(edgeNum)].verts[INTSIGNBITSET(edgeNum)];
 310                 v1 = surf->edges[abs(edgeNum)].verts[INTSIGNBITNOTSET(edgeNum)];
 311
 312                 for ( i = 1; onPlaneEdges[s][i] >= 0; i++ ) {
 313                         for ( j = i+1; onPlaneEdges[s][j] >= 0; j++ ) {
 314                                 edgeNum = surf->edgeIndexes[onPlaneEdges[s][j]];
 315                                 if ( v1 == surf->edges[abs(edgeNum)].verts[INTSIGNBITSET(edgeNum)] ) {
 316                                         v1 = surf->edges[abs(edgeNum)].verts[INTSIGNBITNOTSET(edgeNum)];
 317                                         idSwap( onPlaneEdges[s][i], onPlaneEdges[s][j] );
 318                                         break;
 319                                 }
 320                         }
 321                 }
 322
 323                 for ( i = 2; onPlaneEdges[s][i] >= 0; i++ ) {
 324                         edgeNum = surf->edgeIndexes[onPlaneEdges[s][i]];
 325                         v1 = surf->edges[abs(edgeNum)].verts[INTSIGNBITNOTSET(edgeNum)];
 326                         v2 = surf->edges[abs(edgeNum)].verts[INTSIGNBITSET(edgeNum)];
 327                         surf->indexes.Append( v0 );
 328                         surf->indexes.Append( v1 );
 329                         surf->indexes.Append( v2 );
 330                 }
 331
 332                 surf->GenerateEdgeIndexes();
 333         }
 334
 335         return side;
 336 }