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