HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups 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 "GU_Detail.h"
18 #include "GU_PathHedge.h"
19 
20 #include <GA/GA_Types.h>
21 #include <SYS/SYS_Math.h>
22 #include <GEO/GEO_HedgeInterface.h>
23 #include <GA/GA_DataBitArray.h>
24 #include <GA/GA_Group.h>
25 #include <GA/GA_ElementGroup.h>
26 #include <GA/GA_EdgeGroup.h>
27 #include <UT/UT_PriorityQueue.h>
28 #include <UT/UT_Set.h>
29 #include <UT/UT_Map.h>
30 #include <UT/UT_Array.h>
31 #include <UT/UT_BitArray.h>
32 
34 
36 
37 
39 {
40 public:
41  enum Type
42  {
43  QUAD_LEFT = 0,
48  ANY,
50  };
51 
52  enum Mask
53  {
54  ANY_MASK = 0,
60  };
61 
63 
64  GU_PathSHedge &operator()(int i) { return mySucc[i]; }
65  GU_PathSHedge operator()(int i) const { return mySucc[i]; }
66 
67  static
69  { return t < NUM_TYPES ? Mask(1 << t) : ANY_MASK; }
70 
71  void clear()
72  {
73  for (int i = 0; i < NUM_TYPES; ++i)
74  mySucc[i] = GU_PathSHedge();
75  }
76 
77 private:
78  GU_PathSHedge mySucc[NUM_TYPES];
79 };
80 
81 // Template parameter T is the cost class
82 
83 template <class T = gu_ShortestPathCost>
85 {
86 public:
87 
88  class PathEdge
89  {
90  public:
91  PathEdge() : mySHedge(GU_PathSHedge()), myPrev(GU_PathSHedge())
92  { }
93 
94  explicit
96  GU_PathSHedge prev = GU_PathSHedge()) :
97  mySHedge(sh), myPrev(prev) { myPathCost.zero(); }
98 
99  PathEdge(GU_PathSHedge sh, GU_PathSHedge prev, const T &cost) :
100  mySHedge(sh), myPrev(prev), myPathCost(cost) { }
101 
102  bool operator()(PathEdge &p1, PathEdge &p2) const
103  { return (p1.myPathCost > p2.myPathCost); }
104 
105  T getPathCost() { return myPathCost; }
106  GU_PathSHedge getSHedge() { return mySHedge; }
107  GU_PathSHedge getPrev() { return myPrev; }
108  bool hasPrev() { return myPrev.isValid(); }
109 
110  private:
111  GU_PathSHedge mySHedge, myPrev;
112  T myPathCost;
113  };
114 
115  using CostType = T;
116 
117 public:
118 
119  // If the uv_attrib parameter is passed, then the search takes place
120  // in UV space (boundaries, connectivity, etc follow the UVs).
121 
122  explicit GU_PathFinder(GU_PathHedge::Interface *dhip,
123  const GA_Attribute *uv_attrib = nullptr);
124 
125  // Paths are formed of *signed* half-edges, where the sign indicates
126  // whether the half-edge is being travelled from source to destination
127  // (positive) or the other way around (negative). Dual paths are sequences
128  // of edges (represented by half-edges) which are typically separated by
129  // polygons but may share endpoints. In specifying the start and end
130  // targets for path search, we used signed half-edges to indicate the
131  // direction of departure or arrival at the start or end edges
132  // respectively. In the dual path search, we only use positive half-edges
133  // since all that we care about are the start and end edges. Note that
134  // a search can specify multiple start and end (signed) half-edges. This
135  // is particularly used in implementing primitive, point, and vertex loops.
136 
137  // Set a start or ending half-edge for the next search. If and_equiv
138  // is set to true, then all equivalent half-edges to the given one are
139  // also added as possible start or end half-edges. Note that any generated
140  // path should follow the direction of one of these starting half-edges.
141  void setStartHedge(const GU_PathHedge& sh, bool and_equiv = true);
142  void setEndHedge(const GU_PathHedge& eh, bool and_equiv = true);
143 
144  // Set a start or end *signed* half-edge. Specifying the start or end
145  // half-edge this way can be used to free us from the actual direction of
146  // existing half-edges, particularly when the intended direction may not
147  // be realized by any half-edges, mostly notably in case of boundaries when
148  // we have a single half-edge. If and_reverse is set to true, the half-edge
149  // is added in both directions.
150  void setStartSHedge(const GU_PathSHedge& ssh,
151  bool and_reverse = false);
152  void setEndSHedge(const GU_PathSHedge& ssh,
153  bool and_reverse = false);
154 
155  // Specify the search start and end by points. These get translated to
156  // appropriate half-edges.
157  void setStartPoint(GA_Offset pt);
158  void setEndPoint(GA_Offset pt);
159 
160  // Specify the search start and end by vertices. These get translated to
161  // appropriate half-edges. Note that vertex path returns "representative"
162  // vertices between the two ends which are themselves treated as
163  // representatives of their respective points (or their respective island
164  // points if there's an active UV attribute).
165 
166  void setStartVertex(GA_Offset vtx);
167  void setEndVertex(GA_Offset vtx);
168 
169  // Set start and end primitives. These get translated to appropriate
170  // half-edges.
171  void setStartPrimitive(GA_Offset prim);
172  void setEndPrimitive(GA_Offset prim);
173 
174 
175  void clearStartSHedges();
176  void addStartSHedge(const GU_PathSHedge& sh,
177  bool and_reverse = false);
178 
179  void clearEndSHedges();
180  void addEndSHedge(const GU_PathSHedge& sh, bool and_reverse = false);
181 
182  // The main method to search for a the shortest path between a start
183  // signed half edge and an end one. The successor type mask allows
184  // to prioritize various types of successors and change the cost values
185  // and is utilized by the template parameter cost class.
186  T findPath(GU_SHedgeArray &path,
187  GU_EdgeSuccessor::Mask succ_type);
188 
189  // Find a dual path between a source and a destination half-edge.
190  T findDualPath(GU_SHedgeArray &path,
191  GU_EdgeSuccessor::Mask succ_type);
192 
193 
194  // Assign a group of points to be avoided by search paths.
196  { myAvoidPoints = grp; }
197 
198  // Assign a group of edges to be avoided by search paths.
200  { myAvoidEdges = grp; }
201 
202  // Assign a group of primitives to be avoided by search paths.
204  { myAvoidPrimitives = grp; }
205 
206  // Assign a group of vertices to be avoided by search paths.
208  { myAvoidVertices = grp; }
209 
210 
212  GA_EdgeGroup * edgegrp,
213  GA_VertexGroup *vtxgrp,
214  GA_PrimitiveGroup *primgrp)
215  {
216  if (ptgrp && ptgrp->entries())
217  avoidPoints(ptgrp);
218 
219  if (edgegrp && edgegrp->entries())
220  avoidEdges(edgegrp);
221 
222  if (vtxgrp && vtxgrp->entries())
223  avoidVertices(vtxgrp);
224 
225  if (primgrp && primgrp->entries())
226  avoidPrimitives(primgrp);
227  };
228 
230  {
231  avoidPoints(nullptr);
232  avoidEdges(nullptr);
233  avoidPrimitives(nullptr);
234  avoidVertices(nullptr);
235  }
236 
237  void setCollisionGroup(const GA_Group * group, bool exclude, bool strong)
238  {
239  myCollisionPoints = nullptr;
240  myCollisionPrimitives = nullptr;
241  myCollisionVertices = nullptr;
242  myCollisionEdges = nullptr;
243  myCollisionGroup = group;
244  myExcludeCollisionGroup = exclude;
245  myCollisionStrong = strong;
246  if (!group)
247  return;
248 
249  switch (group->classType())
250  {
251  case GA_GROUP_POINT:
252  myCollisionPoints = static_cast<const GA_PointGroup *>(group);
253  break;
254  case GA_GROUP_PRIMITIVE:
255  myCollisionPrimitives = static_cast<const GA_PrimitiveGroup *>(group);
256  break;
257  case GA_GROUP_VERTEX:
258  myCollisionVertices = static_cast<const GA_VertexGroup *>(group);
259  break;
260  case GA_GROUP_EDGE:
261  myCollisionEdges = static_cast<const GA_EdgeGroup *>(group);
262  break;
263  default:
264  break;
265  }
266  }
267 
268  // Reset partial search results. This clears the start and end elements,
269  // unless heap_only is set to true in which case only the partial search
270  // tree is cleared.
271  void reset(bool heap_only = false);
272 
273  const
275  { return myStartSHedges; }
276 
278  T &getBestCost(const GU_PathSHedge & sh);
279 
280  // Bypass cycles in the path or dual path.
281  void simplifyPath(GU_SHedgeArray &path);
282  void simplifyDualPath(GU_SHedgeArray &path);
283 
284  // Extend an open path on both ends by walking straight at regular
285  // quad junctions until the two ends meet or irregular points are reached.
286  // Returns true if the path changes and false otherwise.
287  bool extendPath(GU_SHedgeArray &path,
288  bool trim_crossing = true);
289 
290  // Extend an open dual path on both ends by walk over opposite quad edges
291  // until a closed edge ring is formed or a non-quad is reached.
292  bool extendDualPath(GU_SHedgeArray &path,
293  bool trim_crossing = true,
294  bool is_for_prim_loo = false);
295 
296  // Determine whether the start or end edges are boundary edges. When a
297  // UV attribute is given, this is determined with regard to that.
298 
299  bool isStartOnBoundary() { return myStartOnBoundary; }
300  bool isEndOnBoundary() { return myEndOnBoundary; }
301 
302 private:
303 
304  void dumpSHedge(const GU_PathSHedge & sh) const;
305 
307  void mark(const GU_PathSHedge & sh);
308 
310  bool isMarked(const GU_PathSHedge & sh);
311 
312  void initializeEdgeHeap();
313 
315  void setBestCost(const GU_PathSHedge& sh, const T &cost,
316  GU_PathSHedge prev_sh = GU_PathSHedge());
317 
319  GU_PathSHedge getPrev(const GU_PathSHedge & sh);
320 
322  bool hasPrev(const GU_PathSHedge & sh)
323  { return myDhip->isValidHedge(getPrev(sh).hedge()); }
324 
325  // Search for the destination point of the first signed half-edge in the
326  // path that matches pt and truncates the rest of the path. Returns true
327  // if the point is found or false otherwise.
328  bool trimPathAtPoint(GU_SHedgeArray &path, GA_Offset pt);
329 
330  // Search for a half-edge in the path incident to a primitive and truncates
331  // the rest of the path after that half-edge. Returns true if the primitive
332  // is found.
333  bool trimDualPathAtPrimitive(GU_SHedgeArray &path,
334  const GU_PathHedge & h);
335 
336  GA_Offset trimCrossingPaths(GU_SHedgeArray &w0,
337  GU_SHedgeArray &w1);
338 
339  GA_Offset trimCrossingDualPaths(GU_SHedgeArray &w0,
340  GU_SHedgeArray &w1);
341 
342 
343  // fills path with signed hedges from the optimal path found from a start
344  // signed hedge to esh.
345  void extractPath(const GU_PathSHedge & esh, GU_SHedgeArray &path);
346  void extractDualPath(const GU_PathSHedge &esh, GU_SHedgeArray &path);
347 
348  bool isStartSHedge(const GU_PathSHedge & sh);
349  bool isStartSHedgePrimary(const GU_PathSHedge &sh);
350 
351  bool isEndSHedge(const GU_PathSHedge & sh);
352  bool isEndSHedgePrimary(const GU_PathSHedge & sh);
353 
354  GU_PathSHedge findMarkedEndSHedge();
355  GU_PathSHedge findMarkedEndSHedgePrimary();
356 
357  // Some signed hedge helper methods
358 
359  GU_PathSHedge primary(const GU_PathSHedge &sh) const;
360  bool isPrimary(const GU_PathSHedge &sh) const;
361 
362  // Returns the right sign for h to have pt as it source.
364  int relativeSign(const GU_PathHedge & h, GA_Offset pt) const
365  { return pt == myDhip->srcPoint(h) ? 1 : -1; }
366 
367 
369  GA_Edge gaEdge(const GU_PathHedge & h) const
370  { return GA_Edge(myDhip->srcPoint(h),
371  myDhip->dstPoint(h)); }
372 
374  GA_Edge gaEdge(const GU_PathSHedge & sh) const;
375 
378  using SuccessorMask = GU_EdgeSuccessor::Mask;
379 
380  //const
381  GU_PathHedge::Interface *myDhip;
382 
383  const GA_Detail *myGdp;
384  GA_ROHandleV2 myUV;
385 
386  //These are very costly, may want to find some other way
387  UT_Set<GU_PathHedge> myPosMarked, myNegMarked;
388  UT_Map<GU_PathHedge, GU_PathSHedge> myPosPrev, myNegPrev;
389  UT_Map<GU_PathHedge, T> myPosCost, myNegCost;
390 
391  //Versions for polygons as an optimization
392  UT_BitArray myPolyPosMarked, myPolyNegMarked;
393  UT_Array<GU_PathSHedge> myPolyPosPrev, myPolyNegPrev;
394  UT_Array<T> myPolyPosCost, myPolyNegCost;
395 
396  EdgeHeap myEdgeHeap;
397 
398  GU_SHedgeArray myStartSHedges;
399  GU_SHedgeArray myStartSHedgePrimaries;
400  GU_SHedgeArray myEndSHedges;
401  GU_SHedgeArray myEndSHedgePrimaries;
402 
403  GU_PathSHedge myLastStartSHedge = GU_PathSHedge();
404  bool myLastStartSHedgeFlag = false;
405 
406  GU_PathHedge myLastStartHedge = GU_PathHedge();
407  bool myLastStartHedgeFlag = false;
408 
409  bool myStartOnBoundary = false;
410  bool myEndOnBoundary = false;
411 
412  GA_Offset myLastStartPoint = GA_INVALID_OFFSET;
413  GA_Offset myLastStartPrimitive = GA_INVALID_OFFSET;
414  GA_Offset myLastStartVertex = GA_INVALID_OFFSET;
415 
416 
417  GA_EdgeGroup *myAvoidEdges = nullptr;
418  GA_PointGroup *myAvoidPoints = nullptr;
419  GA_PrimitiveGroup *myAvoidPrimitives = nullptr;
420  GA_VertexGroup *myAvoidVertices = nullptr;
421 
422  //keep a pointer to each collision group type as an optimization
423  const GA_EdgeGroup *myCollisionEdges = nullptr;
424  const GA_PointGroup *myCollisionPoints = nullptr;
425  const GA_PrimitiveGroup *myCollisionPrimitives = nullptr;
426  const GA_VertexGroup *myCollisionVertices = nullptr;
427  //should be the same pointer as the non-null one above
428  const GA_Group * myCollisionGroup = nullptr;
429 
430  //when true will NOT allow paths containing collision group
431  //when false will constrain paths to collision group
432  bool myExcludeCollisionGroup = true;
433 
434  //when true will NOT allow paths along boundar
435  //when false will allow paths to partially contain collision group
436  bool myCollisionStrong = false;
437 
438  SuccessorMask mySuccessorTypeMask;
439 };
440 
442 {
443 public:
444  gu_ShortestPathCost() = default;
445  explicit gu_ShortestPathCost(fpreal l) : myLength(l) { }
446 
449  { myLength = dhip->length(sh.hedge()); }
450 
452  = default;
453 
455  void zero() { myLength = 0.0; }
456 
458  void unset() { myLength = -1.0; }
459 
461  bool isSet() { return myLength > -0.5; }
462 
464  bool operator>(const gu_ShortestPathCost &c) const
465  { return myLength > c.myLength; }
466 
469 
471  const
473  {
474  myLength += c.myLength;
475  return *this;
476  }
477 
479  static
481  const GU_PathSHedge & from_sh,
482  const GU_PathSHedge & to_sh,
483  const GU_EdgeSuccessor &exits)
484  {
485  return gu_ShortestPathCost(dhip->length(to_sh.hedge()));
486  }
487 
489  fpreal getLength() { return myLength; }
490 
491 private:
492  fpreal myLength = -1.0;
493 };
494 
496 {
497 public:
498  gu_EdgeLoopCost() = default;
500  GU_PathHedge::Interface *dhip) :
501  myPenalty(0),
502  myPathLength(dhip->length(sh.hedge())) { }
503 
504  gu_EdgeLoopCost(fpreal len, int bends) :
505  myPathLength(len), myPenalty(bends) { }
506 
508  myPathLength(c.myPathLength),
509  myPenalty(c.myPenalty) { }
510 
512  void zero()
513  {
514  myPathLength = 0.0;
515  myPenalty = 0;
516  }
517 
519  void unset() { myPathLength = -1.0; }
520 
522  bool isSet() { return myPathLength > -0.5; }
523 
525  bool operator>(const gu_EdgeLoopCost &c) const
526  {
527  if (myPenalty != c.myPenalty)
528  return myPenalty > c.myPenalty;
529 
530  return myPathLength > c.myPathLength;
531  }
532 
533  gu_EdgeLoopCost &operator=(const gu_EdgeLoopCost &c) = default;
534 
536  const
538  {
539  myPenalty += c.myPenalty;
540  myPathLength += c.myPathLength;
541  return *this;
542  }
543 
545  static
547  const GU_PathSHedge & from_sh,
548  const GU_PathSHedge & to_sh,
549  const GU_EdgeSuccessor &successors)
550  {
551  fpreal len = dhip->length(to_sh.hedge());
552 
553  GU_PathSHedge bd_succ = successors(GU_EdgeSuccessor::BOUNDARY);
554  if (bd_succ.isValid() && dhip->areEquivalent(to_sh, bd_succ))
555  return gu_EdgeLoopCost(len, 0);
556 
557  GU_PathSHedge sided_quad_succ = successors(GU_EdgeSuccessor::QUAD_LEFT);
558  if (!sided_quad_succ.isValid())
559  sided_quad_succ = successors(GU_EdgeSuccessor::QUAD_RIGHT);
560 
562  if (!opposite.isValid())
563  opposite = successors(GU_EdgeSuccessor::OPPOSITE);
564 
565  bool to_sided_quad_succ = (sided_quad_succ.isValid() &&
566  dhip->areEquivalent(to_sh, sided_quad_succ));
567 
568  bool to_opposite = opposite.isValid() &&
569  dhip->areEquivalent(to_sh, opposite);
570 
571  if (to_sided_quad_succ)
572  return gu_EdgeLoopCost(len, 1);
573 
574  if (to_opposite)
575  return gu_EdgeLoopCost(len, 99);
576 
577  return gu_EdgeLoopCost(len, 100);
578  }
579 
581  fpreal getLength() { return myPathLength; }
582 
583 private:
584  fpreal myPathLength = -1.0;
585  int myPenalty = -1;
586 };
587 
588 
589 
591 {
592 public:
593  gu_EdgeRingCost() = default;
595  GU_PathHedge::Interface *dhip) :
596  myPenalty(0),
597  myPathLength(dhip->length(sh.hedge())) { }
598 
599  gu_EdgeRingCost(fpreal len, int bends) :
600  myPathLength(len), myPenalty(bends) { }
601 
602 
603  gu_EdgeRingCost(const gu_EdgeRingCost &c) = default;
604 
606  void zero()
607  {
608  myPathLength = 0.0;
609  myPenalty = 0;
610  }
611 
613  void unset() { myPathLength = -1.0; }
614 
616  bool isSet() { return myPathLength > -0.5; }
617 
619  bool operator>(const gu_EdgeRingCost &c) const
620  {
621  if (myPenalty != c.myPenalty)
622  return myPenalty > c.myPenalty;
623 
624  return myPathLength > c.myPathLength;
625  }
626 
627  gu_EdgeRingCost &operator=(const gu_EdgeRingCost &c) = default;
628 
630  const
632  {
633  myPenalty += c.myPenalty;
634  myPathLength += c.myPathLength;
635  return *this;
636  }
637 
639  static
641  const GU_PathSHedge& from_sh,
642  const GU_PathSHedge& to_sh,
643  const GU_EdgeSuccessor &successors)
644  {
645  fpreal len = dhip->length(to_sh.hedge());
646 
647  GU_PathSHedge bd_succ = successors(GU_EdgeSuccessor::BOUNDARY);
648  bool to_bd_succ = bd_succ.isValid() &&
649  dhip->areEquivalent(to_sh, bd_succ);
650 
651  if (to_bd_succ)
652  return gu_EdgeRingCost(len, 0);
653 
654  GU_PathSHedge sided_quad_succ = successors(GU_EdgeSuccessor::QUAD_LEFT);
655  if (!sided_quad_succ.isValid())
656  sided_quad_succ = successors(GU_EdgeSuccessor::QUAD_RIGHT);
657 
659  if (!opposite.isValid())
660  opposite = successors(GU_EdgeSuccessor::OPPOSITE);
661 
662  bool to_sided_quad_succ = (sided_quad_succ.isValid() &&
663  dhip->areEquivalent(to_sh, sided_quad_succ));
664 
665  bool to_opposite = opposite.isValid() &&
666  dhip->areEquivalent(to_sh, opposite);
667 
668  if (to_sided_quad_succ)
669  return gu_EdgeRingCost(len, 1);
670 
671  if (to_opposite)
672  return gu_EdgeRingCost(len, 99);
673 
674  return gu_EdgeRingCost(len, 100);
675  }
676 
678  fpreal getLength() { return myPathLength; }
679 
680 private:
681  fpreal myPathLength = -1.0;
682  int myPenalty = -1;
683 };
684 
685 
686 // Marking of signed half-edges: Each half-edge in each orientation is
687 // given a flag which can be set or checked.
688 
689 template <class T>
690 void
692 {
693  if (myDhip->isHedgeValidPolygon(sh.hedge()))
694  {
695  if (sh.isPositive())
696  myPolyPosMarked.setBitFast(sh.hedge().v0(), true);
697  else
698  myPolyNegMarked.setBitFast(sh.hedge().v0(), true);
699  }
700  else
701  {
702  if (sh.isPositive())
703  myPosMarked.insert(sh.hedge());
704  else
705  myNegMarked.insert(sh.hedge());
706  }
707 }
708 
709 template <class T>
710 bool
712 {
713  if (myDhip->isHedgeValidPolygon(sh.hedge()))
714  {
715  if (sh.isPositive())
716  return myPolyPosMarked.getBitFast(sh.hedge().v0());
717  else
718  return myPolyNegMarked.getBitFast(sh.hedge().v0());
719  }
720  else
721  {
722  if (sh.isPositive())
723  return myPosMarked.contains(sh.hedge());
724  else
725  return myNegMarked.contains(sh.hedge());
726  }
727 }
728 
729 template <class T>
730 void
732  const T &cost,
733  GU_PathSHedge prev_sh)
734 {
735  if (myDhip->isHedgeValidPolygon(sh.hedge()))
736  {
737  if (sh.isPositive())
738  {
739  myPolyPosCost[sh.hedge().v0()] = cost;
740  myPolyPosPrev[sh.hedge().v0()] = prev_sh;
741  }
742  else
743  {
744  myPolyNegCost[sh.hedge().v0()] = cost;
745  myPolyNegPrev[sh.hedge().v0()] = prev_sh;
746  }
747  }
748  else
749  {
750  if (sh.isPositive())
751  {
752  myPosCost[sh.hedge()] = cost;
753  myPosPrev[sh.hedge()] = prev_sh;
754  }
755  else
756  {
757  myNegCost[sh.hedge()] = cost;
758  myNegPrev[sh.hedge()] = prev_sh;
759  }
760  }
761 }
762 
763 template <class T>
764 T &
766 {
767  if (myDhip->isHedgeValidPolygon(sh.hedge()))
768  {
769  if (sh.isPositive())
770  return myPolyPosCost[sh.hedge().v0()];
771  else
772  return myPolyNegCost[sh.hedge().v0()];
773  }
774  else
775  {
776  if (sh.isPositive())
777  return myPosCost[sh.hedge()];
778  else
779  return myNegCost[sh.hedge()];
780  }
781 }
782 
783 
784 template <class T>
787 {
788  if (myDhip->isHedgeValidPolygon(sh.hedge()))
789  {
790  if (sh.isPositive())
791  return myPolyPosPrev[sh.hedge().v0()];
792  else
793  return myPolyNegPrev[sh.hedge().v0()];
794  }
795  else
796  {
797  if (sh.isPositive())
798  return myPosPrev[sh.hedge()];
799  else
800  return myNegPrev[sh.hedge()];
801  }
802 }
803 
804 
805 template <class T>
806 GA_Edge
807 GU_PathFinder<T>::gaEdge(const GU_PathSHedge & sh) const
808 {
809  return sh.isNegative() ?
810  GA_Edge(myDhip->dstPoint(sh.hedge()), myDhip->srcPoint(sh.hedge())) :
811  GA_Edge(myDhip->srcPoint(sh.hedge()), myDhip->dstPoint(sh.hedge()));
812 }
813 
814 
815 
818 
820 {
821  GU_NO_SUCCESSOR, // No viable successors to take
822  GU_HIT_BOUNDARY, // Reached a boundary
823  GU_HIT_SELF, // Crossed itself
824  GU_COMPLETED // Closed the path
825 };
826 
828  const GA_ROHandleV2 &uvh,
830  GU_SHedgeArray &walk,
831  bool backward = false,
832  bool no_self_intersection = false,
833  bool include_ends = false,
834  const GA_PrimitiveGroup * avoid_prims = nullptr,
835  const GA_PointGroup * avoid_points = nullptr,
836  const GA_VertexGroup * avoid_vtx = nullptr,
837  const GA_EdgeGroup * avoid_edges = nullptr,
838  const GA_Group * collision_group = nullptr,
839  bool exclude_collision = true,
840  bool strong_rule = true);
841 
843  const GA_ROHandleV2 &uvh,
845  GU_SHedgeArray &walk,
846  bool backward = false,
847  bool no_self_intersection = false,
848  bool include_ends = false,
849  const GA_PrimitiveGroup * avoid_prims = nullptr,
850  const GA_PointGroup * avoid_points = nullptr,
851  const GA_VertexGroup * avoid_vtx = nullptr,
852  const GA_EdgeGroup * avoid_edges = nullptr,
853  const GA_Group * collision_group = nullptr,
854  bool exclude_collision = true,
855  bool strong_rule = true);
856 
857 #endif
858 
GU_WalkEndReason GU_API guDualEdgeWalk(GU_PathHedge::Interface *dhip, const GA_ROHandleV2 &uvh, GU_SHedgeArray &path, GU_SHedgeArray &walk, bool backward=false, bool no_self_intersection=false, bool include_ends=false, const GA_PrimitiveGroup *avoid_prims=nullptr, const GA_PointGroup *avoid_points=nullptr, const GA_VertexGroup *avoid_vtx=nullptr, const GA_EdgeGroup *avoid_edges=nullptr, const GA_Group *collision_group=nullptr, bool exclude_collision=true, bool strong_rule=true)
GA_Size entries() const override
Returns the number of edges in this group.
Definition: GA_EdgeGroup.h:303
SYS_FORCE_INLINE void unset()
SYS_FORCE_INLINE GA_Offset srcPoint(const GA_Detail *gdp, GEO_Hedge h)
Definition: GEO_Hedge.h:186
SYS_FORCE_INLINE bool isPositive() const
Definition: GU_PathHedge.h:380
void avoidGroups(GA_PointGroup *ptgrp, GA_EdgeGroup *edgegrp, GA_VertexGroup *vtxgrp, GA_PrimitiveGroup *primgrp)
Definition of a geometry attribute.
Definition: GA_Attribute.h:196
const GU_SHedgeArray & getStartSHedges() const
SYS_FORCE_INLINE gu_ShortestPathCost & operator=(const gu_ShortestPathCost &c)=default
void avoidPoints(GA_PointGroup *grp)
GU_WalkEndReason GU_API guEdgeWalk(GU_PathHedge::Interface *dhip, const GA_ROHandleV2 &uvh, GU_SHedgeArray &path, GU_SHedgeArray &walk, bool backward=false, bool no_self_intersection=false, bool include_ends=false, const GA_PrimitiveGroup *avoid_prims=nullptr, const GA_PointGroup *avoid_points=nullptr, const GA_VertexGroup *avoid_vtx=nullptr, const GA_EdgeGroup *avoid_edges=nullptr, const GA_Group *collision_group=nullptr, bool exclude_collision=true, bool strong_rule=true)
SYS_FORCE_INLINE fpreal length(const GU_PathHedge &h) const
Definition: GU_PathHedge.h:249
GU_PathSHedge operator()(int i) const
Definition: GU_PathFinder.h:65
GA_Size entries() const overridefinal
Will return the number of primary elements.
SYS_FORCE_INLINE const gu_EdgeLoopCost & operator+=(const gu_EdgeLoopCost &c)
SYS_FORCE_INLINE void unset()
SYS_FORCE_INLINE fpreal getLength()
gu_EdgeLoopCost & operator=(const gu_EdgeLoopCost &c)=default
SYS_FORCE_INLINE fpreal getLength()
SYS_FORCE_INLINE bool isNegative() const
Definition: GU_PathHedge.h:383
PathEdge(GU_PathSHedge sh, GU_PathSHedge prev=GU_PathSHedge())
Definition: GU_PathFinder.h:95
GLdouble l
Definition: glew.h:9122
SYS_FORCE_INLINE bool areEquivalent(const GU_PathHedge &h1, const GU_PathHedge &h2)
Definition: GU_PathHedge.h:174
SYS_FORCE_INLINE const GU_PathHedge & hedge() const
Definition: GU_PathHedge.h:369
GLboolean reset
Definition: glew.h:4959
GA_EdgeT< GA_Offset, false > GA_Edge
Definition: GA_Edge.h:91
gu_EdgeRingCost(const GU_PathSHedge &sh, GU_PathHedge::Interface *dhip)
SYS_FORCE_INLINE void zero()
PathEdge(GU_PathSHedge sh, GU_PathSHedge prev, const T &cost)
Definition: GU_PathFinder.h:99
#define GA_INVALID_OFFSET
Definition: GA_Types.h:676
SYS_FORCE_INLINE T & getBestCost(const GU_PathSHedge &sh)
SYS_FORCE_INLINE bool isSet()
GU_PathSHedge getSHedge()
SYS_FORCE_INLINE bool isValid() const
Definition: GU_PathHedge.h:366
bool isEndOnBoundary()
gu_ShortestPathCost(const GU_PathSHedge &sh, GU_PathHedge::Interface *dhip)
GA_Size GA_Offset
Definition: GA_Types.h:639
GU_PathFinder< gu_EdgeRingCost > GU_EdgeRingFinder
gu_EdgeLoopCost(const gu_EdgeLoopCost &c)
GU_PathFinder< gu_EdgeLoopCost > GU_EdgeLoopFinder
gu_ShortestPathCost(fpreal l)
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
SYS_FORCE_INLINE fpreal getLength()
const GLfloat * c
Definition: glew.h:16296
GLuint GLsizei GLsizei * length
Definition: glew.h:1825
SYS_FORCE_INLINE bool isSet()
void resetAvoidGroups()
SYS_FORCE_INLINE const gu_ShortestPathCost & operator+=(const gu_ShortestPathCost &c)
#define GU_API
Definition: GU_API.h:14
GLfloat GLfloat GLfloat GLfloat h
Definition: glew.h:8011
void avoidPrimitives(GA_PrimitiveGroup *grp)
gu_EdgeRingCost & operator=(const gu_EdgeRingCost &c)=default
GU_WalkEndReason
GA_GroupType classType() const
Definition: GA_Group.h:54
SYS_FORCE_INLINE bool operator>(const gu_EdgeLoopCost &c) const
void avoidVertices(GA_VertexGroup *grp)
gu_EdgeLoopCost()=default
GLsizei const GLchar *const * path
Definition: glew.h:6461
static SYS_FORCE_INLINE gu_ShortestPathCost turnCost(GU_PathHedge::Interface *dhip, const GU_PathSHedge &from_sh, const GU_PathSHedge &to_sh, const GU_EdgeSuccessor &exits)
bool isStartOnBoundary()
SYS_FORCE_INLINE void unset()
bool operator()(PathEdge &p1, PathEdge &p2) const
SYS_FORCE_INLINE bool operator>(const gu_EdgeRingCost &c) const
SYS_FORCE_INLINE bool isSet()
fpreal64 fpreal
Definition: SYS_Types.h:277
GU_PathSHedge getPrev()
gu_EdgeLoopCost(fpreal len, int bends)
SYS_FORCE_INLINE bool operator>(const gu_ShortestPathCost &c) const
static SYS_FORCE_INLINE gu_EdgeRingCost turnCost(GU_PathHedge::Interface *dhip, const GU_PathSHedge &from_sh, const GU_PathSHedge &to_sh, const GU_EdgeSuccessor &successors)
gu_EdgeRingCost()=default
SYS_FORCE_INLINE void zero()
gu_EdgeRingCost(fpreal len, int bends)
Container class for all geometry.
Definition: GA_Detail.h:95
gu_ShortestPathCost()=default
void avoidEdges(GA_EdgeGroup *grp)
SYS_FORCE_INLINE Side opposite(Side s)
const GEO_DetachedHedgeInterface HedgeInterface
Definition: GU_Decompose.h:54
void setCollisionGroup(const GA_Group *group, bool exclude, bool strong)
SYS_FORCE_INLINE void zero()
SYS_FORCE_INLINE GA_Offset v0() const
Definition: GU_PathHedge.h:45
SYS_FORCE_INLINE const gu_EdgeRingCost & operator+=(const gu_EdgeRingCost &c)
GLdouble GLdouble t
Definition: glew.h:1398
gu_EdgeLoopCost(const GU_PathSHedge &sh, GU_PathHedge::Interface *dhip)
static Mask typeMask(Type t)
Definition: GU_PathFinder.h:68
static SYS_FORCE_INLINE gu_EdgeLoopCost turnCost(GU_PathHedge::Interface *dhip, const GU_PathSHedge &from_sh, const GU_PathSHedge &to_sh, const GU_EdgeSuccessor &successors)
GLboolean GLuint group
Definition: glew.h:2745
GLenum GLsizei len
Definition: glew.h:7752
SYS_FORCE_INLINE GA_Offset dstPoint(T &iface, GEO_Hedge h)
Definition: GEO_Hedge.h:244
GU_PathSHedge & operator()(int i)
Definition: GU_PathFinder.h:64