Point Cloud Library (PCL) 1.12.0
Loading...
Searching...
No Matches
triangle_mesh.h
1/*
2 * Software License Agreement (BSD License)
3 *
4 * Point Cloud Library (PCL) - www.pointclouds.org
5 * Copyright (c) 2009-2012, Willow Garage, Inc.
6 * Copyright (c) 2012-, Open Perception, Inc.
7 *
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * * Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * * Redistributions in binary form must reproduce the above
17 * copyright notice, this list of conditions and the following
18 * disclaimer in the documentation and/or other materials provided
19 * with the distribution.
20 * * Neither the name of the copyright holder(s) nor the names of its
21 * contributors may be used to endorse or promote products derived
22 * from this software without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
27 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
28 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
29 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
30 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
31 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
32 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
34 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
36 *
37 * $Id$
38 *
39 */
40
41#pragma once
42
43#include <pcl/geometry/mesh_base.h>
44#include <pcl/memory.h>
45#include <pcl/pcl_macros.h>
46
47#include <utility>
48
49namespace pcl {
50namespace geometry {
51/** \brief Tag describing the type of the mesh. */
53
54/** \brief Half-edge mesh that can only store triangles.
55 * \tparam MeshTraitsT Please have a look at pcl::geometry::DefaultMeshTraits.
56 * \author Martin Saelzle
57 * \ingroup geometry
58 */
59template <class MeshTraitsT>
60class TriangleMesh : public pcl::geometry::MeshBase<TriangleMesh<MeshTraitsT>,
61 MeshTraitsT,
62 TriangleMeshTag> {
63public:
64 using Base =
66
68 using Ptr = shared_ptr<Self>;
69 using ConstPtr = shared_ptr<const Self>;
70
71 using VertexData = typename Base::VertexData;
73 using EdgeData = typename Base::EdgeData;
74 using FaceData = typename Base::FaceData;
75 using IsManifold = typename Base::IsManifold;
76 using MeshTag = typename Base::MeshTag;
77
82
87
88 // Indices
91 using EdgeIndex = typename Base::EdgeIndex;
92 using FaceIndex = typename Base::FaceIndex;
93 using FaceIndexPair = std::pair<FaceIndex, FaceIndex>;
94
99
100 // Circulators
113
114 /** \brief Constructor. */
115 TriangleMesh() : Base(), add_triangle_(3), inner_he_atp_(4), is_new_atp_(4) {}
116
117 /** \brief The base method of addFace is hidden because of the overloads in this
118 * class. */
119 using Base::addFace;
120
121 /** \brief Add a triangle to the mesh. Data is only added if it is associated with the
122 * elements. The last vertex is connected with the first one.
123 * \param[in] idx_v_0 Index to the first vertex.
124 * \param[in] idx_v_1 Index to the second vertex.
125 * \param[in] idx_v_2 Index to the third vertex.
126 * \param[in] face_data Data that is set for the face.
127 * \param[in] half_edge_data Data that is set for all added half-edges.
128 * \param[in] edge_data Data that is set for all added edges.
129 * \return Index to the new face. Failure is signaled by returning an invalid face
130 * index.
131 * \warning The vertices must be valid and unique (each vertex may be contained
132 * only once). Not complying with this requirement results in undefined behavior!
133 */
134 inline FaceIndex
135 addFace(const VertexIndex& idx_v_0,
136 const VertexIndex& idx_v_1,
137 const VertexIndex& idx_v_2,
138 const FaceData& face_data = FaceData(),
139 const EdgeData& edge_data = EdgeData(),
140 const HalfEdgeData& half_edge_data = HalfEdgeData())
141 {
142 add_triangle_[0] = idx_v_0;
143 add_triangle_[1] = idx_v_1;
144 add_triangle_[2] = idx_v_2;
145
146 return (this->addFaceImplBase(add_triangle_, face_data, edge_data, half_edge_data));
147 }
148
149 /** \brief Add two triangles for the four given input vertices. When using a manifold
150 * triangle mesh it is not possible to connect two bounded regions without going
151 * through a non-manifold intermediate step. This method first tries to add the
152 * triangles individually and if this fails connects the whole configuration at once
153 * (if possible).
154 * \param[in] vertices Indices to the vertices of the new face. (The size
155 * must be equal to four).
156 * \param[in] face_data Data that is set for the face.
157 * \param[in] half_edge_data Data that is set for all added half-edges.
158 * \param[in] edge_data Data that is set for all added edges.
159 * \return Pair of face indices. The first index is valid if one triangle was added.
160 * Both indices are valid if two triangles were added.
161 * \warning The vertices must be valid and unique (each vertex may be contained only
162 * once). Not complying with this requirement results in undefined behavior!
163 */
166 const FaceData& face_data = FaceData(),
167 const EdgeData& edge_data = EdgeData(),
168 const HalfEdgeData& half_edge_data = HalfEdgeData())
169 {
170 if (vertices.size() != 4) {
171 return (std::make_pair(FaceIndex(), FaceIndex()));
172 }
173 return (this->addTrianglePair(vertices[0],
174 vertices[1],
175 vertices[2],
176 vertices[3],
177 face_data,
178 edge_data,
179 half_edge_data));
180 }
181
182 /** \brief Add two triangles for the four given input vertices. When using a manifold
183 * triangle mesh it is not possible to connect two bounded regions without going
184 * through a non-manifold intermediate step. This method first tries to add the
185 * triangles individually and if this fails connects the whole configuration at once
186 * (if possible).
187 * \param[in] idx_v_0 Index to the first vertex.
188 * \param[in] idx_v_1 Index to the second vertex.
189 * \param[in] idx_v_2 Index to the third vertex.
190 * \param[in] idx_v_3 Index to the fourth vertex.
191 * \param[in] face_data Data that is set for the face.
192 * \param[in] half_edge_data Data that is set for all added half-edges.
193 * \param[in] edge_data Data that is set for all added edges.
194 * \return Pair of face indices. The first index is valid if one triangle was added.
195 * Both indices are valid if two triangles were added.
196 * \warning The vertices must be valid and unique (each vertex may be contained only
197 * once). Not complying with this requirement results in undefined behavior!
198 */
199 inline FaceIndexPair
201 const VertexIndex& idx_v_1,
202 const VertexIndex& idx_v_2,
203 const VertexIndex& idx_v_3,
204 const FaceData& face_data = FaceData(),
205 const EdgeData& edge_data = EdgeData(),
206 const HalfEdgeData& half_edge_data = HalfEdgeData())
207 {
208 // Try to add two faces
209 // 3 - 2
210 // | / |
211 // 0 - 1
212 FaceIndex idx_face_0 = this->addFace(idx_v_0, idx_v_1, idx_v_2, face_data);
213 FaceIndex idx_face_1 = this->addFace(idx_v_0, idx_v_2, idx_v_3, face_data);
214
215 if (idx_face_0.isValid()) {
216 return (std::make_pair(idx_face_0, idx_face_1));
217 }
218 if (idx_face_1.isValid()) {
219 idx_face_0 = this->addFace(
220 idx_v_0, idx_v_1, idx_v_2, face_data); // might be possible to add now
221 return (std::make_pair(idx_face_1, idx_face_0));
222 }
223
224 // Try to add two faces
225 // 3 - 2
226 // | \ |
227 // 0 - 1
228 idx_face_0 = this->addFace(idx_v_1, idx_v_2, idx_v_3, face_data);
229 idx_face_1 = this->addFace(idx_v_0, idx_v_1, idx_v_3, face_data);
230
231 if (idx_face_0.isValid()) {
232 return (std::make_pair(idx_face_0, idx_face_1));
233 }
234 if (idx_face_1.isValid()) {
235 idx_face_0 = this->addFace(
236 idx_v_1, idx_v_2, idx_v_3, face_data); // might be possible to add now
237 return (std::make_pair(idx_face_1, idx_face_0));
238 }
239
240 if (!IsManifold::value) {
241 return (std::make_pair(FaceIndex(), FaceIndex()));
242 }
243
244 // Check manifoldness
246 idx_v_0, idx_v_1, inner_he_atp_[0], is_new_atp_[0], IsManifold()) ||
248 idx_v_1, idx_v_2, inner_he_atp_[1], is_new_atp_[1], IsManifold()) ||
250 idx_v_2, idx_v_3, inner_he_atp_[2], is_new_atp_[2], IsManifold()) ||
252 idx_v_3, idx_v_0, inner_he_atp_[3], is_new_atp_[3], IsManifold())) {
253 return (std::make_pair(FaceIndex(), FaceIndex()));
254 }
255
256 // Connect the triangle pair
257 if (!is_new_atp_[0] && is_new_atp_[1] && !is_new_atp_[2] && is_new_atp_[3]) {
258 return (this->connectTrianglePair(inner_he_atp_[0],
259 inner_he_atp_[2],
260 idx_v_0,
261 idx_v_1,
262 idx_v_2,
263 idx_v_3,
264 face_data,
265 edge_data,
266 half_edge_data));
267 }
268 if (is_new_atp_[0] && !is_new_atp_[1] && is_new_atp_[2] && !is_new_atp_[3]) {
269 return (this->connectTrianglePair(inner_he_atp_[1],
270 inner_he_atp_[3],
271 idx_v_1,
272 idx_v_2,
273 idx_v_3,
274 idx_v_0,
275 face_data,
276 edge_data,
277 half_edge_data));
278 }
279 return (std::make_pair(FaceIndex(), FaceIndex()));
280 }
281
282private:
283 // NOTE: Can't use the typedef of Base as a friend.
284 friend class pcl::geometry::
285 MeshBase<TriangleMesh<MeshTraitsT>, MeshTraitsT, pcl::geometry::TriangleMeshTag>;
286
287 /** \brief addFace for the triangular mesh. */
288 inline FaceIndex
289 addFaceImpl(const VertexIndices& vertices,
290 const FaceData& face_data,
291 const EdgeData& edge_data,
292 const HalfEdgeData& half_edge_data)
293 {
294 if (vertices.size() == 3)
295 return (this->addFaceImplBase(vertices, face_data, edge_data, half_edge_data));
296 return (FaceIndex());
297 }
298
299 /** \brief Connect the triangles a-b-c and a-c-d. The edges a-b and c-d must be old
300 * and the edges b-c and d-a must be new. */
301 // d - c
302 // | / |
303 // a - b
305 connectTrianglePair(const HalfEdgeIndex& idx_he_ab,
306 const HalfEdgeIndex& idx_he_cd,
307 const VertexIndex& idx_v_a,
308 const VertexIndex& idx_v_b,
309 const VertexIndex& idx_v_c,
310 const VertexIndex& idx_v_d,
311 const FaceData& face_data,
312 const EdgeData& edge_data,
313 const HalfEdgeData& he_data)
314 {
315 // Add new half-edges
316 const HalfEdgeIndex idx_he_bc = Base::addEdge(idx_v_b, idx_v_c, he_data, edge_data);
317 const HalfEdgeIndex idx_he_da = Base::addEdge(idx_v_d, idx_v_a, he_data, edge_data);
318 const HalfEdgeIndex idx_he_ca = Base::addEdge(idx_v_c, idx_v_a, he_data, edge_data);
319
320 const HalfEdgeIndex idx_he_cb = Base::getOppositeHalfEdgeIndex(idx_he_bc);
321 const HalfEdgeIndex idx_he_ad = Base::getOppositeHalfEdgeIndex(idx_he_da);
322 const HalfEdgeIndex idx_he_ac = Base::getOppositeHalfEdgeIndex(idx_he_ca);
323
324 // Get the existing half-edges
325 const HalfEdgeIndex idx_he_ab_prev =
326 Base::getPrevHalfEdgeIndex(idx_he_ab); // No reference!
327 const HalfEdgeIndex idx_he_ab_next =
328 Base::getNextHalfEdgeIndex(idx_he_ab); // No reference!
329
330 const HalfEdgeIndex idx_he_cd_prev =
331 Base::getPrevHalfEdgeIndex(idx_he_cd); // No reference!
332 const HalfEdgeIndex idx_he_cd_next =
333 Base::getNextHalfEdgeIndex(idx_he_cd); // No reference!
334
335 // Connect the outer half-edges
336 Base::connectPrevNext(idx_he_ab_prev, idx_he_ad);
337 Base::connectPrevNext(idx_he_ad, idx_he_cd_next);
338 Base::connectPrevNext(idx_he_cd_prev, idx_he_cb);
339 Base::connectPrevNext(idx_he_cb, idx_he_ab_next);
340
341 // Connect the inner half-edges
342 Base::connectPrevNext(idx_he_ab, idx_he_bc);
343 Base::connectPrevNext(idx_he_bc, idx_he_ca);
344 Base::connectPrevNext(idx_he_ca, idx_he_ab);
345
346 Base::connectPrevNext(idx_he_ac, idx_he_cd);
347 Base::connectPrevNext(idx_he_cd, idx_he_da);
348 Base::connectPrevNext(idx_he_da, idx_he_ac);
349
350 // Connect the vertices to the boundary half-edges
351 Base::setOutgoingHalfEdgeIndex(idx_v_a, idx_he_ad);
352 Base::setOutgoingHalfEdgeIndex(idx_v_b, idx_he_ab_next);
353 Base::setOutgoingHalfEdgeIndex(idx_v_c, idx_he_cb);
354 Base::setOutgoingHalfEdgeIndex(idx_v_d, idx_he_cd_next);
355
356 // Add and connect the faces
357 HalfEdgeIndices inner_he_abc;
358 inner_he_abc.reserve(3);
359 inner_he_abc.push_back(idx_he_ab);
360 inner_he_abc.push_back(idx_he_bc);
361 inner_he_abc.push_back(idx_he_ca);
362
363 HalfEdgeIndices inner_he_acd;
364 inner_he_acd.reserve(3);
365 inner_he_acd.push_back(idx_he_ac);
366 inner_he_acd.push_back(idx_he_cd);
367 inner_he_acd.push_back(idx_he_da);
368
369 const FaceIndex idx_f_abc = Base::connectFace(inner_he_abc, face_data);
370 const FaceIndex idx_f_acd = Base::connectFace(inner_he_acd, face_data);
371
372 return (std::make_pair(idx_f_abc, idx_f_acd));
373 }
374
375 ////////////////////////////////////////////////////////////////////////
376 // Members
377 ////////////////////////////////////////////////////////////////////////
378
379 /** \brief Storage for adding a triangle. */
380 VertexIndices add_triangle_;
381
382 /** \brief Storage for addTrianglePair. */
383 HalfEdgeIndices inner_he_atp_;
384
385 /** \brief Storage for addTrianglePair. */
386 std::vector<bool> is_new_atp_;
387
388public:
390};
391} // namespace geometry
392} // End namespace pcl
Base class for the half-edge mesh.
Definition mesh_base.h:96
void setOutgoingHalfEdgeIndex(const VertexIndex &idx_vertex, const HalfEdgeIndex &idx_outgoing_half_edge)
Set the outgoing half-edge index to a given vertex.
Definition mesh_base.h:1878
HalfEdgeIndex getNextHalfEdgeIndex(const HalfEdgeIndex &idx_half_edge) const
Get the next half-edge index to a given half-edge.
Definition mesh_base.h:404
std::integral_constant< bool, !std::is_same< VertexData, pcl::geometry::NoData >::value > HasVertexData
Definition mesh_base.h:120
pcl::geometry::IncomingHalfEdgeAroundVertexCirculator< const Self > IncomingHalfEdgeAroundVertexCirculator
Definition mesh_base.h:153
pcl::geometry::OuterHalfEdgeAroundFaceCirculator< const Self > OuterHalfEdgeAroundFaceCirculator
Definition mesh_base.h:161
HalfEdgeIndex getOppositeHalfEdgeIndex(const HalfEdgeIndex &idx_half_edge) const
Get the opposite half-edge index to a given half-edge.
Definition mesh_base.h:394
FaceIndex connectFace(const HalfEdgeIndices &inner_he, const FaceData &face_data)
Add a face to the mesh and connect it to the half-edges.
Definition mesh_base.h:1415
bool checkTopology1(const VertexIndex &idx_v_a, const VertexIndex &idx_v_b, HalfEdgeIndex &idx_he_ab, std::vector< bool >::reference is_new_ab, std::true_type) const
Check if the edge between the two vertices can be added.
Definition mesh_base.h:1270
HalfEdgeIndex getPrevHalfEdgeIndex(const HalfEdgeIndex &idx_half_edge) const
Get the previous half-edge index to a given half-edge.
Definition mesh_base.h:412
pcl::geometry::FaceAroundFaceCirculator< const Self > FaceAroundFaceCirculator
Definition mesh_base.h:162
FaceIndex addFaceImplBase(const VertexIndices &vertices, const FaceData &face_data, const EdgeData &edge_data, const HalfEdgeData &half_edge_data)
General implementation of addFace.
Definition mesh_base.h:1158
pcl::geometry::FaceAroundVertexCirculator< const Self > FaceAroundVertexCirculator
Definition mesh_base.h:155
std::integral_constant< bool, !std::is_same< EdgeData, pcl::geometry::NoData >::value > HasEdgeData
Definition mesh_base.h:126
std::integral_constant< bool, !std::is_same< FaceData, pcl::geometry::NoData >::value > HasFaceData
Definition mesh_base.h:129
FaceIndex addFace(const VertexIndices &vertices, const FaceData &face_data=FaceData(), const EdgeData &edge_data=EdgeData(), const HalfEdgeData &half_edge_data=HalfEdgeData())
Add a face to the mesh.
Definition mesh_base.h:203
void connectPrevNext(const HalfEdgeIndex &idx_he_ab, const HalfEdgeIndex &idx_he_bc)
Connect the next and prev indices of the two half-edges with each other.
Definition mesh_base.h:1431
pcl::geometry::VertexAroundFaceCirculator< const Self > VertexAroundFaceCirculator
Definition mesh_base.h:157
pcl::geometry::InnerHalfEdgeAroundFaceCirculator< const Self > InnerHalfEdgeAroundFaceCirculator
Definition mesh_base.h:159
pcl::geometry::VertexAroundVertexCirculator< const Self > VertexAroundVertexCirculator
Definition mesh_base.h:149
HalfEdgeIndex addEdge(const VertexIndex &idx_v_a, const VertexIndex &idx_v_b, const HalfEdgeData &he_data, const EdgeData &edge_data)
Add an edge between the two given vertices and connect them with the vertices.
Definition mesh_base.h:1242
std::integral_constant< bool, !std::is_same< HalfEdgeData, pcl::geometry::NoData >::value > HasHalfEdgeData
Definition mesh_base.h:123
pcl::geometry::OutgoingHalfEdgeAroundVertexCirculator< const Self > OutgoingHalfEdgeAroundVertexCirculator
Definition mesh_base.h:151
Half-edge mesh that can only store triangles.
typename Base::EdgeData EdgeData
TriangleMesh< MeshTraitsT > Self
typename Base::InnerHalfEdgeAroundFaceCirculator InnerHalfEdgeAroundFaceCirculator
typename Base::HalfEdgeDataCloud HalfEdgeDataCloud
shared_ptr< const Self > ConstPtr
typename Base::VertexDataCloud VertexDataCloud
FaceIndex addFace(const VertexIndex &idx_v_0, const VertexIndex &idx_v_1, const VertexIndex &idx_v_2, const FaceData &face_data=FaceData(), const EdgeData &edge_data=EdgeData(), const HalfEdgeData &half_edge_data=HalfEdgeData())
Add a triangle to the mesh.
typename Base::HasFaceData HasFaceData
FaceIndexPair addTrianglePair(const VertexIndices &vertices, const FaceData &face_data=FaceData(), const EdgeData &edge_data=EdgeData(), const HalfEdgeData &half_edge_data=HalfEdgeData())
Add two triangles for the four given input vertices.
typename Base::MeshTag MeshTag
typename Base::VertexData VertexData
typename Base::VertexAroundVertexCirculator VertexAroundVertexCirculator
typename Base::VertexAroundFaceCirculator VertexAroundFaceCirculator
typename Base::EdgeIndex EdgeIndex
typename Base::HalfEdgeData HalfEdgeData
typename Base::IsManifold IsManifold
typename Base::HasVertexData HasVertexData
typename Base::OuterHalfEdgeAroundFaceCirculator OuterHalfEdgeAroundFaceCirculator
typename Base::IncomingHalfEdgeAroundVertexCirculator IncomingHalfEdgeAroundVertexCirculator
FaceIndexPair addTrianglePair(const VertexIndex &idx_v_0, const VertexIndex &idx_v_1, const VertexIndex &idx_v_2, const VertexIndex &idx_v_3, const FaceData &face_data=FaceData(), const EdgeData &edge_data=EdgeData(), const HalfEdgeData &half_edge_data=HalfEdgeData())
Add two triangles for the four given input vertices.
typename Base::FaceAroundVertexCirculator FaceAroundVertexCirculator
typename Base::EdgeDataCloud EdgeDataCloud
typename Base::FaceIndices FaceIndices
typename Base::HalfEdgeIndices HalfEdgeIndices
std::pair< FaceIndex, FaceIndex > FaceIndexPair
typename Base::EdgeIndices EdgeIndices
typename Base::HalfEdgeIndex HalfEdgeIndex
typename Base::FaceDataCloud FaceDataCloud
typename Base::FaceAroundFaceCirculator FaceAroundFaceCirculator
typename Base::HasHalfEdgeData HasHalfEdgeData
typename Base::VertexIndex VertexIndex
typename Base::HasEdgeData HasEdgeData
typename Base::FaceIndex FaceIndex
typename Base::OutgoingHalfEdgeAroundVertexCirculator OutgoingHalfEdgeAroundVertexCirculator
typename Base::VertexIndices VertexIndices
typename Base::FaceData FaceData
#define PCL_MAKE_ALIGNED_OPERATOR_NEW
Macro to signal a class requires a custom allocator.
Definition memory.h:63
Defines functions, macros and traits for allocating and using memory.
Defines all the PCL and non-PCL macros used.
Tag describing the type of the mesh.