HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GA_PolyCounts.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: GA_PolyCounts.h (GA Library, C++)
7  *
8  * COMMENTS: Implementation of a simple run-length encoded array
9  * intended for storing polygon vertex counts.
10  */
11 
12 #ifndef __GA_PolyCounts__
13 #define __GA_PolyCounts__
14 
15 #include "GA_API.h"
16 
17 #include "GA_Types.h"
18 #include <UT/UT_Array.h>
19 #include <UT/UT_Assert.h>
20 #include <SYS/SYS_Inline.h>
21 #include <SYS/SYS_Types.h>
22 
23 #include <tbb/tbb_stddef.h>
24 typedef tbb::split UT_Split;
25 
27 {
28 public:
29 
30  class SizeCount
31  {
32  public:
33  SizeCount() {}
34  SizeCount(int sz, int ct)
35  : mySize(sz)
36  , myCount(ct)
37  {}
38  SizeCount(const SizeCount &that)
39  : mySize(that.mySize)
40  , myCount(that.myCount)
41  {}
42  const int &size() const { return mySize; }
43  const int &count() const { return myCount; }
44  int &size() { return mySize; }
45  int &count() { return myCount; }
46  GA_Size product() const { return GA_Size(mySize)*GA_Size(myCount); }
47 
48  typedef int InternalType;
49  private:
50  int mySize;
51  int myCount;
52  };
53 
54  template<typename CLASS,typename ARRAYCLASS>
55  class iteratorT
56  {
57  public:
58  iteratorT() {}
59  iteratorT(CLASS &list)
60  : myArray(&list.array)
61  , myPolygon(0)
62  , myStart(0)
63  , myIndex(0)
64  , myCount(0)
65  {}
66  iteratorT(CLASS &list, GA_Size polygon)
67  : myArray(&list.array)
68  , myPolygon(polygon)
69  {
70  ARRAYCLASS &array = *myArray;
71  UT_ASSERT_P(array.entries() != 0);
72  GA_Size start = 0;
73  GA_Size i;
74  for (i = 0; i < array.entries()
75  && polygon >= array(i).count(); ++i)
76  {
77  start += array(i).product();
78  polygon -= array(i).count();
79  }
80  if (i < array.entries())
81  start += polygon*array(i).size();
82  myStart = start;
83  myIndex = i;
84  myCount = polygon;
85  }
87  : myArray(that.myArray)
88  , myPolygon(that.myPolygon)
89  , myStart(that.myStart)
90  , myIndex(that.myIndex)
91  , myCount(that.myCount)
92  {}
93  iteratorT(ARRAYCLASS *array, GA_Size polygon, GA_Size start, GA_Size index, GA_Size count)
94  : myArray(array)
95  , myPolygon(polygon)
96  , myStart(start)
97  , myIndex(index)
98  , myCount(count)
99  {}
100  SYS_FORCE_INLINE bool atEnd() const
101  {
102  return myIndex == (*myArray).entries();
103  }
105  {
106  ++myPolygon;
107  myStart += nvertices();
108  ++myCount;
109  if (myCount == (*myArray)(myIndex).count())
110  {
111  myCount = 0;
112  ++myIndex;
113  }
114  return *this;
115  }
117  {
118  if (myCount == 0)
119  {
120  --myIndex;
121  myCount = (*myArray)(myIndex).count();
122  }
123  --myCount;
124  myStart -= nvertices();
125  --myPolygon;
126  return *this;
127  }
129  {
130  if (count == 0)
131  return *this;
132 
133  ARRAYCLASS &array = *myArray;
134 
135  GA_Size polygon = myPolygon + count;
136  UT_ASSERT_P(polygon >= 0);
137  GA_Size start = myStart;
138  GA_Size i = myIndex;
139  count += myCount;
140  // If in the same block, just adjust start
141  if (count >= 0 && count < array(i).count())
142  {
143  start += (count - myCount)*array(i).size();
144  }
145  // If past the end of the current block
146  else if (count >= array(i).count())
147  {
148  start += (array(i).count() - myCount)*array(i).size();
149  count -= array(i).count();
150  for (++i; i < array.entries() && count >= array(i).count(); ++i)
151  {
152  start += array(i).product();
153  count -= array(i).count();
154  }
155  if (i < array.entries())
156  start += count*array(i).size();
157  }
158  // If before the beginning of the current block
159  else
160  {
161  if (i < array.entries())
162  start -= myCount*array(i).size();
163  for (--i; -count >= array(i).count(); --i)
164  {
165  start -= array(i).product();
166  count += array(i).count();
167  }
168  start -= (array(i).count() + count)*array(i).size();
169  count += array(i).count();
170  }
171  return iteratorT<CLASS, ARRAYCLASS>(myArray, polygon, start, i, count);
172  }
174  {
175  return (*this)+(-count);
176  }
178  {
179  if (&that!=this)
180  {
181  // NOTE: Cannot assign from an iterator
182  // of a different GA_PolyCounts
183  myArray = that.myArray;
184  myPolygon = that.myPolygon;
185  myStart = that.myStart;
186  myIndex = that.myIndex;
187  myCount = that.myCount;
188  }
189  return *this;
190  }
191  bool operator==(const iteratorT<CLASS, ARRAYCLASS> &that) const
192  {
193  // NOTE: For efficiency, cannot compare with an iterator
194  // of a different GA_PolyCounts
195  return (myPolygon == that.myPolygon);
196  }
197  bool operator!=(const iteratorT<CLASS, ARRAYCLASS> &that) const
198  {
199  // NOTE: For efficiency, cannot compare with an iterator
200  // of a different GA_PolyCounts
201  return (myPolygon != that.myPolygon);
202  }
204  {
205  return (*myArray)(myIndex).size();
206  }
208  {
209  return myPolygon;
210  }
212  {
213  return myStart;
214  }
215 
216  private:
217  ARRAYCLASS *myArray;
218  GA_Size myPolygon;
219  GA_Size myStart;
220  GA_Size myIndex;
221  GA_Size myCount;
222  };
225 
226  /// Range class for multi-threading with TBB
227  class Range
228  {
229  public:
230  Range(const GA_PolyCounts &list)
231  : myIt(list)
232  , myNPolygons(list.getNumPolygons())
233  , myGrainSize(1)
234  {}
235  Range(const GA_PolyCounts &list, GA_Size begin, GA_Size end, GA_Size grainsize = 1)
236  : myIt(list)
237  , myNPolygons(list.getNumPolygons())
238  , myGrainSize(grainsize)
239  {}
241  : myIt(that.myIt + that.myNPolygons/2)
242  , myNPolygons(that.myNPolygons - (that.myNPolygons/2))
243  , myGrainSize(that.myGrainSize)
244  {
245  that.myNPolygons = that.myNPolygons/2;
246  }
247 
248  const_iterator begin() const { return myIt; }
249 
250  // NOTE: DO NOT use the return value from end() as a real iterator;
251  // It is intended for uses like: it != end()
252  // Constructing a full end iterator is expensive, and if
253  // necessary, can be done with: begin() + size()
255  { return const_iterator(NULL, myIt.polygon() + myNPolygons, 0, 0, 0); }
256 
257  GA_Size size() const { return myNPolygons; }
258  GA_Size grainsize() const { return myGrainSize; }
259  bool empty() const { return myNPolygons == 0; }
260  bool is_divisible() const { return myNPolygons >= 2*myGrainSize; }
261  private:
262  const_iterator myIt;
263  GA_Size myNPolygons;
264  const GA_Size myGrainSize;
265  };
266 
268  {}
269 
271  : array(that.array)
272  {}
273 
275  {
276  if (this == &that)
277  return *this;
278 
279  array = that.array;
280  return *this;
281  }
282 
283  iterator begin() { return iterator(*this); }
284  const_iterator begin() const { return const_iterator(*this); }
285 
286  // NOTE: DO NOT use the return value from end() as a real iterator;
287  // It is intended for uses like: it != end()
288  // Constructing a full end iterator is expensive, and if
289  // necessary, can be done with: begin() + size()
290  const_iterator end() const { return const_iterator(NULL, getNumPolygons(), 0, 0, 0); }
291 
292  const_iterator findVertex(GA_Size relativevertex) const
293  {
294  GA_Size start = relativevertex;
295  GA_Size polygon = 0;
296  GA_Size i;
297  for (i = 0; i < array.entries()
298  && relativevertex >= array(i).product(); ++i)
299  {
300  relativevertex -= array(i).product();
301  polygon += array(i).count();
302  }
303  GA_Size count = 0;
304  if (relativevertex)
305  {
306  GA_Size remainder;
307  SYSdivMod(relativevertex, GA_Size(array(i).size()), count, remainder);
308  polygon += count;
309  start -= remainder;
310  }
311  return const_iterator(&array, polygon, start, i, count);
312  }
313 
314  Range range() const { return Range(*this); }
315 
316  UT_Array<SizeCount> &getArray() { return array; }
317  const UT_Array<SizeCount> &getArray() const { return array; }
318 
319  void clear() { array.clear(); }
320 
321  /// Adds "count" polygons with "size" vertices each to the end of the list.
322  /// For example, to add 5000000 triangles, call append(3,5000000).
323  /// Since this is run-length encoded, if the last entry was already
324  /// for polygons with "size" vertices, "count" will just be added to
325  /// the last entry.
327  {
328  if (count == 0)
329  return;
330  if (array.entries() && array.last().size() == size)
331  array.last().count() += count;
332  else
333  array.append(SizeCount(size, count));
334  }
335 
336  void append(const GA_PolyCounts &that)
337  {
338  if (!that.array.entries())
339  return;
340 
341  if (array.entries() && array.last().size() == that.array(0).size())
342  array.last().count() += that.array(0).count();
343  else
344  array.append(that.array(0));
345 
346  for (GA_Size i = 1; i < that.array.entries(); ++i)
347  array.append(that.array(i));
348  }
349 
351  GA_Size sum = 0;
352  for (GA_Size i = 0; i < array.entries(); ++i)
353  sum += array(i).count();
354  return sum;
355  }
356 
358  GA_Size sum = 0;
359  for (GA_Size i = 0; i < array.entries(); ++i)
360  sum += array(i).product();
361  return sum;
362  }
363 
364  /// Simpler than getVertexRange if you just want the polygon size
365  GA_Size getSize(GA_Size polygon) const
366  {
367  UT_ASSERT_P(array.entries() != 0);
368  GA_Size i;
369  for (i = 0; polygon >= array(i).count(); ++i)
370  polygon -= array(i).count();
371  return array(i).size();
372  }
373 
374  void getVertexRange(GA_Size polygon, GA_Size &start, GA_Size &size) const
375  {
376  UT_ASSERT_P(array.entries() != 0);
377  GA_Size index = 0;
378  GA_Size i;
379  for (i = 0; polygon >= array(i).count(); ++i)
380  {
381  index += array(i).product();
382  polygon -= array(i).count();
383  }
384  index += polygon*array(i).size();
385  start = index;
386  size = array(i).size();
387  }
388 
389  int64 getMemoryUsage(bool inclusive) const
390  { return (inclusive ? sizeof(*this) : 0) + array.getMemoryUsage(false); }
391 
392 private:
393  UT_Array<SizeCount> array;
394 };
395 
396 /// This is needed by the tbb wrapper in UT_ParallelUtil
397 /// It returns an upper bound for the actual number of work items
398 /// in the range.
400 {
401  return range.size();
402 }
403 
404 #endif
Range class for multi-threading with TBB.
GA_API size_t UTestimatedNumItems(const GA_PolyCounts::Range &range)
Range(const GA_PolyCounts &list, GA_Size begin, GA_Size end, GA_Size grainsize=1)
const_iterator end() const
GLenum GLint * range
Definition: glcorearb.h:1924
const UT_Array< SizeCount > & getArray() const
UT_Array< SizeCount > & getArray()
iteratorT(CLASS &list, GA_Size polygon)
Definition: GA_PolyCounts.h:66
tbb::split UT_Split
Definition: GA_PolyCounts.h:24
void append(const GA_PolyCounts &that)
GLuint start
Definition: glcorearb.h:474
bool is_divisible() const
SizeCount(const SizeCount &that)
Definition: GA_PolyCounts.h:38
const int & size() const
Definition: GA_PolyCounts.h:42
GA_PolyCounts & operator=(const GA_PolyCounts &that)
#define GA_API
Definition: GA_API.h:12
SizeCount(int sz, int ct)
Definition: GA_PolyCounts.h:34
GA_Size getNumVertices() const
png_uint_32 i
Definition: png.h:2877
exint GA_Size
Defines the bit width for index and offset types in GA.
Definition: GA_Types.h:211
Range range() const
GLsizeiptr size
Definition: glcorearb.h:663
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:101
GA_Size getSize(GA_Size polygon) const
Simpler than getVertexRange if you just want the polygon size.
iteratorT< CLASS, ARRAYCLASS > & operator++()
GA_Size getNumPolygons() const
long long int64
Definition: SYS_Types.h:106
GA_Size grainsize() const
const_iterator begin() const
iteratorT< CLASS, ARRAYCLASS > operator-(GA_Size count) const
bool operator!=(const iteratorT< CLASS, ARRAYCLASS > &that) const
iteratorT< GA_PolyCounts, UT_Array< SizeCount > > iterator
GLuint GLuint end
Definition: glcorearb.h:474
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
const_iterator end() const
iterator begin()
int64 getMemoryUsage(bool inclusive) const
iteratorT< const GA_PolyCounts, const UT_Array< SizeCount > > const_iterator
bool empty() const
iteratorT< CLASS, ARRAYCLASS > & operator--()
Range(const GA_PolyCounts &list)
const int & count() const
Definition: GA_PolyCounts.h:43
SYS_FORCE_INLINE bool atEnd() const
GLint GLsizei count
Definition: glcorearb.h:404
const_iterator findVertex(GA_Size relativevertex) const
SYS_FORCE_INLINE GA_Size start() const
const_iterator begin() const
iteratorT(const iteratorT< CLASS, ARRAYCLASS > &that)
Definition: GA_PolyCounts.h:86
void append(GA_Size size, GA_Size count=1)
GLuint index
Definition: glcorearb.h:785
GA_PolyCounts(const GA_PolyCounts &that)
iteratorT(ARRAYCLASS *array, GA_Size polygon, GA_Size start, GA_Size index, GA_Size count)
Definition: GA_PolyCounts.h:93
bool operator==(const iteratorT< CLASS, ARRAYCLASS > &that) const
Range(Range &that, UT_Split)
void getVertexRange(GA_Size polygon, GA_Size &start, GA_Size &size) const
GA_Size size() const
SYS_FORCE_INLINE GA_Size nvertices() const
GA_Size product() const
Definition: GA_PolyCounts.h:46
iteratorT< CLASS, ARRAYCLASS > operator+(GA_Size count) const
SYS_FORCE_INLINE GA_Size polygon() const
iteratorT< CLASS, ARRAYCLASS > & operator=(const iteratorT< CLASS, ARRAYCLASS > &that)