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