doxygen: add newline after \file
[blender.git] / source / blender / bmesh / intern / bmesh_interp.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) 2007 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bmesh
22  *
23  * Functions for interpolating data across the surface of a mesh.
24  */
25
26 #include "MEM_guardedalloc.h"
27
28 #include "DNA_meshdata_types.h"
29
30 #include "BLI_alloca.h"
31 #include "BLI_linklist.h"
32 #include "BLI_math.h"
33 #include "BLI_memarena.h"
34 #include "BLI_task.h"
35
36 #include "BKE_customdata.h"
37 #include "BKE_multires.h"
38
39 #include "bmesh.h"
40 #include "intern/bmesh_private.h"
41
42 /* edge and vertex share, currently theres no need to have different logic */
43 static void bm_data_interp_from_elem(
44         CustomData *data_layer, const BMElem *ele_src_1, const BMElem *ele_src_2,
45         BMElem *ele_dst, const float fac)
46 {
47         if (ele_src_1->head.data && ele_src_2->head.data) {
48                 /* first see if we can avoid interpolation */
49                 if (fac <= 0.0f) {
50                         if (ele_src_1 == ele_dst) {
51                                 /* do nothing */
52                         }
53                         else {
54                                 CustomData_bmesh_free_block_data(data_layer, ele_dst->head.data);
55                                 CustomData_bmesh_copy_data(data_layer, data_layer, ele_src_1->head.data, &ele_dst->head.data);
56                         }
57                 }
58                 else if (fac >= 1.0f) {
59                         if (ele_src_2 == ele_dst) {
60                                 /* do nothing */
61                         }
62                         else {
63                                 CustomData_bmesh_free_block_data(data_layer, ele_dst->head.data);
64                                 CustomData_bmesh_copy_data(data_layer, data_layer, ele_src_2->head.data, &ele_dst->head.data);
65                         }
66                 }
67                 else {
68                         const void *src[2];
69                         float w[2];
70
71                         src[0] = ele_src_1->head.data;
72                         src[1] = ele_src_2->head.data;
73                         w[0] = 1.0f - fac;
74                         w[1] = fac;
75                         CustomData_bmesh_interp(data_layer, src, w, NULL, 2, ele_dst->head.data);
76                 }
77         }
78 }
79
80 /**
81  * \brief Data, Interp From Verts
82  *
83  * Interpolates per-vertex data from two sources to \a v_dst
84  *
85  * \note This is an exact match to #BM_data_interp_from_edges
86  */
87 void BM_data_interp_from_verts(BMesh *bm, const BMVert *v_src_1, const BMVert *v_src_2, BMVert *v_dst, const float fac)
88 {
89         bm_data_interp_from_elem(&bm->vdata, (const BMElem *)v_src_1, (const BMElem *)v_src_2, (BMElem *)v_dst, fac);
90 }
91
92 /**
93  * \brief Data, Interp From Edges
94  *
95  * Interpolates per-edge data from two sources to \a e_dst.
96  *
97  * \note This is an exact match to #BM_data_interp_from_verts
98  */
99 void BM_data_interp_from_edges(BMesh *bm, const BMEdge *e_src_1, const BMEdge *e_src_2, BMEdge *e_dst, const float fac)
100 {
101         bm_data_interp_from_elem(&bm->edata, (const BMElem *)e_src_1, (const BMElem *)e_src_2, (BMElem *)e_dst, fac);
102 }
103
104 /**
105  * \brief Data Vert Average
106  *
107  * Sets all the customdata (e.g. vert, loop) associated with a vert
108  * to the average of the face regions surrounding it.
109  */
110 static void UNUSED_FUNCTION(BM_Data_Vert_Average)(BMesh *UNUSED(bm), BMFace *UNUSED(f))
111 {
112         // BMIter iter;
113 }
114
115 /**
116  * \brief Data Face-Vert Edge Interp
117  *
118  * Walks around the faces of \a e and interpolates
119  * the loop data between two sources.
120  */
121 void BM_data_interp_face_vert_edge(
122         BMesh *bm, const BMVert *v_src_1, const BMVert *UNUSED(v_src_2), BMVert *v, BMEdge *e, const float fac)
123 {
124         float w[2];
125         BMLoop *l_v1 = NULL, *l_v = NULL, *l_v2 = NULL;
126         BMLoop *l_iter = NULL;
127
128         if (!e->l) {
129                 return;
130         }
131
132         w[1] = 1.0f - fac;
133         w[0] = fac;
134
135         l_iter = e->l;
136         do {
137                 if (l_iter->v == v_src_1) {
138                         l_v1 = l_iter;
139                         l_v = l_v1->next;
140                         l_v2 = l_v->next;
141                 }
142                 else if (l_iter->v == v) {
143                         l_v1 = l_iter->next;
144                         l_v = l_iter;
145                         l_v2 = l_iter->prev;
146                 }
147
148                 if (!l_v1 || !l_v2) {
149                         return;
150                 }
151                 else {
152                         const void *src[2];
153                         src[0] = l_v1->head.data;
154                         src[1] = l_v2->head.data;
155
156                         CustomData_bmesh_interp(&bm->ldata, src, w, NULL, 2, l_v->head.data);
157                 }
158         } while ((l_iter = l_iter->radial_next) != e->l);
159 }
160
161 /**
162  * \brief Data Interp From Face
163  *
164  * projects target onto source, and pulls interpolated customdata from
165  * source.
166  *
167  * \note Only handles loop customdata. multires is handled.
168  */
169 void BM_face_interp_from_face_ex(
170         BMesh *bm, BMFace *f_dst, const BMFace *f_src, const bool do_vertex,
171         const void **blocks_l, const void **blocks_v, float (*cos_2d)[2], float axis_mat[3][3])
172 {
173         BMLoop *l_iter;
174         BMLoop *l_first;
175
176         float *w = BLI_array_alloca(w, f_src->len);
177         float co[2];
178         int i;
179
180         if (f_src != f_dst)
181                 BM_elem_attrs_copy(bm, bm, f_src, f_dst);
182
183         /* interpolate */
184         i = 0;
185         l_iter = l_first = BM_FACE_FIRST_LOOP(f_dst);
186         do {
187                 mul_v2_m3v3(co, axis_mat, l_iter->v->co);
188                 interp_weights_poly_v2(w, cos_2d, f_src->len, co);
189                 CustomData_bmesh_interp(&bm->ldata, blocks_l, w, NULL, f_src->len, l_iter->head.data);
190                 if (do_vertex) {
191                         CustomData_bmesh_interp(&bm->vdata, blocks_v, w, NULL, f_src->len, l_iter->v->head.data);
192                 }
193         } while ((void)i++, (l_iter = l_iter->next) != l_first);
194 }
195
196 void BM_face_interp_from_face(BMesh *bm, BMFace *f_dst, const BMFace *f_src, const bool do_vertex)
197 {
198         BMLoop *l_iter;
199         BMLoop *l_first;
200
201         const void **blocks_l    = BLI_array_alloca(blocks_l, f_src->len);
202         const void **blocks_v    = do_vertex ? BLI_array_alloca(blocks_v, f_src->len) : NULL;
203         float (*cos_2d)[2] = BLI_array_alloca(cos_2d, f_src->len);
204         float axis_mat[3][3];  /* use normal to transform into 2d xy coords */
205         int i;
206
207         /* convert the 3d coords into 2d for projection */
208         BLI_assert(BM_face_is_normal_valid(f_src));
209         axis_dominant_v3_to_m3(axis_mat, f_src->no);
210
211         i = 0;
212         l_iter = l_first = BM_FACE_FIRST_LOOP(f_src);
213         do {
214                 mul_v2_m3v3(cos_2d[i], axis_mat, l_iter->v->co);
215                 blocks_l[i] = l_iter->head.data;
216                 if (do_vertex) blocks_v[i] = l_iter->v->head.data;
217         } while ((void)i++, (l_iter = l_iter->next) != l_first);
218
219         BM_face_interp_from_face_ex(bm, f_dst, f_src, do_vertex,
220                                     blocks_l, blocks_v, cos_2d, axis_mat);
221 }
222
223 /**
224  * \brief Multires Interpolation
225  *
226  * mdisps is a grid of displacements, ordered thus:
227  * <pre>
228  *      v1/center----v4/next -> x
229  *          |           |
230  *          |           |
231  *       v2/prev------v3/cur
232  *          |
233  *          V
234  *          y
235  * </pre>
236  */
237 static int compute_mdisp_quad(
238         const BMLoop *l, const float l_f_center[3],
239         float v1[3], float v2[3], float v3[3], float v4[3],
240         float e1[3], float e2[3])
241 {
242         float n[3], p[3];
243
244 #ifndef NDEBUG
245         {
246                 float cent[3];
247                 /* computer center */
248                 BM_face_calc_center_median(l->f, cent);
249                 BLI_assert(equals_v3v3(cent, l_f_center));
250         }
251 #endif
252
253         mid_v3_v3v3(p, l->prev->v->co, l->v->co);
254         mid_v3_v3v3(n, l->next->v->co, l->v->co);
255
256         copy_v3_v3(v1, l_f_center);
257         copy_v3_v3(v2, p);
258         copy_v3_v3(v3, l->v->co);
259         copy_v3_v3(v4, n);
260
261         sub_v3_v3v3(e1, v2, v1);
262         sub_v3_v3v3(e2, v3, v4);
263
264         return 1;
265 }
266
267 static bool quad_co(
268         const float v1[3], const float v2[3], const float v3[3], const float v4[3],
269         const float p[3], const float n[3],
270         float r_uv[2])
271 {
272         float projverts[5][3], n2[3];
273         float origin[2] = {0.0f, 0.0f};
274         int i;
275
276         /* project points into 2d along normal */
277         copy_v3_v3(projverts[0], v1);
278         copy_v3_v3(projverts[1], v2);
279         copy_v3_v3(projverts[2], v3);
280         copy_v3_v3(projverts[3], v4);
281         copy_v3_v3(projverts[4], p);
282
283         normal_quad_v3(n2, projverts[0], projverts[1], projverts[2], projverts[3]);
284
285         if (dot_v3v3(n, n2) < -FLT_EPSILON) {
286                 return false;
287         }
288
289         /* rotate */
290         poly_rotate_plane(n, projverts, 5);
291
292         /* subtract origin */
293         for (i = 0; i < 4; i++) {
294                 sub_v2_v2(projverts[i], projverts[4]);
295         }
296
297         if (!isect_point_quad_v2(origin, projverts[0], projverts[1], projverts[2], projverts[3])) {
298                 return false;
299         }
300
301         resolve_quad_uv_v2(r_uv, origin, projverts[0], projverts[3], projverts[2], projverts[1]);
302
303         return true;
304 }
305
306 static void mdisp_axis_from_quad(
307         float v1[3], float v2[3], float UNUSED(v3[3]), float v4[3],
308         float r_axis_x[3], float r_axis_y[3])
309 {
310         sub_v3_v3v3(r_axis_x, v4, v1);
311         sub_v3_v3v3(r_axis_y, v2, v1);
312
313         normalize_v3(r_axis_x);
314         normalize_v3(r_axis_y);
315 }
316
317 /* tl is loop to project onto, l is loop whose internal displacement, co, is being
318  * projected.  x and y are location in loop's mdisps grid of point co. */
319 static bool mdisp_in_mdispquad(
320         BMLoop *l_src, BMLoop *l_dst, const float l_dst_f_center[3],
321         const float p[3], int res,
322         float r_axis_x[3], float r_axis_y[3], float r_uv[2])
323 {
324         float v1[3], v2[3], c[3], v3[3], v4[3], e1[3], e2[3];
325         float eps = FLT_EPSILON * 4000;
326
327         if (is_zero_v3(l_src->v->no))
328                 BM_vert_normal_update_all(l_src->v);
329         if (is_zero_v3(l_dst->v->no))
330                 BM_vert_normal_update_all(l_dst->v);
331
332         compute_mdisp_quad(l_dst, l_dst_f_center, v1, v2, v3, v4, e1, e2);
333
334         /* expand quad a bit */
335         mid_v3_v3v3v3v3(c, v1, v2, v3, v4);
336
337         sub_v3_v3(v1, c); sub_v3_v3(v2, c);
338         sub_v3_v3(v3, c); sub_v3_v3(v4, c);
339         mul_v3_fl(v1, 1.0f + eps); mul_v3_fl(v2, 1.0f + eps);
340         mul_v3_fl(v3, 1.0f + eps); mul_v3_fl(v4, 1.0f + eps);
341         add_v3_v3(v1, c); add_v3_v3(v2, c);
342         add_v3_v3(v3, c); add_v3_v3(v4, c);
343
344         if (!quad_co(v1, v2, v3, v4, p, l_src->v->no, r_uv))
345                 return 0;
346
347         mul_v2_fl(r_uv, (float)(res - 1));
348
349         mdisp_axis_from_quad(v1, v2, v3, v4, r_axis_x, r_axis_y);
350
351         return 1;
352 }
353
354 static float bm_loop_flip_equotion(
355         float mat[2][2], float b[2], const float target_axis_x[3], const float target_axis_y[3],
356         const float coord[3], int i, int j)
357 {
358         mat[0][0] = target_axis_x[i];
359         mat[0][1] = target_axis_y[i];
360         mat[1][0] = target_axis_x[j];
361         mat[1][1] = target_axis_y[j];
362         b[0] = coord[i];
363         b[1] = coord[j];
364
365         return cross_v2v2(mat[0], mat[1]);
366 }
367
368 static void bm_loop_flip_disp(
369         const float source_axis_x[3], const float source_axis_y[3],
370         const float target_axis_x[3], const float target_axis_y[3], float disp[3])
371 {
372         float vx[3], vy[3], coord[3];
373         float n[3], vec[3];
374         float b[2], mat[2][2], d;
375
376         mul_v3_v3fl(vx, source_axis_x, disp[0]);
377         mul_v3_v3fl(vy, source_axis_y, disp[1]);
378         add_v3_v3v3(coord, vx, vy);
379
380         /* project displacement from source grid plane onto target grid plane */
381         cross_v3_v3v3(n, target_axis_x, target_axis_y);
382         project_v3_v3v3(vec, coord, n);
383         sub_v3_v3v3(coord, coord, vec);
384
385         d = bm_loop_flip_equotion(mat, b, target_axis_x, target_axis_y, coord, 0, 1);
386
387         if (fabsf(d) < 1e-4f) {
388                 d = bm_loop_flip_equotion(mat, b, target_axis_x, target_axis_y, coord, 0, 2);
389                 if (fabsf(d) < 1e-4f)
390                         d = bm_loop_flip_equotion(mat, b, target_axis_x, target_axis_y, coord, 1, 2);
391         }
392
393         disp[0] = (b[0] * mat[1][1] - mat[0][1] * b[1]) / d;
394         disp[1] = (mat[0][0] * b[1] - b[0] * mat[1][0]) / d;
395 }
396
397
398 typedef struct BMLoopInterpMultiresData {
399         BMLoop *l_dst;
400         BMLoop *l_src_first;
401         int cd_loop_mdisp_offset;
402
403         MDisps *md_dst;
404         const float *f_src_center;
405
406         float *axis_x, *axis_y;
407         float *v1, *v4;
408         float *e1, *e2;
409
410         int res;
411         float d;
412 } BMLoopInterpMultiresData;
413
414 static void loop_interp_multires_cb(
415         void *__restrict userdata,
416         const int ix,
417         const ParallelRangeTLS *__restrict UNUSED(tls))
418 {
419         BMLoopInterpMultiresData *data = userdata;
420
421         BMLoop *l_first = data->l_src_first;
422         BMLoop *l_dst = data->l_dst;
423         const int cd_loop_mdisp_offset = data->cd_loop_mdisp_offset;
424
425         MDisps *md_dst = data->md_dst;
426         const float *f_src_center = data->f_src_center;
427
428         float *axis_x = data->axis_x;
429         float *axis_y = data->axis_y;
430
431         float *v1 = data->v1;
432         float *v4 = data->v4;
433         float *e1 = data->e1;
434         float *e2 = data->e2;
435
436         const int res = data->res;
437         const float d = data->d;
438
439         float x = d * ix, y;
440         int iy;
441         for (y = 0.0f, iy = 0; iy < res; y += d, iy++) {
442                 BMLoop *l_iter = l_first;
443                 float co1[3], co2[3], co[3];
444
445                 madd_v3_v3v3fl(co1, v1, e1, y);
446                 madd_v3_v3v3fl(co2, v4, e2, y);
447                 interp_v3_v3v3(co, co1, co2, x);
448
449                 do {
450                         MDisps *md_src;
451                         float src_axis_x[3], src_axis_y[3];
452                         float uv[2];
453
454                         md_src = BM_ELEM_CD_GET_VOID_P(l_iter, cd_loop_mdisp_offset);
455
456                         if (mdisp_in_mdispquad(l_dst, l_iter, f_src_center, co, res, src_axis_x, src_axis_y, uv)) {
457                                 old_mdisps_bilinear(md_dst->disps[iy * res + ix], md_src->disps, res, uv[0], uv[1]);
458                                 bm_loop_flip_disp(src_axis_x, src_axis_y, axis_x, axis_y, md_dst->disps[iy * res + ix]);
459
460                                 break;
461                         }
462                 } while ((l_iter = l_iter->next) != l_first);
463         }
464 }
465
466 void BM_loop_interp_multires_ex(
467         BMesh *UNUSED(bm), BMLoop *l_dst, const BMFace *f_src,
468         const float f_dst_center[3], const float f_src_center[3], const int cd_loop_mdisp_offset)
469 {
470         MDisps *md_dst;
471         float v1[3], v2[3], v3[3], v4[3] = {0.0f, 0.0f, 0.0f}, e1[3], e2[3];
472         float axis_x[3], axis_y[3];
473
474         /* ignore 2-edged faces */
475         if (UNLIKELY(l_dst->f->len < 3))
476                 return;
477
478         md_dst = BM_ELEM_CD_GET_VOID_P(l_dst, cd_loop_mdisp_offset);
479         compute_mdisp_quad(l_dst, f_dst_center, v1, v2, v3, v4, e1, e2);
480
481         /* if no disps data allocate a new grid, the size of the first grid in f_src. */
482         if (!md_dst->totdisp) {
483                 const MDisps *md_src = BM_ELEM_CD_GET_VOID_P(BM_FACE_FIRST_LOOP(f_src), cd_loop_mdisp_offset);
484
485                 md_dst->totdisp = md_src->totdisp;
486                 md_dst->level = md_src->level;
487                 if (md_dst->totdisp) {
488                         md_dst->disps = MEM_callocN(sizeof(float) * 3 * md_dst->totdisp, __func__);
489                 }
490                 else {
491                         return;
492                 }
493         }
494
495         mdisp_axis_from_quad(v1, v2, v3, v4, axis_x, axis_y);
496
497         const int res = (int)sqrt(md_dst->totdisp);
498         BMLoopInterpMultiresData data = {
499                 .l_dst = l_dst, .l_src_first = BM_FACE_FIRST_LOOP(f_src),
500                 .cd_loop_mdisp_offset = cd_loop_mdisp_offset,
501                 .md_dst = md_dst, .f_src_center = f_src_center,
502                 .axis_x = axis_x, .axis_y = axis_y, .v1 = v1, .v4 = v4, .e1 = e1, .e2 = e2,
503                 .res = res, .d = 1.0f / (float)(res - 1),
504         };
505         ParallelRangeSettings settings;
506         BLI_parallel_range_settings_defaults(&settings);
507         settings.use_threading = (res > 5);
508         BLI_task_parallel_range(0, res, &data, loop_interp_multires_cb, &settings);
509 }
510
511 /**
512  * project the multires grid in target onto f_src's set of multires grids
513  */
514 void BM_loop_interp_multires(BMesh *bm, BMLoop *l_dst, const BMFace *f_src)
515 {
516         const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
517
518         if (cd_loop_mdisp_offset != -1) {
519                 float f_dst_center[3];
520                 float f_src_center[3];
521
522                 BM_face_calc_center_median(l_dst->f, f_dst_center);
523                 BM_face_calc_center_median(f_src,    f_src_center);
524
525                 BM_loop_interp_multires_ex(bm, l_dst, f_src, f_dst_center, f_src_center, cd_loop_mdisp_offset);
526         }
527 }
528
529 void BM_face_interp_multires_ex(
530         BMesh *bm, BMFace *f_dst, const BMFace *f_src,
531         const float f_dst_center[3], const float f_src_center[3], const int cd_loop_mdisp_offset)
532 {
533         BMLoop *l_iter, *l_first;
534         l_iter = l_first = BM_FACE_FIRST_LOOP(f_dst);
535         do {
536                 BM_loop_interp_multires_ex(
537                         bm, l_iter, f_src,
538                         f_dst_center, f_src_center, cd_loop_mdisp_offset);
539         } while ((l_iter = l_iter->next) != l_first);
540 }
541
542 void BM_face_interp_multires(BMesh *bm, BMFace *f_dst, const BMFace *f_src)
543 {
544         const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
545
546         if (cd_loop_mdisp_offset != -1) {
547                 float f_dst_center[3];
548                 float f_src_center[3];
549
550                 BM_face_calc_center_median(f_dst, f_dst_center);
551                 BM_face_calc_center_median(f_src, f_src_center);
552
553                 BM_face_interp_multires_ex(bm, f_dst, f_src, f_dst_center, f_src_center, cd_loop_mdisp_offset);
554         }
555 }
556
557 /**
558  * smooths boundaries between multires grids,
559  * including some borders in adjacent faces
560  */
561 void BM_face_multires_bounds_smooth(BMesh *bm, BMFace *f)
562 {
563         const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
564         BMLoop *l;
565         BMIter liter;
566
567         if (cd_loop_mdisp_offset == -1)
568                 return;
569
570         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
571                 MDisps *mdp = BM_ELEM_CD_GET_VOID_P(l->prev, cd_loop_mdisp_offset);
572                 MDisps *mdl = BM_ELEM_CD_GET_VOID_P(l, cd_loop_mdisp_offset);
573                 MDisps *mdn = BM_ELEM_CD_GET_VOID_P(l->next, cd_loop_mdisp_offset);
574                 float co1[3];
575                 int sides;
576                 int y;
577
578                 /**
579                  * mdisps is a grid of displacements, ordered thus:
580                  * <pre>
581                  *                    v4/next
582                  *                      |
583                  *  |      v1/cent-----mid2 ---> x
584                  *  |         |         |
585                  *  |         |         |
586                  * v2/prev---mid1-----v3/cur
587                  *            |
588                  *            V
589                  *            y
590                  * </pre>
591                  */
592
593                 sides = (int)sqrt(mdp->totdisp);
594                 for (y = 0; y < sides; y++) {
595                         mid_v3_v3v3(co1, mdn->disps[y * sides], mdl->disps[y]);
596
597                         copy_v3_v3(mdn->disps[y * sides], co1);
598                         copy_v3_v3(mdl->disps[y], co1);
599                 }
600         }
601
602         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
603                 MDisps *mdl1 = BM_ELEM_CD_GET_VOID_P(l, cd_loop_mdisp_offset);
604                 MDisps *mdl2;
605                 float co1[3], co2[3], co[3];
606                 int sides;
607                 int y;
608
609                 /**
610                  * mdisps is a grid of displacements, ordered thus:
611                  * <pre>
612                  *                    v4/next
613                  *                      |
614                  *  |      v1/cent-----mid2 ---> x
615                  *  |         |         |
616                  *  |         |         |
617                  * v2/prev---mid1-----v3/cur
618                  *            |
619                  *            V
620                  *            y
621                  * </pre>
622                  */
623
624                 if (l->radial_next == l)
625                         continue;
626
627                 if (l->radial_next->v == l->v)
628                         mdl2 = BM_ELEM_CD_GET_VOID_P(l->radial_next, cd_loop_mdisp_offset);
629                 else
630                         mdl2 = BM_ELEM_CD_GET_VOID_P(l->radial_next->next, cd_loop_mdisp_offset);
631
632                 sides = (int)sqrt(mdl1->totdisp);
633                 for (y = 0; y < sides; y++) {
634                         int a1, a2, o1, o2;
635
636                         if (l->v != l->radial_next->v) {
637                                 a1 = sides * y + sides - 2;
638                                 a2 = (sides - 2) * sides + y;
639
640                                 o1 = sides * y + sides - 1;
641                                 o2 = (sides - 1) * sides + y;
642                         }
643                         else {
644                                 a1 = sides * y + sides - 2;
645                                 a2 = sides * y + sides - 2;
646                                 o1 = sides * y + sides - 1;
647                                 o2 = sides * y + sides - 1;
648                         }
649
650                         /* magic blending numbers, hardcoded! */
651                         add_v3_v3v3(co1, mdl1->disps[a1], mdl2->disps[a2]);
652                         mul_v3_fl(co1, 0.18);
653
654                         add_v3_v3v3(co2, mdl1->disps[o1], mdl2->disps[o2]);
655                         mul_v3_fl(co2, 0.32);
656
657                         add_v3_v3v3(co, co1, co2);
658
659                         copy_v3_v3(mdl1->disps[o1], co);
660                         copy_v3_v3(mdl2->disps[o2], co);
661                 }
662         }
663 }
664
665 /**
666  * projects a single loop, target, onto f_src for customdata interpolation. multires is handled.
667  * if do_vertex is true, target's vert data will also get interpolated.
668  */
669 void BM_loop_interp_from_face(
670         BMesh *bm, BMLoop *l_dst, const BMFace *f_src,
671         const bool do_vertex, const bool do_multires)
672 {
673         BMLoop *l_iter;
674         BMLoop *l_first;
675         const void **vblocks  = do_vertex ? BLI_array_alloca(vblocks, f_src->len) : NULL;
676         const void **blocks   = BLI_array_alloca(blocks, f_src->len);
677         float (*cos_2d)[2] = BLI_array_alloca(cos_2d, f_src->len);
678         float *w        = BLI_array_alloca(w, f_src->len);
679         float axis_mat[3][3];  /* use normal to transform into 2d xy coords */
680         float co[2];
681         int i;
682
683         /* convert the 3d coords into 2d for projection */
684         BLI_assert(BM_face_is_normal_valid(f_src));
685         axis_dominant_v3_to_m3(axis_mat, f_src->no);
686
687         i = 0;
688         l_iter = l_first = BM_FACE_FIRST_LOOP(f_src);
689         do {
690                 mul_v2_m3v3(cos_2d[i], axis_mat, l_iter->v->co);
691                 blocks[i] = l_iter->head.data;
692
693                 if (do_vertex) {
694                         vblocks[i] = l_iter->v->head.data;
695                 }
696         } while ((void)i++, (l_iter = l_iter->next) != l_first);
697
698         mul_v2_m3v3(co, axis_mat, l_dst->v->co);
699
700         /* interpolate */
701         interp_weights_poly_v2(w, cos_2d, f_src->len, co);
702         CustomData_bmesh_interp(&bm->ldata, blocks, w, NULL, f_src->len, l_dst->head.data);
703         if (do_vertex) {
704                 CustomData_bmesh_interp(&bm->vdata, vblocks, w, NULL, f_src->len, l_dst->v->head.data);
705         }
706
707         if (do_multires) {
708                 BM_loop_interp_multires(bm, l_dst, f_src);
709         }
710 }
711
712
713 void BM_vert_interp_from_face(BMesh *bm, BMVert *v_dst, const BMFace *f_src)
714 {
715         BMLoop *l_iter;
716         BMLoop *l_first;
717         const void **blocks   = BLI_array_alloca(blocks, f_src->len);
718         float (*cos_2d)[2] = BLI_array_alloca(cos_2d, f_src->len);
719         float *w        = BLI_array_alloca(w,      f_src->len);
720         float axis_mat[3][3];  /* use normal to transform into 2d xy coords */
721         float co[2];
722         int i;
723
724         /* convert the 3d coords into 2d for projection */
725         BLI_assert(BM_face_is_normal_valid(f_src));
726         axis_dominant_v3_to_m3(axis_mat, f_src->no);
727
728         i = 0;
729         l_iter = l_first = BM_FACE_FIRST_LOOP(f_src);
730         do {
731                 mul_v2_m3v3(cos_2d[i], axis_mat, l_iter->v->co);
732                 blocks[i] = l_iter->v->head.data;
733         } while ((void)i++, (l_iter = l_iter->next) != l_first);
734
735         mul_v2_m3v3(co, axis_mat, v_dst->co);
736
737         /* interpolate */
738         interp_weights_poly_v2(w, cos_2d, f_src->len, co);
739         CustomData_bmesh_interp(&bm->vdata, blocks, w, NULL, f_src->len, v_dst->head.data);
740 }
741
742 static void update_data_blocks(BMesh *bm, CustomData *olddata, CustomData *data)
743 {
744         BMIter iter;
745         BLI_mempool *oldpool = olddata->pool;
746         void *block;
747
748         if (data == &bm->vdata) {
749                 BMVert *eve;
750
751                 CustomData_bmesh_init_pool(data, bm->totvert, BM_VERT);
752
753                 BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) {
754                         block = NULL;
755                         CustomData_bmesh_set_default(data, &block);
756                         CustomData_bmesh_copy_data(olddata, data, eve->head.data, &block);
757                         CustomData_bmesh_free_block(olddata, &eve->head.data);
758                         eve->head.data = block;
759                 }
760         }
761         else if (data == &bm->edata) {
762                 BMEdge *eed;
763
764                 CustomData_bmesh_init_pool(data, bm->totedge, BM_EDGE);
765
766                 BM_ITER_MESH (eed, &iter, bm, BM_EDGES_OF_MESH) {
767                         block = NULL;
768                         CustomData_bmesh_set_default(data, &block);
769                         CustomData_bmesh_copy_data(olddata, data, eed->head.data, &block);
770                         CustomData_bmesh_free_block(olddata, &eed->head.data);
771                         eed->head.data = block;
772                 }
773         }
774         else if (data == &bm->ldata) {
775                 BMIter liter;
776                 BMFace *efa;
777                 BMLoop *l;
778
779                 CustomData_bmesh_init_pool(data, bm->totloop, BM_LOOP);
780                 BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
781                         BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
782                                 block = NULL;
783                                 CustomData_bmesh_set_default(data, &block);
784                                 CustomData_bmesh_copy_data(olddata, data, l->head.data, &block);
785                                 CustomData_bmesh_free_block(olddata, &l->head.data);
786                                 l->head.data = block;
787                         }
788                 }
789         }
790         else if (data == &bm->pdata) {
791                 BMFace *efa;
792
793                 CustomData_bmesh_init_pool(data, bm->totface, BM_FACE);
794
795                 BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
796                         block = NULL;
797                         CustomData_bmesh_set_default(data, &block);
798                         CustomData_bmesh_copy_data(olddata, data, efa->head.data, &block);
799                         CustomData_bmesh_free_block(olddata, &efa->head.data);
800                         efa->head.data = block;
801                 }
802         }
803         else {
804                 /* should never reach this! */
805                 BLI_assert(0);
806         }
807
808         if (oldpool) {
809                 /* this should never happen but can when dissolve fails - [#28960] */
810                 BLI_assert(data->pool != oldpool);
811
812                 BLI_mempool_destroy(oldpool);
813         }
814 }
815
816 void BM_data_layer_add(BMesh *bm, CustomData *data, int type)
817 {
818         CustomData olddata;
819
820         olddata = *data;
821         olddata.layers = (olddata.layers) ? MEM_dupallocN(olddata.layers) : NULL;
822
823         /* the pool is now owned by olddata and must not be shared */
824         data->pool = NULL;
825
826         CustomData_add_layer(data, type, CD_DEFAULT, NULL, 0);
827
828         update_data_blocks(bm, &olddata, data);
829         if (olddata.layers) MEM_freeN(olddata.layers);
830 }
831
832 void BM_data_layer_add_named(BMesh *bm, CustomData *data, int type, const char *name)
833 {
834         CustomData olddata;
835
836         olddata = *data;
837         olddata.layers = (olddata.layers) ? MEM_dupallocN(olddata.layers) : NULL;
838
839         /* the pool is now owned by olddata and must not be shared */
840         data->pool = NULL;
841
842         CustomData_add_layer_named(data, type, CD_DEFAULT, NULL, 0, name);
843
844         update_data_blocks(bm, &olddata, data);
845         if (olddata.layers) MEM_freeN(olddata.layers);
846 }
847
848 void BM_data_layer_free(BMesh *bm, CustomData *data, int type)
849 {
850         CustomData olddata;
851         bool has_layer;
852
853         olddata = *data;
854         olddata.layers = (olddata.layers) ? MEM_dupallocN(olddata.layers) : NULL;
855
856         /* the pool is now owned by olddata and must not be shared */
857         data->pool = NULL;
858
859         has_layer = CustomData_free_layer_active(data, type, 0);
860         /* assert because its expensive to realloc - better not do if layer isnt present */
861         BLI_assert(has_layer != false);
862         UNUSED_VARS_NDEBUG(has_layer);
863
864         update_data_blocks(bm, &olddata, data);
865         if (olddata.layers) MEM_freeN(olddata.layers);
866 }
867
868 void BM_data_layer_free_n(BMesh *bm, CustomData *data, int type, int n)
869 {
870         CustomData olddata;
871         bool has_layer;
872
873         olddata = *data;
874         olddata.layers = (olddata.layers) ? MEM_dupallocN(olddata.layers) : NULL;
875
876         /* the pool is now owned by olddata and must not be shared */
877         data->pool = NULL;
878
879         has_layer = CustomData_free_layer(data, type, 0, CustomData_get_layer_index_n(data, type, n));
880         /* assert because its expensive to realloc - better not do if layer isnt present */
881         BLI_assert(has_layer != false);
882         UNUSED_VARS_NDEBUG(has_layer);
883
884         update_data_blocks(bm, &olddata, data);
885         if (olddata.layers) MEM_freeN(olddata.layers);
886 }
887
888 void BM_data_layer_copy(BMesh *bm, CustomData *data, int type, int src_n, int dst_n)
889 {
890         BMIter iter;
891
892         if (&bm->vdata == data) {
893                 BMVert *eve;
894
895                 BM_ITER_MESH (eve, &iter, bm, BM_VERTS_OF_MESH) {
896                         void *ptr = CustomData_bmesh_get_n(data, eve->head.data, type, src_n);
897                         CustomData_bmesh_set_n(data, eve->head.data, type, dst_n, ptr);
898                 }
899         }
900         else if (&bm->edata == data) {
901                 BMEdge *eed;
902
903                 BM_ITER_MESH (eed, &iter, bm, BM_EDGES_OF_MESH) {
904                         void *ptr = CustomData_bmesh_get_n(data, eed->head.data, type, src_n);
905                         CustomData_bmesh_set_n(data, eed->head.data, type, dst_n, ptr);
906                 }
907         }
908         else if (&bm->pdata == data) {
909                 BMFace *efa;
910
911                 BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
912                         void *ptr = CustomData_bmesh_get_n(data, efa->head.data, type, src_n);
913                         CustomData_bmesh_set_n(data, efa->head.data, type, dst_n, ptr);
914                 }
915         }
916         else if (&bm->ldata == data) {
917                 BMIter liter;
918                 BMFace *efa;
919                 BMLoop *l;
920
921                 BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
922                         BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
923                                 void *ptr = CustomData_bmesh_get_n(data, l->head.data, type, src_n);
924                                 CustomData_bmesh_set_n(data, l->head.data, type, dst_n, ptr);
925                         }
926                 }
927         }
928         else {
929                 /* should never reach this! */
930                 BLI_assert(0);
931         }
932 }
933
934 float BM_elem_float_data_get(CustomData *cd, void *element, int type)
935 {
936         const float *f = CustomData_bmesh_get(cd, ((BMHeader *)element)->data, type);
937         return f ? *f : 0.0f;
938 }
939
940 void BM_elem_float_data_set(CustomData *cd, void *element, int type, const float val)
941 {
942         float *f = CustomData_bmesh_get(cd, ((BMHeader *)element)->data, type);
943         if (f) *f = val;
944 }
945
946 /** \name Loop interpolation functions: BM_vert_loop_groups_data_layer_***
947  *
948  * Handling loop custom-data such as UV's, while keeping contiguous fans is rather tedious.
949  * Especially when a verts loops can have multiple CustomData layers,
950  * and each layer can have multiple (different) contiguous fans.
951  * Said differently, a single vertices loops may span multiple UV islands.
952  *
953  * These functions snapshot vertices loops, storing each contiguous fan in its own group.
954  * The caller can manipulate the loops, then re-combine the CustomData values.
955  *
956  * While these functions don't explicitly handle multiple layers at once,
957  * the caller can simply store its own list.
958  *
959  * \note Currently they are averaged back together (weighted by loop angle)
960  * but we could copy add other methods to re-combine CustomData-Loop-Fans.
961  *
962  * \{ */
963
964 struct LoopWalkCtx {
965         /* same for all groups */
966         int type;
967         int cd_layer_offset;
968         const float *loop_weights;
969         MemArena *arena;
970
971         /* --- Per loop fan vars --- */
972
973         /* reference for this contiguous fan */
974         const void *data_ref;
975         int data_len;
976
977         /* accumulate 'LoopGroupCD.weight' to make unit length */
978         float weight_accum;
979
980         /* both arrays the size of the 'BM_vert_face_count(v)'
981          * each contiguous fan gets a slide of these arrays */
982         void **data_array;
983         int *data_index_array;
984         float *weight_array;
985 };
986
987 /* Store vars to pass into 'CustomData_bmesh_interp' */
988 struct LoopGroupCD {
989         /* direct customdata pointer array */
990         void **data;
991         /* weights (aligned with 'data') */
992         float *data_weights;
993         /* index-in-face */
994         int *data_index;
995         /* number of loops in the fan */
996         int data_len;
997 };
998
999 static void bm_loop_walk_add(struct LoopWalkCtx *lwc, BMLoop *l)
1000 {
1001         const int i = BM_elem_index_get(l);
1002         const float w = lwc->loop_weights[i];
1003         BM_elem_flag_disable(l, BM_ELEM_INTERNAL_TAG);
1004         lwc->data_array[lwc->data_len] = BM_ELEM_CD_GET_VOID_P(l, lwc->cd_layer_offset);
1005         lwc->data_index_array[lwc->data_len] = i;
1006         lwc->weight_array[lwc->data_len] = w;
1007         lwc->weight_accum += w;
1008
1009         lwc->data_len += 1;
1010 }
1011
1012 /**
1013  * called recursively, keep stack-usage minimal.
1014  *
1015  * \note called for fan matching so we're pretty much safe not to break the stack
1016  */
1017 static void bm_loop_walk_data(struct LoopWalkCtx *lwc, BMLoop *l_walk)
1018 {
1019         int i;
1020
1021         BLI_assert(CustomData_data_equals(lwc->type, lwc->data_ref, BM_ELEM_CD_GET_VOID_P(l_walk, lwc->cd_layer_offset)));
1022         BLI_assert(BM_elem_flag_test(l_walk, BM_ELEM_INTERNAL_TAG));
1023
1024         bm_loop_walk_add(lwc, l_walk);
1025
1026         /* recurse around this loop-fan (in both directions) */
1027         for (i = 0; i < 2; i++) {
1028                 BMLoop *l_other = ((i == 0) ? l_walk : l_walk->prev)->radial_next;
1029                 if (l_other->radial_next != l_other) {
1030                         if (l_other->v != l_walk->v) {
1031                                 l_other = l_other->next;
1032                         }
1033                         BLI_assert(l_other->v == l_walk->v);
1034                         if (BM_elem_flag_test(l_other, BM_ELEM_INTERNAL_TAG)) {
1035                                 if (CustomData_data_equals(lwc->type, lwc->data_ref, BM_ELEM_CD_GET_VOID_P(l_other, lwc->cd_layer_offset))) {
1036                                         bm_loop_walk_data(lwc, l_other);
1037                                 }
1038                         }
1039                 }
1040         }
1041 }
1042
1043 LinkNode *BM_vert_loop_groups_data_layer_create(
1044         BMesh *bm, BMVert *v, const int layer_n, const float *loop_weights, MemArena *arena)
1045 {
1046         struct LoopWalkCtx lwc;
1047         LinkNode *groups = NULL;
1048         BMLoop *l;
1049         BMIter liter;
1050         int loop_num;
1051
1052
1053         lwc.type = bm->ldata.layers[layer_n].type;
1054         lwc.cd_layer_offset = bm->ldata.layers[layer_n].offset;
1055         lwc.loop_weights = loop_weights;
1056         lwc.arena = arena;
1057
1058         /* Enable 'BM_ELEM_INTERNAL_TAG', leaving the flag clean on completion. */
1059         loop_num = 0;
1060         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
1061                 BM_elem_flag_enable(l, BM_ELEM_INTERNAL_TAG);
1062                 BM_elem_index_set(l, loop_num);  /* set_dirty! */
1063                 loop_num++;
1064         }
1065         bm->elem_index_dirty |= BM_LOOP;
1066
1067         lwc.data_len = 0;
1068         lwc.data_array = BLI_memarena_alloc(lwc.arena, sizeof(void *) * loop_num);
1069         lwc.data_index_array = BLI_memarena_alloc(lwc.arena, sizeof(int) * loop_num);
1070         lwc.weight_array = BLI_memarena_alloc(lwc.arena, sizeof(float) * loop_num);
1071
1072         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
1073                 if (BM_elem_flag_test(l, BM_ELEM_INTERNAL_TAG)) {
1074                         struct LoopGroupCD *lf = BLI_memarena_alloc(lwc.arena, sizeof(*lf));
1075                         int len_prev = lwc.data_len;
1076
1077                         lwc.data_ref = BM_ELEM_CD_GET_VOID_P(l, lwc.cd_layer_offset);
1078
1079                         /* assign len-last */
1080                         lf->data         = &lwc.data_array[lwc.data_len];
1081                         lf->data_index   = &lwc.data_index_array[lwc.data_len];
1082                         lf->data_weights = &lwc.weight_array[lwc.data_len];
1083                         lwc.weight_accum = 0.0f;
1084
1085                         /* new group */
1086                         bm_loop_walk_data(&lwc, l);
1087                         lf->data_len = lwc.data_len - len_prev;
1088
1089                         if (LIKELY(lwc.weight_accum != 0.0f)) {
1090                                 mul_vn_fl(lf->data_weights, lf->data_len, 1.0f / lwc.weight_accum);
1091                         }
1092                         else {
1093                                 copy_vn_fl(lf->data_weights, lf->data_len, 1.0f / (float)lf->data_len);
1094                         }
1095
1096                         BLI_linklist_prepend_arena(&groups, lf, lwc.arena);
1097                 }
1098         }
1099
1100         BLI_assert(lwc.data_len == loop_num);
1101
1102         return groups;
1103 }
1104
1105 static void bm_vert_loop_groups_data_layer_merge__single(
1106         BMesh *bm, void *lf_p, int layer_n,
1107         void *data_tmp)
1108 {
1109         struct LoopGroupCD *lf = lf_p;
1110         const int type = bm->ldata.layers[layer_n].type;
1111         int i;
1112         const float *data_weights;
1113
1114         data_weights = lf->data_weights;
1115
1116         CustomData_bmesh_interp_n(
1117                 &bm->ldata, (const void **)lf->data,
1118                 data_weights, NULL, lf->data_len, data_tmp, layer_n);
1119
1120         for (i = 0; i < lf->data_len; i++) {
1121                 CustomData_copy_elements(type, data_tmp, lf->data[i], 1);
1122         }
1123 }
1124
1125 static void bm_vert_loop_groups_data_layer_merge_weights__single(
1126         BMesh *bm, void *lf_p, const int layer_n, void *data_tmp,
1127         const float *loop_weights)
1128 {
1129         struct LoopGroupCD *lf = lf_p;
1130         const int type = bm->ldata.layers[layer_n].type;
1131         int i;
1132         const float *data_weights;
1133
1134         /* re-weight */
1135         float *temp_weights = BLI_array_alloca(temp_weights, lf->data_len);
1136         float weight_accum = 0.0f;
1137
1138         for (i = 0; i < lf->data_len; i++) {
1139                 float w = loop_weights[lf->data_index[i]] * lf->data_weights[i];
1140                 temp_weights[i] = w;
1141                 weight_accum += w;
1142         }
1143
1144         if (LIKELY(weight_accum != 0.0f)) {
1145                 mul_vn_fl(temp_weights, lf->data_len, 1.0f / weight_accum);
1146                 data_weights = temp_weights;
1147         }
1148         else {
1149                 data_weights = lf->data_weights;
1150         }
1151
1152         CustomData_bmesh_interp_n(
1153                 &bm->ldata, (const void **)lf->data,
1154                 data_weights, NULL, lf->data_len, data_tmp, layer_n);
1155
1156         for (i = 0; i < lf->data_len; i++) {
1157                 CustomData_copy_elements(type, data_tmp, lf->data[i], 1);
1158         }
1159 }
1160
1161 /**
1162  * Take existing custom data and merge each fan's data.
1163  */
1164 void BM_vert_loop_groups_data_layer_merge(BMesh *bm, LinkNode *groups, const int layer_n)
1165 {
1166         const int type = bm->ldata.layers[layer_n].type;
1167         const int size = CustomData_sizeof(type);
1168         void *data_tmp = alloca(size);
1169
1170         do {
1171                 bm_vert_loop_groups_data_layer_merge__single(bm, groups->link, layer_n, data_tmp);
1172         } while ((groups = groups->next));
1173 }
1174
1175 /**
1176  * A version of #BM_vert_loop_groups_data_layer_merge
1177  * that takes an array of loop-weights (aligned with #BM_LOOPS_OF_VERT iterator)
1178  */
1179 void BM_vert_loop_groups_data_layer_merge_weights(
1180         BMesh *bm, LinkNode *groups, const int layer_n, const float *loop_weights)
1181 {
1182         const int type = bm->ldata.layers[layer_n].type;
1183         const int size = CustomData_sizeof(type);
1184         void *data_tmp = alloca(size);
1185
1186         do {
1187                 bm_vert_loop_groups_data_layer_merge_weights__single(bm, groups->link, layer_n, data_tmp, loop_weights);
1188         } while ((groups = groups->next));
1189 }
1190
1191 /** \} */