Blender  V3.3
subd/split.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0
2  * Copyright 2011-2022 Blender Foundation */
3 
4 #include "scene/camera.h"
5 #include "scene/mesh.h"
6 
7 #include "subd/dice.h"
8 #include "subd/patch.h"
9 #include "subd/split.h"
10 
11 #include "util/algorithm.h"
12 #include "util/foreach.h"
13 #include "util/hash.h"
14 #include "util/math.h"
15 #include "util/types.h"
16 
18 
19 /* DiagSplit */
20 
21 #define DSPLIT_NON_UNIFORM -1
22 #define STITCH_NGON_CENTER_VERT_INDEX_OFFSET 0x60000000
23 #define STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG (0x60000000 - 1)
24 
25 DiagSplit::DiagSplit(const SubdParams &params_) : params(params_)
26 {
27 }
28 
29 float3 DiagSplit::to_world(Patch *patch, float2 uv)
30 {
31  float3 P;
32 
33  patch->eval(&P, NULL, NULL, NULL, uv.x, uv.y);
34  if (params.camera)
35  P = transform_point(&params.objecttoworld, P);
36 
37  return P;
38 }
39 
40 static void order_float2(float2 &a, float2 &b)
41 {
42  if (b.x < a.x || b.y < a.y) {
43  swap(a, b);
44  }
45 }
46 
47 int DiagSplit::T(Patch *patch, float2 Pstart, float2 Pend, bool recursive_resolve)
48 {
49  order_float2(Pstart, Pend); /* May not be necessary, but better to be safe. */
50 
51  float Lsum = 0.0f;
52  float Lmax = 0.0f;
53 
54  float3 Plast = to_world(patch, Pstart);
55 
56  for (int i = 1; i < params.test_steps; i++) {
57  float t = i / (float)(params.test_steps - 1);
58 
59  float3 P = to_world(patch, Pstart + t * (Pend - Pstart));
60 
61  float L;
62 
63  if (!params.camera) {
64  L = len(P - Plast);
65  }
66  else {
67  Camera *cam = params.camera;
68 
69  float pixel_width = cam->world_to_raster_size((P + Plast) * 0.5f);
70  L = len(P - Plast) / pixel_width;
71  }
72 
73  Lsum += L;
74  Lmax = max(L, Lmax);
75 
76  Plast = P;
77  }
78 
79  int tmin = (int)ceilf(Lsum / params.dicing_rate);
80  int tmax = (int)ceilf((params.test_steps - 1) * Lmax /
81  params.dicing_rate); // XXX paper says N instead of N-1, seems wrong?
82  int res = max(tmax, 1);
83 
84  if (tmax - tmin > params.split_threshold) {
85  if (!recursive_resolve) {
86  res = DSPLIT_NON_UNIFORM;
87  }
88  else {
89  float2 P = (Pstart + Pend) * 0.5f;
90  res = T(patch, Pstart, P, true) + T(patch, P, Pend, true);
91  }
92  }
93 
94  limit_edge_factor(res, patch, Pstart, Pend);
95  return res;
96 }
97 
98 void DiagSplit::partition_edge(
99  Patch *patch, float2 *P, int *t0, int *t1, float2 Pstart, float2 Pend, int t)
100 {
101  if (t == DSPLIT_NON_UNIFORM) {
102  *P = (Pstart + Pend) * 0.5f;
103  *t0 = T(patch, Pstart, *P);
104  *t1 = T(patch, *P, Pend);
105  }
106  else {
107  assert(t >= 2); /* Need at least two segments to partition into. */
108 
109  int I = (int)floorf((float)t * 0.5f);
110  *P = interp(Pstart, Pend, I / (float)t);
111  *t0 = I;
112  *t1 = t - I;
113  }
114 }
115 
116 void DiagSplit::limit_edge_factor(int &T, Patch *patch, float2 Pstart, float2 Pend)
117 {
118  int max_t = 1 << params.max_level;
119  int max_t_for_edge = int(max_t * len(Pstart - Pend));
120 
121  if (patch->from_ngon) {
122  max_t_for_edge >>= 1; /* Initial split of ngon causes edges to extend half the distance. */
123  }
124 
125  T = (max_t_for_edge <= 1) ? 1 : min(T, max_t_for_edge);
126 
127  assert(T >= 1 || T == DSPLIT_NON_UNIFORM);
128 }
129 
130 void DiagSplit::resolve_edge_factors(Subpatch &sub)
131 {
132  /* Resolve DSPLIT_NON_UNIFORM to actual T value if splitting is no longer possible. */
133  if (sub.edge_u0.T == 1 && sub.edge_u1.T == DSPLIT_NON_UNIFORM) {
134  sub.edge_u1.T = T(sub.patch, sub.c01, sub.c11, true);
135  }
136  if (sub.edge_u1.T == 1 && sub.edge_u0.T == DSPLIT_NON_UNIFORM) {
137  sub.edge_u0.T = T(sub.patch, sub.c00, sub.c10, true);
138  }
139  if (sub.edge_v0.T == 1 && sub.edge_v1.T == DSPLIT_NON_UNIFORM) {
140  sub.edge_v1.T = T(sub.patch, sub.c11, sub.c10, true);
141  }
142  if (sub.edge_v1.T == 1 && sub.edge_v0.T == DSPLIT_NON_UNIFORM) {
143  sub.edge_v0.T = T(sub.patch, sub.c01, sub.c00, true);
144  }
145 }
146 
147 void DiagSplit::split(Subpatch &sub, int depth)
148 {
149  if (depth > 32) {
150  /* We should never get here, but just in case end recursion safely. */
151  assert(!"diagsplit recursion limit reached");
152 
153  sub.edge_u0.T = 1;
154  sub.edge_u1.T = 1;
155  sub.edge_v0.T = 1;
156  sub.edge_v1.T = 1;
157 
158  subpatches.push_back(sub);
159  return;
160  }
161 
162  bool split_u = (sub.edge_u0.T == DSPLIT_NON_UNIFORM || sub.edge_u1.T == DSPLIT_NON_UNIFORM);
163  bool split_v = (sub.edge_v0.T == DSPLIT_NON_UNIFORM || sub.edge_v1.T == DSPLIT_NON_UNIFORM);
164 
165  /* Split subpatches such that the ratio of T for opposite edges doesn't
166  * exceed 1.5, this reduces over tessellation for some patches
167  */
168  /* clang-format off */
169  if (min(sub.edge_u0.T, sub.edge_u1.T) > 8 && /* Must be uniform and preferably greater than 8 to split. */
170  min(sub.edge_v0.T, sub.edge_v1.T) >= 2 && /* Must be uniform and at least 2 to split. */
171  max(sub.edge_u0.T, sub.edge_u1.T) / min(sub.edge_u0.T, sub.edge_u1.T) > 1.5f)
172  {
173  split_v = true;
174  }
175  if (min(sub.edge_v0.T, sub.edge_v1.T) > 8 &&
176  min(sub.edge_u0.T, sub.edge_u1.T) >= 2 &&
177  max(sub.edge_v0.T, sub.edge_v1.T) / min(sub.edge_v0.T, sub.edge_v1.T) > 1.5f)
178  {
179  split_u = true;
180  }
181  /* clang-format on */
182 
183  /* Alternate axis. */
184  if (split_u && split_v) {
185  split_u = depth % 2;
186  }
187 
188  if (!split_u && !split_v) {
189  /* Add the unsplit subpatch. */
190  subpatches.push_back(sub);
191  Subpatch &subpatch = subpatches[subpatches.size() - 1];
192 
193  /* Update T values and offsets. */
194  for (int i = 0; i < 4; i++) {
195  Subpatch::edge_t &edge = subpatch.edges[i];
196 
197  edge.offset = edge.edge->T;
198  edge.edge->T += edge.T;
199  }
200  }
201  else {
202  /* Copy into new subpatches. */
203  Subpatch sub_a = sub;
204  Subpatch sub_b = sub;
205 
206  /* Pointers to various subpatch elements. */
207  Subpatch::edge_t *sub_across_0, *sub_across_1;
208  Subpatch::edge_t *sub_a_across_0, *sub_a_across_1;
209  Subpatch::edge_t *sub_b_across_0, *sub_b_across_1;
210 
211  Subpatch::edge_t *sub_a_split, *sub_b_split;
212 
213  float2 *Pa, *Pb, *Pc, *Pd;
214 
215  /* Set pointers based on split axis. */
216  if (split_u) {
217  sub_across_0 = &sub.edge_u0;
218  sub_across_1 = &sub.edge_u1;
219  sub_a_across_0 = &sub_a.edge_u0;
220  sub_a_across_1 = &sub_a.edge_u1;
221  sub_b_across_0 = &sub_b.edge_u0;
222  sub_b_across_1 = &sub_b.edge_u1;
223 
224  sub_a_split = &sub_a.edge_v1;
225  sub_b_split = &sub_b.edge_v0;
226 
227  Pa = &sub_a.c11;
228  Pb = &sub_a.c10;
229  Pc = &sub_b.c01;
230  Pd = &sub_b.c00;
231  }
232  else {
233  sub_across_0 = &sub.edge_v0;
234  sub_across_1 = &sub.edge_v1;
235  sub_a_across_0 = &sub_a.edge_v0;
236  sub_a_across_1 = &sub_a.edge_v1;
237  sub_b_across_0 = &sub_b.edge_v0;
238  sub_b_across_1 = &sub_b.edge_v1;
239 
240  sub_a_split = &sub_a.edge_u0;
241  sub_b_split = &sub_b.edge_u1;
242 
243  Pa = &sub_a.c10;
244  Pb = &sub_a.c00;
245  Pc = &sub_b.c11;
246  Pd = &sub_b.c01;
247  }
248 
249  /* Partition edges */
250  float2 P0, P1;
251 
252  partition_edge(
253  sub.patch, &P0, &sub_a_across_0->T, &sub_b_across_0->T, *Pd, *Pb, sub_across_0->T);
254  partition_edge(
255  sub.patch, &P1, &sub_a_across_1->T, &sub_b_across_1->T, *Pc, *Pa, sub_across_1->T);
256 
257  /* Split */
258  *Pa = P1;
259  *Pb = P0;
260 
261  *Pc = P1;
262  *Pd = P0;
263 
264  int tsplit = T(sub.patch, P0, P1);
265 
266  if (depth == -2 && tsplit == 1) {
267  tsplit = 2; /* Ensure we can always split at depth -1. */
268  }
269 
270  sub_a_split->T = tsplit;
271  sub_b_split->T = tsplit;
272 
273  resolve_edge_factors(sub_a);
274  resolve_edge_factors(sub_b);
275 
276  /* Create new edge */
277  Edge &edge = *alloc_edge();
278 
279  sub_a_split->edge = &edge;
280  sub_b_split->edge = &edge;
281 
282  sub_a_split->offset = 0;
283  sub_b_split->offset = 0;
284 
285  sub_a_split->indices_decrease_along_edge = false;
286  sub_b_split->indices_decrease_along_edge = true;
287 
288  sub_a_split->sub_edges_created_in_reverse_order = !split_u;
289  sub_b_split->sub_edges_created_in_reverse_order = !split_u;
290 
291  edge.top_indices_decrease = sub_across_1->sub_edges_created_in_reverse_order;
292  edge.bottom_indices_decrease = sub_across_0->sub_edges_created_in_reverse_order;
293 
294  /* Recurse */
295  edge.T = 0;
296  split(sub_a, depth + 1);
297 
298  int edge_t = edge.T;
299  (void)edge_t;
300 
301  edge.top_offset = sub_across_1->edge->T;
302  edge.bottom_offset = sub_across_0->edge->T;
303 
304  edge.T = 0; /* We calculate T twice along each edge. :/ */
305  split(sub_b, depth + 1);
306 
307  assert(edge.T == edge_t); /* If this fails we will crash at some later point! */
308 
309  edge.top = sub_across_1->edge;
310  edge.bottom = sub_across_0->edge;
311  }
312 }
313 
314 int DiagSplit::alloc_verts(int n)
315 {
316  int a = num_alloced_verts;
317  num_alloced_verts += n;
318  return a;
319 }
320 
322 {
323  edges.emplace_back();
324  return &edges.back();
325 }
326 
327 void DiagSplit::split_patches(Patch *patches, size_t patches_byte_stride)
328 {
329  int patch_index = 0;
330 
331  for (int f = 0; f < params.mesh->get_num_subd_faces(); f++) {
332  Mesh::SubdFace face = params.mesh->get_subd_face(f);
333 
334  Patch *patch = (Patch *)(((char *)patches) + patch_index * patches_byte_stride);
335 
336  if (face.is_quad()) {
337  patch_index++;
338 
339  split_quad(face, patch);
340  }
341  else {
342  patch_index += face.num_corners;
343 
344  split_ngon(face, patch, patches_byte_stride);
345  }
346  }
347 
348  params.mesh->vert_to_stitching_key_map.clear();
349  params.mesh->vert_stitching_map.clear();
350 
351  post_split();
352 }
353 
355  const Mesh *mesh,
356  const Mesh::SubdFace &face,
357  int corner,
358  bool &reversed,
359  int v0,
360  int v1)
361 {
362  int a = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 0, face.num_corners)];
363  int b = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 1, face.num_corners)];
364 
365  reversed = !(b < a);
366 
367  if (b < a) {
368  swap(a, b);
369  swap(v0, v1);
370  }
371 
372  Edge *edge = split->alloc_edge();
373 
374  edge->is_stitch_edge = true;
375  edge->stitch_start_vert_index = a;
376  edge->stitch_end_vert_index = b;
377 
378  edge->start_vert_index = v0;
379  edge->end_vert_index = v1;
380 
381  edge->stitch_edge_key = {a, b};
382 
383  return edge;
384 }
385 
386 void DiagSplit::split_quad(const Mesh::SubdFace &face, Patch *patch)
387 {
388  Subpatch subpatch(patch);
389 
390  int v = alloc_verts(4);
391 
392  bool v0_reversed, u1_reversed, v1_reversed, u0_reversed;
394  this, params.mesh, face, 3, v0_reversed, v + 3, v + 0);
396  this, params.mesh, face, 2, u1_reversed, v + 2, v + 3);
398  this, params.mesh, face, 1, v1_reversed, v + 1, v + 2);
400  this, params.mesh, face, 0, u0_reversed, v + 0, v + 1);
401 
402  subpatch.edge_v0.sub_edges_created_in_reverse_order = !v0_reversed;
403  subpatch.edge_u1.sub_edges_created_in_reverse_order = u1_reversed;
404  subpatch.edge_v1.sub_edges_created_in_reverse_order = v1_reversed;
405  subpatch.edge_u0.sub_edges_created_in_reverse_order = !u0_reversed;
406 
407  subpatch.edge_v0.indices_decrease_along_edge = v0_reversed;
408  subpatch.edge_u1.indices_decrease_along_edge = u1_reversed;
409  subpatch.edge_v1.indices_decrease_along_edge = v1_reversed;
410  subpatch.edge_u0.indices_decrease_along_edge = u0_reversed;
411 
412  /* Forces a split in both axis for quads, needed to match split of ngons into quads. */
413  subpatch.edge_u0.T = DSPLIT_NON_UNIFORM;
414  subpatch.edge_u1.T = DSPLIT_NON_UNIFORM;
415  subpatch.edge_v0.T = DSPLIT_NON_UNIFORM;
416  subpatch.edge_v1.T = DSPLIT_NON_UNIFORM;
417 
418  split(subpatch, -2);
419 }
420 
422  const Mesh *mesh,
423  const Mesh::SubdFace &face,
424  int corner,
425  int side,
426  bool &reversed,
427  int v0,
428  int v1,
429  int vc)
430 {
431  Edge *edge = split->alloc_edge();
432 
433  int a = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 0, face.num_corners)];
434  int b = mesh->get_subd_face_corners()[face.start_corner + mod(corner + 1, face.num_corners)];
435 
436  if (b < a) {
437  edge->stitch_edge_key = {b, a};
438  }
439  else {
440  edge->stitch_edge_key = {a, b};
441  }
442 
443  reversed = !(b < a);
444 
445  if (side == 0) {
446  a = vc;
447  }
448  else {
449  b = vc;
450  }
451 
452  if (!reversed) {
453  swap(a, b);
454  swap(v0, v1);
455  }
456 
457  edge->is_stitch_edge = true;
458  edge->stitch_start_vert_index = a;
459  edge->stitch_end_vert_index = b;
460 
461  edge->start_vert_index = v0;
462  edge->end_vert_index = v1;
463 
464  return edge;
465 }
466 
467 void DiagSplit::split_ngon(const Mesh::SubdFace &face, Patch *patches, size_t patches_byte_stride)
468 {
469  Edge *prev_edge_u0 = nullptr;
470  Edge *first_edge_v0 = nullptr;
471 
472  for (int corner = 0; corner < face.num_corners; corner++) {
473  Patch *patch = (Patch *)(((char *)patches) + corner * patches_byte_stride);
474 
475  Subpatch subpatch(patch);
476 
477  int v = alloc_verts(4);
478 
479  /* Setup edges. */
480  Edge *edge_u1 = alloc_edge();
481  Edge *edge_v1 = alloc_edge();
482 
483  edge_v1->is_stitch_edge = true;
484  edge_u1->is_stitch_edge = true;
485 
486  edge_u1->stitch_start_vert_index = -(face.start_corner + mod(corner + 0, face.num_corners)) -
487  1;
489 
490  edge_u1->start_vert_index = v + 3;
491  edge_u1->end_vert_index = v + 2;
492 
493  edge_u1->stitch_edge_key = {edge_u1->stitch_start_vert_index, edge_u1->stitch_end_vert_index};
494 
495  edge_v1->stitch_start_vert_index = -(face.start_corner + mod(corner + 1, face.num_corners)) -
496  1;
498 
499  edge_v1->start_vert_index = v + 1;
500  edge_v1->end_vert_index = v + 2;
501 
502  edge_v1->stitch_edge_key = {edge_v1->stitch_start_vert_index, edge_v1->stitch_end_vert_index};
503 
504  bool v0_reversed, u0_reversed;
505 
507  params.mesh,
508  face,
509  corner - 1,
510  0,
511  v0_reversed,
512  v + 3,
513  v + 0,
515 
516  subpatch.edge_u1.edge = edge_u1;
517  subpatch.edge_v1.edge = edge_v1;
518 
520  params.mesh,
521  face,
522  corner + 0,
523  1,
524  u0_reversed,
525  v + 0,
526  v + 1,
528 
529  subpatch.edge_v0.sub_edges_created_in_reverse_order = !v0_reversed;
532  subpatch.edge_u0.sub_edges_created_in_reverse_order = !u0_reversed;
533 
534  subpatch.edge_v0.indices_decrease_along_edge = v0_reversed;
535  subpatch.edge_u1.indices_decrease_along_edge = false;
536  subpatch.edge_v1.indices_decrease_along_edge = true;
537  subpatch.edge_u0.indices_decrease_along_edge = u0_reversed;
538 
539  /* Perform split. */
540  {
541  subpatch.edge_u0.T = T(subpatch.patch, subpatch.c00, subpatch.c10);
542  subpatch.edge_u1.T = T(subpatch.patch, subpatch.c01, subpatch.c11);
543  subpatch.edge_v0.T = T(subpatch.patch, subpatch.c00, subpatch.c01);
544  subpatch.edge_v1.T = T(subpatch.patch, subpatch.c10, subpatch.c11);
545 
546  resolve_edge_factors(subpatch);
547 
548  split(subpatch, 0);
549  }
550 
551  /* Update offsets after T is known from split. */
552  edge_u1->top = subpatch.edge_v0.edge;
553  edge_u1->stitch_top_offset = edge_u1->top->T * (v0_reversed ? -1 : 1);
554  edge_v1->top = subpatch.edge_u0.edge;
555  edge_v1->stitch_top_offset = edge_v1->top->T * (!u0_reversed ? -1 : 1);
556 
557  if (corner == 0) {
558  first_edge_v0 = subpatch.edge_v0.edge;
559  }
560 
561  if (prev_edge_u0) {
562  if (v0_reversed) {
563  subpatch.edge_v0.edge->stitch_offset = prev_edge_u0->T;
564  }
565  else {
566  prev_edge_u0->stitch_offset = subpatch.edge_v0.edge->T;
567  }
568 
569  int T = subpatch.edge_v0.edge->T + prev_edge_u0->T;
570  subpatch.edge_v0.edge->stitch_edge_T = T;
571  prev_edge_u0->stitch_edge_T = T;
572  }
573 
574  if (corner == face.num_corners - 1) {
575  if (v0_reversed) {
576  subpatch.edge_u0.edge->stitch_offset = first_edge_v0->T;
577  }
578  else {
579  first_edge_v0->stitch_offset = subpatch.edge_u0.edge->T;
580  }
581 
582  int T = first_edge_v0->T + subpatch.edge_u0.edge->T;
583  first_edge_v0->stitch_edge_T = T;
584  subpatch.edge_u0.edge->stitch_edge_T = T;
585  }
586 
587  prev_edge_u0 = subpatch.edge_u0.edge;
588  }
589 }
590 
592 {
593  int num_stitch_verts = 0;
594 
595  /* All patches are now split, and all T values known. */
596 
597  foreach (Edge &edge, edges) {
598  if (edge.second_vert_index < 0) {
599  edge.second_vert_index = alloc_verts(edge.T - 1);
600  }
601 
602  if (edge.is_stitch_edge) {
603  num_stitch_verts = max(num_stitch_verts,
604  max(edge.stitch_start_vert_index, edge.stitch_end_vert_index));
605  }
606  }
607 
608  num_stitch_verts += 1;
609 
610  /* Map of edge key to edge stitching vert offset. */
611  struct pair_hasher {
612  size_t operator()(const pair<int, int> &k) const
613  {
614  return hash_uint2(k.first, k.second);
615  }
616  };
617  typedef unordered_map<pair<int, int>, int, pair_hasher> edge_stitch_verts_map_t;
618  edge_stitch_verts_map_t edge_stitch_verts_map;
619 
620  foreach (Edge &edge, edges) {
621  if (edge.is_stitch_edge) {
622  if (edge.stitch_edge_T == 0) {
623  edge.stitch_edge_T = edge.T;
624  }
625 
626  if (edge_stitch_verts_map.find(edge.stitch_edge_key) == edge_stitch_verts_map.end()) {
627  edge_stitch_verts_map[edge.stitch_edge_key] = num_stitch_verts;
628  num_stitch_verts += edge.stitch_edge_T - 1;
629  }
630  }
631  }
632 
633  /* Set start and end indices for edges generated from a split. */
634  foreach (Edge &edge, edges) {
635  if (edge.start_vert_index < 0) {
636  /* Fix up offsets. */
637  if (edge.top_indices_decrease) {
638  edge.top_offset = edge.top->T - edge.top_offset;
639  }
640 
641  edge.start_vert_index = edge.top->get_vert_along_edge(edge.top_offset);
642  }
643 
644  if (edge.end_vert_index < 0) {
645  if (edge.bottom_indices_decrease) {
646  edge.bottom_offset = edge.bottom->T - edge.bottom_offset;
647  }
648 
649  edge.end_vert_index = edge.bottom->get_vert_along_edge(edge.bottom_offset);
650  }
651  }
652 
653  int vert_offset = params.mesh->verts.size();
654 
655  /* Add verts to stitching map. */
656  foreach (const Edge &edge, edges) {
657  if (edge.is_stitch_edge) {
658  int second_stitch_vert_index = edge_stitch_verts_map[edge.stitch_edge_key];
659 
660  for (int i = 0; i <= edge.T; i++) {
661  /* Get proper stitching key. */
662  int key;
663 
664  if (i == 0) {
665  key = edge.stitch_start_vert_index;
666  }
667  else if (i == edge.T) {
668  key = edge.stitch_end_vert_index;
669  }
670  else {
671  key = second_stitch_vert_index + i - 1 + edge.stitch_offset;
672  }
673 
675  if (i == 0) {
676  key = second_stitch_vert_index - 1 + edge.stitch_offset;
677  }
678  else if (i == edge.T) {
679  key = second_stitch_vert_index - 1 + edge.T;
680  }
681  }
682  else if (key < 0 && edge.top) { /* ngon spoke edge */
683  int s = edge_stitch_verts_map[edge.top->stitch_edge_key];
684  if (edge.stitch_top_offset >= 0) {
685  key = s - 1 + edge.stitch_top_offset;
686  }
687  else {
688  key = s - 1 + edge.top->stitch_edge_T + edge.stitch_top_offset;
689  }
690  }
691 
692  /* Get real vert index. */
693  int vert = edge.get_vert_along_edge(i) + vert_offset;
694 
695  /* Add to map */
696  if (params.mesh->vert_to_stitching_key_map.find(vert) ==
697  params.mesh->vert_to_stitching_key_map.end()) {
698  params.mesh->vert_to_stitching_key_map[vert] = key;
699  params.mesh->vert_stitching_map.insert({key, vert});
700  }
701  }
702  }
703  }
704 
705  /* Dice; TODO(mai): Move this out of split. */
706  QuadDice dice(params);
707 
708  int num_verts = num_alloced_verts;
709  int num_triangles = 0;
710 
711  for (size_t i = 0; i < subpatches.size(); i++) {
712  subpatches[i].inner_grid_vert_offset = num_verts;
713  num_verts += subpatches[i].calc_num_inner_verts();
714  num_triangles += subpatches[i].calc_num_triangles();
715  }
716 
717  dice.reserve(num_verts, num_triangles);
718 
719  for (size_t i = 0; i < subpatches.size(); i++) {
720  Subpatch &sub = subpatches[i];
721 
722  sub.edge_u0.T = max(sub.edge_u0.T, 1);
723  sub.edge_u1.T = max(sub.edge_u1.T, 1);
724  sub.edge_v0.T = max(sub.edge_v0.T, 1);
725  sub.edge_v1.T = max(sub.edge_v1.T, 1);
726 
727  dice.dice(sub);
728  }
729 
730  /* Cleanup */
731  subpatches.clear();
732  edges.clear();
733 }
734 
typedef float(TangentPoint)[2]
void swap(T &a, T &b)
Definition: Common.h:19
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
ATTR_WARN_UNUSED_RESULT const BMVert * v
SIMD_FORCE_INLINE btVector3 operator()(const btVector3 &x) const
Return the transform of the vector.
Definition: btTransform.h:90
void post_split()
Definition: subd/split.cpp:591
void split_patches(Patch *patches, size_t patches_byte_stride)
Definition: subd/split.cpp:327
void split_quad(const Mesh::SubdFace &face, Patch *patch)
Definition: subd/split.cpp:386
void split_ngon(const Mesh::SubdFace &face, Patch *patches, size_t patches_byte_stride)
Definition: subd/split.cpp:467
DiagSplit(const SubdParams &params)
Definition: subd/split.cpp:25
Edge * alloc_edge()
Definition: subd/split.cpp:321
void reserve(int num_verts, int num_triangles)
Definition: dice.cpp:28
bool from_ngon
Definition: subd/patch.h:24
virtual void eval(float3 *P, float3 *dPdu, float3 *dPdv, float3 *N, float u, float v)=0
Definition: dice.h:69
void dice(Subpatch &sub)
Definition: dice.cpp:240
edge_t edges[4]
Definition: subpatch.h:50
float2 c11
Definition: subpatch.h:44
edge_t edge_v1
Definition: subpatch.h:52
edge_t edge_u0
Definition: subpatch.h:52
float2 c01
Definition: subpatch.h:44
class Patch * patch
Definition: subpatch.h:16
edge_t edge_u1
Definition: subpatch.h:52
edge_t edge_v0
Definition: subpatch.h:52
float2 c10
Definition: subpatch.h:44
float2 c00
Definition: subpatch.h:44
#define CCL_NAMESPACE_END
Definition: cuda/compat.h:9
SyclQueue void void size_t num_bytes void
int len
Definition: draw_manager.c:108
ccl_device_inline uint hash_uint2(uint kx, uint ky)
Definition: hash.h:70
uiWidgetBaseParameters params[MAX_WIDGET_BASE_BATCH]
CCL_NAMESPACE_END CCL_NAMESPACE_BEGIN ccl_device_inline float3 transform_point(ccl_private const Transform *t, const float3 a)
ccl_device_inline float2 interp(const float2 &a, const float2 &b, float t)
Definition: math_float2.h:232
static float P(float k)
Definition: math_interp.c:25
#define T
#define L
#define ceilf(x)
Definition: metal/compat.h:225
#define floorf(x)
Definition: metal/compat.h:224
static unsigned a[3]
Definition: RandGen.cpp:78
void split(const std::string &s, const char delim, std::vector< std::string > &tokens)
Definition: abc_util.cc:92
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
#define I
#define min(a, b)
Definition: sort.c:35
float world_to_raster_size(float3 P)
int stitch_offset
Definition: subpatch.h:142
int T
Definition: subpatch.h:119
int stitch_end_vert_index
Definition: subpatch.h:145
int start_vert_index
Definition: subpatch.h:127
Edge * top
Definition: subpatch.h:122
int stitch_top_offset
Definition: subpatch.h:143
pair< int, int > stitch_edge_key
Definition: subpatch.h:138
bool is_stitch_edge
Definition: subpatch.h:134
int stitch_edge_T
Definition: subpatch.h:141
int stitch_start_vert_index
Definition: subpatch.h:144
int end_vert_index
Definition: subpatch.h:128
bool is_quad()
Definition: scene/mesh.h:92
size_t get_num_subd_faces() const
Definition: scene/mesh.h:232
float size[3]
SubdFace get_subd_face(size_t index) const
Definition: scene/mesh.cpp:390
int max_level
Definition: dice.h:30
Mesh * mesh
Definition: dice.h:24
Camera * camera
Definition: dice.h:31
Transform objecttoworld
Definition: dice.h:32
int split_threshold
Definition: dice.h:28
float dicing_rate
Definition: dice.h:29
int test_steps
Definition: dice.h:27
bool sub_edges_created_in_reverse_order
Definition: subpatch.h:24
struct Edge * edge
Definition: subpatch.h:26
bool indices_decrease_along_edge
Definition: subpatch.h:23
float x
Definition: types_float2.h:15
float y
Definition: types_float2.h:15
#define DSPLIT_NON_UNIFORM
Definition: subd/split.cpp:21
static Edge * create_split_edge_from_corner(DiagSplit *split, const Mesh *mesh, const Mesh::SubdFace &face, int corner, int side, bool &reversed, int v0, int v1, int vc)
Definition: subd/split.cpp:421
#define STITCH_NGON_CENTER_VERT_INDEX_OFFSET
Definition: subd/split.cpp:22
static Edge * create_edge_from_corner(DiagSplit *split, const Mesh *mesh, const Mesh::SubdFace &face, int corner, bool &reversed, int v0, int v1)
Definition: subd/split.cpp:354
static void order_float2(float2 &a, float2 &b)
Definition: subd/split.cpp:40
#define STITCH_NGON_SPLIT_EDGE_CENTER_VERT_TAG
Definition: subd/split.cpp:23
float max
ccl_device_inline int mod(int x, int m)
Definition: util/math.h:490