libsurf
Programmer's Documentation

dnedge.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_DNEDGE_H
16 #define SURF_DNEDGE_H
17 
28 class DnEdge
29 {
30  public:
31 
33  DnEdge(uint a, uint b) {
34  reconnect(a,b);
35  }
36 
38  void reconnect(uint a, uint b) {
39  assert(a != NotFound);
40  assert(b != NotFound);
41  if (a < b) {
42  vi[0] = a;
43  vi[1] = b;
44  } else {
45  vi[0] = b;
46  vi[1] = a;
47  }
48  nbf[1] = nbf[0] = NotFound;
49  }
50 
52  bool isValid() const {return vi[0] != NotFound;}
53 
55  void invalidate() {vi[0] = vi[1] = NotFound;}
56 
58  uint source() const {return vi[0];}
59 
61  uint target() const {return vi[1];}
62 
64  uint nNeighbors() const {
65  uint nnb(2);
66  if (nbf[0] == NotFound)
67  --nnb;
68  if (nbf[1] == NotFound)
69  --nnb;
70  return nnb;
71  }
72 
74  uint nbTriangle(uint i) const {
75  assert(i < 2);
76  return nbf[i];
77  }
78 
80  uint opposed(uint ti) const {
81  if (nbf[0] == ti)
82  return nbf[1];
83  else if (nbf[1] == ti)
84  return nbf[0];
85  else
86  return NotFound;
87  }
88 
90  uint find(uint i) const {
91  if (vi[0] == i)
92  return 0;
93  else if (vi[1] == i)
94  return 1;
95  else
96  return NotFound;
97  }
98 
100  uint attachTriangle(uint fi) {
101  if (nbf[0] == fi)
102  return 0;
103  else if (nbf[1] == fi)
104  return 1;
105  else if (nbf[0] == NotFound) {
106  nbf[0] = fi;
107  return 0;
108  } else if (nbf[1] == NotFound) {
109  nbf[1] = fi;
110  return 1;
111  } else
112  return NotFound;
113  }
114 
116  uint detachTriangle(uint fi) {
117  if (nbf[0] == fi) {
118  nbf[0] = NotFound;
119  return 0;
120  } else if (nbf[1] == fi) {
121  nbf[1] = NotFound;
122  return 1;
123  } else
124  return NotFound;
125  }
126 
128  uint replaceTriangle(uint fold, uint fnew) {
129  if (nbf[0] == fold) {
130  nbf[0] = fnew;
131  return 0;
132  } else if (nbf[1] == fold) {
133  nbf[1] = fnew;
134  return 1;
135  } else
136  return NotFound;
137  }
138 
140  bool operator< (const DnEdge & a) const {
141  if (vi[0] < a.vi[0])
142  return true;
143  else if (vi[0] > a.vi[0])
144  return false;
145  else if (vi[1] < a.vi[1])
146  return true;
147  else
148  return false;
149  }
150 
152  bool operator== (const DnEdge & a) const {
153  if (vi[0] != a.vi[0])
154  return false;
155  else if (vi[1] != a.vi[1])
156  return false;
157  else
158  return true;
159  }
160 
162  Real pIntersect(const DnVertexArray & vtx, uint a, uint b) const {
163  assert(isValid());
164  const Vct2 & p1(vtx[vi[0]].parpos());
165  const Vct2 & p2(vtx[vi[1]].parpos());
166  const Vct2 & pa(vtx[a].parpos());
167  const Vct2 & pb(vtx[b].parpos());
168  Real a11 = p2[0] - p1[0];
169  Real a21 = p2[1] - p1[1];
170  Real a12 = pa[0] - pb[0];
171  Real a22 = pa[1] - pb[1];
172  Real det = a11*a22 - a12*a21;
173  if (fabs(det) < gmepsilon)
174  return huge;
175  Real r1 = pa[0] - p1[0];
176  Real r2 = pa[1] - p1[1];
177  Real s = (r1*a22 - r2*a12) / det;
178  return s;
179  }
180 
182  bool pIntersects(const DnVertexArray & vtx, uint a, uint b) const {
183  assert(isValid());
184  const Vct2 & p1(vtx[vi[0]].parpos());
185  const Vct2 & p2(vtx[vi[1]].parpos());
186  const Vct2 & pa(vtx[a].parpos());
187  const Vct2 & pb(vtx[b].parpos());
188  Real a11 = p2[0] - p1[0];
189  Real a21 = p2[1] - p1[1];
190  Real a12 = pa[0] - pb[0];
191  Real a22 = pa[1] - pb[1];
192  Real det = a11*a22 - a12*a21;
193  if (fabs(det) < gmepsilon)
194  return false;
195  Real r1 = pa[0] - p1[0];
196  Real r2 = pa[1] - p1[1];
197  Real s = (r1*a22 - r2*a12) / det;
198  if (s < 0.0 or s > 1.0)
199  return false;
200  Real t = (a11*r2 - a21*r1) / det;
201  if (t < 0.0 or t > 1.0)
202  return false;
203  else
204  return true;
205  }
206 
208  bool sIntersects(const Surface & srf, const DnVertexArray & vtx, uint a, uint b) const {
209  assert(isValid());
210  const Vct3 & p1(vtx[vi[0]].eval());
211  const Vct3 & p2(vtx[vi[1]].eval());
212  const Vct3 & pa(vtx[a].eval());
213  const Vct3 & pb(vtx[b].eval());
214 
215  // minimize distance between *this and line (a,b)
216  Real a11(0.0), a12(0.0), a22(0.0);
217  Real d1, d2, d3, r1(0.0), r2(0.0);
218  for (uint k=0; k<3; ++k) {
219  d1 = p2[k] - p1[k];
220  d2 = pb[k] - pa[k];
221  d3 = p1[k] - pa[k];
222  a11 += d1*d1;
223  a12 -= d1*d2;
224  a22 += d2*d2;
225  r1 -= d1*d3;
226  r2 += d2*d3;
227  }
228  Real a21 = a12;
229  Real det = a11*a22 - a12*a21;
230  if (fabs(det) < gmepsilon)
231  return false;
232  Real s = (r1*a22 - r2*a12) / det;
233  if (s < 0.0 or s > 1.0)
234  return false;
235  Real t = (a11*r2 - a21*r1) / det;
236  if (t < 0.0 or t > 1.0)
237  return false;
238 
239  // compute line-line distance in 3D space
240  Vct3 pself( (1.-s)*p1 + s*p2 );
241  Vct3 pother( (1.-t)*pa + t*pb );
242  Real lldst = norm(pself - pother);
243  if (lldst < gmepsilon)
244  return true;
245 
246  // at the point where the two lines are nearest, compute
247  // the distance of the projection point on each line to the surface
248  Vct2 qself( (1.-s)*vtx[vi[0]].parpos() + s*vtx[vi[1]].parpos() );
249  Real sgap = norm(pself - srf.eval(qself[0], qself[1]));
250  Vct2 qother( (1.-t)*vtx[a].parpos() + t*vtx[b].parpos() );
251  Real tgap = norm(pother - srf.eval(qother[0], qother[1]));
252 
253  // lines are considered intersecting if their distance is smaller
254  // than the gap between the lines and the surface
255  if (lldst < 2*std::max(sgap,tgap))
256  return true;
257  else
258  return false;
259  }
260 
262  Real pLength(const DnVertexArray & vtx) const {
263  return norm(vtx[vi[0]].parpos() - vtx[vi[1]].parpos());
264  }
265 
267  Real sLength(const DnVertexArray & vtx) const {
268  return norm(vtx[vi[0]].eval() - vtx[vi[1]].eval());
269  }
270 
271  private:
272 
274  uint vi[2];
275 
277  uint nbf[2];
278 };
279 
280 #endif
void reconnect(uint a, uint b)
connect edge to different vertices
Definition: dnedge.h:38
DnEdge(uint a, uint b)
construct new edge
Definition: dnedge.h:33
uint find(uint i) const
check if edge has vertex i
Definition: dnedge.h:90
uint nNeighbors() const
count number of neighbor triangles
Definition: dnedge.h:64
void invalidate()
mark edge as invalid
Definition: dnedge.h:55
Real sLength(const DnVertexArray &vtx) const
edge length in 3D space
Definition: dnedge.h:267
uint replaceTriangle(uint fold, uint fnew)
replace a connection with another
Definition: dnedge.h:128
Real pIntersect(const DnVertexArray &vtx, uint a, uint b) const
compute where *this intersects (a,b) in the parameter domain
Definition: dnedge.h:162
Edge in a Delaunay triangulation.
Definition: dnedge.h:28
Real pLength(const DnVertexArray &vtx) const
edge length in parameter space
Definition: dnedge.h:262
uint source() const
access source vertex index
Definition: dnedge.h:58
uint opposed(uint ti) const
access triangle which is opposed to triangle with index ti
Definition: dnedge.h:80
uint vi[2]
source and target edge
Definition: dnedge.h:274
uint nbf[2]
exactly two neighbor faces
Definition: dnedge.h:277
bool isValid() const
check if edge is defined
Definition: dnedge.h:52
uint detachTriangle(uint fi)
remove triangle from neighbor list
Definition: dnedge.h:116
uint nbTriangle(uint i) const
access neighbor triangle indices
Definition: dnedge.h:74
uint attachTriangle(uint fi)
add triangle to neighbor list
Definition: dnedge.h:100
bool pIntersects(const DnVertexArray &vtx, uint a, uint b) const
test if *this intersects (a,b) in the parameter domain
Definition: dnedge.h:182
bool sIntersects(const Surface &srf, const DnVertexArray &vtx, uint a, uint b) const
test if *this overlaps (a,b) in 3D space with small distance
Definition: dnedge.h:208
virtual Vct3 eval(Real u, Real v) const =0
evaluation interface
uint target() const
access target vertex index
Definition: dnedge.h:61
Surface interface.
Definition: surface.h:37
bool operator==(const DnEdge &a) const
define edge identity
Definition: dnedge.h:152
bool operator<(const DnEdge &a) const
define a unique ordering for edges
Definition: dnedge.h:140
Generated on Wed Jan 19 2022 03:03:15 for libsurf by   doxygen 1.8.5