HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GEO_AdjPolyIterator.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: Adjacent Polygon Iterator
7  *
8  * COMMENTS: This iterator has multiple functionalities:
9  * 1. iterate through polygons adjacent to a single point
10  * 2. iterate through polygons adjacent to a single polygon
11  * 3. iterate through polygons adjacent to a list of polygons
12  *
13  */
14 
15 #ifndef __GEO_AdjPolyIterator_h__
16 #define __GEO_AdjPolyIterator_h__
17 
18 #include "GEO_Detail.h"
19 #include "GEO_PrimPoly.h"
20 #include <UT/UT_Interrupt.h>
21 #include <queue>
22 
24 {
25 protected:
31 
32 public:
33  // iteration routines
34  virtual bool advance() = 0;
35  void rewind() { myIterationCount = 0; }
36  GEO_AdjPolyIterator &operator++() { advance(); return *this; }
37 
38  // state accessors
39  GEO_PrimPoly *getAdjPoly() { return myAdjacentPoly; }
40 
41  // constructor
43  const GA_PrimitiveGroup *process_grp = NULL )
44  : myGdp(gdp), myProcess(process_grp), myIterationCount(-1)
45  , myAdjacentPoly(NULL), myNumAdjacentPolys(-1)
46  { }
47 
48  virtual ~GEO_AdjPolyIterator() { }
49 };
50 
51 
52 // This is an iterator of a UT_ValArray<GA_Offset> returned from
53 // getPrimitivesReferencingPoint() from GEO_Detail. However it skipps all
54 // primitives that aren't of the type GEO_PRIMPOLY
56 {
57 private:
58  GA_OffsetArray myAdjacentPolys;
59 
60 public:
61  virtual bool advance()
62  {
63  while( ++myIterationCount < myNumAdjacentPolys )
64  {
65  GA_Offset adj_poly_off = myAdjacentPolys(myIterationCount);
66 
67  if( myProcess && !myProcess->containsOffset(adj_poly_off) )
68  continue;
69 
70  GA_Primitive *adj_prim =
71  myGdp->getPrimitiveList().get(adj_poly_off);
72  myAdjacentPoly = static_cast<GEO_PrimPoly*>(adj_prim);
73 
74  return true;
75  }
76 
77  rewind();
78  return false;
79  }
80 
82  GA_Offset pt_offset,
83  const GA_PrimitiveGroup *process_grp = NULL )
84  : GEO_AdjPolyIterator(gdp, process_grp)
85  {
86  myNumAdjacentPolys =
87  gdp->getPrimitivesReferencingPoint(myAdjacentPolys, pt_offset);
88  }
89 
91 };
92 
93 // This is an iterator of a an array of adjacency data that includes the
94 // adjacent polygon offset, and the point shared between the original polygon
95 // and the adjacency. This data is returned by getPointAdjacentPolygons()
96 // from GEO_Detail
98 {
99 private:
100  GEO_Detail::GEO_PointAdjArray myAdjacencyData;
101  GA_Offset mySharedPoint;
102 
103 public:
104  virtual bool advance()
105  {
106  while( ++myIterationCount < myNumAdjacentPolys )
107  {
109  myAdjacencyData(myIterationCount);
110  GA_Offset adj_poly_off = data.myAdjacentPolygon;
111 
112  if( myProcess && !myProcess->containsOffset(adj_poly_off) )
113  continue;
114 
115  GA_Primitive *adj_prim =
116  myGdp->getPrimitiveList().get(adj_poly_off);
117  myAdjacentPoly = static_cast<GEO_PrimPoly*>(adj_prim);
118  mySharedPoint = data.mySharedPoint;
119 
120  return true;
121  }
122 
123  rewind();
124  return false;
125  }
126 
127  GA_Offset getSharedPoint() { return mySharedPoint; }
128 
130  GA_Offset poly_offset,
131  const GA_PrimitiveGroup *process_grp = NULL )
132  : GEO_AdjPolyIterator(gdp, process_grp)
133  , mySharedPoint(GA_INVALID_OFFSET)
134  {
135  myNumAdjacentPolys =
136  gdp->getPointAdjacentPolygons(myAdjacencyData, poly_offset);
137  }
138 
140 };
141 
142 // This is an iterator of an array of adjacency data that includes the
143 // adjacent polygon offset, the shared edge and a boolean indicating whether
144 // the winding order between poly and it's adjacent poly is reversed or not.
145 // Information is provided by the getEdgeAdjacentPolygons() call from
146 // GEO_Detail.
148 {
149 private:
150  GEO_Detail::GEO_EdgeAdjArray myAdjacencyData;
151  GA_Offset myStartEdgePt;
152  GA_Offset myEndEdgePt;
153  bool myWindingReversed;
154 
155 public:
156  virtual bool advance()
157  {
158  while( ++myIterationCount < myNumAdjacentPolys )
159  {
161  myAdjacencyData(myIterationCount);
162  GA_Offset adj_poly_off = data.myAdjacentPolygon;
163 
164  if( myProcess && !myProcess->containsOffset(adj_poly_off) )
165  continue;
166 
167  GA_Primitive *adj_prim =
168  myGdp->getPrimitiveList().get(adj_poly_off);
169  myAdjacentPoly = static_cast<GEO_PrimPoly*>(adj_prim);
170  myStartEdgePt = data.myStartEdgePoint;
171  myEndEdgePt = data.myEndEdgePoint;
172  myWindingReversed = data.myWindingReversed;
173 
174  return true;
175  }
176 
177  rewind();
178  return false;
179  }
180 
181  bool isWindingReversed() { return myWindingReversed; }
182  GA_Offset getStartEdgePt() { return myStartEdgePt; }
183  GA_Offset getEndEdgePt() { return myEndEdgePt; }
184 
186  GA_Offset poly_offset,
187  const GA_PrimitiveGroup *process_grp = NULL )
188  : GEO_AdjPolyIterator(gdp, process_grp), myStartEdgePt(GA_INVALID_OFFSET)
189  , myEndEdgePt(GA_INVALID_OFFSET), myWindingReversed(false)
190  {
191  myNumAdjacentPolys =
192  gdp->getEdgeAdjacentPolygons(myAdjacencyData, poly_offset);
193  }
194 
196 };
197 
198 //
199 // Iterator Visitors
200 //
201 
202 // TODO: rename the callbacks to something more meaningful
204 {
205 public:
206  // these are pure virtual to insure that you can't instantiate this class
207  virtual void onVisitedPoly(GEO_PrimPoly *visited) = 0;
208  virtual void onEndOfConnectedGeometry() = 0;
209  virtual void onStartOfConnectedGeometry(GEO_PrimPoly *source) = 0;
211 };
212 
214 {
215 public:
216  virtual void onVisitedPoly(GEO_PrimPoly *visited) { }
217  virtual void onEndOfConnectedGeometry() { }
219 
220  // Override these callbacks for EDGE adjacent BFS traverser
221  virtual void onNewlyDiscoveredPoly(GEO_PrimPoly *visited,
222  GEO_PrimPoly *discovered,
223  GA_Offset edge_start_pt,
224  GA_Offset edge_end_pt,
225  bool winding_reversed) { }
226 
228  GEO_PrimPoly *discovered,
229  GA_Offset edge_start_pt,
230  GA_Offset edge_end_pt,
231  bool winding_reversed) { }
232 
233 };
234 
236 {
237 public:
238  virtual void onVisitedPoly(GEO_PrimPoly *visited) { }
239  virtual void onEndOfConnectedGeometry() { }
241 
242  // Override these callbacks for POINT adjacent BFS traverser
243  virtual void onNewlyDiscoveredPoly(GEO_PrimPoly *visited,
244  GEO_PrimPoly *discovered,
245  GA_Offset shared_pt) { }
246 
248  GEO_PrimPoly *discovered,
249  GA_Offset shared_pt) { }
250 };
251 
252 // Breadth First Polygon Iterator
253 // iterator over all adjacent polygons via BFS
255 {
256 protected:
258  GEO_PrimPoly *myVisitedPoly, *myDiscoveredPoly;
259  GA_Offset myVisitedOffset, myDiscoveredOffset;
262 
263  // visited polygons. Used to avoid cycles in the BFS algorithm
265 
266  // Queue implementation used for breadth-first traversal
267  class OffsetQueue : public std::queue<GA_Offset>
268  {
269  public:
270  void enqueue(GA_Offset thing) { std::queue<GA_Offset>::push(thing); }
271 
273  {
274  GA_Offset thing = std::queue<GA_Offset>::front();
275  std::queue<GA_Offset>::pop();
276  return thing;
277  }
278  } myQueue;
279 
280 private:
281  GA_Iterator myProcessIt;
282 
283  GEO_PrimPoly * getPolyFromOffset(GA_Offset poly_off);
284 
285  UT_Interrupt *myBoss;
286  GA_Size myProgressCounter;
287 protected:
288  virtual void iterateThroughAdjacentPolygons() = 0;
289 
290 public:
291  // Trigger
292  void run();
293 
294 private:
295  void init( bool insure_poly_only );
296 
297 public:
298  // constructors to iterate over all polygons and their adjacencies
299  // contained in the process group, bitarray or the whole gdp via
300  // breadth first search
301  // TODO: initialize EVERYTHING
303  const GA_PrimitiveGroup *process_grp,
304  GEO_BFSTraverserVisitor &visitor,
305  UT_Interrupt *boss,
306  bool insure_poly_only )
307  : myVisitedPoly(NULL), myGdp(gdp), myVisitor(visitor), myBoss(boss), myProgressCounter(0)
308  {
309  myProcess = myGdp->newInternalPrimitiveGroup();
310  myProcess->copyMembership(*process_grp); // make a copy
311  init( insure_poly_only );
312  }
313 
315  GEO_BFSTraverserVisitor &visitor,
316  UT_Interrupt *boss)
317  : myVisitedPoly(NULL), myGdp(gdp), myVisitor(visitor), myBoss(boss), myProgressCounter(0)
318  {
319  myProcess = myGdp->newInternalPrimitiveGroup();
320  myProcess->toggleEntries();
321  init( true );
322  }
323 
325  {
326  myGdp->destroyPrimitiveGroup(myProcess);
327  myGdp->destroyPrimitiveGroup(myDiscoveredPolyGrp);
328  }
329 };
330 
332 {
333 protected:
334  virtual void iterateThroughAdjacentPolygons();
335 
336 public:
338  const GA_PrimitiveGroup *process_grp,
339  GEO_BFSTraverserVisitor &visitor,
340  UT_Interrupt *boss = NULL,
341  bool insure_poly_only = false )
342  : GEO_BFSAdjPolyTraverser( gdp, process_grp, visitor, boss, insure_poly_only )
343  { }
344 
346  GEO_BFSTraverserVisitor &visitor,
347  UT_Interrupt *boss = NULL)
348  : GEO_BFSAdjPolyTraverser( gdp, visitor, boss )
349  { }
350 
351 };
352 
354 {
355 protected:
356  virtual void iterateThroughAdjacentPolygons();
357 
358 public:
360  const GA_PrimitiveGroup *process_grp,
361  GEO_BFSTraverserVisitor &visitor,
362  UT_Interrupt *boss = NULL,
363  bool insure_poly_only = false )
364  : GEO_BFSAdjPolyTraverser( gdp, process_grp, visitor, boss, insure_poly_only )
365  { }
366 
368  GEO_BFSTraverserVisitor &visitor,
369  UT_Interrupt *boss)
370  : GEO_BFSAdjPolyTraverser( gdp, visitor, boss )
371  { }
372 
373 };
374 
375 //
376 // Macros
377 //
378 // WARNING: each of these iterators allocates space for an array of
379 // primitives so use with care
380 
381 // iterate through polygons adjacent to a single point
382 #define GEO_FOR_ALL_POLY_ADJ_TO_PT( gdp, pt_offset, adj_poly ) \
383  GEO_PointAdjPolyIterator poly_it( (gdp), (pt_offset) ); \
384  while( poly_it.advance() && (adj_poly = poly_it.getAdjPoly()) )
385 
386 #define GEO_FOR_ALL_GROUP_POLY_ADJ_TO_PT( gdp, grp, pt_offset, adj_poly ) \
387  GEO_PointAdjPolyIterator poly_it( (gdp), (pt_offset), (grp) ); \
388  while( poly_it.advance() && (adj_poly = poly_it.getAdjPoly()) )
389 
390 // iterate through polygons adjacent to a single polygon
391 #define GEO_FOR_ALL_POLY_EDGE_ADJ_TO_POLY( gdp, poly, adj_poly ) \
392  GEO_EdgeAdjPolyIterator poly_it( (gdp), (poly)->getMapOffset() ); \
393  while( poly_it.advance() && (adj_poly = poly_it.getAdjPoly()) )
394 
395 #define GEO_FOR_ALL_GROUP_POLY_EDGE_ADJ_TO_POLY( gdp, grp, poly, adj_poly ) \
396  GEO_EdgeAdjPolyIterator poly_it( (gdp), (poly)->getMapOffset(), (grp) ); \
397  while( poly_it.advance() && (adj_poly = poly_it.getAdjPoly()) )
398 
399 #define GEO_FOR_ALL_POLY_ADJ_TO_POLY( gdp, poly, adj_poly ) \
400  GEO_PolyAdjPolyIterator poly_it( (gdp), (poly)->getMapOffset() ); \
401  while( poly_it.advance() && (adj_poly = poly_it.getAdjPoly()) )
402 
403 #define GEO_FOR_ALL_GROUP_POLY_ADJ_TO_POLY( gdp, grp, poly, adj_poly ) \
404  GEO_PolyAdjPolyIterator poly_it( (gdp), (poly)->getMapOffset(), (grp) ); \
405  while( poly_it.advance() && (adj_poly = poly_it.getAdjPoly()) )
406 
407 // for BFS iteration please use the visitors
408 
409 #endif
virtual void onNewlyDiscoveredPoly(GEO_PrimPoly *visited, GEO_PrimPoly *discovered, GA_Offset shared_pt)
GEO_PrimPoly * myAdjacentPoly
virtual void onPreviouslyDiscoveredPoly(GEO_PrimPoly *visited, GEO_PrimPoly *discovered, GA_Offset shared_pt)
Iteration over a range of elements.
Definition: GA_Iterator.h:28
virtual void onStartOfConnectedGeometry(GEO_PrimPoly *source)
const GA_PrimitiveGroup * myProcess
GEO_BFSAdjPolyTraverser(GEO_Detail *gdp, const GA_PrimitiveGroup *process_grp, GEO_BFSTraverserVisitor &visitor, UT_Interrupt *boss, bool insure_poly_only)
GEO_BFSEdgeAdjPolyTraverser(GEO_Detail *gdp, GEO_BFSTraverserVisitor &visitor, UT_Interrupt *boss=NULL)
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:211
GEO_PrimPoly * getAdjPoly()
virtual void onStartOfConnectedGeometry(GEO_PrimPoly *source)
virtual void onEndOfConnectedGeometry()
#define GA_INVALID_OFFSET
Definition: GA_Types.h:654
virtual void onNewlyDiscoveredPoly(GEO_PrimPoly *visited, GEO_PrimPoly *discovered, GA_Offset edge_start_pt, GA_Offset edge_end_pt, bool winding_reversed)
virtual void onPreviouslyDiscoveredPoly(GEO_PrimPoly *visited, GEO_PrimPoly *discovered, GA_Offset edge_start_pt, GA_Offset edge_end_pt, bool winding_reversed)
GA_Size GA_Offset
Definition: GA_Types.h:617
GA_Size getEdgeAdjacentPolygons(GEO_EdgeAdjArray &adjacencies, GA_Offset poly_off) const
GEO_BFSPointAdjPolyTraverser(GEO_Detail *gdp, GEO_BFSTraverserVisitor &visitor, UT_Interrupt *boss)
GEO_BFSEdgeAdjPolyTraverser(GEO_Detail *gdp, const GA_PrimitiveGroup *process_grp, GEO_BFSTraverserVisitor &visitor, UT_Interrupt *boss=NULL, bool insure_poly_only=false)
GEO_PolyAdjPolyIterator(GEO_Detail *gdp, GA_Offset poly_offset, const GA_PrimitiveGroup *process_grp=NULL)
GEO_BFSPointAdjPolyTraverser(GEO_Detail *gdp, const GA_PrimitiveGroup *process_grp, GEO_BFSTraverserVisitor &visitor, UT_Interrupt *boss=NULL, bool insure_poly_only=false)
GA_PrimitiveGroup * myProcess
GLsizei GLsizei GLchar * source
Definition: glcorearb.h:802
#define GEO_API
Definition: GEO_API.h:10
virtual void onVisitedPoly(GEO_PrimPoly *visited)
GLboolean * data
Definition: glcorearb.h:130
GA_Size getPointAdjacentPolygons(GEO_PointAdjArray &adjacencies, GA_Offset poly_off) const
virtual void onVisitedPoly(GEO_PrimPoly *visited)
GEO_BFSTraverserVisitor & myVisitor
GEO_AdjPolyIterator & operator++()
virtual void iterateThroughAdjacentPolygons()=0
GEO_AdjPolyIterator(GEO_Detail *gdp, const GA_PrimitiveGroup *process_grp=NULL)
GEO_PointAdjPolyIterator(GEO_Detail *gdp, GA_Offset pt_offset, const GA_PrimitiveGroup *process_grp=NULL)
GEO_EdgeAdjPolyIterator(GEO_Detail *gdp, GA_Offset poly_offset, const GA_PrimitiveGroup *process_grp=NULL)
GA_PrimitiveGroup * myDiscoveredPolyGrp
GA_Size getPrimitivesReferencingPoint(GA_OffsetArray &primitives, GA_Offset point_offset) const
Given a point offset, return a list of all primitives which reference it.
GEO_BFSAdjPolyTraverser(GEO_Detail *gdp, GEO_BFSTraverserVisitor &visitor, UT_Interrupt *boss)