HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GU_PathFinder.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: GU_PathFinder.h
7  *
8  * COMMENTS:
9  * Finds paths of various specifications between various element types
10  * in polygon meshes.
11  */
12 
13 #ifndef __GU_PathFinder__
14 #define __GU_PathFinder__
15 
16 #include "GU_API.h"
17 #include <UT/UT_PriorityQueue.h>
18 #include <GA/GA_DataBitArray.h>
19 #include "GU_Detail.h"
20 
23 
25 
34 };
35 
43 };
44 
46 {
47 public:
49  {
50  clear();
51  }
52 
53  void clear()
54  {
55  for (int i = 0; i < GU_NUM_EDGE_SUCCESSOR_TYPES; ++i)
56  myExits[i] = GEO_INVALID_SHEDGE;
57  }
58 
59  const GEO_SHedge operator()(int i) const
60  {
61  return myExits[i];
62  }
63 
65  {
66  return myExits[i];
67  }
68 
69  bool hasExits()
70  {
71  for (int i = 0; i < GU_NUM_EDGE_SUCCESSOR_TYPES; ++i)
72  if (myExits[i].isValid())
73  return true;
74  return false;
75  }
76 
78  {
79  return t < GU_NUM_EDGE_SUCCESSOR_TYPES ?
81  }
82 
83 private:
85 };
86 
87 // Template parameter T is the cost class
88 template <class T = gu_ShortestPathCost>
90 {
91 public:
92 
93  class PathEdge
94  {
95  public:
97  mySHedge(GEO_INVALID_SHEDGE),
98  myPrev(GEO_INVALID_SHEDGE) {}
99 
102  mySHedge(sh), myPrev(prev) { myPathCost.zero(); }
103 
105  const T &cost) :
106  mySHedge(sh), myPrev(prev), myPathCost(cost) {}
107 
108  bool operator()(PathEdge &p1, PathEdge &p2) const
109  { return (p1.myPathCost > p2.myPathCost); }
110 
111  T getPathCost() { return myPathCost; }
112  GEO_SHedge getSHedge() { return mySHedge; }
113  GEO_SHedge getPrev() { return myPrev; }
114  bool hasPrev() { return myPrev.isValid(); }
115 
116  private:
117  GEO_SHedge mySHedge, myPrev;
118  T myPathCost;
119  };
120 
121  typedef T CostType;
122 
123 public:
125 
126  void setStartHedge(GEO_Hedge sh, bool and_equiv = true);
127  void setEndHedge(GEO_Hedge eh, bool and_equiv = true);
128 
129 
130  void setStartSHedge(GEO_SHedge ssh,
131  bool and_reverse = false);
132  void setEndSHedge(GEO_SHedge ssh,
133  bool and_reverse = false);
134 
135  void setStartPoint(GA_Offset pt);
136  void setEndPoint(GA_Offset pt);
137 
138  void setStartPrimitive(GA_Offset prim);
139  void setEndPrimitive(GA_Offset prim);
140 
141 
142  void clearStartSHedges();
143  void addStartSHedge(GEO_SHedge sh,
144  bool and_reverse = false);
145 
146  void clearEndSHedges();
147  void addEndSHedge(GEO_SHedge sh, bool and_reverse = false);
148 
149  T findPath(GU_SHedgeArray &path,
150  GU_EdgeSuccessorTypeMask succ_type);
151 
152  T findDualPath(GU_SHedgeArray &path,
153  GU_EdgeSuccessorTypeMask succ_type);
154 
155  void dumpSHedge(GEO_SHedge sh) const;
156 
158  { myAvoidPoints = grp; }
159 
161  { myAvoidEdges = grp; }
162 
164  { myAvoidPrimitives = grp; }
165 
166  void reset(bool heap_only = false);
167 
168  bool trimPathAtPoint(GU_SHedgeArray &path, GA_Offset pt);
169 
170  bool trimDualPathAtPrimitive(GU_SHedgeArray &path,
171  GA_Offset prim);
172 
173  GA_Offset trimCrossingPaths(GU_SHedgeArray &w0,
174  GU_SHedgeArray &w1);
175 
176  GA_Offset trimCrossingDualPaths(GU_SHedgeArray &w0,
177  GU_SHedgeArray &w1);
178 
179  const GU_SHedgeArray
181  { return myStartSHedges; }
182 
183  T &getBestCost(GEO_SHedge sh);
184 
185  void simplifyPath(GU_SHedgeArray &path);
186  void simplifyDualPath(GU_SHedgeArray &path);
187 
188  bool extendPath(GU_SHedgeArray &path,
189  bool trim_crossing = true);
190 
191  bool extendDualPath(GU_SHedgeArray &path,
192  bool trim_crossing = true,
193  bool is_for_prim_loo = false);
194 
195  bool isStartOnBoundary() { return myStartOnBoundary; }
196  bool isEndOnBoundary() { return myEndOnBoundary; }
197 
198 private:
199 
200  void mark(GEO_SHedge sh);
201 
202  bool isMarked(GEO_SHedge sh);
203 
204  void initializeEdgeHeap();
205 
206  void setBestCost(GEO_SHedge sh, const T &cost,
207  GEO_SHedge prev_sh = GEO_INVALID_SHEDGE);
208 
209  GEO_SHedge getPrev(GEO_SHedge sh);
210  bool hasPrev(GEO_SHedge sh);
211 
212  void addPathToEdgeGroup(GEO_SHedge sh,
213  GA_EdgeGroup &edges);
214 
215  // fills path with signed hedges from the optimal path found from a start
216  // signed hedge to esh.
217  void extractPath(GEO_SHedge esh, GU_SHedgeArray &path);
218  void extractDualPath(GEO_SHedge esh, GU_SHedgeArray &path);
219 
220  bool isStartSHedge(GEO_SHedge sh);
221  bool isStartSHedgePrimary(GEO_SHedge sh);
222 
223  bool isEndSHedge(GEO_SHedge sh);
224  bool isEndSHedgePrimary(GEO_SHedge sh);
225 
226  GEO_SHedge findMarkedEndSHedge();
227  GEO_SHedge findMarkedEndSHedgePrimary();
228 
229  // Some signed hedge helper methods
230 
231  GEO_SHedge primary(const GEO_SHedge sh) const;
232  GA_Offset srcPoint(const GEO_SHedge sh) const;
233  GA_Offset dstPoint(const GEO_SHedge sh) const;
234  int relativeSign(const GEO_SHedge sh, GEO_Hedge h) const;
235  int relativeSign(const GEO_SHedge sh, GA_Offset pt) const;
236  int relativeSign(GEO_Hedge h0, GEO_Hedge h1) const;
237  int relativeSign(GEO_Hedge h, GA_Offset pt) const;
238 
239  GA_Edge gaEdge(GEO_Hedge h) const;
240  GA_Edge gaEdge(const GEO_SHedge sh) const;
241 
243 
244  const GEO_DetachedHedgeInterface *myDhip;
245 
246  const GA_Detail *myGdp;
247 
248  GA_DataBitArray myPosMarked, myNegMarked;
249  GU_SHedgeArray myPosPrev, myNegPrev;
250 
251  UT_Array<T> myPosCost, myNegCost;
252 
253  EdgeHeap myEdgeHeap;
254 
255  GEO_Hedge myStartEdge;
256  int myStartEdgeSign;
257 
258  GU_SHedgeArray myStartSHedges;
259  GU_SHedgeArray myStartSHedgePrimaries;
260  GU_SHedgeArray myEndSHedges;
261  GU_SHedgeArray myEndSHedgePrimaries;
262 
263  GEO_SHedge myLastStartSHedge;
264  bool myLastStartSHedgeAndReverse;
265 
266  GEO_SHedge myLastStartHedge;
267  bool myLastStartHedgeAndEquivalent;
268 
269  bool myStartOnBoundary;
270  bool myEndOnBoundary;
271 
272  GA_Offset myLastStartPoint;
273  GA_Offset myLastStartPrimitive;
274 
275 
276  GA_EdgeGroup *myAvoidEdges;
277  GA_PointGroup *myAvoidPoints;
278  GA_PrimitiveGroup *myAvoidPrimitives;
279 
281  mySuccessorTypeMask;
282 };
283 
285 {
286 public:
288  {
289  myLength = -1.0;
290  }
291 
293  {
294  myLength = l;
295  }
296 
298  const GEO_DetachedHedgeInterface *dhip)
299  {
300  myLength = dhip->length(sh.hedge());
301  }
302 
304  {
305  myLength = c.myLength;
306  }
307 
308  void zero()
309  {
310  myLength = 0.0;
311  }
312 
313  void unset()
314  {
315  myLength = -1.0;
316  }
317 
318  bool isSet()
319  {
320  return myLength > -0.5;
321  }
322 
323  bool operator>(const gu_ShortestPathCost &c) const
324  {
325  return myLength > c.myLength;
326  }
327 
328  const gu_ShortestPathCost &
330  {
331  myLength = c.myLength;
332  return *this;
333  }
334 
335  const gu_ShortestPathCost &
337  {
338  myLength += c.myLength;
339  return *this;
340  }
341 
342  static gu_ShortestPathCost
344  GEO_SHedge to_sh, const GU_EdgeSuccessor &exits)
345  {
346  return gu_ShortestPathCost(dhip->length(to_sh.hedge()));
347  }
348 
350  {
351  return myLength;
352  }
353 
354  void dumpCost()
355  {
356  std::cout << myLength;
357  }
358 
359 private:
360  fpreal myLength;
361 };
362 
364 {
365 public:
367  {
368  myPathLength = -1.0;
369  myPenalty = -1;
370  }
371 
373  const GEO_DetachedHedgeInterface *dhip)
374  {
375  myPenalty = 0;
376  myPathLength = dhip->length(sh.hedge());
377  }
378 
379  gu_EdgeLoopCost(fpreal len, int bends)
380  {
381  myPathLength = len;
382  myPenalty = bends;
383  }
384 
386  {
387  myPathLength = c.myPathLength;
388  myPenalty = c.myPenalty;
389  }
390 
391  void zero()
392  {
393  myPathLength = 0.0;
394  myPenalty = 0;
395  }
396 
397  void unset()
398  {
399  myPathLength = -1.0;
400  }
401 
402  bool isSet()
403  {
404  return myPathLength > -0.5;
405  }
406 
407  bool operator>(const gu_EdgeLoopCost &c) const
408  {
409  if (myPenalty != c.myPenalty)
410  return myPenalty > c.myPenalty;
411 
412  return myPathLength > c.myPathLength;
413  }
414 
415  const gu_EdgeLoopCost &
417  {
418  myPathLength = c.myPathLength;
419  myPenalty = c.myPenalty;
420  return *this;
421  }
422 
423  const gu_EdgeLoopCost &
425  {
426  myPenalty += c.myPenalty;
427  myPathLength += c.myPathLength;
428  return *this;
429  }
430 
431  static gu_EdgeLoopCost
433  GEO_SHedge to_sh, const GU_EdgeSuccessor &successors)
434  {
435  fpreal len = dhip->length(to_sh.hedge());
436 
437  GEO_SHedge bd_succ = successors(GU_BOUNDARY);
438  if (bd_succ.isValid() && dhip->areEquivalent(to_sh, bd_succ))
439  return gu_EdgeLoopCost(len, 0);
440 
441  GEO_SHedge sided_quad_succ = successors(GU_QUAD_LEFT);
442  if (!sided_quad_succ.isValid())
443  sided_quad_succ = successors(GU_QUAD_RIGHT);
444 
445  GEO_SHedge opposite = successors(GU_QUAD_OPPOSITE);
446  if (!opposite.isValid())
447  opposite = successors(GU_OPPOSITE);
448 
449  bool to_sided_quad_succ = (sided_quad_succ.isValid() &&
450  dhip->areEquivalent(to_sh, sided_quad_succ));
451 
452  bool to_opposite = opposite.isValid() &&
453  dhip->areEquivalent(to_sh, opposite);
454 
455  if (to_sided_quad_succ)
456  return gu_EdgeLoopCost(len, 1);
457 
458  if (to_opposite)
459  return gu_EdgeLoopCost(len, 99);
460 
461  return gu_EdgeLoopCost(len, 100);
462  }
463 
464  void dumpCost()
465  {
466  std::cout << myPenalty << ", " << myPathLength;
467  }
468 
469  fpreal getLength() { return myPathLength; }
470 
471 private:
472  fpreal myPathLength;
473  int myPenalty;
474 };
475 
476 
477 
479 {
480 public:
482  {
483  myPathLength = -1.0;
484  myPenalty = -1;
485  }
486 
488  const GEO_DetachedHedgeInterface *dhip)
489  {
490  myPenalty = 0;
491  myPathLength = dhip->length(sh.hedge());
492  }
493 
494  gu_EdgeRingCost(fpreal len, int bends)
495  {
496  myPathLength = len;
497  myPenalty = bends;
498  }
499 
501  {
502  myPathLength = c.myPathLength;
503  myPenalty = c.myPenalty;
504  }
505 
506  void zero()
507  {
508  myPathLength = 0.0;
509  myPenalty = 0;
510  }
511 
512  void unset()
513  {
514  myPathLength = -1.0;
515  }
516 
517  bool isSet()
518  {
519  return myPathLength > -0.5;
520  }
521 
522  bool operator>(const gu_EdgeRingCost &c) const
523  {
524  if (myPenalty != c.myPenalty)
525  return myPenalty > c.myPenalty;
526 
527  return myPathLength > c.myPathLength;
528  }
529 
530  const gu_EdgeRingCost &
532  {
533  myPathLength = c.myPathLength;
534  myPenalty = c.myPenalty;
535  return *this;
536  }
537 
538  const gu_EdgeRingCost &
540  {
541  myPenalty += c.myPenalty;
542  myPathLength += c.myPathLength;
543  return *this;
544  }
545 
546  static gu_EdgeRingCost
548  GEO_SHedge to_sh, const GU_EdgeSuccessor &successors)
549  {
550  fpreal len = dhip->length(to_sh.hedge());
551 
552  GEO_SHedge bd_succ = successors(GU_BOUNDARY);
553  bool to_bd_succ = bd_succ.isValid() &&
554  dhip->areEquivalent(to_sh, bd_succ);
555 
556  if (to_bd_succ)
557  return gu_EdgeRingCost(len, 0);
558 
559  GEO_SHedge sided_quad_succ = successors(GU_QUAD_LEFT);
560  if (!sided_quad_succ.isValid())
561  sided_quad_succ = successors(GU_QUAD_RIGHT);
562 
563  GEO_SHedge opposite = successors(GU_QUAD_OPPOSITE);
564  if (!opposite.isValid())
565  opposite = successors(GU_OPPOSITE);
566 
567  bool to_sided_quad_succ = (sided_quad_succ.isValid() &&
568  dhip->areEquivalent(to_sh, sided_quad_succ));
569 
570  bool to_opposite = opposite.isValid() &&
571  dhip->areEquivalent(to_sh, opposite);
572 
573  if (to_sided_quad_succ)
574  return gu_EdgeRingCost(len, 1);
575 
576  if (to_opposite)
577  return gu_EdgeRingCost(len, 99);
578 
579  return gu_EdgeRingCost(len, 100);
580  }
581 
582  void dumpCost()
583  {
584  std::cout << myPenalty << ", " << myPathLength;
585  }
586 
587  fpreal getLength() { return myPathLength; }
588 
589 private:
590  fpreal myPathLength;
591  int myPenalty;
592 };
593 
594 
597 
599 {
604 };
605 
608  GU_SHedgeArray &walk,
609  bool backward = false,
610  bool no_self_intersection = false,
611  bool include_ends = false);
612 
615  GU_SHedgeArray &walk,
616  bool backward = false,
617  bool no_self_intersection = false,
618  bool include_ends = false);
619 
620 #endif
621 
gu_EdgeRingCost(const GEO_SHedge sh, const GEO_DetachedHedgeInterface *dhip)
bool operator>(const gu_EdgeLoopCost &c) const
gu_EdgeLoopCost(const GEO_SHedge sh, const GEO_DetachedHedgeInterface *dhip)
const GU_SHedgeArray & getStartSHedges() const
GU_WalkEndReason GU_API guDualEdgeWalk(const GEO_DetachedHedgeInterface *dhip, GU_SHedgeArray &path, GU_SHedgeArray &walk, bool backward=false, bool no_self_intersection=false, bool include_ends=false)
void avoidPoints(GA_PointGroup *grp)
static gu_EdgeRingCost turnCost(const GEO_DetachedHedgeInterface *dhip, GEO_SHedge from_sh, GEO_SHedge to_sh, const GU_EdgeSuccessor &successors)
const gu_ShortestPathCost & operator+=(const gu_ShortestPathCost &c)
bool areEquivalent(GEO_Hedge e1, GEO_Hedge e2) const
Returns true if e1 and e2 are equivalent hedges.
GLsizei const GLchar *const * path
Definition: glcorearb.h:3340
const gu_ShortestPathCost & operator=(const gu_ShortestPathCost &c)
SYS_FORCE_INLINE GA_Offset srcPoint(const GA_Detail *gdp, GEO_Hedge e)
Definition: GEO_Hedge.h:173
GU_EdgeSuccessorTypeMask
Definition: GU_PathFinder.h:36
bool operator>(const gu_ShortestPathCost &c) const
const gu_EdgeRingCost & operator+=(const gu_EdgeRingCost &c)
const gu_EdgeRingCost & operator=(const gu_EdgeRingCost &c)
fpreal getLength()
png_uint_32 i
Definition: png.h:2877
fpreal getLength()
bool operator>(const gu_EdgeRingCost &c) const
bool isEndOnBoundary()
gu_EdgeRingCost(const gu_EdgeRingCost &c)
GA_Size GA_Offset
Definition: GA_Types.h:617
PathEdge(GEO_SHedge sh, GEO_SHedge prev, const T &cost)
GU_PathFinder< gu_EdgeRingCost > GU_EdgeRingFinder
fpreal length(GEO_Hedge e) const
gu_EdgeLoopCost(const gu_EdgeLoopCost &c)
gu_ShortestPathCost(const GEO_SHedge sh, const GEO_DetachedHedgeInterface *dhip)
GU_PathFinder< gu_EdgeLoopCost > GU_EdgeLoopFinder
const gu_EdgeLoopCost & operator+=(const gu_EdgeLoopCost &c)
#define GEO_INVALID_SHEDGE
GEO_SHedge encapsulates a signed half-edge. It is a half-edge together.
Definition: GEO_Hedge.h:78
gu_ShortestPathCost(fpreal l)
GEO_Hedge encapsulates a half-edge (hedge) which is the restriction of.
Definition: GEO_Hedge.h:47
PathEdge(GEO_SHedge sh, GEO_SHedge prev=GEO_INVALID_SHEDGE)
static gu_ShortestPathCost turnCost(const GEO_DetachedHedgeInterface *dhip, GEO_SHedge from_sh, GEO_SHedge to_sh, const GU_EdgeSuccessor &exits)
gu_ShortestPathCost(const gu_ShortestPathCost &c)
static GU_EdgeSuccessorTypeMask typeMask(GU_EdgeSuccessorType t)
Definition: GU_PathFinder.h:77
#define GU_API
Definition: GU_API.h:11
UT_Array< GEO_SHedge > GU_SHedgeArray
Definition: GU_PathFinder.h:22
void avoidPrimitives(GA_PrimitiveGroup *grp)
GU_WalkEndReason
SYS_FORCE_INLINE GA_Offset dstPoint(T &iface, GEO_Hedge e)
Definition: GEO_Hedge.h:231
GU_WalkEndReason GU_API guEdgeWalk(const GEO_DetachedHedgeInterface *dhip, GU_SHedgeArray &path, GU_SHedgeArray &walk, bool backward=false, bool no_self_intersection=false, bool include_ends=false)
bool isStartOnBoundary()
const gu_EdgeLoopCost & operator=(const gu_EdgeLoopCost &c)
bool operator()(PathEdge &p1, PathEdge &p2) const
GLfloat GLfloat GLfloat GLfloat h
Definition: glcorearb.h:2001
double fpreal
Definition: SYS_Types.h:263
GU_EdgeSuccessorType
Definition: GU_PathFinder.h:26
const GEO_SHedge operator()(int i) const
Definition: GU_PathFinder.h:59
static gu_EdgeLoopCost turnCost(const GEO_DetachedHedgeInterface *dhip, GEO_SHedge from_sh, GEO_SHedge to_sh, const GU_EdgeSuccessor &successors)
gu_EdgeLoopCost(fpreal len, int bends)
gu_EdgeRingCost(fpreal len, int bends)
Container class for all geometry.
Definition: GA_Detail.h:96
void avoidEdges(GA_EdgeGroup *grp)
SYS_FORCE_INLINE GEO_Hedge hedge() const
Definition: GEO_Hedge.h:145
bool isValid() const
Definition: GEO_Hedge.h:96
GEO_SHedge & operator()(int i)
Definition: GU_PathFinder.h:64
An array of bits.