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