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