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