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