libgenua
Basic Geometry, Numerical Algorithms and Interfaces
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Groups Pages
mxelementtree.h
1 
2 /* Copyright (C) 2015 David Eller <david@larosterna.com>
3  *
4  * Commercial License Usage
5  * Licensees holding valid commercial licenses may use this file in accordance
6  * with the terms contained in their respective non-exclusive license agreement.
7  * For further information contact david@larosterna.com .
8  *
9  * GNU General Public License Usage
10  * Alternatively, this file may be used under the terms of the GNU General
11  * Public License version 3.0 as published by the Free Software Foundation and
12  * appearing in the file gpl.txt included in the packaging of this file.
13  */
14 
15 #ifndef GENUA_MXELEMENTTREE_H
16 #define GENUA_MXELEMENTTREE_H
17 
18 #include "kdop.h"
19 #include "implicittree.h"
20 #include "mxmesh.h"
21 
32 {
33 public:
34 
35  typedef Dop3d3<Real> DopType;
36 
39 
41  void allocate(MxMeshPtr pm, uint mincount = 8);
42 
44  void allocateSections(MxMeshPtr pm, const Indices & sects, uint mincount = 8);
45 
47  void sort();
48 
50  uint minElemCount() const {return itree.minSize();}
51 
53  uint nelements() const {return elix.size();}
54 
56  MxMeshPtr mesh() {return pmx;}
57 
59  DopType & dop(uint k) {
60  assert(k < bvol.size());
61  return bvol[k];
62  }
63 
65  const Vct3 & point(uint k) const {return pmx->node(k);}
66 
68  uint mappedIndex(uint k) const {
69  assert(k < elix.size());
70  return elix[k];
71  }
72 
74  const uint *mappedElement(uint k, uint & nv, uint & isec) const {
75  assert(pmx);
76  return pmx->globalElement(elix[k], nv, isec);
77  }
78 
80  uint nearest(const Vct3 & p) const;
81 
83  bool find(const Vct3 & p, Real radius, Indices & eix) const;
84 
85 private:
86 
88  Real elementDistance(const Vct3 & p, uint k) const;
89 
91  Real edTri3(const Vct3 & p, const uint *vi) const;
92 
93  template <int N>
94  Real edMultiTri3(const Vct3 &p, const uint map[], const uint vi[]) const
95  {
96  Real mindst = std::numeric_limits<Real>::max();
97  uint w[3];
98  for (int i=0; i<N; ++i) {
99  for (int k=0; k<3; ++k)
100  w[k] = vi[ map[3*i+k] ];
101  Real dsq = this->edTri3(p, w);
102  mindst = std::min(dsq, mindst);
103  }
104  return mindst;
105  }
106 
107 private:
108 
110  MxMeshPtr pmx;
111 
114 
116  Indices elix;
117 
119  std::vector<DopType> bvol;
120 };
121 
137 {
138 public:
139 
140  typedef Dop3d3<float> DopType;
141 
142  struct Subset {
143  Indices elementList;
144  uint isection;
145  bool operator== (const Subset &a) const {return isection == a.isection;}
146  bool operator< (const Subset &a) const {return isection < a.isection;}
147  bool operator< (uint a) const {return isection < a;}
148  };
149 
150  typedef std::vector<Subset> SubsetArray;
151 
152  // only here because MSVC 2008 does not find the operator< in struct Subset
153  struct SubsetCompare {
154  bool operator() (const Subset &a, const Subset &b) const {
155  return a.isection < b.isection;
156  }
157  bool operator() (const Subset &a, uint b) const {
158  return a.isection < b;
159  }
160  bool operator() (uint a, const Subset &b) const {
161  return a < b.isection;
162  }
163  };
164 
166  MxTriTree(uint mincount = 4) : m_mincount(mincount) {}
167 
169  void build(const MxMesh &msh);
170 
172  void build(const MxMesh &msh, const Indices &sections);
173 
175  void build(const MxMesh &msh, const SubsetArray &sba);
176 
178  void build(const PointList<3,float> &pts, const Indices &tri);
179 
181  void build(const PointList<3,double> &pts, const Indices &tri);
182 
184  const Indices & globalNodes() const {return m_gnix;}
185 
187  uint nearestTriangle(const Vct3 & p) const {return nearestTriangle(Vct3f(p));}
188 
190  uint nearestTriangle(const Vct3f & pf) const;
191 
193  bool projection(const Vct3 &p, uint nodes[], float coef[]) const;
194 
196  void projection(const PointList<3> &vtx, const Indices &imap,
197  CsrMatrix<float,1> &op, uint ncol = 0) const;
198 
200  bool empty() const {return m_tri.empty();}
201 
203  uint ntriangles() const {return m_tri.size()/3;}
204 
206  const uint *vertices(uint k) const {
207  assert(3*k+2 < m_tri.size());
208  return &m_tri[3*k];
209  }
210 
212  uint nvertices() const {return m_vtx.size();}
213 
215  const Vct3f & vertex(uint k) const {return m_vtx[k];}
216 
218  DopType & dop(uint k) {
219  assert(k < m_dop.size());
220  return m_dop[k];
221  }
222 
224  const DopType & dop(uint k) const {
225  assert(k < m_dop.size());
226  return m_dop[k];
227  }
228 
230  uint triangleIndex(uint k) const {return m_itree.index(k);}
231 
233  uint globalElement(uint itri) const {
234  assert(itri < m_gelix.size());
235  return m_gelix[itri];
236  }
237 
239  void offsetRange(uint k, uint & beg, uint & end) const {
240  m_itree.offsetRange(k, beg, end);
241  }
242 
244  bool leaf(uint inode) const {
245  return m_itree.rightChild(inode) >= m_dop.size();
246  }
247 
249  uint leftChild(uint inode) const { return m_itree.leftChild(inode); }
250 
252  uint rightChild(uint inode) const { return m_itree.rightChild(inode); }
253 
255  uint minElemCount() const {return m_mincount;}
256 
258  void clear();
259 
261  void dump(const std::string &fname) const;
262 
263 private:
264 
266  void sort();
267 
269  void splitElements(const MxMesh &msh, uint isec,
270  const Indices &elix = Indices());
271 
273  float tridist(uint itri, const Vct3f &pf) const;
274 
275 private:
276 
279 
281  Indices m_tri;
282 
284  Indices m_gnix;
285 
287  Indices m_gelix;
288 
291 
293  std::vector<DopType> m_dop;
294 
297 };
298 
299 #endif // MXELEMENTTREE_H
uint ntriangles() const
number of triangles
Definition: mxelementtree.h:203
uint size() const
vector length
Definition: point.h:445
MxMeshPtr pmx
pointer to mesh to use
Definition: mxelementtree.h:110
DopType & dop(uint k)
access bounding volume
Definition: mxelementtree.h:59
uint leftChild(uint k) const
left child node index
Definition: implicittree.h:115
bool leaf(uint inode) const
test whether node inode is a leaf node
Definition: mxelementtree.h:244
bool find(const Vct3 &p, Real radius, Indices &eix) const
find all surface elements within radius r of p
Definition: mxelementtree.cpp:256
Real elementDistance(const Vct3 &p, uint k) const
determine distance of p from element k
Definition: mxelementtree.cpp:315
MxElementTree()
empty tree
Definition: mxelementtree.h:38
PointList< 3, float > m_vtx
vertices indexed by triangles
Definition: mxelementtree.h:278
uint minElemCount() const
minimum number of elements in node
Definition: mxelementtree.h:255
DopType & dop(uint k)
access bounding volume for a single node
Definition: mxelementtree.h:218
void allocate(MxMeshPtr pm, uint mincount=8)
allocate tree for all elements in the entire mesh
Definition: mxelementtree.cpp:124
const DopType & dop(uint k) const
access bounding volume for a single node
Definition: mxelementtree.h:224
bool offsetRange(uint k, uint &ibegin, uint &iend) const
extract range of valid indices, relies on NotFound sorted back
Definition: implicittree.h:170
uint m_mincount
minimum number of triangles in node
Definition: mxelementtree.h:296
bool empty() const
true if no triangles present in tree
Definition: mxelementtree.h:200
const uint * mappedElement(uint k, uint &nv, uint &isec) const
access element vertices through mapping
Definition: mxelementtree.h:74
uint mappedIndex(uint k) const
access element mapping
Definition: mxelementtree.h:68
ImplicitTree itree
binary tree
Definition: mxelementtree.h:113
uint rightChild(uint k) const
left child node index
Definition: implicittree.h:118
std::vector< DopType > m_dop
bounding volumes
Definition: mxelementtree.h:293
Mesh with dissimilar elements.
Definition: mxmesh.h:48
uint rightChild(uint inode) const
left child of node inode
Definition: mxelementtree.h:252
Balanced binary tree using implicit references to content.
Definition: implicittree.h:66
MxTriTree(uint mincount=4)
empty tree
Definition: mxelementtree.h:166
void build(const MxMesh &msh)
gather all surface elements (shell elements)
Definition: mxelementtree.cpp:415
void splitElements(const MxMesh &msh, uint isec, const Indices &elix=Indices())
split all elements of a given section into triangles
Definition: mxelementtree.cpp:563
const Vct3 & point(uint k) const
access mesh node
Definition: mxelementtree.h:65
Indices elix
element indices used in tree
Definition: mxelementtree.h:116
const Vct3f & vertex(uint k) const
access vertex k
Definition: mxelementtree.h:215
uint index(uint k) const
access index
Definition: implicittree.h:126
bool projection(const Vct3 &p, uint nodes[], float coef[]) const
determine projection coefficients for a single point (thread-safe)
Definition: mxelementtree.cpp:737
Axis-aligned 3D bounding box expressed as a k-DOP.
Definition: forward.h:465
float tridist(uint itri, const Vct3f &pf) const
distance of point to its projection on triangle
Definition: mxelementtree.cpp:642
const Indices & globalNodes() const
access set of global node indices used
Definition: mxelementtree.h:184
uint triangleIndex(uint k) const
triangle index from tree node index
Definition: mxelementtree.h:230
uint nvertices() const
number of vertices stored
Definition: mxelementtree.h:212
uint globalElement(uint itri) const
global element index from triangle index
Definition: mxelementtree.h:233
void offsetRange(uint k, uint &beg, uint &end) const
access index offset range for node k
Definition: mxelementtree.h:239
void sort()
sort entire tree, computes bounding volumes
Definition: mxelementtree.cpp:163
Element seach tree for deformation mapping.
Definition: mxelementtree.h:136
void allocateSections(MxMeshPtr pm, const Indices &sects, uint mincount=8)
allocate tree for sections listed
Definition: mxelementtree.cpp:137
std::vector< DopType > bvol
bounding volumes for nodes
Definition: mxelementtree.h:119
uint minElemCount() const
access minimum element count per node
Definition: mxelementtree.h:50
ImplicitTree m_itree
balanced binary tree
Definition: mxelementtree.h:290
MxMeshPtr mesh()
access stored mesh
Definition: mxelementtree.h:56
Indices m_gnix
global node indices of the vertices in m_vtx
Definition: mxelementtree.h:284
Compressed-row sparse matrix.
Definition: csrmatrix.h:68
Element search tree for MxMesh.
Definition: mxelementtree.h:31
void dump(const std::string &fname) const
write projection surface as a mesh (for debugging)
Definition: mxelementtree.cpp:870
Real edTri3(const Vct3 &p, const uint *vi) const
distance of p from Tri3
Definition: mxelementtree.cpp:342
uint leftChild(uint inode) const
left child of node inode
Definition: mxelementtree.h:249
Indices m_tri
triangles vertices mapping m_vtx
Definition: mxelementtree.h:281
uint nelements() const
number of elements searched
Definition: mxelementtree.h:53
Indices m_gelix
global element indices for the triangles in m_tri
Definition: mxelementtree.h:287
const uint * vertices(uint k) const
access vertex indices of triangle k
Definition: mxelementtree.h:206
uint nearestTriangle(const Vct3 &p) const
identify triangle nearest to p (thread-safe)
Definition: mxelementtree.h:187
void clear()
remove all triangles
Definition: mxelementtree.cpp:860
uint nearest(const Vct3 &p) const
locate surface element which is nearest to point p
Definition: mxelementtree.cpp:169
void sort()
allocate and sort tree
Definition: mxelementtree.cpp:845
uint minSize() const
minimum number of items in node
Definition: implicittree.h:107