Loading [MathJax]/extensions/tex2jax.js
ug4
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
ntree_traverser.h
Go to the documentation of this file.
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
41namespace ug{
42
43template <class tree_t>
45{
46 public:
49
50 void begin_traversal(const tree_t& tree)
51 {
53 }
54
55 int visit_up(const tree_t& tree, size_t node)
56 {
57 if(tree.num_child_nodes(node) == 0){
58 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 size_t result() const {return m_lowestLeafNodeLvl;}
69
70 private:
72};
73
74template <class tree_t>
75size_t FindLowestLeafNodeLevel(const tree_t& tree)
76{
78 TraverseBreadthFirst(tree, trav);
79 return trav.result();
80}
81
82
84template <class tree_t>
86{
87 public:
91
92 void begin_traversal(const tree_t& tree)
93 {
95 m_elemCount = 0;
96 m_firstEval = true;
97 }
98
99 int visit_up(const tree_t& tree, size_t node)
100 {
101 if(tree.level(node) == m_lvl)
102 m_elemCount = 0;
103
104 if(tree.level(node) >= m_lvl)
105 m_elemCount += tree.num_elements(node);
106
107 return TRAVERSE_CHILDREN;
108 }
109
110 void visit_down(const tree_t& tree, size_t node)
111 {
112 if(tree.level(node) == m_lvl){
113 if(m_firstEval){
115 m_firstEval = false;
116 }
117 else{
120 }
121 }
122 }
123
124 void end_traversal(const tree_t&) {}
125
126 size_t min_num_elements() const {return m_minNumElements;}
127 size_t max_num_elements() const {return m_maxNumElements;}
128
129 private:
130 size_t m_lvl;
135};
136
137template <class tree_t>
138std::pair<size_t, size_t> GetMinMaxNumElements(const tree_t& tree, size_t lvl)
139{
141 TraverseDepthFirst(tree, trav);
142 return std::make_pair(trav.min_num_elements(), trav.max_num_elements());
143}
144
145
146template <class tree_t>
148{
149 public:
150 typedef typename tree_t::elem_t elem_t;
151 typedef typename tree_t::vector_t vector_t;
152
154 m_point(point),
155 m_foundElem(false)
156 {}
157
158 void begin_traversal(const tree_t& tree)
159 {
160 m_foundElem = false;
162 }
163
164 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 if(!tree_t::traits::box_contains_point(tree.bounding_box(node), m_point))
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 iter != tree.elems_end(node); ++iter)
177 {
179 if(tree_t::traits::contains_point(*iter, m_point, tree.common_data())){
180 m_foundElem = true;
181 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 if(m_foundElem)
196 foundElemOut = m_elem;
197 return m_foundElem;
198 }
199
200 size_t num_elems_checked() const {return m_numElemsChecked;}
201
202 private:
207};
208
209template <class tree_t>
210bool FindContainingElement(typename tree_t::elem_t& elemOut, const tree_t& tree,
211 const typename tree_t::vector_t& point)
212{
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 elemOut = tmpElem;
219 return true;
220 }
221 return false;
222}
223
224
225template <class tree_t>
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
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))
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:
270 std::vector<elem_t> m_foundElems;
271};
272
273template <class tree_t>
274bool FindElementsInIntersectingNodes(std::vector<typename tree_t::elem_t>& elemsOut,
275 const tree_t& tree,
276 const typename tree_t::box_t& bbox)
277{
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
308template <class TElem>
310{
312 RayElemIntersectionRecord(number _smin, number _smax, TElem _elem) :
313 smin(_smin), smax(_smax), elem(_elem) {}
314
317 TElem elem;
318};
319
320template <class tree_t>
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;
328
330 const vector_t rayDir,
331 const number small = 1.e-12) :
332 m_rayFrom(rayFrom),
333 m_rayDir(rayDir),
334 m_small(small)
335 {}
336
337 void begin_traversal(const tree_t& tree)
338 {
339 m_intersections.clear();
340 }
341
342 int visit_up(const tree_t& tree, size_t node)
343 {
344 box_t box = tree.bounding_box(node);
345 vector_t vsmall;
346 VecSet(vsmall, m_small);
347 VecScale(vsmall, vsmall, VecLength(tree_t::traits::box_diagonal(box)));
348 tree_t::traits::grow_box(box, box, vsmall);
349
350 if(!tree_t::traits::ray_box_intersection(m_rayFrom, m_rayDir, box))
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 number smin = 0, smax = 0;
358 for(typename tree_t::elem_iterator_t iter = tree.elems_begin(node);
359 iter != tree.elems_end(node); ++iter)
360 {
361 if(tree_t::traits::intersects_ray(
362 *iter, m_rayFrom, m_rayDir, tree.common_data(),
363 smin, smax, m_small))
364 {
365 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:
382 std::vector<intersection_record_t> m_intersections;
383};
384
385template <class tree_t>
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 intersectionsOut = trav.result();
397 return !intersectionsOut.empty();
398}
399
400}// end of namespace
401
402#endif
Definition ntree_traverser.h:148
tree_t::vector_t vector_t
Definition ntree_traverser.h:151
void visit_down(const tree_t &, size_t)
Definition ntree_traverser.h:189
void end_traversal(const tree_t &)
Definition ntree_traverser.h:191
size_t m_numElemsChecked
Definition ntree_traverser.h:205
tree_t::elem_t elem_t
Definition ntree_traverser.h:150
int visit_up(const tree_t &tree, size_t node)
Definition ntree_traverser.h:164
Traverser_FindContainingElement(const vector_t &point)
Definition ntree_traverser.h:153
elem_t m_elem
Definition ntree_traverser.h:204
void begin_traversal(const tree_t &tree)
Definition ntree_traverser.h:158
bool result(elem_t &foundElemOut) const
Definition ntree_traverser.h:193
vector_t m_point
Definition ntree_traverser.h:203
bool m_foundElem
Definition ntree_traverser.h:206
size_t num_elems_checked() const
Definition ntree_traverser.h:200
Definition ntree_traverser.h:227
void end_traversal(const tree_t &)
Definition ntree_traverser.h:264
tree_t::box_t box_t
Definition ntree_traverser.h:231
void begin_traversal(const tree_t &tree)
Definition ntree_traverser.h:237
tree_t::elem_t elem_t
Definition ntree_traverser.h:229
Traverser_FindElementsInIntersectingNodes(const box_t &bbox)
Definition ntree_traverser.h:233
const std::vector< elem_t > & result() const
Definition ntree_traverser.h:266
std::vector< elem_t > m_foundElems
Definition ntree_traverser.h:270
int visit_up(const tree_t &tree, size_t node)
Definition ntree_traverser.h:242
box_t m_bbox
Definition ntree_traverser.h:269
void visit_down(const tree_t &, size_t)
Definition ntree_traverser.h:262
tree_t::vector_t vector_t
Definition ntree_traverser.h:230
Definition ntree_traverser.h:45
Traverser_FindLowestLeafNodeLevel()
Definition ntree_traverser.h:47
void visit_down(const tree_t &, size_t)
Definition ntree_traverser.h:64
int visit_up(const tree_t &tree, size_t node)
Definition ntree_traverser.h:55
size_t m_lowestLeafNodeLvl
Definition ntree_traverser.h:71
void end_traversal(const tree_t &)
Definition ntree_traverser.h:66
void begin_traversal(const tree_t &tree)
Definition ntree_traverser.h:50
size_t result() const
Definition ntree_traverser.h:68
returns the minimum and maximum number of elements in all subtrees of nodes of the given level
Definition ntree_traverser.h:86
size_t max_num_elements() const
Definition ntree_traverser.h:127
size_t m_maxNumElements
Definition ntree_traverser.h:132
size_t m_elemCount
Definition ntree_traverser.h:133
bool m_firstEval
Definition ntree_traverser.h:134
size_t m_minNumElements
Definition ntree_traverser.h:131
void visit_down(const tree_t &tree, size_t node)
Definition ntree_traverser.h:110
size_t m_lvl
Definition ntree_traverser.h:130
int visit_up(const tree_t &tree, size_t node)
Definition ntree_traverser.h:99
void end_traversal(const tree_t &)
Definition ntree_traverser.h:124
size_t min_num_elements() const
Definition ntree_traverser.h:126
void begin_traversal(const tree_t &tree)
Definition ntree_traverser.h:92
Traverser_MinMaxNumElements(size_t lvl)
Definition ntree_traverser.h:88
Definition ntree_traverser.h:322
Traverser_RayElementIntersection(const vector_t &rayFrom, const vector_t rayDir, const number small=1.e-12)
Definition ntree_traverser.h:329
const std::vector< intersection_record_t > & result() const
Definition ntree_traverser.h:376
tree_t::box_t box_t
Definition ntree_traverser.h:326
RayElemIntersectionRecord< elem_t > intersection_record_t
Definition ntree_traverser.h:327
vector_t m_rayFrom
Definition ntree_traverser.h:379
tree_t::elem_t elem_t
Definition ntree_traverser.h:324
tree_t::vector_t vector_t
Definition ntree_traverser.h:325
void end_traversal(const tree_t &)
Definition ntree_traverser.h:374
std::vector< intersection_record_t > m_intersections
Definition ntree_traverser.h:382
void visit_down(const tree_t &, size_t)
Definition ntree_traverser.h:372
const number m_small
Definition ntree_traverser.h:381
int visit_up(const tree_t &tree, size_t node)
Definition ntree_traverser.h:342
void begin_traversal(const tree_t &tree)
Definition ntree_traverser.h:337
vector_t m_rayDir
Definition ntree_traverser.h:380
double number
Definition types.h:124
vector_t::value_type VecLength(const vector_t &v)
returns the length of v. Slower than VecLengthSq.
Definition math_vector_functions_common_impl.hpp:341
void VecSet(vector_t &vInOut, typename vector_t::value_type s)
Set each vector component to scalar (componentwise)
Definition math_vector_functions_common_impl.hpp:539
void VecScale(vector_t &vOut, const vector_t &v, typename vector_t::value_type s)
scales a MathVector<N>
Definition math_vector_functions_common_impl.hpp:252
the ug namespace
size_t FindLowestLeafNodeLevel(const tree_t &tree)
Definition ntree_traverser.h:75
bool FindElementsInIntersectingNodes(std::vector< typename tree_t::elem_t > &elemsOut, const tree_t &tree, const typename tree_t::box_t &bbox)
Definition ntree_traverser.h:274
bool RayElementIntersections(std::vector< RayElemIntersectionRecord< typename tree_t::elem_t > > &intersectionsOut, const tree_t &tree, const typename tree_t::vector_t &rayFrom, const typename tree_t::vector_t &rayDir, const number small=1.e-12)
Definition ntree_traverser.h:386
@ ABORT_TRAVERSAL
Definition ntree_traversal.h:41
@ DONT_TRAVERSE_CHILDREN
Definition ntree_traversal.h:39
@ TRAVERSE_CHILDREN
Definition ntree_traversal.h:40
void TraverseDepthFirst(const tree_t &tree, traverser_t &traverser)
Definition ntree_traversal.h:107
bool FindContainingElement(typename tree_t::elem_t &elemOut, const tree_t &tree, const typename tree_t::vector_t &point)
Definition ntree_traverser.h:210
std::pair< size_t, size_t > GetMinMaxNumElements(const tree_t &tree, size_t lvl)
Definition ntree_traverser.h:138
void TraverseBreadthFirst(const tree_t &tree, traverser_t &traverser)
Definition ntree_traversal.h:45
Definition ntree_traverser.h:310
number smin
relative coordinate where the ray enters the element
Definition ntree_traverser.h:315
RayElemIntersectionRecord(number _smin, number _smax, TElem _elem)
Definition ntree_traverser.h:312
TElem elem
the element that was intersected
Definition ntree_traverser.h:317
number smax
relative coordinate where the ray leaves the element. May be equal to smin.
Definition ntree_traverser.h:316
RayElemIntersectionRecord()
Definition ntree_traverser.h:311