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