Subsurf: Support subdivision of loose elements
[blender.git] / source / blender / blenkernel / intern / subdiv_mesh.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_mesh.c
27  *  \ingroup bke
28  */
29
30 #include "BKE_subdiv.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
46 #include "MEM_guardedalloc.h"
47
48 /* =============================================================================
49  * General helpers.
50  */
51
52 /* Number of ptex faces for a given polygon. */
53 BLI_INLINE int num_ptex_faces_per_poly_get(const MPoly *poly)
54 {
55         return (poly->totloop == 4) ? 1 : poly->totloop;
56 }
57
58 BLI_INLINE int num_edges_per_ptex_face_get(const int resolution)
59 {
60         return 2 * (resolution - 1) * resolution;
61 }
62
63 BLI_INLINE int num_inner_edges_per_ptex_face_get(const int resolution)
64 {
65         if (resolution < 2) {
66                 return 0;
67         }
68         return (resolution - 2) * resolution +
69                (resolution - 1) * (resolution - 1);
70 }
71
72 /* Number of subdivision polygons per ptex face. */
73 BLI_INLINE int num_polys_per_ptex_get(const int resolution)
74 {
75         return (resolution - 1) * (resolution - 1);
76 }
77
78 /* Subdivision resolution per given polygon's ptex faces. */
79 BLI_INLINE int ptex_face_resolution_get(const MPoly *poly, int resolution)
80 {
81         return (poly->totloop == 4) ? (resolution)
82                                     : ((resolution >> 1) + 1);
83 }
84
85 /* =============================================================================
86  * Mesh subdivision context.
87  */
88
89 typedef struct SubdivMeshContext {
90         const Mesh *coarse_mesh;
91         Subdiv *subdiv;
92         Mesh *subdiv_mesh;
93         const SubdivToMeshSettings *settings;
94         /* Cached custom data arrays for fastter access. */
95         int *vert_origindex;
96         int *edge_origindex;
97         int *loop_origindex;
98         int *poly_origindex;
99         /* UV layers interpolation. */
100         int num_uv_layers;
101         MLoopUV *uv_layers[MAX_MTFACE];
102         /* Counters of geometry in subdivided mesh, initialized as a part of
103          * offsets calculation.
104          */
105         int num_subdiv_vertices;
106         int num_subdiv_edges;
107         int num_subdiv_loops;
108         int num_subdiv_polygons;
109         /* Offsets of various geometry in the subdivision mesh arrays. */
110         int vertices_corner_offset;
111         int vertices_edge_offset;
112         int vertices_inner_offset;
113         int edge_boundary_offset;
114         int edge_inner_offset;
115         /* Indexed by coarse polygon index, indicates offset in subdivided mesh
116          * vertices, edges and polygons arrays, where first element of the poly
117          * begins.
118          */
119         int *subdiv_vertex_offset;
120         int *subdiv_edge_offset;
121         int *subdiv_polygon_offset;
122         /* Indexed by base face index, element indicates total number of ptex faces
123          * created for preceding base faces.
124          */
125         int *face_ptex_offset;
126         /* Bitmap indicating whether vertex was used already or not.
127          * - During patch evaluation indicates whether coarse vertex was already
128          *   evaluated and its position on limit is already known.
129          */
130         BLI_bitmap *coarse_vertices_used_map;
131         /* Bitmap indicating whether edge was used already or not. This includes:
132          * - During context initialization it indicates whether subdivided verticies
133          *   for corresponding edge were already calculated or not.
134          * - During patch evaluation it indicates whether vertices along this edge
135          *   were already evaluated.
136          */
137         BLI_bitmap *coarse_edges_used_map;
138 } SubdivMeshContext;
139
140 static void subdiv_mesh_ctx_cache_uv_layers(SubdivMeshContext *ctx)
141 {
142         Mesh *subdiv_mesh = ctx->subdiv_mesh;
143         ctx->num_uv_layers =
144                 CustomData_number_of_layers(&subdiv_mesh->ldata, CD_MLOOPUV);
145         for (int layer_index = 0; layer_index < ctx->num_uv_layers; ++layer_index) {
146                 ctx->uv_layers[layer_index] = CustomData_get_layer_n(
147                         &subdiv_mesh->ldata, CD_MLOOPUV, layer_index);
148         }
149 }
150
151 static void subdiv_mesh_ctx_cache_custom_data_layers(SubdivMeshContext *ctx)
152 {
153         Mesh *subdiv_mesh = ctx->subdiv_mesh;
154         /* Pointers to original indices layers. */
155         ctx->vert_origindex = CustomData_get_layer(
156                 &subdiv_mesh->vdata, CD_ORIGINDEX);
157         ctx->edge_origindex = CustomData_get_layer(
158                 &subdiv_mesh->edata, CD_ORIGINDEX);
159         ctx->loop_origindex = CustomData_get_layer(
160                 &subdiv_mesh->ldata, CD_ORIGINDEX);
161         ctx->poly_origindex = CustomData_get_layer(
162                 &subdiv_mesh->pdata, CD_ORIGINDEX);
163         /* UV layers interpolation. */
164         subdiv_mesh_ctx_cache_uv_layers(ctx);
165 }
166
167 /* NOTE: Expects edge map to be zeroed. */
168 static void subdiv_mesh_ctx_count(SubdivMeshContext *ctx)
169 {
170         /* Reset counters. */
171         ctx->num_subdiv_vertices = 0;
172         ctx->num_subdiv_edges = 0;
173         ctx->num_subdiv_loops = 0;
174         ctx->num_subdiv_polygons = 0;
175         /* Static geometry counters. */
176         const int resolution = ctx->settings->resolution;
177         const int no_quad_patch_resolution = ((resolution >> 1) + 1);
178         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
179         const int num_inner_vertices_per_quad = (resolution - 2) * (resolution - 2);
180         const int num_inner_vertices_per_noquad_patch =
181                 (no_quad_patch_resolution - 2) * (no_quad_patch_resolution - 2);
182         const Mesh *coarse_mesh = ctx->coarse_mesh;
183         const MLoop *coarse_mloop = coarse_mesh->mloop;
184         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
185         ctx->num_subdiv_vertices = coarse_mesh->totvert;
186         ctx->num_subdiv_edges =
187                 coarse_mesh->totedge * (num_subdiv_vertices_per_coarse_edge + 1);
188         /* Calculate extra vertices and edges createdd by non-loose geometry. */
189         for (int poly_index = 0; poly_index < coarse_mesh->totpoly; poly_index++) {
190                 const MPoly *coarse_poly = &coarse_mpoly[poly_index];
191                 const int num_ptex_faces_per_poly =
192                         num_ptex_faces_per_poly_get(coarse_poly);
193                 for (int corner = 0; corner < coarse_poly->totloop; corner++) {
194                          const MLoop *loop = &coarse_mloop[coarse_poly->loopstart + corner];
195                          const bool is_edge_used =
196                                  BLI_BITMAP_TEST_BOOL(ctx->coarse_edges_used_map, loop->e);
197                         /* Edges which aren't counted yet. */
198                         if (!is_edge_used) {
199                                 BLI_BITMAP_ENABLE(ctx->coarse_edges_used_map, loop->e);
200                                 ctx->num_subdiv_vertices += num_subdiv_vertices_per_coarse_edge;
201                         }
202                 }
203                 /* Inner verticies of polygon. */
204                 if (num_ptex_faces_per_poly == 1) {
205                         ctx->num_subdiv_vertices += num_inner_vertices_per_quad;
206                         ctx->num_subdiv_edges +=
207                                 num_edges_per_ptex_face_get(resolution - 2) +
208                                 4 * num_subdiv_vertices_per_coarse_edge;
209                         ctx->num_subdiv_polygons += num_polys_per_ptex_get(resolution);
210                 }
211                 else {
212                         ctx->num_subdiv_vertices +=
213                                 1 +
214                                 num_ptex_faces_per_poly * (no_quad_patch_resolution - 2) +
215                                 num_ptex_faces_per_poly * num_inner_vertices_per_noquad_patch;
216                         ctx->num_subdiv_edges +=
217                                 num_ptex_faces_per_poly *
218                                         (num_inner_edges_per_ptex_face_get(
219                                                  no_quad_patch_resolution - 1) +
220                                          (no_quad_patch_resolution - 2) +
221                                          num_subdiv_vertices_per_coarse_edge);
222                         if (no_quad_patch_resolution >= 3) {
223                                 ctx->num_subdiv_edges += coarse_poly->totloop;
224                         }
225                         ctx->num_subdiv_polygons +=
226                                 num_ptex_faces_per_poly *
227                                 num_polys_per_ptex_get(no_quad_patch_resolution);
228                 }
229         }
230         /* Calculate extra edges createdd by loose edges. */
231         for (int edge_index = 0; edge_index < coarse_mesh->totedge; edge_index++) {
232                 if (!BLI_BITMAP_TEST_BOOL(ctx->coarse_edges_used_map, edge_index)) {
233                         ctx->num_subdiv_vertices += num_subdiv_vertices_per_coarse_edge;
234                 }
235         }
236         ctx->num_subdiv_loops = ctx->num_subdiv_polygons * 4;
237 }
238
239 static void subdiv_mesh_ctx_init_offsets(SubdivMeshContext *ctx)
240 {
241         const Mesh *coarse_mesh = ctx->coarse_mesh;
242         const int resolution = ctx->settings->resolution;
243         const int resolution_2 = resolution - 2;
244         const int resolution_2_squared = resolution_2 * resolution_2;
245         const int no_quad_patch_resolution = ((resolution >> 1) + 1);
246         const int num_irregular_vertices_per_patch =
247                 (no_quad_patch_resolution - 2) * (no_quad_patch_resolution - 1);
248         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
249         const int num_subdiv_edges_per_coarse_edge = resolution - 1;
250         /* Constant offsets in arrays. */
251         ctx->vertices_corner_offset = 0;
252         ctx->vertices_edge_offset = coarse_mesh->totvert;
253         ctx->vertices_inner_offset =
254                 ctx->vertices_edge_offset +
255                 coarse_mesh->totedge * num_subdiv_vertices_per_coarse_edge;
256         ctx->edge_boundary_offset = 0;
257         ctx->edge_inner_offset =
258                 ctx->edge_boundary_offset +
259                 coarse_mesh->totedge * num_subdiv_edges_per_coarse_edge;
260         /* "Indexed" offsets. */
261         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
262         int vertex_offset = 0;
263         int edge_offset = 0;
264         int polygon_offset = 0;
265         int face_ptex_offset = 0;
266         for (int poly_index = 0; poly_index < coarse_mesh->totpoly; poly_index++) {
267                 const MPoly *coarse_poly = &coarse_mpoly[poly_index];
268                 const int num_ptex_faces_per_poly =
269                         num_ptex_faces_per_poly_get(coarse_poly);
270                 ctx->face_ptex_offset[poly_index] = face_ptex_offset;
271                 ctx->subdiv_vertex_offset[poly_index] = vertex_offset;
272                 ctx->subdiv_edge_offset[poly_index] = edge_offset;
273                 ctx->subdiv_polygon_offset[poly_index] = polygon_offset;
274                 face_ptex_offset += num_ptex_faces_per_poly;
275                 if (num_ptex_faces_per_poly == 1) {
276                         vertex_offset += resolution_2_squared;
277                         edge_offset += num_edges_per_ptex_face_get(resolution - 2) +
278                                        4 * num_subdiv_vertices_per_coarse_edge;
279                         polygon_offset += num_polys_per_ptex_get(resolution);
280                 }
281                 else {
282                         vertex_offset +=
283                                 1 +
284                                 num_ptex_faces_per_poly * num_irregular_vertices_per_patch;
285                         edge_offset +=
286                                 num_ptex_faces_per_poly *
287                                         (num_inner_edges_per_ptex_face_get(
288                                                  no_quad_patch_resolution - 1) +
289                                          (no_quad_patch_resolution - 2) +
290                                          num_subdiv_vertices_per_coarse_edge);
291                         if (no_quad_patch_resolution >= 3) {
292                                 edge_offset += coarse_poly->totloop;
293                         }
294                         polygon_offset +=
295                                 num_ptex_faces_per_poly *
296                                 num_polys_per_ptex_get(no_quad_patch_resolution);
297                 }
298         }
299 }
300
301 static void subdiv_mesh_ctx_init(SubdivMeshContext *ctx)
302 {
303         const Mesh *coarse_mesh = ctx->coarse_mesh;
304         /* Allocate maps and offsets. */
305         ctx->coarse_vertices_used_map =
306                 BLI_BITMAP_NEW(coarse_mesh->totvert, "vertices used map");
307         ctx->coarse_edges_used_map =
308                 BLI_BITMAP_NEW(coarse_mesh->totedge, "edges used map");
309         ctx->subdiv_vertex_offset = MEM_malloc_arrayN(
310                 coarse_mesh->totpoly,
311                 sizeof(*ctx->subdiv_vertex_offset),
312                 "vertex_offset");
313         ctx->subdiv_edge_offset = MEM_malloc_arrayN(
314                 coarse_mesh->totpoly,
315                 sizeof(*ctx->subdiv_edge_offset),
316                 "subdiv_edge_offset");
317         ctx->subdiv_polygon_offset = MEM_malloc_arrayN(
318                 coarse_mesh->totpoly,
319                 sizeof(*ctx->subdiv_polygon_offset),
320                 "subdiv_edge_offset");
321         ctx->face_ptex_offset = MEM_malloc_arrayN(coarse_mesh->totpoly,
322                                                   sizeof(*ctx->face_ptex_offset),
323                                                   "face_ptex_offset");
324         /* Initialize all offsets. */
325         subdiv_mesh_ctx_init_offsets(ctx);
326         /* Calculate number of geometry in the result subdivision mesh. */
327         subdiv_mesh_ctx_count(ctx);
328         /* Re-set maps which were used at this step. */
329         BLI_BITMAP_SET_ALL(ctx->coarse_edges_used_map, false, coarse_mesh->totedge);
330 }
331
332 static void subdiv_mesh_ctx_init_result(SubdivMeshContext *ctx)
333 {
334         subdiv_mesh_ctx_cache_custom_data_layers(ctx);
335 }
336
337 static void subdiv_mesh_ctx_free(SubdivMeshContext *ctx)
338 {
339         MEM_freeN(ctx->coarse_vertices_used_map);
340         MEM_freeN(ctx->coarse_edges_used_map);
341         MEM_freeN(ctx->subdiv_vertex_offset);
342         MEM_freeN(ctx->subdiv_edge_offset);
343         MEM_freeN(ctx->subdiv_polygon_offset);
344         MEM_freeN(ctx->face_ptex_offset);
345 }
346
347 /* =============================================================================
348  * Loop custom data copy helpers.
349  */
350
351 typedef struct LoopsOfPtex {
352         /* First loop of the ptex, starts at ptex (0, 0) and goes in u direction. */
353         const MLoop *first_loop;
354         /* Last loop of the ptex, starts at ptex (0, 0) and goes in v direction. */
355         const MLoop *last_loop;
356         /* For quad coarse faces only. */
357         const MLoop *second_loop;
358         const MLoop *third_loop;
359 } LoopsOfPtex;
360
361 static void loops_of_ptex_get(
362         const SubdivMeshContext *ctx,
363         LoopsOfPtex *loops_of_ptex,
364         const MPoly *coarse_poly,
365         const int ptex_of_poly_index)
366 {
367         const MLoop *coarse_mloop = ctx->coarse_mesh->mloop;
368         const int first_ptex_loop_index =
369                 coarse_poly->loopstart + ptex_of_poly_index;
370         /* Loop which look in the (opposite) V direction of the current
371          * ptex face.
372          *
373          * TOOD(sergey): Get rid of using module on every iteration.
374          */
375         const int last_ptex_loop_index =
376                 coarse_poly->loopstart +
377                 (ptex_of_poly_index + coarse_poly->totloop - 1) %
378                         coarse_poly->totloop;
379         loops_of_ptex->first_loop = &coarse_mloop[first_ptex_loop_index];
380         loops_of_ptex->last_loop = &coarse_mloop[last_ptex_loop_index];
381         if (coarse_poly->totloop == 4) {
382                 loops_of_ptex->second_loop = loops_of_ptex->first_loop + 1;
383                 loops_of_ptex->third_loop = loops_of_ptex->first_loop + 2;
384         }
385         else {
386                 loops_of_ptex->second_loop = NULL;
387                 loops_of_ptex->third_loop = NULL;
388         }
389 }
390
391 /* =============================================================================
392  * Vertex custom data interpolation helpers.
393  */
394
395 /* TODO(sergey): Somehow de-duplicate with loops storage, without too much
396  * exception cases all over the code.
397  */
398
399 typedef struct VerticesForInterpolation {
400         /* This field points to a vertex data which is to be used for interpolation.
401          * The idea is to avoid unnecessary allocations for regular faces, where
402          * we can simply
403          */
404         const CustomData *vertex_data;
405         /* Vertices data calculated for ptex corners. There are always 4 elements
406          * in this custom data, aligned the following way:
407          *
408          *   index 0 -> uv (0, 0)
409          *   index 1 -> uv (0, 1)
410          *   index 2 -> uv (1, 1)
411          *   index 3 -> uv (1, 0)
412          *
413          * Is allocated for non-regular faces (triangles and n-gons).
414          */
415         CustomData vertex_data_storage;
416         bool vertex_data_storage_allocated;
417         /* Infices within vertex_data to interpolate for. The indices are aligned
418          * with uv coordinates in a similar way as indices in loop_data_storage.
419          */
420         int vertex_indices[4];
421 } VerticesForInterpolation;
422
423 static void vertex_interpolation_init(
424         const SubdivMeshContext *ctx,
425         VerticesForInterpolation *vertex_interpolation,
426         const MPoly *coarse_poly)
427 {
428         const Mesh *coarse_mesh = ctx->coarse_mesh;
429         const MLoop *coarse_mloop = coarse_mesh->mloop;
430         if (coarse_poly->totloop == 4) {
431                 vertex_interpolation->vertex_data = &coarse_mesh->vdata;
432                 vertex_interpolation->vertex_indices[0] =
433                         coarse_mloop[coarse_poly->loopstart + 0].v;
434                 vertex_interpolation->vertex_indices[1] =
435                         coarse_mloop[coarse_poly->loopstart + 1].v;
436                 vertex_interpolation->vertex_indices[2] =
437                         coarse_mloop[coarse_poly->loopstart + 2].v;
438                 vertex_interpolation->vertex_indices[3] =
439                         coarse_mloop[coarse_poly->loopstart + 3].v;
440                 vertex_interpolation->vertex_data_storage_allocated = false;
441         }
442         else {
443                 vertex_interpolation->vertex_data =
444                         &vertex_interpolation->vertex_data_storage;
445                 /* Allocate storage for loops corresponding to ptex corners. */
446                 CustomData_copy(&ctx->coarse_mesh->vdata,
447                                 &vertex_interpolation->vertex_data_storage,
448                                 CD_MASK_EVERYTHING,
449                                 CD_CALLOC,
450                                 4);
451                 /* Initialize indices. */
452                 vertex_interpolation->vertex_indices[0] = 0;
453                 vertex_interpolation->vertex_indices[1] = 1;
454                 vertex_interpolation->vertex_indices[2] = 2;
455                 vertex_interpolation->vertex_indices[3] = 3;
456                 vertex_interpolation->vertex_data_storage_allocated = true;
457                 /* Interpolate center of poly right away, it stays unchanged for all
458                  * ptex faces.
459                  */
460                 const float weight = 1.0f / (float)coarse_poly->totloop;
461                 float *weights = BLI_array_alloca(weights, coarse_poly->totloop);
462                 int *indices = BLI_array_alloca(indices, coarse_poly->totloop);
463                 for (int i = 0; i < coarse_poly->totloop; ++i) {
464                         weights[i] = weight;
465                         indices[i] = coarse_mloop[coarse_poly->loopstart + i].v;
466                 }
467                 CustomData_interp(&coarse_mesh->vdata,
468                                   &vertex_interpolation->vertex_data_storage,
469                                   indices,
470                                   weights, NULL,
471                                   coarse_poly->totloop,
472                                   2);
473         }
474 }
475
476 static void vertex_interpolation_from_ptex(
477         const SubdivMeshContext *ctx,
478         VerticesForInterpolation *vertex_interpolation,
479         const MPoly *coarse_poly,
480         const int ptex_of_poly_index)
481 {
482         if (coarse_poly->totloop == 4) {
483                 /* Nothing to do, all indices and data is already assigned. */
484         }
485         else {
486                 const CustomData *vertex_data = &ctx->coarse_mesh->vdata;
487                 const Mesh *coarse_mesh = ctx->coarse_mesh;
488                 const MLoop *coarse_mloop = coarse_mesh->mloop;
489                 LoopsOfPtex loops_of_ptex;
490                 loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, ptex_of_poly_index);
491                 /* Ptex face corner corresponds to a poly loop with same index. */
492                 CustomData_copy_data(
493                         vertex_data,
494                         &vertex_interpolation->vertex_data_storage,
495                         coarse_mloop[coarse_poly->loopstart + ptex_of_poly_index].v,
496                         0,
497                         1);
498                 /* Interpolate remaining ptex face corners, which hits loops
499                  * middle points.
500                  *
501                  * TODO(sergey): Re-use one of interpolation results from previous
502                  * iteration.
503                  */
504                 const float weights[2] = {0.5f, 0.5f};
505                 const int first_loop_index = loops_of_ptex.first_loop - coarse_mloop;
506                 const int last_loop_index = loops_of_ptex.last_loop - coarse_mloop;
507                 const int first_indices[2] = {
508                         coarse_mloop[first_loop_index].v,
509                         coarse_mloop[coarse_poly->loopstart +
510                                 (first_loop_index - coarse_poly->loopstart + 1) %
511                                         coarse_poly->totloop].v};
512                 const int last_indices[2] = {coarse_mloop[first_loop_index].v,
513                                              coarse_mloop[last_loop_index].v};
514                 CustomData_interp(vertex_data,
515                                   &vertex_interpolation->vertex_data_storage,
516                                   first_indices,
517                                   weights, NULL,
518                                   2,
519                                   1);
520                 CustomData_interp(vertex_data,
521                                   &vertex_interpolation->vertex_data_storage,
522                                   last_indices,
523                                   weights, NULL,
524                                   2,
525                                   3);
526         }
527 }
528
529 static void vertex_interpolation_end(
530         VerticesForInterpolation *vertex_interpolation)
531 {
532         if (vertex_interpolation->vertex_data_storage_allocated) {
533                 CustomData_free(&vertex_interpolation->vertex_data_storage, 4);
534         }
535 }
536
537 /* =============================================================================
538  * Loop custom data interpolation helpers.
539  */
540
541 typedef struct LoopsForInterpolation {
542  /* This field points to a loop data which is to be used for interpolation.
543          * The idea is to avoid unnecessary allocations for regular faces, where
544          * we can simply
545          */
546         const CustomData *loop_data;
547         /* Loops data calculated for ptex corners. There are always 4 elements
548          * in this custom data, aligned the following way:
549          *
550          *   index 0 -> uv (0, 0)
551          *   index 1 -> uv (0, 1)
552          *   index 2 -> uv (1, 1)
553          *   index 3 -> uv (1, 0)
554          *
555          * Is allocated for non-regular faces (triangles and n-gons).
556          */
557         CustomData loop_data_storage;
558         bool loop_data_storage_allocated;
559         /* Infices within loop_data to interpolate for. The indices are aligned with
560          * uv coordinates in a similar way as indices in loop_data_storage.
561          */
562         int loop_indices[4];
563 } LoopsForInterpolation;
564
565 static void loop_interpolation_init(
566         const SubdivMeshContext *ctx,
567         LoopsForInterpolation *loop_interpolation,
568         const MPoly *coarse_poly)
569 {
570         const Mesh *coarse_mesh = ctx->coarse_mesh;
571         if (coarse_poly->totloop == 4) {
572                 loop_interpolation->loop_data = &coarse_mesh->ldata;
573                 loop_interpolation->loop_indices[0] = coarse_poly->loopstart + 0;
574                 loop_interpolation->loop_indices[1] = coarse_poly->loopstart + 1;
575                 loop_interpolation->loop_indices[2] = coarse_poly->loopstart + 2;
576                 loop_interpolation->loop_indices[3] = coarse_poly->loopstart + 3;
577                 loop_interpolation->loop_data_storage_allocated = false;
578         }
579         else {
580                 loop_interpolation->loop_data = &loop_interpolation->loop_data_storage;
581                 /* Allocate storage for loops corresponding to ptex corners. */
582                 CustomData_copy(&ctx->coarse_mesh->ldata,
583                                 &loop_interpolation->loop_data_storage,
584                                 CD_MASK_EVERYTHING,
585                                 CD_CALLOC,
586                                 4);
587                 /* Initialize indices. */
588                 loop_interpolation->loop_indices[0] = 0;
589                 loop_interpolation->loop_indices[1] = 1;
590                 loop_interpolation->loop_indices[2] = 2;
591                 loop_interpolation->loop_indices[3] = 3;
592                 loop_interpolation->loop_data_storage_allocated = true;
593                 /* Interpolate center of poly right away, it stays unchanged for all
594                  * ptex faces.
595                  */
596                 const float weight = 1.0f / (float)coarse_poly->totloop;
597                 float *weights = BLI_array_alloca(weights, coarse_poly->totloop);
598                 int *indices = BLI_array_alloca(indices, coarse_poly->totloop);
599                 for (int i = 0; i < coarse_poly->totloop; ++i) {
600                         weights[i] = weight;
601                         indices[i] = coarse_poly->loopstart + i;
602                 }
603                 CustomData_interp(&coarse_mesh->ldata,
604                                   &loop_interpolation->loop_data_storage,
605                                   indices,
606                                   weights, NULL,
607                                   coarse_poly->totloop,
608                                   2);
609         }
610 }
611
612 static void loop_interpolation_from_ptex(
613         const SubdivMeshContext *ctx,
614         LoopsForInterpolation *loop_interpolation,
615         const MPoly *coarse_poly,
616         const int ptex_face_index)
617 {
618         if (coarse_poly->totloop == 4) {
619                 /* Nothing to do, all indices and data is already assigned. */
620         }
621         else {
622                 const CustomData *loop_data = &ctx->coarse_mesh->ldata;
623                 const Mesh *coarse_mesh = ctx->coarse_mesh;
624                 const MLoop *coarse_mloop = coarse_mesh->mloop;
625                 LoopsOfPtex loops_of_ptex;
626                 loops_of_ptex_get(ctx, &loops_of_ptex, coarse_poly, ptex_face_index);
627                 /* Ptex face corner corresponds to a poly loop with same index. */
628                 CustomData_copy_data(loop_data,
629                                      &loop_interpolation->loop_data_storage,
630                                      coarse_poly->loopstart + ptex_face_index,
631                                      0,
632                                      1);
633                 /* Interpolate remaining ptex face corners, which hits loops
634                  * middle points.
635                  *
636                  * TODO(sergey): Re-use one of interpolation results from previous
637                  * iteration.
638                  */
639                 const float weights[2] = {0.5f, 0.5f};
640                 const int first_indices[2] = {
641                         loops_of_ptex.first_loop - coarse_mloop,
642                         (loops_of_ptex.first_loop + 1 - coarse_mloop) %
643                                 coarse_poly->totloop};
644                 const int last_indices[2] = {
645                         loops_of_ptex.last_loop - coarse_mloop,
646                         loops_of_ptex.first_loop - coarse_mloop};
647                 CustomData_interp(loop_data,
648                                   &loop_interpolation->loop_data_storage,
649                                   first_indices,
650                                   weights, NULL,
651                                   2,
652                                   1);
653                 CustomData_interp(loop_data,
654                                   &loop_interpolation->loop_data_storage,
655                                   last_indices,
656                                   weights, NULL,
657                                   2,
658                                   3);
659         }
660 }
661
662 static void loop_interpolation_end(LoopsForInterpolation *loop_interpolation)
663 {
664         if (loop_interpolation->loop_data_storage_allocated) {
665                 CustomData_free(&loop_interpolation->loop_data_storage, 4);
666         }
667 }
668
669 /* =============================================================================
670  * Vertex subdivision process.
671  */
672
673 /* Custom data interpolation helpers. */
674
675 static void subdiv_vertex_data_copy(
676         const SubdivMeshContext *ctx,
677         const MVert *coarse_vertex,
678         MVert *subdiv_vertex)
679 {
680         const Mesh *coarse_mesh = ctx->coarse_mesh;
681         Mesh *subdiv_mesh = ctx->subdiv_mesh;
682         const int coarse_vertex_index = coarse_vertex - coarse_mesh->mvert;
683         const int subdiv_vertex_index = subdiv_vertex - subdiv_mesh->mvert;
684         CustomData_copy_data(&coarse_mesh->vdata,
685                              &ctx->subdiv_mesh->vdata,
686                              coarse_vertex_index,
687                              subdiv_vertex_index,
688                              1);
689 }
690
691 static void subdiv_vertex_data_interpolate(
692         const SubdivMeshContext *ctx,
693         MVert *subdiv_vertex,
694         const VerticesForInterpolation *vertex_interpolation,
695         const float u, const float v)
696 {
697         const int subdiv_vertex_index = subdiv_vertex - ctx->subdiv_mesh->mvert;
698         const float weights[4] = {(1.0f - u) * (1.0f - v),
699                                   u * (1.0f - v),
700                                   u * v,
701                                   (1.0f - u) * v};
702         CustomData_interp(vertex_interpolation->vertex_data,
703                           &ctx->subdiv_mesh->vdata,
704                           vertex_interpolation->vertex_indices,
705                           weights, NULL,
706                           4,
707                           subdiv_vertex_index);
708         if (ctx->vert_origindex != NULL) {
709                 ctx->vert_origindex[subdiv_vertex_index] = ORIGINDEX_NONE;
710         }
711 }
712
713 /* Evaluation of corner vertices. They are coming from coarse vertices. */
714
715 static void subdiv_evaluate_corner_vertices_regular(
716         SubdivMeshContext *ctx,
717         const MPoly *coarse_poly)
718 {
719         const float weights[4][2] = {{0.0f, 0.0f},
720                                      {1.0f, 0.0f},
721                                      {1.0f, 1.0f},
722                                      {0.0f, 1.0f}};
723         Subdiv *subdiv = ctx->subdiv;
724         const Mesh *coarse_mesh = ctx->coarse_mesh;
725         const MVert *coarse_mvert = coarse_mesh->mvert;
726         const MLoop *coarse_mloop = coarse_mesh->mloop;
727         Mesh *subdiv_mesh = ctx->subdiv_mesh;
728         MVert *subdiv_mvert = subdiv_mesh->mvert;
729         const int poly_index = coarse_poly - coarse_mesh->mpoly;
730         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
731         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
732                 const MLoop *coarse_loop =
733                     &coarse_mloop[coarse_poly->loopstart + corner];
734                 if (BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_vertices_used_map,
735                                                    coarse_loop->v))
736                 {
737                         continue;
738                 }
739                 const MVert *coarse_vert = &coarse_mvert[coarse_loop->v];
740                 MVert *subdiv_vert = &subdiv_mvert[
741                         ctx->vertices_corner_offset + coarse_loop->v];
742                 subdiv_vertex_data_copy(ctx, coarse_vert, subdiv_vert);
743                 BKE_subdiv_eval_limit_point_and_short_normal(
744                         subdiv,
745                         ptex_face_index,
746                         weights[corner][0], weights[corner][1],
747                         subdiv_vert->co, subdiv_vert->no);
748         }
749 }
750
751 static void subdiv_evaluate_corner_vertices_special(
752         SubdivMeshContext *ctx,
753         const MPoly *coarse_poly)
754 {
755         Subdiv *subdiv = ctx->subdiv;
756         const Mesh *coarse_mesh = ctx->coarse_mesh;
757         const MVert *coarse_mvert = coarse_mesh->mvert;
758         const MLoop *coarse_mloop = coarse_mesh->mloop;
759         Mesh *subdiv_mesh = ctx->subdiv_mesh;
760         MVert *subdiv_mvert = subdiv_mesh->mvert;
761         const int poly_index = coarse_poly - coarse_mesh->mpoly;
762         int ptex_face_index = ctx->face_ptex_offset[poly_index];
763         for (int corner = 0;
764              corner < coarse_poly->totloop;
765              corner++, ptex_face_index++)
766         {
767                 const MLoop *coarse_loop =
768                     &coarse_mloop[coarse_poly->loopstart + corner];
769                 if (BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_vertices_used_map,
770                                                    coarse_loop->v))
771                 {
772                         continue;
773                 }
774                 const MVert *coarse_vert = &coarse_mvert[coarse_loop->v];
775                 MVert *subdiv_vert = &subdiv_mvert[
776                         ctx->vertices_corner_offset + coarse_loop->v];
777                 subdiv_vertex_data_copy(ctx, coarse_vert, subdiv_vert);
778                 BKE_subdiv_eval_limit_point_and_short_normal(
779                         subdiv,
780                         ptex_face_index,
781                         0.0f, 0.0f,
782                         subdiv_vert->co, subdiv_vert->no);
783         }
784 }
785
786 static void subdiv_evaluate_corner_vertices(SubdivMeshContext *ctx,
787                                             const MPoly *coarse_poly)
788 {
789         if (coarse_poly->totloop == 4) {
790                 subdiv_evaluate_corner_vertices_regular(ctx, coarse_poly);
791         }
792         else {
793                 subdiv_evaluate_corner_vertices_special(ctx, coarse_poly);
794         }
795 }
796
797 /* Evaluation of edge vertices. They are coming from coarse edges. */
798
799 static void subdiv_evaluate_edge_vertices_regular(
800         SubdivMeshContext *ctx,
801         const MPoly *coarse_poly,
802         VerticesForInterpolation *vertex_interpolation)
803 {
804         const int resolution = ctx->settings->resolution;
805         const int resolution_1 = resolution - 1;
806         const float inv_resolution_1 = 1.0f / (float)resolution_1;
807         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
808         Subdiv *subdiv = ctx->subdiv;
809         const Mesh *coarse_mesh = ctx->coarse_mesh;
810         const MEdge *coarse_medge = coarse_mesh->medge;
811         const MLoop *coarse_mloop = coarse_mesh->mloop;
812         Mesh *subdiv_mesh = ctx->subdiv_mesh;
813         MVert *subdiv_mvert = subdiv_mesh->mvert;
814         const int poly_index = coarse_poly - coarse_mesh->mpoly;
815         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
816         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
817                 const MLoop *coarse_loop =
818                     &coarse_mloop[coarse_poly->loopstart + corner];
819                 if (BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_edges_used_map,
820                                                    coarse_loop->e))
821                 {
822                         continue;
823                 }
824                 vertex_interpolation_from_ptex(ctx,
825                                                vertex_interpolation,
826                                                coarse_poly,
827                                                corner);
828                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
829                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
830                 MVert *subdiv_vert = &subdiv_mvert[
831                         ctx->vertices_edge_offset +
832                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge];
833                 for (int vertex_index = 0;
834                      vertex_index < num_subdiv_vertices_per_coarse_edge;
835                      vertex_index++, subdiv_vert++)
836                 {
837                         float fac = (vertex_index + 1) * inv_resolution_1;
838                         if (flip) {
839                                 fac = 1.0f - fac;
840                         }
841                         if (corner >= 2) {
842                                 fac = 1.0f - fac;
843                         }
844                         float u, v;
845                         if ((corner & 1) == 0) {
846                                 u = fac;
847                                 v = (corner == 2) ? 1.0f : 0.0f;
848                         }
849                         else {
850                                 u = (corner == 1) ? 1.0f : 0.0f;
851                                 v = fac;
852                         }
853                         subdiv_vertex_data_interpolate(ctx,
854                                                        subdiv_vert,
855                                                        vertex_interpolation,
856                                                        u, v);
857                         BKE_subdiv_eval_limit_point_and_short_normal(
858                                 subdiv,
859                                 ptex_face_index,
860                                 u, v,
861                                 subdiv_vert->co, subdiv_vert->no);
862                 }
863         }
864 }
865
866 static void subdiv_evaluate_edge_vertices_special(
867         SubdivMeshContext *ctx,
868         const MPoly *coarse_poly,
869         VerticesForInterpolation *vertex_interpolation)
870 {
871         const int resolution = ctx->settings->resolution;
872         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
873         const int num_vertices_per_ptex_edge = ((resolution >> 1) + 1);
874         const float inv_ptex_resolution_1 =
875                 1.0f / (float)(num_vertices_per_ptex_edge - 1);
876         Subdiv *subdiv = ctx->subdiv;
877         const Mesh *coarse_mesh = ctx->coarse_mesh;
878         const MEdge *coarse_medge = coarse_mesh->medge;
879         const MLoop *coarse_mloop = coarse_mesh->mloop;
880         Mesh *subdiv_mesh = ctx->subdiv_mesh;
881         MVert *subdiv_mvert = subdiv_mesh->mvert;
882         const int poly_index = coarse_poly - coarse_mesh->mpoly;
883         const int ptex_face_start_index = ctx->face_ptex_offset[poly_index];
884         int ptex_face_index = ptex_face_start_index;
885         for (int corner = 0;
886              corner < coarse_poly->totloop;
887              corner++, ptex_face_index++)
888         {
889                 const MLoop *coarse_loop =
890                         &coarse_mloop[coarse_poly->loopstart + corner];
891                 if (BLI_BITMAP_TEST_AND_SET_ATOMIC(ctx->coarse_edges_used_map,
892                                                    coarse_loop->e))
893                 {
894                         continue;
895                 }
896                 vertex_interpolation_from_ptex(ctx,
897                                                vertex_interpolation,
898                                                coarse_poly,
899                                                corner);
900                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
901                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
902                 MVert *subdiv_vert = &subdiv_mvert[
903                         ctx->vertices_edge_offset +
904                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge];
905                 int veretx_delta = 1;
906                 if (flip) {
907                         subdiv_vert += num_subdiv_vertices_per_coarse_edge - 1;
908                         veretx_delta = -1;
909                 }
910                 for (int vertex_index = 1;
911                      vertex_index < num_vertices_per_ptex_edge;
912                      vertex_index++, subdiv_vert += veretx_delta)
913                 {
914                         float u = vertex_index * inv_ptex_resolution_1;
915                         subdiv_vertex_data_interpolate(ctx,
916                                                        subdiv_vert,
917                                                        vertex_interpolation,
918                                                        u, 0.0f);
919                         BKE_subdiv_eval_limit_point_and_short_normal(
920                                 subdiv,
921                                 ptex_face_index,
922                                 u, 0.0f,
923                                 subdiv_vert->co, subdiv_vert->no);
924                 }
925                 const int next_ptex_face_index =
926                         ptex_face_start_index + (corner + 1) % coarse_poly->totloop;
927                 for (int vertex_index = 1;
928                      vertex_index < num_vertices_per_ptex_edge - 1;
929                      vertex_index++, subdiv_vert += veretx_delta)
930                 {
931                         float v = 1.0f - vertex_index * inv_ptex_resolution_1;
932                         subdiv_vertex_data_interpolate(ctx,
933                                                        subdiv_vert,
934                                                        vertex_interpolation,
935                                                        0.0f, v);
936                         BKE_subdiv_eval_limit_point_and_short_normal(
937                                 subdiv,
938                                 next_ptex_face_index,
939                                 0.0f, v,
940                                 subdiv_vert->co, subdiv_vert->no);
941                 }
942         }
943 }
944
945 static void subdiv_evaluate_edge_vertices(
946         SubdivMeshContext *ctx,
947         const MPoly *coarse_poly,
948         VerticesForInterpolation *vertex_interpolation)
949 {
950         if (coarse_poly->totloop == 4) {
951                 subdiv_evaluate_edge_vertices_regular(
952                         ctx, coarse_poly, vertex_interpolation);
953         }
954         else {
955                 subdiv_evaluate_edge_vertices_special(
956                         ctx, coarse_poly, vertex_interpolation);
957         }
958 }
959
960 /* Evaluation of inner vertices, they are coming from ptex patches. */
961
962 static void subdiv_evaluate_inner_vertices_regular(
963         SubdivMeshContext *ctx,
964         const MPoly *coarse_poly,
965         VerticesForInterpolation *vertex_interpolation)
966 {
967         const int resolution = ctx->settings->resolution;
968         const float inv_resolution_1 = 1.0f / (float)(resolution - 1);
969         Subdiv *subdiv = ctx->subdiv;
970         const Mesh *coarse_mesh = ctx->coarse_mesh;
971         Mesh *subdiv_mesh = ctx->subdiv_mesh;
972         MVert *subdiv_mvert = subdiv_mesh->mvert;
973         const int poly_index = coarse_poly - coarse_mesh->mpoly;
974         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
975         const int start_vertex_index = ctx->subdiv_vertex_offset[poly_index];
976         MVert *subdiv_vert =
977                 &subdiv_mvert[ctx->vertices_inner_offset + start_vertex_index];
978         vertex_interpolation_from_ptex(ctx,
979                                        vertex_interpolation,
980                                        coarse_poly,
981                                        0);
982         for (int y = 1; y < resolution - 1; y++) {
983                 const float v = y * inv_resolution_1;
984                 for (int x = 1; x < resolution - 1; x++, subdiv_vert++) {
985                         const float u = x * inv_resolution_1;
986                         subdiv_vertex_data_interpolate(ctx,
987                                                        subdiv_vert,
988                                                        vertex_interpolation,
989                                                        u, v);
990                         BKE_subdiv_eval_limit_point_and_short_normal(
991                                 subdiv,
992                                 ptex_face_index,
993                                 u, v,
994                                 subdiv_vert->co, subdiv_vert->no);
995                 }
996         }
997 }
998
999 static void subdiv_evaluate_inner_vertices_special(
1000         SubdivMeshContext *ctx,
1001         const MPoly *coarse_poly,
1002         VerticesForInterpolation *vertex_interpolation)
1003 {
1004         const int resolution = ctx->settings->resolution;
1005         const int ptex_face_resolution = ptex_face_resolution_get(
1006                 coarse_poly, resolution);
1007         const float inv_ptex_face_resolution_1 =
1008                 1.0f / (float)(ptex_face_resolution - 1);
1009         Subdiv *subdiv = ctx->subdiv;
1010         const Mesh *coarse_mesh = ctx->coarse_mesh;
1011         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1012         MVert *subdiv_mvert = subdiv_mesh->mvert;
1013         const int poly_index = coarse_poly - coarse_mesh->mpoly;
1014         int ptex_face_index = ctx->face_ptex_offset[poly_index];
1015         const int start_vertex_index = ctx->subdiv_vertex_offset[poly_index];
1016         MVert *subdiv_vert =
1017                 &subdiv_mvert[ctx->vertices_inner_offset + start_vertex_index];
1018         vertex_interpolation_from_ptex(ctx,
1019                                        vertex_interpolation,
1020                                        coarse_poly,
1021                                        0);
1022         subdiv_vertex_data_interpolate(ctx,
1023                                        subdiv_vert,
1024                                        vertex_interpolation,
1025                                        1.0f, 1.0f);
1026         BKE_subdiv_eval_limit_point_and_short_normal(
1027                 subdiv,
1028                 ptex_face_index,
1029                 1.0f, 1.0f,
1030                 subdiv_vert->co, subdiv_vert->no);
1031         subdiv_vert++;
1032         for (int corner = 0;
1033              corner < coarse_poly->totloop;
1034              corner++, ptex_face_index++)
1035         {
1036                 if (corner != 0) {
1037                         vertex_interpolation_from_ptex(ctx,
1038                                                        vertex_interpolation,
1039                                                        coarse_poly,
1040                                                        corner);
1041                 }
1042                 for (int y = 1; y < ptex_face_resolution - 1; y++) {
1043                         const float v = y * inv_ptex_face_resolution_1;
1044                         for (int x = 1; x < ptex_face_resolution; x++, subdiv_vert++) {
1045                                 const float u = x * inv_ptex_face_resolution_1;
1046                                 subdiv_vertex_data_interpolate(ctx,
1047                                                                subdiv_vert,
1048                                                                vertex_interpolation,
1049                                                                u, v);
1050                                 BKE_subdiv_eval_limit_point_and_short_normal(
1051                                         subdiv,
1052                                         ptex_face_index,
1053                                         u, v,
1054                                         subdiv_vert->co, subdiv_vert->no);
1055                         }
1056                 }
1057         }
1058 }
1059
1060 static void subdiv_evaluate_inner_vertices(
1061         SubdivMeshContext *ctx,
1062         const MPoly *coarse_poly,
1063         VerticesForInterpolation *vertex_interpolation)
1064 {
1065         if (coarse_poly->totloop == 4) {
1066                 subdiv_evaluate_inner_vertices_regular(
1067                         ctx, coarse_poly, vertex_interpolation);
1068         }
1069         else {
1070                 subdiv_evaluate_inner_vertices_special(
1071                         ctx, coarse_poly, vertex_interpolation);
1072         }
1073 }
1074
1075 /* Evaluate all vertices which are emitted from given coarse polygon. */
1076 static void subdiv_evaluate_vertices(SubdivMeshContext *ctx,
1077                                      const int poly_index)
1078 {
1079         /* Base/coarse mesh information. */
1080         const Mesh *coarse_mesh = ctx->coarse_mesh;
1081         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1082         const MPoly *coarse_poly = &coarse_mpoly[poly_index];
1083         /* Initialize vertex interpolation, it is reused by corner vertices, coarse
1084          * edges and patch evaluation.
1085          */
1086         VerticesForInterpolation vertex_interpolation;
1087         vertex_interpolation_init(ctx, &vertex_interpolation, coarse_poly);
1088         (void) vertex_interpolation;
1089         subdiv_evaluate_corner_vertices(ctx, coarse_poly);
1090         subdiv_evaluate_edge_vertices(ctx, coarse_poly, &vertex_interpolation);
1091         subdiv_evaluate_inner_vertices(ctx, coarse_poly, &vertex_interpolation);
1092         vertex_interpolation_end(&vertex_interpolation);
1093 }
1094
1095 /* =============================================================================
1096  * Edge subdivision process.
1097  */
1098
1099 static void subdiv_copy_edge_data(
1100         SubdivMeshContext *ctx,
1101         MEdge *subdiv_edge,
1102         const MEdge *coarse_edge)
1103 {
1104         const int subdiv_edge_index = subdiv_edge - ctx->subdiv_mesh->medge;
1105         if (coarse_edge == NULL) {
1106                 subdiv_edge->crease = 0;
1107                 subdiv_edge->bweight = 0;
1108                 subdiv_edge->flag = 0;
1109                 if (ctx->edge_origindex != NULL) {
1110                         ctx->edge_origindex[subdiv_edge_index] = ORIGINDEX_NONE;
1111                 }
1112                 return;
1113         }
1114         const int coarse_edge_index = coarse_edge - ctx->coarse_mesh->medge;
1115         CustomData_copy_data(&ctx->coarse_mesh->edata,
1116                              &ctx->subdiv_mesh->edata,
1117                              coarse_edge_index,
1118                              subdiv_edge_index,
1119                              1);
1120 }
1121
1122 static MEdge *subdiv_create_edges_row(SubdivMeshContext *ctx,
1123                                       MEdge *subdiv_edge,
1124                                       const MEdge *coarse_edge,
1125                                       const int start_vertex_index,
1126                                       const int num_edges_per_row)
1127 {
1128         int vertex_index = start_vertex_index;
1129         for (int edge_index = 0;
1130              edge_index < num_edges_per_row - 1;
1131              edge_index++, subdiv_edge++)
1132         {
1133                 subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge);
1134                 subdiv_edge->v1 = vertex_index;
1135                 subdiv_edge->v2 = vertex_index + 1;
1136                 vertex_index += 1;
1137         }
1138         return subdiv_edge;
1139 }
1140
1141 static MEdge *subdiv_create_edges_column(SubdivMeshContext *ctx,
1142                                          MEdge *subdiv_edge,
1143                                          const MEdge *coarse_start_edge,
1144                                          const MEdge *coarse_end_edge,
1145                                          const int start_vertex_index,
1146                                          const int num_edges_per_row)
1147 {
1148         int vertex_index = start_vertex_index;
1149         for (int edge_index = 0;
1150              edge_index < num_edges_per_row;
1151              edge_index++, subdiv_edge++)
1152         {
1153                 const MEdge *coarse_edge = NULL;
1154                 if (edge_index == 0) {
1155                         coarse_edge = coarse_start_edge;
1156                 }
1157                 else if (edge_index == num_edges_per_row - 1) {
1158                         coarse_edge = coarse_end_edge;
1159                 }
1160                 subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge);
1161                 subdiv_edge->v1 = vertex_index;
1162                 subdiv_edge->v2 = vertex_index + num_edges_per_row;
1163                 vertex_index += 1;
1164         }
1165         return subdiv_edge;
1166 }
1167
1168 /* Create edges between inner vertices of patch, and also edges to the
1169  * boundary.
1170  */
1171
1172 /* Consider a subdivision of base face at level 1:
1173  *
1174  *  y
1175  *  ^
1176  *  |   (6) ---- (7) ---- (8)
1177  *  |    |        |        |
1178  *  |   (3) ---- (4) ---- (5)
1179  *  |    |        |        |
1180  *  |   (0) ---- (1) ---- (2)
1181  *  o---------------------------> x
1182  *
1183  * This is illustrate which parts of geometry is created by code below.
1184  */
1185
1186 static void subdiv_create_edges_all_patches_regular(
1187         SubdivMeshContext *ctx,
1188         const MPoly *coarse_poly)
1189 {
1190         const Mesh *coarse_mesh = ctx->coarse_mesh;
1191         const MEdge *coarse_medge = coarse_mesh->medge;
1192         const MLoop *coarse_mloop = coarse_mesh->mloop;
1193         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1194         const int poly_index = coarse_poly - coarse_mpoly;
1195         const int resolution = ctx->settings->resolution;
1196         const int start_vertex_index =
1197                 ctx->vertices_inner_offset +
1198                 ctx->subdiv_vertex_offset[poly_index];
1199         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1200         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1201         MEdge *subdiv_medge = subdiv_mesh->medge;
1202         MEdge *subdiv_edge = &subdiv_medge[
1203                 ctx->edge_inner_offset + ctx->subdiv_edge_offset[poly_index]];
1204         /* Create bottom row of edges (0-1, 1-2). */
1205         subdiv_edge = subdiv_create_edges_row(
1206                 ctx,
1207                 subdiv_edge,
1208                 NULL,
1209                 start_vertex_index,
1210                 resolution - 2);
1211         /* Create remaining edges. */
1212         for (int row = 0; row < resolution - 3; row++) {
1213                 const int start_row_vertex_index =
1214                         start_vertex_index + row * (resolution - 2);
1215                 /* Create vertical columns.
1216                  *
1217                  * At first iteration it will be edges (0-3. 1-4, 2-5), then it
1218                  * will be (3-6, 4-7, 5-8) and so on.
1219                  */
1220                 subdiv_edge = subdiv_create_edges_column(
1221                         ctx,
1222                         subdiv_edge,
1223                         NULL,
1224                         NULL,
1225                         start_row_vertex_index,
1226                         resolution - 2);
1227                 /* Create horizontal edge row.
1228                  *
1229                  * At first iteration it will be edges (3-4, 4-5), then it will be
1230                  * (6-7, 7-8) and so on.
1231                  */
1232                 subdiv_edge = subdiv_create_edges_row(
1233                         ctx,
1234                         subdiv_edge,
1235                         NULL,
1236                         start_row_vertex_index + resolution - 2,
1237                         resolution - 2);
1238         }
1239         /* Connect inner part of patch to boundary. */
1240         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1241                 const MLoop *coarse_loop =
1242                         &coarse_mloop[coarse_poly->loopstart + corner];
1243                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1244                 const int start_edge_vertex = ctx->vertices_edge_offset +
1245                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1246                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
1247                 int side_start_index = start_vertex_index;
1248                 int side_stride = 0;
1249                 /* Calculate starting veretx of corresponding inner part of ptex. */
1250                 if (corner == 0) {
1251                         side_stride = 1;
1252                 }
1253                 else if (corner == 1) {
1254                         side_start_index += resolution - 3;
1255                         side_stride = resolution - 2;
1256                 }
1257                 else if (corner == 2) {
1258                         side_start_index += num_subdiv_vertices_per_coarse_edge *
1259                                             num_subdiv_vertices_per_coarse_edge - 1;
1260                         side_stride = -1;
1261                 }
1262                 else if (corner == 3) {
1263                         side_start_index += num_subdiv_vertices_per_coarse_edge *
1264                                             (num_subdiv_vertices_per_coarse_edge - 1);
1265                         side_stride = -(resolution - 2);
1266                 }
1267                 for (int i = 0; i < resolution - 2; i++, subdiv_edge++) {
1268                         subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1269                         if (flip) {
1270                                 subdiv_edge->v1 = start_edge_vertex + (resolution - i - 3);
1271                         }
1272                         else {
1273                                 subdiv_edge->v1 = start_edge_vertex + i;
1274                         }
1275                         subdiv_edge->v2 = side_start_index + side_stride * i;
1276                 }
1277         }
1278 }
1279
1280 static void subdiv_create_edges_all_patches_special(
1281         SubdivMeshContext *ctx,
1282         const MPoly *coarse_poly)
1283 {
1284         const Mesh *coarse_mesh = ctx->coarse_mesh;
1285         const MEdge *coarse_medge = coarse_mesh->medge;
1286         const MLoop *coarse_mloop = coarse_mesh->mloop;
1287         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1288         const int poly_index = coarse_poly - coarse_mpoly;
1289         const int resolution = ctx->settings->resolution;
1290         const int ptex_face_resolution =
1291                 ptex_face_resolution_get(coarse_poly, resolution);
1292         const int ptex_face_inner_resolution = ptex_face_resolution - 2;
1293         const int num_inner_vertices_per_ptex =
1294                 (ptex_face_resolution - 1) * (ptex_face_resolution - 2);
1295         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1296         const int center_vertex_index =
1297                 ctx->vertices_inner_offset +
1298                 ctx->subdiv_vertex_offset[poly_index];
1299         const int start_vertex_index = center_vertex_index + 1;
1300         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1301         MEdge *subdiv_medge = subdiv_mesh->medge;
1302         MEdge *subdiv_edge = &subdiv_medge[
1303                 ctx->edge_inner_offset + ctx->subdiv_edge_offset[poly_index]];
1304         /* Create inner ptex edges. */
1305         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1306                 const int start_ptex_face_vertex_index =
1307                         start_vertex_index + corner * num_inner_vertices_per_ptex;
1308                 /* Similar steps to regular patch case. */
1309                 subdiv_edge = subdiv_create_edges_row(
1310                         ctx,
1311                         subdiv_edge,
1312                         NULL,
1313                         start_ptex_face_vertex_index,
1314                         ptex_face_inner_resolution + 1);
1315                 for (int row = 0; row < ptex_face_inner_resolution - 1; row++) {
1316                         const int start_row_vertex_index =
1317                                 start_ptex_face_vertex_index +
1318                                 row * (ptex_face_inner_resolution + 1);
1319                         subdiv_edge = subdiv_create_edges_column(
1320                                 ctx,
1321                                 subdiv_edge,
1322                                 NULL,
1323                                 NULL,
1324                                 start_row_vertex_index,
1325                                 ptex_face_inner_resolution + 1);
1326                         subdiv_edge = subdiv_create_edges_row(
1327                                 ctx,
1328                                 subdiv_edge,
1329                                 NULL,
1330                                 start_row_vertex_index + ptex_face_inner_resolution + 1,
1331                                 ptex_face_inner_resolution + 1);
1332                 }
1333         }
1334         /* Create connections between ptex faces. */
1335         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1336                 const int next_corner = (corner + 1) % coarse_poly->totloop;
1337                 int current_patch_vertex_index =
1338                         start_vertex_index + corner * num_inner_vertices_per_ptex +
1339                         ptex_face_inner_resolution;
1340                 int next_path_vertex_index =
1341                         start_vertex_index + next_corner * num_inner_vertices_per_ptex +
1342                         num_inner_vertices_per_ptex - ptex_face_resolution + 1;
1343                 for (int row = 0;
1344                      row < ptex_face_inner_resolution;
1345                      row++, subdiv_edge++)
1346                 {
1347                         subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1348                         subdiv_edge->v1 = current_patch_vertex_index;
1349                         subdiv_edge->v2 = next_path_vertex_index;
1350                         current_patch_vertex_index += ptex_face_inner_resolution + 1;
1351                         next_path_vertex_index += 1;
1352                 }
1353         }
1354         /* Create edges from center. */
1355         if (ptex_face_resolution >= 3) {
1356                 for (int corner = 0;
1357                      corner < coarse_poly->totloop;
1358                      corner++, subdiv_edge++)
1359                 {
1360                         const int current_patch_end_vertex_index =
1361                                 start_vertex_index + corner * num_inner_vertices_per_ptex +
1362                                 num_inner_vertices_per_ptex - 1;
1363                         subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1364                         subdiv_edge->v1 = center_vertex_index;
1365                         subdiv_edge->v2 = current_patch_end_vertex_index;
1366                 }
1367         }
1368         /* Connect inner path of patch to boundary. */
1369         const MLoop *prev_coarse_loop =
1370                 &coarse_mloop[coarse_poly->loopstart + coarse_poly->totloop - 1];
1371         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1372                 const MLoop *coarse_loop =
1373                         &coarse_mloop[coarse_poly->loopstart + corner];
1374                 {
1375                         const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1376                         const int start_edge_vertex = ctx->vertices_edge_offset +
1377                                 coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1378                         const bool flip = (coarse_edge->v2 == coarse_loop->v);
1379                         int side_start_index;
1380                         if (ptex_face_resolution >= 3) {
1381                                 side_start_index =
1382                                         start_vertex_index + num_inner_vertices_per_ptex * corner;
1383                         }
1384                         else {
1385                                 side_start_index = center_vertex_index;
1386                         }
1387                         for (int i = 0; i < ptex_face_resolution - 1; i++, subdiv_edge++) {
1388                                 subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1389                                 if (flip) {
1390                                         subdiv_edge->v1 = start_edge_vertex + (resolution - i - 3);
1391                                 }
1392                                 else {
1393                                         subdiv_edge->v1 = start_edge_vertex + i;
1394                                 }
1395                                 subdiv_edge->v2 = side_start_index + i;
1396                         }
1397                 }
1398                 if (ptex_face_resolution >= 3) {
1399                         const MEdge *coarse_edge = &coarse_medge[prev_coarse_loop->e];
1400                         const int start_edge_vertex = ctx->vertices_edge_offset +
1401                                 prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1402                         const bool flip = (coarse_edge->v2 == coarse_loop->v);
1403                         int side_start_index =
1404                                 start_vertex_index + num_inner_vertices_per_ptex * corner;
1405                         for (int i = 0; i < ptex_face_resolution - 2; i++, subdiv_edge++) {
1406                                 subdiv_copy_edge_data(ctx, subdiv_edge, NULL);
1407                                 if (flip) {
1408                                         subdiv_edge->v1 = start_edge_vertex + (resolution - i - 3);
1409                                 }
1410                                 else {
1411                                         subdiv_edge->v1 = start_edge_vertex + i;
1412                                 }
1413                                 subdiv_edge->v2 = side_start_index +
1414                                                   (ptex_face_inner_resolution + 1) * i;
1415                         }
1416                 }
1417                 prev_coarse_loop = coarse_loop;
1418         }
1419 }
1420
1421 static void subdiv_create_edges_all_patches(
1422         SubdivMeshContext *ctx,
1423         const MPoly *coarse_poly)
1424 {
1425         if (coarse_poly->totloop == 4) {
1426                 subdiv_create_edges_all_patches_regular(ctx, coarse_poly);
1427         }
1428         else {
1429                 subdiv_create_edges_all_patches_special(ctx, coarse_poly);
1430         }
1431 }
1432
1433 static void subdiv_create_edges(SubdivMeshContext *ctx, int poly_index)
1434 {
1435         const Mesh *coarse_mesh = ctx->coarse_mesh;
1436         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1437         const MPoly *coarse_poly = &coarse_mpoly[poly_index];
1438         subdiv_create_edges_all_patches(ctx, coarse_poly);
1439 }
1440
1441 static void subdiv_create_boundary_edges(
1442         SubdivMeshContext *ctx,
1443         int edge_index)
1444 {
1445         const Mesh *coarse_mesh = ctx->coarse_mesh;
1446         const MEdge *coarse_medge = coarse_mesh->medge;
1447         const MEdge *coarse_edge = &coarse_medge[edge_index];
1448         const int resolution = ctx->settings->resolution;
1449         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1450         const int num_subdiv_edges_per_coarse_edge = resolution - 1;
1451         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1452         MEdge *subdiv_medge = subdiv_mesh->medge;
1453         MEdge *subdiv_edge = &subdiv_medge[
1454                 ctx->edge_boundary_offset +
1455                 edge_index * num_subdiv_edges_per_coarse_edge];
1456         int last_vertex_index = ctx->vertices_corner_offset + coarse_edge->v1;
1457         for (int i = 0;
1458              i < num_subdiv_edges_per_coarse_edge - 1;
1459              i++, subdiv_edge++)
1460         {
1461                 subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge);
1462                 subdiv_edge->v1 = last_vertex_index;
1463                 subdiv_edge->v2 =
1464                         ctx->vertices_edge_offset +
1465                         edge_index * num_subdiv_vertices_per_coarse_edge +
1466                         i;
1467                 last_vertex_index = subdiv_edge->v2;
1468         }
1469         subdiv_copy_edge_data(ctx, subdiv_edge, coarse_edge);
1470         subdiv_edge->v1 = last_vertex_index;
1471         subdiv_edge->v2 = ctx->vertices_corner_offset + coarse_edge->v2;
1472 }
1473
1474 /* =============================================================================
1475  * Loops creation/interpolation.
1476  */
1477
1478 static void subdiv_copy_loop_data(
1479         const SubdivMeshContext *ctx,
1480         MLoop *subdiv_loop,
1481         const LoopsForInterpolation *loop_interpolation,
1482         const float u, const float v)
1483 {
1484         const int subdiv_loop_index = subdiv_loop - ctx->subdiv_mesh->mloop;
1485         const float weights[4] = {(1.0f - u) * (1.0f - v),
1486                                   u * (1.0f - v),
1487                                   u * v,
1488                                   (1.0f - u) * v};
1489         CustomData_interp(loop_interpolation->loop_data,
1490                           &ctx->subdiv_mesh->ldata,
1491                           loop_interpolation->loop_indices,
1492                           weights, NULL,
1493                           4,
1494                           subdiv_loop_index);
1495         /* TODO(sergey): Set ORIGINDEX. */
1496 }
1497
1498 static void subdiv_eval_uv_layer(SubdivMeshContext *ctx,
1499                                  MLoop *subdiv_loop,
1500                                  const int ptex_face_index,
1501                                  const float u, const float v,
1502                                  const float du, const float dv)
1503 {
1504         if (ctx->num_uv_layers == 0) {
1505                 return;
1506         }
1507         Subdiv *subdiv = ctx->subdiv;
1508         const int mloop_index = subdiv_loop - ctx->subdiv_mesh->mloop;
1509         for (int layer_index = 0; layer_index < ctx->num_uv_layers; layer_index++) {
1510                 MLoopUV *subdiv_loopuv = &ctx->uv_layers[layer_index][mloop_index];
1511                 BKE_subdiv_eval_face_varying(subdiv,
1512                                              ptex_face_index,
1513                                              u, v,
1514                                              subdiv_loopuv[0].uv);
1515                 BKE_subdiv_eval_face_varying(subdiv,
1516                                              ptex_face_index,
1517                                              u + du, v,
1518                                              subdiv_loopuv[1].uv);
1519                 BKE_subdiv_eval_face_varying(subdiv,
1520                                              ptex_face_index,
1521                                              u + du, v + dv,
1522                                              subdiv_loopuv[2].uv);
1523                 BKE_subdiv_eval_face_varying(subdiv,
1524                                              ptex_face_index,
1525                                              u, v + dv,
1526                                              subdiv_loopuv[3].uv);
1527                 /* TODO(sergey): Currently evaluator only has single UV layer, so can
1528                  * not evaluate more than that. Need to be solved.
1529                  */
1530                 break;
1531         }
1532 }
1533
1534 static void rotate_indices(const int rot, int *a, int *b, int *c, int *d)
1535 {
1536         int values[4] = {*a, *b, *c, *d};
1537         *a = values[(0 - rot + 4) % 4];
1538         *b = values[(1 - rot + 4) % 4];
1539         *c = values[(2 - rot + 4) % 4];
1540         *d = values[(3 - rot + 4) % 4];
1541 }
1542
1543 static void subdiv_create_loops_of_poly(
1544         SubdivMeshContext *ctx,
1545         LoopsForInterpolation *loop_interpolation,
1546         MLoop *subdiv_loop_start,
1547         const int ptex_face_index,
1548         const int rotation,
1549         /*const*/ int v0, /*const*/ int e0,
1550         /*const*/ int v1, /*const*/ int e1,
1551         /*const*/ int v2, /*const*/ int e2,
1552         /*const*/ int v3, /*const*/ int e3,
1553         const float u, const float v,
1554         const float du, const float dv)
1555 {
1556         rotate_indices(rotation, &v0, &v1, &v2, &v3);
1557         rotate_indices(rotation, &e0, &e1, &e2, &e3);
1558         subdiv_copy_loop_data(ctx,
1559                               &subdiv_loop_start[0],
1560                               loop_interpolation,
1561                               u, v);
1562         subdiv_loop_start[0].v = v0;
1563         subdiv_loop_start[0].e = e0;
1564         subdiv_copy_loop_data(ctx,
1565                               &subdiv_loop_start[1],
1566                               loop_interpolation,
1567                               u + du, v);
1568         subdiv_loop_start[1].v = v1;
1569         subdiv_loop_start[1].e = e1;
1570         subdiv_copy_loop_data(ctx,
1571                               &subdiv_loop_start[2],
1572                               loop_interpolation,
1573                               u + du, v + dv);
1574         subdiv_loop_start[2].v = v2;
1575         subdiv_loop_start[2].e = e2;
1576         subdiv_copy_loop_data(ctx,
1577                               &subdiv_loop_start[3],
1578                               loop_interpolation,
1579                               u, v + dv);
1580         subdiv_loop_start[3].v = v3;
1581         subdiv_loop_start[3].e = e3;
1582         /* Interpolate UV layers using OpenSubdiv. */
1583         subdiv_eval_uv_layer(ctx,
1584                              subdiv_loop_start,
1585                              ptex_face_index,
1586                              u, v, du, dv);
1587 }
1588
1589 static void subdiv_create_loops_regular(SubdivMeshContext *ctx,
1590                                         const MPoly *coarse_poly)
1591 {
1592         const int resolution = ctx->settings->resolution;
1593         /* Base/coarse mesh information. */
1594         const Mesh *coarse_mesh = ctx->coarse_mesh;
1595         const MEdge *coarse_medge = coarse_mesh->medge;
1596         const MLoop *coarse_mloop = coarse_mesh->mloop;
1597         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1598         const int poly_index = coarse_poly - coarse_mpoly;
1599         const int ptex_resolution =
1600                 ptex_face_resolution_get(coarse_poly, resolution);
1601         const int ptex_inner_resolution = ptex_resolution - 2;
1602         const int num_subdiv_edges_per_coarse_edge = resolution - 1;
1603         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1604         const float inv_ptex_resolution_1 = 1.0f / (float)(ptex_resolution - 1);
1605         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
1606         const int start_vertex_index =
1607                 ctx->vertices_inner_offset +
1608                 ctx->subdiv_vertex_offset[poly_index];
1609         const int start_edge_index =
1610                 ctx->edge_inner_offset +
1611                 ctx->subdiv_edge_offset[poly_index];
1612         const int start_poly_index = ctx->subdiv_polygon_offset[poly_index];
1613         const int start_loop_index = 4 * start_poly_index;
1614         const float du = inv_ptex_resolution_1;
1615         const float dv = inv_ptex_resolution_1;
1616         /* Hi-poly subdivided mesh. */
1617         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1618         MLoop *subdiv_loopoop = subdiv_mesh->mloop;
1619         MLoop *subdiv_loop = &subdiv_loopoop[start_loop_index];
1620         LoopsForInterpolation loop_interpolation;
1621         loop_interpolation_init(ctx, &loop_interpolation, coarse_poly);
1622         loop_interpolation_from_ptex(ctx,
1623                                      &loop_interpolation,
1624                                      coarse_poly,
1625                                      0);
1626         /* Loops for inner part of ptex. */
1627         for (int y = 1; y < ptex_resolution - 2; y++) {
1628                 const float v = y * inv_ptex_resolution_1;
1629                 const int inner_y = y - 1;
1630                 for (int x = 1; x < ptex_resolution - 2; x++, subdiv_loop += 4) {
1631                         const int inner_x = x - 1;
1632                         const float u = x * inv_ptex_resolution_1;
1633                         /* Vertex indicies ordered counter-clockwise. */
1634                         const int v0 = start_vertex_index +
1635                                        (inner_y * ptex_inner_resolution + inner_x);
1636                         const int v1 = v0 + 1;
1637                         const int v2 = v0 + ptex_inner_resolution + 1;
1638                         const int v3 = v0 + ptex_inner_resolution;
1639                         /* Edge indicies ordered counter-clockwise. */
1640                         const int e0 = start_edge_index +
1641                                 (inner_y * (2 * ptex_inner_resolution - 1) + inner_x);
1642                         const int e1 = e0 + ptex_inner_resolution;
1643                         const int e2 = e0 + (2 * ptex_inner_resolution - 1);
1644                         const int e3 = e0 + ptex_inner_resolution - 1;
1645                         subdiv_create_loops_of_poly(
1646                                 ctx, &loop_interpolation, subdiv_loop, ptex_face_index, 0,
1647                                 v0, e0, v1, e1, v2, e2, v3, e3,
1648                                 u, v, du, dv);
1649                 }
1650         }
1651         /* Loops for faces connecting inner ptex part with boundary. */
1652         const MLoop *prev_coarse_loop =
1653                 &coarse_mloop[coarse_poly->loopstart + coarse_poly->totloop - 1];
1654         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1655                 const MLoop *coarse_loop =
1656                         &coarse_mloop[coarse_poly->loopstart + corner];
1657                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1658                 const MEdge *prev_coarse_edge = &coarse_medge[prev_coarse_loop->e];
1659                 const int start_edge_vertex = ctx->vertices_edge_offset +
1660                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1661                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
1662                 int side_start_index = start_vertex_index;
1663                 int side_stride = 0;
1664                 int v0 = ctx->vertices_corner_offset + coarse_loop->v;
1665                 int v3, e3;
1666                 int e2_offset, e2_stride;
1667                 float u, v, delta_u, delta_v;
1668                 if (prev_coarse_loop->v == prev_coarse_edge->v1) {
1669                         v3 = ctx->vertices_edge_offset +
1670                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge +
1671                         num_subdiv_vertices_per_coarse_edge - 1;
1672                         e3 = ctx->edge_boundary_offset +
1673                                  prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1674                                  num_subdiv_edges_per_coarse_edge - 1;
1675                 }
1676                 else {
1677                         v3 = ctx->vertices_edge_offset +
1678                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1679                         e3 = ctx->edge_boundary_offset +
1680                                  prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge;
1681                 }
1682                 /* Calculate starting veretx of corresponding inner part of ptex. */
1683                 if (corner == 0) {
1684                         side_stride = 1;
1685                         e2_offset = 0;
1686                         e2_stride = 1;
1687                         u = 0.0f;
1688                         v = 0.0f;
1689                         delta_u = du;
1690                         delta_v = 0.0f;
1691                 }
1692                 else if (corner == 1) {
1693                         side_start_index += resolution - 3;
1694                         side_stride = resolution - 2;
1695                         e2_offset = 2 * num_subdiv_edges_per_coarse_edge - 4;
1696                         e2_stride = 2 * num_subdiv_edges_per_coarse_edge - 3;
1697                         u = 1.0f - du;
1698                         v = 0;
1699                         delta_u = 0.0f;
1700                         delta_v = dv;
1701                 }
1702                 else if (corner == 2) {
1703                         side_start_index += num_subdiv_vertices_per_coarse_edge *
1704                                             num_subdiv_vertices_per_coarse_edge - 1;
1705                         side_stride = -1;
1706                         e2_offset = num_edges_per_ptex_face_get(resolution - 2) - 1;
1707                         e2_stride = -1;
1708                         u = 1.0f - du;
1709                         v = 1.0f - dv;
1710                         delta_u = -du;
1711                         delta_v = 0.0f;
1712                 }
1713                 else if (corner == 3) {
1714                         side_start_index += num_subdiv_vertices_per_coarse_edge *
1715                                             (num_subdiv_vertices_per_coarse_edge - 1);
1716                         side_stride = -(resolution - 2);
1717                         e2_offset = num_edges_per_ptex_face_get(resolution - 2) -
1718                                     (2 * num_subdiv_edges_per_coarse_edge - 3);
1719                         e2_stride = -(2 * num_subdiv_edges_per_coarse_edge - 3);
1720                         u = 0.0f;
1721                         v = 1.0f - dv;
1722                         delta_u = 0.0f;
1723                         delta_v = -dv;
1724                 }
1725                 for (int i = 0; i < resolution - 2; i++, subdiv_loop += 4) {
1726                         int v1;
1727                         if (flip) {
1728                                 v1 = start_edge_vertex + (resolution - i - 3);
1729                         }
1730                         else {
1731                                 v1 = start_edge_vertex + i;
1732                         }
1733                         const int v2 = side_start_index + side_stride * i;
1734                         int e0;
1735                         if (flip) {
1736                                 e0 = ctx->edge_boundary_offset +
1737                                          coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1738                                          num_subdiv_edges_per_coarse_edge - i - 1;
1739                         }
1740                         else {
1741                                 e0 = ctx->edge_boundary_offset +
1742                                          coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1743                                          i;
1744                         }
1745                         int e1 = start_edge_index +
1746                                 num_edges_per_ptex_face_get(resolution - 2) +
1747                                 corner * num_subdiv_vertices_per_coarse_edge +
1748                                 i;
1749                         int e2;
1750                         if (i == 0) {
1751                                 e2 = start_edge_index +
1752                                         num_edges_per_ptex_face_get(resolution - 2) +
1753                                         ((corner - 1 + coarse_poly->totloop) %
1754                                                 coarse_poly->totloop) *
1755                                                         num_subdiv_vertices_per_coarse_edge +
1756                                         num_subdiv_vertices_per_coarse_edge - 1;
1757                         }
1758                         else {
1759                                 e2 = start_edge_index + e2_offset + e2_stride * (i - 1);
1760                         }
1761                         subdiv_create_loops_of_poly(
1762                                 ctx, &loop_interpolation, subdiv_loop,
1763                                 ptex_face_index, corner,
1764                                 v0, e0, v1, e1, v2, e2, v3, e3,
1765                                 u + delta_u * i, v + delta_v * i, du, dv);
1766                         v0 = v1;
1767                         v3 = v2;
1768                         e3 = e1;
1769                 }
1770                 prev_coarse_loop = coarse_loop;
1771         }
1772         loop_interpolation_end(&loop_interpolation);
1773 }
1774
1775 static void subdiv_create_loops_special(SubdivMeshContext *ctx,
1776                                         const MPoly *coarse_poly)
1777 {
1778         const int resolution = ctx->settings->resolution;
1779         /* Base/coarse mesh information. */
1780         const Mesh *coarse_mesh = ctx->coarse_mesh;
1781         const MEdge *coarse_medge = coarse_mesh->medge;
1782         const MLoop *coarse_mloop = coarse_mesh->mloop;
1783         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1784         const int poly_index = coarse_poly - coarse_mpoly;
1785         const int ptex_face_resolution =
1786                 ptex_face_resolution_get(coarse_poly, resolution);
1787         const int ptex_face_inner_resolution = ptex_face_resolution - 2;
1788         const float inv_ptex_resolution_1 =
1789                1.0f / (float)(ptex_face_resolution - 1);
1790         const int num_inner_vertices_per_ptex =
1791                 (ptex_face_resolution - 1) * (ptex_face_resolution - 2);
1792         const int num_inner_edges_per_ptex_face =
1793                 num_inner_edges_per_ptex_face_get(
1794                         ptex_face_inner_resolution + 1);
1795         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
1796         const int num_subdiv_edges_per_coarse_edge = resolution - 1;
1797         const int ptex_face_index = ctx->face_ptex_offset[poly_index];
1798         const int center_vertex_index =
1799                 ctx->vertices_inner_offset +
1800                 ctx->subdiv_vertex_offset[poly_index];
1801         const int start_vertex_index = center_vertex_index + 1;
1802         const int start_inner_vertex_index = center_vertex_index + 1;
1803         const int start_edge_index = ctx->edge_inner_offset +
1804                                      ctx->subdiv_edge_offset[poly_index];
1805         const int start_poly_index = ctx->subdiv_polygon_offset[poly_index];
1806         const int start_loop_index = 4 * start_poly_index;
1807         const float du = inv_ptex_resolution_1;
1808         const float dv = inv_ptex_resolution_1;
1809         /* Hi-poly subdivided mesh. */
1810         Mesh *subdiv_mesh = ctx->subdiv_mesh;
1811         MLoop *subdiv_loopoop = subdiv_mesh->mloop;
1812         MLoop *subdiv_loop = &subdiv_loopoop[start_loop_index];
1813         LoopsForInterpolation loop_interpolation;
1814         loop_interpolation_init(ctx, &loop_interpolation, coarse_poly);
1815         for (int corner = 0;
1816              corner < coarse_poly->totloop;
1817              corner++)
1818         {
1819                 const int corner_vertex_index =
1820                         start_vertex_index + corner * num_inner_vertices_per_ptex;
1821                 const int corner_edge_index =
1822                         start_edge_index + corner * num_inner_edges_per_ptex_face;
1823                 loop_interpolation_from_ptex(ctx,
1824                                              &loop_interpolation,
1825                                              coarse_poly,
1826                                              corner);
1827                 for (int y = 1; y < ptex_face_inner_resolution; y++) {
1828                         const float v = y * inv_ptex_resolution_1;
1829                         const int inner_y = y - 1;
1830                         for (int x = 1;
1831                              x < ptex_face_inner_resolution + 1;
1832                              x++, subdiv_loop += 4)
1833                         {
1834                                 const int inner_x = x - 1;
1835                                 const float u = x * inv_ptex_resolution_1;
1836                                 /* Vertex indicies ordered counter-clockwise. */
1837                                 const int v0 =
1838                                         corner_vertex_index +
1839                                         (inner_y * (ptex_face_inner_resolution + 1) + inner_x);
1840                                 const int v1 = v0 + 1;
1841                                 const int v2 = v0 + ptex_face_inner_resolution + 2;
1842                                 const int v3 = v0 + ptex_face_inner_resolution + 1;
1843                                 /* Edge indicies ordered counter-clockwise. */
1844                                 const int e0 = corner_edge_index +
1845                                           (inner_y * (2 * ptex_face_inner_resolution + 1) + inner_x);
1846                                 const int e1 = e0 + ptex_face_inner_resolution + 1;
1847                                 const int e2 = e0 + (2 * ptex_face_inner_resolution + 1);
1848                                 const int e3 = e0 + ptex_face_inner_resolution;
1849                                 subdiv_create_loops_of_poly(
1850                                         ctx, &loop_interpolation, subdiv_loop,
1851                                         ptex_face_index + corner, 0,
1852                                         v0, e0, v1, e1, v2, e2, v3, e3,
1853                                         u, v, du, dv);
1854                         }
1855                 }
1856         }
1857         /* Create connections between ptex faces. */
1858         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1859                 const int next_corner = (corner + 1) % coarse_poly->totloop;
1860                 const int corner_edge_index =
1861                         start_edge_index + corner * num_inner_edges_per_ptex_face;
1862                 const int next_corner_edge_index =
1863                         start_edge_index + next_corner * num_inner_edges_per_ptex_face;
1864                 int current_patch_vertex_index =
1865                         start_inner_vertex_index +
1866                         corner * num_inner_vertices_per_ptex +
1867                         ptex_face_inner_resolution;
1868                 int next_path_vertex_index =
1869                         start_inner_vertex_index +
1870                         next_corner * num_inner_vertices_per_ptex +
1871                         num_inner_vertices_per_ptex - ptex_face_resolution + 1;
1872                 int v0 = current_patch_vertex_index;
1873                 int v1 = next_path_vertex_index;
1874                 current_patch_vertex_index += ptex_face_inner_resolution + 1;
1875                 next_path_vertex_index += 1;
1876                 int e0 = start_edge_index +
1877                          coarse_poly->totloop * num_inner_edges_per_ptex_face +
1878                          corner * (ptex_face_resolution - 2);
1879                 int e1 = next_corner_edge_index + num_inner_edges_per_ptex_face -
1880                          ptex_face_resolution + 2;
1881                 int e3 = corner_edge_index + 2 * ptex_face_resolution - 4;
1882                 loop_interpolation_from_ptex(ctx,
1883                                              &loop_interpolation,
1884                                              coarse_poly,
1885                                              next_corner);
1886                 for (int row = 1;
1887                      row < ptex_face_inner_resolution;
1888                      row++, subdiv_loop += 4)
1889                 {
1890                         const int v2 = next_path_vertex_index;
1891                         const int v3 = current_patch_vertex_index;
1892                         const int e2 = e0 + 1;
1893                         const float u = row * du;
1894                         const float v = 1.0f - dv;
1895                         subdiv_create_loops_of_poly(
1896                                 ctx, &loop_interpolation, subdiv_loop,
1897                                 ptex_face_index + next_corner, 3,
1898                                 v0, e0, v1, e1, v2, e2, v3, e3,
1899                                 u, v, du, dv);
1900                         current_patch_vertex_index += ptex_face_inner_resolution + 1;
1901                         next_path_vertex_index += 1;
1902                         v0 = v3;
1903                         v1 = v2;
1904                         e0 = e2;
1905                         e1 += 1;
1906                         e3 += 2 * ptex_face_resolution - 3;
1907                 }
1908         }
1909         /* Create loops from center. */
1910         if (ptex_face_resolution >= 3) {
1911                 const int start_center_edge_index =
1912                         start_edge_index +
1913                         (num_inner_edges_per_ptex_face +
1914                          ptex_face_inner_resolution) * coarse_poly->totloop;
1915                 const int start_boundary_edge =
1916                         start_edge_index +
1917                         coarse_poly->totloop * num_inner_edges_per_ptex_face +
1918                         ptex_face_inner_resolution - 1;
1919                 for (int corner = 0, prev_corner = coarse_poly->totloop - 1;
1920                      corner < coarse_poly->totloop;
1921                      prev_corner = corner, corner++, subdiv_loop += 4)
1922                 {
1923                         loop_interpolation_from_ptex(ctx,
1924                                                      &loop_interpolation,
1925                                                      coarse_poly,
1926                                                      corner);
1927                         const int corner_edge_index =
1928                                 start_edge_index +
1929                                 corner * num_inner_edges_per_ptex_face;
1930                         const int current_patch_end_vertex_index =
1931                                 start_vertex_index + corner * num_inner_vertices_per_ptex +
1932                                 num_inner_vertices_per_ptex - 1;
1933                         const int prev_current_patch_end_vertex_index =
1934                                 start_vertex_index + prev_corner *
1935                                         num_inner_vertices_per_ptex +
1936                                 num_inner_vertices_per_ptex - 1;
1937                         const int v0 = center_vertex_index;
1938                         const int v1 = prev_current_patch_end_vertex_index;
1939                         const int v2 = current_patch_end_vertex_index - 1;
1940                         const int v3 = current_patch_end_vertex_index;
1941                         const int e0 = start_center_edge_index + prev_corner;
1942                         const int e1 = start_boundary_edge +
1943                                        prev_corner * (ptex_face_inner_resolution);
1944                         const int e2 = corner_edge_index +
1945                                        num_inner_edges_per_ptex_face - 1;
1946                         const int e3 = start_center_edge_index + corner;
1947                         const float u = 1.0f - du;
1948                         const float v = 1.0f - dv;
1949                         subdiv_create_loops_of_poly(
1950                                 ctx, &loop_interpolation, subdiv_loop,
1951                                 ptex_face_index + corner, 2,
1952                                 v0, e0, v1, e1, v2, e2, v3, e3,
1953                                 u, v, du, dv);
1954                 }
1955         }
1956         /* Loops for faces connecting inner ptex part with boundary. */
1957         const MLoop *prev_coarse_loop =
1958                 &coarse_mloop[coarse_poly->loopstart + coarse_poly->totloop - 1];
1959         for (int prev_corner = coarse_poly->totloop - 1, corner = 0;
1960              corner < coarse_poly->totloop;
1961              prev_corner = corner, corner++)
1962         {
1963                 loop_interpolation_from_ptex(ctx,
1964                                              &loop_interpolation,
1965                                              coarse_poly,
1966                                              corner);
1967                 const MLoop *coarse_loop =
1968                         &coarse_mloop[coarse_poly->loopstart + corner];
1969                 const MEdge *coarse_edge = &coarse_medge[coarse_loop->e];
1970                 const MEdge *prev_coarse_edge = &coarse_medge[prev_coarse_loop->e];
1971                 const bool flip = (coarse_edge->v2 == coarse_loop->v);
1972                 const int start_edge_vertex = ctx->vertices_edge_offset +
1973                         coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1974                 const int corner_vertex_index =
1975                         start_vertex_index + corner * num_inner_vertices_per_ptex;
1976                 const int corner_edge_index =
1977                         start_edge_index + corner * num_inner_edges_per_ptex_face;
1978                 /* Create loops for polygons along U axis. */
1979                 int v0 = ctx->vertices_corner_offset + coarse_loop->v;
1980                 int v3, e3;
1981                 if (prev_coarse_loop->v == prev_coarse_edge->v1) {
1982                         v3 = ctx->vertices_edge_offset +
1983                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge +
1984                         num_subdiv_vertices_per_coarse_edge - 1;
1985                         e3 = ctx->edge_boundary_offset +
1986                                  prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge +
1987                                  num_subdiv_edges_per_coarse_edge - 1;
1988                 }
1989                 else {
1990                         v3 = ctx->vertices_edge_offset +
1991                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
1992                         e3 = ctx->edge_boundary_offset +
1993                                  prev_coarse_loop->e * num_subdiv_edges_per_coarse_edge;
1994                 }
1995                 for (int i = 0;
1996                      i <= ptex_face_inner_resolution;
1997                      i++, subdiv_loop += 4)
1998                 {
1999                         int v1;
2000                         if (flip) {
2001                                 v1 = start_edge_vertex + (resolution - i - 3);
2002                         }
2003                         else {
2004                                 v1 = start_edge_vertex + i;
2005                         }
2006                         int v2;
2007                         if (ptex_face_inner_resolution >= 1) {
2008                                 v2 = corner_vertex_index + i;
2009                         }
2010                         else {
2011                                 v2 = center_vertex_index;
2012                         }
2013                         int e0;
2014                         if (flip) {
2015                                 e0 = ctx->edge_boundary_offset +
2016                                          coarse_loop->e * num_subdiv_edges_per_coarse_edge +
2017                                          num_subdiv_edges_per_coarse_edge - i - 1;
2018                         }
2019                         else {
2020                                 e0 = ctx->edge_boundary_offset +
2021                                          coarse_loop->e * num_subdiv_edges_per_coarse_edge +
2022                                          i;
2023                         }
2024                         int e1 = start_edge_index +
2025                                  corner * (2 * ptex_face_inner_resolution + 1);
2026                         if (ptex_face_resolution >= 3) {
2027                                 e1 += coarse_poly->totloop * (num_inner_edges_per_ptex_face +
2028                                                               ptex_face_inner_resolution + 1) +
2029                                       i;
2030                         }
2031                         int e2 = 0;
2032                         if (i == 0 && ptex_face_resolution >= 3) {
2033                                 e2 = start_edge_index +
2034                                          coarse_poly->totloop *
2035                                                  (num_inner_edges_per_ptex_face +
2036                                                   ptex_face_inner_resolution + 1) +
2037                                          corner * (2 * ptex_face_inner_resolution + 1) +
2038                                          ptex_face_inner_resolution + 1;
2039                         }
2040                         else if (i == 0 && ptex_face_resolution < 3) {
2041                                 e2 = start_edge_index +
2042                                  prev_corner * (2 * ptex_face_inner_resolution + 1);
2043                         }
2044                         else {
2045                                 e2 = corner_edge_index + i - 1;
2046                         }
2047                         const float u = du * i;
2048                         const float v = 0.0f;
2049                         subdiv_create_loops_of_poly(
2050                                 ctx, &loop_interpolation, subdiv_loop,
2051                                 ptex_face_index + corner, 0,
2052                                 v0, e0, v1, e1, v2, e2, v3, e3,
2053                                 u, v, du, dv);
2054                         v0 = v1;
2055                         v3 = v2;
2056                         e3 = e1;
2057                 }
2058                 /* Create loops for polygons along V axis. */
2059                 const bool flip_prev = (prev_coarse_edge->v2 == coarse_loop->v);
2060                 v0 = corner_vertex_index;
2061                 if (prev_coarse_loop->v == prev_coarse_edge->v1) {
2062                         v3 = ctx->vertices_edge_offset +
2063                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge +
2064                         num_subdiv_vertices_per_coarse_edge - 1;
2065                 }
2066                 else {
2067                         v3 = ctx->vertices_edge_offset +
2068                         prev_coarse_loop->e * num_subdiv_vertices_per_coarse_edge;
2069                 }
2070                 e3 = start_edge_index +
2071                          coarse_poly->totloop *
2072                                  (num_inner_edges_per_ptex_face +
2073                                   ptex_face_inner_resolution + 1) +
2074                          corner * (2 * ptex_face_inner_resolution + 1) +
2075                          ptex_face_inner_resolution + 1;
2076                 for (int i = 0;
2077                      i <= ptex_face_inner_resolution - 1;
2078                      i++, subdiv_loop += 4)
2079                 {
2080                         int v1;
2081                         int e0, e1;
2082                         if (i == ptex_face_inner_resolution - 1) {
2083                                 v1 = start_vertex_index +
2084                                      prev_corner * num_inner_vertices_per_ptex +
2085                                      ptex_face_inner_resolution;
2086                                 e1 = start_edge_index +
2087                                          coarse_poly->totloop *
2088                                                  (num_inner_edges_per_ptex_face +
2089                                                   ptex_face_inner_resolution + 1) +
2090                                          prev_corner * (2 * ptex_face_inner_resolution + 1) +
2091                                          ptex_face_inner_resolution;
2092                                 e0 = start_edge_index +
2093                                       coarse_poly->totloop * num_inner_edges_per_ptex_face +
2094                                       prev_corner * ptex_face_inner_resolution;
2095                         }
2096                         else {
2097                                 v1 = v0 + ptex_face_inner_resolution + 1;
2098                                 e0 = corner_edge_index + ptex_face_inner_resolution +
2099                                          i * (2 * ptex_face_inner_resolution + 1);
2100                                 e1 = e3 + 1;
2101                         }
2102                         int v2 = flip_prev ? v3 - 1 : v3 + 1;
2103                         int e2;
2104                         if (flip_prev) {
2105                                 e2 = ctx->edge_boundary_offset +
2106                                          prev_coarse_loop->e *
2107                                                  num_subdiv_edges_per_coarse_edge +
2108                                          num_subdiv_edges_per_coarse_edge - 2 - i;
2109                         }
2110                         else {
2111                                 e2 = ctx->edge_boundary_offset +
2112                                          prev_coarse_loop->e *
2113                                                  num_subdiv_edges_per_coarse_edge + 1 + i;
2114                         }
2115                         const float u = 0.0f;
2116                         const float v = du * (i + 1);
2117                         subdiv_create_loops_of_poly(
2118                                 ctx, &loop_interpolation, subdiv_loop,
2119                                 ptex_face_index + corner, 1,
2120                                 v0, e0, v1, e1, v2, e2, v3, e3,
2121                                 u, v, du, dv);
2122                         v0 = v1;
2123                         v3 = v2;
2124                         e3 = e1;
2125                 }
2126                 prev_coarse_loop = coarse_loop;
2127         }
2128         loop_interpolation_end(&loop_interpolation);
2129 }
2130
2131 static void subdiv_create_loops(SubdivMeshContext *ctx, int poly_index)
2132 {
2133         const Mesh *coarse_mesh = ctx->coarse_mesh;
2134         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
2135         const MPoly *coarse_poly = &coarse_mpoly[poly_index];
2136         if (coarse_poly->totloop == 4) {
2137                 subdiv_create_loops_regular(ctx, coarse_poly);
2138         }
2139         else {
2140                 subdiv_create_loops_special(ctx, coarse_poly);
2141         }
2142 }
2143
2144 /* =============================================================================
2145  * Polygons subdivision process.
2146  */
2147
2148 static void subdiv_copy_poly_data(const SubdivMeshContext *ctx,
2149                                   MPoly *subdiv_poly,
2150                                   const MPoly *coarse_poly)
2151 {
2152         const int coarse_poly_index = coarse_poly - ctx->coarse_mesh->mpoly;
2153         const int subdiv_poly_index = subdiv_poly - ctx->subdiv_mesh->mpoly;
2154         CustomData_copy_data(&ctx->coarse_mesh->pdata,
2155                              &ctx->subdiv_mesh->pdata,
2156                              coarse_poly_index,
2157                              subdiv_poly_index,
2158                              1);
2159 }
2160
2161 static void subdiv_create_polys(SubdivMeshContext *ctx, int poly_index)
2162 {
2163         const int resolution = ctx->settings->resolution;
2164         const int start_poly_index = ctx->subdiv_polygon_offset[poly_index];
2165         /* Base/coarse mesh information. */
2166         const Mesh *coarse_mesh = ctx->coarse_mesh;
2167         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
2168         const MPoly *coarse_poly = &coarse_mpoly[poly_index];
2169         const int num_ptex_faces_per_poly =
2170                 num_ptex_faces_per_poly_get(coarse_poly);
2171         const int ptex_resolution =
2172                 ptex_face_resolution_get(coarse_poly, resolution);
2173         const int num_polys_per_ptex = num_polys_per_ptex_get(ptex_resolution);
2174         const int num_loops_per_ptex = 4 * num_polys_per_ptex;
2175         const int start_loop_index = 4 * start_poly_index;
2176         /* Hi-poly subdivided mesh. */
2177         Mesh *subdiv_mesh = ctx->subdiv_mesh;
2178         MPoly *subdiv_mpoly = subdiv_mesh->mpoly;
2179         MPoly *subdiv_mp = &subdiv_mpoly[start_poly_index];
2180         for (int ptex_of_poly_index = 0;
2181              ptex_of_poly_index < num_ptex_faces_per_poly;
2182              ptex_of_poly_index++)
2183         {
2184                 for (int subdiv_poly_index = 0;
2185                      subdiv_poly_index < num_polys_per_ptex;
2186                      subdiv_poly_index++, subdiv_mp++)
2187                 {
2188                         subdiv_copy_poly_data(ctx, subdiv_mp, coarse_poly);
2189                         subdiv_mp->loopstart = start_loop_index +
2190                                                (ptex_of_poly_index * num_loops_per_ptex) +
2191                                                (subdiv_poly_index * 4);
2192                         subdiv_mp->totloop = 4;
2193                 }
2194         }
2195 }
2196
2197 /* =============================================================================
2198  * Loose elements subdivision process.
2199  */
2200
2201 static void subdiv_create_loose_vertices_task(
2202         void *__restrict userdata,
2203         const int vertex_index,
2204         const ParallelRangeTLS *__restrict UNUSED(tls))
2205 {
2206         SubdivMeshContext *ctx = userdata;
2207         if (BLI_BITMAP_TEST_BOOL(ctx->coarse_vertices_used_map, vertex_index)) {
2208                 /* Vertex is not loose, was handled when handling polygons. */
2209                 return;
2210         }
2211         const Mesh *coarse_mesh = ctx->coarse_mesh;
2212         const MVert *coarse_mvert = coarse_mesh->mvert;
2213         const MVert *coarse_vertex = &coarse_mvert[vertex_index];
2214         Mesh *subdiv_mesh = ctx->subdiv_mesh;
2215         MVert *subdiv_mvert = subdiv_mesh->mvert;
2216         MVert *subdiv_vertex = &subdiv_mvert[
2217                 ctx->vertices_corner_offset + vertex_index];
2218         subdiv_vertex_data_copy(ctx, coarse_vertex, subdiv_vertex);
2219 }
2220
2221 /* Get neighbor edges of the given one.
2222  * - neighbors[0] is an edge adjacent to edge->v1.
2223  * - neighbors[1] is an edge adjacent to edge->v1.
2224  */
2225 static void find_edge_neighbors(const SubdivMeshContext *ctx,
2226                                 const MEdge *edge,
2227                                 const MEdge *neighbors[2])
2228 {
2229         const Mesh *coarse_mesh = ctx->coarse_mesh;
2230         const MEdge *coarse_medge = coarse_mesh->medge;
2231         neighbors[0] = NULL;
2232         neighbors[1] = NULL;
2233         for (int edge_index = 0; edge_index < coarse_mesh->totedge; edge_index++) {
2234                 if (BLI_BITMAP_TEST_BOOL(ctx->coarse_edges_used_map, edge_index)) {
2235                         continue;
2236                 }
2237                 const MEdge *current_edge = &coarse_medge[edge_index];
2238                 if (current_edge == edge) {
2239                         continue;
2240                 }
2241                 if (ELEM(edge->v1, current_edge->v1, current_edge->v2)) {
2242                         neighbors[0] = current_edge;
2243                 }
2244                 if (ELEM(edge->v2, current_edge->v1, current_edge->v2)) {
2245                         neighbors[1] = current_edge;
2246                 }
2247         }
2248 }
2249
2250 static void points_for_loose_edges_interpolation_get(
2251         SubdivMeshContext *ctx,
2252         const MEdge *coarse_edge,
2253         const MEdge *neighbors[2],
2254                 float points_r[4][3])
2255 {
2256         const Mesh *coarse_mesh = ctx->coarse_mesh;
2257         const MVert *coarse_mvert = coarse_mesh->mvert;
2258         /* Middle points corresponds to the edge. */
2259         copy_v3_v3(points_r[1], coarse_mvert[coarse_edge->v1].co);
2260         copy_v3_v3(points_r[2], coarse_mvert[coarse_edge->v2].co);
2261         /* Start point, duplicate from edge start if no neighbor. */
2262         if (neighbors[0] != NULL) {
2263                 if (neighbors[0]->v1 == coarse_edge->v1) {
2264                         copy_v3_v3(points_r[0], coarse_mvert[neighbors[0]->v2].co);
2265                 }
2266                 else {
2267                         copy_v3_v3(points_r[0], coarse_mvert[neighbors[0]->v1].co);
2268                 }
2269         }
2270         else {
2271                 sub_v3_v3v3(points_r[0], points_r[1], points_r[2]);
2272                 add_v3_v3(points_r[0], points_r[1]);
2273         }
2274         /* End point, duplicate from edge end if no neighbor. */
2275         if (neighbors[1] != NULL) {
2276                 if (neighbors[1]->v1 == coarse_edge->v2) {
2277                         copy_v3_v3(points_r[3], coarse_mvert[neighbors[1]->v2].co);
2278                 }
2279                 else {
2280                         copy_v3_v3(points_r[3], coarse_mvert[neighbors[1]->v1].co);
2281                 }
2282         }
2283         else {
2284                 sub_v3_v3v3(points_r[3], points_r[2], points_r[1]);
2285                 add_v3_v3(points_r[3], points_r[2]);
2286         }
2287 }
2288
2289 static void subdiv_create_vertices_of_loose_edges_task(
2290         void *__restrict userdata,
2291         const int edge_index,
2292         const ParallelRangeTLS *__restrict UNUSED(tls))
2293 {
2294         SubdivMeshContext *ctx = userdata;
2295         if (BLI_BITMAP_TEST_BOOL(ctx->coarse_edges_used_map, edge_index)) {
2296                 /* Vertex is not loose, was handled when handling polygons. */
2297                 return;
2298         }
2299         const int resolution = ctx->settings->resolution;
2300         const int resolution_1 = resolution - 1;
2301         const float inv_resolution_1 = 1.0f / (float)resolution_1;
2302         const int num_subdiv_vertices_per_coarse_edge = resolution - 2;
2303         const Mesh *coarse_mesh = ctx->coarse_mesh;
2304         const MEdge *coarse_edge = &coarse_mesh->medge[edge_index];
2305         Mesh *subdiv_mesh = ctx->subdiv_mesh;
2306         MVert *subdiv_mvert = subdiv_mesh->mvert;
2307         /* Find neighbors of the current loose edge. */
2308         const MEdge *neighbors[2];
2309         find_edge_neighbors(ctx, coarse_edge, neighbors);
2310         /* Get points for b-spline interpolation. */
2311         float points[4][3];
2312         points_for_loose_edges_interpolation_get(
2313                 ctx, coarse_edge, neighbors, points);
2314         /* Subdivion verticies which corresponds to edge's v1 and v2. */
2315         MVert *subdiv_v1 = &subdiv_mvert[
2316                 ctx->vertices_corner_offset + coarse_edge->v1];
2317         MVert *subdiv_v2 = &subdiv_mvert[
2318                 ctx->vertices_corner_offset + coarse_edge->v2];
2319         /* First subdivided inner vertex of the edge.  */
2320         MVert *subdiv_start_vertex = &subdiv_mvert[
2321                 ctx->vertices_edge_offset +
2322                 edge_index * num_subdiv_vertices_per_coarse_edge];
2323         /* Perform interpolation. */
2324         for (int i = 0; i < resolution; i++) {
2325                 const float u = i * inv_resolution_1;
2326                 float weights[4];
2327                 key_curve_position_weights(u, weights, KEY_BSPLINE);
2328
2329                 MVert *subdiv_vertex;
2330                 if (i == 0) {
2331                         subdiv_vertex = subdiv_v1;
2332                 }
2333                 else if (i == resolution - 1) {
2334                         subdiv_vertex = subdiv_v2;
2335                 }
2336                 else {
2337                         subdiv_vertex = &subdiv_start_vertex[i - 1];
2338                 }
2339                 interp_v3_v3v3v3v3(subdiv_vertex->co,
2340                                    points[0],
2341                                    points[1],
2342                                    points[2],
2343                                    points[3],
2344                                    weights);
2345                 /* Reset flags and such. */
2346                 subdiv_vertex->flag = 0;
2347                 subdiv_vertex->bweight = 0.0f;
2348                 /* Reset normal. */
2349                 subdiv_vertex->no[0] = 0.0f;
2350                 subdiv_vertex->no[1] = 0.0f;
2351                 subdiv_vertex->no[2] = 1.0f;
2352         }
2353 }
2354
2355 /* =============================================================================
2356  * Subdivision process entry points.
2357  */
2358
2359 static void subdiv_eval_task(
2360         void *__restrict userdata,
2361         const int poly_index,
2362         const ParallelRangeTLS *__restrict UNUSED(tls))
2363 {
2364         SubdivMeshContext *ctx = userdata;
2365         /* Evaluate hi-poly vertex coordinates and normals. */
2366         subdiv_evaluate_vertices(ctx, poly_index);
2367         /* Create mesh geometry for the given base poly index. */
2368         subdiv_create_edges(ctx, poly_index);
2369         subdiv_create_loops(ctx, poly_index);
2370         subdiv_create_polys(ctx, poly_index);
2371 }
2372
2373 static void subdiv_create_boundary_edges_task(
2374         void *__restrict userdata,
2375         const int edge_index,
2376         const ParallelRangeTLS *__restrict UNUSED(tls))
2377 {
2378         SubdivMeshContext *ctx = userdata;
2379         subdiv_create_boundary_edges(ctx, edge_index);
2380 }
2381
2382 Mesh *BKE_subdiv_to_mesh(
2383         Subdiv *subdiv,
2384         const SubdivToMeshSettings *settings,
2385         const Mesh *coarse_mesh)
2386 {
2387         BKE_subdiv_stats_begin(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH);
2388         /* Make sure evaluator is up to date with possible new topology, and that
2389          * is is refined for the new positions of coarse vertices.
2390          */
2391         BKE_subdiv_eval_update_from_mesh(subdiv, coarse_mesh);
2392         SubdivMeshContext ctx = {0};
2393         ctx.coarse_mesh = coarse_mesh;
2394         ctx.subdiv = subdiv;
2395         ctx.settings = settings;
2396         subdiv_mesh_ctx_init(&ctx);
2397         Mesh *result = BKE_mesh_new_nomain_from_template(
2398                 coarse_mesh,
2399                 ctx.num_subdiv_vertices,
2400                 ctx.num_subdiv_edges,
2401                 0,
2402                 ctx.num_subdiv_loops,
2403                 ctx.num_subdiv_polygons);
2404         ctx.subdiv_mesh = result;
2405         subdiv_mesh_ctx_init_result(&ctx);
2406         /* Multi-threaded evaluation. */
2407         ParallelRangeSettings parallel_range_settings;
2408         BKE_subdiv_stats_begin(&subdiv->stats,
2409                                SUBDIV_STATS_SUBDIV_TO_MESH_GEOMETRY);
2410         BLI_parallel_range_settings_defaults(&parallel_range_settings);
2411         BLI_task_parallel_range(0, coarse_mesh->totpoly,
2412                                 &ctx,
2413                                 subdiv_eval_task,
2414                                 &parallel_range_settings);
2415         BLI_task_parallel_range(0, coarse_mesh->totvert,
2416                                 &ctx,
2417                                 subdiv_create_loose_vertices_task,
2418                                 &parallel_range_settings);
2419         BLI_task_parallel_range(0, coarse_mesh->totedge,
2420                                 &ctx,
2421                                 subdiv_create_vertices_of_loose_edges_task,
2422                                 &parallel_range_settings);
2423         BLI_task_parallel_range(0, coarse_mesh->totedge,
2424                                 &ctx,
2425                                 subdiv_create_boundary_edges_task,
2426                                 &parallel_range_settings);
2427         subdiv_mesh_ctx_free(&ctx);
2428         BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH_GEOMETRY);
2429         // BKE_mesh_validate(result, true, true);
2430         BKE_subdiv_stats_end(&subdiv->stats, SUBDIV_STATS_SUBDIV_TO_MESH);
2431         return result;
2432 }