1 // This is brl/bbas/bmsh3d/bmsh3d_face.h
2 //---------------------------------------------------------------------
3 #ifndef bmsh3d_face_h_
4 #define bmsh3d_face_h_
5 //:
6 // \file
7 // \brief Basic 3d face on a mesh
8 //
9 // \author
10 // MingChing Chang April 22, 2005
11 //
12 // \verbatim
13 // Modifications
14 // <none>
15 // \endverbatim
16 //
17 //-------------------------------------------------------------------------
18
19 #include <vector>
20 #include <iostream>
21 #include <sstream>
22 #ifdef _MSC_VER
23 # include <vcl_msvc_warnings.h>
24 #endif
25 #include <cassert>
26 #include <vgl/vgl_point_2d.h>
27 #include <vgl/vgl_point_3d.h>
28 #include <vgl/vgl_vector_3d.h>
29 #include <vgl/vgl_box_3d.h>
30
31 #include "bmsh3d_utils.h"
32 #include "bmsh3d_vertex.h"
33 class bmsh3d_edge;
34
35 //Color code to visualize several mesh objects.
36 typedef enum
37 {
38 BOGUS_TRIFACE = 0,
39 TRIFACE_111 = 1,
40 TRIFACE_112 = 2,
41 TRIFACE_113P = 3,
42 TRIFACE_122 = 4,
43 TRIFACE_123P = 5,
44 TRIFACE_13P3P = 6,
45 TRIFACE_222 = 7,
46 TRIFACE_223P = 8,
47 TRIFACE_23P3P = 9,
48 TRIFACE_3P3P3P = 10,
49 TRIFACE_E4P = 11,
50 } TRIFACE_TYPE;
51
52 class bmsh3d_mesh;
53
54 class bmsh3d_face : public vispt_elm
55 {
56 protected:
57 //: Pointer to the IFS vertices of this face.
58 std::vector<bmsh3d_vertex*> vertices_;
59
60 bmsh3d_halfedge* halfedge_;
61
62 int id_;
63
64 //:
65 // This variable is used for
66 // - i_visited_ flag for mesh traversal.
67 // - a flag in gdt propagation.
68 // - storing the sheet id.
69 int i_value_;
70
71 public:
72 //###### Constructor/Destructor ######
bmsh3d_face()73 bmsh3d_face() {
74 halfedge_ = nullptr;
75 i_value_ = 0;
76 id_ = -1;
77 }
bmsh3d_face(bmsh3d_halfedge * he)78 bmsh3d_face(bmsh3d_halfedge* he) {
79 halfedge_ = he;
80 i_value_ = 0;
81 id_ = -1;
82 }
bmsh3d_face(const int id)83 bmsh3d_face(const int id) {
84 halfedge_ = nullptr;
85 id_ = id;
86 i_value_ = 0;
87 }
88
~bmsh3d_face()89 ~bmsh3d_face() override {
90 vertices_.clear();
91 // make sure that all halfedges are deleted before the destructor.
92 // You should use bmsh3d_mesh::delete_face to delete a face.
93 assert (halfedge_ == nullptr);
94 }
95
96 //###### Data access functions ######
97
vertices(unsigned int i)98 const bmsh3d_vertex* vertices(unsigned int i) const { return vertices_[i]; }
vertices(unsigned int i)99 bmsh3d_vertex* vertices(unsigned int i) { return vertices_[i]; }
vertices()100 const std::vector<bmsh3d_vertex*>& vertices() const { return vertices_; }
vertices()101 std::vector<bmsh3d_vertex*>& vertices() { return vertices_; }
102
halfedge()103 bmsh3d_halfedge* halfedge() const { return halfedge_; }
halfedge()104 bmsh3d_halfedge* & halfedge() { return halfedge_; }
set_halfedge(bmsh3d_halfedge * he)105 void set_halfedge(bmsh3d_halfedge* he) { halfedge_ = he; }
id()106 int id() const { return id_; }
set_id(int id)107 void set_id(int id) { id_ = id; }
108
109 //: if i_value_ less than i_traverse_flag, it's not visited
is_visited(int traverse_value)110 bool is_visited(int traverse_value) const { return i_value_ >= traverse_value; }
set_i_visited(int traverse_value)111 void set_i_visited(int traverse_value) { i_value_ = traverse_value; }
112
113 //: just use the i_value_ as a boolean flag
b_visited()114 bool b_visited() const { return i_value_ != 0; }
set_visited(bool b)115 void set_visited(bool b) { i_value_ = b ? 1 : 0; }
sid()116 int sid() const { return i_value_; }
set_sid(int sid)117 void set_sid(int sid) { i_value_ = sid; }
118
119 //###### Connectivity Query via Halfedges ######
120
121 void get_incident_HEs(std::vector<bmsh3d_halfedge*>& incident_HEs) const;
122 void get_incident_Es(std::vector<bmsh3d_edge*>& incident_Es) const;
123 unsigned int n_incident_Es() const;
124 bool is_E_incident(const bmsh3d_edge* inputE) const;
125 bmsh3d_halfedge* find_bnd_HE() const;
126
127 bool is_V_incident_via_HE(const bmsh3d_vertex* inputV) const;
128 bmsh3d_vertex* get_next_V_via_HE(const bmsh3d_vertex* inputV) const;
129
130 //: Given a vertex V and an edge of this face incident to V, find the other edge of this face incident to V.
131 bmsh3d_edge* find_other_E(const bmsh3d_vertex* inputV,
132 const bmsh3d_edge* inputE) const;
133
134 //: Given a vertex V and a halfedge of this face incident to V, find the other halfedge of this face incident to V.
135 bmsh3d_halfedge* find_other_HE(const bmsh3d_vertex* inputV,
136 const bmsh3d_halfedge* inputHE) const;
137
138 //: Given a vertex V and an edge of this face incident to V, find the next edge (following the circular halfedge list) of this face incident to V.
139 bmsh3d_edge* find_next_E(const bmsh3d_vertex* inputV,
140 const bmsh3d_edge* inputE) const;
141
142 //: Given a vertex V and a halfedge of this face incident to V, find the next halfedge (following the circular halfedge list) of this face incident to V.
143 bmsh3d_halfedge* find_next_HE(const bmsh3d_vertex* inputV,
144 const bmsh3d_halfedge* inputHE) const;
145
146 double angle_at_V(const bmsh3d_vertex* inputV) const;
147
148 int n_incident_Vs_in_set(std::set<bmsh3d_vertex*>& vertices) const;
149 bool all_Vs_incident(std::vector<bmsh3d_vertex*>& vertices) const;
150
151 void get_ordered_Vs(std::vector<bmsh3d_vertex*>& vertices) const;
152 void _get_ordered_Vs_MHE(std::vector<bmsh3d_vertex*>& vertices) const;
153 void _get_ordered_Vs_IFS(std::vector<bmsh3d_vertex*>& vertices) const;
154
155 void get_ordered_V_ids(std::vector<int>& vids) const;
156 void _get_ordered_V_ids_MHE(std::vector<int>& vids) const;
157 void _get_ordered_V_ids_IFS(std::vector<int>& vids) const;
158
159 //###### Handle local list of incident vertices ######
_ifs_add_vertex(bmsh3d_vertex * V)160 void _ifs_add_vertex(bmsh3d_vertex* V) { vertices_.push_back(V); }
_ifs_clear_vertices()161 void _ifs_clear_vertices() { vertices_.clear(); }
_ifs_prev_V(bmsh3d_vertex * inputV)162 bmsh3d_vertex* _ifs_prev_V(bmsh3d_vertex* inputV) const {
163 if (vertices_[0] == inputV)
164 return vertices_[vertices_.size()-1];
165
166 for (unsigned int i=1; i<vertices_.size(); i++) {
167 if (vertices_[i] == inputV)
168 return vertices_[i-1];
169 }
170 assert (0);
171 return nullptr;
172 }
_ifs_next_V(bmsh3d_vertex * inputV)173 bmsh3d_vertex* _ifs_next_V(bmsh3d_vertex* inputV) const {
174 if (vertices_[vertices_.size()-1] == inputV)
175 return vertices_[0];
176
177 for (unsigned int i=0; i<vertices_.size()-1; i++) {
178 if (vertices_[i] == inputV)
179 return vertices_[i+1];
180 }
181 assert (0);
182 return nullptr;
183 }
184 //: track incident vertices and reset ifs_face::vertices_[]
185 void _ifs_track_ordered_vertices();
186
_ifs_assign_Vs_vid_by_id()187 void _ifs_assign_Vs_vid_by_id() {
188 for (auto V : vertices_) {
189 V->set_vid(V->id());
190 }
191 }
192
193 //Test if the face's IFS structure is correct (repeated or wrong Vids).
194 bool _is_ifs_valid(bmsh3d_mesh* M);
195
196 bool _ifs_inside_box(const vgl_box_3d<double>& box) const;
197 bool _ifs_outside_box(const vgl_box_3d<double>& box) const;
198
199 //###### Geometry Query Functions ######
200
201 bool is_inside_box(const vgl_box_3d<double>& box) const;
202 bool is_outside_box(const vgl_box_3d<double>& box) const;
203 vgl_point_3d<double> compute_center_pt() const;
204 vgl_point_3d<double> compute_center_pt(const std::vector<bmsh3d_vertex*>& vertices) const;
205 vgl_vector_3d<double> compute_normal();
206
207 //###### Connectivity Modification Functions ######
208
209 //: Connect a halfedge to this mesh face.
210 void _connect_HE_to_end(bmsh3d_halfedge* inputHE);
211 //: Remove the input halfedge from the face's halfedge list.
212 bool _remove_HE(bmsh3d_halfedge* inputHE);
213 //: Create a halfedge and connect a mesh face and an edge.
214 void connect_E_to_end(bmsh3d_edge* E);
215 //: Disconnect a face and an edge(delete the halfedge).
216 void disconnect_E(bmsh3d_halfedge* HE);
217
218 //: Sort the incident halfedges to form a circular list
219 bool _sort_HEs_circular();
220
221 //: disconnect all associated halfedges from their edges and delete them.
222 virtual void _discon_all_incident_Es();
223
224 //: reverse the orientation of chain of halfedges of this face.
225 void _reverse_HE_chain();
226
227 void set_orientation(bmsh3d_halfedge* new_start_he,
228 bmsh3d_vertex* new_next_v);
229
230 //###### Other functions ######
231
232 void getInfo(std::ostringstream& ostrm) override;
233
234 //###### For triangular face only ######
235 TRIFACE_TYPE tri_get_topo_type() const;
236 std::string tri_get_topo_string() const;
237
238 //###### For the face of a 2-manifold triangular mesh only ######
239 // these functions start with tag m2t (manifold-2-triangle)
240
241 bmsh3d_edge* m2t_edge_against_vertex(bmsh3d_vertex* input_vertex);
242 bmsh3d_halfedge* m2t_halfedge_against_vertex(bmsh3d_vertex* input_vertex);
243
244 //: given input_face, find the neighboring face against the input_vertex
245 bmsh3d_face* m2t_nbr_face_against_vertex(bmsh3d_vertex* input_vertex);
246
247 bmsh3d_face* m2t_nbr_face_sharing_edge(bmsh3d_vertex* v1, bmsh3d_vertex* v2);
248
249 //: given v1, v2, find v3
250 bmsh3d_vertex* t_3rd_vertex(const bmsh3d_vertex* V1, const bmsh3d_vertex* V2) const;
251 bmsh3d_vertex* t_vertex_against_edge(const bmsh3d_edge* inputE) const;
252 };
253
254 //###### Additional Functions ######
255
256 bmsh3d_halfedge* _find_prev_in_HE_chain(const bmsh3d_halfedge* inputHE);
257
258 //: disconnect all associated halfedges from their edges from the given he_head.
259 void _delete_HE_chain(bmsh3d_halfedge* & he_head);
260
261 // Return: the set of incident edges that get disconnected.
262 // Also set the he_head to be NULL after calling it.
263 void _delete_HE_chain(bmsh3d_halfedge* & he_head,
264 std::vector<bmsh3d_edge*>& incident_edge_list);
265
266 //: Given the face, current halfedge, and current eV, find the next halfedge given in the vector<>.
267 bmsh3d_halfedge* _find_next_halfedge(bmsh3d_halfedge* HE,
268 bmsh3d_vertex* eV,
269 std::vector<bmsh3d_halfedge*>& inc_hes);
270
271 //: Assume the mesh face is planar and compute a 2D planar coordinate for it.
272 void get_2d_coord(const std::vector<bmsh3d_vertex*>& vertices,
273 vgl_vector_3d<double>& N, vgl_vector_3d<double>& AX,
274 vgl_vector_3d<double>& AY);
275
276 //: Return ordered set of vertices in 2D (x,y) coord.
277 void get_2d_polygon(const std::vector<bmsh3d_vertex*>& vertices,
278 std::vector<double>& xs, std::vector<double>& ys);
279
280 //: Return the projected point in the local 2D (x,y) coord.
281 vgl_point_2d<double> get_2d_proj_pt(vgl_point_3d<double> P, const vgl_point_3d<double>& A,
282 const vgl_vector_3d<double>& AX,
283 const vgl_vector_3d<double>& AY);
284
285 vgl_point_3d<double> compute_cen(const std::vector<bmsh3d_vertex*>& vertices);
286
287 vgl_vector_3d<double> compute_normal_ifs(const std::vector<bmsh3d_vertex*>& vertices);
288
289 //: Compute face normal using the given edge and starting node.
290 vgl_vector_3d<double> compute_normal(const vgl_point_3d<double>& C,
291 const bmsh3d_edge* E,
292 const bmsh3d_vertex* Es);
293
294 //: Return true if vertices is a polygon or obtuse triangle.
295 bool is_tri_non_acute(const std::vector<bmsh3d_vertex*>& vertices);
296
297 bool is_F_extraneous(bmsh3d_face* F);
298
299 bmsh3d_face* get_F_sharing_Es(bmsh3d_edge* E1, bmsh3d_edge* E2);
300
301 //###### For the face of a 2-manifold triangular mesh only ######
302
m2t_compute_tri_angles(const double & c,const double & l,const double & r,double & angle_cl,double & angle_cr,double & angle_lr)303 inline void m2t_compute_tri_angles(const double& c, const double& l, const double& r,
304 double& angle_cl, double& angle_cr, double& angle_lr)
305 {
306 angle_cl = std::acos( (c*c + l*l - r*r)/(c*l*2) );
307 angle_cr = std::acos( (c*c + r*r - l*l)/(c*r*2) );
308 angle_lr = std::acos( (l*l + r*r - c*c)/(l*r*2) );
309 }
310
m2t_compute_angles_cl_cr(const double & c,const double & l,const double & r,double & angle_cl,double & angle_cr)311 inline void m2t_compute_angles_cl_cr(const double& c, const double& l, const double& r,
312 double& angle_cl, double& angle_cr)
313 {
314 angle_cl = std::acos( (c*c + l*l - r*r)/(c*l*2) );
315 angle_cr = std::acos( (c*c + r*r - l*l)/(c*r*2) );
316 }
317
m2t_compute_angle_cl(const double & c,const double & l,const double & r)318 inline double m2t_compute_angle_cl(const double& c, const double& l, const double& r)
319 {
320 return std::acos( (c*c + l*l - r*r)/(c*l*2) );
321 }
322
m2t_compute_angle_cr(const double & c,const double & l,const double & r)323 inline double m2t_compute_angle_cr(const double& c, const double& l, const double& r)
324 {
325 return std::acos( (c*c + r*r - l*l)/(c*r*2) );
326 }
327
m2t_compute_angle_lr(const double & c,const double & l,const double & r)328 inline double m2t_compute_angle_lr(const double& c, const double& l, const double& r)
329 {
330 return std::acos( (l*l + r*r - c*c)/(l*r*2) );
331 }
332
333 #endif
334