1 /****************************************************************************** 2 3 @File PVRTMisc.cpp 4 5 @Title PVRTMisc 6 7 @Version 8 9 @Copyright Copyright (c) Imagination Technologies Limited. 10 11 @Platform ANSI compatible 12 13 @Description Miscellaneous functions used in 3D rendering. 14 15 ******************************************************************************/ 16 #include <string.h> 17 #include <stdlib.h> 18 #include <ctype.h> 19 #include <limits.h> 20 #include <math.h> 21 #include "PVRTGlobal.h" 22 #include "PVRTContext.h" 23 #include "PVRTFixedPoint.h" 24 #include "PVRTMatrix.h" 25 #include "PVRTMisc.h" 26 27 28 29 /*!*************************************************************************** 30 @Function PVRTMiscCalculateIntersectionLinePlane 31 @Input pfPlane Length 4 [A,B,C,D], values for plane 32 equation 33 @Input pv0 A point on the line 34 @Input pv1 Another point on the line 35 @Output pvIntersection The point of intersection 36 @Description Calculates coords of the intersection of a line and an 37 infinite plane 38 *****************************************************************************/ 39 void PVRTMiscCalculateIntersectionLinePlane( 40 PVRTVECTOR3 * const pvIntersection, 41 const VERTTYPE pfPlane[4], 42 const PVRTVECTOR3 * const pv0, 43 const PVRTVECTOR3 * const pv1) 44 { 45 PVRTVECTOR3 vD; 46 VERTTYPE fN, fD, fT; 47 48 /* Calculate vector from point0 to point1 */ 49 vD.x = pv1->x - pv0->x; 50 vD.y = pv1->y - pv0->y; 51 vD.z = pv1->z - pv0->z; 52 53 /* Denominator */ 54 fD = 55 VERTTYPEMUL(pfPlane[0], vD.x) + 56 VERTTYPEMUL(pfPlane[1], vD.y) + 57 VERTTYPEMUL(pfPlane[2], vD.z); 58 59 /* Numerator */ 60 fN = 61 VERTTYPEMUL(pfPlane[0], pv0->x) + 62 VERTTYPEMUL(pfPlane[1], pv0->y) + 63 VERTTYPEMUL(pfPlane[2], pv0->z) + 64 pfPlane[3]; 65 66 fT = VERTTYPEDIV(-fN, fD); 67 68 /* And for a finale, calculate the intersection coordinate */ 69 pvIntersection->x = pv0->x + VERTTYPEMUL(fT, vD.x); 70 pvIntersection->y = pv0->y + VERTTYPEMUL(fT, vD.y); 71 pvIntersection->z = pv0->z + VERTTYPEMUL(fT, vD.z); 72 } 73 74 75 /*!*************************************************************************** 76 @Function PVRTMiscCalculateInfinitePlane 77 @Input nStride Size of each vertex structure containing pfVtx 78 @Input pvPlane Length 4 [A,B,C,D], values for plane equation 79 @Input pmViewProjInv The inverse of the View Projection matrix 80 @Input pFrom Position of the camera 81 @Input fFar Far clipping distance 82 @Output pfVtx Position of the first of 3 floats to receive 83 the position of vertex 0; up to 5 vertex positions 84 will be written (5 is the maximum number of vertices 85 required to draw an infinite polygon clipped to screen 86 and far clip plane). 87 @Returns Number of vertices in the polygon fan (Can be 0, 3, 4 or 5) 88 @Description Calculates world-space coords of a screen-filling 89 representation of an infinite plane The resulting vertices run 90 counter-clockwise around the screen, and can be simply drawn using 91 non-indexed TRIANGLEFAN 92 *****************************************************************************/ 93 int PVRTMiscCalculateInfinitePlane( 94 VERTTYPE * const pfVtx, 95 const int nStride, 96 const PVRTVECTOR4 * const pvPlane, 97 const PVRTMATRIX * const pmViewProjInv, 98 const PVRTVECTOR3 * const pFrom, 99 const VERTTYPE fFar) 100 { 101 PVRTVECTOR3 pvWorld[5]; 102 PVRTVECTOR3 *pvPolyPtr; 103 unsigned int dwCount; 104 bool bClip; 105 int nVert; 106 VERTTYPE fDotProduct; 107 108 /* 109 Check whether the plane faces the camera 110 */ 111 fDotProduct = 112 VERTTYPEMUL((pFrom->x + VERTTYPEMUL(pvPlane->x, pvPlane->w)), pvPlane->x) + 113 VERTTYPEMUL((pFrom->y + VERTTYPEMUL(pvPlane->y, pvPlane->w)), pvPlane->y) + 114 VERTTYPEMUL((pFrom->z + VERTTYPEMUL(pvPlane->z, pvPlane->w)), pvPlane->z); 115 116 if(fDotProduct < 0) { 117 /* Camera is behind plane, hence it's not visible */ 118 return 0; 119 } 120 121 /* 122 Back transform front clipping plane into world space, 123 to give us a point on the line through each corner of the screen 124 (from the camera). 125 */ 126 127 /* x = -1.0f; y = -1.0f; z = 1.0f; w = 1.0f */ 128 pvWorld[0].x = VERTTYPEMUL((-pmViewProjInv->f[ 0] - pmViewProjInv->f[ 4] + pmViewProjInv->f[ 8] + pmViewProjInv->f[12]), fFar); 129 pvWorld[0].y = VERTTYPEMUL((-pmViewProjInv->f[ 1] - pmViewProjInv->f[ 5] + pmViewProjInv->f[ 9] + pmViewProjInv->f[13]), fFar); 130 pvWorld[0].z = VERTTYPEMUL((-pmViewProjInv->f[ 2] - pmViewProjInv->f[ 6] + pmViewProjInv->f[10] + pmViewProjInv->f[14]), fFar); 131 /* x = 1.0f, y = -1.0f, z = 1.0f; w = 1.0f */ 132 pvWorld[1].x = VERTTYPEMUL(( pmViewProjInv->f[ 0] - pmViewProjInv->f[ 4] + pmViewProjInv->f[ 8] + pmViewProjInv->f[12]), fFar); 133 pvWorld[1].y = VERTTYPEMUL(( pmViewProjInv->f[ 1] - pmViewProjInv->f[ 5] + pmViewProjInv->f[ 9] + pmViewProjInv->f[13]), fFar); 134 pvWorld[1].z = VERTTYPEMUL(( pmViewProjInv->f[ 2] - pmViewProjInv->f[ 6] + pmViewProjInv->f[10] + pmViewProjInv->f[14]), fFar); 135 /* x = 1.0f, y = 1.0f, z = 1.0f; w = 1.0f */ 136 pvWorld[2].x = VERTTYPEMUL(( pmViewProjInv->f[ 0] + pmViewProjInv->f[ 4] + pmViewProjInv->f[ 8] + pmViewProjInv->f[12]), fFar); 137 pvWorld[2].y = VERTTYPEMUL(( pmViewProjInv->f[ 1] + pmViewProjInv->f[ 5] + pmViewProjInv->f[ 9] + pmViewProjInv->f[13]), fFar); 138 pvWorld[2].z = VERTTYPEMUL(( pmViewProjInv->f[ 2] + pmViewProjInv->f[ 6] + pmViewProjInv->f[10] + pmViewProjInv->f[14]), fFar); 139 /* x = -1.0f, y = 1.0f, z = 1.0f; w = 1.0f */ 140 pvWorld[3].x = VERTTYPEMUL((-pmViewProjInv->f[ 0] + pmViewProjInv->f[ 4] + pmViewProjInv->f[ 8] + pmViewProjInv->f[12]), fFar); 141 pvWorld[3].y = VERTTYPEMUL((-pmViewProjInv->f[ 1] + pmViewProjInv->f[ 5] + pmViewProjInv->f[ 9] + pmViewProjInv->f[13]), fFar); 142 pvWorld[3].z = VERTTYPEMUL((-pmViewProjInv->f[ 2] + pmViewProjInv->f[ 6] + pmViewProjInv->f[10] + pmViewProjInv->f[14]), fFar); 143 144 /* We need to do a closed loop of the screen vertices, so copy the first vertex into the last */ 145 pvWorld[4] = pvWorld[0]; 146 147 /* 148 Now build a pre-clipped polygon 149 */ 150 151 /* Lets get ready to loop */ 152 dwCount = 0; 153 bClip = false; 154 pvPolyPtr = (PVRTVECTOR3*)pfVtx; 155 156 nVert = 5; 157 while(nVert) 158 { 159 nVert--; 160 161 /* 162 Check which side of the Plane this corner of the far clipping 163 plane is on. [A,B,C] of plane equation is the plane normal, D is 164 distance from origin; hence [pvPlane->x * -pvPlane->w, 165 pvPlane->y * -pvPlane->w, 166 pvPlane->z * -pvPlane->w] 167 is a point on the plane 168 */ 169 fDotProduct = 170 VERTTYPEMUL((pvWorld[nVert].x + VERTTYPEMUL(pvPlane->x, pvPlane->w)), pvPlane->x) + 171 VERTTYPEMUL((pvWorld[nVert].y + VERTTYPEMUL(pvPlane->y, pvPlane->w)), pvPlane->y) + 172 VERTTYPEMUL((pvWorld[nVert].z + VERTTYPEMUL(pvPlane->z, pvPlane->w)), pvPlane->z); 173 174 if(fDotProduct < 0) 175 { 176 /* 177 Behind plane; Vertex does NOT need clipping 178 */ 179 if(bClip == true) 180 { 181 /* Clipping finished */ 182 bClip = false; 183 184 /* 185 We've been clipping, so we need to add an additional 186 point on the line to this point, where clipping was 187 stopped. 188 */ 189 PVRTMiscCalculateIntersectionLinePlane(pvPolyPtr, &pvPlane->x, &pvWorld[nVert+1], &pvWorld[nVert]); 190 pvPolyPtr = (PVRTVECTOR3*)((char*)pvPolyPtr + nStride); 191 dwCount++; 192 } 193 194 if(!nVert) 195 { 196 /* Abort, abort: we've closed the loop with the clipped point */ 197 break; 198 } 199 200 /* Add the current point */ 201 PVRTMiscCalculateIntersectionLinePlane(pvPolyPtr, &pvPlane->x, pFrom, &pvWorld[nVert]); 202 pvPolyPtr = (PVRTVECTOR3*)((char*)pvPolyPtr + nStride); 203 dwCount++; 204 } 205 else 206 { 207 /* 208 Before plane; Vertex DOES need clipping 209 */ 210 if(bClip == true) 211 { 212 /* Already in clipping, skip point */ 213 continue; 214 } 215 216 /* Clipping initiated */ 217 bClip = true; 218 219 /* Don't bother with entry point on first vertex; will take care of it on last vertex (which is a repeat of first vertex) */ 220 if(nVert != 4) 221 { 222 /* We need to add an additional point on the line to this point, where clipping was started */ 223 PVRTMiscCalculateIntersectionLinePlane(pvPolyPtr, &pvPlane->x, &pvWorld[nVert+1], &pvWorld[nVert]); 224 pvPolyPtr = (PVRTVECTOR3*)((char*)pvPolyPtr + nStride); 225 dwCount++; 226 } 227 } 228 } 229 230 /* Valid vertex counts are 0, 3, 4, 5 */ 231 _ASSERT(dwCount <= 5); 232 _ASSERT(dwCount != 1); 233 _ASSERT(dwCount != 2); 234 235 return dwCount; 236 } 237 238 239 /*!*************************************************************************** 240 @Function SetVertex 241 @Modified Vertices 242 @Input index 243 @Input x 244 @Input y 245 @Input z 246 @Description Writes a vertex in a vertex array 247 *****************************************************************************/ 248 static void SetVertex(VERTTYPE** Vertices, int index, VERTTYPE x, VERTTYPE y, VERTTYPE z) 249 { 250 (*Vertices)[index*3+0] = x; 251 (*Vertices)[index*3+1] = y; 252 (*Vertices)[index*3+2] = z; 253 } 254 255 /*!*************************************************************************** 256 @Function SetUV 257 @Modified UVs 258 @Input index 259 @Input u 260 @Input v 261 @Description Writes a texture coordinate in a texture coordinate array 262 *****************************************************************************/ 263 static void SetUV(VERTTYPE** UVs, int index, VERTTYPE u, VERTTYPE v) 264 { 265 (*UVs)[index*2+0] = u; 266 (*UVs)[index*2+1] = v; 267 } 268 269 /*!*************************************************************************** 270 @Function PVRTCreateSkybox 271 @Input scale Scale the skybox 272 @Input adjustUV Adjust or not UVs for PVRT compression 273 @Input textureSize Texture size in pixels 274 @Output Vertices Array of vertices 275 @Output UVs Array of UVs 276 @Description Creates the vertices and texture coordinates for a skybox 277 *****************************************************************************/ 278 void PVRTCreateSkybox(float scale, bool adjustUV, int textureSize, VERTTYPE** Vertices, VERTTYPE** UVs) 279 { 280 *Vertices = new VERTTYPE[24*3]; 281 *UVs = new VERTTYPE[24*2]; 282 283 VERTTYPE unit = f2vt(1); 284 VERTTYPE a0 = 0, a1 = unit; 285 286 if (adjustUV) 287 { 288 VERTTYPE oneover = f2vt(1.0f / textureSize); 289 a0 = VERTTYPEMUL(f2vt(4.0f), oneover); 290 a1 = unit - a0; 291 } 292 293 // Front 294 SetVertex(Vertices, 0, -unit, +unit, -unit); 295 SetVertex(Vertices, 1, +unit, +unit, -unit); 296 SetVertex(Vertices, 2, -unit, -unit, -unit); 297 SetVertex(Vertices, 3, +unit, -unit, -unit); 298 SetUV(UVs, 0, a0, a1); 299 SetUV(UVs, 1, a1, a1); 300 SetUV(UVs, 2, a0, a0); 301 SetUV(UVs, 3, a1, a0); 302 303 // Right 304 SetVertex(Vertices, 4, +unit, +unit, -unit); 305 SetVertex(Vertices, 5, +unit, +unit, +unit); 306 SetVertex(Vertices, 6, +unit, -unit, -unit); 307 SetVertex(Vertices, 7, +unit, -unit, +unit); 308 SetUV(UVs, 4, a0, a1); 309 SetUV(UVs, 5, a1, a1); 310 SetUV(UVs, 6, a0, a0); 311 SetUV(UVs, 7, a1, a0); 312 313 // Back 314 SetVertex(Vertices, 8 , +unit, +unit, +unit); 315 SetVertex(Vertices, 9 , -unit, +unit, +unit); 316 SetVertex(Vertices, 10, +unit, -unit, +unit); 317 SetVertex(Vertices, 11, -unit, -unit, +unit); 318 SetUV(UVs, 8 , a0, a1); 319 SetUV(UVs, 9 , a1, a1); 320 SetUV(UVs, 10, a0, a0); 321 SetUV(UVs, 11, a1, a0); 322 323 // Left 324 SetVertex(Vertices, 12, -unit, +unit, +unit); 325 SetVertex(Vertices, 13, -unit, +unit, -unit); 326 SetVertex(Vertices, 14, -unit, -unit, +unit); 327 SetVertex(Vertices, 15, -unit, -unit, -unit); 328 SetUV(UVs, 12, a0, a1); 329 SetUV(UVs, 13, a1, a1); 330 SetUV(UVs, 14, a0, a0); 331 SetUV(UVs, 15, a1, a0); 332 333 // Top 334 SetVertex(Vertices, 16, -unit, +unit, +unit); 335 SetVertex(Vertices, 17, +unit, +unit, +unit); 336 SetVertex(Vertices, 18, -unit, +unit, -unit); 337 SetVertex(Vertices, 19, +unit, +unit, -unit); 338 SetUV(UVs, 16, a0, a1); 339 SetUV(UVs, 17, a1, a1); 340 SetUV(UVs, 18, a0, a0); 341 SetUV(UVs, 19, a1, a0); 342 343 // Bottom 344 SetVertex(Vertices, 20, -unit, -unit, -unit); 345 SetVertex(Vertices, 21, +unit, -unit, -unit); 346 SetVertex(Vertices, 22, -unit, -unit, +unit); 347 SetVertex(Vertices, 23, +unit, -unit, +unit); 348 SetUV(UVs, 20, a0, a1); 349 SetUV(UVs, 21, a1, a1); 350 SetUV(UVs, 22, a0, a0); 351 SetUV(UVs, 23, a1, a0); 352 353 for (int i=0; i<24*3; i++) (*Vertices)[i] = VERTTYPEMUL((*Vertices)[i], f2vt(scale)); 354 } 355 356 /*!*************************************************************************** 357 @Function PVRTDestroySkybox 358 @Input Vertices Vertices array to destroy 359 @Input UVs UVs array to destroy 360 @Description Destroy the memory allocated for a skybox 361 *****************************************************************************/ 362 void PVRTDestroySkybox(VERTTYPE* Vertices, VERTTYPE* UVs) 363 { 364 delete [] Vertices; 365 delete [] UVs; 366 } 367 368 /*!*************************************************************************** 369 @Function PVRTGetPOTHigher 370 @Input uiOriginalValue Base value 371 @Input iTimesHigher Multiplier 372 @Description When iTimesHigher is one, this function will return the closest 373 power-of-two value above the base value. 374 For every increment beyond one for the iTimesHigher value, 375 the next highest power-of-two value will be calculated. 376 *****************************************************************************/ 377 unsigned int PVRTGetPOTHigher(unsigned int uiOriginalValue, int iTimesHigher) 378 { 379 if(uiOriginalValue == 0 || iTimesHigher < 0) 380 { 381 return 0; 382 } 383 384 unsigned int uiSize = 1; 385 while (uiSize < uiOriginalValue) uiSize *= 2; 386 387 // Keep increasing the POT value until the iTimesHigher value has been met 388 for(int i = 1 ; i < iTimesHigher; ++i) 389 { 390 uiSize *= 2; 391 } 392 393 return uiSize; 394 } 395 396 /*!*************************************************************************** 397 @Function PVRTGetPOTLower 398 @Input uiOriginalValue Base value 399 @Input iTimesLower Multiplier 400 @Description When iTimesLower is one, this function will return the closest 401 power-of-two value below the base value. 402 For every increment beyond one for the iTimesLower value, 403 the next lowest power-of-two value will be calculated. The lowest 404 value that can be reached is 1. 405 *****************************************************************************/ 406 // NOTE: This function should be optimised 407 unsigned int PVRTGetPOTLower(unsigned int uiOriginalValue, int iTimesLower) 408 { 409 if(uiOriginalValue == 0 || iTimesLower < 0) 410 { 411 return 0; 412 } 413 unsigned int uiSize = PVRTGetPOTHigher(uiOriginalValue,1); 414 uiSize >>= 1;//uiSize /=2; 415 416 for(int i = 1; i < iTimesLower; ++i) 417 { 418 uiSize >>= 1;//uiSize /=2; 419 if(uiSize == 1) 420 { 421 // Lowest possible value has been reached, so break 422 break; 423 } 424 } 425 return uiSize; 426 } 427 428 429 430 /***************************************************************************** 431 End of file (PVRTMisc.cpp) 432 *****************************************************************************/ 433 434
