tetrahedralization.h 7.74 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

template <typename PFP>
class EarTriangulation
{
	typedef typename PFP::MAP MAP ;
untereiner's avatar
untereiner committed
53
	typedef typename PFP::MAP::IMPL MAP_IMPL ;
54 55 56 57 58 59 60
	typedef typename PFP::VEC3 VEC3 ;

protected:
	// forward declaration
	class VertexPoly;

	// multiset typedef for simple writing
Sylvain Thery's avatar
Sylvain Thery committed
61
	typedef std::multiset<VertexPoly,VertexPoly> VPMS;
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
	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
87
	MAP& m_map;
88

untereiner's avatar
untereiner committed
89
	VertexAutoAttribute<EarAttr, MAP_IMPL> m_dartEars;
90

untereiner's avatar
untereiner committed
91
	VertexAttribute<VEC3, MAP_IMPL> m_position;
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

	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)
	{
		m_position = map.template getAttribute<VEC3, VERTEX>("position");
	}

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

	void triangule(unsigned int thread = 0);

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


119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
///**
//* 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);
135

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

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

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

151 152 153
//!
/*!
 *
Pierre Kraemer's avatar
Pierre Kraemer committed
154 155
 */
template <typename PFP>
Pierre Kraemer's avatar
Pierre Kraemer committed
156
bool isTetrahedron(typename PFP::MAP& map, Dart d, unsigned int thread = 0);
Pierre Kraemer's avatar
Pierre Kraemer committed
157

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

165

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

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

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

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

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

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

205 206 207
//!
/*!
 *  called edge removal (equivalent to G32)
208 209
 * 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
210 211
 */
template <typename PFP>
212
Dart swapGen3To2(typename PFP::MAP& map, Dart d);
213

214 215 216 217 218 219 220 221 222
//!
/*!
 * 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);

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

230
/************************************************************************************************
231
 *											Flip Functions 										*
232 233
 ************************************************************************************************/

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

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

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

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

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


//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
282 283
} // namespace Tetrahedralization

284
} // namespace Volume
285

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

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

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

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

#endif