All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
loop.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 HBRLOOP_H
26 #define HBRLOOP_H
27 
28 #include <cmath>
29 #include <assert.h>
30 #include <algorithm>
31 
32 #include "../hbr/subdivision.h"
33 
34 #include "../version.h"
35 
36 namespace OpenSubdiv {
37 namespace OPENSUBDIV_VERSION {
38 
39 /* #define HBR_DEBUG */
40 
41 template <class T>
43 public:
45  : HbrSubdivision<T>() {}
46 
47  virtual HbrSubdivision<T>* Clone() const {
48  return new HbrLoopSubdivision<T>();
49  }
50 
51  virtual void Refine(HbrMesh<T>* mesh, HbrFace<T>* face);
52  virtual HbrFace<T>* RefineFaceAtVertex(HbrMesh<T>* mesh, HbrFace<T>* face, HbrVertex<T>* vertex);
53  virtual void GuaranteeNeighbor(HbrMesh<T>* mesh, HbrHalfedge<T>* edge);
54  virtual void GuaranteeNeighbors(HbrMesh<T>* mesh, HbrVertex<T>* vertex);
55 
56  virtual bool HasLimit(HbrMesh<T>* mesh, HbrFace<T>* face);
57  virtual bool HasLimit(HbrMesh<T>* mesh, HbrHalfedge<T>* edge);
58  virtual bool HasLimit(HbrMesh<T>* mesh, HbrVertex<T>* vertex);
59 
60  virtual HbrVertex<T>* Subdivide(HbrMesh<T>* mesh, HbrFace<T>* face);
61  virtual HbrVertex<T>* Subdivide(HbrMesh<T>* mesh, HbrHalfedge<T>* edge);
62  virtual HbrVertex<T>* Subdivide(HbrMesh<T>* mesh, HbrVertex<T>* vertex);
63 
64  virtual bool VertexIsExtraordinary(HbrMesh<T> const * /* mesh */, HbrVertex<T>* vertex) { return vertex->GetValence() != 6; }
65  virtual bool FaceIsExtraordinary(HbrMesh<T> const * /* mesh */, HbrFace<T>* face) { return face->GetNumVertices() != 3; }
66 
67  virtual int GetFaceChildrenCount(int /* nvertices */) const { return 4; }
68 
69 private:
70 
71  // Transfers facevarying data from a parent face to a child face
72  void transferFVarToChild(HbrMesh<T>* mesh, HbrFace<T>* face, HbrFace<T>* child, int index);
73 
74  // Transfers vertex and edge edits from a parent face to a child face
75  void transferEditsToChild(HbrFace<T>* face, HbrFace<T>* child, int index);
76 
77  // Generates the fourth child of a triangle: the triangle in the
78  // middle whose vertices have parents which are all edges
79  void refineFaceAtMiddle(HbrMesh<T>* mesh, HbrFace<T>* face);
80 
81 };
82 
83 template <class T>
84 void
87  HbrVertex<T>* childVertex;
88 
89  // In the case of index == 3, this is the middle face, and so
90  // we need to do three edge subdivision rules
91  if (index == 3) {
92  const int fvarcount = mesh->GetFVarCount();
93  for (int i = 0; i < 3; ++i) {
94  HbrHalfedge<T> *edge = face->GetEdge(i);
95  GuaranteeNeighbor(mesh, edge);
96  childVertex = child->GetVertex((i + 2) % 3);
97  bool fvIsSmooth = !edge->IsFVarInfiniteSharpAnywhere();
98  if (!fvIsSmooth) {
99  childVertex->NewFVarData(child);
100  }
101  HbrFVarData<T>& fv = childVertex->GetFVarData(child);
102  int fvarindex = 0;
103  for (int fvaritem = 0; fvaritem < fvarcount; ++fvaritem) {
104  const int fvarwidth = mesh->GetFVarWidths()[fvaritem];
105 
106  if (fvarinterp == HbrMesh<T>::k_InterpolateBoundaryNone ||
107  face->GetEdge(i)->GetFVarSharpness(fvaritem) || face->GetEdge(i)->IsBoundary()) {
108 
109  // Sharp edge rule
110  fv.SetWithWeight(face->GetFVarData(i), fvarindex, fvarwidth, 0.5f);
111  fv.AddWithWeight(face->GetFVarData((i + 1) % 3), fvarindex, fvarwidth, 0.5f);
112  } else if (!fvIsSmooth || !fv.IsInitialized()) {
113  // Smooth edge subdivision. Add 0.375 of adjacent vertices
114  fv.SetWithWeight(face->GetFVarData(i), fvarindex, fvarwidth, 0.375f);
115  fv.AddWithWeight(face->GetFVarData((i + 1) % 3), fvarindex, fvarwidth, 0.375f);
116  // Add 0.125 of opposite vertices
117  fv.AddWithWeight(face->GetFVarData((i + 2) % 3), fvarindex, fvarwidth, 0.125f);
118  HbrFace<T>* oppFace = face->GetEdge(i)->GetRightFace();
119  for (int j = 0; j < oppFace->GetNumVertices(); ++j) {
120  if (oppFace->GetVertex(j) == face->GetVertex(i)) {
121  fv.AddWithWeight(oppFace->GetFVarData((j+1)%oppFace->GetNumVertices()), fvarindex, fvarwidth, 0.125f);
122  break;
123  }
124  }
125  }
126  fvarindex += fvarwidth;
127  }
128  fv.SetInitialized();
129  }
130  return;
131  }
132 
133  HbrHalfedge<T>* edge;
134  HbrVertex<T>* v = face->GetVertex(index);
135 
136  // Otherwise we proceed with one vertex and two edge subdivision
137  // applications. First the vertex subdivision rule. Analyze
138  // whether the vertex is on the boundary and whether it's an
139  // infinitely sharp corner. We determine the last by checking the
140  // propagate corners flag on the mesh; if it's off, we check the
141  // two edges of this face incident to that vertex and determining
142  // whether they are facevarying boundary edges - this is analogous
143  // to what goes on for the interpolateboundary tag (which when set
144  // to EDGEANDCORNER marks vertices with a valence of two as being
145  // sharp corners). If propagate corners is on, we check *all*
146  // faces to see if two edges side by side are facevarying boundary
147  // edges. The facevarying boundary check ignores geometric
148  // sharpness, otherwise we may swim at geometric creases which
149  // aren't actually discontinuous.
150  //
151  // We need to make sure that that each of the vertices of the
152  // child face have the appropriate facevarying storage as
153  // needed. If there are discontinuities in any facevarying datum,
154  // the vertex must allocate a new block of facevarying storage
155  // specific to the child face.
156 
157  v->GuaranteeNeighbors();
158 
159 
160  bool fv0IsSmooth, fv1IsSmooth, fv2IsSmooth;
161 
162  childVertex = child->GetVertex(index);
163  fv0IsSmooth = v->IsFVarAllSmooth();
164  if (!fv0IsSmooth) {
165  childVertex->NewFVarData(child);
166  }
167  HbrFVarData<T>& fv0 = childVertex->GetFVarData(child);
168 
169  edge = face->GetEdge(index);
170  GuaranteeNeighbor(mesh, edge);
171  assert(edge->GetOrgVertex() == v);
172  childVertex = child->GetVertex((index + 1) % 3);
173  fv1IsSmooth = !edge->IsFVarInfiniteSharpAnywhere();
174  if (!fv1IsSmooth) {
175  childVertex->NewFVarData(child);
176  }
177  HbrFVarData<T>& fv1 = childVertex->GetFVarData(child);
178 
179  edge = edge->GetPrev();
180  GuaranteeNeighbor(mesh, edge);
181  assert(edge == face->GetEdge((index + 2) % 3));
182  assert(edge->GetDestVertex() == v);
183  childVertex = child->GetVertex((index + 2) % 3);
184  fv2IsSmooth = !edge->IsFVarInfiniteSharpAnywhere();
185  if (!fv2IsSmooth) {
186  childVertex->NewFVarData(child);
187  }
188  HbrFVarData<T>& fv2 = childVertex->GetFVarData(child);
189 
190  const int fvarcount = mesh->GetFVarCount();
191  int fvarindex = 0;
192  for (int fvaritem = 0; fvaritem < fvarcount; ++fvaritem) {
193  bool infcorner = false;
194  const int fvarwidth = mesh->GetFVarWidths()[fvaritem];
195  const char fvarmask = v->GetFVarMask(fvaritem);
196  if (fvarinterp == HbrMesh<T>::k_InterpolateBoundaryEdgeAndCorner) {
197  if (fvarmask >= HbrVertex<T>::k_Corner) {
198  infcorner = true;
199  } else if (mesh->GetFVarPropagateCorners()) {
200  if (v->IsFVarCorner(fvaritem)) {
201  infcorner = true;
202  }
203  } else {
204  if (face->GetEdge(index)->GetFVarSharpness(fvaritem, true) && face->GetEdge(index)->GetPrev()->GetFVarSharpness(fvaritem, true)) {
205  infcorner = true;
206  }
207  }
208  }
209 
210  // Infinitely sharp vertex rule. Applied if the vertex is:
211  // - undergoing no facevarying boundary interpolation;
212  // - at a geometric crease, in either boundary interpolation case; or
213  // - is an infinitely sharp facevarying vertex, in the EDGEANDCORNER case; or
214  // - has a mask equal or greater than one, in the "always
215  // sharp" interpolate boundary case
216  if (fvarinterp == HbrMesh<T>::k_InterpolateBoundaryNone ||
217  (fvarinterp == HbrMesh<T>::k_InterpolateBoundaryAlwaysSharp &&
218  fvarmask >= 1) ||
219  v->GetSharpness() > HbrVertex<T>::k_Smooth ||
220  infcorner) {
221  fv0.SetWithWeight(face->GetFVarData(index), fvarindex, fvarwidth, 1.0f);
222  }
223  // Dart rule: unlike geometric creases, because there's two
224  // discontinuous values for the one incident edge, we use the
225  // boundary rule and not the smooth rule
226  else if (fvarmask == 1) {
227  // Use 0.75 of the current vert
228  fv0.SetWithWeight(face->GetFVarData(index), fvarindex, fvarwidth, 0.75f);
229 
230  // 0.125 of "two adjacent edge vertices", which in actuality
231  // are the facevarying values of the same vertex but on each
232  // side of the single incident facevarying sharp edge
233  HbrHalfedge<T>* start = v->GetIncidentEdge(), *edge, *nextedge;
234  edge = start;
235  while (edge) {
236  if (edge->GetFVarSharpness(fvaritem)) {
237  break;
238  }
239  nextedge = v->GetNextEdge(edge);
240  if (nextedge == start) {
241  assert(0); // we should have found it by now
242  break;
243  } else if (!nextedge) {
244  // should never get into this case - if the vertex is
245  // on a boundary, it can never be a facevarying dart
246  // vertex
247  assert(0);
248  edge = edge->GetPrev();
249  break;
250  } else {
251  edge = nextedge;
252  }
253  }
254  HbrVertex<T>* w = edge->GetDestVertex();
255  HbrFace<T>* bestface = edge->GetLeftFace();
256  int j;
257  for (j = 0; j < bestface->GetNumVertices(); ++j) {
258  if (bestface->GetVertex(j) == w) break;
259  }
260  assert(j != bestface->GetNumVertices());
261  fv0.AddWithWeight(bestface->GetFVarData(j), fvarindex, fvarwidth, 0.125f);
262  bestface = edge->GetRightFace();
263  for (j = 0; j < bestface->GetNumVertices(); ++j) {
264  if (bestface->GetVertex(j) == w) break;
265  }
266  assert(j != bestface->GetNumVertices());
267  fv0.AddWithWeight(bestface->GetFVarData(j), fvarindex, fvarwidth, 0.125f);
268  }
269  // Boundary vertex rule (can use FVarSmooth, which is equivalent
270  // to checking that it's sharper than a dart)
271  else if (fvarmask != 0) {
272 
273  // Use 0.75 of the current vert
274  fv0.SetWithWeight(face->GetFVarData(index), fvarindex, fvarwidth, 0.75f);
275 
276  // Compute 0.125 of two adjacent edge vertices. However the
277  // two adjacent edge vertices we use must be part of the
278  // facevarying "boundary". To find the first edge we cycle
279  // counterclockwise around the current vertex v and look for
280  // the first boundary edge
281 
282  HbrFace<T>* bestface = face;
283  HbrHalfedge<T>* bestedge = face->GetEdge(index)->GetPrev();
284  HbrHalfedge<T>* starte = bestedge->GetOpposite();
285  HbrVertex<T>* w = 0;
286  if (!starte) {
287  w = face->GetEdge(index)->GetPrev()->GetOrgVertex();
288  } else {
289  HbrHalfedge<T>* e = starte, *next;
290  assert(starte->GetOrgVertex() == v);
291  do {
292  if (e->GetFVarSharpness(fvaritem) || !e->GetLeftFace()) {
293  bestface = e->GetRightFace();
294  bestedge = e;
295  break;
296  }
297  next = v->GetNextEdge(e);
298  if (!next) {
299  bestface = e->GetLeftFace();
300  w = e->GetPrev()->GetOrgVertex();
301  break;
302  }
303  e = next;
304  } while (e && e != starte);
305  }
306  if (!w) w = bestedge->GetDestVertex();
307  int j;
308  for (j = 0; j < bestface->GetNumVertices(); ++j) {
309  if (bestface->GetVertex(j) == w) break;
310  }
311  assert(j != bestface->GetNumVertices());
312  fv0.AddWithWeight(bestface->GetFVarData(j), fvarindex, fvarwidth, 0.125f);
313 
314  // Look for the other edge by cycling clockwise around v
315  bestface = face;
316  bestedge = face->GetEdge(index);
317  starte = bestedge;
318  w = 0;
319  if (HbrHalfedge<T>* e = starte) {
320  assert(starte->GetOrgVertex() == v);
321  do {
322  if (e->GetFVarSharpness(fvaritem) || !e->GetRightFace()) {
323  bestface = e->GetLeftFace();
324  bestedge = e;
325  break;
326  }
327  assert(e->GetOpposite());
328  e = v->GetPreviousEdge(e);
329  } while (e && e != starte);
330  }
331  if (!w) w = bestedge->GetDestVertex();
332  for (j = 0; j < bestface->GetNumVertices(); ++j) {
333  if (bestface->GetVertex(j) == w) break;
334  }
335  assert(j != bestface->GetNumVertices());
336  fv0.AddWithWeight(bestface->GetFVarData(j), fvarindex, fvarwidth, 0.125f);
337 
338  }
339  // Smooth rule
340  else if (!fv0IsSmooth || !fv0.IsInitialized()) {
341  int valence = v->GetValence();
342  float invvalence = 1.0f / valence;
343  float beta = 0.25f * cosf((float)M_PI * 2.0f * invvalence) + 0.375f;
344  beta = beta * beta;
345  beta = (0.625f - beta) * invvalence;
346 
347  // Use 1 - beta * valence of the current vertex value
348  fv0.SetWithWeight(face->GetFVarData(index), fvarindex, fvarwidth, 1 - (beta * valence));
349 
350  // Add beta of surrounding vertices averages. We loop over all
351  // surrounding faces..
352  HbrHalfedge<T>* start = v->GetIncidentEdge(), *edge;
353  edge = start;
354  while (edge) {
355  HbrFace<T>* g = edge->GetLeftFace();
356 
357  // .. and look for the edge on that face whose origin is
358  // the same as v, and add a contribution from its
359  // destination vertex value; this takes care of the
360  // surrounding edge vertex addition.
361  for (int j = 0; j < g->GetNumVertices(); ++j) {
362  if (g->GetEdge(j)->GetOrgVertex() == v) {
363  fv0.AddWithWeight(g->GetFVarData((j + 1) % g->GetNumVertices()), fvarindex, fvarwidth, beta);
364  break;
365  }
366  }
367  edge = v->GetNextEdge(edge);
368  if (edge == start) break;
369  }
370  }
371 
372  // Edge subdivision rule
373  HbrHalfedge<T>* edge = face->GetEdge(index);
374 
375  if (fvarinterp == HbrMesh<T>::k_InterpolateBoundaryNone ||
376  edge->GetFVarSharpness(fvaritem) || edge->IsBoundary()) {
377 
378  // Sharp edge rule
379  fv1.SetWithWeight(face->GetFVarData(index), fvarindex, fvarwidth, 0.5f);
380  fv1.AddWithWeight(face->GetFVarData((index + 1) % 3), fvarindex, fvarwidth, 0.5f);
381  } else if (!fv1IsSmooth || !fv1.IsInitialized()) {
382  // Smooth edge subdivision. Add 0.375 of adjacent vertices
383  fv1.SetWithWeight(face->GetFVarData(index), fvarindex, fvarwidth, 0.375f);
384  fv1.AddWithWeight(face->GetFVarData((index + 1) % 3), fvarindex, fvarwidth, 0.375f);
385  // Add 0.125 of opposite vertices
386  fv1.AddWithWeight(face->GetFVarData((index + 2) % 3), fvarindex, fvarwidth, 0.125f);
387  HbrFace<T>* oppFace = edge->GetRightFace();
388  for (int j = 0; j < oppFace->GetNumVertices(); ++j) {
389  if (oppFace->GetVertex(j) == v) {
390  fv1.AddWithWeight(oppFace->GetFVarData((j+1)%oppFace->GetNumVertices()), fvarindex, fvarwidth, 0.125f);
391  break;
392  }
393  }
394  }
395 
396 
397  // Edge subdivision rule
398  edge = edge->GetPrev();
399 
400  if (fvarinterp == HbrMesh<T>::k_InterpolateBoundaryNone ||
401  edge->GetFVarSharpness(fvaritem) || edge->IsBoundary()) {
402 
403  // Sharp edge rule
404  fv2.SetWithWeight(face->GetFVarData((index + 2) % 3), fvarindex, fvarwidth, 0.5f);
405  fv2.AddWithWeight(face->GetFVarData(index), fvarindex, fvarwidth, 0.5f);
406  } else if (!fv2IsSmooth || !fv2.IsInitialized()) {
407  // Smooth edge subdivision. Add 0.375 of adjacent vertices
408  fv2.SetWithWeight(face->GetFVarData((index + 2) % 3), fvarindex, fvarwidth, 0.375f);
409  fv2.AddWithWeight(face->GetFVarData(index), fvarindex, fvarwidth, 0.375f);
410  // Add 0.125 of opposite vertices
411  fv2.AddWithWeight(face->GetFVarData((index + 1) % 3), fvarindex, fvarwidth, 0.125f);
412 
413  HbrFace<T>* oppFace = edge->GetRightFace();
414  for (int j = 0; j < oppFace->GetNumVertices(); ++j) {
415  if (oppFace->GetVertex(j) == v) {
416  fv2.AddWithWeight(oppFace->GetFVarData((j+2)%oppFace->GetNumVertices()), fvarindex, fvarwidth, 0.125f);
417  break;
418  }
419  }
420  }
421 
422  fvarindex += fvarwidth;
423  }
424  fv0.SetInitialized();
425  fv1.SetInitialized();
426  fv2.SetInitialized();
427 }
428 
429 template <class T>
430 void
431 HbrLoopSubdivision<T>::transferEditsToChild(HbrFace<T>* face, HbrFace<T>* child, int index) {
432 
433  // Hand down hole tag
434  child->SetHole(face->IsHole());
435 
436  // Hand down pointers to hierarchical edits
437  if (HbrHierarchicalEdit<T>** edits = face->GetHierarchicalEdits()) {
438  while (HbrHierarchicalEdit<T>* edit = *edits) {
439  if (!edit->IsRelevantToFace(face)) break;
440  if (edit->GetNSubfaces() > face->GetDepth() &&
441  (edit->GetSubface(face->GetDepth()) == index)) {
442  child->SetHierarchicalEdits(edits);
443  break;
444  }
445  edits++;
446  }
447  }
448 }
449 
450 template <class T>
451 void
453 
454 #ifdef HBR_DEBUG
455  std::cerr << "\n\nRefining face " << *face << "\n";
456 #endif
457 
458  assert(face->GetNumVertices() == 3); // or triangulate it?
459 
460  HbrHalfedge<T>* edge = face->GetFirstEdge();
461  HbrHalfedge<T>* prevedge = edge->GetPrev();
462  for (int i = 0; i < 3; ++i) {
463  HbrVertex<T>* vertex = edge->GetOrgVertex();
464  if (!face->GetChild(i)) {
465 #ifdef HBR_DEBUG
466  std::cerr << "Kid " << i << "\n";
467 #endif
468  HbrFace<T>* child;
469  HbrVertex<T>* vertices[3];
470 
471  vertices[i] = vertex->Subdivide();
472  vertices[(i + 1) % 3] = edge->Subdivide();
473  vertices[(i + 2) % 3] = prevedge->Subdivide();
474  child = mesh->NewFace(3, vertices, face, i);
475 #ifdef HBR_DEBUG
476  std::cerr << "Creating face " << *child << " during refine\n";
477 #endif
478 
479  // Hand down edge sharpness
480  float sharpness;
481  HbrHalfedge<T>* childedge;
482 
483  childedge = child->GetEdge(i);
484  if ((sharpness = edge->GetSharpness()) > HbrHalfedge<T>::k_Smooth) {
486  edge, edge->GetOrgVertex(), childedge);
487  }
488  childedge->CopyFVarInfiniteSharpness(edge);
489 
490  childedge = child->GetEdge((i+2)%3);
491  if ((sharpness = prevedge->GetSharpness()) > HbrHalfedge<T>::k_Smooth) {
493  prevedge, prevedge->GetDestVertex(), childedge);
494  }
495  childedge->CopyFVarInfiniteSharpness(prevedge);
496 
497  if (mesh->GetTotalFVarWidth()) {
498  transferFVarToChild(mesh, face, child, i);
499  }
500 
501  transferEditsToChild(face, child, i);
502 
503  }
504  prevedge = edge;
505  edge = edge->GetNext();
506  }
507 
508  refineFaceAtMiddle(mesh, face);
509 }
510 
511 template <class T>
512 HbrFace<T>*
514 
515 #ifdef HBR_DEBUG
516  std::cerr << " forcing refine on " << *face << " at " << *vertex << '\n';
517 #endif
518  HbrHalfedge<T>* edge = face->GetFirstEdge();
519  HbrHalfedge<T>* prevedge = edge->GetPrev();
520 
521  for (int i = 0; i < 3; ++i) {
522  if (edge->GetOrgVertex() == vertex) {
523  if (!face->GetChild(i)) {
524 #ifdef HBR_DEBUG
525  std::cerr << "Kid " << i << "\n";
526 #endif
527  HbrFace<T>* child;
528  HbrVertex<T>* vertices[3];
529 
530  vertices[i] = vertex->Subdivide();
531  vertices[(i + 1) % 3] = edge->Subdivide();
532  vertices[(i + 2) % 3] = prevedge->Subdivide();
533  child = mesh->NewFace(3, vertices, face, i);
534 #ifdef HBR_DEBUG
535  std::cerr << "Creating face " << *child << " during refine\n";
536 #endif
537 
538  // Hand down edge sharpness
539  float sharpness;
540  HbrHalfedge<T>* childedge;
541 
542  childedge = child->GetEdge(i);
543  if ((sharpness = edge->GetSharpness()) > HbrHalfedge<T>::k_Smooth) {
545  edge, edge->GetOrgVertex(), childedge);
546  }
547  childedge->CopyFVarInfiniteSharpness(edge);
548 
549  childedge = child->GetEdge((i+2)%3);
550  if ((sharpness = prevedge->GetSharpness()) > HbrHalfedge<T>::k_Smooth) {
552  prevedge, prevedge->GetDestVertex(), childedge);
553  }
554  childedge->CopyFVarInfiniteSharpness(prevedge);
555 
556  if (mesh->GetTotalFVarWidth()) {
557  transferFVarToChild(mesh, face, child, i);
558  }
559 
560  transferEditsToChild(face, child, i);
561 
562  return child;
563  } else {
564  return face->GetChild(i);
565  }
566  }
567  prevedge = edge;
568  edge = edge->GetNext();
569  }
570  return 0;
571 }
572 
573 template <class T>
574 void
576  if (edge->GetOpposite()) {
577  return;
578  }
579 
580 #ifdef HBR_DEBUG
581  std::cerr << "\n\nneighbor guarantee at " << *edge << " invoked\n";
582 #endif
583 
584  /*
585  Imagine the following:
586 
587  X
588  / \
589  / \
590  / \
591  X \
592  /\ \
593  2/ \3 \
594  / \ \
595  X------X--------X
596  1
597 
598  If the parent of _both_ incident vertices are themselves edges,
599  (like the edge marked 3 above), then this edge is in the center
600  of the parent face. Refining the parent face in the middle or
601  refining the parent face at one vertex (where the two parent
602  edges meet) should suffice
603  */
604  HbrHalfedge<T>* parentEdge1 = edge->GetOrgVertex()->GetParentEdge();
605  HbrHalfedge<T>* parentEdge2 = edge->GetDestVertex()->GetParentEdge();
606  if (parentEdge1 && parentEdge2) {
607 #ifdef HBR_DEBUG
608  std::cerr << "two parent edge situation\n";
609 #endif
610  HbrFace<T>* parentFace = parentEdge1->GetFace();
611  assert(parentFace == parentEdge2->GetFace());
612  if(parentEdge1->GetOrgVertex() == parentEdge2->GetDestVertex()) {
613  refineFaceAtMiddle(mesh, parentFace);
614  } else {
615  RefineFaceAtVertex(mesh, parentFace, parentEdge1->GetOrgVertex());
616  }
617  assert(edge->GetOpposite());
618  return;
619  }
620 
621  // Otherwise we're in the situation of edge 1 or edge 2 in the
622  // diagram above.
623  if (parentEdge1) {
624 #ifdef HBR_DEBUG
625  std::cerr << "parent edge 1 " << *parentEdge1 << "\n";
626 #endif
627  HbrVertex<T>* parentVertex2 = edge->GetDestVertex()->GetParentVertex();
628  assert(parentVertex2);
629  RefineFaceAtVertex(mesh, parentEdge1->GetLeftFace(), parentVertex2);
630  if (parentEdge1->GetRightFace()) {
631  RefineFaceAtVertex(mesh, parentEdge1->GetRightFace(), parentVertex2);
632  }
633  } else if (parentEdge2) {
634 #ifdef HBR_DEBUG
635  std::cerr << "parent edge 2 " << *parentEdge2 << "\n";
636 #endif
637  HbrVertex<T>* parentVertex1 = edge->GetOrgVertex()->GetParentVertex();
638  assert(parentVertex1);
639  RefineFaceAtVertex(mesh, parentEdge2->GetLeftFace(), parentVertex1);
640  if (parentEdge2->GetRightFace()) {
641  RefineFaceAtVertex(mesh, parentEdge2->GetRightFace(), parentVertex1);
642  }
643  }
644 }
645 
646 template <class T>
647 void
649 
650 #ifdef HBR_DEBUG
651  std::cerr << "\n\nneighbor guarantee at " << *vertex << " invoked\n";
652 #endif
653 
654  assert(vertex->GetParentFace() == 0);
655 
656  // The first case: the vertex is a child of an edge. Make sure
657  // that the parent faces on either side of the parent edge exist,
658  // and have 1) refined at both vertices of the parent edge, and 2)
659  // have refined their "middle" face (which doesn't live at either
660  // vertex).
661 
662  HbrHalfedge<T>* parentEdge = vertex->GetParentEdge();
663  if (parentEdge) {
664 #ifdef HBR_DEBUG
665  std::cerr << "parent edge situation " << *parentEdge << "\n";
666 #endif
667  HbrVertex<T>* dest = parentEdge->GetDestVertex();
668  HbrVertex<T>* org = parentEdge->GetOrgVertex();
669  GuaranteeNeighbor(mesh, parentEdge);
670  HbrFace<T>* parentFace = parentEdge->GetLeftFace();
671  RefineFaceAtVertex(mesh, parentFace, dest);
672  RefineFaceAtVertex(mesh, parentFace, org);
673  refineFaceAtMiddle(mesh, parentFace);
674  parentFace = parentEdge->GetRightFace();
675  // The right face may not necessarily exist even after
676  // GuaranteeNeighbor
677  if (parentFace) {
678  RefineFaceAtVertex(mesh, parentFace, dest);
679  RefineFaceAtVertex(mesh, parentFace, org);
680  refineFaceAtMiddle(mesh, parentFace);
681  }
682  return;
683  }
684 
685  // The second case: the vertex is a child of a vertex. In this case
686  // we have to recursively guarantee that the parent's adjacent
687  // faces also exist.
688  HbrVertex<T>* parentVertex = vertex->GetParentVertex();
689  if (parentVertex) {
690 #ifdef HBR_DEBUG
691  std::cerr << "parent vertex situation " << *parentVertex << "\n";
692 #endif
693  parentVertex->GuaranteeNeighbors();
694 
695  // And then we refine all the face neighbors of the parent
696  // vertex
697  HbrHalfedge<T>* start = parentVertex->GetIncidentEdge(), *edge;
698  edge = start;
699  while (edge) {
700  HbrFace<T>* f = edge->GetLeftFace();
701  RefineFaceAtVertex(mesh, f, parentVertex);
702  edge = parentVertex->GetNextEdge(edge);
703  if (edge == start) break;
704  }
705  }
706 }
707 
708 template <class T>
709 bool
711 
712  if (face->IsHole()) return false;
713  // A limit face exists if all the bounding edges have limit curves
714  for (int i = 0; i < face->GetNumVertices(); ++i) {
715  if (!HasLimit(mesh, face->GetEdge(i))) {
716  return false;
717  }
718  }
719  return true;
720 }
721 
722 template <class T>
723 bool
725  // A sharp edge has a limit curve if both endpoints have limits.
726  // A smooth edge has a limit if both endpoints have limits and
727  // the edge isn't on the boundary.
728 
729  if (edge->GetSharpness() >= HbrHalfedge<T>::k_InfinitelySharp) return true;
730 
731  if (!HasLimit(mesh, edge->GetOrgVertex()) || !HasLimit(mesh, edge->GetDestVertex())) return false;
732 
733  return !edge->IsBoundary();
734 }
735 
736 template <class T>
737 bool
739  vertex->GuaranteeNeighbors();
740  switch (vertex->GetMask(false)) {
743  return !vertex->OnBoundary();
744  break;
747  default:
748  if (vertex->IsVolatile()) {
749  // Search for any incident semisharp boundary edge
750  HbrHalfedge<T>* start = vertex->GetIncidentEdge(), *edge, *next;
751  edge = start;
752  while (edge) {
753  if (edge->IsBoundary() && edge->GetSharpness() < HbrHalfedge<T>::k_InfinitelySharp) {
754  return false;
755  }
756  next = vertex->GetNextEdge(edge);
757  if (next == start) {
758  break;
759  } else if (!next) {
760  edge = edge->GetPrev();
761  if (edge->IsBoundary() && edge->GetSharpness() < HbrHalfedge<T>::k_InfinitelySharp) {
762  return false;
763  }
764  break;
765  } else {
766  edge = next;
767  }
768  }
769  }
770  return true;
771  }
772 }
773 
774 template <class T>
777  // In loop subdivision, faces never subdivide
778  assert(0);
779  return 0;
780 }
781 
782 template <class T>
785 
786 #ifdef HBR_DEBUG
787  std::cerr << "Subdividing at " << *edge << "\n";
788 #endif
789  // Ensure the opposite face exists.
790  GuaranteeNeighbor(mesh, edge);
791 
792  float esharp = edge->GetSharpness();
793  HbrVertex<T>* v = mesh->NewVertex();
794  T& data = v->GetData();
795 
796  // If there's the possibility of vertex edits on either vertex, we
797  // have to make sure the edit has been applied
798  if (mesh->HasVertexEdits()) {
799  edge->GetOrgVertex()->GuaranteeNeighbors();
800  edge->GetDestVertex()->GuaranteeNeighbors();
801  }
802 
803  if (!edge->IsBoundary() && esharp <= 1.0f) {
804 
805  // Of the two half-edges, pick one of them consistently such
806  // that the org and dest vertices are also consistent through
807  // multi-threading. It doesn't matter as far as the
808  // theoretical calculation is concerned, but it is desirable
809  // to be consistent about it in the face of the limitations of
810  // floating point commutativity. So we always pick the
811  // half-edge such that its incident face is the smallest of
812  // the two faces, as far as the face paths are concerned.
813  if (edge->GetOpposite() && edge->GetOpposite()->GetFace()->GetPath() < edge->GetFace()->GetPath()) {
814  edge = edge->GetOpposite();
815  }
816 
817  // Handle both the smooth and fractional sharpness cases. We
818  // lerp between the sharp case (average of the two end points)
819  // and the unsharp case (3/8 of each of the two end points
820  // plus 1/8 of the two opposite face averages).
821 
822  // Lerp end point weight between non sharp contribution of
823  // 3/8 and the sharp contribution of 0.5.
824  float endPtWeight = 0.375f + esharp * (0.5f - 0.375f);
825  data.AddWithWeight(edge->GetOrgVertex()->GetData(), endPtWeight);
826  data.AddWithWeight(edge->GetDestVertex()->GetData(), endPtWeight);
827 
828  // Lerp the opposite pt weights between non sharp contribution
829  // of 1/8 and the sharp contribution of 0.
830  float oppPtWeight = 0.125f * (1 - esharp);
831  HbrHalfedge<T>* ee = edge->GetNext();
832  data.AddWithWeight(ee->GetDestVertex()->GetData(), oppPtWeight);
833  ee = edge->GetOpposite()->GetNext();
834  data.AddWithWeight(ee->GetDestVertex()->GetData(), oppPtWeight);
835  } else {
836  // Fully sharp edge, just average the two end points
837  data.AddWithWeight(edge->GetOrgVertex()->GetData(), 0.5f);
838  data.AddWithWeight(edge->GetDestVertex()->GetData(), 0.5f);
839  }
840 
841  // Varying data is always the average of two end points
842  data.AddVaryingWithWeight(edge->GetOrgVertex()->GetData(), 0.5f);
843  data.AddVaryingWithWeight(edge->GetDestVertex()->GetData(), 0.5f);
844 
845 #ifdef HBR_DEBUG
846  std::cerr << " created " << *v << "\n";
847 #endif
848 
849  // Only boundary edges will create extraordinary vertices
850  if (edge->IsBoundary()) {
851  v->SetExtraordinary();
852  }
853  return v;
854 }
855 
856 template <class T>
859 
860  // Ensure the ring of faces around this vertex exists before
861  // we compute the valence
862  vertex->GuaranteeNeighbors();
863 
864  float valence = static_cast<float>(vertex->GetValence());
865  float invvalence = 1.0f / valence;
866 
867  HbrVertex<T>* v = mesh->NewVertex();
868  T& data = v->GetData();
869 
870  // Due to fractional weights we may need to do two subdivision
871  // passes
872  int masks[2];
873  float weights[2];
874  int passes;
875  masks[0] = vertex->GetMask(false);
876  masks[1] = vertex->GetMask(true);
877  // If the masks are different, we subdivide twice: once using the
878  // current mask, once using the mask at the next level of
879  // subdivision, then use fractional mask weights to weigh
880  // each weighing
881  if (masks[0] != masks[1]) {
882  weights[1] = vertex->GetFractionalMask();
883  weights[0] = 1.0f - weights[1];
884  passes = 2;
885  } else {
886  weights[0] = 1.0f;
887  weights[1] = 0.0f;
888  passes = 1;
889  }
890  for (int i = 0; i < passes; ++i) {
891  switch (masks[i]) {
893  case HbrVertex<T>::k_Dart: {
894  float beta = 0.25f * cosf((float)M_PI * 2.0f * invvalence) + 0.375f;
895  beta = beta * beta;
896  beta = (0.625f - beta) * invvalence;
897 
898  data.AddWithWeight(vertex->GetData(), weights[i] * (1 - (beta * valence)));
899 
901  mesh, vertex, weights[i] * beta, &data);
902  break;
903  }
904  case HbrVertex<T>::k_Crease: {
905  // Compute 3/4 of old vertex value
906  data.AddWithWeight(vertex->GetData(), weights[i] * 0.75f);
907 
908  // Add 0.125f of the (hopefully only two!) neighbouring
909  // sharp edges
911  mesh, vertex, i == 1, weights[i] * 0.125f, &data);
912  break;
913  }
915  default: {
916  // Just copy the old value
917  data.AddWithWeight(vertex->GetData(), weights[i]);
918  break;
919  }
920  }
921  }
922 
923  // Varying data is always just propagated down
924  data.AddVaryingWithWeight(vertex->GetData(), 1.0f);
925 
926 #ifdef HBR_DEBUG
927  std::cerr << "Subdividing at " << *vertex << "\n";
928  std::cerr << " created " << *v << "\n";
929 #endif
930  // Inherit extraordinary flag and sharpness
931  if (vertex->IsExtraordinary()) v->SetExtraordinary();
932  float sharp = vertex->GetSharpness();
933  if (sharp >= HbrVertex<T>::k_InfinitelySharp) {
934  v->SetSharpness(HbrVertex<T>::k_InfinitelySharp);
935  } else if (sharp > HbrVertex<T>::k_Smooth) {
936  v->SetSharpness(std::max((float) HbrVertex<T>::k_Smooth, sharp - 1.0f));
937  } else {
938  v->SetSharpness(HbrVertex<T>::k_Smooth);
939  }
940  return v;
941 }
942 
943 template <class T>
944 void
946 
947 #ifdef HBR_DEBUG
948  std::cerr << "Refining middle face of " << *face << "\n";
949 #endif
950 
951  if (!face->GetChild(3)) {
952  HbrFace<T>* child;
953  HbrVertex<T>* vertices[3];
954 
955  // The fourth face is not an obvious child of any vertex. We
956  // assign it index 3 despite there being no fourth vertex in
957  // the triangle. The ordering of vertices here is done to
958  // preserve parametric space as best we can
959  vertices[0] = face->GetEdge(1)->Subdivide();
960  vertices[1] = face->GetEdge(2)->Subdivide();
961  vertices[2] = face->GetEdge(0)->Subdivide();
962  child = mesh->NewFace(3, vertices, face, 3);
963 #ifdef HBR_DEBUG
964  std::cerr << "Creating face " << *child << "\n";
965 #endif
966  if (mesh->GetTotalFVarWidth()) {
967  transferFVarToChild(mesh, face, child, 3);
968  }
969 
970  transferEditsToChild(face, child, 3);
971  }
972 }
973 
974 } // end namespace OPENSUBDIV_VERSION
975 using namespace OPENSUBDIV_VERSION;
976 
977 } // end namespace OpenSubdiv
978 
979 #endif /* HBRLOOP_H */
980 
HbrFVarData< T > & NewFVarData(const HbrFace< T > *face)
Definition: vertex.h:907
HbrHalfedge< T > * GetEdge(int index) const
Definition: face.h:718
HbrVertex< T > * NewVertex(int id, const T &data)
Definition: mesh.h:533
virtual bool FaceIsExtraordinary(HbrMesh< T > const *, HbrFace< T > *face)
Definition: loop.h:65
InterpolateBoundaryMethod GetFVarInterpolateBoundaryMethod() const
Definition: mesh.h:211
void CopyFVarInfiniteSharpness(HbrHalfedge< T > *edge)
Definition: halfedge.h:185
unsigned char GetMask(bool next)
Definition: vertex.h:1179
HbrHalfedge< T > * GetFirstEdge() const
Definition: face.h:136
HbrHalfedge< T > * GetEdge(const HbrVertex< T > *dest) const
Definition: vertex.h:954
void SubdivideCreaseWeight(HbrHalfedge< T > *edge, HbrVertex< T > *vertex, HbrHalfedge< T > *subedge)
Definition: subdivision.h:205
virtual HbrVertex< T > * Subdivide(HbrMesh< T > *mesh, HbrFace< T > *face)
Definition: loop.h:776
HbrFace< T > * GetChild(int index) const
Definition: face.h:164
HbrHalfedge< T > * GetNext() const
Definition: halfedge.h:80
HbrVertex< T > * GetDestVertex() const
Definition: halfedge.h:143
virtual void Refine(HbrMesh< T > *mesh, HbrFace< T > *face)
Definition: loop.h:452
virtual bool HasLimit(HbrMesh< T > *mesh, HbrFace< T > *face)
Definition: loop.h:710
virtual bool VertexIsExtraordinary(HbrMesh< T > const *, HbrVertex< T > *vertex)
Definition: loop.h:64
HbrVertex< T > * GetParentVertex() const
Definition: vertex.h:222
HbrFVarData< T > & GetFVarData(int index)
Definition: face.h:221
virtual int GetFaceChildrenCount(int) const
Definition: loop.h:67
virtual void GuaranteeNeighbors(HbrMesh< T > *mesh, HbrVertex< T > *vertex)
Definition: loop.h:648
HbrHalfedge< T > * GetIncidentEdge() const
Definition: vertex.h:285
HbrHalfedge< T > * GetNextEdge(const HbrHalfedge< T > *edge) const
Definition: vertex.h:990
void AddCreaseEdgesWithWeight(HbrMesh< T > *mesh, HbrVertex< T > *vertex, bool next, float weight, T *data)
Definition: subdivision.h:283
HbrHalfedge< T > * GetOpposite() const
Definition: halfedge.h:74
HbrVertex< T > * GetVertex(int index) const
Definition: face.h:730
HbrVertex< T > * GetOrgVertex() const
Definition: halfedge.h:125
virtual HbrFace< T > * RefineFaceAtVertex(HbrMesh< T > *mesh, HbrFace< T > *face, HbrVertex< T > *vertex)
Definition: loop.h:513
virtual HbrSubdivision< T > * Clone() const
Definition: loop.h:47
HbrFace< T > * NewFace(int nvertices, const int *vtx, int uindex)
Definition: mesh.h:607
void AddSurroundingVerticesWithWeight(HbrMesh< T > *mesh, HbrVertex< T > *vertex, float weight, T *data)
Definition: subdivision.h:276
virtual void GuaranteeNeighbor(HbrMesh< T > *mesh, HbrHalfedge< T > *edge)
Definition: loop.h:575
HbrHalfedge< T > * GetPrev() const
Definition: halfedge.h:98
const int * GetFVarWidths() const
Definition: mesh.h:187
HbrFVarData< T > & GetFVarData(const HbrFace< T > *face)
Definition: vertex.h:887