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