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*****************************************************************************/
39void 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*****************************************************************************/
93int 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*****************************************************************************/
248static 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*****************************************************************************/
263static 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*****************************************************************************/
278void 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*****************************************************************************/
362void 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*****************************************************************************/
377unsigned 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
407unsigned 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