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