summaryrefslogtreecommitdiffhomepage
path: root/Opcode/Ice/IceAABB.cpp
blob: 149211c1b2d9ee69cc39b349e1d2d774eeeb4e07 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Contains AABB-related code.
 *	\file		IceAABB.cpp
 *	\author		Pierre Terdiman
 *	\date		January, 29, 2000
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	AABB class.
 *	\class		AABB
 *	\author		Pierre Terdiman
 *	\version	1.0
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Precompiled Header
#include "Stdafx.h"

using namespace IceMaths;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the sum of two AABBs.
 *	\param		aabb	[in] the other AABB
 *	\return		Self-Reference
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
AABB& AABB::Add(const AABB& aabb)
{
	// Compute new min & max values
	IcePoint Min;	GetMin(Min);
	IcePoint Tmp;	aabb.GetMin(Tmp);
	Min.Min(Tmp);

	IcePoint Max;	GetMax(Max);
	aabb.GetMax(Tmp);
	Max.Max(Tmp);

	// Update this
	SetMinMax(Min, Max);
	return *this;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Makes a cube from the AABB.
 *	\param		cube	[out] the cube AABB
 *	\return		cube edge length
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
float AABB::MakeCube(AABB& cube) const
{
	IcePoint Ext;	GetExtents(Ext);
	float Max = Ext.Max();

	IcePoint Cnt;	GetCenter(Cnt);
	cube.SetCenterExtents(Cnt, IcePoint(Max, Max, Max));
	return Max;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Makes a sphere from the AABB.
 *	\param		sphere	[out] sphere containing the AABB
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void AABB::MakeSphere(Sphere& sphere) const
{
	GetExtents(sphere.mCenter);
	sphere.mRadius = sphere.mCenter.Magnitude() * 1.00001f;	// To make sure sphere::Contains(*this)	succeeds
	GetCenter(sphere.mCenter);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Checks a box is inside another box.
 *	\param		box		[in] the other AABB
 *	\return		true if current box is inside input box
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool AABB::IsInside(const AABB& box) const
{
	if(box.GetMin(0)>GetMin(0))	return false;
	if(box.GetMin(1)>GetMin(1))	return false;
	if(box.GetMin(2)>GetMin(2))	return false;
	if(box.GetMax(0)<GetMax(0))	return false;
	if(box.GetMax(1)<GetMax(1))	return false;
	if(box.GetMax(2)<GetMax(2))	return false;
	return true;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the AABB planes.
 *	\param		planes	[out] 6 planes surrounding the box
 *	\return		true if success
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool AABB::ComputePlanes(Plane* planes)	const
{
	// Checkings
	if(!planes)	return false;

	IcePoint Center, Extents;
	GetCenter(Center);
	GetExtents(Extents);

	// Writes normals
	planes[0].n = IcePoint(1.0f, 0.0f, 0.0f);
	planes[1].n = IcePoint(-1.0f, 0.0f, 0.0f);
	planes[2].n = IcePoint(0.0f, 1.0f, 0.0f);
	planes[3].n = IcePoint(0.0f, -1.0f, 0.0f);
	planes[4].n = IcePoint(0.0f, 0.0f, 1.0f);
	planes[5].n = IcePoint(0.0f, 0.0f, -1.0f);

	// Compute a point on each plane
	IcePoint p0 = IcePoint(Center.x+Extents.x, Center.y, Center.z);
	IcePoint p1 = IcePoint(Center.x-Extents.x, Center.y, Center.z);
	IcePoint p2 = IcePoint(Center.x, Center.y+Extents.y, Center.z);
	IcePoint p3 = IcePoint(Center.x, Center.y-Extents.y, Center.z);
	IcePoint p4 = IcePoint(Center.x, Center.y, Center.z+Extents.z);
	IcePoint p5 = IcePoint(Center.x, Center.y, Center.z-Extents.z);

	// Compute d
	planes[0].d = -(planes[0].n|p0);
	planes[1].d = -(planes[1].n|p1);
	planes[2].d = -(planes[2].n|p2);
	planes[3].d = -(planes[3].n|p3);
	planes[4].d = -(planes[4].n|p4);
	planes[5].d = -(planes[5].n|p5);

	return true;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Computes the aabb points.
 *	\param		pts	[out] 8 box points
 *	\return		true if success
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool AABB::ComputePoints(IcePoint* pts)	const
{
	// Checkings
	if(!pts)	return false;

	// Get box corners
	IcePoint min;	GetMin(min);
	IcePoint max;	GetMax(max);

	//     7+------+6			0 = ---
	//     /|     /|			1 = +--
	//    / |    / |			2 = ++-
	//   / 4+---/--+5			3 = -+-
	// 3+------+2 /    y   z	4 = --+
	//  | /    | /     |  /		5 = +-+
	//  |/     |/      |/		6 = +++
	// 0+------+1      *---x	7 = -++

	// Generate 8 corners of the bbox
	pts[0] = IcePoint(min.x, min.y, min.z);
	pts[1] = IcePoint(max.x, min.y, min.z);
	pts[2] = IcePoint(max.x, max.y, min.z);
	pts[3] = IcePoint(min.x, max.y, min.z);
	pts[4] = IcePoint(min.x, min.y, max.z);
	pts[5] = IcePoint(max.x, min.y, max.z);
	pts[6] = IcePoint(max.x, max.y, max.z);
	pts[7] = IcePoint(min.x, max.y, max.z);

	return true;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Gets vertex normals.
 *	\param		pts	[out] 8 box points
 *	\return		true if success
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const IcePoint* AABB::GetVertexNormals()	const
{
	static float VertexNormals[] = 
	{
		-INVSQRT3,	-INVSQRT3,	-INVSQRT3,
		INVSQRT3,	-INVSQRT3,	-INVSQRT3,
		INVSQRT3,	INVSQRT3,	-INVSQRT3,
		-INVSQRT3,	INVSQRT3,	-INVSQRT3,
		-INVSQRT3,	-INVSQRT3,	INVSQRT3,
		INVSQRT3,	-INVSQRT3,	INVSQRT3,
		INVSQRT3,	INVSQRT3,	INVSQRT3,
		-INVSQRT3,	INVSQRT3,	INVSQRT3
	};
	return (const IcePoint*)VertexNormals;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Returns edges.
 *	\return		24 indices (12 edges) indexing the list returned by ComputePoints()
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const udword* AABB::GetEdges() const
{
	static udword Indices[] = {
	0, 1,	1, 2,	2, 3,	3, 0,
	7, 6,	6, 5,	5, 4,	4, 7,
	1, 5,	6, 2,
	3, 7,	4, 0
	};
	return Indices;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
 *	Returns edge normals.
 *	\return		edge normals in local space
 */
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const IcePoint* AABB::GetEdgeNormals() const
{
	static float EdgeNormals[] = 
	{
		0,			-INVSQRT2,	-INVSQRT2,	// 0-1
		INVSQRT2,	0,			-INVSQRT2,	// 1-2
		0,			INVSQRT2,	-INVSQRT2,	// 2-3
		-INVSQRT2,	0,			-INVSQRT2,	// 3-0

		0,			INVSQRT2,	INVSQRT2,	// 7-6
		INVSQRT2,	0,			INVSQRT2,	// 6-5
		0,			-INVSQRT2,	INVSQRT2,	// 5-4
		-INVSQRT2,	0,			INVSQRT2,	// 4-7

		INVSQRT2,	-INVSQRT2,	0,			// 1-5
		INVSQRT2,	INVSQRT2,	0,			// 6-2
		-INVSQRT2,	INVSQRT2,	0,			// 3-7
		-INVSQRT2,	-INVSQRT2,	0			// 4-0
	};
	return (const IcePoint*)EdgeNormals;
}

// ===========================================================================
//  (C) 1996-98 Vienna University of Technology
// ===========================================================================
//  NAME:       bboxarea
//  TYPE:       c++ code
//  PROJECT:    Bounding Box Area
//  CONTENT:    Computes area of 2D projection of 3D oriented bounding box
//  VERSION:    1.0
// ===========================================================================
//  AUTHORS:    ds      Dieter Schmalstieg
//              ep      Erik Pojar
// ===========================================================================
//  HISTORY:
//
//  19-sep-99 15:23:03  ds      last modification
//  01-dec-98 15:23:03  ep      created
// ===========================================================================

//----------------------------------------------------------------------------
// SAMPLE CODE STARTS HERE
//----------------------------------------------------------------------------

// NOTE: This sample program requires OPEN INVENTOR!

//indexlist: this table stores the 64 possible cases of classification of
//the eyepoint with respect to the 6 defining planes of the bbox (2^6=64)
//only 26 (3^3-1, where 1 is "inside" cube) of these cases are valid.
//the first 6 numbers in each row are the indices of the bbox vertices that
//form the outline of which we want to compute the area (counterclockwise
//ordering), the 7th entry means the number of vertices in the outline.
//there are 6 cases with a single face and and a 4-vertex outline, and
//20 cases with 2 or 3 faces and a 6-vertex outline. a value of 0 indicates
//an invalid case.


// Original list was made of 7 items, I added an 8th element:
// - to padd on a cache line
// - to repeat the first entry to avoid modulos
//
// I also replaced original ints with sbytes.

static const sbyte gIndexList[64][8] =
{
    {-1,-1,-1,-1,-1,-1,-1,   0}, // 0 inside
    { 0, 4, 7, 3, 0,-1,-1,   4}, // 1 left
    { 1, 2, 6, 5, 1,-1,-1,   4}, // 2 right
    {-1,-1,-1,-1,-1,-1,-1,   0}, // 3 -
    { 0, 1, 5, 4, 0,-1,-1,   4}, // 4 bottom
    { 0, 1, 5, 4, 7, 3, 0,   6}, // 5 bottom, left
    { 0, 1, 2, 6, 5, 4, 0,   6}, // 6 bottom, right
    {-1,-1,-1,-1,-1,-1,-1,   0}, // 7 -
    { 2, 3, 7, 6, 2,-1,-1,   4}, // 8 top
    { 0, 4, 7, 6, 2, 3, 0,   6}, // 9 top, left
    { 1, 2, 3, 7, 6, 5, 1,   6}, //10 top, right
    {-1,-1,-1,-1,-1,-1,-1,   0}, //11 -
    {-1,-1,-1,-1,-1,-1,-1,   0}, //12 -
    {-1,-1,-1,-1,-1,-1,-1,   0}, //13 -
    {-1,-1,-1,-1,-1,-1,-1,   0}, //14 -
    {-1,-1,-1,-1,-1,-1,-1,   0}, //15 -
    { 0, 3, 2, 1, 0,-1,-1,   4}, //16 front
    { 0, 4, 7, 3, 2, 1, 0,   6}, //17 front, left
    { 0, 3, 2, 6, 5, 1, 0,   6}, //18 front, right
    {-1,-1,-1,-1,-1,-1,-1,   0}, //19 -
    { 0, 3, 2, 1, 5, 4, 0,   6}, //20 front, bottom
    { 1, 5, 4, 7, 3, 2, 1,   6}, //21 front, bottom, left
    { 0, 3, 2, 6, 5, 4, 0,   6}, //22 front, bottom, right
    {-1,-1,-1,-1,-1,-1,-1,   0}, //23 -
    { 0, 3, 7, 6, 2, 1, 0,   6}, //24 front, top
    { 0, 4, 7, 6, 2, 1, 0,   6}, //25 front, top, left
    { 0, 3, 7, 6, 5, 1, 0,   6}, //26 front, top, right
    {-1,-1,-1,-1,-1,-1,-1,   0}, //27 -
    {-1,-1,-1,-1,-1,-1,-1,   0}, //28 -
    {-1,-1,-1,-1,-1,-1,-1,   0}, //29 -
    {-1,-1,-1,-1,-1,-1,-1,   0}, //30 -
    {-1,-1,-1,-1,-1,-1,-1,   0}, //31 -
    { 4, 5, 6, 7, 4,-1,-1,   4}, //32 back
    { 0, 4, 5, 6, 7, 3, 0,   6}, //33 back, left
    { 1, 2, 6, 7, 4, 5, 1,   6}, //34 back, right
    {-1,-1,-1,-1,-1,-1,-1,   0}, //35 -
    { 0, 1, 5, 6, 7, 4, 0,   6}, //36 back, bottom
    { 0, 1, 5, 6, 7, 3, 0,   6}, //37 back, bottom, left
    { 0, 1, 2, 6, 7, 4, 0,   6}, //38 back, bottom, right
    {-1,-1,-1,-1,-1,-1,-1,   0}, //39 -
    { 2, 3, 7, 4, 5, 6, 2,   6}, //40 back, top
    { 0, 4, 5, 6, 2, 3, 0,   6}, //41 back, top, left
    { 1, 2, 3, 7, 4, 5, 1,   6}, //42 back, top, right
    {-1,-1,-1,-1,-1,-1,-1,   0}, //43 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //44 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //45 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //46 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //47 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //48 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //49 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //50 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //51 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //52 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //53 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //54 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //55 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //56 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //57 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //58 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //59 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //60 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //61 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}, //62 invalid
    {-1,-1,-1,-1,-1,-1,-1,   0}  //63 invalid
};

const sbyte* AABB::ComputeOutline(const IcePoint& local_eye, sdword& num)	const
{
	// Get box corners
	IcePoint min;	GetMin(min);
	IcePoint max;	GetMax(max);

	// Compute 6-bit code to classify eye with respect to the 6 defining planes of the bbox
	int pos = ((local_eye.x < min.x) ?  1 : 0)	// 1 = left
			+ ((local_eye.x > max.x) ?  2 : 0)	// 2 = right
			+ ((local_eye.y < min.y) ?  4 : 0)	// 4 = bottom
			+ ((local_eye.y > max.y) ?  8 : 0)	// 8 = top
			+ ((local_eye.z < min.z) ? 16 : 0)	// 16 = front
			+ ((local_eye.z > max.z) ? 32 : 0);	// 32 = back

	// Look up number of vertices in outline
	num = (sdword)gIndexList[pos][7];
	// Zero indicates invalid case
	if(!num) return null;

	return &gIndexList[pos][0];
}

// calculateBoxArea: computes the screen-projected 2D area of an oriented 3D bounding box

//const IcePoint&		eye,		//eye point (in bbox object coordinates)
//const AABB&			box,		//3d bbox
//const Matrix4x4&	mat,		//free transformation for bbox
//float width, float height, int& num)
float AABB::ComputeBoxArea(const IcePoint& eye, const Matrix4x4& mat, float width, float height, sdword& num)	const
{
	const sbyte* Outline = ComputeOutline(eye, num);
	if(!Outline)	return -1.0f;

	// Compute box vertices
	IcePoint vertexBox[8], dst[8];
	ComputePoints(vertexBox);

	// Transform all outline corners into 2D screen space
	for(sdword i=0;i<num;i++)
	{
		HPoint Projected;
		vertexBox[Outline[i]].ProjectToScreen(width, height, mat, Projected);
		dst[i] = Projected;
	}

	float Sum = (dst[num-1][0] - dst[0][0]) * (dst[num-1][1] + dst[0][1]);

	for(int i=0; i<num-1; i++)
		Sum += (dst[i][0] - dst[i+1][0]) * (dst[i][1] + dst[i+1][1]);

	return Sum * 0.5f;	//return computed value corrected by 0.5
}