Merge branch 'blender2.7'
[blender.git] / source / blender / blenkernel / intern / multires_reshape.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 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/multires_reshape.c
27  *  \ingroup bke
28  */
29
30 #include "MEM_guardedalloc.h"
31
32 #include "DNA_mesh_types.h"
33 #include "DNA_meshdata_types.h"
34 #include "DNA_scene_types.h"
35
36 #include "BLI_utildefines.h"
37 #include "BLI_math_vector.h"
38 #include "BLI_task.h"
39
40 #include "BKE_ccg.h"
41 #include "BKE_library.h"
42 #include "BKE_mesh.h"
43 #include "BKE_mesh_runtime.h"
44 #include "BKE_modifier.h"
45 #include "BKE_multires.h"
46 #include "BKE_subdiv.h"
47 #include "BKE_subdiv_ccg.h"
48 #include "BKE_subdiv_eval.h"
49 #include "BKE_subdiv_foreach.h"
50 #include "BKE_subdiv_mesh.h"
51
52 #include "DEG_depsgraph_query.h"
53
54 static void multires_reshape_init_mmd(
55         MultiresModifierData *reshape_mmd,
56         const MultiresModifierData *mmd)
57 {
58         *reshape_mmd = *mmd;
59 }
60
61 static void multires_reshape_init_mmd_top_level(
62         MultiresModifierData *reshape_mmd,
63         const MultiresModifierData *mmd)
64 {
65         *reshape_mmd = *mmd;
66         reshape_mmd->lvl = reshape_mmd->totlvl;
67 }
68
69 /* =============================================================================
70  * General reshape implementation, reused by all particular cases.
71  */
72
73 typedef struct MultiresReshapeContext {
74         Subdiv *subdiv;
75         const Mesh *coarse_mesh;
76         MDisps *mdisps;
77         GridPaintMask *grid_paint_mask;
78         int top_grid_size;
79         int top_level;
80         /* Indexed by coarse face index, returns first ptex face index corresponding
81          * to that coarse face. */
82         int *face_ptex_offset;
83 } MultiresReshapeContext;
84
85 static void multires_reshape_allocate_displacement_grid(
86         MDisps *displacement_grid, const int level)
87 {
88         const int grid_size = BKE_subdiv_grid_size_from_level(level);
89         const int grid_area = grid_size * grid_size;
90         float (*disps)[3] = MEM_calloc_arrayN(
91                 grid_area, 3 * sizeof(float), "multires disps");
92         displacement_grid->disps = disps;
93         displacement_grid->totdisp = grid_area;
94         displacement_grid->level = level;
95 }
96
97 static void multires_reshape_ensure_displacement_grid(
98         MDisps *displacement_grid, const int level)
99 {
100         if (displacement_grid->disps != NULL) {
101                 return;
102         }
103         multires_reshape_allocate_displacement_grid(
104         displacement_grid, level);
105 }
106
107 static void multires_reshape_ensure_displacement_grids(
108         Mesh *mesh,
109         const int grid_level)
110 {
111         const int num_grids = mesh->totloop;
112         MDisps *mdisps = CustomData_get_layer(&mesh->ldata, CD_MDISPS);
113         for (int grid_index = 0; grid_index < num_grids; grid_index++) {
114                 multires_reshape_ensure_displacement_grid(
115                         &mdisps[grid_index], grid_level);
116         }
117 }
118
119 static void multires_reshape_ensure_mask_grids(Mesh *mesh, const int grid_level)
120 {
121         GridPaintMask *grid_paint_masks =
122                 CustomData_get_layer(&mesh->ldata, CD_GRID_PAINT_MASK);
123         if (grid_paint_masks == NULL) {
124                 return;
125         }
126         const int num_grids = mesh->totloop;
127         const int grid_size = BKE_subdiv_grid_size_from_level(grid_level);
128         const int grid_area = grid_size * grid_size;
129         for (int grid_index = 0; grid_index < num_grids; grid_index++) {
130                 GridPaintMask *grid_paint_mask = &grid_paint_masks[grid_index];
131                 if (grid_paint_mask->level == grid_level) {
132                         continue;
133                 }
134                 grid_paint_mask->level = grid_level;
135                 if (grid_paint_mask->data) {
136                         MEM_freeN(grid_paint_mask->data);
137                 }
138                 grid_paint_mask->data = MEM_calloc_arrayN(
139                         grid_area, sizeof(float), "gpm.data");
140         }
141 }
142
143 static void multires_reshape_ensure_grids(Mesh *mesh, const int grid_level)
144 {
145         multires_reshape_ensure_displacement_grids(mesh, grid_level);
146         multires_reshape_ensure_mask_grids(mesh, grid_level);
147 }
148
149 /* Convert normalized coordinate within a grid to a normalized coordinate within
150  * a ptex face. */
151 static void multires_reshape_corner_coord_to_ptex(
152         const MPoly *coarse_poly,
153         const int corner, const float corner_u, const float corner_v,
154         float *r_ptex_face_u, float *r_ptex_face_v)
155 {
156         if (coarse_poly->totloop == 4) {
157                 float grid_u, grid_v;
158                 BKE_subdiv_ptex_face_uv_to_grid_uv(
159                         corner_u, corner_v, &grid_u, &grid_v);
160                 BKE_subdiv_rotate_grid_to_quad(corner, grid_u, grid_v,
161                                                r_ptex_face_u, r_ptex_face_v);
162         }
163         else {
164                 *r_ptex_face_u = corner_u;
165                 *r_ptex_face_v = corner_v;
166         }
167 }
168
169 /* NOTE: The tangent vectors are measured in ptex face normalized coordinates,
170  * which is different from grid tangent. */
171 static void multires_reshape_sample_surface(
172         Subdiv *subdiv,
173         const MPoly *coarse_poly,
174         const int corner, const float corner_u, const float corner_v,
175         const int ptex_face_index,
176         float r_P[3], float r_dPdu[3], float r_dPdv[3])
177 {
178         float ptex_face_u, ptex_face_v;
179         multires_reshape_corner_coord_to_ptex(
180                 coarse_poly, corner, corner_u, corner_v,
181                 &ptex_face_u, &ptex_face_v);
182         BKE_subdiv_eval_limit_point_and_derivatives(
183                 subdiv,
184                 ptex_face_index, ptex_face_u, ptex_face_v,
185                 r_P, r_dPdu, r_dPdv);
186 }
187
188 static void multires_reshape_tangent_matrix_for_corner(
189         const MPoly *coarse_poly,
190         const int coarse_corner,
191         const float dPdu[3], const float dPdv[3],
192         float r_tangent_matrix[3][3])
193 {
194         /* For a quad faces we would need to flip the tangent, since they will use
195          * use different coordinates within displacement grid comparent to ptex
196          * face. */
197         const bool is_quad = (coarse_poly->totloop == 4);
198         const int tangent_corner = is_quad ? coarse_corner : 0;
199         BKE_multires_construct_tangent_matrix(
200                 r_tangent_matrix, dPdu, dPdv, tangent_corner);
201 }
202
203 static void multires_reshape_vertex_from_final_data(
204         MultiresReshapeContext *ctx,
205         const int ptex_face_index,
206         const float corner_u, const float corner_v,
207         const int coarse_poly_index,
208         const int coarse_corner,
209         const float final_P[3], const float final_mask)
210 {
211         Subdiv *subdiv = ctx->subdiv;
212         const int grid_size = ctx->top_grid_size;
213         const Mesh *coarse_mesh = ctx->coarse_mesh;
214         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
215         const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index];
216         const int loop_index = coarse_poly->loopstart + coarse_corner;
217         /* Evaluate limit surface. */
218         float P[3], dPdu[3], dPdv[3];
219         multires_reshape_sample_surface(
220                 subdiv,
221                 coarse_poly,
222                 coarse_corner, corner_u, corner_v,
223                 ptex_face_index,
224                 P, dPdu, dPdv);
225         /* Construct tangent matrix which matches orientation of the current
226          * displacement grid. */
227         float tangent_matrix[3][3], inv_tangent_matrix[3][3];
228         multires_reshape_tangent_matrix_for_corner(coarse_poly, coarse_corner,
229                                                    dPdu, dPdv,
230                                                    tangent_matrix);
231         invert_m3_m3(inv_tangent_matrix, tangent_matrix);
232         /* Convert object coordinate to a tangent space of displacement grid. */
233         float D[3];
234         sub_v3_v3v3(D, final_P, P);
235         float tangent_D[3];
236         mul_v3_m3v3(tangent_D, inv_tangent_matrix, D);
237         /* Calculate index of element within the grid. */
238         float grid_u, grid_v;
239         BKE_subdiv_ptex_face_uv_to_grid_uv(corner_u, corner_v, &grid_u, &grid_v);
240         const int grid_x = (grid_u * (grid_size - 1) + 0.5f);
241         const int grid_y = (grid_v * (grid_size - 1) + 0.5f);
242         const int index = grid_y * grid_size + grid_x;
243         /* Write tangent displacement. */
244         MDisps *displacement_grid = &ctx->mdisps[loop_index];
245         copy_v3_v3(displacement_grid->disps[index], tangent_D);
246         /* Write mask grid. */
247         if (ctx->grid_paint_mask != NULL) {
248                 GridPaintMask *grid_paint_mask = &ctx->grid_paint_mask[loop_index];
249                 BLI_assert(grid_paint_mask->level == displacement_grid->level);
250                 grid_paint_mask->data[index] = final_mask;
251         }
252 }
253
254 /* =============================================================================
255  * Helpers to propagate displacement to higher levels.
256  */
257
258 typedef struct MultiresPropagateData {
259         /* Number of displacement grids. */
260         int num_grids;
261         /* Resolution level up to which displacement is known. */
262         int reshape_level;
263         /* Resolution up to which propagation is happening, affecting all the
264          * levels in [reshape_level + 1, top_level]. */
265         int top_level;
266         /* Grid sizes at the corresponding levels. */
267         int reshape_grid_size;
268         int top_grid_size;
269         /* Keys to access CCG at different levels. */
270         CCGKey reshape_level_key;
271         CCGKey top_level_key;
272         /* Original grid data, before any updates for reshape.
273          * Contains data at the reshape_level resolution level. */
274         CCGElem **orig_grids_data;
275         /* Custom data layers from a coarse mesh. */
276         MDisps *mdisps;
277         GridPaintMask *grid_paint_mask;
278 } MultiresPropagateData;
279
280 static CCGElem **allocate_grids(CCGKey *key, int num_grids)
281 {
282         CCGElem **grids = MEM_calloc_arrayN(
283                 num_grids, sizeof(CCGElem *), "reshape grids*");
284         for (int grid_index = 0; grid_index < num_grids; grid_index++) {
285                 grids[grid_index] = MEM_calloc_arrayN(
286                         key->elem_size,
287                         key->grid_area,
288                         "reshape orig_grids_data elems");
289         }
290         return grids;
291 }
292
293 static void free_grids(CCGElem **grids, int num_grids)
294 {
295         if (grids == NULL) {
296                 return;
297         }
298         for (int grid_index = 0; grid_index < num_grids; grid_index++) {
299                 MEM_freeN(grids[grid_index]);
300         }
301         MEM_freeN(grids);
302 }
303
304 /* Initialize element sizes and offsets. */
305 static void multires_reshape_init_key_layers(
306         CCGKey *key,
307         const MultiresPropagateData *data)
308 {
309         key->elem_size = 3 * sizeof(float);
310         if (data->grid_paint_mask != NULL) {
311                 key->mask_offset = 3 * sizeof(float);
312                 key->elem_size += sizeof(float);
313                 key->has_mask = true;
314         }
315         else {
316                 key->mask_offset = -1;
317                 key->has_mask = false;
318         }
319         /* We never have normals in original grids. */
320         key->normal_offset = -1;
321         key->has_normals = false;
322 }
323
324 /* Initialize key used to access reshape grids at given level. */
325 static void multires_reshape_init_level_key(
326         CCGKey *key,
327         const MultiresPropagateData *data,
328         const int level)
329 {
330         key->level = level;
331         /* Init layers. */
332         multires_reshape_init_key_layers(key, data);
333         /* By default, only 3 floats for coordinate, */
334         key->grid_size = BKE_subdiv_grid_size_from_level(key->level);
335         key->grid_area = key->grid_size * key->grid_size;
336         key->grid_bytes = key->elem_size * key->grid_area;
337 }
338
339 static void multires_reshape_store_original_grids(
340         MultiresPropagateData *data)
341 {
342         const int num_grids = data->num_grids;
343         /* Original data to be backed up. */
344         const MDisps *mdisps = data->mdisps;
345         const GridPaintMask *grid_paint_mask = data->grid_paint_mask;
346         /* Allocate grids for backup. */
347         CCGKey *orig_key = &data->reshape_level_key;
348         CCGElem **orig_grids_data = allocate_grids(orig_key, num_grids);
349         /* Fill in grids. */
350         const int orig_grid_size = data->reshape_grid_size;
351         const int top_grid_size = data->top_grid_size;
352         const int skip = (top_grid_size - 1) / (orig_grid_size - 1);
353         for (int grid_index = 0; grid_index < num_grids; grid_index++) {
354                 CCGElem *orig_grid = orig_grids_data[grid_index];
355                 for (int y = 0; y < orig_grid_size; y++) {
356                         const int top_y = y * skip;
357                         for (int x = 0; x < orig_grid_size; x++) {
358                                 const int top_x = x * skip;
359                                 const int top_index = top_y * top_grid_size + top_x;
360                                 memcpy(CCG_grid_elem_co(orig_key, orig_grid, x, y),
361                                        mdisps[grid_index].disps[top_index],
362                                        sizeof(float) * 3);
363                                 if (orig_key->has_mask) {
364                                         *CCG_grid_elem_mask(orig_key, orig_grid, x, y) =
365                                                 grid_paint_mask[grid_index].data[top_index];
366                                 }
367                         }
368                 }
369         }
370         /* Store in the context. */
371         data->orig_grids_data = orig_grids_data;
372 }
373
374 static void multires_reshape_propagate_prepare(
375         MultiresPropagateData *data,
376         Mesh *coarse_mesh,
377         const int reshape_level,
378         const int top_level)
379 {
380         BLI_assert(reshape_level <= top_level);
381         memset(data, 0, sizeof(*data));
382         data->num_grids = coarse_mesh->totloop;
383         data->reshape_level = reshape_level;
384         data->top_level = top_level;
385         if (reshape_level == top_level) {
386                 /* Nothing to do, reshape will happen on the whole grid content. */
387                 return;
388         }
389         data->mdisps = CustomData_get_layer(&coarse_mesh->ldata, CD_MDISPS);
390         data->grid_paint_mask =
391                 CustomData_get_layer(&coarse_mesh->ldata, CD_GRID_PAINT_MASK);
392         data->top_grid_size = BKE_subdiv_grid_size_from_level(top_level);
393         data->reshape_grid_size = BKE_subdiv_grid_size_from_level(reshape_level);
394         /* Initialize keys to access CCG at different levels. */
395         multires_reshape_init_level_key(
396                 &data->reshape_level_key, data, data->reshape_level);
397         multires_reshape_init_level_key(
398                 &data->top_level_key, data, data->top_level);
399         /* Make a copy of grids before reshaping, so we can calculate deltas
400          * later on. */
401         multires_reshape_store_original_grids(data);
402 }
403
404 static void multires_reshape_propagate_prepare_from_mmd(
405         MultiresPropagateData *data,
406         struct Depsgraph *depsgraph,
407         Object *object,
408         const MultiresModifierData *mmd,
409         const int top_level,
410         const bool use_render_params)
411 {
412     /* TODO(sergey): Find mode reliable way of getting current level. */
413         Scene *scene_eval = DEG_get_evaluated_scene(depsgraph);
414         Mesh *mesh = object->data;
415         const int level = multires_get_level(
416                 scene_eval, object, mmd, use_render_params, true);
417         multires_reshape_propagate_prepare(data, mesh, level, top_level);
418 }
419
420 /* Calculate delta of changed reshape level data layers. Delta goes to a
421  * grids at top level (meaning, the result grids are only partially filled
422  * in). */
423 static void multires_reshape_calculate_delta(
424         MultiresPropagateData *data,
425         CCGElem **delta_grids_data)
426 {
427         const int num_grids = data->num_grids;
428         /* At this point those custom data layers has updated data for the
429          * level we are propagating from. */
430         const MDisps *mdisps = data->mdisps;
431         const GridPaintMask *grid_paint_mask = data->grid_paint_mask;
432         CCGKey *reshape_key = &data->reshape_level_key;
433         CCGKey *delta_level_key = &data->top_level_key;
434         /* Calculate delta. */
435         const int top_grid_size = data->top_grid_size;
436         const int reshape_grid_size = data->reshape_grid_size;
437         const int delta_grid_size = data->top_grid_size;
438         const int skip = (top_grid_size - 1) / (reshape_grid_size - 1);
439         for (int grid_index = 0; grid_index < num_grids; grid_index++) {
440                 /*const*/ CCGElem *orig_grid = data->orig_grids_data[grid_index];
441                 CCGElem *delta_grid = delta_grids_data[grid_index];
442                 for (int y = 0; y < reshape_grid_size; y++) {
443                         const int top_y = y * skip;
444                         for (int x = 0; x < reshape_grid_size; x++) {
445                                 const int top_x = x * skip;
446                                 const int top_index = top_y * delta_grid_size + top_x;
447                                 sub_v3_v3v3(
448                                         CCG_grid_elem_co(
449                                                 delta_level_key, delta_grid, top_x, top_y),
450                                         mdisps[grid_index].disps[top_index],
451                                         CCG_grid_elem_co(reshape_key, orig_grid, x, y));
452                                 if (delta_level_key->has_mask) {
453                                         const float old_mask_value = *CCG_grid_elem_mask(
454                                                 reshape_key, orig_grid, x, y);
455                                         const float new_mask_value =
456                                                 grid_paint_mask[grid_index].data[top_index];
457                                         *CCG_grid_elem_mask(
458                                                 delta_level_key, delta_grid, top_x, top_y) =
459                                                         new_mask_value - old_mask_value;
460                                 }
461                         }
462                 }
463         }
464 }
465
466 /* Makes it so delta is propagated onto all the higher levels, but is also
467  * that this delta is smoothed in a way that it does not cause artifacts on
468  * boundaries. */
469
470 typedef struct MultiresPropagateCornerData {
471         float coord_delta[3];
472         float mask_delta;
473 } MultiresPropagateCornerData;
474
475 BLI_INLINE void multires_reshape_propagate_init_patch_corners(
476         MultiresPropagateData *data,
477         CCGElem *delta_grid,
478         const int patch_x, const int patch_y,
479         MultiresPropagateCornerData r_corners[4])
480 {
481         CCGKey *delta_level_key = &data->top_level_key;
482         const int orig_grid_size = data->reshape_grid_size;
483         const int top_grid_size = data->top_grid_size;
484         const int skip = (top_grid_size - 1) / (orig_grid_size - 1);
485         const int x = patch_x * skip;
486         const int y = patch_y * skip;
487         /* Store coordinate deltas. */
488         copy_v3_v3(r_corners[0].coord_delta,
489                    CCG_grid_elem_co(delta_level_key, delta_grid, x, y));
490         copy_v3_v3(r_corners[1].coord_delta,
491                    CCG_grid_elem_co(delta_level_key, delta_grid, x + skip, y));
492         copy_v3_v3(r_corners[2].coord_delta,
493                    CCG_grid_elem_co(delta_level_key, delta_grid, x, y + skip));
494         copy_v3_v3(r_corners[3].coord_delta,
495                    CCG_grid_elem_co(delta_level_key, delta_grid,
496                                     x + skip, y + skip));
497         if (delta_level_key->has_mask) {
498                 r_corners[0].mask_delta =
499                            *CCG_grid_elem_mask(delta_level_key, delta_grid, x, y);
500                 r_corners[1].mask_delta =
501                            *CCG_grid_elem_mask(delta_level_key, delta_grid,
502                                                x + skip, y);
503                 r_corners[2].mask_delta =
504                            *CCG_grid_elem_mask(delta_level_key, delta_grid,
505                                                x, y + skip);
506                 r_corners[3].mask_delta =
507                            *CCG_grid_elem_mask(delta_level_key, delta_grid,
508                                                x + skip, y + skip);
509         }
510 }
511
512 BLI_INLINE void multires_reshape_propagate_interpolate_coord(
513         float delta[3],
514         const MultiresPropagateCornerData corners[4],
515         const float weights[4])
516 {
517         interp_v3_v3v3v3v3(
518                delta,
519                corners[0].coord_delta, corners[1].coord_delta,
520                corners[2].coord_delta, corners[3].coord_delta,
521                weights);
522 }
523
524 BLI_INLINE float multires_reshape_propagate_interpolate_mask(
525         const MultiresPropagateCornerData corners[4],
526         const float weights[4])
527 {
528         return corners[0].mask_delta * weights[0] +
529                corners[1].mask_delta * weights[1] +
530                corners[2].mask_delta * weights[2] +
531                corners[3].mask_delta * weights[3];
532 }
533
534 BLI_INLINE void multires_reshape_propagate_and_smooth_delta_grid_patch(
535         MultiresPropagateData *data,
536         CCGElem *delta_grid,
537         const int patch_x, const int patch_y)
538 {
539         CCGKey *delta_level_key = &data->top_level_key;
540         const int orig_grid_size = data->reshape_grid_size;
541         const int top_grid_size = data->top_grid_size;
542         const int skip = (top_grid_size - 1) / (orig_grid_size - 1);
543         const float skip_inv = 1.0f / (float)skip;
544         MultiresPropagateCornerData corners[4];
545         multires_reshape_propagate_init_patch_corners(
546                 data, delta_grid, patch_x, patch_y, corners);
547         const int start_x = patch_x * skip;
548         const int start_y = patch_y * skip;
549         for (int y = 0; y <= skip; y++) {
550                 const float v = (float)y * skip_inv;
551                 const int final_y = start_y + y;
552                 for (int x = 0; x <= skip; x++) {
553                         const float u = (float)x * skip_inv;
554                         const int final_x = start_x + x;
555                         const float linear_weights[4] = {(1.0f - u) * (1.0f - v),
556                                                          u * (1.0f - v),
557                                                          (1.0f - u) * v,
558                                                          u * v};
559                         multires_reshape_propagate_interpolate_coord(
560                                 CCG_grid_elem_co(delta_level_key, delta_grid,
561                                                  final_x, final_y),
562                                 corners,
563                                 linear_weights);
564                         if (delta_level_key->has_mask) {
565                                 float *mask = CCG_grid_elem_mask(delta_level_key, delta_grid,
566                                                                  final_x, final_y);
567                                 *mask = multires_reshape_propagate_interpolate_mask(
568                                         corners, linear_weights);
569                         }
570                 }
571         }
572 }
573
574 BLI_INLINE void multires_reshape_propagate_and_smooth_delta_grid(
575         MultiresPropagateData *data,
576         CCGElem *delta_grid)
577 {
578         const int orig_grid_size = data->reshape_grid_size;
579         for (int patch_y = 0; patch_y < orig_grid_size - 1; patch_y++) {
580                 for (int patch_x = 0; patch_x < orig_grid_size - 1; patch_x++) {
581                         multires_reshape_propagate_and_smooth_delta_grid_patch(
582                                 data, delta_grid, patch_x, patch_y);
583                 }
584         }
585 }
586
587 /* Entry point to propagate+smooth. */
588 static void multires_reshape_propagate_and_smooth_delta(
589         MultiresPropagateData *data,
590         CCGElem **delta_grids_data)
591 {
592         const int num_grids = data->num_grids;
593         for (int grid_index = 0; grid_index < num_grids; grid_index++) {
594                 CCGElem *delta_grid = delta_grids_data[grid_index];
595                 multires_reshape_propagate_and_smooth_delta_grid(data, delta_grid);
596         }
597 }
598
599 /* Apply smoothed deltas on the actual data layers. */
600 static void multires_reshape_propagate_apply_delta(
601         MultiresPropagateData *data,
602         CCGElem **delta_grids_data)
603 {
604         const int num_grids = data->num_grids;
605         /* At this point those custom data layers has updated data for the
606          * level we are propagating from. */
607         MDisps *mdisps = data->mdisps;
608         GridPaintMask *grid_paint_mask = data->grid_paint_mask;
609         CCGKey *orig_key = &data->reshape_level_key;
610         CCGKey *delta_level_key = &data->top_level_key;
611         CCGElem **orig_grids_data = data->orig_grids_data;
612         const int orig_grid_size = data->reshape_grid_size;
613         const int top_grid_size = data->top_grid_size;
614         const int skip = (top_grid_size - 1) / (orig_grid_size - 1);
615         /* Restore grid values at the reshape level. Those values are to be changed
616          * to the accommodate for the smooth delta. */
617         for (int grid_index = 0; grid_index < num_grids; grid_index++) {
618                 CCGElem *orig_grid = orig_grids_data[grid_index];
619                 for (int y = 0; y < orig_grid_size; y++) {
620                         const int top_y = y * skip;
621                         for (int x = 0; x < orig_grid_size; x++) {
622                                 const int top_x = x * skip;
623                                 const int top_index = top_y * top_grid_size + top_x;
624                                 copy_v3_v3(mdisps[grid_index].disps[top_index],
625                                        CCG_grid_elem_co(orig_key, orig_grid, x, y));
626                                 if (grid_paint_mask != NULL) {
627                                         grid_paint_mask[grid_index].data[top_index] =
628                                                 *CCG_grid_elem_mask(orig_key, orig_grid, x, y);
629                                 }
630                         }
631                 }
632         }
633         /* Add smoothed delta to all the levels. */
634         for (int grid_index = 0; grid_index < num_grids; grid_index++) {
635                 CCGElem *delta_grid = delta_grids_data[grid_index];
636                 for (int y = 0; y < top_grid_size; y++) {
637                         for (int x = 0; x < top_grid_size; x++) {
638                                 const int top_index = y * top_grid_size + x;
639                                 add_v3_v3(mdisps[grid_index].disps[top_index],
640                                        CCG_grid_elem_co(delta_level_key, delta_grid, x, y));
641                                 if (delta_level_key->has_mask) {
642                                         grid_paint_mask[grid_index].data[top_index] +=
643                                                *CCG_grid_elem_mask(
644                                                        delta_level_key, delta_grid, x, y);
645                                 }
646                         }
647                 }
648         }
649 }
650
651 static void multires_reshape_propagate(MultiresPropagateData *data)
652 {
653         if (data->reshape_level == data->top_level) {
654                 return;
655         }
656         const int num_grids = data->num_grids;
657         /* Calculate delta made at the reshape level. */
658         CCGKey *delta_level_key = &data->top_level_key;
659         CCGElem **delta_grids_data = allocate_grids(delta_level_key, num_grids);
660         multires_reshape_calculate_delta(data, delta_grids_data);
661         /* Propagate deltas to the higher levels. */
662         multires_reshape_propagate_and_smooth_delta(data, delta_grids_data);
663         /* Finally, apply smoothed deltas. */
664         multires_reshape_propagate_apply_delta(data, delta_grids_data);
665         /* Cleanup. */
666         free_grids(delta_grids_data, num_grids);
667 }
668
669 static void multires_reshape_propagate_free(MultiresPropagateData *data)
670 {
671         free_grids(data->orig_grids_data, data->num_grids);
672 }
673
674 /* =============================================================================
675  * Reshape from deformed vertex coordinates.
676  */
677
678 typedef struct MultiresReshapeFromDeformedVertsContext {
679         MultiresReshapeContext reshape_ctx;
680         const float (*deformed_verts)[3];
681         int num_deformed_verts;
682 } MultiresReshapeFromDeformedVertsContext;
683
684 static bool multires_reshape_topology_info(
685         const SubdivForeachContext *foreach_context,
686         const int num_vertices,
687         const int UNUSED(num_edges),
688         const int UNUSED(num_loops),
689         const int UNUSED(num_polygons))
690 {
691         MultiresReshapeFromDeformedVertsContext *ctx = foreach_context->user_data;
692         if (num_vertices != ctx->num_deformed_verts) {
693                 return false;
694         }
695         return true;
696 }
697
698 /* Will run reshaping for all grid elements which are adjacent to the given
699  * one. This is the way to ensure continuity of displacement stored in the
700  * grids across the inner boundaries of the grids. */
701 static void multires_reshape_neighour_boundary_vertices(
702         MultiresReshapeContext *ctx,
703         const int UNUSED(ptex_face_index),
704         const float corner_u, const float corner_v,
705         const int coarse_poly_index,
706         const int coarse_corner,
707         const float final_P[3], const float final_mask)
708 {
709         const Mesh *coarse_mesh = ctx->coarse_mesh;
710         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
711         const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index];
712         const int num_corners = coarse_poly->totloop;
713         const int start_ptex_face_index = ctx->face_ptex_offset[coarse_poly_index];
714         const bool is_quad = (coarse_poly->totloop == 4);
715         if (corner_u == 1.0f && corner_v == 1.0f) {
716                 for (int current_corner = 0;
717                      current_corner < num_corners;
718                      ++current_corner)
719                 {
720                         if (current_corner == coarse_corner) {
721                                 continue;
722                         }
723                         const int current_ptex_face_index =
724                                 is_quad ? start_ptex_face_index
725                                         : start_ptex_face_index + current_corner;
726                         multires_reshape_vertex_from_final_data(
727                                 ctx,
728                                 current_ptex_face_index, 1.0f, 1.0f,
729                                 coarse_poly_index,
730                                 current_corner,
731                                 final_P, final_mask);
732                 }
733         }
734         else if (corner_u == 1.0f) {
735                 const float next_corner_index = (coarse_corner + 1) % num_corners;
736                 const float next_corner_u = corner_v;
737                 const float next_corner_v = 1.0f;
738                 const int next_ptex_face_index =
739                         is_quad ? start_ptex_face_index
740                                 : start_ptex_face_index + next_corner_index;
741                 multires_reshape_vertex_from_final_data(
742                         ctx,
743                         next_ptex_face_index, next_corner_u, next_corner_v,
744                         coarse_poly_index,
745                         next_corner_index,
746                         final_P, final_mask);
747         }
748         else if (corner_v == 1.0f) {
749                 const float prev_corner_index =
750                         (coarse_corner + num_corners - 1) % num_corners;
751                 const float prev_corner_u = 1.0f;
752                 const float prev_corner_v = corner_u;
753                 const int prev_ptex_face_index =
754                         is_quad ? start_ptex_face_index
755                                 : start_ptex_face_index + prev_corner_index;
756                 multires_reshape_vertex_from_final_data(
757                         ctx,
758                         prev_ptex_face_index, prev_corner_u, prev_corner_v,
759                         coarse_poly_index,
760                         prev_corner_index,
761                         final_P, final_mask);
762         }
763 }
764
765 static void multires_reshape_vertex(
766         MultiresReshapeFromDeformedVertsContext *ctx,
767         const int ptex_face_index,
768         const float u, const float v,
769         const int coarse_poly_index,
770         const int coarse_corner,
771         const int subdiv_vertex_index)
772 {
773         const float *final_P = ctx->deformed_verts[subdiv_vertex_index];
774         const Mesh *coarse_mesh = ctx->reshape_ctx.coarse_mesh;
775         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
776         const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index];
777         const bool is_quad = (coarse_poly->totloop == 4);
778         float corner_u, corner_v;
779         int actual_coarse_corner;
780         if (is_quad) {
781                 actual_coarse_corner = BKE_subdiv_rotate_quad_to_corner(
782                         u, v, &corner_u, &corner_v);
783         }
784         else {
785                 actual_coarse_corner = coarse_corner;
786                 corner_u = u;
787                 corner_v = v;
788         }
789         multires_reshape_vertex_from_final_data(
790                 &ctx->reshape_ctx,
791                 ptex_face_index, corner_u, corner_v,
792                 coarse_poly_index,
793                 actual_coarse_corner,
794                 final_P, 0.0f);
795         multires_reshape_neighour_boundary_vertices(
796                 &ctx->reshape_ctx,
797                 ptex_face_index, corner_u, corner_v,
798                 coarse_poly_index,
799                 actual_coarse_corner,
800                 final_P, 0.0f);
801 }
802
803 static void multires_reshape_vertex_inner(
804         const SubdivForeachContext *foreach_context,
805         void *UNUSED(tls_v),
806         const int ptex_face_index,
807         const float u, const float v,
808         const int coarse_poly_index,
809         const int coarse_corner,
810         const int subdiv_vertex_index)
811 {
812         MultiresReshapeFromDeformedVertsContext *ctx = foreach_context->user_data;
813         multires_reshape_vertex(
814                 ctx,
815                 ptex_face_index, u, v,
816                 coarse_poly_index,
817                 coarse_corner,
818                 subdiv_vertex_index);
819 }
820
821 static void multires_reshape_vertex_every_corner(
822         const struct SubdivForeachContext *foreach_context,
823         void *UNUSED(tls_v),
824         const int ptex_face_index,
825         const float u, const float v,
826         const int UNUSED(coarse_vertex_index),
827         const int coarse_poly_index,
828         const int coarse_corner,
829         const int subdiv_vertex_index)
830 {
831         MultiresReshapeFromDeformedVertsContext *ctx = foreach_context->user_data;
832         multires_reshape_vertex(
833                 ctx,
834                 ptex_face_index, u, v,
835                 coarse_poly_index,
836                 coarse_corner,
837                 subdiv_vertex_index);
838 }
839
840 static void multires_reshape_vertex_every_edge(
841         const struct SubdivForeachContext *foreach_context,
842         void *UNUSED(tls_v),
843         const int ptex_face_index,
844         const float u, const float v,
845         const int UNUSED(coarse_edge_index),
846         const int coarse_poly_index,
847         const int coarse_corner,
848         const int subdiv_vertex_index)
849 {
850         MultiresReshapeFromDeformedVertsContext *ctx = foreach_context->user_data;
851         multires_reshape_vertex(
852                 ctx,
853                 ptex_face_index, u, v,
854                 coarse_poly_index,
855                 coarse_corner,
856                 subdiv_vertex_index);
857 }
858
859 static Subdiv *multires_create_subdiv_for_reshape(
860         struct Depsgraph *depsgraph,
861         /*const*/ Object *object,
862         const MultiresModifierData *mmd)
863 {
864         Scene *scene_eval = DEG_get_evaluated_scene(depsgraph);
865         Object *object_eval = DEG_get_evaluated_object(depsgraph, object);
866         Mesh *deformed_mesh = mesh_get_eval_deform(
867                 depsgraph, scene_eval, object_eval, CD_MASK_BAREMESH);
868         SubdivSettings subdiv_settings;
869         BKE_multires_subdiv_settings_init(&subdiv_settings, mmd);
870         Subdiv *subdiv = BKE_subdiv_new_from_mesh(&subdiv_settings, deformed_mesh);
871         if (!BKE_subdiv_eval_update_from_mesh(subdiv, deformed_mesh)) {
872                 BKE_subdiv_free(subdiv);
873                 return NULL;
874         }
875         return subdiv;
876 }
877
878 static bool multires_reshape_from_vertcos(
879         struct Depsgraph *depsgraph,
880         Object *object,
881         const MultiresModifierData *mmd,
882         const float (*deformed_verts)[3],
883         const int num_deformed_verts,
884         const bool use_render_params)
885 {
886         Scene *scene_eval = DEG_get_evaluated_scene(depsgraph);
887         Mesh *coarse_mesh = object->data;
888         MDisps *mdisps = CustomData_get_layer(&coarse_mesh->ldata, CD_MDISPS);
889         /* Pick maximum between multires level and dispalcement level.
890          * This is because mesh can be used by objects with multires at different
891          * levels.
892          *
893          * TODO(sergey): At this point it should be possible to always use
894          * mdisps->level. */
895         const int top_level = max_ii(mmd->totlvl, mdisps->level);
896         /* Make sure displacement grids are ready. */
897         multires_reshape_ensure_grids(coarse_mesh, top_level);
898         /* Initialize subdivision surface. */
899         Subdiv *subdiv = multires_create_subdiv_for_reshape(depsgraph, object, mmd);
900         if (subdiv == NULL) {
901                 return false;
902         }
903         /* Construct context. */
904         MultiresReshapeFromDeformedVertsContext reshape_deformed_verts_ctx = {
905                 .reshape_ctx = {
906                         .subdiv = subdiv,
907                         .coarse_mesh = coarse_mesh,
908                         .mdisps = mdisps,
909                         .grid_paint_mask = NULL,
910                         .top_grid_size = BKE_subdiv_grid_size_from_level(top_level),
911                         .top_level = top_level,
912                         .face_ptex_offset = BKE_subdiv_face_ptex_offset_get(subdiv),
913                 },
914                 .deformed_verts = deformed_verts,
915                 .num_deformed_verts = num_deformed_verts,
916         };
917         SubdivForeachContext foreach_context = {
918                 .topology_info = multires_reshape_topology_info,
919                 .vertex_inner = multires_reshape_vertex_inner,
920                 .vertex_every_edge = multires_reshape_vertex_every_edge,
921                 .vertex_every_corner = multires_reshape_vertex_every_corner,
922                 .user_data = &reshape_deformed_verts_ctx,
923         };
924         /* Initialize mesh rasterization settings. */
925         SubdivToMeshSettings mesh_settings;
926         BKE_multires_subdiv_mesh_settings_init(
927         &mesh_settings, scene_eval, object, mmd, use_render_params, true);
928         /* Initialize propagation to higher levels. */
929         MultiresPropagateData propagate_data;
930         multires_reshape_propagate_prepare_from_mmd(
931         &propagate_data, depsgraph, object, mmd, top_level, use_render_params);
932         /* Run all the callbacks. */
933         BKE_subdiv_foreach_subdiv_geometry(
934                 subdiv,
935                 &foreach_context,
936                 &mesh_settings,
937                 coarse_mesh);
938         BKE_subdiv_free(subdiv);
939         /* Update higher levels if needed. */
940         multires_reshape_propagate(&propagate_data);
941         multires_reshape_propagate_free(&propagate_data);
942         return true;
943 }
944
945 /* =============================================================================
946  * Reshape from object.
947  */
948
949 /* Returns truth on success, false otherwise.
950  *
951  * This function might fail in cases like source and destination not having
952  * matched amount of vertices. */
953 bool multiresModifier_reshapeFromObject(
954         struct Depsgraph *depsgraph,
955         MultiresModifierData *mmd,
956         Object *dst,
957         Object *src)
958 {
959         /* Would be cool to support this eventually, but it is very tricky to match
960          * vertices order even for meshes, when mixing meshes and other objects it's
961          * even more tricky. */
962         if (src->type != OB_MESH) {
963                 return false;
964         }
965         MultiresModifierData reshape_mmd;
966         multires_reshape_init_mmd(&reshape_mmd, mmd);
967         /* Get evaluated vertices locations to reshape to. */
968         Scene *scene_eval = DEG_get_evaluated_scene(depsgraph);
969         Object *src_eval = DEG_get_evaluated_object(depsgraph, src);
970         Mesh *src_mesh_eval = mesh_get_eval_final(
971                 depsgraph, scene_eval, src_eval, CD_MASK_BAREMESH);
972         int num_deformed_verts;
973         float (*deformed_verts)[3] = BKE_mesh_vertexCos_get(
974                 src_mesh_eval, &num_deformed_verts);
975         bool result = multires_reshape_from_vertcos(
976                 depsgraph,
977                 dst,
978                 &reshape_mmd,
979                 deformed_verts,
980                 num_deformed_verts,
981                 false);
982         MEM_freeN(deformed_verts);
983         return result;
984 }
985
986 /* =============================================================================
987  * Reshape from modifier.
988  */
989
990 bool multiresModifier_reshapeFromDeformModifier(
991         struct Depsgraph *depsgraph,
992         MultiresModifierData *mmd,
993         Object *object,
994         ModifierData *md)
995 {
996         MultiresModifierData highest_mmd;
997         /* It is possible that the current subdivision level of multires is lower
998          * that it's maximum possible one (i.e., viewport is set to a lower level
999          * for the performance purposes). But even then, we want all the multires
1000          * levels to be reshaped. Most accurate way to do so is to ignore all
1001          * simplifications and calculate deformation modifier for the highest
1002          * possible multires level.
1003          * Alternative would be propagate displacement from current level to a
1004          * higher ones, but that is likely to cause artifacts. */
1005         multires_reshape_init_mmd_top_level(&highest_mmd, mmd);
1006         Scene *scene_eval = DEG_get_evaluated_scene(depsgraph);
1007         /* Perform sanity checks and early output. */
1008         if (multires_get_level(
1009                     scene_eval, object, &highest_mmd, false, true) == 0)
1010         {
1011                 return false;
1012         }
1013         /* Create mesh for the multires, ignoring any further modifiers (leading
1014          * deformation modifiers will be applied though). */
1015         Mesh *multires_mesh = BKE_multires_create_mesh(
1016                 depsgraph, scene_eval, &highest_mmd, object);
1017         int num_deformed_verts;
1018         float (*deformed_verts)[3] = BKE_mesh_vertexCos_get(
1019                 multires_mesh, &num_deformed_verts);
1020         /* Apply deformation modifier on the multires, */
1021         const ModifierEvalContext modifier_ctx = {
1022                 .depsgraph = depsgraph,
1023                 .object = object,
1024                 .flag = MOD_APPLY_USECACHE | MOD_APPLY_IGNORE_SIMPLIFY,
1025         };
1026         modwrap_deformVerts(
1027                 md, &modifier_ctx, multires_mesh, deformed_verts,
1028                 multires_mesh->totvert);
1029         BKE_id_free(NULL, multires_mesh);
1030         /* Reshaping */
1031         bool result = multires_reshape_from_vertcos(
1032                 depsgraph,
1033                 object,
1034                 &highest_mmd,
1035                 deformed_verts,
1036                 num_deformed_verts,
1037                 false);
1038         /* Cleanup */
1039         MEM_freeN(deformed_verts);
1040         return result;
1041 }
1042
1043 /* =============================================================================
1044  * Reshape from grids.
1045  */
1046
1047 typedef struct ReshapeFromCCGTaskData {
1048         MultiresReshapeContext reshape_ctx;
1049         const CCGKey *key;
1050         /*const*/ CCGElem **grids;
1051 } ReshapeFromCCGTaskData;
1052
1053 static void reshape_from_ccg_task(
1054         void *__restrict userdata,
1055         const int coarse_poly_index,
1056         const ParallelRangeTLS *__restrict UNUSED(tls))
1057 {
1058         ReshapeFromCCGTaskData *data = userdata;
1059         const CCGKey *key = data->key;
1060         /*const*/ CCGElem **grids = data->grids;
1061         const Mesh *coarse_mesh = data->reshape_ctx.coarse_mesh;
1062         const MPoly *coarse_mpoly = coarse_mesh->mpoly;
1063         const MPoly *coarse_poly = &coarse_mpoly[coarse_poly_index];
1064         const int key_grid_size = key->grid_size;
1065         const int key_grid_size_1 = key_grid_size - 1;
1066         const int resolution = key_grid_size;
1067         const float resolution_1_inv = 1.0f / (float)(resolution - 1);
1068         const int start_ptex_face_index =
1069                 data->reshape_ctx.face_ptex_offset[coarse_poly_index];
1070         const bool is_quad = (coarse_poly->totloop == 4);
1071         for (int corner = 0; corner < coarse_poly->totloop; corner++) {
1072                 for (int y = 0; y < resolution; y++) {
1073                         const float corner_v = y * resolution_1_inv;
1074                         for (int x = 0; x < resolution; x++) {
1075                                 const float corner_u = x * resolution_1_inv;
1076                                 /* Quad faces consists of a single ptex face. */
1077                                 const int ptex_face_index =
1078                                         is_quad ? start_ptex_face_index
1079                                                 : start_ptex_face_index + corner;
1080                                 float grid_u, grid_v;
1081                                 BKE_subdiv_ptex_face_uv_to_grid_uv(
1082                                         corner_u, corner_v, &grid_u, &grid_v);
1083                                 /*const*/ CCGElem *grid =
1084                                         grids[coarse_poly->loopstart + corner];
1085                                 /*const*/ CCGElem *grid_element = CCG_grid_elem(
1086                                         key,
1087                                         grid,
1088                                         key_grid_size_1 * grid_u,
1089                                         key_grid_size_1 * grid_v);
1090                                 const float *final_P = CCG_elem_co(key, grid_element);
1091                                 float final_mask = 0.0f;
1092                                 if (key->has_mask) {
1093                                         final_mask = *CCG_elem_mask(key, grid_element);
1094                                 }
1095                                 multires_reshape_vertex_from_final_data(
1096                                         &data->reshape_ctx,
1097                                         ptex_face_index,
1098                                         corner_u, corner_v,
1099                                         coarse_poly_index,
1100                                         corner,
1101                                         final_P, final_mask);
1102                         }
1103                 }
1104         }
1105 }
1106
1107 bool multiresModifier_reshapeFromCCG(
1108         const int tot_level,
1109         Mesh *coarse_mesh,
1110         SubdivCCG *subdiv_ccg)
1111 {
1112         CCGKey key;
1113         BKE_subdiv_ccg_key_top_level(&key, subdiv_ccg);
1114         /* Sanity checks. */
1115         if (coarse_mesh->totloop != subdiv_ccg->num_grids) {
1116                 /* Grids are supposed to eb created for each face-cornder (aka loop). */
1117                 return false;
1118         }
1119         MDisps *mdisps = CustomData_get_layer(&coarse_mesh->ldata, CD_MDISPS);
1120         if (mdisps == NULL) {
1121                 /* Multires displacement has been removed before current changes were
1122                  * applies to all the levels. */
1123                 return false;
1124         }
1125         GridPaintMask *grid_paint_mask =
1126                 CustomData_get_layer(&coarse_mesh->ldata, CD_GRID_PAINT_MASK);
1127         Subdiv *subdiv = subdiv_ccg->subdiv;
1128         /* Pick maximum between multires level and dispalcement level.
1129          * This is because mesh can be used by objects with multires at different
1130          * levels.
1131          *
1132          * TODO(sergey): At this point it should be possible to always use
1133          * mdisps->level. */
1134         const int top_level = max_ii(tot_level, mdisps->level);
1135         /* Make sure displacement grids are ready. */
1136         multires_reshape_ensure_grids(coarse_mesh, top_level);
1137         /* Construct context. */
1138         ReshapeFromCCGTaskData data = {
1139                 .reshape_ctx = {
1140                         .subdiv = subdiv,
1141                         .coarse_mesh = coarse_mesh,
1142                         .mdisps  = mdisps,
1143                         .grid_paint_mask = grid_paint_mask,
1144                         .top_grid_size = BKE_subdiv_grid_size_from_level(top_level),
1145                         .top_level = top_level,
1146                         .face_ptex_offset = BKE_subdiv_face_ptex_offset_get(subdiv),
1147                 },
1148                 .key = &key,
1149                 .grids = subdiv_ccg->grids,
1150         };
1151         /* Initialize propagation to higher levels. */
1152         MultiresPropagateData propagate_data;
1153         multires_reshape_propagate_prepare(
1154                 &propagate_data, coarse_mesh, key.level, top_level);
1155         /* Threaded grids iteration. */
1156         ParallelRangeSettings parallel_range_settings;
1157         BLI_parallel_range_settings_defaults(&parallel_range_settings);
1158         BLI_task_parallel_range(0, coarse_mesh->totpoly,
1159                                 &data,
1160                                 reshape_from_ccg_task,
1161                                 &parallel_range_settings);
1162         /* Update higher levels if needed. */
1163         multires_reshape_propagate(&propagate_data);
1164         multires_reshape_propagate_free(&propagate_data);
1165         return true;
1166 }