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