tetrahedralization.h 7.65 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
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/

untereiner's avatar
untereiner committed
25 26
#ifndef __TETRAHEDRALIZATION_H__
#define __TETRAHEDRALIZATION_H__
Pierre Kraemer's avatar
Pierre Kraemer committed
27

28
//#include "tetgen/tetgen.h"
29
#include "Algo/Geometry/normal.h"
Sylvain Thery's avatar
Sylvain Thery committed
30
#include <set>
31

Pierre Kraemer's avatar
Pierre Kraemer committed
32 33 34 35 36 37
namespace CGoGN
{

namespace Algo
{

38 39 40
namespace Volume
{

Pierre Kraemer's avatar
Pierre Kraemer committed
41 42 43
namespace Modelisation
{

44
//TODO change namespace
untereiner's avatar
untereiner committed
45
namespace Tetrahedralization
Pierre Kraemer's avatar
Pierre Kraemer committed
46 47
{

48 49 50 51 52 53 54 55 56 57 58 59

template <typename PFP>
class EarTriangulation
{
	typedef typename PFP::MAP MAP ;
	typedef typename PFP::VEC3 VEC3 ;

protected:
	// forward declaration
	class VertexPoly;

	// multiset typedef for simple writing
Sylvain Thery's avatar
Sylvain Thery committed
60
	typedef std::multiset<VertexPoly,VertexPoly> VPMS;
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
	typedef typename VPMS::iterator VMPSITER;
	typedef NoTypeNameAttribute<VMPSITER> EarAttr ;

	class VertexPoly
	{
	public:
		Dart dart;
		float angle;
		float length;

		VertexPoly()
		{}

		VertexPoly(Dart d, float v, float l) : dart(d), angle(v), length(l)
		{}

		bool operator()(const VertexPoly& vp1, const VertexPoly& vp2)
		{
			if (fabs(vp1.angle - vp2.angle) < 0.2f)
				return vp1.length < vp2.length;
			return vp1.angle < vp2.angle;
		}
	};

protected:
untereiner's avatar
untereiner committed
86
	MAP& m_map;
87

88
	VertexAutoAttribute<EarAttr, MAP> m_dartEars;
89

90
	VertexAttribute<VEC3, MAP> m_position;
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105

	std::vector<Dart> m_resTets;

	VPMS m_ears;

	bool inTriangle(const VEC3& P, const VEC3& normal, const VEC3& Ta, const VEC3& Tb, const VEC3& Tc);

	void recompute2Ears(Dart d, const VEC3& normalPoly, bool convex);

	float computeEarInit(Dart d, const VEC3& normalPoly, float& val);

public:

	EarTriangulation(MAP& map) : m_map(map), m_dartEars(map)
	{
106
		m_position = map.template getAttribute<VEC3, VERTEX, MAP>("position");
107 108 109 110 111
	}

//	void trianguleFace(Dart d, DartMarker& mark);
	void trianguleFace(Dart d);

Sylvain Thery's avatar
Sylvain Thery committed
112
	void triangule();
113 114 115 116 117

	std::vector<Dart> getResultingTets() { return m_resTets; }
};


118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
///**
//* subdivide a hexahedron into 5 tetrahedron
//*/
//template <typename PFP>
//void hexahedronToTetrahedron(typename PFP::MAP& map, Dart d);
//
///**
//* WARNING : assume all volumes to be hexahedrons
//* subdivide a hexahedron mesh into a tetrahedron mesh
//*/
//template <typename PFP>
//void hexahedronsToTetrahedrons(typename PFP::MAP& map);
//
//
//template <typename PFP>
//void tetrahedrizeVolume(typename PFP::MAP& map, VertexAttribute<typename PFP::VEC3>& position);
134

135
/************************************************************************************************
136
 * 									Collapse / Split Operators									*
137
 ************************************************************************************************/
138 139 140 141 142

//!
/*!
 *
 */
143 144 145
template <typename PFP>
Dart splitVertex(typename PFP::MAP& map, std::vector<Dart>& vd);

146
/************************************************************************************************
147
 * 									Tetrahedron functions										*
148
 ************************************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
149

150 151 152
//!
/*!
 *
Pierre Kraemer's avatar
Pierre Kraemer committed
153 154
 */
template <typename PFP>
Sylvain Thery's avatar
Sylvain Thery committed
155
bool isTetrahedron(typename PFP::MAP& map, Dart d);
Pierre Kraemer's avatar
Pierre Kraemer committed
156

157 158 159
//!
/*!
 *
160 161
 */
template <typename PFP>
162
bool isTetrahedralization(typename PFP::MAP& map);
163

164

165
/************************************************************************************************
166
 *										Swap Functions 											*
167
 ************************************************************************************************/
Pierre Kraemer's avatar
Pierre Kraemer committed
168

169 170
//!
/*!
Pierre Kraemer's avatar
Pierre Kraemer committed
171 172 173
 *
 */
template <typename PFP>
174
Dart swap2To2(typename PFP::MAP& map, Dart d);
Pierre Kraemer's avatar
Pierre Kraemer committed
175

176 177
//!
/*!
Pierre Kraemer's avatar
Pierre Kraemer committed
178 179 180
 *
 */
template <typename PFP>
181
Dart swap4To4(typename PFP::MAP& map, Dart d);
Pierre Kraemer's avatar
Pierre Kraemer committed
182

183 184
//!
/*!
Pierre Kraemer's avatar
Pierre Kraemer committed
185 186 187
 *
 */
template <typename PFP>
188
Dart swap3To2(typename PFP::MAP& map, Dart d);
Pierre Kraemer's avatar
Pierre Kraemer committed
189

190 191
//!
/*!
Pierre Kraemer's avatar
Pierre Kraemer committed
192 193 194
 *
 */
template <typename PFP>
195
Dart swap2To3(typename PFP::MAP& map, Dart d);
Pierre Kraemer's avatar
Pierre Kraemer committed
196

197 198
//!
/*!
Pierre Kraemer's avatar
Pierre Kraemer committed
199 200 201
 *
 */
template <typename PFP>
202
Dart swap5To4(typename PFP::MAP& map, Dart d);
Pierre Kraemer's avatar
Pierre Kraemer committed
203

204 205 206
//!
/*!
 *  called edge removal (equivalent to G32)
207 208
 * Connect the vertex of dart d to each vertex of the polygonal face
 * @return A dart from the vertex that is incident to the tetrahedra created during the swap
209 210
 */
template <typename PFP>
211
Dart swapGen3To2(typename PFP::MAP& map, Dart d);
212

213 214 215 216 217 218 219 220 221
//!
/*!
 * Edge removal
 * Optimized version : do an ear cutting on the sandwiched polygonal face
 * @return : A dart of each tetrahedra created during the swap
 */
template <typename PFP>
std::vector<Dart> swapGen3To2Optimized(typename PFP::MAP& map, Dart d);

222 223 224 225 226 227 228
//!
/*!
 * called multi-face removal (equivalent to G23 )
 */
template <typename PFP>
void swapGen2To3(typename PFP::MAP& map, Dart d);

229
/************************************************************************************************
230
 *											Flip Functions 										*
231 232
 ************************************************************************************************/

233 234
//!
/*!
235 236 237
 *
 */
template <typename PFP>
238
Dart flip1To4(typename PFP::MAP& map, Dart d);
239

240 241 242 243 244
//!
/*!
 *
 */
template <typename PFP>
245
Dart flip1To3(typename PFP::MAP& map, Dart d);
246 247

/************************************************************************************************
248
 *									Bisection Functions 										*
249 250 251 252
 ************************************************************************************************/

//!
/*!
253 254 255
 *
 */
template <typename PFP>
256
Dart edgeBisection(typename PFP::MAP& map, Dart d);
257

258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280


//namespace Tetgen
//{

///**
// * generate tetrahedra based on an surface mesh object
// */
//template <typename PFP>
//bool tetrahedralize(const typename PFP::MAP2& map2, typename PFP::MAP3& map3, bool add_steiner_points_on_exterior_boundary,
//                    bool add_steiner_points_on_interior_boundary, double max_volume, double max_shape);

///**
// * generate tetrahedra based on an surface mesh object
// */
//template <typename PFP>
//bool process(const std::string& filename, typename PFP::MAP3& map3, bool add_steiner_points_on_exterior_boundary,
//             bool add_steiner_points_on_interior_boundary, double max_volume, double max_shape);

//} //namespace Tetgen



Pierre Kraemer's avatar
Pierre Kraemer committed
281 282
} // namespace Tetrahedralization

283
} // namespace Volume
284

Pierre Kraemer's avatar
Pierre Kraemer committed
285
} // namespace Modelisation
286

Pierre Kraemer's avatar
Pierre Kraemer committed
287 288 289
} // namespace Algo

} // namespace CGoGN
Pierre Kraemer's avatar
Pierre Kraemer committed
290

untereiner's avatar
untereiner committed
291
#include "Algo/Modelisation/tetrahedralization.hpp"
Pierre Kraemer's avatar
Pierre Kraemer committed
292 293

#endif