triangulation.hpp 6.89 KB
Newer Older
Sylvain Thery's avatar
Sylvain Thery 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           *
Sylvain Thery's avatar
Sylvain Thery 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/                                           *
Sylvain Thery's avatar
Sylvain Thery committed
21 22 23 24 25 26
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

namespace CGoGN
{
27

Sylvain Thery's avatar
Sylvain Thery committed
28 29
namespace Algo
{
30

31 32 33
namespace Surface
{

Sylvain Thery's avatar
Sylvain Thery committed
34 35 36 37 38 39
namespace Modelisation
{

template<typename PFP>
bool EarTriangulation<PFP>::inTriangle(const typename PFP::VEC3& P, const typename PFP::VEC3& normal, const typename PFP::VEC3& Ta,  const typename PFP::VEC3& Tb, const typename PFP::VEC3& Tc)
{
40 41
	typedef typename PFP::VEC3 VEC3 ;
	typedef typename VEC3::DATA_TYPE T ;
Sylvain Thery's avatar
Sylvain Thery committed
42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

	if (Geom::tripleProduct(P-Ta, (Tb-Ta), normal) >= T(0))
		return false;

	if (Geom::tripleProduct(P-Tb, (Tc-Tb), normal) >= T(0))
		return false;

	if (Geom::tripleProduct(P-Tc, (Ta-Tc), normal) >= T(0))
		return false;

	return true;
}

template<typename PFP>
void EarTriangulation<PFP>::recompute2Ears( Dart d, const typename PFP::VEC3& normalPoly, bool convex)
{
58 59
	typedef typename PFP::VEC3 VEC3 ;

Sylvain Thery's avatar
Sylvain Thery committed
60 61 62 63
	Dart d2 = m_map.phi_1(d);
	Dart d_p = m_map.phi_1(d2);
	Dart d_n = m_map.phi1(d);

64 65 66 67
	const VEC3& Ta = m_position[d2];
	const VEC3& Tb = m_position[d];
	const VEC3& Tc = m_position[d_p];
	const VEC3& Td = m_position[d_n];
Sylvain Thery's avatar
Sylvain Thery committed
68 69

	// compute angle
70 71 72
	VEC3 v1= Tb - Ta;
	VEC3 v2= Tc - Ta;
	VEC3 v3= Td - Tb;
Sylvain Thery's avatar
Sylvain Thery committed
73 74 75 76 77 78 79 80 81 82 83 84

	v1.normalize();
	v2.normalize();
	v3.normalize();

//	float dotpr1 = 1.0f - (v1*v2);
//	float dotpr2 = 1.0f + (v1*v3);
	float dotpr1 = acos(v1*v2) / (M_PI/2.0f);
	float dotpr2 = acos(-(v1*v3)) / (M_PI/2.0f);

	if (!convex)	// if convex no need to test if vertex is an ear (yes)
	{
85 86
		VEC3 nv1 = v1^v2;
		VEC3 nv2 = v1^v3;
Sylvain Thery's avatar
Sylvain Thery committed
87 88 89 90 91 92 93 94 95 96

		if (nv1*normalPoly < 0.0)
			dotpr1 = 10.0f - dotpr1;// not an ears  (concave)
		if (nv2*normalPoly < 0.0)
			dotpr2 = 10.0f - dotpr2;// not an ears  (concave)

		bool finished = (dotpr1>=5.0f) && (dotpr2>=5.0f);
		for (typename VPMS::reverse_iterator it = m_ears.rbegin(); (!finished)&&(it != m_ears.rend())&&(it->angle > 5.0f); ++it)
		{
			Dart dx = it->dart;
97
			const VEC3& P = m_position[dx];
Sylvain Thery's avatar
Sylvain Thery committed
98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

			if ((dotpr1 < 5.0f) && (d != d_p))
				if (inTriangle(P, normalPoly,Tb,Tc,Ta))
					dotpr1 = 5.0f;// not an ears !

			if ((dotpr2 < 5.0f) && (d != d_n) )
				if (inTriangle(P, normalPoly,Td,Ta,Tb))
					dotpr2 = 5.0f;// not an ears !

			finished = ((dotpr1 >= 5.0f)&&(dotpr2 >= 5.0f));
		}
	}

	float length = (Tb-Tc).norm2();
	m_dartEars[d2] = m_ears.insert(VertexPoly(d2,dotpr1,length));

	length = (Td-Ta).norm2();
	m_dartEars[d] = m_ears.insert(VertexPoly(d,dotpr2,length));
}

template<typename PFP>
float EarTriangulation<PFP>::computeEarInit(Dart d, const typename PFP::VEC3& normalPoly, float& val)
{
121 122
	typedef typename PFP::VEC3 VEC3 ;

Sylvain Thery's avatar
Sylvain Thery committed
123 124 125
	Dart e =  m_map.phi1(d);
	Dart f =  m_map.phi1(e);

126 127 128
	const VEC3& Ta = m_position[e];
	const VEC3& Tb = m_position[f];
	const VEC3& Tc = m_position[d];
Sylvain Thery's avatar
Sylvain Thery committed
129

130 131
	VEC3 v1 = Tc-Ta;
	VEC3 v2 = Tb-Ta;
Sylvain Thery's avatar
Sylvain Thery committed
132 133 134 135 136 137
	v1.normalize();
	v2.normalize();

//	val = 1.0f - (v1*v2);
	val = acos(v1*v2) / (M_PI/2.0f);

138
	VEC3 vn = v1^v2;
Sylvain Thery's avatar
Sylvain Thery committed
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160
	if (vn*normalPoly > 0.0f)
		val = 10.0f - val; 		// not an ears  (concave, store at the end for optimized use for intersections)

	if (val>5.0f)
		return 0.0f;

	//INTERSECTION
	f =  m_map.phi1(f);
	while (f != d)
	{
		if (inTriangle(m_position[f], normalPoly,Tb,Tc,Ta))
		{
			val = 5.0f;
			return 0.0f;
		}
		f =  m_map.phi1(f);
	}

	return (Tb-Tc).norm2();
}

template<typename PFP>
161 162
//void EarTriangulation<PFP>::trianguleFace(Dart d, DartMarker& mark)
void EarTriangulation<PFP>::trianguleFace(Dart d)
Sylvain Thery's avatar
Sylvain Thery committed
163 164
{
	// compute normal to polygon
165
	typename PFP::VEC3 normalPoly = Algo::Surface::Geometry::newellNormal<PFP>(m_map, d, m_position);
Sylvain Thery's avatar
Sylvain Thery committed
166 167 168 169 170 171 172 173

	// first pass create polygon in chained list witht angle computation
	unsigned int nbv = 0;
	unsigned int nbe = 0;
	Dart a = d;

	if (m_map.template phi<111>(d) ==d)
	{
Pierre Kraemer's avatar
Pierre Kraemer committed
174
//		mark.markOrbit<FACE>(d);	// mark the face
Sylvain Thery's avatar
Sylvain Thery committed
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
		return;
	}

	do
	{
		float val;
		float length = computeEarInit(a,normalPoly,val);
		a = m_map.phi1(a);	// phi here because ears is next of a
		m_dartEars[a] = m_ears.insert(VertexPoly(a,val,length));
		if (length!=0)
			nbe++;
		nbv++;
	}while (a!=d);

	// NO WE HAVE THE POLYGON AND EARS
	// LET'S REMOVE THEM

	bool convex = nbe==nbv;

	while (nbv>3)
	{
		// take best (and valid!) ear
		typename VPMS::iterator be_it = m_ears.begin(); // best ear
		Dart d_e = be_it->dart;
		Dart e1 = m_map.phi1(d_e);
		Dart e2 = m_map.phi_1(d_e);

		m_map.splitFace(e1,e2);
Pierre Kraemer's avatar
Pierre Kraemer committed
203
//		mark.markOrbit<FACE>(d_e);
Sylvain Thery's avatar
Sylvain Thery committed
204 205 206 207 208 209 210 211 212 213 214 215 216 217
		nbv--;

		if (nbv>3)	// do not recompute if only one triangle left
		{
			//remove ears and two sided ears

			m_ears.erase(be_it);					// from map of ears
			m_ears.erase(m_dartEars[e1]);
			m_ears.erase(m_dartEars[e2]);

			recompute2Ears(e1,normalPoly,convex);

			convex = (m_ears.rbegin()->angle) < 5.0f;
		}
218
//		else
Pierre Kraemer's avatar
Pierre Kraemer committed
219
//			mark.markOrbit<FACE>(e1);	// mark last face
Sylvain Thery's avatar
Sylvain Thery committed
220 221 222 223 224
	}
	m_ears.clear();
}

template<typename PFP>
Sylvain Thery's avatar
Sylvain Thery committed
225
void EarTriangulation<PFP>::triangule()
Sylvain Thery's avatar
Sylvain Thery committed
226
{
Sylvain Thery's avatar
Sylvain Thery committed
227
//	DartMarker m(m_map);
228 229 230
//
//	for(Dart d = m_map.begin(); d != m_map.end(); m_map.next(d))
//	{
231
//		if(!m.isMarked(d))
232 233 234 235 236 237 238 239
//		{
//			Dart e = m_map.template phi<111>(d);
//			if (e!=d)
//				trianguleFace(d, m);
//		}
//	}
//	m.unmarkAll();

Sylvain Thery's avatar
Sylvain Thery committed
240
	TraversorF<typename PFP::MAP> trav(m_map);
241 242

	for(Dart d = trav.begin(); d != trav.end(); d = trav.next())
Sylvain Thery's avatar
Sylvain Thery committed
243
	{
244 245 246
		Dart e = m_map.template phi<111>(d);
		if (e!=d)
			trianguleFace(d);
Sylvain Thery's avatar
Sylvain Thery committed
247 248 249
	}
}

250
} // namespace Modelisation
Sylvain Thery's avatar
Sylvain Thery committed
251

252
} // namespace Surface
253

254
} // namespace Algo
Sylvain Thery's avatar
Sylvain Thery committed
255

256
} // namespace CGoGN