All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
face.h
Go to the documentation of this file.
1 //
2 // Copyright 2013 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 
25 #ifndef HBRFACE_H
26 #define HBRFACE_H
27 
28 #include <assert.h>
29 #include <cstdio>
30 #include <functional>
31 #include <iostream>
32 #include <algorithm>
33 #include <vector>
34 
35 #include "../hbr/fvarData.h"
36 #include "../hbr/allocator.h"
37 #ifdef HBRSTITCH
38 #include "libgprims/stitch.h"
39 #include "libgprims/stitchInternal.h"
40 #endif
41 
42 #include "../version.h"
43 
44 namespace OpenSubdiv {
45 namespace OPENSUBDIV_VERSION {
46 
47 template <class T> class HbrVertex;
48 template <class T> class HbrHalfedge;
49 template <class T> class HbrFace;
50 template <class T> class HbrMesh;
51 template <class T> class HbrHierarchicalEdit;
52 
53 template <class T> std::ostream& operator<<(std::ostream& out, const HbrFace<T>& face);
54 
55 // A descriptor for a path to a face
56 struct HbrFacePath {
57  void Print() const {
58  printf("%d", topface);
59  for (std::vector<int>::const_reverse_iterator i = remainder.rbegin(); i != remainder.rend(); ++i) {
60  printf(" %d", *i);
61  }
62  printf("\n");
63  }
64 
65  int topface;
66  // Note that the elements in remainder are stored in reverse order.
67  std::vector<int> remainder;
68  friend bool operator< (const HbrFacePath& x, const HbrFacePath& y);
69 };
70 
71 inline bool operator< (const HbrFacePath& x, const HbrFacePath& y) {
72  if (x.topface != y.topface) {
73  return x.topface < y.topface;
74  } else if (x.remainder.size() != y.remainder.size()) {
75  return x.remainder.size() < y.remainder.size();
76  } else {
77  std::vector<int>::const_reverse_iterator i = x.remainder.rbegin();
78  std::vector<int>::const_reverse_iterator j = y.remainder.rbegin();
79  for ( ; i != x.remainder.rend(); ++i, ++j) {
80  if (*i != *j) return (*i < *j);
81  }
82  return true;
83  }
84 }
85 
86 // A simple wrapper around an array of four children. Used to block
87 // allocate pointers to children of HbrFace in the common case
88 template <class T>
90 public:
91  HbrFace<T> *& operator[](const int index) {
92  return children[index];
93  }
94 
95  const HbrFace<T> *& operator[](const int index) const {
96  return children[index];
97  }
98 
99 
100 private:
101  friend class HbrAllocator<HbrFaceChildren<T> >;
102 
103  // Used by block allocator
104  HbrFaceChildren<T>*& GetNext() { return (HbrFaceChildren<T>*&) children; }
105 
106  HbrFaceChildren() {}
107 
108  ~HbrFaceChildren() {}
109 
110  HbrFace<T> *children[4];
111 };
112 
113 template <class T> class HbrFace {
114 
115 private:
116  friend class HbrAllocator<HbrFace<T> >;
117  friend class HbrHalfedge<T>;
118  HbrFace();
119  ~HbrFace();
120 
121 public:
122 
123  void Initialize(HbrMesh<T>* mesh, HbrFace<T>* parent, int childindex, int id, int uindex, int nvertices, HbrVertex<T>** vertices, int fvarwidth = 0, int depth = 0);
124  void Destroy();
125 
126  // Returns the mesh to which this face belongs
127  HbrMesh<T>* GetMesh() const { return mesh; }
128 
129  // Return number of vertices
130  int GetNumVertices() const { return nvertices; }
131 
132  // Return face ID
133  int GetID() const { return id; }
134 
135  // Return the first halfedge of the face
137  if (nvertices > 4) {
138  return (HbrHalfedge<T>*)(extraedges);
139  } else {
140  return const_cast<HbrHalfedge<T>*>(&edges[0]);
141  }
142  }
143 
144  // Return the halfedge which originates at the vertex with the
145  // indicated origin index
146  HbrHalfedge<T>* GetEdge(int index) const;
147 
148  // Return the vertex with the indicated index
149  HbrVertex<T>* GetVertex(int index) const;
150 
151  // Return the ID of the vertex with the indicated index
152  int GetVertexID(int index) const;
153 
154  // Return the parent of this face
156  if (parent == -1) return NULL;
157  return mesh->GetFace(parent);
158  }
159 
160  // Set the child
161  void SetChild(int index, HbrFace<T>* face);
162 
163  // Return the child with the indicated index
164  HbrFace<T>* GetChild(int index) const {
165  int nchildren = mesh->GetSubdivision()->GetFaceChildrenCount(nvertices);
166  if (!children.children || index < 0 || index >= nchildren) return 0;
167  if (nchildren > 4) {
168  return children.extrachildren[index];
169  } else {
170  return (*children.children)[index];
171  }
172  }
173 
174  // Subdivide the face into a vertex if needed and return
176 
177  bool HasChildVertex() const { return vchild!=-1; }
178 
179  // Remove the reference to subdivided vertex
180  void RemoveChild() { vchild = -1; }
181 
182  // "Hole" flags used by subdivision to drop faces
183  bool IsHole() const { return hole; }
184  void SetHole(bool h=1) { hole = h; }
185 
186  // Coarse faces are the top level faces of a mesh. This will be
187  // set by mesh->Finish()
188  bool IsCoarse() const { return coarse; }
189  void SetCoarse() { coarse = 1; }
190 
191  // Protected faces cannot be garbage collected; this may be set on
192  // coarse level faces if the mesh is shared
193  bool IsProtected() const { return protect; }
194  void SetProtected() { protect = 1; }
195  void ClearProtected() { protect = 0; }
196 
197  // Simple bookkeeping needed for garbage collection by HbrMesh
198  bool IsCollected() const { return collected; }
199  void SetCollected() { collected = 1; }
200  void ClearCollected() { collected = 0; }
201 
202  // Refine the face
203  void Refine();
204 
205  // Unrefine the face
206  void Unrefine();
207 
208  // Returns true if the face has a limit surface
209  bool HasLimit();
210 
211  // Returns memory statistics
212  unsigned long GetMemStats() const;
213 
214  // Return facevarying data from the appropriate vertex index
215  // registered to this face. Note that this may either be "generic"
216  // facevarying item (data.GetFace() == 0) or one specifically
217  // registered to the face (data.GetFace() == this) - this is
218  // important when trying to figure out whether the vertex has
219  // created some storage for the item designed to store
220  // discontinuous values for this face.
222  return GetVertex(index)->GetFVarData(this);
223  }
224 
225  // Mark this face as being used, which in turn increments the
226  // usage counter of all vertices in the support for the face. A
227  // used face can not be garbage collected
228  void MarkUsage();
229 
230  // Clears the usage of this face, which in turn decrements the
231  // usage counter of all vertices in the support for the face and
232  // marks the face as a candidate for garbage collection
233  void ClearUsage();
234 
235  // A face can be cleaned if all of its vertices are not being
236  // used; has no children; and (for top level faces) deletion of
237  // its edges will not leave singular vertices
238  bool GarbageCollectable() const;
239 
240  // Connect this face to a list of hierarchical edits
242 
243  // Return the list of hierarchical edits associated with this face
245  if (editOffset == -1) {
246  return NULL;
247  }
248  return mesh->GetHierarchicalEditsAtOffset(editOffset);
249  }
250 
251  // Whether the face has certain types of edits (not necessarily
252  // local - could apply to a subface)
253  bool HasVertexEdits() const { return hasVertexEdits; }
254  void MarkVertexEdits() { hasVertexEdits = 1; }
255 
256  // Return the depth of the face
257  int GetDepth() const { return static_cast<int>(depth); }
258 
259  // Return the uniform index of the face. This is different
260  // from the ID because it may be shared with other faces
261  int GetUniformIndex() const { return uindex; }
262 
263  // Set the uniform index of the face
264  void SetUniformIndex(int i) { uindex = i; }
265 
266  // Return the ptex index
267  int GetPtexIndex() const { return ptexindex; }
268 
269  // Set the ptex index of the face
270  void SetPtexIndex(int i) { ptexindex = i; }
271 
272  // Used by block allocator
273  HbrFace<T>*& GetNext() { return (HbrFace<T>*&) mesh; }
274 
276  HbrFacePath path;
277  path.remainder.reserve(GetDepth());
278  const HbrFace<T>* f = this, *p = GetParent();
279  while (p) {
280  int nchildren = mesh->GetSubdivision()->GetFaceChildrenCount(p->nvertices);
281  if (nchildren > 4) {
282  for (int i = 0; i < nchildren; ++i) {
283  if (p->children.extrachildren[i] == f) {
284  path.remainder.push_back(i);
285  break;
286  }
287  }
288  } else {
289  for (int i = 0; i < nchildren; ++i) {
290  if ((*p->children.children)[i] == f) {
291  path.remainder.push_back(i);
292  break;
293  }
294  }
295  }
296  f = p;
297  p = f->GetParent();
298  }
299  path.topface = f->GetID();
300  assert(GetDepth() == 0 || static_cast<int>(path.remainder.size()) == GetDepth());
301  return path;
302  }
303 
304  void PrintPath() const {
305  GetPath().Print();
306  }
307 
308  // Returns the blind pointer to client data
309  void *GetClientData() const {
310  return mesh->GetFaceClientData(id);
311  }
312 
313  // Sets the blind pointer to client data
314  void SetClientData(void *data) {
315  mesh->SetFaceClientData(id, data);
316  }
317 
318  // Gets the list of vertices which are in the support for the face.
319  void GetSupportingVertices(std::vector<int> &support);
320 
321 private:
322 
323  // Mesh to which this face belongs
324  HbrMesh<T>* mesh;
325 
326  // Unique id for this face
327  int id;
328 
329  // Uniform index
330  int uindex;
331 
332  // Ptex index
333  int ptexindex;
334 
335  // Number of vertices (and number of edges)
336  int nvertices;
337 
338  // Halfedge array for this face
339  HbrHalfedge<T> edges[4];
340 
341  // Edge storage if this face is not a triangle or quad
342  char* extraedges;
343 
344  // Pointer to children array. If there are four children or less,
345  // we use the HbrFaceChildren pointer, otherwise we use
346  // extrachildren
347  union {
350  } children;
351 
352  // Bits used by halfedges to track facevarying sharpnesses
353  unsigned int *fvarbits;
354 
355 #ifdef HBRSTITCH
356  // Pointers to stitch edges used by the half edges.
357  StitchEdge **stitchEdges;
358 #endif
359 
360  // Index of parent face
361  int parent;
362 
363  // Index of subdivided vertex child
364  int vchild;
365 
366  // Offset to the mesh' list of hierarchical edits applicable to this face
367  int editOffset;
368 
369  // Depth of the face in the mesh hierarchy - coarse faces are
370  // level 0. (Hmmm.. is it safe to assume that we'll never
371  // subdivide to greater than 255?)
372  unsigned char depth;
373 
374  unsigned short hole:1;
375  unsigned short coarse:1;
376  unsigned short protect:1;
377  unsigned short collected:1;
378  unsigned short hasVertexEdits:1;
379  unsigned short initialized:1;
380  unsigned short destroyed:1;
381 
382 #ifdef HBR_ADAPTIVE
383 public:
384  enum PatchType { kUnknown=0,
385  kFull=1,
386  kEnd=2,
387  kGregory=3 };
388 
389  enum TransitionType { kTransition0=0,
390  kTransition1=1,
391  kTransition2=2,
392  kTransition3=3,
393  kTransition4=4,
394  kNone=5 };
395 
396  struct AdaptiveFlags {
397  unsigned patchType:2;
398  unsigned transitionType:3;
399  unsigned rots:2;
400  unsigned brots:2;
401  unsigned bverts:2;
402  unsigned isCritical:1;
403  unsigned isExtraordinary:1;
404  unsigned isTagged:1;
405 
406  AdaptiveFlags() : patchType(0), transitionType(5), rots(0), brots(0), bverts(0), isCritical(0), isExtraordinary(0), isTagged(0) { }
407  };
408 
409  AdaptiveFlags _adaptiveFlags;
410 
411  bool isTransitionPatch() const {
412  return (_adaptiveFlags.transitionType!=kNone);
413  }
414 
415  bool hasTaggedVertices() {
416  int nv = GetNumVertices();
417  for (int i=0; i<nv; ++i) {
418  if (GetVertex(i)->_adaptiveFlags.wasTagged)
419  return true;
420  }
421  return false;
422  }
423 #endif
424 };
425 
426 } // end namespace OPENSUBDIV_VERSION
427 using namespace OPENSUBDIV_VERSION;
428 
429 } // end namespace OpenSubdiv
430 
431 #include "../hbr/mesh.h"
432 
433 namespace OpenSubdiv {
434 namespace OPENSUBDIV_VERSION {
435 
436 template <class T>
437 HbrFace<T>::HbrFace()
438  : mesh(0), id(-1), uindex(-1), ptexindex(-1), nvertices(0), extraedges(0), fvarbits(0), parent(-1), vchild(-1),
439 #ifdef HBRSTITCH
440  stitchEdges(0),
441 #endif
442  editOffset(-1), depth(0), hole(0), coarse(0), protect(0), collected(0), hasVertexEdits(0), initialized(0), destroyed(0) {
443  children.children = 0;
444 }
445 
446 template <class T>
447 void
448 HbrFace<T>::Initialize(HbrMesh<T>* m, HbrFace<T>* _parent, int childindex, int fid, int _uindex, int nv, HbrVertex<T>** vertices, int /* fvarwidth */, int _depth) {
449  mesh = m;
450  id = fid;
451  uindex = _uindex;
452  ptexindex = -1;
453  nvertices = nv;
454  extraedges = 0;
455  children.children = 0;
456  vchild = -1;
457  fvarbits = 0;
458 #ifdef HBRSTITCH
459  stitchEdges = 0;
460 #endif
461  editOffset = -1;
462  depth = static_cast<unsigned char>(_depth);
463  hole = 0;
464  coarse = 0;
465  protect = 0;
466  collected = 0;
467  hasVertexEdits = 0;
468  initialized = 1;
469  destroyed = 0;
470 
471  int i;
472  const int fvarcount = mesh->GetFVarCount();
473  int fvarbitsSizePerEdge = ((fvarcount + 15) / 16);
474 
475  if (nv > 4) {
476 
477  // If we have more than four vertices, we ignore the
478  // overallocation and allocate our own buffers for stitch
479  // edges and facevarying data.
480 #ifdef HBRSTITCH
481  if (mesh->GetStitchCount()) {
482  const size_t buffersize = nv * (mesh->GetStitchCount() * sizeof(StitchEdge*));
483  char *buffer = (char *) malloc(buffersize);
484  memset(buffer, 0, buffersize);
485  stitchEdges = (StitchEdge**) buffer;
486  }
487 #endif
488  if (fvarcount) {
489  // We allocate fvarbits in one chunk.
490  // fvarbits needs capacity for two bits per fvardatum per edge,
491  // minimum size one integer per edge
492  const size_t fvarbitsSize = nv * (fvarbitsSizePerEdge * sizeof(unsigned int));
493  char *buffer = (char*) malloc(fvarbitsSize);
494  fvarbits = (unsigned int*) buffer;
495  }
496 
497  // We also ignore the edge array and allocate extra storage -
498  // this simplifies GetNext and GetPrev math in HbrHalfedge
499  const size_t edgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
500  extraedges = (char *) malloc(nv * edgesize);
501  for (i = 0; i < nv; ++i) {
502  HbrHalfedge<T>* edge = (HbrHalfedge<T>*)(extraedges + i * edgesize);
503  new (edge) HbrHalfedge<T>();
504  }
505 
506  } else {
507  // Under four vertices: upstream allocation for the class has
508  // been over allocated to include storage for stitchEdges
509  // and fvarbits. Just point our pointers at it.
510  char *buffer = ((char *) this + sizeof(*this));
511 #ifdef HBRSTITCH
512  if (mesh->GetStitchCount()) {
513  const size_t buffersize = 4 * (mesh->GetStitchCount() * sizeof(StitchEdge*));
514  memset(buffer, 0, buffersize);
515  stitchEdges = (StitchEdge**) buffer;
516  buffer += buffersize;
517  }
518 #endif
519  if (fvarcount) {
520  fvarbits = (unsigned int*) buffer;
521  }
522  }
523 
524  // Must do this before we create edges
525  if (_parent) {
526  _parent->SetChild(childindex, this);
527  }
528 
529  // Edges must be constructed in this two part approach: we must
530  // ensure that opposite/next/previous ptrs are all set up
531  // correctly, before we can begin adding incident edges to
532  // vertices.
533  int next;
534  unsigned int *curfvarbits = fvarbits;
535  HbrHalfedge<T>* edge;
536  size_t edgesize;
537  if (nv > 4) {
538  edge = (HbrHalfedge<T>*)(extraedges);
539  edgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
540  } else {
541  edge = edges;
542  edgesize = sizeof(HbrHalfedge<T>);
543  }
544  for (i = 0, next = 1; i < nv; ++i, ++next) {
545  if (next == nv) next = 0;
546  HbrHalfedge<T>* opposite = vertices[next]->GetEdge(vertices[i]->GetID());
547  edge->Initialize(opposite, i, vertices[i], curfvarbits, this);
548  if (opposite) opposite->SetOpposite(edge);
549  if (fvarbits) {
550  curfvarbits = curfvarbits + fvarbitsSizePerEdge;
551  }
552  edge = (HbrHalfedge<T>*)((char *) edge + edgesize);
553  }
554  if (nv > 4) {
555  edge = (HbrHalfedge<T>*)(extraedges);
556  } else {
557  edge = edges;
558  }
559  for (i = 0; i < nv; ++i) {
560  vertices[i]->AddIncidentEdge(edge);
561  edge = (HbrHalfedge<T>*)((char *) edge + edgesize);
562  }
563 }
564 
565 template <class T>
567  Destroy();
568 }
569 
570 template <class T>
571 void
573  if (initialized && !destroyed) {
574  int i;
575 #ifdef HBRSTITCH
576  const int stitchCount = mesh->GetStitchCount();
577 #endif
578 
579  // Remove children's references to self
580  if (children.children) {
581  int nchildren = mesh->GetSubdivision()->GetFaceChildrenCount(nvertices);
582  if (nchildren > 4) {
583  for (i = 0; i < nchildren; ++i) {
584  if (children.extrachildren[i]) {
585  children.extrachildren[i]->parent = -1;
586  children.extrachildren[i] = 0;
587  }
588  }
589  delete[] children.extrachildren;
590  children.extrachildren = 0;
591  } else {
592  for (i = 0; i < nchildren; ++i) {
593  if ((*children.children)[i]) {
594  (*children.children)[i]->parent = -1;
595  (*children.children)[i] = 0;
596  }
597  }
598  mesh->DeleteFaceChildren(children.children);
599  children.children = 0;
600  }
601  }
602 
603  // Deleting the incident edges from the vertices in this way is
604  // the safest way of doing things. Doing it in the halfedge
605  // destructor will not work well because it disrupts cycle
606  // finding/incident edge replacement in the vertex code.
607  // We also take this time to clean up any orphaned stitches
608  // still belonging to the edges.
609  HbrHalfedge<T>* edge;
610  size_t edgesize;
611  if (nvertices > 4) {
612  edge = (HbrHalfedge<T>*)(extraedges);
613  edgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
614  } else {
615  edge = edges;
616  edgesize = sizeof(HbrHalfedge<T>);
617  }
618  for (i = 0; i < nvertices; ++i) {
619 #ifdef HBRSTITCH
620  edge->DestroyStitchEdges(stitchCount);
621 #endif
622  HbrVertex<T>* vertex = mesh->GetVertex(edge->GetOrgVertexID());
623  if (fvarbits) {
624  HbrFVarData<T>& fvt = vertex->GetFVarData(this);
625  if (fvt.GetFaceID() == GetID()) {
626  fvt.SetFaceID(-1);
627  }
628  }
629  vertex->RemoveIncidentEdge(edge);
630  vertex->UnGuaranteeNeighbors();
631  edge = (HbrHalfedge<T>*)((char *) edge + edgesize);
632  }
633  if (extraedges) {
634  edge = (HbrHalfedge<T>*)(extraedges);
635  for (i = 0; i < nvertices; ++i) {
636  edge->~HbrHalfedge<T>();
637  edge = (HbrHalfedge<T>*)((char *) edge + edgesize);
638  }
639  free(extraedges);
640  extraedges = 0;
641  }
642 
643  // Remove parent's reference to self
644  HbrFace<T> *parentFace = GetParent();
645  if (parentFace) {
646  bool parentHasOtherKids = false;
647  int nchildren = mesh->GetSubdivision()->GetFaceChildrenCount(parentFace->nvertices);
648  if (nchildren > 4) {
649  for (i = 0; i < nchildren; ++i) {
650  if (parentFace->children.extrachildren[i] == this) {
651  parentFace->children.extrachildren[i] = 0;
652  } else if (parentFace->children.extrachildren[i]) parentHasOtherKids = true;
653  }
654  // After cleaning the parent's reference to self, the parent
655  // may be able to clean itself up
656  if (!parentHasOtherKids) {
657  delete[] parentFace->children.extrachildren;
658  parentFace->children.extrachildren = 0;
659  if (parentFace->GarbageCollectable()) {
660  mesh->DeleteFace(parentFace);
661  }
662  }
663  } else {
664  for (i = 0; i < nchildren; ++i) {
665  if ((*parentFace->children.children)[i] == this) {
666  (*parentFace->children.children)[i] = 0;
667  } else if ((*parentFace->children.children)[i]) parentHasOtherKids = true;
668  }
669  // After cleaning the parent's reference to self, the parent
670  // may be able to clean itself up
671  if (!parentHasOtherKids) {
672  mesh->DeleteFaceChildren(parentFace->children.children);
673  parentFace->children.children = 0;
674  if (parentFace->GarbageCollectable()) {
675  mesh->DeleteFace(parentFace);
676  }
677  }
678  }
679  parent = -1;
680  }
681 
682  // Orphan the child vertex
683  if (vchild != -1) {
684  HbrVertex<T> *vchildVert = mesh->GetVertex(vchild);
685  vchildVert->SetParent(static_cast<HbrFace*>(0));
686  vchild = -1;
687  }
688 
689  if (nvertices > 4 && fvarbits) {
690  free(fvarbits);
691 #ifdef HBRSTITCH
692  if (stitchEdges) {
693  free(stitchEdges);
694  }
695 #endif
696  }
697  fvarbits = 0;
698 #ifdef HBRSTITCH
699  stitchEdges = 0;
700 #endif
701 
702  // Make sure the four edges intrinsic to face are properly cleared
703  // if they were used
704  if (nvertices <= 4) {
705  for (i = 0; i < nvertices; ++i) {
706  edges[i].Clear();
707  }
708  }
709  nvertices = 0;
710  initialized = 0;
711  mesh = 0;
712  destroyed = 1;
713  }
714 }
715 
716 template <class T>
718 HbrFace<T>::GetEdge(int index) const {
719  assert(index >= 0 && index < nvertices);
720  if (nvertices > 4) {
721  const size_t edgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
722  return (HbrHalfedge<T>*)(extraedges + index * edgesize);
723  } else {
724  return const_cast<HbrHalfedge<T>*>(edges + index);
725  }
726 }
727 
728 template <class T>
730 HbrFace<T>::GetVertex(int index) const {
731  assert(index >= 0 && index < nvertices);
732  if (nvertices > 4) {
733  const size_t edgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
734  HbrHalfedge<T>* edge = (HbrHalfedge<T>*)(extraedges +
735  index * edgesize);
736  return mesh->GetVertex(edge->GetOrgVertexID());
737  } else {
738  return mesh->GetVertex(edges[index].GetOrgVertexID());
739  }
740 }
741 
742 template <class T>
743 int
744 HbrFace<T>::GetVertexID(int index) const {
745  assert(index >= 0 && index < nvertices);
746  if (nvertices > 4) {
747  const size_t edgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
748  HbrHalfedge<T>* edge = (HbrHalfedge<T>*)(extraedges +
749  index * edgesize);
750  return edge->GetOrgVertexID();
751  } else {
752  return edges[index].GetOrgVertexID();
753  }
754 }
755 
756 template <class T>
757 void
758 HbrFace<T>::SetChild(int index, HbrFace<T>* face) {
759  assert(id != -1);
760  int nchildren = mesh->GetSubdivision()->GetFaceChildrenCount(nvertices);
761  // Construct the children array if it doesn't already exist
762  if (!children.children) {
763  int i;
764  if (nchildren > 4) {
765  children.extrachildren = new HbrFace<T>*[nchildren];
766  for (i = 0; i < nchildren; ++i) {
767  children.extrachildren[i] = 0;
768  }
769  } else {
770  children.children = mesh->NewFaceChildren();
771  for (i = 0; i < nchildren; ++i) {
772  (*children.children)[i] = 0;
773  }
774  }
775  }
776  if (nchildren > 4) {
777  children.extrachildren[index] = face;
778  } else {
779  (*children.children)[index] = face;
780  }
781  face->parent = this->id;
782 }
783 
784 template <class T>
787  if (vchild != -1) return mesh->GetVertex(vchild);
788  HbrVertex<T>* vchildVert = mesh->GetSubdivision()->Subdivide(mesh, this);
789  vchild = vchildVert->GetID();
790  vchildVert->SetParent(this);
791  return vchildVert;
792 }
793 
794 template <class T>
795 void
797  mesh->GetSubdivision()->Refine(mesh, this);
798 }
799 
800 template <class T>
801 void
803  // Delete the children, via the mesh (so that the mesh loses
804  // references to the children)
805  if (children.children) {
806  int nchildren = mesh->GetSubdivision()->GetFaceChildrenCount(nvertices);
807  if (nchildren > 4) {
808  for (int i = 0; i < nchildren; ++i) {
809  if (children.extrachildren[i]) mesh->DeleteFace(children.extrachildren[i]);
810  }
811  delete[] children.extrachildren;
812  children.extrachildren = 0;
813  } else {
814  for (int i = 0; i < nchildren; ++i) {
815  if ((*children.children)[i]) mesh->DeleteFace((*children.children)[i]);
816  }
817  mesh->DeleteFaceChildren(children.children);
818  children.children = 0;
819  }
820  }
821 }
822 
823 template <class T>
824 bool
826  return mesh->GetSubdivision()->HasLimit(mesh, this);
827 }
828 
829 template <class T>
830 unsigned long
832  return sizeof(HbrFace<T>);
833 }
834 
835 template <class T>
836 void
838  // Must increment the usage on all vertices which are in the
839  // support for this face. Note well: this will increment vertices
840  // more than once. This doesn't really matter as long as
841  // ClearUsage also does the same number of decrements. If we
842  // really were concerned about ensuring single increments, we can
843  // use GetSupportingVertices, but that's slower.
844  HbrVertex<T>* v;
845  HbrHalfedge<T>* e, *ee, *eee, *start;
846  size_t edgesize, eedgesize;
847  if (nvertices > 4) {
848  e = (HbrHalfedge<T>*)(extraedges);
849  edgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
850  } else {
851  e = edges;
852  edgesize = sizeof(HbrHalfedge<T>);
853  }
854  for (int i = 0; i < nvertices; ++i) {
855  v = mesh->GetVertex(e->GetOrgVertexID());
856  v->GuaranteeNeighbors();
857  start = v->GetIncidentEdge();
858  ee = start;
859  do {
860  HbrFace<T>* f = ee->GetLeftFace();
861  int nv = f->GetNumVertices();
862  if (nv > 4) {
863  eee = (HbrHalfedge<T>*)(f->extraedges);
864  eedgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
865  } else {
866  eee = f->edges;
867  eedgesize = sizeof(HbrHalfedge<T>);
868  }
869  for (int j = 0; j < nv; ++j) {
870  mesh->GetVertex(eee->GetOrgVertexID())->IncrementUsage();
871  eee = (HbrHalfedge<T>*)((char *) eee + eedgesize);
872  }
873  ee = v->GetNextEdge(ee);
874  if (ee == start) break;
875  } while (ee);
876  e = (HbrHalfedge<T>*)((char *) e + edgesize);
877  }
878 }
879 
880 template <class T>
881 void
883  bool gc = false;
884  // Must mark all vertices which may affect this face
885  HbrVertex<T>* v, *vv;
886  HbrHalfedge<T>* e, *ee, *eee, *start;
887  size_t edgesize, eedgesize;
888  if (nvertices > 4) {
889  e = (HbrHalfedge<T>*)(extraedges);
890  edgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
891  } else {
892  e = edges;
893  edgesize = sizeof(HbrHalfedge<T>);
894  }
895  for (int i = 0; i < nvertices; ++i) {
896  v = mesh->GetVertex(e->GetOrgVertexID());
897  start = v->GetIncidentEdge();
898  ee = start;
899  do {
900  HbrFace<T>* f = ee->GetLeftFace();
901  int nv = f->GetNumVertices();
902  if (nv > 4) {
903  eee = (HbrHalfedge<T>*)(f->extraedges);
904  eedgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
905  } else {
906  eee = f->edges;
907  eedgesize = sizeof(HbrHalfedge<T>);
908  }
909  for (int j = 0; j < nv; ++j) {
910  HbrVertex<T>* vert = mesh->GetVertex(eee->GetOrgVertexID());
911  vert->DecrementUsage();
912  if (!vert->IsUsed()) {
913  mesh->AddGarbageCollectableVertex(vert);
914  gc = true;
915  }
916  eee = (HbrHalfedge<T>*)((char *) eee + eedgesize);
917  }
918  ee = v->GetNextEdge(ee);
919  if (ee == start) break;
920  } while (ee);
921  e = (HbrHalfedge<T>*)((char *) e + edgesize);
922  }
923  if (gc) mesh->GarbageCollect();
924 }
925 
926 template <class T>
927 bool
929  if (children.children || protect) return false;
930  for (int i = 0; i < nvertices; ++i) {
931  HbrHalfedge<T>* edge = GetEdge(i);
932  HbrVertex<T>* vertex = edge->GetOrgVertex(mesh);
933  if (vertex->IsUsed()) return false;
934  if (!GetParent() && vertex->EdgeRemovalWillMakeSingular(edge)) {
935  return false;
936  }
937  }
938  return true;
939 }
940 
941 template <class T>
942 void
944  HbrHierarchicalEdit<T>** faceedits = edits;
945  HbrHierarchicalEdit<T>** baseedit = mesh->GetHierarchicalEditsAtOffset(0);
946  editOffset = int(faceedits - baseedit);
947 
948  // Walk the list of edits and look for any which apply locally.
949  while (HbrHierarchicalEdit<T>* edit = *faceedits) {
950  if (!edit->IsRelevantToFace(this)) break;
951  edit->ApplyEditToFace(this);
952  faceedits++;
953  }
954 }
955 
956 template <class T>
957 void
958 HbrFace<T>::GetSupportingVertices(std::vector<int> &support) {
959  support.reserve(16);
960  HbrVertex<T>* v;
961  HbrHalfedge<T>* e, *ee, *eee, *start;
962  size_t edgesize, eedgesize;
963  if (nvertices > 4) {
964  e = (HbrHalfedge<T>*)(extraedges);
965  edgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
966  } else {
967  e = edges;
968  edgesize = sizeof(HbrHalfedge<T>);
969  }
970  for (int i = 0; i < nvertices; ++i) {
971  v = mesh->GetVertex(e->GetOrgVertexID());
972  v->GuaranteeNeighbors();
973  start = v->GetIncidentEdge();
974  ee = start;
975  do {
976  HbrFace<T>* f = ee->GetLeftFace();
977  int nv = f->GetNumVertices();
978  if (nv > 4) {
979  eee = (HbrHalfedge<T>*)(f->extraedges);
980  eedgesize = sizeof(HbrHalfedge<T>) + sizeof(HbrFace<T>*);
981  } else {
982  eee = f->edges;
983  eedgesize = sizeof(HbrHalfedge<T>);
984  }
985  for (int j = 0; j < nv; ++j) {
986  int id = eee->GetOrgVertexID();
987  std::vector<int>::iterator vi =
988  std::lower_bound(support.begin(), support.end(), id);
989  if (vi == support.end() || *vi != id) {
990  support.insert(vi, id);
991  }
992  eee = (HbrHalfedge<T>*)((char *) eee + eedgesize);
993  }
994  ee = v->GetNextEdge(ee);
995  if (ee == start) break;
996  } while (ee);
997  e = (HbrHalfedge<T>*)((char *) e + edgesize);
998  }
999 }
1000 
1001 template <class T>
1002 std::ostream& operator<<(std::ostream& out, const HbrFace<T>& face) {
1003  out << "face " << face.GetID() << ", " << face.GetNumVertices() << " vertices (";
1004  for (int i = 0; i < face.GetNumVertices(); ++i) {
1005  HbrHalfedge<T>* e = face.GetEdge(i);
1006  out << *(e->GetOrgVertex());
1007  if (e->IsBoundary()) {
1008  out << " -/-> ";
1009  } else {
1010  out << " ---> ";
1011  }
1012  }
1013  out << ")";
1014  return out;
1015 }
1016 
1017 template <class T>
1019 public:
1020  virtual void operator() (HbrFace<T> &face) = 0;
1021  virtual ~HbrFaceOperator() {}
1022 };
1023 
1024 } // end namespace OPENSUBDIV_VERSION
1025 using namespace OPENSUBDIV_VERSION;
1026 
1027 } // end namespace OpenSubdiv
1028 
1029 #endif /* HBRFACE_H */
1030 
void RemoveIncidentEdge(HbrHalfedge< T > *edge)
Definition: vertex.h:685
void SetChild(int index, HbrFace< T > *face)
Definition: face.h:758
HbrHalfedge< T > * GetEdge(int index) const
Definition: face.h:718
HbrFacePath GetPath() const
Definition: face.h:275
HbrFaceChildren< T > * children
Definition: face.h:348
bool EdgeRemovalWillMakeSingular(HbrHalfedge< T > *edge) const
Definition: vertex.h:800
HbrHalfedge< T > * GetFirstEdge() const
Definition: face.h:136
HbrHalfedge< T > * GetEdge(const HbrVertex< T > *dest) const
Definition: vertex.h:954
HbrFace< T > * GetChild(int index) const
Definition: face.h:164
int GetVertexID(int index) const
Definition: face.h:744
HbrVertex< T > * GetVertex() const
Definition: halfedge.h:110
HbrFace< T > * GetLeftFace() const
Definition: halfedge.h:169
const HbrFace< T > *& operator[](const int index) const
Definition: face.h:95
HbrHierarchicalEdit< T > ** GetHierarchicalEdits() const
Definition: face.h:244
HbrVertex< T > * Subdivide()
Definition: face.h:786
HbrFace< T > * GetParent() const
Definition: face.h:155
HbrFace< T > *& operator[](const int index)
Definition: face.h:91
friend bool operator<(const HbrFacePath &x, const HbrFacePath &y)
Definition: face.h:71
HbrFVarData< T > & GetFVarData(int index)
Definition: face.h:221
HbrMesh< T > * GetMesh() const
Definition: face.h:127
bool operator<(const HbrFacePath &x, const HbrFacePath &y)
Definition: face.h:71
HbrHalfedge< T > * GetIncidentEdge() const
Definition: vertex.h:285
void Initialize(HbrMesh< T > *mesh, HbrFace< T > *parent, int childindex, int id, int uindex, int nvertices, HbrVertex< T > **vertices, int fvarwidth=0, int depth=0)
Definition: face.h:448
HbrHalfedge< T > * GetNextEdge(const HbrHalfedge< T > *edge) const
Definition: vertex.h:990
HbrVertex< T > * GetVertex(int index) const
Definition: face.h:730
HbrVertex< T > * GetOrgVertex() const
Definition: halfedge.h:125
void SetParent(HbrHalfedge< T > *edge)
Definition: vertex.h:225
virtual void operator()(HbrFace< T > &face)=0
unsigned long GetMemStats() const
Definition: face.h:831
void SetHierarchicalEdits(HbrHierarchicalEdit< T > **edits)
Definition: face.h:943
void SetOpposite(HbrHalfedge< T > *opposite)
Definition: halfedge.h:77
void GetSupportingVertices(std::vector< int > &support)
Definition: face.h:958
HbrFVarData< T > & GetFVarData(const HbrFace< T > *face)
Definition: vertex.h:887
void AddIncidentEdge(HbrHalfedge< T > *edge)
Definition: vertex.h:513