Line data Source code
1 : /*
2 : * Copyright (c) 2015: G-CSC, Goethe University Frankfurt
3 : * Author: Sebastian Reiter
4 : *
5 : * This file is part of UG4.
6 : *
7 : * UG4 is free software: you can redistribute it and/or modify it under the
8 : * terms of the GNU Lesser General Public License version 3 (as published by the
9 : * Free Software Foundation) with the following additional attribution
10 : * requirements (according to LGPL/GPL v3 §7):
11 : *
12 : * (1) The following notice must be displayed in the Appropriate Legal Notices
13 : * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 : *
15 : * (2) The following notice must be displayed at a prominent place in the
16 : * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 : *
18 : * (3) The following bibliography is recommended for citation and must be
19 : * preserved in all covered files:
20 : * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 : * parallel geometric multigrid solver on hierarchically distributed grids.
22 : * Computing and visualization in science 16, 4 (2013), 151-164"
23 : * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 : * flexible software system for simulating pde based models on high performance
25 : * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 : *
27 : * This program is distributed in the hope that it will be useful,
28 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 : * GNU Lesser General Public License for more details.
31 : */
32 :
33 : #ifndef __H__UG_delaunay_info
34 : #define __H__UG_delaunay_info
35 :
36 : #include <queue>
37 : #include <vector>
38 : #include <sstream>
39 : #include "common/ug_config.h"
40 : #include "lib_grid/lg_base.h"
41 : #include "lib_grid/algorithms/attachment_util.h"
42 :
43 : namespace ug{
44 :
45 : /** This class intended for internal use in delaunay related algorithms.
46 : */
47 : template <class TAAPos>
48 : class UG_API DelaunayInfo : public GridObserver
49 : {
50 : typedef TAAPos AAPos;
51 : typedef typename TAAPos::ValueType vector_t;
52 :
53 : public:
54 : enum Mark{
55 : NONE,
56 : INNER,
57 : NEW_INNER,
58 : SEGMENT,
59 : NEW_SEGMENT,
60 : DART,
61 : SHELL
62 : };
63 :
64 : DelaunayInfo(Grid& g, TAAPos& aaPos,
65 : Grid::edge_traits::callback cbConstrainedEdge);
66 :
67 : ~DelaunayInfo();
68 :
69 0 : Grid& grid() {return m_grid;}
70 0 : AAPos& position_accessor() {return m_aaPos;}
71 :
72 :
73 : /** \warning init_marks may currently only be called once! Undefined behaviour
74 : * if called multiple times or after marks have already been set.
75 : * \todo think about adding a cleanup at the beginning of init_marks (costly)*/
76 : template <class TIter>
77 : void init_marks(TIter trisBegin, TIter trisEnd, bool pushFlipCandidates);
78 :
79 : ////////////////////////////////////////////////////////////////
80 : // MARKS
81 0 : void set_mark(Vertex* v, Mark m) {m_aaMark[v] = m;}
82 0 : Mark mark(Vertex* v) const {return static_cast<Mark>(m_aaMark[v]);}
83 :
84 0 : void set_mark(Edge* e, Mark m) {m_aaMark[e] = m;}
85 0 : Mark mark(Edge* e) const {return static_cast<Mark>(m_aaMark[e]);}
86 :
87 : void set_mark(Face* f, Mark m);
88 0 : Mark mark(Face* f) const {return static_cast<Mark>(m_aaMark[f]);}
89 :
90 : template <class TIter>
91 : void set_mark(TIter begin, TIter end, Mark m)
92 : {
93 : while(begin != end) {set_mark(*begin, m); ++begin;}
94 : }
95 :
96 : /// returns true if the specified element is either marked as INNER or as NEW_INNER
97 : template <class TElem>
98 : bool is_inner(TElem* e);
99 :
100 : /// returns true if the specified element is either marked as SEGMENT, NEW_SEGMENT, DART or SHELL
101 : template <class TElem>
102 : bool is_segment(TElem* e);
103 :
104 : /// returns true if the specified edge is a segment and is connected to a DART vertex
105 : bool is_dart_segment(Edge* e);
106 :
107 : /// returns true if the specified edge is a new segment and is connected to a DART vertex
108 : bool is_new_dart_segment(Edge* e);
109 :
110 : /// returns true if the specified edge is a segment and connects a DART and a SHELL vertex
111 : bool is_dart_shell_segment(Edge* e);
112 :
113 : /// returns true if the face can be classified
114 : /** Faces which contain two shell vertices whose subtended angle is small
115 : * are not classifiable.*/
116 : bool is_classifiable(Face* f);
117 :
118 : ////////////////////////////////////////////////////////////////
119 : // CANDIDATES
120 : /** candidates are used during MakeDelaunay to define the set of edges which
121 : * may have to be swapped to obtain a delaunay triangulation.
122 : * \{ */
123 0 : bool is_candidate(Edge* e) {return m_aaCandidateEDGE[e];}
124 : void push_candidate(Edge* e);
125 : Edge* pop_candidate();
126 0 : bool candidates_left() {return !m_qEdgeCandidates.empty();}
127 : /** \} */
128 :
129 : /// newly created edges will be recorded as possible new candidates
130 : /** All newly created edges will be added to a list of possible candidates,
131 : * however, they are not added to the list of candidates until stop_candidate_recording()
132 : * has been called. This is important since recorded possible candidates may be erased
133 : * again from the grid (opposed to real candidates, which may not be erased).*/
134 : void start_candidate_recording();
135 :
136 : /// stops candidate recording and pushes all valid recorded edges to the list of real candidates
137 : void stop_candidate_recording();
138 :
139 :
140 : ////////////////////////////////////////////////////////////////
141 : // FACE-CLASSIFICATION
142 : /** Face classification is used to define and order the set of faces which
143 : * whose circumcenter may have to be inserted in order to obtain a delaunay-
144 : * triangulation with prescribed minimal angle during QualityGridGeneration.
145 : * Face classification is not required for MakeDelaunay.
146 : * \{ */
147 : bool classified_faces_left();
148 : Face* pop_classified_face();
149 0 : bool face_classification_enabled() {return m_aaFaceInfo.valid();}
150 : void enable_face_classification(number minAngle);
151 :
152 0 : number min_angle() const {return m_minAngle;}
153 0 : number max_dot() const {return m_maxDot;}
154 : /** \} */
155 :
156 : ////////////////////////////////////////////////////////////////
157 : // GRID-OBERSERVER CALLBACKS
158 : virtual void vertex_created(Grid* grid, Vertex* vrt,
159 : GridObject* pParent,
160 : bool replacesParent);
161 :
162 : virtual void edge_created(Grid* grid, Edge* e,
163 : GridObject* pParent,
164 : bool replacesParent);
165 :
166 : virtual void face_created(Grid* grid, Face* f,
167 : GridObject* pParent,
168 : bool replacesParent);
169 :
170 :
171 : virtual void edge_to_be_erased(Grid* grid, Edge* e, Edge* replacedBy);
172 :
173 : virtual void face_to_be_erased(Grid* grid, Face* f, Face* replacedBy);
174 :
175 : private:
176 : struct FaceInfo{
177 0 : FaceInfo() : f(NULL), priority(0), classified(false) {}
178 : Face* f;
179 : number priority;
180 : bool classified;
181 : };
182 :
183 : struct CompareFaceInfo{
184 0 : bool operator()(const FaceInfo* fi1, const FaceInfo* fi2) const
185 : {
186 0 : return fi1->priority < fi2->priority;
187 : }
188 : };
189 :
190 : typedef Attachment<FaceInfo*> AFaceInfo;
191 :
192 : typedef std::priority_queue<FaceInfo*, std::vector<FaceInfo*>,
193 : CompareFaceInfo>
194 : FacePriorityQueue;
195 :
196 :
197 : bool is_classified(Face* f);
198 : bool classify_face(Face* f);
199 :
200 : private:
201 : Grid& m_grid;
202 : AAPos m_aaPos;
203 :
204 : AByte m_aMark;
205 : MultiElementAttachmentAccessor<AByte> m_aaMark;
206 :
207 : AFaceInfo m_aFaceInfo;
208 : Grid::AttachmentAccessor<Face, AFaceInfo> m_aaFaceInfo;
209 : FacePriorityQueue m_faceQueue;
210 :
211 : number m_minAngle;
212 : number m_maxDot;
213 : Grid::edge_traits::callback m_cbConstrainedEdge;
214 :
215 : // candidate edges
216 : ABool m_aCandidate;
217 : Grid::AttachmentAccessor<Edge, ABool> m_aaCandidateEDGE;
218 : std::queue<Edge*> m_qEdgeCandidates;
219 :
220 : // helper vector used during start/stop_candidate_recording
221 : bool m_candidateRecordingEnabled;
222 : std::vector<Edge*> m_recordedCandidates;
223 : };
224 :
225 : }// end of namespace
226 :
227 :
228 : ////////////////////////////////////////
229 : // include implementation
230 : #include "delaunay_info_impl.h"
231 :
232 :
233 : #endif //__H__UG_delaunay_info
|
