ClangFormat: apply to source, most of intern
[blender.git] / source / blender / blenkernel / intern / editderivedmesh.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) 2005 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  *
23  * basic design:
24  *
25  * the bmesh derivedmesh exposes the mesh as triangles.  it stores pointers
26  * to three loops per triangle.  the derivedmesh stores a cache of tessellations
27  * for each face.  this cache will smartly update as needed (though at first
28  * it'll simply be more brute force).  keeping track of face/edge counts may
29  * be a small problem.
30  *
31  * this won't be the most efficient thing, considering that internal edges and
32  * faces of tessellations are exposed.  looking up an edge by index in particular
33  * is likely to be a little slow.
34  */
35
36 #include "atomic_ops.h"
37
38 #include "BLI_math.h"
39 #include "BLI_jitter_2d.h"
40 #include "BLI_bitmap.h"
41 #include "BLI_task.h"
42
43 #include "BKE_cdderivedmesh.h"
44 #include "BKE_deform.h"
45 #include "BKE_mesh.h"
46 #include "BKE_mesh_iterators.h"
47 #include "BKE_editmesh.h"
48 #include "BKE_editmesh_bvh.h"
49 #include "BKE_editmesh_cache.h"
50 #include "BKE_editmesh_tangent.h"
51
52 #include "DNA_scene_types.h"
53 #include "DNA_object_types.h"
54 #include "DNA_mesh_types.h"
55
56 #include "MEM_guardedalloc.h"
57
58 /* -------------------------------------------------------------------- */
59 /* StatVis Functions */
60
61 static void axis_from_enum_v3(float v[3], const char axis)
62 {
63   zero_v3(v);
64   if (axis < 3)
65     v[axis] = 1.0f;
66   else
67     v[axis - 3] = -1.0f;
68 }
69
70 static void statvis_calc_overhang(BMEditMesh *em,
71                                   const float (*polyNos)[3],
72                                   /* values for calculating */
73                                   const float min,
74                                   const float max,
75                                   const char axis,
76                                   /* result */
77                                   unsigned char (*r_face_colors)[4])
78 {
79   BMIter iter;
80   BMesh *bm = em->bm;
81   BMFace *f;
82   float dir[3];
83   int index;
84   const float minmax_irange = 1.0f / (max - min);
85   bool is_max;
86
87   /* fallback */
88   unsigned char col_fallback[4] = {64, 64, 64, 255};  /* gray */
89   unsigned char col_fallback_max[4] = {0, 0, 0, 255}; /* max color */
90
91   BLI_assert(min <= max);
92
93   axis_from_enum_v3(dir, axis);
94
95   if (LIKELY(em->ob)) {
96     mul_transposed_mat3_m4_v3(em->ob->obmat, dir);
97     normalize_v3(dir);
98   }
99
100   /* fallback max */
101   {
102     float fcol[3];
103     BKE_defvert_weight_to_rgb(fcol, 1.0f);
104     rgb_float_to_uchar(col_fallback_max, fcol);
105   }
106
107   /* now convert into global space */
108   BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, index) {
109     float fac = angle_normalized_v3v3(polyNos ? polyNos[index] : f->no, dir) / (float)M_PI;
110
111     /* remap */
112     if ((is_max = (fac <= max)) && (fac >= min)) {
113       float fcol[3];
114       fac = (fac - min) * minmax_irange;
115       fac = 1.0f - fac;
116       CLAMP(fac, 0.0f, 1.0f);
117       BKE_defvert_weight_to_rgb(fcol, fac);
118       rgb_float_to_uchar(r_face_colors[index], fcol);
119     }
120     else {
121       const unsigned char *fallback = is_max ? col_fallback_max : col_fallback;
122       copy_v4_v4_uchar(r_face_colors[index], fallback);
123     }
124   }
125 }
126
127 /* so we can use jitter values for face interpolation */
128 static void uv_from_jitter_v2(float uv[2])
129 {
130   uv[0] += 0.5f;
131   uv[1] += 0.5f;
132   if (uv[0] + uv[1] > 1.0f) {
133     uv[0] = 1.0f - uv[0];
134     uv[1] = 1.0f - uv[1];
135   }
136
137   CLAMP(uv[0], 0.0f, 1.0f);
138   CLAMP(uv[1], 0.0f, 1.0f);
139 }
140
141 static void statvis_calc_thickness(BMEditMesh *em,
142                                    const float (*vertexCos)[3],
143                                    /* values for calculating */
144                                    const float min,
145                                    const float max,
146                                    const int samples,
147                                    /* result */
148                                    unsigned char (*r_face_colors)[4])
149 {
150   const float eps_offset = 0.00002f;          /* values <= 0.00001 give errors */
151   float *face_dists = (float *)r_face_colors; /* cheating */
152   const bool use_jit = samples < 32;
153   float jit_ofs[32][2];
154   BMesh *bm = em->bm;
155   const int tottri = em->tottri;
156   const float minmax_irange = 1.0f / (max - min);
157   int i;
158
159   struct BMLoop *(*looptris)[3] = em->looptris;
160
161   /* fallback */
162   const unsigned char col_fallback[4] = {64, 64, 64, 255};
163
164   struct BMBVHTree *bmtree;
165
166   BLI_assert(min <= max);
167
168   copy_vn_fl(face_dists, em->bm->totface, max);
169
170   if (use_jit) {
171     int j;
172     BLI_assert(samples < 32);
173     BLI_jitter_init(jit_ofs, samples);
174
175     for (j = 0; j < samples; j++) {
176       uv_from_jitter_v2(jit_ofs[j]);
177     }
178   }
179
180   BM_mesh_elem_index_ensure(bm, BM_FACE);
181   if (vertexCos) {
182     BM_mesh_elem_index_ensure(bm, BM_VERT);
183   }
184
185   bmtree = BKE_bmbvh_new_from_editmesh(em, 0, vertexCos, false);
186
187   for (i = 0; i < tottri; i++) {
188     BMFace *f_hit;
189     BMLoop **ltri = looptris[i];
190     const int index = BM_elem_index_get(ltri[0]->f);
191     const float *cos[3];
192     float ray_co[3];
193     float ray_no[3];
194
195     if (vertexCos) {
196       cos[0] = vertexCos[BM_elem_index_get(ltri[0]->v)];
197       cos[1] = vertexCos[BM_elem_index_get(ltri[1]->v)];
198       cos[2] = vertexCos[BM_elem_index_get(ltri[2]->v)];
199     }
200     else {
201       cos[0] = ltri[0]->v->co;
202       cos[1] = ltri[1]->v->co;
203       cos[2] = ltri[2]->v->co;
204     }
205
206     normal_tri_v3(ray_no, cos[2], cos[1], cos[0]);
207
208 #define FACE_RAY_TEST_ANGLE \
209   f_hit = BKE_bmbvh_ray_cast(bmtree, ray_co, ray_no, 0.0f, &dist, NULL, NULL); \
210   if (f_hit && dist < face_dists[index]) { \
211     float angle_fac = fabsf(dot_v3v3(ltri[0]->f->no, f_hit->no)); \
212     angle_fac = 1.0f - angle_fac; \
213     angle_fac = angle_fac * angle_fac * angle_fac; \
214     angle_fac = 1.0f - angle_fac; \
215     dist /= angle_fac; \
216     if (dist < face_dists[index]) { \
217       face_dists[index] = dist; \
218     } \
219   } \
220   (void)0
221
222     if (use_jit) {
223       int j;
224       for (j = 0; j < samples; j++) {
225         float dist = face_dists[index];
226         interp_v3_v3v3v3_uv(ray_co, cos[0], cos[1], cos[2], jit_ofs[j]);
227         madd_v3_v3fl(ray_co, ray_no, eps_offset);
228
229         FACE_RAY_TEST_ANGLE;
230       }
231     }
232     else {
233       float dist = face_dists[index];
234       mid_v3_v3v3v3(ray_co, cos[0], cos[1], cos[2]);
235       madd_v3_v3fl(ray_co, ray_no, eps_offset);
236
237       FACE_RAY_TEST_ANGLE;
238     }
239   }
240
241   BKE_bmbvh_free(bmtree);
242
243   /* convert floats into color! */
244   for (i = 0; i < bm->totface; i++) {
245     float fac = face_dists[i];
246
247     /* important not '<=' */
248     if (fac < max) {
249       float fcol[3];
250       fac = (fac - min) * minmax_irange;
251       fac = 1.0f - fac;
252       CLAMP(fac, 0.0f, 1.0f);
253       BKE_defvert_weight_to_rgb(fcol, fac);
254       rgb_float_to_uchar(r_face_colors[i], fcol);
255     }
256     else {
257       copy_v4_v4_uchar(r_face_colors[i], col_fallback);
258     }
259   }
260 }
261
262 static void statvis_calc_intersect(BMEditMesh *em,
263                                    const float (*vertexCos)[3],
264                                    /* result */
265                                    unsigned char (*r_face_colors)[4])
266 {
267   BMesh *bm = em->bm;
268   int i;
269
270   /* fallback */
271   // const char col_fallback[4] = {64, 64, 64, 255};
272   float fcol[3];
273   unsigned char col[3];
274
275   struct BMBVHTree *bmtree;
276   BVHTreeOverlap *overlap;
277   unsigned int overlap_len;
278
279   memset(r_face_colors, 64, sizeof(int) * em->bm->totface);
280
281   BM_mesh_elem_index_ensure(bm, BM_FACE);
282   if (vertexCos) {
283     BM_mesh_elem_index_ensure(bm, BM_VERT);
284   }
285
286   bmtree = BKE_bmbvh_new_from_editmesh(em, 0, vertexCos, false);
287
288   overlap = BKE_bmbvh_overlap(bmtree, bmtree, &overlap_len);
289
290   /* same for all faces */
291   BKE_defvert_weight_to_rgb(fcol, 1.0f);
292   rgb_float_to_uchar(col, fcol);
293
294   if (overlap) {
295     for (i = 0; i < overlap_len; i++) {
296       BMFace *f_hit_pair[2] = {
297           em->looptris[overlap[i].indexA][0]->f,
298           em->looptris[overlap[i].indexB][0]->f,
299       };
300       int j;
301
302       for (j = 0; j < 2; j++) {
303         BMFace *f_hit = f_hit_pair[j];
304         int index;
305
306         index = BM_elem_index_get(f_hit);
307
308         copy_v3_v3_uchar(r_face_colors[index], col);
309       }
310     }
311     MEM_freeN(overlap);
312   }
313
314   BKE_bmbvh_free(bmtree);
315 }
316
317 static void statvis_calc_distort(BMEditMesh *em,
318                                  const float (*vertexCos)[3],
319                                  const float (*polyNos)[3],
320                                  /* values for calculating */
321                                  const float min,
322                                  const float max,
323                                  /* result */
324                                  unsigned char (*r_face_colors)[4])
325 {
326   BMIter iter;
327   BMesh *bm = em->bm;
328   BMFace *f;
329   const float *f_no;
330   int index;
331   const float minmax_irange = 1.0f / (max - min);
332
333   /* fallback */
334   const unsigned char col_fallback[4] = {64, 64, 64, 255};
335
336   /* now convert into global space */
337   BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, index) {
338     float fac;
339
340     if (f->len == 3) {
341       fac = -1.0f;
342     }
343     else {
344       BMLoop *l_iter, *l_first;
345       if (vertexCos) {
346         f_no = polyNos[index];
347       }
348       else {
349         f_no = f->no;
350       }
351
352       fac = 0.0f;
353       l_iter = l_first = BM_FACE_FIRST_LOOP(f);
354       do {
355         float no_corner[3];
356         if (vertexCos) {
357           normal_tri_v3(no_corner,
358                         vertexCos[BM_elem_index_get(l_iter->prev->v)],
359                         vertexCos[BM_elem_index_get(l_iter->v)],
360                         vertexCos[BM_elem_index_get(l_iter->next->v)]);
361         }
362         else {
363           BM_loop_calc_face_normal_safe(l_iter, no_corner);
364         }
365         /* simple way to detect (what is most likely) concave */
366         if (dot_v3v3(f_no, no_corner) < 0.0f) {
367           negate_v3(no_corner);
368         }
369         fac = max_ff(fac, angle_normalized_v3v3(f_no, no_corner));
370       } while ((l_iter = l_iter->next) != l_first);
371       fac *= 2.0f;
372     }
373
374     /* remap */
375     if (fac >= min) {
376       float fcol[3];
377       fac = (fac - min) * minmax_irange;
378       CLAMP(fac, 0.0f, 1.0f);
379       BKE_defvert_weight_to_rgb(fcol, fac);
380       rgb_float_to_uchar(r_face_colors[index], fcol);
381     }
382     else {
383       copy_v4_v4_uchar(r_face_colors[index], col_fallback);
384     }
385   }
386 }
387
388 static void statvis_calc_sharp(BMEditMesh *em,
389                                const float (*vertexCos)[3],
390                                /* values for calculating */
391                                const float min,
392                                const float max,
393                                /* result */
394                                unsigned char (*r_vert_colors)[4])
395 {
396   float *vert_angles = (float *)r_vert_colors; /* cheating */
397   BMIter iter;
398   BMesh *bm = em->bm;
399   BMEdge *e;
400   //float f_no[3];
401   const float minmax_irange = 1.0f / (max - min);
402   int i;
403
404   /* fallback */
405   const unsigned char col_fallback[4] = {64, 64, 64, 255};
406
407   (void)vertexCos; /* TODO */
408
409   copy_vn_fl(vert_angles, em->bm->totvert, -M_PI);
410
411   /* first assign float values to verts */
412   BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
413     float angle = BM_edge_calc_face_angle_signed(e);
414     float *col1 = &vert_angles[BM_elem_index_get(e->v1)];
415     float *col2 = &vert_angles[BM_elem_index_get(e->v2)];
416     *col1 = max_ff(*col1, angle);
417     *col2 = max_ff(*col2, angle);
418   }
419
420   /* convert floats into color! */
421   for (i = 0; i < bm->totvert; i++) {
422     float fac = vert_angles[i];
423
424     /* important not '<=' */
425     if (fac > min) {
426       float fcol[3];
427       fac = (fac - min) * minmax_irange;
428       CLAMP(fac, 0.0f, 1.0f);
429       BKE_defvert_weight_to_rgb(fcol, fac);
430       rgb_float_to_uchar(r_vert_colors[i], fcol);
431     }
432     else {
433       copy_v4_v4_uchar(r_vert_colors[i], col_fallback);
434     }
435   }
436 }
437
438 void BKE_editmesh_statvis_calc(BMEditMesh *em, EditMeshData *emd, const MeshStatVis *statvis)
439 {
440   switch (statvis->type) {
441     case SCE_STATVIS_OVERHANG: {
442       BKE_editmesh_color_ensure(em, BM_FACE);
443       statvis_calc_overhang(em,
444                             emd ? emd->polyNos : NULL,
445                             statvis->overhang_min / (float)M_PI,
446                             statvis->overhang_max / (float)M_PI,
447                             statvis->overhang_axis,
448                             em->derivedFaceColor);
449       break;
450     }
451     case SCE_STATVIS_THICKNESS: {
452       const float scale = 1.0f / mat4_to_scale(em->ob->obmat);
453       BKE_editmesh_color_ensure(em, BM_FACE);
454       statvis_calc_thickness(em,
455                              emd ? emd->vertexCos : NULL,
456                              statvis->thickness_min * scale,
457                              statvis->thickness_max * scale,
458                              statvis->thickness_samples,
459                              em->derivedFaceColor);
460       break;
461     }
462     case SCE_STATVIS_INTERSECT: {
463       BKE_editmesh_color_ensure(em, BM_FACE);
464       statvis_calc_intersect(em, emd ? emd->vertexCos : NULL, em->derivedFaceColor);
465       break;
466     }
467     case SCE_STATVIS_DISTORT: {
468       BKE_editmesh_color_ensure(em, BM_FACE);
469
470       if (emd) {
471         BKE_editmesh_cache_ensure_poly_normals(em, emd);
472       }
473
474       statvis_calc_distort(em,
475                            emd ? emd->vertexCos : NULL,
476                            emd ? emd->polyNos : NULL,
477                            statvis->distort_min,
478                            statvis->distort_max,
479                            em->derivedFaceColor);
480       break;
481     }
482     case SCE_STATVIS_SHARP: {
483       BKE_editmesh_color_ensure(em, BM_VERT);
484       statvis_calc_sharp(em,
485                          emd ? emd->vertexCos : NULL,
486                          statvis->sharp_min,
487                          statvis->sharp_max,
488                          /* in this case they are vertex colors */
489                          em->derivedVertColor);
490       break;
491     }
492   }
493 }
494
495 /* -------------------------------------------------------------------- */
496 /* Editmesh Vert Coords */
497
498 struct CageUserData {
499   int totvert;
500   float (*cos_cage)[3];
501   BLI_bitmap *visit_bitmap;
502 };
503
504 static void cage_mapped_verts_callback(void *userData,
505                                        int index,
506                                        const float co[3],
507                                        const float UNUSED(no_f[3]),
508                                        const short UNUSED(no_s[3]))
509 {
510   struct CageUserData *data = userData;
511
512   if ((index >= 0 && index < data->totvert) && (!BLI_BITMAP_TEST(data->visit_bitmap, index))) {
513     BLI_BITMAP_ENABLE(data->visit_bitmap, index);
514     copy_v3_v3(data->cos_cage[index], co);
515   }
516 }
517
518 float (*BKE_editmesh_vertexCos_get(
519     struct Depsgraph *depsgraph, BMEditMesh *em, Scene *scene, int *r_numVerts))[3]
520 {
521   Mesh *cage;
522   BLI_bitmap *visit_bitmap;
523   struct CageUserData data;
524   float(*cos_cage)[3];
525
526   cage = editbmesh_get_eval_cage(depsgraph, scene, em->ob, em, &CD_MASK_BAREMESH);
527   cos_cage = MEM_callocN(sizeof(*cos_cage) * em->bm->totvert, "bmbvh cos_cage");
528
529   /* when initializing cage verts, we only want the first cage coordinate for each vertex,
530    * so that e.g. mirror or array use original vertex coordinates and not mirrored or duplicate */
531   visit_bitmap = BLI_BITMAP_NEW(em->bm->totvert, __func__);
532
533   data.totvert = em->bm->totvert;
534   data.cos_cage = cos_cage;
535   data.visit_bitmap = visit_bitmap;
536
537   BKE_mesh_foreach_mapped_vert(cage, cage_mapped_verts_callback, &data, MESH_FOREACH_NOP);
538
539   MEM_freeN(visit_bitmap);
540
541   if (r_numVerts) {
542     *r_numVerts = em->bm->totvert;
543   }
544
545   return cos_cage;
546 }