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