bounding_box.hpp 9.24 KB
Newer Older
Pierre Kraemer's avatar
Pierre Kraemer committed
1 2 3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2012, IGG Team, LSIIT, University of Strasbourg           *
Pierre Kraemer's avatar
Pierre Kraemer committed
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.unistra.fr/                                           *
Pierre Kraemer's avatar
Pierre Kraemer committed
21 22 23 24 25 26 27 28 29 30 31
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

namespace CGoGN
{

namespace Geom
{

template <typename VEC>
32 33 34 35
BoundingBox<VEC>::BoundingBox() :
	m_initialized(false),
	m_pMin(0),
	m_pMax(0)
Pierre Kraemer's avatar
Pierre Kraemer committed
36 37
{}

38 39 40 41 42 43
template <typename VEC>
BoundingBox<VEC>::BoundingBox(const VEC& p) :
	m_initialized(true),
	m_pMin(p),
	m_pMax(p)
{}
Pierre Kraemer's avatar
Pierre Kraemer committed
44 45 46 47

template <typename VEC>
VEC& BoundingBox<VEC>::min()
{
48
	assert(m_initialized || !"Bounding box not initialized");
Pierre Kraemer's avatar
Pierre Kraemer committed
49 50 51 52 53 54
	return m_pMin ;
}

template <typename VEC>
const VEC& BoundingBox<VEC>::min() const
{
55
	assert(m_initialized || !"Bounding box not initialized");
Pierre Kraemer's avatar
Pierre Kraemer committed
56 57 58 59 60 61
	return m_pMin ;
}

template <typename VEC>
VEC& BoundingBox<VEC>::max()
{
62
	assert(m_initialized || !"Bounding box not initialized");
Pierre Kraemer's avatar
Pierre Kraemer committed
63 64 65 66 67 68
	return m_pMax ;
}

template <typename VEC>
const VEC& BoundingBox<VEC>::max() const
{
69
	assert(m_initialized);
Pierre Kraemer's avatar
Pierre Kraemer committed
70 71 72 73 74 75
	return m_pMax ;
}

template <typename VEC>
typename VEC::DATA_TYPE BoundingBox<VEC>::size(unsigned int coord) const
{
76
	assert(m_initialized && coord < m_pMax.dimension()) ;
Pierre Kraemer's avatar
Pierre Kraemer committed
77 78 79
	return m_pMax[coord] - m_pMin[coord] ;
}

80 81 82
template <typename VEC>
typename VEC::DATA_TYPE BoundingBox<VEC>::maxSize() const
{
83
	assert(m_initialized || !"Bounding box not initialized");
84 85 86 87 88 89 90 91 92 93 94 95 96
	typename VEC::DATA_TYPE max = m_pMax[0] - m_pMin[0] ;
	for(unsigned int i = 1; i < m_pMax.dimension(); ++i)
	{
		typename VEC::DATA_TYPE size = m_pMax[i] - m_pMin[i] ;
		if(size > max)
			max = size ;
	}
	return max ;
}

template <typename VEC>
typename VEC::DATA_TYPE BoundingBox<VEC>::minSize() const
{
97
	assert(m_initialized || !"Bounding box not initialized");
98 99 100 101 102 103 104 105 106 107 108 109 110
	typename VEC::DATA_TYPE min = m_pMax[0] - m_pMin[0] ;
	for(unsigned int i = 1; i < m_pMax.dimension(); ++i)
	{
		typename VEC::DATA_TYPE size = m_pMax[i] - m_pMin[i] ;
		if(size < min)
			min = size ;
	}
	return min ;
}

template <typename VEC>
VEC BoundingBox<VEC>::diag() const
{
111
	assert(m_initialized || !"Bounding box not initialized");
112 113 114 115 116 117
	return m_pMax - m_pMin ;
}

template <typename VEC>
typename VEC::DATA_TYPE BoundingBox<VEC>::diagSize() const
{
118
	assert(m_initialized || !"Bounding box not initialized");
Sylvain Thery's avatar
Sylvain Thery committed
119
	return VEC::DATA_TYPE((m_pMax - m_pMin).norm());
120 121
}

Pierre Kraemer's avatar
Pierre Kraemer committed
122 123 124
template <typename VEC>
VEC BoundingBox<VEC>::center() const
{
125
	assert(m_initialized || !"Bounding box not initialized");
Pierre Kraemer's avatar
Pierre Kraemer committed
126 127 128 129
	VEC center = (m_pMax + m_pMin) / typename VEC::DATA_TYPE(2) ;
	return center ;
}

untereiner's avatar
ihm3  
untereiner committed
130 131 132 133 134 135
template <typename VEC>
bool BoundingBox<VEC>::isInitialized() const
{
	return m_initialized;
}

Pierre Kraemer's avatar
Pierre Kraemer committed
136 137 138 139
/**********************************************/
/*                 FUNCTIONS                  */
/**********************************************/

140 141 142
template <typename VEC>
void BoundingBox<VEC>::reset()
{
143
	m_initialized = false;
144 145
	m_pMin = VEC(0);
	m_pMax = VEC(0);
146 147
}

Pierre Kraemer's avatar
Pierre Kraemer committed
148 149 150
template <typename VEC>
void BoundingBox<VEC>::addPoint(const VEC& p)
{
151 152 153 154
	if(!m_initialized)
	{
		m_pMin = p ;
		m_pMax = p ;
155
		m_initialized = true ;
156 157
	}
	else
Pierre Kraemer's avatar
Pierre Kraemer committed
158
	{
159 160 161 162 163 164 165
		for(unsigned int i = 0; i < p.dimension(); ++i)
		{
			if(p[i] < m_pMin[i])
				m_pMin[i] = p[i] ;
			if(p[i] > m_pMax[i])
				m_pMax[i] = p[i] ;
		}
Pierre Kraemer's avatar
Pierre Kraemer committed
166 167 168 169 170 171
	}
}

template <typename VEC>
bool BoundingBox<VEC>::intersects(const BoundingBox<VEC>& bb)
{
172
	assert(m_initialized || !"Bounding box not initialized");
Pierre Kraemer's avatar
Pierre Kraemer committed
173 174
	VEC bbmin = bb.min() ;
	VEC bbmax = bb.max() ;
175
	for(unsigned int i = 0; i < bbmin.dimension(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
176 177 178 179 180 181 182 183 184 185 186 187
	{
		if(m_pMax[i] < bbmin[i])
			return false ;
		if(m_pMin[i] > bbmax[i])
			return false ;
	}
	return true ;
}

template <typename VEC>
void BoundingBox<VEC>::fusion(const BoundingBox<VEC>& bb)
{
188
	assert(m_initialized || !"Bounding box not initialized");
Pierre Kraemer's avatar
Pierre Kraemer committed
189 190
	VEC bbmin = bb.min() ;
	VEC bbmax = bb.max() ;
Pierre Kraemer's avatar
Pierre Kraemer committed
191
	for(unsigned int i = 0; i < bbmin.dimension(); ++i)
Pierre Kraemer's avatar
Pierre Kraemer committed
192 193 194 195 196 197 198 199
	{
		if(bbmin[i] < m_pMin[i])
			m_pMin[i] = bbmin[i] ;
		if(bbmax[i] > m_pMax[i])
			m_pMax[i] = bbmax[i] ;
	}
}

200 201 202
template <typename VEC>
bool BoundingBox<VEC>::contains(const VEC& p)
{
203
	assert(m_initialized || !"Bounding box not initialized");
204 205 206 207 208 209 210 211 212 213 214
	for(unsigned int i = 0; i < m_pMin.dimension(); ++i)
	{
		if(m_pMin[i] > p[i])
			return false ;
		if(p[i] > m_pMax[i])
			return false ;
	}

	return true;
}

215 216 217 218 219 220 221 222 223 224
template <typename VEC>
bool BoundingBox<VEC>::contains(const VEC& a, const VEC& b)
{
	assert(m_initialized || !"Bounding box not initialized");

#define LEFT 'l'
#define RIGHT 'r'
#define MIDDLE 'm'

	//Algorithm from Graphic Gems
225
	//modified to test segment
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
	VEC dir(b-a);		/*ray */

	bool inside = true;
	char quadrant[m_pMin.dimension()];

	VEC candidatePlane;

	/* Find candidate planes; this loop can be avoided if
	rays cast all from the eye(assume perpsective view) */
	for (unsigned int i=0; i< m_pMin.dimension(); i++)
	{
		if(a[i] < m_pMin[i])
		{
			quadrant[i] = LEFT;
			candidatePlane[i] = m_pMin[i];
			inside = false;
		}
		else if (a[i] > m_pMax[i])
		{
			quadrant[i] = RIGHT;
			candidatePlane[i] = m_pMax[i];
			inside = false;
		}
		else
		{
			quadrant[i] = MIDDLE;
		}
	}

	/* Ray origin inside bounding box */
	if(inside)
		return true;

	VEC maxT;
	VEC coord;			/* hit point */
	/* Calculate T distances to candidate planes */
	for(unsigned int i = 0; i < m_pMin.dimension(); i++)
	{
		if (quadrant[i] != MIDDLE && dir[i] !=0)
			maxT[i] = (candidatePlane[i]-a[i]) / dir[i];
		else
			maxT[i] = -1.;
	}

#undef LEFT
#undef RIGHT
#undef MIDDLE

	/* Get largest of the maxT's for final choice of intersection */
	unsigned int whichPlane = 0;
	for(unsigned int i = 1; i < m_pMin.dimension(); i++)
		if (maxT[whichPlane] < maxT[i])
			whichPlane = i;

	/* Check final candidate actually inside box */
	if (maxT[whichPlane] < 0.)
		return false;
	for (unsigned int i = 0; i < m_pMin.dimension(); i++)
	{
		if (whichPlane != i)
		{
			coord[i] = a[i] + maxT[whichPlane] *dir[i];
			if (coord[i] < m_pMin[i] || coord[i] > m_pMax[i])
				return false;
290 291
			else
				coord[i] = candidatePlane[i];
292 293 294
		}
	}

295
	return VEC(coord-b)*VEC(a-b); /* intersection in segment ?*/
296 297
}

298 299 300
template <typename VEC>
bool BoundingBox<VEC>::contains(const BoundingBox<VEC>& bb)
{
301
	assert(m_initialized || !"Bounding box not initialized");
302 303 304
	return this->contains(bb.min()) && this->contains(bb.max());
}

305
template <typename VEC>
306
void BoundingBox<VEC>::scale(typename VEC::DATA_TYPE size)
307 308
{
	assert(m_initialized || !"Bounding box not initialized");
309 310
	m_pMin *= size ;
	m_pMax *= size ;
311
}
312

313 314 315 316 317 318 319
template <typename VEC>
void BoundingBox<VEC>::centeredScale(typename VEC::DATA_TYPE size)
{
	VEC center = (m_pMin + m_pMax) / typename VEC::DATA_TYPE(2) ;
	m_pMin = ((m_pMin - center) * size) + center ;
	m_pMax = ((m_pMax - center) * size) + center ;
}
Pierre Kraemer's avatar
Pierre Kraemer committed
320

Sylvain Thery's avatar
Sylvain Thery committed
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


/// test if bb is intersected by a ray
template <typename VEC>
bool BoundingBox<VEC>::rayIntersect(const VEC& P, const VEC& V) const
{
	static float EPSILON = 0.000001f;

	if (fabs(V[2]) > EPSILON)
	{
		VEC Q = P + ((m_pMin[2] - P[2])/V[2])*V;
		if ((Q[0]<m_pMax[0]) && (Q[0]>m_pMin[0]) && (Q[1]<m_pMax[1]) && (Q[1]>m_pMin[1]))
			return true;
		Q = P + ((m_pMax[2] - P[2])/V[2])*V;
				if ((Q[0]<m_pMax[0]) && (Q[0]>m_pMin[0]) && (Q[1]<m_pMax[1]) && (Q[1]>m_pMin[1]))
					return true;
	}

	if (fabs(V[1]) > EPSILON)
	{
		VEC Q = P + ((m_pMin[1] - P[1])/V[1])*V;
		if ((Q[0]<m_pMax[0]) && (Q[0]>m_pMin[0]) && (Q[2]<m_pMax[2]) && (Q[2]>m_pMin[2]))
			return true;
		Q = P + ((m_pMax[1] - P[1])/V[1])*V;
				if ((Q[0]<m_pMax[0]) && (Q[0]>m_pMin[0]) && (Q[2]<m_pMax[2]) && (Q[2]>m_pMin[2]))
					return true;
	}


	if (fabs(V[0]) > EPSILON)
	{
		VEC Q = P + ((m_pMin[0] - P[0])/V[0])*V;
		if ((Q[1]<m_pMax[1]) && (Q[1]>m_pMin[1]) && (Q[2]<m_pMax[2]) && (Q[2]>m_pMin[2]))
			return true;
		Q = P + ((m_pMax[0] - P[0])/V[0])*V;
				if ((Q[1]<m_pMax[1]) && (Q[1]>m_pMin[1]) && (Q[2]<m_pMax[2]) && (Q[2]>m_pMin[2]))
					return true;
	}

	return false;
}




366
} // namespace Geom
Pierre Kraemer's avatar
Pierre Kraemer committed
367

368
} // namespace CGoGN