Surface_Polytope.cpp 9.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335
  1. /*
  2. ===========================================================================
  3. Doom 3 BFG Edition GPL Source Code
  4. Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company.
  5. This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code").
  6. Doom 3 BFG Edition Source Code is free software: you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation, either version 3 of the License, or
  9. (at your option) any later version.
  10. Doom 3 BFG Edition Source Code is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. GNU General Public License for more details.
  14. You should have received a copy of the GNU General Public License
  15. along with Doom 3 BFG Edition Source Code. If not, see <http://www.gnu.org/licenses/>.
  16. In addition, the Doom 3 BFG Edition 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 BFG Edition Source Code. If not, please request a copy in writing from id Software at the address below.
  17. 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.
  18. ===========================================================================
  19. */
  20. #pragma hdrstop
  21. #include "../precompiled.h"
  22. #define POLYTOPE_VERTEX_EPSILON 0.1f
  23. /*
  24. ====================
  25. idSurface_Polytope::FromPlanes
  26. ====================
  27. */
  28. void idSurface_Polytope::FromPlanes( const idPlane *planes, const int numPlanes ) {
  29. int i, j, k, *windingVerts;
  30. idFixedWinding w;
  31. idDrawVert newVert;
  32. windingVerts = (int *) _alloca( MAX_POINTS_ON_WINDING * sizeof( int ) );
  33. memset( &newVert, 0, sizeof( newVert ) );
  34. for ( i = 0; i < numPlanes; i++ ) {
  35. w.BaseForPlane( planes[i] );
  36. for ( j = 0; j < numPlanes; j++ ) {
  37. if ( j == i ) {
  38. continue;
  39. }
  40. if ( !w.ClipInPlace( -planes[j], ON_EPSILON, true ) ) {
  41. break;
  42. }
  43. }
  44. if ( !w.GetNumPoints() ) {
  45. continue;
  46. }
  47. for ( j = 0; j < w.GetNumPoints(); j++ ) {
  48. for ( k = 0; k < verts.Num(); k++ ) {
  49. if ( verts[k].xyz.Compare( w[j].ToVec3(), POLYTOPE_VERTEX_EPSILON ) ) {
  50. break;
  51. }
  52. }
  53. if ( k >= verts.Num() ) {
  54. newVert.xyz = w[j].ToVec3();
  55. k = verts.Append( newVert );
  56. }
  57. windingVerts[j] = k;
  58. }
  59. for ( j = 2; j < w.GetNumPoints(); j++ ) {
  60. indexes.Append( windingVerts[0] );
  61. indexes.Append( windingVerts[j-1] );
  62. indexes.Append( windingVerts[j] );
  63. }
  64. }
  65. GenerateEdgeIndexes();
  66. }
  67. /*
  68. ====================
  69. idSurface_Polytope::SetupTetrahedron
  70. ====================
  71. */
  72. void idSurface_Polytope::SetupTetrahedron( const idBounds &bounds ) {
  73. idVec3 center, scale;
  74. float c1, c2, c3;
  75. c1 = 0.4714045207f;
  76. c2 = 0.8164965809f;
  77. c3 = -0.3333333333f;
  78. center = bounds.GetCenter();
  79. scale = bounds[1] - center;
  80. verts.SetNum( 4 );
  81. verts[0].xyz = center + idVec3( 0.0f, 0.0f, scale.z );
  82. verts[1].xyz = center + idVec3( 2.0f * c1 * scale.x, 0.0f, c3 * scale.z );
  83. verts[2].xyz = center + idVec3( -c1 * scale.x, c2 * scale.y, c3 * scale.z );
  84. verts[3].xyz = center + idVec3( -c1 * scale.x, -c2 * scale.y, c3 * scale.z );
  85. indexes.SetNum( 4*3 );
  86. indexes[0*3+0] = 0;
  87. indexes[0*3+1] = 1;
  88. indexes[0*3+2] = 2;
  89. indexes[1*3+0] = 0;
  90. indexes[1*3+1] = 2;
  91. indexes[1*3+2] = 3;
  92. indexes[2*3+0] = 0;
  93. indexes[2*3+1] = 3;
  94. indexes[2*3+2] = 1;
  95. indexes[3*3+0] = 1;
  96. indexes[3*3+1] = 3;
  97. indexes[3*3+2] = 2;
  98. GenerateEdgeIndexes();
  99. }
  100. /*
  101. ====================
  102. idSurface_Polytope::SetupHexahedron
  103. ====================
  104. */
  105. void idSurface_Polytope::SetupHexahedron( const idBounds &bounds ) {
  106. idVec3 center, scale;
  107. center = bounds.GetCenter();
  108. scale = bounds[1] - center;
  109. verts.SetNum( 8 );
  110. verts[0].xyz = center + idVec3( -scale.x, -scale.y, -scale.z );
  111. verts[1].xyz = center + idVec3( scale.x, -scale.y, -scale.z );
  112. verts[2].xyz = center + idVec3( scale.x, scale.y, -scale.z );
  113. verts[3].xyz = center + idVec3( -scale.x, scale.y, -scale.z );
  114. verts[4].xyz = center + idVec3( -scale.x, -scale.y, scale.z );
  115. verts[5].xyz = center + idVec3( scale.x, -scale.y, scale.z );
  116. verts[6].xyz = center + idVec3( scale.x, scale.y, scale.z );
  117. verts[7].xyz = center + idVec3( -scale.x, scale.y, scale.z );
  118. indexes.SetNum( 12*3 );
  119. indexes[ 0*3+0] = 0;
  120. indexes[ 0*3+1] = 3;
  121. indexes[ 0*3+2] = 2;
  122. indexes[ 1*3+0] = 0;
  123. indexes[ 1*3+1] = 2;
  124. indexes[ 1*3+2] = 1;
  125. indexes[ 2*3+0] = 0;
  126. indexes[ 2*3+1] = 1;
  127. indexes[ 2*3+2] = 5;
  128. indexes[ 3*3+0] = 0;
  129. indexes[ 3*3+1] = 5;
  130. indexes[ 3*3+2] = 4;
  131. indexes[ 4*3+0] = 0;
  132. indexes[ 4*3+1] = 4;
  133. indexes[ 4*3+2] = 7;
  134. indexes[ 5*3+0] = 0;
  135. indexes[ 5*3+1] = 7;
  136. indexes[ 5*3+2] = 3;
  137. indexes[ 6*3+0] = 6;
  138. indexes[ 6*3+1] = 5;
  139. indexes[ 6*3+2] = 1;
  140. indexes[ 7*3+0] = 6;
  141. indexes[ 7*3+1] = 1;
  142. indexes[ 7*3+2] = 2;
  143. indexes[ 8*3+0] = 6;
  144. indexes[ 8*3+1] = 2;
  145. indexes[ 8*3+2] = 3;
  146. indexes[ 9*3+0] = 6;
  147. indexes[ 9*3+1] = 3;
  148. indexes[ 9*3+2] = 7;
  149. indexes[10*3+0] = 6;
  150. indexes[10*3+1] = 7;
  151. indexes[10*3+2] = 4;
  152. indexes[11*3+0] = 6;
  153. indexes[11*3+1] = 4;
  154. indexes[11*3+2] = 5;
  155. GenerateEdgeIndexes();
  156. }
  157. /*
  158. ====================
  159. idSurface_Polytope::SetupOctahedron
  160. ====================
  161. */
  162. void idSurface_Polytope::SetupOctahedron( const idBounds &bounds ) {
  163. idVec3 center, scale;
  164. center = bounds.GetCenter();
  165. scale = bounds[1] - center;
  166. verts.SetNum( 6 );
  167. verts[0].xyz = center + idVec3( scale.x, 0.0f, 0.0f );
  168. verts[1].xyz = center + idVec3( -scale.x, 0.0f, 0.0f );
  169. verts[2].xyz = center + idVec3( 0.0f, scale.y, 0.0f );
  170. verts[3].xyz = center + idVec3( 0.0f, -scale.y, 0.0f );
  171. verts[4].xyz = center + idVec3( 0.0f, 0.0f, scale.z );
  172. verts[5].xyz = center + idVec3( 0.0f, 0.0f, -scale.z );
  173. indexes.SetNum( 8*3 );
  174. indexes[0*3+0] = 4;
  175. indexes[0*3+1] = 0;
  176. indexes[0*3+2] = 2;
  177. indexes[1*3+0] = 4;
  178. indexes[1*3+1] = 2;
  179. indexes[1*3+2] = 1;
  180. indexes[2*3+0] = 4;
  181. indexes[2*3+1] = 1;
  182. indexes[2*3+2] = 3;
  183. indexes[3*3+0] = 4;
  184. indexes[3*3+1] = 3;
  185. indexes[3*3+2] = 0;
  186. indexes[4*3+0] = 5;
  187. indexes[4*3+1] = 2;
  188. indexes[4*3+2] = 0;
  189. indexes[5*3+0] = 5;
  190. indexes[5*3+1] = 1;
  191. indexes[5*3+2] = 2;
  192. indexes[6*3+0] = 5;
  193. indexes[6*3+1] = 3;
  194. indexes[6*3+2] = 1;
  195. indexes[7*3+0] = 5;
  196. indexes[7*3+1] = 0;
  197. indexes[7*3+2] = 3;
  198. GenerateEdgeIndexes();
  199. }
  200. /*
  201. ====================
  202. idSurface_Polytope::SetupDodecahedron
  203. ====================
  204. */
  205. void idSurface_Polytope::SetupDodecahedron( const idBounds &bounds ) {
  206. }
  207. /*
  208. ====================
  209. idSurface_Polytope::SetupIcosahedron
  210. ====================
  211. */
  212. void idSurface_Polytope::SetupIcosahedron( const idBounds &bounds ) {
  213. }
  214. /*
  215. ====================
  216. idSurface_Polytope::SetupCylinder
  217. ====================
  218. */
  219. void idSurface_Polytope::SetupCylinder( const idBounds &bounds, const int numSides ) {
  220. }
  221. /*
  222. ====================
  223. idSurface_Polytope::SetupCone
  224. ====================
  225. */
  226. void idSurface_Polytope::SetupCone( const idBounds &bounds, const int numSides ) {
  227. }
  228. /*
  229. ====================
  230. idSurface_Polytope::SplitPolytope
  231. ====================
  232. */
  233. int idSurface_Polytope::SplitPolytope( const idPlane &plane, const float epsilon, idSurface_Polytope **front, idSurface_Polytope **back ) const {
  234. int side, i, j, s, v0, v1, v2, edgeNum;
  235. idSurface *surface[2];
  236. idSurface_Polytope *polytopeSurfaces[2], *surf;
  237. int *onPlaneEdges[2];
  238. onPlaneEdges[0] = (int *) _alloca( indexes.Num() / 3 * sizeof( int ) );
  239. onPlaneEdges[1] = (int *) _alloca( indexes.Num() / 3 * sizeof( int ) );
  240. side = Split( plane, epsilon, &surface[0], &surface[1], onPlaneEdges[0], onPlaneEdges[1] );
  241. *front = polytopeSurfaces[0] = new (TAG_IDLIB_SURFACE) idSurface_Polytope;
  242. *back = polytopeSurfaces[1] = new (TAG_IDLIB_SURFACE) idSurface_Polytope;
  243. for ( s = 0; s < 2; s++ ) {
  244. if ( surface[s] ) {
  245. polytopeSurfaces[s] = new idSurface_Polytope( *surface[s] );
  246. delete surface[s];
  247. surface[s] = NULL;
  248. }
  249. }
  250. *front = polytopeSurfaces[0];
  251. *back = polytopeSurfaces[1];
  252. if ( side != SIDE_CROSS ) {
  253. return side;
  254. }
  255. // add triangles to close off the front and back polytope
  256. for ( s = 0; s < 2; s++ ) {
  257. surf = polytopeSurfaces[s];
  258. edgeNum = surf->edgeIndexes[onPlaneEdges[s][0]];
  259. v0 = surf->edges[abs(edgeNum)].verts[INT32_SIGNBITSET(edgeNum)];
  260. v1 = surf->edges[abs(edgeNum)].verts[INT32_SIGNBITNOTSET(edgeNum)];
  261. for ( i = 1; onPlaneEdges[s][i] >= 0; i++ ) {
  262. for ( j = i+1; onPlaneEdges[s][j] >= 0; j++ ) {
  263. edgeNum = surf->edgeIndexes[onPlaneEdges[s][j]];
  264. if ( v1 == surf->edges[abs(edgeNum)].verts[INT32_SIGNBITSET(edgeNum)] ) {
  265. v1 = surf->edges[abs(edgeNum)].verts[INT32_SIGNBITNOTSET(edgeNum)];
  266. SwapValues( onPlaneEdges[s][i], onPlaneEdges[s][j] );
  267. break;
  268. }
  269. }
  270. }
  271. for ( i = 2; onPlaneEdges[s][i] >= 0; i++ ) {
  272. edgeNum = surf->edgeIndexes[onPlaneEdges[s][i]];
  273. v1 = surf->edges[abs(edgeNum)].verts[INT32_SIGNBITNOTSET(edgeNum)];
  274. v2 = surf->edges[abs(edgeNum)].verts[INT32_SIGNBITSET(edgeNum)];
  275. surf->indexes.Append( v0 );
  276. surf->indexes.Append( v1 );
  277. surf->indexes.Append( v2 );
  278. }
  279. surf->GenerateEdgeIndexes();
  280. }
  281. return side;
  282. }