Line data Source code
1 : /*
2 : * Copyright (c) 2013-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__ntree_traverser__
34 : #define __H__UG__ntree_traverser__
35 :
36 : #include <algorithm>
37 : #include <utility>
38 : #include <vector>
39 : #include "ntree_traversal.h"
40 :
41 : namespace ug{
42 :
43 : template <class tree_t>
44 : class Traverser_FindLowestLeafNodeLevel
45 : {
46 : public:
47 0 : Traverser_FindLowestLeafNodeLevel() :
48 0 : m_lowestLeafNodeLvl(0) {}
49 :
50 : void begin_traversal(const tree_t& tree)
51 : {
52 0 : m_lowestLeafNodeLvl = 0;
53 0 : }
54 :
55 : int visit_up(const tree_t& tree, size_t node)
56 : {
57 : if(tree.num_child_nodes(node) == 0){
58 0 : m_lowestLeafNodeLvl = tree.level(node);
59 : return ABORT_TRAVERSAL;
60 : }
61 : return TRAVERSE_CHILDREN;
62 : }
63 :
64 : void visit_down(const tree_t&, size_t) {}
65 :
66 : void end_traversal(const tree_t&) {}
67 :
68 0 : size_t result() const {return m_lowestLeafNodeLvl;}
69 :
70 : private:
71 : size_t m_lowestLeafNodeLvl;
72 : };
73 :
74 : template <class tree_t>
75 : size_t FindLowestLeafNodeLevel(const tree_t& tree)
76 : {
77 : Traverser_FindLowestLeafNodeLevel<tree_t> trav;
78 0 : TraverseBreadthFirst(tree, trav);
79 : return trav.result();
80 : }
81 :
82 :
83 : /// returns the minimum and maximum number of elements in all subtrees of nodes of the given level
84 : template <class tree_t>
85 : class Traverser_MinMaxNumElements
86 : {
87 : public:
88 0 : Traverser_MinMaxNumElements(size_t lvl) :
89 0 : m_lvl(lvl), m_minNumElements(0), m_maxNumElements(0),
90 0 : m_elemCount(0), m_firstEval(true) {}
91 :
92 : void begin_traversal(const tree_t& tree)
93 : {
94 : m_minNumElements = m_maxNumElements = 0;
95 : m_elemCount = 0;
96 : m_firstEval = true;
97 : }
98 :
99 : int visit_up(const tree_t& tree, size_t node)
100 : {
101 0 : if(tree.level(node) == m_lvl)
102 0 : m_elemCount = 0;
103 :
104 0 : if(tree.level(node) >= m_lvl)
105 0 : m_elemCount += tree.num_elements(node);
106 :
107 : return TRAVERSE_CHILDREN;
108 : }
109 :
110 0 : void visit_down(const tree_t& tree, size_t node)
111 : {
112 0 : if(tree.level(node) == m_lvl){
113 0 : if(m_firstEval){
114 0 : m_minNumElements = m_maxNumElements= m_elemCount;
115 0 : m_firstEval = false;
116 : }
117 : else{
118 0 : m_minNumElements = std::min(m_minNumElements, m_elemCount);
119 0 : m_maxNumElements = std::max(m_maxNumElements, m_elemCount);
120 : }
121 : }
122 0 : }
123 :
124 : void end_traversal(const tree_t&) {}
125 :
126 0 : size_t min_num_elements() const {return m_minNumElements;}
127 0 : size_t max_num_elements() const {return m_maxNumElements;}
128 :
129 : private:
130 : size_t m_lvl;
131 : size_t m_minNumElements;
132 : size_t m_maxNumElements;
133 : size_t m_elemCount;
134 : bool m_firstEval;
135 : };
136 :
137 : template <class tree_t>
138 0 : std::pair<size_t, size_t> GetMinMaxNumElements(const tree_t& tree, size_t lvl)
139 : {
140 : Traverser_MinMaxNumElements<tree_t> trav(lvl);
141 : TraverseDepthFirst(tree, trav);
142 0 : return std::make_pair(trav.min_num_elements(), trav.max_num_elements());
143 : }
144 :
145 :
146 : template <class tree_t>
147 : class Traverser_FindContainingElement
148 : {
149 : public:
150 : typedef typename tree_t::elem_t elem_t;
151 : typedef typename tree_t::vector_t vector_t;
152 :
153 0 : Traverser_FindContainingElement(const vector_t& point) :
154 : m_point(point),
155 0 : m_foundElem(false)
156 : {}
157 :
158 : void begin_traversal(const tree_t& tree)
159 : {
160 : m_foundElem = false;
161 0 : m_numElemsChecked = 0;
162 : }
163 :
164 0 : int visit_up(const tree_t& tree, size_t node)
165 : {
166 : // if the point doesn't lie in the node's bounding box, we don't have
167 : // to check it's elements at all.
168 0 : if(!tree_t::traits::box_contains_point(tree.bounding_box(node), m_point))
169 : return DONT_TRAVERSE_CHILDREN;
170 :
171 : // first check whether the nodes box contains the given point
172 : if(tree.num_child_nodes(node) == 0){
173 : // iterate over all elements. If an element contains the given point,
174 : // we're done and we may return.
175 : for(typename tree_t::elem_iterator_t iter = tree.elems_begin(node);
176 0 : iter != tree.elems_end(node); ++iter)
177 : {
178 0 : ++m_numElemsChecked;
179 0 : if(tree_t::traits::contains_point(*iter, m_point, tree.common_data())){
180 0 : m_foundElem = true;
181 0 : m_elem = *iter;
182 : return ABORT_TRAVERSAL;
183 : }
184 : }
185 : }
186 : return TRAVERSE_CHILDREN;
187 : }
188 :
189 : void visit_down(const tree_t&, size_t) {}
190 :
191 : void end_traversal(const tree_t&) {}
192 :
193 : bool result(elem_t& foundElemOut) const
194 : {
195 0 : if(m_foundElem)
196 0 : foundElemOut = m_elem;
197 : return m_foundElem;
198 : }
199 :
200 : size_t num_elems_checked() const {return m_numElemsChecked;}
201 :
202 : private:
203 : vector_t m_point;
204 : elem_t m_elem;
205 : size_t m_numElemsChecked;
206 : bool m_foundElem;
207 : };
208 :
209 : template <class tree_t>
210 0 : bool FindContainingElement(typename tree_t::elem_t& elemOut, const tree_t& tree,
211 : const typename tree_t::vector_t& point)
212 : {
213 : Traverser_FindContainingElement<tree_t> trav(point);
214 : TraverseDepthFirst(tree, trav);
215 : //UG_LOG("num elems checked for one pick: " << trav.num_elems_checked() << "\n");
216 : typename tree_t::elem_t tmpElem;
217 : if(trav.result(tmpElem)){
218 0 : elemOut = tmpElem;
219 0 : return true;
220 : }
221 : return false;
222 : }
223 :
224 :
225 : template <class tree_t>
226 : class Traverser_FindElementsInIntersectingNodes
227 : {
228 : public:
229 : typedef typename tree_t::elem_t elem_t;
230 : typedef typename tree_t::vector_t vector_t;
231 : typedef typename tree_t::box_t box_t;
232 :
233 : Traverser_FindElementsInIntersectingNodes(const box_t& bbox) :
234 : m_bbox(bbox)
235 : {}
236 :
237 : void begin_traversal(const tree_t& tree)
238 : {
239 : m_foundElems.clear();
240 : }
241 :
242 : int visit_up(const tree_t& tree, size_t node)
243 : {
244 : // if our bounding box doesn't intersect the nodes bounding box,
245 : // then there's nothing to do
246 : if(!tree_t::traits::box_box_intersection(tree.bounding_box(node), m_bbox))
247 : return DONT_TRAVERSE_CHILDREN;
248 :
249 : // first check whether the nodes box contains the given point
250 : if(tree.num_child_nodes(node) == 0){
251 : // iterate over all elements. If an element contains the given point,
252 : // we're done and we may return.
253 : for(typename tree_t::elem_iterator_t iter = tree.elems_begin(node);
254 : iter != tree.elems_end(node); ++iter)
255 : {
256 : m_foundElems.push_back(*iter);
257 : }
258 : }
259 : return TRAVERSE_CHILDREN;
260 : }
261 :
262 : void visit_down(const tree_t&, size_t) {}
263 :
264 : void end_traversal(const tree_t&) {}
265 :
266 : const std::vector<elem_t>& result() const {return m_foundElems;}
267 :
268 : private:
269 : box_t m_bbox;
270 : std::vector<elem_t> m_foundElems;
271 : };
272 :
273 : template <class tree_t>
274 : bool FindElementsInIntersectingNodes(std::vector<typename tree_t::elem_t>& elemsOut,
275 : const tree_t& tree,
276 : const typename tree_t::box_t& bbox)
277 : {
278 : Traverser_FindElementsInIntersectingNodes<tree_t> trav(bbox);
279 : TraverseDepthFirst(tree, trav);
280 : //UG_LOG("num elems checked for one pick: " << trav.num_elems_checked() << "\n");
281 : elemsOut = trav.result();
282 : return !elemsOut.empty();
283 : }
284 :
285 :
286 :
287 : // template <class TVector, class TData>
288 : // class TraceRecorder {
289 : // public:
290 : // typedef TVector vector_t;
291 : // typedef TData data_t;
292 :
293 : // void clear ();
294 : // void set_ray (const vector_t& from, const vector_t& dir);
295 : // void add_point (const vector_t& p, const data_t& d);
296 : // void add_point (number t, const data_t& d);
297 :
298 : // size_t num_points () const;
299 : // const vector_t& point (size_t i) const;
300 : // const point_data& point_data (size_t i) const;
301 : // number local_point_coordinate (size_t i) const;
302 :
303 : // size_t closest_point_index () const;
304 : // size_t closest_positive_point_index () const;
305 : // size_t closest_negative_point_index () const;
306 : // };
307 :
308 : template <class TElem>
309 : struct RayElemIntersectionRecord
310 : {
311 : RayElemIntersectionRecord() {}
312 0 : RayElemIntersectionRecord(number _smin, number _smax, TElem _elem) :
313 0 : smin(_smin), smax(_smax), elem(_elem) {}
314 :
315 : number smin; ///< relative coordinate where the ray enters the element
316 : number smax; ///< relative coordinate where the ray leaves the element. May be equal to smin.
317 : TElem elem; ///< the element that was intersected
318 : };
319 :
320 : template <class tree_t>
321 0 : class Traverser_RayElementIntersection
322 : {
323 : public:
324 : typedef typename tree_t::elem_t elem_t;
325 : typedef typename tree_t::vector_t vector_t;
326 : typedef typename tree_t::box_t box_t;
327 : typedef RayElemIntersectionRecord<elem_t> intersection_record_t;
328 :
329 : Traverser_RayElementIntersection(const vector_t& rayFrom,
330 : const vector_t rayDir,
331 : const number small = 1.e-12) :
332 : m_rayFrom(rayFrom),
333 : m_rayDir(rayDir),
334 0 : m_small(small)
335 : {}
336 :
337 : void begin_traversal(const tree_t& tree)
338 : {
339 : m_intersections.clear();
340 : }
341 :
342 0 : int visit_up(const tree_t& tree, size_t node)
343 : {
344 : box_t box = tree.bounding_box(node);
345 : vector_t vsmall;
346 0 : VecSet(vsmall, m_small);
347 0 : VecScale(vsmall, vsmall, VecLength(tree_t::traits::box_diagonal(box)));
348 : tree_t::traits::grow_box(box, box, vsmall);
349 :
350 0 : if(!tree_t::traits::ray_box_intersection(m_rayFrom, m_rayDir, box))
351 : return DONT_TRAVERSE_CHILDREN;
352 :
353 : if(tree.num_child_nodes(node) == 0){
354 : // iterate over all elements. If an element intersects the given ray,
355 : // we'll record the intersection point
356 : vector_t v;
357 0 : number smin = 0, smax = 0;
358 : for(typename tree_t::elem_iterator_t iter = tree.elems_begin(node);
359 0 : iter != tree.elems_end(node); ++iter)
360 : {
361 0 : if(tree_t::traits::intersects_ray(
362 : *iter, m_rayFrom, m_rayDir, tree.common_data(),
363 0 : smin, smax, m_small))
364 : {
365 0 : m_intersections.push_back(intersection_record_t(smin, smax, *iter));
366 : }
367 : }
368 : }
369 : return TRAVERSE_CHILDREN;
370 : }
371 :
372 : void visit_down(const tree_t&, size_t) {}
373 :
374 : void end_traversal(const tree_t&) {}
375 :
376 : const std::vector<intersection_record_t>& result() const {return m_intersections;}
377 :
378 : private:
379 : vector_t m_rayFrom;
380 : vector_t m_rayDir;
381 : const number m_small;
382 : std::vector<intersection_record_t> m_intersections;
383 : };
384 :
385 : template <class tree_t>
386 0 : bool RayElementIntersections(
387 : std::vector<RayElemIntersectionRecord<typename tree_t::elem_t> >& intersectionsOut,
388 : const tree_t& tree,
389 : const typename tree_t::vector_t& rayFrom,
390 : const typename tree_t::vector_t& rayDir,
391 : const number small = 1.e-12)
392 : {
393 : Traverser_RayElementIntersection<tree_t> trav(rayFrom, rayDir, small);
394 : TraverseDepthFirst(tree, trav);
395 : //UG_LOG("num elems checked for one pick: " << trav.num_elems_checked() << "\n");
396 0 : intersectionsOut = trav.result();
397 0 : return !intersectionsOut.empty();
398 : }
399 :
400 : }// end of namespace
401 :
402 : #endif
|
