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