c3f9bc3400cddef3f0cd22e39fa4d3d7b8a75444
[blender.git] / source / blender / blenkernel / intern / subdiv_foreach.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2018 by Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #include "BKE_subdiv_foreach.h"
25
26 #include "atomic_ops.h"
27
28 #include "DNA_mesh_types.h"
29 #include "DNA_meshdata_types.h"
30 #include "DNA_key_types.h"
31
32 #include "BLI_bitmap.h"
33 #include "BLI_task.h"
34
35 #include "BKE_customdata.h"
36 #include "BKE_mesh.h"
37 #include "BKE_key.h"
38 #include "BKE_subdiv.h"
39 #include "BKE_subdiv_mesh.h"
40
41 #include "MEM_guardedalloc.h"
42
43 /* =============================================================================
44  * General helpers.
45  */
46
47 /* Number of ptex faces for a given polygon. */
48 BLI_INLINE int num_ptex_faces_per_poly_get(const MPoly *poly)
49 {
50   return (poly->totloop == 4) ? 1 : poly->totloop;
51 }
52
53 BLI_INLINE int num_edges_per_ptex_face_get(const int resolution)
54 {
55   return 2 * (resolution - 1) * resolution;
56 }
57
58 BLI_INLINE int num_inner_edges_per_ptex_face_get(const int resolution)
59 {
60   if (resolution < 2) {
61     return 0;
62   }
63   return (resolution - 2) * resolution + (resolution - 1) * (resolution - 1);
64 }
65
66 /* Number of subdivision polygons per ptex face. */
67 BLI_INLINE int num_polys_per_ptex_get(const int resolution)
68 {
69   return (resolution - 1) * (resolution - 1);
70 }
71
72 /* Subdivision resolution per given polygon's ptex faces. */
73 BLI_INLINE int ptex_face_resolution_get(const MPoly *poly, int resolution)
74 {
75   return (poly->totloop == 4) ? (resolution) : ((resolution >> 1) + 1);
76 }
77
78 /* =============================================================================
79  * Context which is passed to all threaded tasks.
80  */
81
82 typedef struct SubdivForeachTaskContext {
83   const Mesh *coarse_mesh;
84   const SubdivToMeshSettings *settings;
85   /* Callbacks. */
86   const SubdivForeachContext *foreach_context;
87   /* Counters of geometry in subdivided mesh, initialized as a part of
88    * offsets calculation.
89    */
90   int num_subdiv_vertices;
91   int num_subdiv_edges;
92   int num_subdiv_loops;
93   int num_subdiv_polygons;
94   /* Offsets of various geometry in the subdivision mesh arrays. */
95   int vertices_corner_offset;
96   int vertices_edge_offset;
97   int vertices_inner_offset;
98   int edge_boundary_offset;
99   int edge_inner_offset;
100   /* Indexed by coarse polygon index, indicates offset in subdivided mesh
101    * vertices, edges and polygons arrays, where first element of the poly
102    * begins.
103    */
104   int *subdiv_vertex_offset;
105   int *subdiv_edge_offset;
106   int *subdiv_polygon_offset;
107   /* Indexed by base face index, element indicates total number of ptex faces
108    * created for preceding base faces.
109    */
110   int *face_ptex_offset;
111   /* Bitmap indicating whether vertex was used already or not.
112    * - During patch evaluation indicates whether coarse vertex was already
113    *   evaluated and its position on limit is already known.
114    */
115   BLI_bitmap *coarse_vertices_used_map;
116   /* Bitmap indicating whether edge was used already or not. This includes:
117    * - During context initialization it indicates whether subdivided vertices
118    *   for corresponding edge were already calculated or not.
119    * - During patch evaluation it indicates whether vertices along this edge
120    *   were already evaluated.
121    */
122   BLI_bitmap *coarse_edges_used_map;
123 } SubdivForeachTaskContext;
124
125 /* =============================================================================
126  * Threading helpers.
127  */
128
129 static void *subdiv_foreach_tls_alloc(SubdivForeachTaskContext *ctx)
130 {
131   const SubdivForeachContext *foreach_context = ctx->foreach_context;
132   void *tls = NULL;
133   if (foreach_context->user_data_tls_size != 0) {
134     tls = MEM_mallocN(foreach_context->user_data_tls_size, "tls");
135     memcpy(tls, foreach_context->user_data_tls, foreach_context->user_data_tls_size);
136   }
137   return tls;
138 }
139
140 static void subdiv_foreach_tls_free(SubdivForeachTaskContext *ctx, void *tls)
141 {
142   if (tls == NULL) {
143     return;
144   }
145   if (ctx->foreach_context != NULL) {
146     ctx->foreach_context->user_data_tls_free(tls);
147   }
148   MEM_freeN(tls);
149 }
150
151 /* =============================================================================
152  * Initialization.
153  */
154
155 /* NOTE: Expects edge map to be zeroed. */
156 static void subdiv_foreach_ctx_count(SubdivForeachTaskContext *ctx)
157 {
158   /* Reset counters. */
159   ctx->num_subdiv_vertices = 0;
160   ctx->num_subdiv_edges = 0;
161   ctx->num_subdiv_loops = 0;
162   ctx->num_subdiv_polygons = 0;
163   /* Static geometry counters. */
164   const int resolution = ctx->settings->resolution;
165   const int no_quad_patch_resolution = ((resolution >> 1) + 1);
166   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
167   const int num_inner_vertices_per_quad = (resolution - 2) * (resolution - 2);
168   const int num_inner_vertices_per_noquad_patch = (no_quad_patch_resolution - 2) *
169                                                   (no_quad_patch_resolution - 2);
170   const Mesh *coarse_mesh = ctx->coarse_mesh;
171   const MLoop *coarse_mloop = coarse_mesh->mloop;
172   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
173   ctx->num_subdiv_vertices = coarse_mesh->totvert;
174   ctx->num_subdiv_edges = coarse_mesh->totedge * (num_subdiv_vertices_per_coarse_edge + 1);
175   /* Calculate extra vertices and edges createdd by non-loose geometry. */
176   for (int poly_index = 0; poly_index < coarse_mesh->totpoly; poly_index++) {
177     const MPoly *coarse_poly = &coarse_mpoly[poly_index];
178     const int num_ptex_faces_per_poly = num_ptex_faces_per_poly_get(coarse_poly);
179     for (int corner = 0; corner < coarse_poly->totloop; corner++) {
180       const MLoop *loop = &coarse_mloop[coarse_poly->loopstart + corner];
181       const bool is_edge_used = BLI_BITMAP_TEST_BOOL(ctx->coarse_edges_used_map, loop->e);
182       /* Edges which aren't counted yet. */
183       if (!is_edge_used) {
184         BLI_BITMAP_ENABLE(ctx->coarse_edges_used_map, loop->e);
185         ctx->num_subdiv_vertices += num_subdiv_vertices_per_coarse_edge;
186       }
187     }
188     /* Inner vertices of polygon. */
189     if (num_ptex_faces_per_poly == 1) {
190       ctx->num_subdiv_vertices += num_inner_vertices_per_quad;
191       ctx->num_subdiv_edges += num_edges_per_ptex_face_get(resolution - 2) +
192                                4 * num_subdiv_vertices_per_coarse_edge;
193       ctx->num_subdiv_polygons += num_polys_per_ptex_get(resolution);
194     }
195     else {
196       ctx->num_subdiv_vertices += 1 + num_ptex_faces_per_poly * (no_quad_patch_resolution - 2) +
197                                   num_ptex_faces_per_poly * num_inner_vertices_per_noquad_patch;
198       ctx->num_subdiv_edges += num_ptex_faces_per_poly *
199                                (num_inner_edges_per_ptex_face_get(no_quad_patch_resolution - 1) +
200                                 (no_quad_patch_resolution - 2) +
201                                 num_subdiv_vertices_per_coarse_edge);
202       if (no_quad_patch_resolution >= 3) {
203         ctx->num_subdiv_edges += coarse_poly->totloop;
204       }
205       ctx->num_subdiv_polygons += num_ptex_faces_per_poly *
206                                   num_polys_per_ptex_get(no_quad_patch_resolution);
207     }
208   }
209   /* Calculate extra vertices createdd by loose edges. */
210   for (int edge_index = 0; edge_index < coarse_mesh->totedge; edge_index++) {
211     if (!BLI_BITMAP_TEST_BOOL(ctx->coarse_edges_used_map, edge_index)) {
212       ctx->num_subdiv_vertices += num_subdiv_vertices_per_coarse_edge;
213     }
214   }
215   ctx->num_subdiv_loops = ctx->num_subdiv_polygons * 4;
216 }
217
218 static void subdiv_foreach_ctx_init_offsets(SubdivForeachTaskContext *ctx)
219 {
220   const Mesh *coarse_mesh = ctx->coarse_mesh;
221   const int resolution = ctx->settings->resolution;
222   const int resolution_2 = resolution - 2;
223   const int resolution_2_squared = resolution_2 * resolution_2;
224   const int no_quad_patch_resolution = ((resolution >> 1) + 1);
225   const int num_irregular_vertices_per_patch = (no_quad_patch_resolution - 2) *
226                                                (no_quad_patch_resolution - 1);
227   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
228   const int num_subdiv_edges_per_coarse_edge = resolution - 1;
229   /* Constant offsets in arrays. */
230   ctx->vertices_corner_offset = 0;
231   ctx->vertices_edge_offset = coarse_mesh->totvert;
232   ctx->vertices_inner_offset = ctx->vertices_edge_offset +
233                                coarse_mesh->totedge * num_subdiv_vertices_per_coarse_edge;
234   ctx->edge_boundary_offset = 0;
235   ctx->edge_inner_offset = ctx->edge_boundary_offset +
236                            coarse_mesh->totedge * num_subdiv_edges_per_coarse_edge;
237   /* "Indexed" offsets. */
238   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
239   int vertex_offset = 0;
240   int edge_offset = 0;
241   int polygon_offset = 0;
242   for (int poly_index = 0; poly_index < coarse_mesh->totpoly; poly_index++) {
243     const MPoly *coarse_poly = &coarse_mpoly[poly_index];
244     const int num_ptex_faces_per_poly = num_ptex_faces_per_poly_get(coarse_poly);
245     ctx->subdiv_vertex_offset[poly_index] = vertex_offset;
246     ctx->subdiv_edge_offset[poly_index] = edge_offset;
247     ctx->subdiv_polygon_offset[poly_index] = polygon_offset;
248     if (num_ptex_faces_per_poly == 1) {
249       vertex_offset += resolution_2_squared;
250       edge_offset += num_edges_per_ptex_face_get(resolution - 2) +
251                      4 * num_subdiv_vertices_per_coarse_edge;
252       polygon_offset += num_polys_per_ptex_get(resolution);
253     }
254     else {
255       vertex_offset += 1 + num_ptex_faces_per_poly * num_irregular_vertices_per_patch;
256       edge_offset += num_ptex_faces_per_poly *
257                      (num_inner_edges_per_ptex_face_get(no_quad_patch_resolution - 1) +
258                       (no_quad_patch_resolution - 2) + num_subdiv_vertices_per_coarse_edge);
259       if (no_quad_patch_resolution >= 3) {
260         edge_offset += coarse_poly->totloop;
261       }
262       polygon_offset += num_ptex_faces_per_poly * num_polys_per_ptex_get(no_quad_patch_resolution);
263     }
264   }
265 }
266
267 static void subdiv_foreach_ctx_init(Subdiv *subdiv, SubdivForeachTaskContext *ctx)
268 {
269   const Mesh *coarse_mesh = ctx->coarse_mesh;
270   /* Allocate maps and offsets. */
271   ctx->coarse_vertices_used_map = BLI_BITMAP_NEW(coarse_mesh->totvert, "vertices used map");
272   ctx->coarse_edges_used_map = BLI_BITMAP_NEW(coarse_mesh->totedge, "edges used map");
273   ctx->subdiv_vertex_offset = MEM_malloc_arrayN(
274       coarse_mesh->totpoly, sizeof(*ctx->subdiv_vertex_offset), "vertex_offset");
275   ctx->subdiv_edge_offset = MEM_malloc_arrayN(
276       coarse_mesh->totpoly, sizeof(*ctx->subdiv_edge_offset), "subdiv_edge_offset");
277   ctx->subdiv_polygon_offset = MEM_malloc_arrayN(
278       coarse_mesh->totpoly, sizeof(*ctx->subdiv_polygon_offset), "subdiv_edge_offset");
279   /* Initialize all offsets. */
280   subdiv_foreach_ctx_init_offsets(ctx);
281   /* Calculate number of geometry in the result subdivision mesh. */
282   subdiv_foreach_ctx_count(ctx);
283   /* Re-set maps which were used at this step. */
284   BLI_bitmap_set_all(ctx->coarse_edges_used_map, false, coarse_mesh->totedge);
285   ctx->face_ptex_offset = BKE_subdiv_face_ptex_offset_get(subdiv);
286 }
287
288 static void subdiv_foreach_ctx_free(SubdivForeachTaskContext *ctx)
289 {
290   MEM_freeN(ctx->coarse_vertices_used_map);
291   MEM_freeN(ctx->coarse_edges_used_map);
292   MEM_freeN(ctx->subdiv_vertex_offset);
293   MEM_freeN(ctx->subdiv_edge_offset);
294   MEM_freeN(ctx->subdiv_polygon_offset);
295 }
296
297 /* =============================================================================
298  * Vertex traversal process.
299  */
300
301 /* Traversal of corner vertices. They are coming from coarse vertices. */
302
303 static void subdiv_foreach_corner_vertices_regular_do(
304     SubdivForeachTaskContext *ctx,
305     void *tls,
306     const MPoly *coarse_poly,
307     SubdivForeachVertexFromCornerCb vertex_corner,
308     bool check_usage)
309 {
310   const float weights[4][2] = {{0.0f, 0.0f}, {1.0f, 0.0f}, {1.0f, 1.0f}, {0.0f, 1.0f}};
311   const Mesh *coarse_mesh = ctx->coarse_mesh;
312   const MLoop *coarse_mloop = coarse_mesh->mloop;
313   const int coarse_poly_index = coarse_poly - coarse_mesh->mpoly;
314   const int ptex_face_index = ctx->face_ptex_offset[coarse_poly_index];
315   for (int corner = 0; corner < coarse_poly->totloop; corner++) {
316     const MLoop *coarse_loop = &coarse_mloop[coarse_poly->loopstart + corner];
317     if (check_usage &&
318         BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_vertices_used_map, coarse_loop->v)) {
319       continue;
320     }
321     const int coarse_vertex_index = coarse_loop->v;
322     const int subdiv_vertex_index = ctx->vertices_corner_offset + coarse_vertex_index;
323     const float u = weights[corner][0];
324     const float v = weights[corner][1];
325     vertex_corner(ctx->foreach_context,
326                   tls,
327                   ptex_face_index,
328                   u,
329                   v,
330                   coarse_vertex_index,
331                   coarse_poly_index,
332                   0,
333                   subdiv_vertex_index);
334   }
335 }
336
337 static void subdiv_foreach_corner_vertices_regular(SubdivForeachTaskContext *ctx,
338                                                    void *tls,
339                                                    const MPoly *coarse_poly)
340 {
341   subdiv_foreach_corner_vertices_regular_do(
342       ctx, tls, coarse_poly, ctx->foreach_context->vertex_corner, true);
343 }
344
345 static void subdiv_foreach_corner_vertices_special_do(
346     SubdivForeachTaskContext *ctx,
347     void *tls,
348     const MPoly *coarse_poly,
349     SubdivForeachVertexFromCornerCb vertex_corner,
350     bool check_usage)
351 {
352   const Mesh *coarse_mesh = ctx->coarse_mesh;
353   const MLoop *coarse_mloop = coarse_mesh->mloop;
354   const int coarse_poly_index = coarse_poly - coarse_mesh->mpoly;
355   int ptex_face_index = ctx->face_ptex_offset[coarse_poly_index];
356   for (int corner = 0; corner < coarse_poly->totloop; corner++, ptex_face_index++) {
357     const MLoop *coarse_loop = &coarse_mloop[coarse_poly->loopstart + corner];
358     if (check_usage &&
359         BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_vertices_used_map, coarse_loop->v)) {
360       continue;
361     }
362     const int coarse_vertex_index = coarse_loop->v;
363     const int subdiv_vertex_index = ctx->vertices_corner_offset + coarse_vertex_index;
364     vertex_corner(ctx->foreach_context,
365                   tls,
366                   ptex_face_index,
367                   0.0f,
368                   0.0f,
369                   coarse_vertex_index,
370                   coarse_poly_index,
371                   corner,
372                   subdiv_vertex_index);
373   }
374 }
375
376 static void subdiv_foreach_corner_vertices_special(SubdivForeachTaskContext *ctx,
377                                                    void *tls,
378                                                    const MPoly *coarse_poly)
379 {
380   subdiv_foreach_corner_vertices_special_do(
381       ctx, tls, coarse_poly, ctx->foreach_context->vertex_corner, true);
382 }
383
384 static void subdiv_foreach_corner_vertices(SubdivForeachTaskContext *ctx,
385                                            void *tls,
386                                            const MPoly *coarse_poly)
387 {
388   if (coarse_poly->totloop == 4) {
389     subdiv_foreach_corner_vertices_regular(ctx, tls, coarse_poly);
390   }
391   else {
392     subdiv_foreach_corner_vertices_special(ctx, tls, coarse_poly);
393   }
394 }
395
396 static void subdiv_foreach_every_corner_vertices_regular(SubdivForeachTaskContext *ctx,
397                                                          void *tls,
398                                                          const MPoly *coarse_poly)
399 {
400   subdiv_foreach_corner_vertices_regular_do(
401       ctx, tls, coarse_poly, ctx->foreach_context->vertex_every_corner, false);
402 }
403
404 static void subdiv_foreach_every_corner_vertices_special(SubdivForeachTaskContext *ctx,
405                                                          void *tls,
406                                                          const MPoly *coarse_poly)
407 {
408   subdiv_foreach_corner_vertices_special_do(
409       ctx, tls, coarse_poly, ctx->foreach_context->vertex_every_corner, false);
410 }
411
412 static void subdiv_foreach_every_corner_vertices(SubdivForeachTaskContext *ctx, void *tls)
413 {
414   if (ctx->foreach_context->vertex_every_corner == NULL) {
415     return;
416   }
417   const Mesh *coarse_mesh = ctx->coarse_mesh;
418   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
419   for (int poly_index = 0; poly_index < coarse_mesh->totpoly; poly_index++) {
420     const MPoly *coarse_poly = &coarse_mpoly[poly_index];
421     if (coarse_poly->totloop == 4) {
422       subdiv_foreach_every_corner_vertices_regular(ctx, tls, coarse_poly);
423     }
424     else {
425       subdiv_foreach_every_corner_vertices_special(ctx, tls, coarse_poly);
426     }
427   }
428 }
429
430 /* Traverse of edge vertices. They are coming from coarse edges. */
431
432 static void subdiv_foreach_edge_vertices_regular_do(SubdivForeachTaskContext *ctx,
433                                                     void *tls,
434                                                     const MPoly *coarse_poly,
435                                                     SubdivForeachVertexFromEdgeCb vertex_edge,
436                                                     bool check_usage)
437 {
438   const int resolution = ctx->settings->resolution;
439   const int resolution_1 = resolution - 1;
440   const float inv_resolution_1 = 1.0f / (float)resolution_1;
441   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
442   const Mesh *coarse_mesh = ctx->coarse_mesh;
443   const MEdge *coarse_medge = coarse_mesh->medge;
444   const MLoop *coarse_mloop = coarse_mesh->mloop;
445   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
446   const int coarse_poly_index = coarse_poly - coarse_mpoly;
447   const int poly_index = coarse_poly - coarse_mesh->mpoly;
448   const int ptex_face_index = ctx->face_ptex_offset[poly_index];
449   for (int corner = 0; corner < coarse_poly->totloop; corner++) {
450     const MLoop *coarse_loop = &coarse_mloop[coarse_poly->loopstart + corner];
451     const int coarse_edge_index = coarse_loop->e;
452     if (check_usage &&
453         BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_edges_used_map, coarse_edge_index)) {
454       continue;
455     }
456     const MEdge *coarse_edge = &coarse_medge[coarse_edge_index];
457     const bool flip = (coarse_edge->v2 == coarse_loop->v);
458     int subdiv_vertex_index = ctx->vertices_edge_offset +
459                               coarse_edge_index * num_subdiv_vertices_per_coarse_edge;
460     for (int vertex_index = 0; vertex_index < num_subdiv_vertices_per_coarse_edge;
461          vertex_index++, subdiv_vertex_index++) {
462       float fac = (vertex_index + 1) * inv_resolution_1;
463       if (flip) {
464         fac = 1.0f - fac;
465       }
466       if (corner >= 2) {
467         fac = 1.0f - fac;
468       }
469       float u, v;
470       if ((corner & 1) == 0) {
471         u = fac;
472         v = (corner == 2) ? 1.0f : 0.0f;
473       }
474       else {
475         u = (corner == 1) ? 1.0f : 0.0f;
476         v = fac;
477       }
478       vertex_edge(ctx->foreach_context,
479                   tls,
480                   ptex_face_index,
481                   u,
482                   v,
483                   coarse_edge_index,
484                   coarse_poly_index,
485                   0,
486                   subdiv_vertex_index);
487     }
488   }
489 }
490
491 static void subdiv_foreach_edge_vertices_regular(SubdivForeachTaskContext *ctx,
492                                                  void *tls,
493                                                  const MPoly *coarse_poly)
494 {
495   subdiv_foreach_edge_vertices_regular_do(
496       ctx, tls, coarse_poly, ctx->foreach_context->vertex_edge, true);
497 }
498
499 static void subdiv_foreach_edge_vertices_special_do(SubdivForeachTaskContext *ctx,
500                                                     void *tls,
501                                                     const MPoly *coarse_poly,
502                                                     SubdivForeachVertexFromEdgeCb vertex_edge,
503                                                     bool check_usage)
504 {
505   const int resolution = ctx->settings->resolution;
506   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
507   const int num_vertices_per_ptex_edge = ((resolution >> 1) + 1);
508   const float inv_ptex_resolution_1 = 1.0f / (float)(num_vertices_per_ptex_edge - 1);
509   const Mesh *coarse_mesh = ctx->coarse_mesh;
510   const MEdge *coarse_medge = coarse_mesh->medge;
511   const MLoop *coarse_mloop = coarse_mesh->mloop;
512   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
513   const int coarse_poly_index = coarse_poly - coarse_mpoly;
514   const int poly_index = coarse_poly - coarse_mesh->mpoly;
515   const int ptex_face_start_index = ctx->face_ptex_offset[poly_index];
516   int ptex_face_index = ptex_face_start_index;
517   for (int corner = 0; corner < coarse_poly->totloop; corner++, ptex_face_index++) {
518     const MLoop *coarse_loop = &coarse_mloop[coarse_poly->loopstart + corner];
519     const int coarse_edge_index = coarse_loop->e;
520     if (check_usage &&
521         BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_edges_used_map, coarse_edge_index)) {
522       continue;
523     }
524     const MEdge *coarse_edge = &coarse_medge[coarse_edge_index];
525     const bool flip = (coarse_edge->v2 == coarse_loop->v);
526     int subdiv_vertex_index = ctx->vertices_edge_offset +
527                               coarse_edge_index * num_subdiv_vertices_per_coarse_edge;
528     int veretx_delta = 1;
529     if (flip) {
530       subdiv_vertex_index += num_subdiv_vertices_per_coarse_edge - 1;
531       veretx_delta = -1;
532     }
533     for (int vertex_index = 1; vertex_index < num_vertices_per_ptex_edge;
534          vertex_index++, subdiv_vertex_index += veretx_delta) {
535       const float u = vertex_index * inv_ptex_resolution_1;
536       vertex_edge(ctx->foreach_context,
537                   tls,
538                   ptex_face_index,
539                   u,
540                   0.0f,
541                   coarse_edge_index,
542                   coarse_poly_index,
543                   corner,
544                   subdiv_vertex_index);
545     }
546     const int next_corner = (corner + 1) % coarse_poly->totloop;
547     const int next_ptex_face_index = ptex_face_start_index + next_corner;
548     for (int vertex_index = 1; vertex_index < num_vertices_per_ptex_edge - 1;
549          vertex_index++, subdiv_vertex_index += veretx_delta) {
550       const float v = 1.0f - vertex_index * inv_ptex_resolution_1;
551       vertex_edge(ctx->foreach_context,
552                   tls,
553                   next_ptex_face_index,
554                   0.0f,
555                   v,
556                   coarse_edge_index,
557                   coarse_poly_index,
558                   next_corner,
559                   subdiv_vertex_index);
560     }
561   }
562 }
563
564 static void subdiv_foreach_edge_vertices_special(SubdivForeachTaskContext *ctx,
565                                                  void *tls,
566                                                  const MPoly *coarse_poly)
567 {
568   subdiv_foreach_edge_vertices_special_do(
569       ctx, tls, coarse_poly, ctx->foreach_context->vertex_edge, true);
570 }
571
572 static void subdiv_foreach_edge_vertices(SubdivForeachTaskContext *ctx,
573                                          void *tls,
574                                          const MPoly *coarse_poly)
575 {
576   if (coarse_poly->totloop == 4) {
577     subdiv_foreach_edge_vertices_regular(ctx, tls, coarse_poly);
578   }
579   else {
580     subdiv_foreach_edge_vertices_special(ctx, tls, coarse_poly);
581   }
582 }
583
584 static void subdiv_foreach_every_edge_vertices_regular(SubdivForeachTaskContext *ctx,
585                                                        void *tls,
586                                                        const MPoly *coarse_poly)
587 {
588   subdiv_foreach_edge_vertices_regular_do(
589       ctx, tls, coarse_poly, ctx->foreach_context->vertex_every_edge, false);
590 }
591
592 static void subdiv_foreach_every_edge_vertices_special(SubdivForeachTaskContext *ctx,
593                                                        void *tls,
594                                                        const MPoly *coarse_poly)
595 {
596   subdiv_foreach_edge_vertices_special_do(
597       ctx, tls, coarse_poly, ctx->foreach_context->vertex_every_edge, false);
598 }
599
600 static void subdiv_foreach_every_edge_vertices(SubdivForeachTaskContext *ctx, void *tls)
601 {
602   if (ctx->foreach_context->vertex_every_edge == NULL) {
603     return;
604   }
605   const Mesh *coarse_mesh = ctx->coarse_mesh;
606   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
607   for (int poly_index = 0; poly_index < coarse_mesh->totpoly; poly_index++) {
608     const MPoly *coarse_poly = &coarse_mpoly[poly_index];
609     if (coarse_poly->totloop == 4) {
610       subdiv_foreach_every_edge_vertices_regular(ctx, tls, coarse_poly);
611     }
612     else {
613       subdiv_foreach_every_edge_vertices_special(ctx, tls, coarse_poly);
614     }
615   }
616 }
617
618 /* Traversal of inner vertices, they are coming from ptex patches. */
619
620 static void subdiv_foreach_inner_vertices_regular(SubdivForeachTaskContext *ctx,
621                                                   void *tls,
622                                                   const MPoly *coarse_poly)
623 {
624   const int resolution = ctx->settings->resolution;
625   const float inv_resolution_1 = 1.0f / (float)(resolution - 1);
626   const Mesh *coarse_mesh = ctx->coarse_mesh;
627   const int coarse_poly_index = coarse_poly - coarse_mesh->mpoly;
628   const int ptex_face_index = ctx->face_ptex_offset[coarse_poly_index];
629   const int start_vertex_index = ctx->subdiv_vertex_offset[coarse_poly_index];
630   int subdiv_vertex_index = ctx->vertices_inner_offset + start_vertex_index;
631   for (int y = 1; y < resolution - 1; y++) {
632     const float v = y * inv_resolution_1;
633     for (int x = 1; x < resolution - 1; x++, subdiv_vertex_index++) {
634       const float u = x * inv_resolution_1;
635       ctx->foreach_context->vertex_inner(ctx->foreach_context,
636                                          tls,
637                                          ptex_face_index,
638                                          u,
639                                          v,
640                                          coarse_poly_index,
641                                          0,
642                                          subdiv_vertex_index);
643     }
644   }
645 }
646
647 static void subdiv_foreach_inner_vertices_special(SubdivForeachTaskContext *ctx,
648                                                   void *tls,
649                                                   const MPoly *coarse_poly)
650 {
651   const int resolution = ctx->settings->resolution;
652   const int ptex_face_resolution = ptex_face_resolution_get(coarse_poly, resolution);
653   const float inv_ptex_face_resolution_1 = 1.0f / (float)(ptex_face_resolution - 1);
654   const Mesh *coarse_mesh = ctx->coarse_mesh;
655   const int coarse_poly_index = coarse_poly - coarse_mesh->mpoly;
656   int ptex_face_index = ctx->face_ptex_offset[coarse_poly_index];
657   const int start_vertex_index = ctx->subdiv_vertex_offset[coarse_poly_index];
658   int subdiv_vertex_index = ctx->vertices_inner_offset + start_vertex_index;
659   ctx->foreach_context->vertex_inner(ctx->foreach_context,
660                                      tls,
661                                      ptex_face_index,
662                                      1.0f,
663                                      1.0f,
664                                      coarse_poly_index,
665                                      0,
666                                      subdiv_vertex_index);
667   subdiv_vertex_index++;
668   for (int corner = 0; corner < coarse_poly->totloop; corner++, ptex_face_index++) {
669     for (int y = 1; y < ptex_face_resolution - 1; y++) {
670       const float v = y * inv_ptex_face_resolution_1;
671       for (int x = 1; x < ptex_face_resolution; x++, subdiv_vertex_index++) {
672         const float u = x * inv_ptex_face_resolution_1;
673         ctx->foreach_context->vertex_inner(ctx->foreach_context,
674                                            tls,
675                                            ptex_face_index,
676                                            u,
677                                            v,
678                                            coarse_poly_index,
679                                            corner,
680                                            subdiv_vertex_index);
681       }
682     }
683   }
684 }
685
686 static void subdiv_foreach_inner_vertices(SubdivForeachTaskContext *ctx,
687                                           void *tls,
688                                           const MPoly *coarse_poly)
689 {
690   if (coarse_poly->totloop == 4) {
691     subdiv_foreach_inner_vertices_regular(ctx, tls, coarse_poly);
692   }
693   else {
694     subdiv_foreach_inner_vertices_special(ctx, tls, coarse_poly);
695   }
696 }
697
698 /* Traverse all vertices which are emitted from given coarse polygon. */
699 static void subdiv_foreach_vertices(SubdivForeachTaskContext *ctx, void *tls, const int poly_index)
700 {
701   const Mesh *coarse_mesh = ctx->coarse_mesh;
702   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
703   const MPoly *coarse_poly = &coarse_mpoly[poly_index];
704   if (ctx->foreach_context->vertex_inner != NULL) {
705     subdiv_foreach_inner_vertices(ctx, tls, coarse_poly);
706   }
707 }
708
709 /* =============================================================================
710  * Edge traversal process.
711  */
712
713 /* TODO(sergey): Coarse edge are always NONE, consider getting rid of it. */
714 static int subdiv_foreach_edges_row(SubdivForeachTaskContext *ctx,
715                                     void *tls,
716                                     const int coarse_edge_index,
717                                     const int start_subdiv_edge_index,
718                                     const int start_vertex_index,
719                                     const int num_edges_per_row)
720 {
721   int subdiv_edge_index = start_subdiv_edge_index;
722   int vertex_index = start_vertex_index;
723   for (int edge_index = 0; edge_index < num_edges_per_row - 1; edge_index++, subdiv_edge_index++) {
724     const int v1 = vertex_index;
725     const int v2 = vertex_index + 1;
726     ctx->foreach_context->edge(
727         ctx->foreach_context, tls, coarse_edge_index, subdiv_edge_index, v1, v2);
728     vertex_index += 1;
729   }
730   return subdiv_edge_index;
731 }
732
733 /* TODO(sergey): Coarse edges are always NONE, consider getting rid of them. */
734 static int subdiv_foreach_edges_column(SubdivForeachTaskContext *ctx,
735                                        void *tls,
736                                        const int coarse_start_edge_index,
737                                        const int coarse_end_edge_index,
738                                        const int start_subdiv_edge_index,
739                                        const int start_vertex_index,
740                                        const int num_edges_per_row)
741 {
742   int subdiv_edge_index = start_subdiv_edge_index;
743   int vertex_index = start_vertex_index;
744   for (int edge_index = 0; edge_index < num_edges_per_row; edge_index++, subdiv_edge_index++) {
745     int coarse_edge_index = ORIGINDEX_NONE;
746     if (edge_index == 0) {
747       coarse_edge_index = coarse_start_edge_index;
748     }
749     else if (edge_index == num_edges_per_row - 1) {
750       coarse_edge_index = coarse_end_edge_index;
751     }
752     const int v1 = vertex_index;
753     const int v2 = vertex_index + num_edges_per_row;
754     ctx->foreach_context->edge(
755         ctx->foreach_context, tls, coarse_edge_index, subdiv_edge_index, v1, v2);
756     vertex_index += 1;
757   }
758   return subdiv_edge_index;
759 }
760
761 /* Defines edges between inner vertices of patch, and also edges to the
762  * boundary.
763  */
764
765 /* Consider a subdivision of base face at level 1:
766  *
767  *  y
768  *  ^
769  *  |   (6) ---- (7) ---- (8)
770  *  |    |        |        |
771  *  |   (3) ---- (4) ---- (5)
772  *  |    |        |        |
773  *  |   (0) ---- (1) ---- (2)
774  *  o---------------------------> x
775  *
776  * This is illustrate which parts of geometry is created by code below.
777  */
778
779 static void subdiv_foreach_edges_all_patches_regular(SubdivForeachTaskContext *ctx,
780                                                      void *tls,
781                                                      const MPoly *coarse_poly)
782 {
783   const Mesh *coarse_mesh = ctx->coarse_mesh;
784   const MEdge *coarse_medge = coarse_mesh->medge;
785   const MLoop *coarse_mloop = coarse_mesh->mloop;
786   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
787   const int poly_index = coarse_poly - coarse_mpoly;
788   const int resolution = ctx->settings->resolution;
789   const int start_vertex_index = ctx->vertices_inner_offset +
790                                  ctx->subdiv_vertex_offset[poly_index];
791   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
792   int subdiv_edge_index = ctx->edge_inner_offset + ctx->subdiv_edge_offset[poly_index];
793   /* Traverse bottom row of edges (0-1, 1-2). */
794   subdiv_edge_index = subdiv_foreach_edges_row(
795       ctx, tls, ORIGINDEX_NONE, subdiv_edge_index, start_vertex_index, resolution - 2);
796   /* Traverse remaining edges. */
797   for (int row = 0; row < resolution - 3; row++) {
798     const int start_row_vertex_index = start_vertex_index + row * (resolution - 2);
799     /* Traverse vertical columns.
800      *
801      * At first iteration it will be edges (0-3. 1-4, 2-5), then it
802      * will be (3-6, 4-7, 5-8) and so on.
803      */
804     subdiv_edge_index = subdiv_foreach_edges_column(ctx,
805                                                     tls,
806                                                     ORIGINDEX_NONE,
807                                                     ORIGINDEX_NONE,
808                                                     subdiv_edge_index,
809                                                     start_row_vertex_index,
810                                                     resolution - 2);
811     /* Create horizontal edge row.
812      *
813      * At first iteration it will be edges (3-4, 4-5), then it will be
814      * (6-7, 7-8) and so on.
815      */
816     subdiv_edge_index = subdiv_foreach_edges_row(ctx,
817                                                  tls,
818                                                  ORIGINDEX_NONE,
819                                                  subdiv_edge_index,
820                                                  start_row_vertex_index + resolution - 2,
821                                                  resolution - 2);
822   }
823   /* Connect inner part of patch to boundary. */
824   for (int corner = 0; corner < coarse_poly->totloop; corner++) {
825     const MLoop *coarse_loop = &coarse_mloop[coarse_poly->loopstart + corner];
826     const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
827     const int start_edge_vertex = ctx->vertices_edge_offset +
828                                   coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
829     const bool flip = (coarse_edge->v2 == coarse_loop->v);
830     int side_start_index = start_vertex_index;
831     int side_stride = 0;
832     /* Calculate starting veretx of corresponding inner part of ptex. */
833     if (corner == 0) {
834       side_stride = 1;
835     }
836     else if (corner == 1) {
837       side_start_index += resolution - 3;
838       side_stride = resolution - 2;
839     }
840     else if (corner == 2) {
841       side_start_index += num_subdiv_vertices_per_coarse_edge *
842                               num_subdiv_vertices_per_coarse_edge -
843                           1;
844       side_stride = -1;
845     }
846     else if (corner == 3) {
847       side_start_index += num_subdiv_vertices_per_coarse_edge *
848                           (num_subdiv_vertices_per_coarse_edge - 1);
849       side_stride = -(resolution - 2);
850     }
851     for (int i = 0; i < resolution - 2; i++, subdiv_edge_index++) {
852       const int v1 = (flip) ? (start_edge_vertex + (resolution - i - 3)) : (start_edge_vertex + i);
853       const int v2 = side_start_index + side_stride * i;
854       ctx->foreach_context->edge(
855           ctx->foreach_context, tls, ORIGINDEX_NONE, subdiv_edge_index, v1, v2);
856     }
857   }
858 }
859
860 static void subdiv_foreach_edges_all_patches_special(SubdivForeachTaskContext *ctx,
861                                                      void *tls,
862                                                      const MPoly *coarse_poly)
863 {
864   const Mesh *coarse_mesh = ctx->coarse_mesh;
865   const MEdge *coarse_medge = coarse_mesh->medge;
866   const MLoop *coarse_mloop = coarse_mesh->mloop;
867   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
868   const int poly_index = coarse_poly - coarse_mpoly;
869   const int resolution = ctx->settings->resolution;
870   const int ptex_face_resolution = ptex_face_resolution_get(coarse_poly, resolution);
871   const int ptex_face_inner_resolution = ptex_face_resolution - 2;
872   const int num_inner_vertices_per_ptex = (ptex_face_resolution - 1) * (ptex_face_resolution - 2);
873   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
874   const int center_vertex_index = ctx->vertices_inner_offset +
875                                   ctx->subdiv_vertex_offset[poly_index];
876   const int start_vertex_index = center_vertex_index + 1;
877   int subdiv_edge_index = ctx->edge_inner_offset + ctx->subdiv_edge_offset[poly_index];
878   /* Traverse inner ptex edges. */
879   for (int corner = 0; corner < coarse_poly->totloop; corner++) {
880     const int start_ptex_face_vertex_index = start_vertex_index +
881                                              corner * num_inner_vertices_per_ptex;
882     /* Similar steps to regular patch case. */
883     subdiv_edge_index = subdiv_foreach_edges_row(ctx,
884                                                  tls,
885                                                  ORIGINDEX_NONE,
886                                                  subdiv_edge_index,
887                                                  start_ptex_face_vertex_index,
888                                                  ptex_face_inner_resolution + 1);
889     for (int row = 0; row < ptex_face_inner_resolution - 1; row++) {
890       const int start_row_vertex_index = start_ptex_face_vertex_index +
891                                          row * (ptex_face_inner_resolution + 1);
892       subdiv_edge_index = subdiv_foreach_edges_column(ctx,
893                                                       tls,
894                                                       ORIGINDEX_NONE,
895                                                       ORIGINDEX_NONE,
896                                                       subdiv_edge_index,
897                                                       start_row_vertex_index,
898                                                       ptex_face_inner_resolution + 1);
899       subdiv_edge_index = subdiv_foreach_edges_row(ctx,
900                                                    tls,
901                                                    ORIGINDEX_NONE,
902                                                    subdiv_edge_index,
903                                                    start_row_vertex_index +
904                                                        ptex_face_inner_resolution + 1,
905                                                    ptex_face_inner_resolution + 1);
906     }
907   }
908   /* Create connections between ptex faces. */
909   for (int corner = 0; corner < coarse_poly->totloop; corner++) {
910     const int next_corner = (corner + 1) % coarse_poly->totloop;
911     int current_patch_vertex_index = start_vertex_index + corner * num_inner_vertices_per_ptex +
912                                      ptex_face_inner_resolution;
913     int next_path_vertex_index = start_vertex_index + next_corner * num_inner_vertices_per_ptex +
914                                  num_inner_vertices_per_ptex - ptex_face_resolution + 1;
915     for (int row = 0; row < ptex_face_inner_resolution; row++, subdiv_edge_index++) {
916       const int v1 = current_patch_vertex_index;
917       const int v2 = next_path_vertex_index;
918       ctx->foreach_context->edge(
919           ctx->foreach_context, tls, ORIGINDEX_NONE, subdiv_edge_index, v1, v2);
920       current_patch_vertex_index += ptex_face_inner_resolution + 1;
921       next_path_vertex_index += 1;
922     }
923   }
924   /* Create edges from center. */
925   if (ptex_face_resolution >= 3) {
926     for (int corner = 0; corner < coarse_poly->totloop; corner++, subdiv_edge_index++) {
927       const int current_patch_end_vertex_index = start_vertex_index +
928                                                  corner * num_inner_vertices_per_ptex +
929                                                  num_inner_vertices_per_ptex - 1;
930       const int v1 = center_vertex_index;
931       const int v2 = current_patch_end_vertex_index;
932       ctx->foreach_context->edge(
933           ctx->foreach_context, tls, ORIGINDEX_NONE, subdiv_edge_index, v1, v2);
934     }
935   }
936   /* Connect inner path of patch to boundary. */
937   const MLoop *prev_coarse_loop = &coarse_mloop[coarse_poly->loopstart + coarse_poly->totloop - 1];
938   for (int corner = 0; corner < coarse_poly->totloop; corner++) {
939     const MLoop *coarse_loop = &coarse_mloop[coarse_poly->loopstart + corner];
940     {
941       const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
942       const int start_edge_vertex = ctx->vertices_edge_offset +
943                                     coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
944       const bool flip = (coarse_edge->v2 == coarse_loop->v);
945       int side_start_index;
946       if (ptex_face_resolution >= 3) {
947         side_start_index = start_vertex_index + num_inner_vertices_per_ptex * corner;
948       }
949       else {
950         side_start_index = center_vertex_index;
951       }
952       for (int i = 0; i < ptex_face_resolution - 1; i++, subdiv_edge_index++) {
953         const int v1 = (flip) ? (start_edge_vertex + (resolution - i - 3)) :
954                                 (start_edge_vertex + i);
955         const int v2 = side_start_index + i;
956         ctx->foreach_context->edge(
957             ctx->foreach_context, tls, ORIGINDEX_NONE, subdiv_edge_index, v1, v2);
958       }
959     }
960     if (ptex_face_resolution >= 3) {
961       const MEdge *coarse_edge = &coarse_medge[prev_coarse_loop->e];
962       const int start_edge_vertex = ctx->vertices_edge_offset +
963                                     prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
964       const bool flip = (coarse_edge->v2 == coarse_loop->v);
965       int side_start_index = start_vertex_index + num_inner_vertices_per_ptex * corner;
966       for (int i = 0; i < ptex_face_resolution - 2; i++, subdiv_edge_index++) {
967         const int v1 = (flip) ? (start_edge_vertex + (resolution - i - 3)) :
968                                 (start_edge_vertex + i);
969         const int v2 = side_start_index + (ptex_face_inner_resolution + 1) * i;
970         ctx->foreach_context->edge(
971             ctx->foreach_context, tls, ORIGINDEX_NONE, subdiv_edge_index, v1, v2);
972       }
973     }
974     prev_coarse_loop = coarse_loop;
975   }
976 }
977
978 static void subdiv_foreach_edges_all_patches(SubdivForeachTaskContext *ctx,
979                                              void *tls,
980                                              const MPoly *coarse_poly)
981 {
982   if (coarse_poly->totloop == 4) {
983     subdiv_foreach_edges_all_patches_regular(ctx, tls, coarse_poly);
984   }
985   else {
986     subdiv_foreach_edges_all_patches_special(ctx, tls, coarse_poly);
987   }
988 }
989
990 static void subdiv_foreach_edges(SubdivForeachTaskContext *ctx, void *tls, int poly_index)
991 {
992   const Mesh *coarse_mesh = ctx->coarse_mesh;
993   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
994   const MPoly *coarse_poly = &coarse_mpoly[poly_index];
995   subdiv_foreach_edges_all_patches(ctx, tls, coarse_poly);
996 }
997
998 static void subdiv_foreach_boundary_edges(SubdivForeachTaskContext *ctx,
999                                           void *tls,
1000                                           int coarse_edge_index)
1001 {
1002   const Mesh *coarse_mesh = ctx->coarse_mesh;
1003   const MEdge *coarse_medge = coarse_mesh->medge;
1004   const MEdge *coarse_edge = &coarse_medge[coarse_edge_index];
1005   const int resolution = ctx->settings->resolution;
1006   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1007   const int num_subdiv_edges_per_coarse_edge = resolution - 1;
1008   int subdiv_edge_index = ctx->edge_boundary_offset +
1009                           coarse_edge_index * num_subdiv_edges_per_coarse_edge;
1010   int last_vertex_index = ctx->vertices_corner_offset + coarse_edge->v1;
1011   for (int i = 0; i < num_subdiv_edges_per_coarse_edge - 1; i++, subdiv_edge_index++) {
1012     const int v1 = last_vertex_index;
1013     const int v2 = ctx->vertices_edge_offset +
1014                    coarse_edge_index * num_subdiv_vertices_per_coarse_edge + i;
1015     ctx->foreach_context->edge(
1016         ctx->foreach_context, tls, coarse_edge_index, subdiv_edge_index, v1, v2);
1017     last_vertex_index = v2;
1018   }
1019   const int v1 = last_vertex_index;
1020   const int v2 = ctx->vertices_corner_offset + coarse_edge->v2;
1021   ctx->foreach_context->edge(
1022       ctx->foreach_context, tls, coarse_edge_index, subdiv_edge_index, v1, v2);
1023 }
1024
1025 /* =============================================================================
1026  * Loops traversal.
1027  */
1028
1029 static void rotate_indices(const int rot, int *a, int *b, int *c, int *d)
1030 {
1031   int values[4] = {*a, *b, *c, *d};
1032   *a = values[(0 - rot + 4) % 4];
1033   *b = values[(1 - rot + 4) % 4];
1034   *c = values[(2 - rot + 4) % 4];
1035   *d = values[(3 - rot + 4) % 4];
1036 }
1037
1038 static void subdiv_foreach_loops_of_poly(SubdivForeachTaskContext *ctx,
1039                                          void *tls,
1040                                          int subdiv_loop_start_index,
1041                                          const int ptex_face_index,
1042                                          const int coarse_poly_index,
1043                                          const int coarse_corner_index,
1044                                          const int rotation,
1045                                          /*const*/ int v0,
1046                                          /*const*/ int e0,
1047                                          /*const*/ int v1,
1048                                          /*const*/ int e1,
1049                                          /*const*/ int v2,
1050                                          /*const*/ int e2,
1051                                          /*const*/ int v3,
1052                                          /*const*/ int e3,
1053                                          const float u,
1054                                          const float v,
1055                                          const float du,
1056                                          const float dv)
1057 {
1058   rotate_indices(rotation, &v0, &v1, &v2, &v3);
1059   rotate_indices(rotation, &e0, &e1, &e2, &e3);
1060   ctx->foreach_context->loop(ctx->foreach_context,
1061                              tls,
1062                              ptex_face_index,
1063                              u,
1064                              v,
1065                              ORIGINDEX_NONE,
1066                              coarse_poly_index,
1067                              coarse_corner_index,
1068                              subdiv_loop_start_index + 0,
1069                              v0,
1070                              e0);
1071   ctx->foreach_context->loop(ctx->foreach_context,
1072                              tls,
1073                              ptex_face_index,
1074                              u + du,
1075                              v,
1076                              ORIGINDEX_NONE,
1077                              coarse_poly_index,
1078                              coarse_corner_index,
1079                              subdiv_loop_start_index + 1,
1080                              v1,
1081                              e1);
1082   ctx->foreach_context->loop(ctx->foreach_context,
1083                              tls,
1084                              ptex_face_index,
1085                              u + du,
1086                              v + dv,
1087                              ORIGINDEX_NONE,
1088                              coarse_poly_index,
1089                              coarse_corner_index,
1090                              subdiv_loop_start_index + 2,
1091                              v2,
1092                              e2);
1093   ctx->foreach_context->loop(ctx->foreach_context,
1094                              tls,
1095                              ptex_face_index,
1096                              u,
1097                              v + dv,
1098                              ORIGINDEX_NONE,
1099                              coarse_poly_index,
1100                              coarse_corner_index,
1101                              subdiv_loop_start_index + 3,
1102                              v3,
1103                              e3);
1104 }
1105
1106 static void subdiv_foreach_loops_regular(SubdivForeachTaskContext *ctx,
1107                                          void *tls,
1108                                          const MPoly *coarse_poly)
1109 {
1110   const int resolution = ctx->settings->resolution;
1111   /* Base/coarse mesh information. */
1112   const Mesh *coarse_mesh = ctx->coarse_mesh;
1113   const MEdge *coarse_medge = coarse_mesh->medge;
1114   const MLoop *coarse_mloop = coarse_mesh->mloop;
1115   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1116   const int coarse_poly_index = coarse_poly - coarse_mpoly;
1117   const int ptex_resolution = ptex_face_resolution_get(coarse_poly, resolution);
1118   const int ptex_inner_resolution = ptex_resolution - 2;
1119   const int num_subdiv_edges_per_coarse_edge = resolution - 1;
1120   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1121   const float inv_ptex_resolution_1 = 1.0f / (float)(ptex_resolution - 1);
1122   const int ptex_face_index = ctx->face_ptex_offset[coarse_poly_index];
1123   const int start_vertex_index = ctx->vertices_inner_offset +
1124                                  ctx->subdiv_vertex_offset[coarse_poly_index];
1125   const int start_edge_index = ctx->edge_inner_offset + ctx->subdiv_edge_offset[coarse_poly_index];
1126   const int start_poly_index = ctx->subdiv_polygon_offset[coarse_poly_index];
1127   const int start_loop_index = 4 * start_poly_index;
1128   const float du = inv_ptex_resolution_1;
1129   const float dv = inv_ptex_resolution_1;
1130   /* Hi-poly subdivided mesh. */
1131   int subdiv_loop_index = start_loop_index;
1132   /* Loops for inner part of ptex. */
1133   for (int y = 1; y < ptex_resolution - 2; y++) {
1134     const float v = y * inv_ptex_resolution_1;
1135     const int inner_y = y - 1;
1136     for (int x = 1; x < ptex_resolution - 2; x++, subdiv_loop_index += 4) {
1137       const int inner_x = x - 1;
1138       const float u = x * inv_ptex_resolution_1;
1139       /* Vertex indices ordered counter-clockwise. */
1140       const int v0 = start_vertex_index + (inner_y * ptex_inner_resolution + inner_x);
1141       const int v1 = v0 + 1;
1142       const int v2 = v0 + ptex_inner_resolution + 1;
1143       const int v3 = v0 + ptex_inner_resolution;
1144       /* Edge indices ordered counter-clockwise. */
1145       const int e0 = start_edge_index + (inner_y * (2 * ptex_inner_resolution - 1) + inner_x);
1146       const int e1 = e0 + ptex_inner_resolution;
1147       const int e2 = e0 + (2 * ptex_inner_resolution - 1);
1148       const int e3 = e0 + ptex_inner_resolution - 1;
1149       subdiv_foreach_loops_of_poly(ctx,
1150                                    tls,
1151                                    subdiv_loop_index,
1152                                    ptex_face_index,
1153                                    coarse_poly_index,
1154                                    0,
1155                                    0,
1156                                    v0,
1157                                    e0,
1158                                    v1,
1159                                    e1,
1160                                    v2,
1161                                    e2,
1162                                    v3,
1163                                    e3,
1164                                    u,
1165                                    v,
1166                                    du,
1167                                    dv);
1168     }
1169   }
1170   /* Loops for faces connecting inner ptex part with boundary. */
1171   const MLoop *prev_coarse_loop = &coarse_mloop[coarse_poly->loopstart + coarse_poly->totloop - 1];
1172   for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1173     const MLoop *coarse_loop = &coarse_mloop[coarse_poly->loopstart + corner];
1174     const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1175     const MEdge *prev_coarse_edge = &coarse_medge[prev_coarse_loop->e];
1176     const int start_edge_vertex = ctx->vertices_edge_offset +
1177                                   coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1178     const bool flip = (coarse_edge->v2 == coarse_loop->v);
1179     int side_start_index = start_vertex_index;
1180     int side_stride = 0;
1181     int v0 = ctx->vertices_corner_offset + coarse_loop->v;
1182     int v3, e3;
1183     int e2_offset, e2_stride;
1184     float u, v, delta_u, delta_v;
1185     if (prev_coarse_loop->v == prev_coarse_edge->v1) {
1186       v3 = ctx->vertices_edge_offset + prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge +
1187            num_subdiv_vertices_per_coarse_edge - 1;
1188       e3 = ctx->edge_boundary_offset + prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1189            num_subdiv_edges_per_coarse_edge - 1;
1190     }
1191     else {
1192       v3 = ctx->vertices_edge_offset + prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1193       e3 = ctx->edge_boundary_offset + prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge;
1194     }
1195     /* Calculate starting veretx of corresponding inner part of ptex. */
1196     if (corner == 0) {
1197       side_stride = 1;
1198       e2_offset = 0;
1199       e2_stride = 1;
1200       u = 0.0f;
1201       v = 0.0f;
1202       delta_u = du;
1203       delta_v = 0.0f;
1204     }
1205     else if (corner == 1) {
1206       side_start_index += resolution - 3;
1207       side_stride = resolution - 2;
1208       e2_offset = 2 * num_subdiv_edges_per_coarse_edge - 4;
1209       e2_stride = 2 * num_subdiv_edges_per_coarse_edge - 3;
1210       u = 1.0f - du;
1211       v = 0;
1212       delta_u = 0.0f;
1213       delta_v = dv;
1214     }
1215     else if (corner == 2) {
1216       side_start_index += num_subdiv_vertices_per_coarse_edge *
1217                               num_subdiv_vertices_per_coarse_edge -
1218                           1;
1219       side_stride = -1;
1220       e2_offset = num_edges_per_ptex_face_get(resolution - 2) - 1;
1221       e2_stride = -1;
1222       u = 1.0f - du;
1223       v = 1.0f - dv;
1224       delta_u = -du;
1225       delta_v = 0.0f;
1226     }
1227     else if (corner == 3) {
1228       side_start_index += num_subdiv_vertices_per_coarse_edge *
1229                           (num_subdiv_vertices_per_coarse_edge - 1);
1230       side_stride = -(resolution - 2);
1231       e2_offset = num_edges_per_ptex_face_get(resolution - 2) -
1232                   (2 * num_subdiv_edges_per_coarse_edge - 3);
1233       e2_stride = -(2 * num_subdiv_edges_per_coarse_edge - 3);
1234       u = 0.0f;
1235       v = 1.0f - dv;
1236       delta_u = 0.0f;
1237       delta_v = -dv;
1238     }
1239     for (int i = 0; i < resolution - 2; i++, subdiv_loop_index += 4) {
1240       int v1;
1241       if (flip) {
1242         v1 = start_edge_vertex + (resolution - i - 3);
1243       }
1244       else {
1245         v1 = start_edge_vertex + i;
1246       }
1247       const int v2 = side_start_index + side_stride * i;
1248       int e0;
1249       if (flip) {
1250         e0 = ctx->edge_boundary_offset + coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1251              num_subdiv_edges_per_coarse_edge - i - 1;
1252       }
1253       else {
1254         e0 = ctx->edge_boundary_offset + coarse_loop->e * num_subdiv_edges_per_coarse_edge + i;
1255       }
1256       int e1 = start_edge_index + num_edges_per_ptex_face_get(resolution - 2) +
1257                corner * num_subdiv_vertices_per_coarse_edge + i;
1258       int e2;
1259       if (i == 0) {
1260         e2 = start_edge_index + num_edges_per_ptex_face_get(resolution - 2) +
1261              ((corner - 1 + coarse_poly->totloop) % coarse_poly->totloop) *
1262                  num_subdiv_vertices_per_coarse_edge +
1263              num_subdiv_vertices_per_coarse_edge - 1;
1264       }
1265       else {
1266         e2 = start_edge_index + e2_offset + e2_stride * (i - 1);
1267       }
1268       subdiv_foreach_loops_of_poly(ctx,
1269                                    tls,
1270                                    subdiv_loop_index,
1271                                    ptex_face_index,
1272                                    coarse_poly_index,
1273                                    corner,
1274                                    corner,
1275                                    v0,
1276                                    e0,
1277                                    v1,
1278                                    e1,
1279                                    v2,
1280                                    e2,
1281                                    v3,
1282                                    e3,
1283                                    u + delta_u * i,
1284                                    v + delta_v * i,
1285                                    du,
1286                                    dv);
1287       v0 = v1;
1288       v3 = v2;
1289       e3 = e1;
1290     }
1291     prev_coarse_loop = coarse_loop;
1292   }
1293 }
1294
1295 static void subdiv_foreach_loops_special(SubdivForeachTaskContext *ctx,
1296                                          void *tls,
1297                                          const MPoly *coarse_poly)
1298 {
1299   const int resolution = ctx->settings->resolution;
1300   /* Base/coarse mesh information. */
1301   const Mesh *coarse_mesh = ctx->coarse_mesh;
1302   const MEdge *coarse_medge = coarse_mesh->medge;
1303   const MLoop *coarse_mloop = coarse_mesh->mloop;
1304   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1305   const int coarse_poly_index = coarse_poly - coarse_mpoly;
1306   const int ptex_face_resolution = ptex_face_resolution_get(coarse_poly, resolution);
1307   const int ptex_face_inner_resolution = ptex_face_resolution - 2;
1308   const float inv_ptex_resolution_1 = 1.0f / (float)(ptex_face_resolution - 1);
1309   const int num_inner_vertices_per_ptex = (ptex_face_resolution - 1) * (ptex_face_resolution - 2);
1310   const int num_inner_edges_per_ptex_face = num_inner_edges_per_ptex_face_get(
1311       ptex_face_inner_resolution + 1);
1312   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1313   const int num_subdiv_edges_per_coarse_edge = resolution - 1;
1314   const int ptex_face_index = ctx->face_ptex_offset[coarse_poly_index];
1315   const int center_vertex_index = ctx->vertices_inner_offset +
1316                                   ctx->subdiv_vertex_offset[coarse_poly_index];
1317   const int start_vertex_index = center_vertex_index + 1;
1318   const int start_inner_vertex_index = center_vertex_index + 1;
1319   const int start_edge_index = ctx->edge_inner_offset + ctx->subdiv_edge_offset[coarse_poly_index];
1320   const int start_poly_index = ctx->subdiv_polygon_offset[coarse_poly_index];
1321   const int start_loop_index = 4 * start_poly_index;
1322   const float du = inv_ptex_resolution_1;
1323   const float dv = inv_ptex_resolution_1;
1324   /* Hi-poly subdivided mesh. */
1325   int subdiv_loop_index = start_loop_index;
1326   for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1327     const int corner_vertex_index = start_vertex_index + corner * num_inner_vertices_per_ptex;
1328     const int corner_edge_index = start_edge_index + corner * num_inner_edges_per_ptex_face;
1329     for (int y = 1; y < ptex_face_inner_resolution; y++) {
1330       const float v = y * inv_ptex_resolution_1;
1331       const int inner_y = y - 1;
1332       for (int x = 1; x < ptex_face_inner_resolution + 1; x++, subdiv_loop_index += 4) {
1333         const int inner_x = x - 1;
1334         const float u = x * inv_ptex_resolution_1;
1335         /* Vertex indices ordered counter-clockwise. */
1336         const int v0 = corner_vertex_index +
1337                        (inner_y * (ptex_face_inner_resolution + 1) + inner_x);
1338         const int v1 = v0 + 1;
1339         const int v2 = v0 + ptex_face_inner_resolution + 2;
1340         const int v3 = v0 + ptex_face_inner_resolution + 1;
1341         /* Edge indices ordered counter-clockwise. */
1342         const int e0 = corner_edge_index +
1343                        (inner_y * (2 * ptex_face_inner_resolution + 1) + inner_x);
1344         const int e1 = e0 + ptex_face_inner_resolution + 1;
1345         const int e2 = e0 + (2 * ptex_face_inner_resolution + 1);
1346         const int e3 = e0 + ptex_face_inner_resolution;
1347         subdiv_foreach_loops_of_poly(ctx,
1348                                      tls,
1349                                      subdiv_loop_index,
1350                                      ptex_face_index + corner,
1351                                      coarse_poly_index,
1352                                      corner,
1353                                      0,
1354                                      v0,
1355                                      e0,
1356                                      v1,
1357                                      e1,
1358                                      v2,
1359                                      e2,
1360                                      v3,
1361                                      e3,
1362                                      u,
1363                                      v,
1364                                      du,
1365                                      dv);
1366       }
1367     }
1368   }
1369   /* Create connections between ptex faces. */
1370   for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1371     const int next_corner = (corner + 1) % coarse_poly->totloop;
1372     const int corner_edge_index = start_edge_index + corner * num_inner_edges_per_ptex_face;
1373     const int next_corner_edge_index = start_edge_index +
1374                                        next_corner * num_inner_edges_per_ptex_face;
1375     int current_patch_vertex_index = start_inner_vertex_index +
1376                                      corner * num_inner_vertices_per_ptex +
1377                                      ptex_face_inner_resolution;
1378     int next_path_vertex_index = start_inner_vertex_index +
1379                                  next_corner * num_inner_vertices_per_ptex +
1380                                  num_inner_vertices_per_ptex - ptex_face_resolution + 1;
1381     int v0 = current_patch_vertex_index;
1382     int v1 = next_path_vertex_index;
1383     current_patch_vertex_index += ptex_face_inner_resolution + 1;
1384     next_path_vertex_index += 1;
1385     int e0 = start_edge_index + coarse_poly->totloop * num_inner_edges_per_ptex_face +
1386              corner * (ptex_face_resolution - 2);
1387     int e1 = next_corner_edge_index + num_inner_edges_per_ptex_face - ptex_face_resolution + 2;
1388     int e3 = corner_edge_index + 2 * ptex_face_resolution - 4;
1389     for (int row = 1; row < ptex_face_inner_resolution; row++, subdiv_loop_index += 4) {
1390       const int v2 = next_path_vertex_index;
1391       const int v3 = current_patch_vertex_index;
1392       const int e2 = e0 + 1;
1393       const float u = row * du;
1394       const float v = 1.0f - dv;
1395       subdiv_foreach_loops_of_poly(ctx,
1396                                    tls,
1397                                    subdiv_loop_index,
1398                                    ptex_face_index + next_corner,
1399                                    coarse_poly_index,
1400                                    next_corner,
1401                                    3,
1402                                    v0,
1403                                    e0,
1404                                    v1,
1405                                    e1,
1406                                    v2,
1407                                    e2,
1408                                    v3,
1409                                    e3,
1410                                    u,
1411                                    v,
1412                                    du,
1413                                    dv);
1414       current_patch_vertex_index += ptex_face_inner_resolution + 1;
1415       next_path_vertex_index += 1;
1416       v0 = v3;
1417       v1 = v2;
1418       e0 = e2;
1419       e1 += 1;
1420       e3 += 2 * ptex_face_resolution - 3;
1421     }
1422   }
1423   /* Create loops from center. */
1424   if (ptex_face_resolution >= 3) {
1425     const int start_center_edge_index = start_edge_index + (num_inner_edges_per_ptex_face +
1426                                                             ptex_face_inner_resolution) *
1427                                                                coarse_poly->totloop;
1428     const int start_boundary_edge = start_edge_index +
1429                                     coarse_poly->totloop * num_inner_edges_per_ptex_face +
1430                                     ptex_face_inner_resolution - 1;
1431     for (int corner = 0, prev_corner = coarse_poly->totloop - 1; corner < coarse_poly->totloop;
1432          prev_corner = corner, corner++, subdiv_loop_index += 4) {
1433       const int corner_edge_index = start_edge_index + corner * num_inner_edges_per_ptex_face;
1434       const int current_patch_end_vertex_index = start_vertex_index +
1435                                                  corner * num_inner_vertices_per_ptex +
1436                                                  num_inner_vertices_per_ptex - 1;
1437       const int prev_current_patch_end_vertex_index = start_vertex_index +
1438                                                       prev_corner * num_inner_vertices_per_ptex +
1439                                                       num_inner_vertices_per_ptex - 1;
1440       const int v0 = center_vertex_index;
1441       const int v1 = prev_current_patch_end_vertex_index;
1442       const int v2 = current_patch_end_vertex_index - 1;
1443       const int v3 = current_patch_end_vertex_index;
1444       const int e0 = start_center_edge_index + prev_corner;
1445       const int e1 = start_boundary_edge + prev_corner * (ptex_face_inner_resolution);
1446       const int e2 = corner_edge_index + num_inner_edges_per_ptex_face - 1;
1447       const int e3 = start_center_edge_index + corner;
1448       const float u = 1.0f - du;
1449       const float v = 1.0f - dv;
1450       subdiv_foreach_loops_of_poly(ctx,
1451                                    tls,
1452                                    subdiv_loop_index,
1453                                    ptex_face_index + corner,
1454                                    coarse_poly_index,
1455                                    corner,
1456                                    2,
1457                                    v0,
1458                                    e0,
1459                                    v1,
1460                                    e1,
1461                                    v2,
1462                                    e2,
1463                                    v3,
1464                                    e3,
1465                                    u,
1466                                    v,
1467                                    du,
1468                                    dv);
1469     }
1470   }
1471   /* Loops for faces connecting inner ptex part with boundary. */
1472   const MLoop *prev_coarse_loop = &coarse_mloop[coarse_poly->loopstart + coarse_poly->totloop - 1];
1473   for (int prev_corner = coarse_poly->totloop - 1, corner = 0; corner < coarse_poly->totloop;
1474        prev_corner = corner, corner++) {
1475     const MLoop *coarse_loop = &coarse_mloop[coarse_poly->loopstart + corner];
1476     const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1477     const MEdge *prev_coarse_edge = &coarse_medge[prev_coarse_loop->e];
1478     const bool flip = (coarse_edge->v2 == coarse_loop->v);
1479     const int start_edge_vertex = ctx->vertices_edge_offset +
1480                                   coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1481     const int corner_vertex_index = start_vertex_index + corner * num_inner_vertices_per_ptex;
1482     const int corner_edge_index = start_edge_index + corner * num_inner_edges_per_ptex_face;
1483     /* Create loops for polygons along U axis. */
1484     int v0 = ctx->vertices_corner_offset + coarse_loop->v;
1485     int v3, e3;
1486     if (prev_coarse_loop->v == prev_coarse_edge->v1) {
1487       v3 = ctx->vertices_edge_offset + prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge +
1488            num_subdiv_vertices_per_coarse_edge - 1;
1489       e3 = ctx->edge_boundary_offset + prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1490            num_subdiv_edges_per_coarse_edge - 1;
1491     }
1492     else {
1493       v3 = ctx->vertices_edge_offset + prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1494       e3 = ctx->edge_boundary_offset + prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge;
1495     }
1496     for (int i = 0; i <= ptex_face_inner_resolution; i++, subdiv_loop_index += 4) {
1497       int v1;
1498       if (flip) {
1499         v1 = start_edge_vertex + (resolution - i - 3);
1500       }
1501       else {
1502         v1 = start_edge_vertex + i;
1503       }
1504       int v2;
1505       if (ptex_face_inner_resolution >= 1) {
1506         v2 = corner_vertex_index + i;
1507       }
1508       else {
1509         v2 = center_vertex_index;
1510       }
1511       int e0;
1512       if (flip) {
1513         e0 = ctx->edge_boundary_offset + coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1514              num_subdiv_edges_per_coarse_edge - i - 1;
1515       }
1516       else {
1517         e0 = ctx->edge_boundary_offset + coarse_loop->e * num_subdiv_edges_per_coarse_edge + i;
1518       }
1519       int e1 = start_edge_index + corner * (2 * ptex_face_inner_resolution + 1);
1520       if (ptex_face_resolution >= 3) {
1521         e1 += coarse_poly->totloop *
1522                   (num_inner_edges_per_ptex_face + ptex_face_inner_resolution + 1) +
1523               i;
1524       }
1525       int e2 = 0;
1526       if (i == 0 && ptex_face_resolution >= 3) {
1527         e2 = start_edge_index +
1528              coarse_poly->totloop *
1529                  (num_inner_edges_per_ptex_face + ptex_face_inner_resolution + 1) +
1530              corner * (2 * ptex_face_inner_resolution + 1) + ptex_face_inner_resolution + 1;
1531       }
1532       else if (i == 0 && ptex_face_resolution < 3) {
1533         e2 = start_edge_index + prev_corner * (2 * ptex_face_inner_resolution + 1);
1534       }
1535       else {
1536         e2 = corner_edge_index + i - 1;
1537       }
1538       const float u = du * i;
1539       const float v = 0.0f;
1540       subdiv_foreach_loops_of_poly(ctx,
1541                                    tls,
1542                                    subdiv_loop_index,
1543                                    ptex_face_index + corner,
1544                                    coarse_poly_index,
1545                                    corner,
1546                                    0,
1547                                    v0,
1548                                    e0,
1549                                    v1,
1550                                    e1,
1551                                    v2,
1552                                    e2,
1553                                    v3,
1554                                    e3,
1555                                    u,
1556                                    v,
1557                                    du,
1558                                    dv);
1559       v0 = v1;
1560       v3 = v2;
1561       e3 = e1;
1562     }
1563     /* Create loops for polygons along V axis. */
1564     const bool flip_prev = (prev_coarse_edge->v2 == coarse_loop->v);
1565     v0 = corner_vertex_index;
1566     if (prev_coarse_loop->v == prev_coarse_edge->v1) {
1567       v3 = ctx->vertices_edge_offset + prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge +
1568            num_subdiv_vertices_per_coarse_edge - 1;
1569     }
1570     else {
1571       v3 = ctx->vertices_edge_offset + prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1572     }
1573     e3 = start_edge_index +
1574          coarse_poly->totloop * (num_inner_edges_per_ptex_face + ptex_face_inner_resolution + 1) +
1575          corner * (2 * ptex_face_inner_resolution + 1) + ptex_face_inner_resolution + 1;
1576     for (int i = 0; i <= ptex_face_inner_resolution - 1; i++, subdiv_loop_index += 4) {
1577       int v1;
1578       int e0, e1;
1579       if (i == ptex_face_inner_resolution - 1) {
1580         v1 = start_vertex_index + prev_corner * num_inner_vertices_per_ptex +
1581              ptex_face_inner_resolution;
1582         e1 = start_edge_index +
1583              coarse_poly->totloop *
1584                  (num_inner_edges_per_ptex_face + ptex_face_inner_resolution + 1) +
1585              prev_corner * (2 * ptex_face_inner_resolution + 1) + ptex_face_inner_resolution;
1586         e0 = start_edge_index + coarse_poly->totloop * num_inner_edges_per_ptex_face +
1587              prev_corner * ptex_face_inner_resolution;
1588       }
1589       else {
1590         v1 = v0 + ptex_face_inner_resolution + 1;
1591         e0 = corner_edge_index + ptex_face_inner_resolution +
1592              i * (2 * ptex_face_inner_resolution + 1);
1593         e1 = e3 + 1;
1594       }
1595       int v2 = flip_prev ? v3 - 1 : v3 + 1;
1596       int e2;
1597       if (flip_prev) {
1598         e2 = ctx->edge_boundary_offset + prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1599              num_subdiv_edges_per_coarse_edge - 2 - i;
1600       }
1601       else {
1602         e2 = ctx->edge_boundary_offset + prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1603              1 + i;
1604       }
1605       const float u = 0.0f;
1606       const float v = du * (i + 1);
1607       subdiv_foreach_loops_of_poly(ctx,
1608                                    tls,
1609                                    subdiv_loop_index,
1610                                    ptex_face_index + corner,
1611                                    coarse_poly_index,
1612                                    corner,
1613                                    1,
1614                                    v0,
1615                                    e0,
1616                                    v1,
1617                                    e1,
1618                                    v2,
1619                                    e2,
1620                                    v3,
1621                                    e3,
1622                                    u,
1623                                    v,
1624                                    du,
1625                                    dv);
1626       v0 = v1;
1627       v3 = v2;
1628       e3 = e1;
1629     }
1630     prev_coarse_loop = coarse_loop;
1631   }
1632 }
1633
1634 static void subdiv_foreach_loops(SubdivForeachTaskContext *ctx, void *tls, int poly_index)
1635 {
1636   const Mesh *coarse_mesh = ctx->coarse_mesh;
1637   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1638   const MPoly *coarse_poly = &coarse_mpoly[poly_index];
1639   if (coarse_poly->totloop == 4) {
1640     subdiv_foreach_loops_regular(ctx, tls, coarse_poly);
1641   }
1642   else {
1643     subdiv_foreach_loops_special(ctx, tls, coarse_poly);
1644   }
1645 }
1646
1647 /* =============================================================================
1648  * Polygons traverse process.
1649  */
1650
1651 static void subdiv_foreach_polys(SubdivForeachTaskContext *ctx, void *tls, int poly_index)
1652 {
1653   const int resolution = ctx->settings->resolution;
1654   const int start_poly_index = ctx->subdiv_polygon_offset[poly_index];
1655   /* Base/coarse mesh information. */
1656   const Mesh *coarse_mesh = ctx->coarse_mesh;
1657   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1658   const MPoly *coarse_poly = &coarse_mpoly[poly_index];
1659   const int num_ptex_faces_per_poly = num_ptex_faces_per_poly_get(coarse_poly);
1660   const int ptex_resolution = ptex_face_resolution_get(coarse_poly, resolution);
1661   const int num_polys_per_ptex = num_polys_per_ptex_get(ptex_resolution);
1662   const int num_loops_per_ptex = 4 * num_polys_per_ptex;
1663   const int start_loop_index = 4 * start_poly_index;
1664   /* Hi-poly subdivided mesh. */
1665   int subdiv_polyon_index = start_poly_index;
1666   for (int ptex_of_poly_index = 0; ptex_of_poly_index < num_ptex_faces_per_poly;
1667        ptex_of_poly_index++) {
1668     for (int subdiv_poly_index = 0; subdiv_poly_index < num_polys_per_ptex;
1669          subdiv_poly_index++, subdiv_polyon_index++) {
1670       const int loopstart = start_loop_index + (ptex_of_poly_index * num_loops_per_ptex) +
1671                             (subdiv_poly_index * 4);
1672       ctx->foreach_context->poly(
1673           ctx->foreach_context, tls, poly_index, subdiv_polyon_index, loopstart, 4);
1674     }
1675   }
1676 }
1677
1678 /* =============================================================================
1679  * Loose elements traverse process.
1680  */
1681
1682 static void subdiv_foreach_loose_vertices_task(void *__restrict userdata,
1683                                                const int coarse_vertex_index,
1684                                                const TaskParallelTLS *__restrict tls)
1685 {
1686   SubdivForeachTaskContext *ctx = userdata;
1687   if (BLI_BITMAP_TEST_BOOL(ctx->coarse_vertices_used_map, coarse_vertex_index)) {
1688     /* Vertex is not loose, was handled when handling polygons. */
1689     return;
1690   }
1691   const int subdiv_vertex_index = ctx->vertices_corner_offset + coarse_vertex_index;
1692   ctx->foreach_context->vertex_loose(
1693       ctx->foreach_context, tls->userdata_chunk, coarse_vertex_index, subdiv_vertex_index);
1694 }
1695
1696 static void subdiv_foreach_vertices_of_loose_edges_task(void *__restrict userdata,
1697                                                         const int coarse_edge_index,
1698                                                         const TaskParallelTLS *__restrict tls)
1699 {
1700   SubdivForeachTaskContext *ctx = userdata;
1701   if (BLI_BITMAP_TEST_BOOL(ctx->coarse_edges_used_map, coarse_edge_index)) {
1702     /* Vertex is not loose, was handled when handling polygons. */
1703     return;
1704   }
1705   const int resolution = ctx->settings->resolution;
1706   const int resolution_1 = resolution - 1;
1707   const float inv_resolution_1 = 1.0f / (float)resolution_1;
1708   const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1709   const Mesh *coarse_mesh = ctx->coarse_mesh;
1710   const MEdge *coarse_edge = &coarse_mesh->medge[coarse_edge_index];
1711   /* Subdivion vertices which corresponds to edge's v1 and v2. */
1712   const int subdiv_v1_index = ctx->vertices_corner_offset + coarse_edge->v1;
1713   const int subdiv_v2_index = ctx->vertices_corner_offset + coarse_edge->v2;
1714   /* First subdivided inner vertex of the edge.  */
1715   const int subdiv_start_vertex = ctx->vertices_edge_offset +
1716                                   coarse_edge_index * num_subdiv_vertices_per_coarse_edge;
1717   /* Perform interpolation. */
1718   for (int i = 0; i < resolution; i++) {
1719     const float u = i * inv_resolution_1;
1720     int subdiv_vertex_index;
1721     if (i == 0) {
1722       subdiv_vertex_index = subdiv_v1_index;
1723     }
1724     else if (i == resolution - 1) {
1725       subdiv_vertex_index = subdiv_v2_index;
1726     }
1727     else {
1728       subdiv_vertex_index = subdiv_start_vertex + (i - 1);
1729     }
1730     ctx->foreach_context->vertex_of_loose_edge(
1731         ctx->foreach_context, tls->userdata_chunk, coarse_edge_index, u, subdiv_vertex_index);
1732   }
1733 }
1734
1735 /* =============================================================================
1736  * Subdivision process entry points.
1737  */
1738
1739 static void subdiv_foreach_single_geometry_vertices(SubdivForeachTaskContext *ctx, void *tls)
1740 {
1741   if (ctx->foreach_context->vertex_corner == NULL) {
1742     return;
1743   }
1744   const Mesh *coarse_mesh = ctx->coarse_mesh;
1745   const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1746   for (int poly_index = 0; poly_index < coarse_mesh->totpoly; poly_index++) {
1747     const MPoly *coarse_poly = &coarse_mpoly[poly_index];
1748     subdiv_foreach_corner_vertices(ctx, tls, coarse_poly);
1749     subdiv_foreach_edge_vertices(ctx, tls, coarse_poly);
1750   }
1751 }
1752
1753 static void subdiv_foreach_single_thread_tasks(SubdivForeachTaskContext *ctx)
1754 {
1755   /* NOTE: In theory, we can try to skip allocation of TLS here, but in
1756    * practice if the callbacks used here are not specified then TLS will not
1757    * be requested anyway. */
1758   void *tls = subdiv_foreach_tls_alloc(ctx);
1759   /* Passes to average displacement on the corner vertices
1760    * and boundary edges. */
1761   subdiv_foreach_every_corner_vertices(ctx, tls);
1762   subdiv_foreach_every_edge_vertices(ctx, tls);
1763   /* Run callbacks which are supposed to be run once per shared geometry. */
1764   subdiv_foreach_single_geometry_vertices(ctx, tls);
1765   subdiv_foreach_tls_free(ctx, tls);
1766 }
1767
1768 static void subdiv_foreach_task(void *__restrict userdata,
1769                                 const int poly_index,
1770                                 const TaskParallelTLS *__restrict tls)
1771 {
1772   SubdivForeachTaskContext *ctx = userdata;
1773   /* Traverse hi-poly vertex coordinates and normals. */
1774   subdiv_foreach_vertices(ctx, tls->userdata_chunk, poly_index);
1775   /* Traverse mesh geometry for the given base poly index. */
1776   if (ctx->foreach_context->edge != NULL) {
1777     subdiv_foreach_edges(ctx, tls->userdata_chunk, poly_index);
1778   }
1779   if (ctx->foreach_context->loop != NULL) {
1780     subdiv_foreach_loops(ctx, tls->userdata_chunk, poly_index);
1781   }
1782   if (ctx->foreach_context->poly != NULL) {
1783     subdiv_foreach_polys(ctx, tls->userdata_chunk, poly_index);
1784   }
1785 }
1786
1787 static void subdiv_foreach_boundary_edges_task(void *__restrict userdata,
1788                                                const int edge_index,
1789                                                const TaskParallelTLS *__restrict tls)
1790 {
1791   SubdivForeachTaskContext *ctx = userdata;
1792   subdiv_foreach_boundary_edges(ctx, tls->userdata_chunk, edge_index);
1793 }
1794
1795 static void subdiv_foreach_finalize(void *__restrict userdata, void *__restrict userdata_chunk)
1796 {
1797   SubdivForeachTaskContext *ctx = userdata;
1798   ctx->foreach_context->user_data_tls_free(userdata_chunk);
1799 }
1800
1801 bool BKE_subdiv_foreach_subdiv_geometry(Subdiv *subdiv,
1802                                         const SubdivForeachContext *context,
1803                                         const SubdivToMeshSettings *mesh_settings,
1804                                         const Mesh *coarse_mesh)
1805 {
1806   SubdivForeachTaskContext ctx = {0};
1807   ctx.coarse_mesh = coarse_mesh;
1808   ctx.settings = mesh_settings;
1809   ctx.foreach_context = context;
1810   subdiv_foreach_ctx_init(subdiv, &ctx);
1811   if (context->topology_info != NULL) {
1812     if (!context->topology_info(context,
1813                                 ctx.num_subdiv_vertices,
1814                                 ctx.num_subdiv_edges,
1815                                 ctx.num_subdiv_loops,
1816                                 ctx.num_subdiv_polygons)) {
1817       subdiv_foreach_ctx_free(&ctx);
1818       return false;
1819     }
1820   }
1821   /* Run all the code which is not supposed to be run from threads. */
1822   subdiv_foreach_single_thread_tasks(&ctx);
1823   /* Threaded traversal of the rest of topology. */
1824   TaskParallelSettings parallel_range_settings;
1825   BLI_parallel_range_settings_defaults(&parallel_range_settings);
1826   parallel_range_settings.userdata_chunk = context->user_data_tls;
1827   parallel_range_settings.userdata_chunk_size = context->user_data_tls_size;
1828   if (context->user_data_tls_free != NULL) {
1829     parallel_range_settings.func_finalize = subdiv_foreach_finalize;
1830   }
1831   BLI_task_parallel_range(
1832       0, coarse_mesh->totpoly, &ctx, subdiv_foreach_task, &parallel_range_settings);
1833   if (context->vertex_loose != NULL) {
1834     BLI_task_parallel_range(0,
1835                             coarse_mesh->totvert,
1836                             &ctx,
1837                             subdiv_foreach_loose_vertices_task,
1838                             &parallel_range_settings);
1839   }
1840   if (context->vertex_of_loose_edge != NULL) {
1841     BLI_task_parallel_range(0,
1842                             coarse_mesh->totedge,
1843                             &ctx,
1844                             subdiv_foreach_vertices_of_loose_edges_task,
1845                             &parallel_range_settings);
1846   }
1847   if (context->edge != NULL) {
1848     BLI_task_parallel_range(0,
1849                             coarse_mesh->totedge,
1850                             &ctx,
1851                             subdiv_foreach_boundary_edges_task,
1852                             &parallel_range_settings);
1853   }
1854   subdiv_foreach_ctx_free(&ctx);
1855   return true;
1856 }