libsurf
Programmer's Documentation

facetree.h (r6227/r5385)
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 SURF_FACETREE_H
16 #define SURF_FACETREE_H
17 
18 #include <genua/sharedvector.h>
19 #include <genua/trimesh.h>
20 #include <genua/bounds.h>
21 #include <genua/plane.h>
22 #include "edgefaceisec.h"
23 
24 
38 class FaceTree
39 {
40 public:
41 
43  class Segment {
44  public:
45 
47  bool intersects(const TriFace & f, const Plane & pln) {
48  return f.intersect(pln, src, trg);
49  }
50 
52  Vct3 projection(const Vct3 & pt) const {
53  Vct3 d(trg - src);
54  Real t = dot( pt-src, d ) / dot(d, d);
55  if (t <= 0.0)
56  return src;
57  else if (t >= 1.0)
58  return trg;
59  else
60  return (src + t*d);
61  }
62 
63  public:
64 
66  Vct3 src, trg;
67 
69  int iface;
70  };
71 
72 public:
73 
75  typedef boost::shared_ptr<FaceTree> FaceTreePtr;
76  typedef std::vector<FaceTree::Segment> SegmentArray;
77 
79  FaceTree() : srf(0), level(0) {}
80 
82  FaceTree(const TriMesh & t);
83 
85  bool isLeaf() const {return (lft == 0) and (rgt == 0);}
86 
88  const FaceTree & left() const {return *lft;}
89 
91  const FaceTree & right() const {return *rgt;}
92 
94  uint nfaces() const {return idx.size();}
95 
97  const TriFace & face(uint i) const {
98  assert(i < idx.size());
99  return faces[idx[i]];
100  }
101 
103  const TriEdge & edge(uint i) const {return srf->edge(i);}
104 
106  void split(uint depth, uint npmin);
107 
109  bool bbintersects(const FaceTree & other) const {
110  return bb.intersects(other.bb);
111  }
112 
114  uint intersect(const FaceTree & other, FaceIsecMap & m) const;
115 
117  uint selfIntersect(FaceIsecMap & m) const;
118 
120  void collectEdges(Indices & eix) const;
121 
123  void intersectPlane(const Plane & pln, Indices & ifaces) const;
124 
126  void intersectPlane(const Plane & pln, SegmentArray & segments) const;
127 
128 private:
129 
131  FaceTree(const FaceArray & fcs, const Indices & ix, uint lv);
132 
134  void init();
135 
137  void fork();
138 
140  bool isLeft(const TriFace & f) const;
141 
142 private:
143 
145  FaceTreePtr lft, rgt;
146 
149 
151  Indices idx;
152 
154  const TriMesh *srf;
155 
157  Vct3 ctr, pcp;
158 
161 
163  uint level;
164 };
165 
166 #endif
167 
BndBox bb
bounding box
Definition: facetree.h:160
bool intersects(const BndBox &other) const
void collectEdges(Indices &eix) const
collect edge indices
Definition: facetree.cpp:131
Intersection between triangle and plane.
Definition: facetree.h:43
uint level
tree depth
Definition: facetree.h:163
const FaceTree & left() const
access left sibling
Definition: facetree.h:88
const FaceTree & right() const
access right sibling
Definition: facetree.h:91
Vct3 projection(const Vct3 &pt) const
compute projection of point on segment
Definition: facetree.h:52
uint intersect(const FaceTree &other, FaceIsecMap &m) const
determine face-edge intersections
Definition: facetree.cpp:145
void split(uint depth, uint npmin)
split recursively
Definition: facetree.cpp:121
uint selfIntersect(FaceIsecMap &m) const
determine the number of self-intersections
Definition: facetree.cpp:208
void intersectPlane(const Plane &pln, Indices &ifaces) const
collect faces intersected by plane pln
Definition: facetree.cpp:252
Indices idx
indices for this node
Definition: facetree.h:151
Vct3 src
intersection points
Definition: facetree.h:66
Vct3 ctr
center and principal direction
Definition: facetree.h:157
int iface
tag associated with the face
Definition: facetree.h:69
const TriEdge & edge(uint i) const
access edge
Definition: facetree.h:103
bool intersect(const Plane &pln, Vct3 &src, Vct3 &trg) const
FaceArray faces
shared array of faces, data stored in/owned by root node
Definition: facetree.h:148
bool isLeft(const TriFace &f) const
check if face belongs to the left child node
Definition: facetree.cpp:83
void init()
initialize geometric properties
Definition: facetree.cpp:38
Binary tree for triangles.
Definition: facetree.h:38
const TriFace & face(uint i) const
access face
Definition: facetree.h:97
void fork()
create child nodes
Definition: facetree.cpp:99
bool bbintersects(const FaceTree &other) const
check bounding box intersection
Definition: facetree.h:109
FaceTreePtr lft
children
Definition: facetree.h:145
bool isLeaf() const
check if this is a leaf node
Definition: facetree.h:85
const TriMesh * srf
associated mesh
Definition: facetree.h:154
FaceTree()
empty constructor
Definition: facetree.h:79
bool intersects(const TriFace &f, const Plane &pln)
return whether face intersects plane
Definition: facetree.h:47
const TriEdge & edge(uint i) const
uint nfaces() const
count faces belonging to this tree
Definition: facetree.h:94
Generated on Wed Jan 19 2022 03:03:15 for libsurf by   doxygen 1.8.5