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