Split Normals I (1/5): basis for split normals (nearly nothing user-visible here):
[blender-staging.git] / source / blender / blenkernel / intern / mesh_evaluate.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) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/mesh_evaluate.c
27  *  \ingroup bke
28  *
29  * Functions to evaluate mesh data.
30  */
31
32 #include <limits.h>
33
34 #include "MEM_guardedalloc.h"
35
36 #include "DNA_object_types.h"
37 #include "DNA_mesh_types.h"
38 #include "DNA_meshdata_types.h"
39
40 #include "BLI_utildefines.h"
41 #include "BLI_memarena.h"
42 #include "BLI_math.h"
43 #include "BLI_edgehash.h"
44 #include "BLI_bitmap.h"
45 #include "BLI_polyfill2d.h"
46 #include "BLI_linklist.h"
47 #include "BLI_linklist_stack.h"
48 #include "BLI_alloca.h"
49
50 #include "BKE_customdata.h"
51 #include "BKE_mesh.h"
52 #include "BKE_multires.h"
53 #include "BKE_report.h"
54
55 #include "BLI_strict_flags.h"
56
57 #include "mikktspace.h"
58
59 // #define DEBUG_TIME
60
61 #ifdef DEBUG_TIME
62 #  include "PIL_time.h"
63 #  include "PIL_time_utildefines.h"
64 #endif
65
66 /* -------------------------------------------------------------------- */
67
68 /** \name Mesh Normal Calculation
69  * \{ */
70
71 /**
72  * Call when there are no polygons.
73  */
74 static void mesh_calc_normals_vert_fallback(MVert *mverts, int numVerts)
75 {
76         int i;
77         for (i = 0; i < numVerts; i++) {
78                 MVert *mv = &mverts[i];
79                 float no[3];
80
81                 normalize_v3_v3(no, mv->co);
82                 normal_float_to_short_v3(mv->no, no);
83         }
84 }
85
86 /* Calculate vertex and face normals, face normals are returned in *r_faceNors if non-NULL
87  * and vertex normals are stored in actual mverts.
88  */
89 void BKE_mesh_calc_normals_mapping(MVert *mverts, int numVerts,
90                                    MLoop *mloop, MPoly *mpolys, int numLoops, int numPolys, float (*r_polyNors)[3],
91                                    MFace *mfaces, int numFaces, const int *origIndexFace, float (*r_faceNors)[3])
92 {
93         BKE_mesh_calc_normals_mapping_ex(mverts, numVerts, mloop, mpolys,
94                                          numLoops, numPolys, r_polyNors, mfaces, numFaces,
95                                          origIndexFace, r_faceNors, false);
96 }
97 /* extended version of 'BKE_mesh_calc_normals_poly' with option not to calc vertex normals */
98 void BKE_mesh_calc_normals_mapping_ex(
99         MVert *mverts, int numVerts,
100         MLoop *mloop, MPoly *mpolys,
101         int numLoops, int numPolys, float (*r_polyNors)[3],
102         MFace *mfaces, int numFaces, const int *origIndexFace, float (*r_faceNors)[3],
103         const bool only_face_normals)
104 {
105         float (*pnors)[3] = r_polyNors, (*fnors)[3] = r_faceNors;
106         int i;
107         MFace *mf;
108         MPoly *mp;
109
110         if (numPolys == 0) {
111                 if (only_face_normals == false) {
112                         mesh_calc_normals_vert_fallback(mverts, numVerts);
113                 }
114                 return;
115         }
116
117         /* if we are not calculating verts and no verts were passes then we have nothing to do */
118         if ((only_face_normals == true) && (r_polyNors == NULL) && (r_faceNors == NULL)) {
119                 printf("%s: called with nothing to do\n", __func__);
120                 return;
121         }
122
123         if (!pnors) pnors = MEM_callocN(sizeof(float[3]) * (size_t)numPolys, __func__);
124         /* if (!fnors) fnors = MEM_callocN(sizeof(float[3]) * numFaces, "face nors mesh.c"); */ /* NO NEED TO ALLOC YET */
125
126
127         if (only_face_normals == false) {
128                 /* vertex normals are optional, they require some extra calculations,
129                  * so make them optional */
130                 BKE_mesh_calc_normals_poly(mverts, numVerts, mloop, mpolys, numLoops, numPolys, pnors, false);
131         }
132         else {
133                 /* only calc poly normals */
134                 mp = mpolys;
135                 for (i = 0; i < numPolys; i++, mp++) {
136                         BKE_mesh_calc_poly_normal(mp, mloop + mp->loopstart, mverts, pnors[i]);
137                 }
138         }
139
140         if (origIndexFace &&
141             /* fnors == r_faceNors */ /* NO NEED TO ALLOC YET */
142             fnors != NULL &&
143             numFaces)
144         {
145                 mf = mfaces;
146                 for (i = 0; i < numFaces; i++, mf++, origIndexFace++) {
147                         if (*origIndexFace < numPolys) {
148                                 copy_v3_v3(fnors[i], pnors[*origIndexFace]);
149                         }
150                         else {
151                                 /* eek, we're not corresponding to polys */
152                                 printf("error in %s: tessellation face indices are incorrect.  normals may look bad.\n", __func__);
153                         }
154                 }
155         }
156
157         if (pnors != r_polyNors) MEM_freeN(pnors);
158         /* if (fnors != r_faceNors) MEM_freeN(fnors); */ /* NO NEED TO ALLOC YET */
159
160         fnors = pnors = NULL;
161         
162 }
163
164 static void mesh_calc_normals_poly_accum(MPoly *mp, MLoop *ml,
165                                          MVert *mvert, float polyno[3], float (*tnorms)[3])
166 {
167         const int nverts = mp->totloop;
168         float (*edgevecbuf)[3] = BLI_array_alloca(edgevecbuf, (size_t)nverts);
169         int i;
170
171         /* Polygon Normal and edge-vector */
172         /* inline version of #BKE_mesh_calc_poly_normal, also does edge-vectors */
173         {
174                 int i_prev = nverts - 1;
175                 float const *v_prev = mvert[ml[i_prev].v].co;
176                 float const *v_curr;
177
178                 zero_v3(polyno);
179                 /* Newell's Method */
180                 for (i = 0; i < nverts; i++) {
181                         v_curr = mvert[ml[i].v].co;
182                         add_newell_cross_v3_v3v3(polyno, v_prev, v_curr);
183
184                         /* Unrelated to normalize, calculate edge-vector */
185                         sub_v3_v3v3(edgevecbuf[i_prev], v_prev, v_curr);
186                         normalize_v3(edgevecbuf[i_prev]);
187                         i_prev = i;
188
189                         v_prev = v_curr;
190                 }
191                 if (UNLIKELY(normalize_v3(polyno) == 0.0f)) {
192                         polyno[2] = 1.0f; /* other axis set to 0.0 */
193                 }
194         }
195
196         /* accumulate angle weighted face normal */
197         /* inline version of #accumulate_vertex_normals_poly */
198         {
199                 const float *prev_edge = edgevecbuf[nverts - 1];
200
201                 for (i = 0; i < nverts; i++) {
202                         const float *cur_edge = edgevecbuf[i];
203
204                         /* calculate angle between the two poly edges incident on
205                          * this vertex */
206                         const float fac = saacos(-dot_v3v3(cur_edge, prev_edge));
207
208                         /* accumulate */
209                         madd_v3_v3fl(tnorms[ml[i].v], polyno, fac);
210                         prev_edge = cur_edge;
211                 }
212         }
213
214 }
215
216 void BKE_mesh_calc_normals_poly(MVert *mverts, int numVerts, MLoop *mloop, MPoly *mpolys,
217                                 int UNUSED(numLoops), int numPolys, float (*r_polynors)[3],
218                                 const bool only_face_normals)
219 {
220         float (*pnors)[3] = r_polynors;
221         float (*tnorms)[3];
222         int i;
223         MPoly *mp;
224
225         if (only_face_normals) {
226                 BLI_assert(pnors != NULL);
227
228 #pragma omp parallel for if (numPolys > BKE_MESH_OMP_LIMIT)
229                 for (i = 0; i < numPolys; i++) {
230                         BKE_mesh_calc_poly_normal(&mpolys[i], mloop + mpolys[i].loopstart, mverts, pnors[i]);
231                 }
232                 return;
233         }
234
235         /* first go through and calculate normals for all the polys */
236         tnorms = MEM_callocN(sizeof(*tnorms) * (size_t)numVerts, __func__);
237
238         if (pnors) {
239                 mp = mpolys;
240                 for (i = 0; i < numPolys; i++, mp++) {
241                         mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, pnors[i], tnorms);
242                 }
243         }
244         else {
245                 float tpnor[3];  /* temp poly normal */
246                 mp = mpolys;
247                 for (i = 0; i < numPolys; i++, mp++) {
248                         mesh_calc_normals_poly_accum(mp, mloop + mp->loopstart, mverts, tpnor, tnorms);
249                 }
250         }
251
252         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
253         for (i = 0; i < numVerts; i++) {
254                 MVert *mv = &mverts[i];
255                 float *no = tnorms[i];
256
257                 if (UNLIKELY(normalize_v3(no) == 0.0f)) {
258                         normalize_v3_v3(no, mv->co);
259                 }
260
261                 normal_float_to_short_v3(mv->no, no);
262         }
263
264         MEM_freeN(tnorms);
265 }
266
267 void BKE_mesh_calc_normals(Mesh *mesh)
268 {
269 #ifdef DEBUG_TIME
270         TIMEIT_START(BKE_mesh_calc_normals);
271 #endif
272         BKE_mesh_calc_normals_poly(mesh->mvert, mesh->totvert,
273                                    mesh->mloop, mesh->mpoly, mesh->totloop, mesh->totpoly,
274                                    NULL, false);
275 #ifdef DEBUG_TIME
276         TIMEIT_END(BKE_mesh_calc_normals);
277 #endif
278 }
279
280 void BKE_mesh_calc_normals_tessface(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*r_faceNors)[3])
281 {
282         float (*tnorms)[3] = MEM_callocN(sizeof(*tnorms) * (size_t)numVerts, "tnorms");
283         float (*fnors)[3] = (r_faceNors) ? r_faceNors : MEM_callocN(sizeof(*fnors) * (size_t)numFaces, "meshnormals");
284         int i;
285
286         for (i = 0; i < numFaces; i++) {
287                 MFace *mf = &mfaces[i];
288                 float *f_no = fnors[i];
289                 float *n4 = (mf->v4) ? tnorms[mf->v4] : NULL;
290                 float *c4 = (mf->v4) ? mverts[mf->v4].co : NULL;
291
292                 if (mf->v4)
293                         normal_quad_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co);
294                 else
295                         normal_tri_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co);
296
297                 accumulate_vertex_normals(tnorms[mf->v1], tnorms[mf->v2], tnorms[mf->v3], n4,
298                                           f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, c4);
299         }
300
301         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
302         for (i = 0; i < numVerts; i++) {
303                 MVert *mv = &mverts[i];
304                 float *no = tnorms[i];
305                 
306                 if (UNLIKELY(normalize_v3(no) == 0.0f)) {
307                         normalize_v3_v3(no, mv->co);
308                 }
309
310                 normal_float_to_short_v3(mv->no, no);
311         }
312         
313         MEM_freeN(tnorms);
314
315         if (fnors != r_faceNors)
316                 MEM_freeN(fnors);
317 }
318
319 /**
320  * Compute split normals, i.e. vertex normals associated with each poly (hence 'loop normals').
321  * Useful to materialize sharp edges (or non-smooth faces) without actually modifying the geometry (splitting edges).
322  */
323 void BKE_mesh_normals_loop_split(MVert *mverts, const int UNUSED(numVerts), MEdge *medges, const int numEdges,
324                                  MLoop *mloops, float (*r_loopnors)[3], const int numLoops,
325                                  MPoly *mpolys, float (*polynors)[3], const int numPolys, float split_angle)
326 {
327 #define INDEX_UNSET INT_MIN
328 #define INDEX_INVALID -1
329 /* See comment about edge_to_loops below. */
330 #define IS_EDGE_SHARP(_e2l) (ELEM((_e2l)[1], INDEX_UNSET, INDEX_INVALID))
331
332         /* Mapping edge -> loops.
333          * If that edge is used by more than two loops (polys), it is always sharp (and tagged as such, see below).
334          * We also use the second loop index as a kind of flag: smooth edge: > 0,
335          *                                                      sharp edge: < 0 (INDEX_INVALID || INDEX_UNSET),
336          *                                                      unset: INDEX_UNSET
337          * Note that currently we only have two values for second loop of sharp edges. However, if needed, we can
338          * store the negated value of loop index instead of INDEX_INVALID to retrieve the real value later in code).
339          * Note also that lose edges always have both values set to 0!
340          */
341         int (*edge_to_loops)[2] = MEM_callocN(sizeof(int[2]) * (size_t)numEdges, __func__);
342
343         /* Simple mapping from a loop to its polygon index. */
344         int *loop_to_poly = MEM_mallocN(sizeof(int) * (size_t)numLoops, __func__);
345
346         MPoly *mp;
347         int mp_index;
348         const bool check_angle = (split_angle < (float)M_PI);
349
350         /* Temp normal stack. */
351         BLI_SMALLSTACK_DECLARE(normal, float *);
352
353 #ifdef DEBUG_TIME
354         TIMEIT_START(BKE_mesh_normals_loop_split);
355 #endif
356
357         if (check_angle) {
358                 split_angle = cosf(split_angle);
359         }
360
361         /* This first loop check which edges are actually smooth, and compute edge vectors. */
362         for (mp = mpolys, mp_index = 0; mp_index < numPolys; mp++, mp_index++) {
363                 MLoop *ml_curr;
364                 int *e2l;
365                 int ml_curr_index = mp->loopstart;
366                 const int ml_last_index = (ml_curr_index + mp->totloop) - 1;
367
368                 ml_curr = &mloops[ml_curr_index];
369
370                 for (; ml_curr_index <= ml_last_index; ml_curr++, ml_curr_index++) {
371                         e2l = edge_to_loops[ml_curr->e];
372
373                         loop_to_poly[ml_curr_index] = mp_index;
374
375                         /* Pre-populate all loop normals as if their verts were all-smooth, this way we don't have to compute
376                          * those later!
377                          */
378                         normal_short_to_float_v3(r_loopnors[ml_curr_index], mverts[ml_curr->v].no);
379
380                         /* Check whether current edge might be smooth or sharp */
381                         if ((e2l[0] | e2l[1]) == 0) {
382                                 /* 'Empty' edge until now, set e2l[0] (and e2l[1] to INDEX_UNSET to tag it as unset). */
383                                 e2l[0] = ml_curr_index;
384                                 /* We have to check this here too, else we might miss some flat faces!!! */
385                                 e2l[1] = (mp->flag & ME_SMOOTH) ? INDEX_UNSET : INDEX_INVALID;
386                         }
387                         else if (e2l[1] == INDEX_UNSET) {
388                                 /* Second loop using this edge, time to test its sharpness.
389                                  * An edge is sharp if it is tagged as such, or its face is not smooth, or angle between
390                                  * both its polys' normals is above split_angle value...
391                                  */
392                                 if (!(mp->flag & ME_SMOOTH) || (medges[ml_curr->e].flag & ME_SHARP) ||
393                                     (check_angle && dot_v3v3(polynors[loop_to_poly[e2l[0]]], polynors[mp_index]) < split_angle))
394                                 {
395                                         /* Note: we are sure that loop != 0 here ;) */
396                                         e2l[1] = INDEX_INVALID;
397                                 }
398                                 else {
399                                         e2l[1] = ml_curr_index;
400                                 }
401                         }
402                         else if (!IS_EDGE_SHARP(e2l)) {
403                                 /* More than two loops using this edge, tag as sharp if not yet done. */
404                                 e2l[1] = INDEX_INVALID;
405                         }
406                         /* Else, edge is already 'disqualified' (i.e. sharp)! */
407                 }
408         }
409
410         /* We now know edges that can be smoothed (with their vector, and their two loops), and edges that will be hard!
411          * Now, time to generate the normals.
412          */
413         for (mp = mpolys, mp_index = 0; mp_index < numPolys; mp++, mp_index++) {
414                 MLoop *ml_curr, *ml_prev;
415                 float (*lnors)[3];
416                 const int ml_last_index = (mp->loopstart + mp->totloop) - 1;
417                 int ml_curr_index = mp->loopstart;
418                 int ml_prev_index = ml_last_index;
419
420                 ml_curr = &mloops[ml_curr_index];
421                 ml_prev = &mloops[ml_prev_index];
422                 lnors = &r_loopnors[ml_curr_index];
423
424                 for (; ml_curr_index <= ml_last_index; ml_curr++, ml_curr_index++, lnors++) {
425                         const int *e2l_curr = edge_to_loops[ml_curr->e];
426                         const int *e2l_prev = edge_to_loops[ml_prev->e];
427
428                         if (!IS_EDGE_SHARP(e2l_curr)) {
429                                 /* A smooth edge.
430                                  * We skip it because it is either:
431                                  * - in the middle of a 'smooth fan' already computed (or that will be as soon as we hit
432                                  *   one of its ends, i.e. one of its two sharp edges), or...
433                                  * - the related vertex is a "full smooth" one, in which case pre-populated normals from vertex
434                                  *   are just fine!
435                                  */
436                         }
437                         else if (IS_EDGE_SHARP(e2l_prev)) {
438                                 /* Simple case (both edges around that vertex are sharp in current polygon),
439                                  * this vertex just takes its poly normal.
440                                  */
441                                 copy_v3_v3(*lnors, polynors[mp_index]);
442                                 /* No need to mark loop as done here, we won't run into it again anyway! */
443                         }
444                         /* This loop may have been already computed, in which case its 'to_poly' map is set to -1... */
445                         else if (loop_to_poly[ml_curr_index] != -1) {
446                                 /* Gah... We have to fan around current vertex, until we find the other non-smooth edge,
447                                  * and accumulate face normals into the vertex!
448                                  * Note in case this vertex has only one sharp edges, this is a waste because the normal is the same as
449                                  * the vertex normal, but I do not see any easy way to detect that (would need to count number
450                                  * of sharp edges per vertex, I doubt the additional memory usage would be worth it, especially as
451                                  * it should not be a common case in real-life meshes anyway).
452                                  */
453                                 const unsigned int mv_pivot_index = ml_curr->v;  /* The vertex we are "fanning" around! */
454                                 const MVert *mv_pivot = &mverts[mv_pivot_index];
455                                 const int *e2lfan_curr;
456                                 float vec_curr[3], vec_prev[3];
457                                 MLoop *mlfan_curr, *mlfan_next;
458                                 MPoly *mpfan_next;
459                                 float lnor[3] = {0.0f, 0.0f, 0.0f};
460                                 /* mlfan_vert_index: the loop of our current edge might not be the loop of our current vertex! */
461                                 int mlfan_curr_index, mlfan_vert_index, mpfan_curr_index;
462
463                                 e2lfan_curr = e2l_prev;
464                                 mlfan_curr = ml_prev;
465                                 mlfan_curr_index = ml_prev_index;
466                                 mlfan_vert_index = ml_curr_index;
467                                 mpfan_curr_index = mp_index;
468
469                                 /* Only need to compute previous edge's vector once, then we can just reuse old current one! */
470                                 {
471                                         const MEdge *me_prev = &medges[ml_curr->e];  /* ml_curr would be mlfan_prev if we needed that one */
472                                         const MVert *mv_2 = (me_prev->v1 == mv_pivot_index) ? &mverts[me_prev->v2] : &mverts[me_prev->v1];
473
474                                         sub_v3_v3v3(vec_prev, mv_2->co, mv_pivot->co);
475                                         normalize_v3(vec_prev);
476                                 }
477
478                                 while (true) {
479                                         /* Compute edge vectors.
480                                          * NOTE: We could pre-compute those into an array, in the first iteration, instead of computing them
481                                          *       twice (or more) here. However, time gained is not worth memory and time lost,
482                                          *       given the fact that this code should not be called that much in real-life meshes...
483                                          */
484                                         {
485                                                 const MEdge *me_curr = &medges[mlfan_curr->e];
486                                                 const MVert *mv_2 = (me_curr->v1 == mv_pivot_index) ? &mverts[me_curr->v2] :
487                                                                                                       &mverts[me_curr->v1];
488
489                                                 sub_v3_v3v3(vec_curr, mv_2->co, mv_pivot->co);
490                                                 normalize_v3(vec_curr);
491                                         }
492
493                                         {
494                                                 /* Code similar to accumulate_vertex_normals_poly. */
495                                                 /* Calculate angle between the two poly edges incident on this vertex. */
496                                                 const float fac = saacos(dot_v3v3(vec_curr, vec_prev));
497                                                 /* Accumulate */
498                                                 madd_v3_v3fl(lnor, polynors[mpfan_curr_index], fac);
499                                         }
500
501                                         /* We store here a pointer to all loop-normals processed. */
502                                         BLI_SMALLSTACK_PUSH(normal, &(r_loopnors[mlfan_vert_index][0]));
503
504                                         /* And we are done with this loop, mark it as such! */
505                                         loop_to_poly[mlfan_vert_index] = -1;
506
507                                         if (IS_EDGE_SHARP(e2lfan_curr)) {
508                                                 /* Current edge is sharp, we have finished with this fan of faces around this vert! */
509                                                 break;
510                                         }
511
512                                         copy_v3_v3(vec_prev, vec_curr);
513
514                                         /* Warning! This is rather complex!
515                                          * We have to find our next edge around the vertex (fan mode).
516                                          * First we find the next loop, which is either previous or next to mlfan_curr_index, depending
517                                          * whether both loops using current edge are in the same direction or not, and whether
518                                          * mlfan_curr_index actually uses the vertex we are fanning around!
519                                          * mlfan_curr_index is the index of mlfan_next here, and mlfan_next is not the real next one
520                                          * (i.e. not the future mlfan_curr)...
521                                          */
522                                         mlfan_curr_index = (e2lfan_curr[0] == mlfan_curr_index) ? e2lfan_curr[1] : e2lfan_curr[0];
523                                         mpfan_curr_index = loop_to_poly[mlfan_curr_index];
524                                         mlfan_next = &mloops[mlfan_curr_index];
525                                         mpfan_next = &mpolys[mpfan_curr_index];
526                                         if ((mlfan_curr->v == mlfan_next->v && mlfan_curr->v == mv_pivot_index) ||
527                                             (mlfan_curr->v != mlfan_next->v && mlfan_curr->v != mv_pivot_index))
528                                         {
529                                                 /* We need the previous loop, but current one is our vertex's loop. */
530                                                 mlfan_vert_index = mlfan_curr_index;
531                                                 if (--mlfan_curr_index < mpfan_next->loopstart) {
532                                                         mlfan_curr_index = mpfan_next->loopstart + mpfan_next->totloop - 1;
533                                                 }
534                                         }
535                                         else {
536                                                 /* We need the next loop, which is also our vertex's loop. */
537                                                 if (++mlfan_curr_index >= mpfan_next->loopstart + mpfan_next->totloop) {
538                                                         mlfan_curr_index = mpfan_next->loopstart;
539                                                 }
540                                                 mlfan_vert_index = mlfan_curr_index;
541                                         }
542                                         mlfan_curr = &mloops[mlfan_curr_index];
543                                         /* And now we are back in sync, mlfan_curr_index is the index of mlfan_curr! Pff! */
544
545                                         e2lfan_curr = edge_to_loops[mlfan_curr->e];
546                                 }
547
548                                 /* In case we get a zero normal here, just use vertex normal already set! */
549                                 if (LIKELY(normalize_v3(lnor) != 0.0f)) {
550                                         /* Copy back the final computed normal into all related loop-normals. */
551                                         float *nor;
552                                         while ((nor = BLI_SMALLSTACK_POP(normal))) {
553                                                 copy_v3_v3(nor, lnor);
554                                         }
555                                 }
556                         }
557
558                         ml_prev = ml_curr;
559                         ml_prev_index = ml_curr_index;
560                 }
561         }
562
563         BLI_SMALLSTACK_FREE(normal);
564
565         MEM_freeN(edge_to_loops);
566         MEM_freeN(loop_to_poly);
567
568 #ifdef DEBUG_TIME
569         TIMEIT_END(BKE_mesh_normals_loop_split);
570 #endif
571
572 #undef INDEX_UNSET
573 #undef INDEX_INVALID
574 #undef IS_EDGE_SHARP
575 }
576
577
578 /** \} */
579
580
581 /* -------------------------------------------------------------------- */
582
583 /** \name Mesh Tangent Calculations
584  * \{ */
585
586 /* Tangent space utils. */
587
588 /* User data. */
589 typedef struct {
590         MPoly *mpolys;         /* faces */
591         MLoop *mloops;         /* faces's vertices */
592         MVert *mverts;         /* vertices */
593         MLoopUV *luvs;         /* texture coordinates */
594         float (*lnors)[3];     /* loops' normals */
595         float (*tangents)[4];  /* output tangents */
596         int num_polys;         /* number of polygons */
597 } BKEMeshToTangent;
598
599 /* Mikktspace's API */
600 static int get_num_faces(const SMikkTSpaceContext *pContext)
601 {
602         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
603         return p_mesh->num_polys;
604 }
605
606 static int get_num_verts_of_face(const SMikkTSpaceContext *pContext, const int face_idx)
607 {
608         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
609         return p_mesh->mpolys[face_idx].totloop;
610 }
611
612 static void get_position(const SMikkTSpaceContext *pContext, float r_co[3], const int face_idx, const int vert_idx)
613 {
614         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
615         const int loop_idx = p_mesh->mpolys[face_idx].loopstart + vert_idx;
616         copy_v3_v3(r_co, p_mesh->mverts[p_mesh->mloops[loop_idx].v].co);
617 }
618
619 static void get_texture_coordinate(const SMikkTSpaceContext *pContext, float r_uv[2], const int face_idx,
620                                    const int vert_idx)
621 {
622         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
623         copy_v2_v2(r_uv, p_mesh->luvs[p_mesh->mpolys[face_idx].loopstart + vert_idx].uv);
624 }
625
626 static void get_normal(const SMikkTSpaceContext *pContext, float r_no[3], const int face_idx, const int vert_idx)
627 {
628         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
629         copy_v3_v3(r_no, p_mesh->lnors[p_mesh->mpolys[face_idx].loopstart + vert_idx]);
630 }
631
632 static void set_tspace(const SMikkTSpaceContext *pContext, const float fv_tangent[3], const float face_sign,
633                        const int face_idx, const int vert_idx)
634 {
635         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
636         float *p_res = p_mesh->tangents[p_mesh->mpolys[face_idx].loopstart + vert_idx];
637         copy_v3_v3(p_res, fv_tangent);
638         p_res[3] = face_sign;
639 }
640
641 /**
642  * Compute simplified tangent space normals, i.e. tangent vector + sign of bi-tangent one, which combined with
643  * split normals can be used to recreate the full tangent space.
644  * Note: * The mesh should be made of only tris and quads!
645  */
646 void BKE_mesh_loop_tangents_ex(MVert *mverts, const int UNUSED(numVerts), MLoop *mloops,
647                                float (*r_looptangent)[4], float (*loopnors)[3], MLoopUV *loopuvs,
648                                const int UNUSED(numLoops), MPoly *mpolys, const int numPolys, ReportList *reports)
649 {
650         BKEMeshToTangent mesh_to_tangent = {NULL};
651         SMikkTSpaceContext s_context = {NULL};
652         SMikkTSpaceInterface s_interface = {NULL};
653
654         MPoly *mp;
655         int mp_index;
656
657         /* First check we do have a tris/quads only mesh. */
658         for (mp = mpolys, mp_index = 0; mp_index < numPolys; mp++, mp_index++) {
659                 if (mp->totloop > 4) {
660                         BKE_report(reports, RPT_ERROR, "Tangent space can only be computed for tris/quads, aborting");
661                         return;
662                 }
663         }
664
665         /* Compute Mikktspace's tangent normals. */
666         mesh_to_tangent.mpolys = mpolys;
667         mesh_to_tangent.mloops = mloops;
668         mesh_to_tangent.mverts = mverts;
669         mesh_to_tangent.luvs = loopuvs;
670         mesh_to_tangent.lnors = loopnors;
671         mesh_to_tangent.tangents = r_looptangent;
672         mesh_to_tangent.num_polys = numPolys;
673
674         s_context.m_pUserData = &mesh_to_tangent;
675         s_context.m_pInterface = &s_interface;
676         s_interface.m_getNumFaces = get_num_faces;
677         s_interface.m_getNumVerticesOfFace = get_num_verts_of_face;
678         s_interface.m_getPosition = get_position;
679         s_interface.m_getTexCoord = get_texture_coordinate;
680         s_interface.m_getNormal = get_normal;
681         s_interface.m_setTSpaceBasic = set_tspace;
682
683         /* 0 if failed */
684         if (genTangSpaceDefault(&s_context) == false) {
685                 BKE_report(reports, RPT_ERROR, "Mikktspace failed to generate tangents for this mesh!");
686         }
687 }
688
689 /**
690  * Wrapper around BKE_mesh_loop_tangents_ex, which takes care of most boiling code.
691  * Note: * There must be a valid loop's CD_NORMALS available.
692  *       * The mesh should be made of only tris and quads!
693  */
694 void BKE_mesh_loop_tangents(Mesh *mesh, const char *uvmap, float (*r_looptangents)[4], ReportList *reports)
695 {
696         MLoopUV *loopuvs;
697         float (*loopnors)[3];
698
699         /* Check we have valid texture coordinates first! */
700         if (uvmap) {
701                 loopuvs = CustomData_get_layer_named(&mesh->ldata, CD_MLOOPUV, uvmap);
702         }
703         else {
704                 loopuvs = CustomData_get_layer(&mesh->ldata, CD_MLOOPUV);
705         }
706         if (!loopuvs) {
707                 BKE_reportf(reports, RPT_ERROR, "Tangent space computation needs an UVMap, \"%s\" not found, aborting", uvmap);
708                 return;
709         }
710
711         loopnors = CustomData_get_layer(&mesh->ldata, CD_NORMAL);
712         if (!loopnors) {
713                 BKE_report(reports, RPT_ERROR, "Tangent space computation needs loop normals, none found, aborting");
714                 return;
715         }
716
717         BKE_mesh_loop_tangents_ex(mesh->mvert, mesh->totvert, mesh->mloop, r_looptangents,
718                               loopnors, loopuvs, mesh->totloop, mesh->mpoly, mesh->totpoly, reports);
719 }
720
721 /** \} */
722
723
724 /* -------------------------------------------------------------------- */
725
726 /** \name Polygon Calculations
727  * \{ */
728
729 /*
730  * COMPUTE POLY NORMAL
731  *
732  * Computes the normal of a planar
733  * polygon See Graphics Gems for
734  * computing newell normal.
735  *
736  */
737 static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart,
738                                   MVert *mvert, float normal[3])
739 {
740         const int nverts = mpoly->totloop;
741         float const *v_prev = mvert[loopstart[nverts - 1].v].co;
742         float const *v_curr;
743         int i;
744
745         zero_v3(normal);
746
747         /* Newell's Method */
748         for (i = 0; i < nverts; i++) {
749                 v_curr = mvert[loopstart[i].v].co;
750                 add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
751                 v_prev = v_curr;
752         }
753
754         if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
755                 normal[2] = 1.0f; /* other axis set to 0.0 */
756         }
757 }
758
759 void BKE_mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart,
760                                MVert *mvarray, float no[3])
761 {
762         if (mpoly->totloop > 4) {
763                 mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no);
764         }
765         else if (mpoly->totloop == 3) {
766                 normal_tri_v3(no,
767                               mvarray[loopstart[0].v].co,
768                               mvarray[loopstart[1].v].co,
769                               mvarray[loopstart[2].v].co
770                               );
771         }
772         else if (mpoly->totloop == 4) {
773                 normal_quad_v3(no,
774                                mvarray[loopstart[0].v].co,
775                                mvarray[loopstart[1].v].co,
776                                mvarray[loopstart[2].v].co,
777                                mvarray[loopstart[3].v].co
778                                );
779         }
780         else { /* horrible, two sided face! */
781                 no[0] = 0.0;
782                 no[1] = 0.0;
783                 no[2] = 1.0;
784         }
785 }
786 /* duplicate of function above _but_ takes coords rather then mverts */
787 static void mesh_calc_ngon_normal_coords(MPoly *mpoly, MLoop *loopstart,
788                                          const float (*vertex_coords)[3], float normal[3])
789 {
790         const int nverts = mpoly->totloop;
791         float const *v_prev = vertex_coords[loopstart[nverts - 1].v];
792         float const *v_curr;
793         int i;
794
795         zero_v3(normal);
796
797         /* Newell's Method */
798         for (i = 0; i < nverts; i++) {
799                 v_curr = vertex_coords[loopstart[i].v];
800                 add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
801                 v_prev = v_curr;
802         }
803
804         if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
805                 normal[2] = 1.0f; /* other axis set to 0.0 */
806         }
807 }
808
809 void BKE_mesh_calc_poly_normal_coords(MPoly *mpoly, MLoop *loopstart,
810                                       const float (*vertex_coords)[3], float no[3])
811 {
812         if (mpoly->totloop > 4) {
813                 mesh_calc_ngon_normal_coords(mpoly, loopstart, vertex_coords, no);
814         }
815         else if (mpoly->totloop == 3) {
816                 normal_tri_v3(no,
817                               vertex_coords[loopstart[0].v],
818                               vertex_coords[loopstart[1].v],
819                               vertex_coords[loopstart[2].v]
820                               );
821         }
822         else if (mpoly->totloop == 4) {
823                 normal_quad_v3(no,
824                                vertex_coords[loopstart[0].v],
825                                vertex_coords[loopstart[1].v],
826                                vertex_coords[loopstart[2].v],
827                                vertex_coords[loopstart[3].v]
828                                );
829         }
830         else { /* horrible, two sided face! */
831                 no[0] = 0.0;
832                 no[1] = 0.0;
833                 no[2] = 1.0;
834         }
835 }
836
837 static void mesh_calc_ngon_center(MPoly *mpoly, MLoop *loopstart,
838                                   MVert *mvert, float cent[3])
839 {
840         const float w = 1.0f / (float)mpoly->totloop;
841         int i;
842
843         zero_v3(cent);
844
845         for (i = 0; i < mpoly->totloop; i++) {
846                 madd_v3_v3fl(cent, mvert[(loopstart++)->v].co, w);
847         }
848 }
849
850 void BKE_mesh_calc_poly_center(MPoly *mpoly, MLoop *loopstart,
851                                MVert *mvarray, float cent[3])
852 {
853         if (mpoly->totloop == 3) {
854                 cent_tri_v3(cent,
855                             mvarray[loopstart[0].v].co,
856                             mvarray[loopstart[1].v].co,
857                             mvarray[loopstart[2].v].co
858                             );
859         }
860         else if (mpoly->totloop == 4) {
861                 cent_quad_v3(cent,
862                              mvarray[loopstart[0].v].co,
863                              mvarray[loopstart[1].v].co,
864                              mvarray[loopstart[2].v].co,
865                              mvarray[loopstart[3].v].co
866                              );
867         }
868         else {
869                 mesh_calc_ngon_center(mpoly, loopstart, mvarray, cent);
870         }
871 }
872
873 /* note, passing polynormal is only a speedup so we can skip calculating it */
874 float BKE_mesh_calc_poly_area(MPoly *mpoly, MLoop *loopstart,
875                               MVert *mvarray, const float polynormal[3])
876 {
877         if (mpoly->totloop == 3) {
878                 return area_tri_v3(mvarray[loopstart[0].v].co,
879                                    mvarray[loopstart[1].v].co,
880                                    mvarray[loopstart[2].v].co
881                                    );
882         }
883         else if (mpoly->totloop == 4) {
884                 return area_quad_v3(mvarray[loopstart[0].v].co,
885                                     mvarray[loopstart[1].v].co,
886                                     mvarray[loopstart[2].v].co,
887                                     mvarray[loopstart[3].v].co
888                                     );
889         }
890         else {
891                 int i;
892                 MLoop *l_iter = loopstart;
893                 float area, polynorm_local[3];
894                 float (*vertexcos)[3] = BLI_array_alloca(vertexcos, (size_t)mpoly->totloop);
895                 const float *no = polynormal ? polynormal : polynorm_local;
896
897                 /* pack vertex cos into an array for area_poly_v3 */
898                 for (i = 0; i < mpoly->totloop; i++, l_iter++) {
899                         copy_v3_v3(vertexcos[i], mvarray[l_iter->v].co);
900                 }
901
902                 /* need normal for area_poly_v3 as well */
903                 if (polynormal == NULL) {
904                         BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, polynorm_local);
905                 }
906
907                 /* finally calculate the area */
908                 area = area_poly_v3((const float (*)[3])vertexcos, (unsigned int)mpoly->totloop, no);
909
910                 return area;
911         }
912 }
913
914 /* note, results won't be correct if polygon is non-planar */
915 static float mesh_calc_poly_planar_area_centroid(MPoly *mpoly, MLoop *loopstart, MVert *mvarray, float cent[3])
916 {
917         int i;
918         float tri_area;
919         float total_area = 0.0f;
920         float v1[3], v2[3], v3[3], normal[3], tri_cent[3];
921
922         BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, normal);
923         copy_v3_v3(v1, mvarray[loopstart[0].v].co);
924         copy_v3_v3(v2, mvarray[loopstart[1].v].co);
925         zero_v3(cent);
926
927         for (i = 2; i < mpoly->totloop; i++) {
928                 copy_v3_v3(v3, mvarray[loopstart[i].v].co);
929
930                 tri_area = area_tri_signed_v3(v1, v2, v3, normal);
931                 total_area += tri_area;
932
933                 cent_tri_v3(tri_cent, v1, v2, v3);
934                 madd_v3_v3fl(cent, tri_cent, tri_area);
935
936                 copy_v3_v3(v2, v3);
937         }
938
939         mul_v3_fl(cent, 1.0f / total_area);
940
941         return total_area;
942 }
943
944 #if 0 /* slow version of the function below */
945 void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart,
946                                MVert *mvarray, float angles[])
947 {
948         MLoop *ml;
949         MLoop *mloop = &loopstart[-mpoly->loopstart];
950
951         int j;
952         for (j = 0, ml = loopstart; j < mpoly->totloop; j++, ml++) {
953                 MLoop *ml_prev = ME_POLY_LOOP_PREV(mloop, mpoly, j);
954                 MLoop *ml_next = ME_POLY_LOOP_NEXT(mloop, mpoly, j);
955
956                 float e1[3], e2[3];
957
958                 sub_v3_v3v3(e1, mvarray[ml_next->v].co, mvarray[ml->v].co);
959                 sub_v3_v3v3(e2, mvarray[ml_prev->v].co, mvarray[ml->v].co);
960
961                 angles[j] = (float)M_PI - angle_v3v3(e1, e2);
962         }
963 }
964
965 #else /* equivalent the function above but avoid multiple subtractions + normalize */
966
967 void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart,
968                                MVert *mvarray, float angles[])
969 {
970         float nor_prev[3];
971         float nor_next[3];
972
973         int i_this = mpoly->totloop - 1;
974         int i_next = 0;
975
976         sub_v3_v3v3(nor_prev, mvarray[loopstart[i_this - 1].v].co, mvarray[loopstart[i_this].v].co);
977         normalize_v3(nor_prev);
978
979         while (i_next < mpoly->totloop) {
980                 sub_v3_v3v3(nor_next, mvarray[loopstart[i_this].v].co, mvarray[loopstart[i_next].v].co);
981                 normalize_v3(nor_next);
982                 angles[i_this] = angle_normalized_v3v3(nor_prev, nor_next);
983
984                 /* step */
985                 copy_v3_v3(nor_prev, nor_next);
986                 i_this = i_next;
987                 i_next++;
988         }
989 }
990 #endif
991
992 void BKE_mesh_poly_edgehash_insert(EdgeHash *ehash, const MPoly *mp, const MLoop *mloop)
993 {
994         const MLoop *ml, *ml_next;
995         int i = mp->totloop;
996
997         ml_next = mloop;       /* first loop */
998         ml = &ml_next[i - 1];  /* last loop */
999
1000         while (i-- != 0) {
1001                 BLI_edgehash_reinsert(ehash, ml->v, ml_next->v, NULL);
1002
1003                 ml = ml_next;
1004                 ml_next++;
1005         }
1006 }
1007
1008 void BKE_mesh_poly_edgebitmap_insert(unsigned int *edge_bitmap, const MPoly *mp, const MLoop *mloop)
1009 {
1010         const MLoop *ml;
1011         int i = mp->totloop;
1012
1013         ml = mloop;
1014
1015         while (i-- != 0) {
1016                 BLI_BITMAP_SET(edge_bitmap, ml->e);
1017                 ml++;
1018         }
1019 }
1020
1021 /** \} */
1022
1023
1024 /* -------------------------------------------------------------------- */
1025
1026 /** \name Mesh Center Calculation
1027  * \{ */
1028
1029 bool BKE_mesh_center_median(Mesh *me, float cent[3])
1030 {
1031         int i = me->totvert;
1032         MVert *mvert;
1033         zero_v3(cent);
1034         for (mvert = me->mvert; i--; mvert++) {
1035                 add_v3_v3(cent, mvert->co);
1036         }
1037         /* otherwise we get NAN for 0 verts */
1038         if (me->totvert) {
1039                 mul_v3_fl(cent, 1.0f / (float)me->totvert);
1040         }
1041
1042         return (me->totvert != 0);
1043 }
1044
1045 bool BKE_mesh_center_bounds(Mesh *me, float cent[3])
1046 {
1047         float min[3], max[3];
1048         INIT_MINMAX(min, max);
1049         if (BKE_mesh_minmax(me, min, max)) {
1050                 mid_v3_v3v3(cent, min, max);
1051                 return true;
1052         }
1053
1054         return false;
1055 }
1056
1057 bool BKE_mesh_center_centroid(Mesh *me, float cent[3])
1058 {
1059         int i = me->totpoly;
1060         MPoly *mpoly;
1061         float poly_area;
1062         float total_area = 0.0f;
1063         float poly_cent[3];
1064
1065         zero_v3(cent);
1066
1067         /* calculate a weighted average of polygon centroids */
1068         for (mpoly = me->mpoly; i--; mpoly++) {
1069                 poly_area = mesh_calc_poly_planar_area_centroid(mpoly, me->mloop + mpoly->loopstart, me->mvert, poly_cent);
1070
1071                 madd_v3_v3fl(cent, poly_cent, poly_area);
1072                 total_area += poly_area;
1073         }
1074         /* otherwise we get NAN for 0 polys */
1075         if (me->totpoly) {
1076                 mul_v3_fl(cent, 1.0f / total_area);
1077         }
1078
1079         /* zero area faces cause this, fallback to median */
1080         if (UNLIKELY(!is_finite_v3(cent))) {
1081                 return BKE_mesh_center_median(me, cent);
1082         }
1083
1084         return (me->totpoly != 0);
1085 }
1086 /** \} */
1087
1088
1089 /* -------------------------------------------------------------------- */
1090
1091 /** \name NGon Tessellation (NGon/Tessface Conversion)
1092  * \{ */
1093
1094 /**
1095  * Convert a triangle or quadrangle of loop/poly data to tessface data
1096  */
1097 void BKE_mesh_loops_to_mface_corners(
1098         CustomData *fdata, CustomData *ldata,
1099         CustomData *pdata, unsigned int lindex[4], int findex,
1100         const int polyindex,
1101         const int mf_len, /* 3 or 4 */
1102
1103         /* cache values to avoid lookups every time */
1104         const int numTex, /* CustomData_number_of_layers(pdata, CD_MTEXPOLY) */
1105         const int numCol, /* CustomData_number_of_layers(ldata, CD_MLOOPCOL) */
1106         const bool hasPCol, /* CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL) */
1107         const bool hasOrigSpace, /* CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP) */
1108         const bool hasLNor /* CustomData_has_layer(ldata, CD_NORMAL) */
1109 )
1110 {
1111         MTFace *texface;
1112         MTexPoly *texpoly;
1113         MCol *mcol;
1114         MLoopCol *mloopcol;
1115         MLoopUV *mloopuv;
1116         int i, j;
1117
1118         for (i = 0; i < numTex; i++) {
1119                 texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
1120                 texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i);
1121
1122                 ME_MTEXFACE_CPY(texface, texpoly);
1123
1124                 for (j = 0; j < mf_len; j++) {
1125                         mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, (int)lindex[j], i);
1126                         copy_v2_v2(texface->uv[j], mloopuv->uv);
1127                 }
1128         }
1129
1130         for (i = 0; i < numCol; i++) {
1131                 mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
1132
1133                 for (j = 0; j < mf_len; j++) {
1134                         mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, (int)lindex[j], i);
1135                         MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
1136                 }
1137         }
1138
1139         if (hasPCol) {
1140                 mcol = CustomData_get(fdata,  findex, CD_PREVIEW_MCOL);
1141
1142                 for (j = 0; j < mf_len; j++) {
1143                         mloopcol = CustomData_get(ldata, (int)lindex[j], CD_PREVIEW_MLOOPCOL);
1144                         MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
1145                 }
1146         }
1147
1148         if (hasOrigSpace) {
1149                 OrigSpaceFace *of = CustomData_get(fdata, findex, CD_ORIGSPACE);
1150                 OrigSpaceLoop *lof;
1151
1152                 for (j = 0; j < mf_len; j++) {
1153                         lof = CustomData_get(ldata, (int)lindex[j], CD_ORIGSPACE_MLOOP);
1154                         copy_v2_v2(of->uv[j], lof->uv);
1155                 }
1156         }
1157
1158         if (hasLNor) {
1159                 short (*tlnors)[3] = CustomData_get(fdata, findex, CD_TESSLOOPNORMAL);
1160
1161                 for (j = 0; j < mf_len; j++) {
1162                         normal_float_to_short_v3(tlnors[j], CustomData_get(ldata, (int)lindex[j], CD_NORMAL));
1163                 }
1164         }
1165 }
1166
1167 /**
1168  * Convert all CD layers from loop/poly to tessface data.
1169  *
1170  * @loopindices is an array of an int[4] per tessface, mapping tessface's verts to loops indices.
1171  *
1172  * Note when mface is not NULL, mface[face_index].v4 is used to test quads, else, loopindices[face_index][3] is used.
1173  */
1174 void BKE_mesh_loops_to_tessdata(CustomData *fdata, CustomData *ldata, CustomData *pdata, MFace *mface,
1175                                 int *polyindices, unsigned int (*loopindices)[4], const int num_faces)
1176 {
1177         /* Note: performances are sub-optimal when we get a NULL mface, we could be ~25% quicker with dedicated code...
1178          *       Issue is, unless having two different functions with nearly the same code, there's not much ways to solve
1179          *       this. Better imho to live with it for now. :/ --mont29
1180          */
1181         const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
1182         const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
1183         const bool hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
1184         const bool hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
1185         const bool hasLoopNormal = CustomData_has_layer(ldata, CD_NORMAL);
1186         int findex, i, j;
1187         int *pidx;
1188         unsigned int (*lidx)[4];
1189
1190         for (i = 0; i < numTex; i++) {
1191                 MTFace *texface = CustomData_get_layer_n(fdata, CD_MTFACE, i);
1192                 MTexPoly *texpoly = CustomData_get_layer_n(pdata, CD_MTEXPOLY, i);
1193                 MLoopUV *mloopuv = CustomData_get_layer_n(ldata, CD_MLOOPUV, i);
1194
1195                 for (findex = 0, pidx = polyindices, lidx = loopindices;
1196                      findex < num_faces;
1197                      pidx++, lidx++, findex++, texface++)
1198                 {
1199                         ME_MTEXFACE_CPY(texface, &texpoly[*pidx]);
1200
1201                         for (j = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) {
1202                                 copy_v2_v2(texface->uv[j], mloopuv[(*lidx)[j]].uv);
1203                         }
1204                 }
1205         }
1206
1207         for (i = 0; i < numCol; i++) {
1208                 MCol (*mcol)[4] = CustomData_get_layer_n(fdata, CD_MCOL, i);
1209                 MLoopCol *mloopcol = CustomData_get_layer_n(ldata, CD_MLOOPCOL, i);
1210
1211                 for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, mcol++) {
1212                         for (j = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) {
1213                                 MESH_MLOOPCOL_TO_MCOL(&mloopcol[(*lidx)[j]], &(*mcol)[j]);
1214                         }
1215                 }
1216         }
1217
1218         if (hasPCol) {
1219                 MCol (*mcol)[4] = CustomData_get_layer(fdata, CD_PREVIEW_MCOL);
1220                 MLoopCol *mloopcol = CustomData_get_layer(ldata, CD_PREVIEW_MLOOPCOL);
1221
1222                 for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, mcol++) {
1223                         for (j = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) {
1224                                 MESH_MLOOPCOL_TO_MCOL(&mloopcol[(*lidx)[j]], &(*mcol)[j]);
1225                         }
1226                 }
1227         }
1228
1229         if (hasOrigSpace) {
1230                 OrigSpaceFace *of = CustomData_get_layer(fdata, CD_ORIGSPACE);
1231                 OrigSpaceLoop *lof = CustomData_get_layer(ldata, CD_ORIGSPACE_MLOOP);
1232
1233                 for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, of++) {
1234                         for (j = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) {
1235                                 copy_v2_v2(of->uv[j], lof[(*lidx)[j]].uv);
1236                         }
1237                 }
1238         }
1239
1240         if (hasLoopNormal) {
1241                 short (*fnors)[4][3] = CustomData_get_layer(fdata, CD_TESSLOOPNORMAL);
1242                 float (*lnors)[3] = CustomData_get_layer(ldata, CD_NORMAL);
1243
1244                 for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, fnors++) {
1245                         for (j = (*lidx)[3] ? 4 : 3; j--;) {
1246                                 normal_float_to_short_v3((*fnors)[j], lnors[(*lidx)[j]]);
1247                         }
1248                 }
1249         }
1250 }
1251
1252 /**
1253  * Recreate tessellation.
1254  *
1255  * @do_face_nor_copy controls whether the normals from the poly are copied to the tessellated faces.
1256  *
1257  * \return number of tessellation faces.
1258  */
1259 int BKE_mesh_recalc_tessellation(CustomData *fdata, CustomData *ldata, CustomData *pdata,
1260                                  MVert *mvert, int totface, int totloop, int totpoly, const bool do_face_nor_cpy)
1261 {
1262         /* use this to avoid locking pthread for _every_ polygon
1263          * and calling the fill function */
1264
1265 #define USE_TESSFACE_SPEEDUP
1266 #define USE_TESSFACE_QUADS  /* NEEDS FURTHER TESTING */
1267
1268 /* We abuse MFace->edcode to tag quad faces. See below for details. */
1269 #define TESSFACE_IS_QUAD 1
1270
1271         const int looptris_tot = poly_to_tri_count(totpoly, totloop);
1272
1273         MPoly *mp, *mpoly;
1274         MLoop *ml, *mloop;
1275         MFace *mface, *mf;
1276         MemArena *arena = NULL;
1277         int *mface_to_poly_map;
1278         unsigned int (*lindices)[4];
1279         int poly_index, mface_index;
1280         unsigned int j;
1281
1282         mpoly = CustomData_get_layer(pdata, CD_MPOLY);
1283         mloop = CustomData_get_layer(ldata, CD_MLOOP);
1284
1285         /* allocate the length of totfaces, avoid many small reallocs,
1286          * if all faces are tri's it will be correct, quads == 2x allocs */
1287         /* take care. we are _not_ calloc'ing so be sure to initialize each field */
1288         mface_to_poly_map = MEM_mallocN(sizeof(*mface_to_poly_map) * (size_t)looptris_tot, __func__);
1289         mface             = MEM_mallocN(sizeof(*mface) *             (size_t)looptris_tot, __func__);
1290         lindices          = MEM_mallocN(sizeof(*lindices) *          (size_t)looptris_tot, __func__);
1291
1292         mface_index = 0;
1293         mp = mpoly;
1294         for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) {
1295                 const unsigned int mp_loopstart = (unsigned int)mp->loopstart;
1296                 const unsigned int mp_totloop = (unsigned int)mp->totloop;
1297                 unsigned int l1, l2, l3, l4;
1298                 unsigned int *lidx;
1299                 if (mp_totloop < 3) {
1300                         /* do nothing */
1301                 }
1302
1303 #ifdef USE_TESSFACE_SPEEDUP
1304
1305 #define ML_TO_MF(i1, i2, i3)                                                  \
1306                 mface_to_poly_map[mface_index] = poly_index;                          \
1307                 mf = &mface[mface_index];                                             \
1308                 lidx = lindices[mface_index];                                         \
1309                 /* set loop indices, transformed to vert indices later */             \
1310                 l1 = mp_loopstart + i1;                                               \
1311                 l2 = mp_loopstart + i2;                                               \
1312                 l3 = mp_loopstart + i3;                                               \
1313                 mf->v1 = mloop[l1].v;                                                 \
1314                 mf->v2 = mloop[l2].v;                                                 \
1315                 mf->v3 = mloop[l3].v;                                                 \
1316                 mf->v4 = 0;                                                           \
1317                 lidx[0] = l1;                                                         \
1318                 lidx[1] = l2;                                                         \
1319                 lidx[2] = l3;                                                         \
1320                 lidx[3] = 0;                                                          \
1321                 mf->mat_nr = mp->mat_nr;                                              \
1322                 mf->flag = mp->flag;                                                  \
1323                 mf->edcode = 0;                                                       \
1324                 (void)0
1325
1326 /* ALMOST IDENTICAL TO DEFINE ABOVE (see EXCEPTION) */
1327 #define ML_TO_MF_QUAD()                                                       \
1328                 mface_to_poly_map[mface_index] = poly_index;                          \
1329                 mf = &mface[mface_index];                                             \
1330                 lidx = lindices[mface_index];                                         \
1331                 /* set loop indices, transformed to vert indices later */             \
1332                 l1 = mp_loopstart + 0; /* EXCEPTION */                                \
1333                 l2 = mp_loopstart + 1; /* EXCEPTION */                                \
1334                 l3 = mp_loopstart + 2; /* EXCEPTION */                                \
1335                 l4 = mp_loopstart + 3; /* EXCEPTION */                                \
1336                 mf->v1 = mloop[l1].v;                                                 \
1337                 mf->v2 = mloop[l2].v;                                                 \
1338                 mf->v3 = mloop[l3].v;                                                 \
1339                 mf->v4 = mloop[l4].v;                                                 \
1340                 lidx[0] = l1;                                                         \
1341                 lidx[1] = l2;                                                         \
1342                 lidx[2] = l3;                                                         \
1343                 lidx[3] = l4;                                                         \
1344                 mf->mat_nr = mp->mat_nr;                                              \
1345                 mf->flag = mp->flag;                                                  \
1346                 mf->edcode = TESSFACE_IS_QUAD;                                        \
1347                 (void)0
1348
1349
1350                 else if (mp_totloop == 3) {
1351                         ML_TO_MF(0, 1, 2);
1352                         mface_index++;
1353                 }
1354                 else if (mp_totloop == 4) {
1355 #ifdef USE_TESSFACE_QUADS
1356                         ML_TO_MF_QUAD();
1357                         mface_index++;
1358 #else
1359                         ML_TO_MF(0, 1, 2);
1360                         mface_index++;
1361                         ML_TO_MF(0, 2, 3);
1362                         mface_index++;
1363 #endif
1364                 }
1365 #endif /* USE_TESSFACE_SPEEDUP */
1366                 else {
1367                         const float *co_curr, *co_prev;
1368
1369                         float normal[3];
1370
1371                         float axis_mat[3][3];
1372                         float (*projverts)[2];
1373                         unsigned int (*tris)[3];
1374
1375                         const unsigned int totfilltri = mp_totloop - 2;
1376
1377                         if (UNLIKELY(arena == NULL)) {
1378                                 arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1379                         }
1380
1381                         tris = BLI_memarena_alloc(arena, sizeof(*tris) * (size_t)totfilltri);
1382                         projverts = BLI_memarena_alloc(arena, sizeof(*projverts) * (size_t)mp_totloop);
1383
1384                         zero_v3(normal);
1385
1386                         /* calc normal */
1387                         ml = mloop + mp_loopstart;
1388                         co_prev = mvert[ml[mp_totloop - 1].v].co;
1389                         for (j = 0; j < mp_totloop; j++, ml++) {
1390                                 co_curr = mvert[ml->v].co;
1391                                 add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
1392                                 co_prev = co_curr;
1393                         }
1394                         if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
1395                                 normal[2] = 1.0f;
1396                         }
1397
1398                         /* project verts to 2d */
1399                         axis_dominant_v3_to_m3(axis_mat, normal);
1400
1401                         ml = mloop + mp_loopstart;
1402                         for (j = 0; j < mp_totloop; j++, ml++) {
1403                                 mul_v2_m3v3(projverts[j], axis_mat, mvert[ml->v].co);
1404                         }
1405
1406                         BLI_polyfill_calc_arena((const float (*)[2])projverts, mp_totloop, tris, arena);
1407
1408                         /* apply fill */
1409                         for (j = 0; j < totfilltri; j++) {
1410                                 unsigned int *tri = tris[j];
1411                                 lidx = lindices[mface_index];
1412
1413                                 mface_to_poly_map[mface_index] = poly_index;
1414                                 mf = &mface[mface_index];
1415
1416                                 /* set loop indices, transformed to vert indices later */
1417                                 l1 = mp_loopstart + tri[0];
1418                                 l2 = mp_loopstart + tri[1];
1419                                 l3 = mp_loopstart + tri[2];
1420
1421                                 /* sort loop indices to ensure winding is correct */
1422                                 if (l1 > l2) SWAP(unsigned int, l1, l2);
1423                                 if (l2 > l3) SWAP(unsigned int, l2, l3);
1424                                 if (l1 > l2) SWAP(unsigned int, l1, l2);
1425
1426                                 mf->v1 = mloop[l1].v;
1427                                 mf->v2 = mloop[l2].v;
1428                                 mf->v3 = mloop[l3].v;
1429                                 mf->v4 = 0;
1430
1431                                 lidx[0] = l1;
1432                                 lidx[1] = l2;
1433                                 lidx[2] = l3;
1434                                 lidx[3] = 0;
1435
1436                                 mf->mat_nr = mp->mat_nr;
1437                                 mf->flag = mp->flag;
1438                                 mf->edcode = 0;
1439
1440                                 mface_index++;
1441                         }
1442
1443                         BLI_memarena_clear(arena);
1444                 }
1445         }
1446
1447         if (arena) {
1448                 BLI_memarena_free(arena);
1449                 arena = NULL;
1450         }
1451
1452         CustomData_free(fdata, totface);
1453         totface = mface_index;
1454
1455         BLI_assert(totface <= looptris_tot);
1456
1457         /* not essential but without this we store over-alloc'd memory in the CustomData layers */
1458         if (LIKELY(looptris_tot != totface)) {
1459                 mface = MEM_reallocN(mface, sizeof(*mface) * (size_t)totface);
1460                 mface_to_poly_map = MEM_reallocN(mface_to_poly_map, sizeof(*mface_to_poly_map) * (size_t)totface);
1461         }
1462
1463         CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
1464
1465         /* CD_ORIGINDEX will contain an array of indices from tessfaces to the polygons
1466          * they are directly tessellated from */
1467         CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, mface_to_poly_map, totface);
1468         CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
1469
1470         if (do_face_nor_cpy) {
1471                 /* If polys have a normals layer, copying that to faces can help
1472                  * avoid the need to recalculate normals later */
1473                 if (CustomData_has_layer(pdata, CD_NORMAL)) {
1474                         float (*pnors)[3] = CustomData_get_layer(pdata, CD_NORMAL);
1475                         float (*fnors)[3] = CustomData_add_layer(fdata, CD_NORMAL, CD_CALLOC, NULL, totface);
1476                         for (mface_index = 0; mface_index < totface; mface_index++) {
1477                                 copy_v3_v3(fnors[mface_index], pnors[mface_to_poly_map[mface_index]]);
1478                         }
1479                 }
1480         }
1481
1482         /* NOTE: quad detection issue - forth vertidx vs forth loopidx:
1483          * Polygons take care of their loops ordering, hence not of their vertices ordering.
1484          * Currently, our tfaces' forth vertex index might be 0 even for a quad. However, we know our forth loop index is
1485          * never 0 for quads (because they are sorted for polygons, and our quads are still mere copies of their polygons).
1486          * So we pass NULL as MFace pointer, and BKE_mesh_loops_to_tessdata will use the forth loop index as quad test.
1487          * ...
1488          */
1489         BKE_mesh_loops_to_tessdata(fdata, ldata, pdata, NULL, mface_to_poly_map, lindices, totface);
1490
1491         /* NOTE: quad detection issue - forth vertidx vs forth loopidx:
1492          * ...However, most TFace code uses 'MFace->v4 == 0' test to check whether it is a tri or quad.
1493          * test_index_face() will check this and rotate the tessellated face if needed.
1494          */
1495 #ifdef USE_TESSFACE_QUADS
1496         mf = mface;
1497         for (mface_index = 0; mface_index < totface; mface_index++, mf++) {
1498                 if (mf->edcode == TESSFACE_IS_QUAD) {
1499                         test_index_face(mf, fdata, mface_index, 4);
1500                         mf->edcode = 0;
1501                 }
1502         }
1503 #endif
1504
1505         MEM_freeN(lindices);
1506
1507         return totface;
1508
1509 #undef USE_TESSFACE_SPEEDUP
1510 #undef USE_TESSFACE_QUADS
1511
1512 #undef ML_TO_MF
1513 #undef ML_TO_MF_QUAD
1514
1515 }
1516
1517 #ifdef USE_BMESH_SAVE_AS_COMPAT
1518
1519 /**
1520  * This function recreates a tessellation.
1521  * returns number of tessellation faces.
1522  *
1523  * for forwards compat only quad->tri polys to mface, skip ngons.
1524  */
1525 int BKE_mesh_mpoly_to_mface(struct CustomData *fdata, struct CustomData *ldata,
1526                             struct CustomData *pdata, int totface, int UNUSED(totloop), int totpoly)
1527 {
1528         MLoop *mloop;
1529
1530         unsigned int lindex[4];
1531         int i;
1532         int k;
1533
1534         MPoly *mp, *mpoly;
1535         MFace *mface, *mf;
1536
1537         const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
1538         const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
1539         const bool hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
1540         const bool hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
1541         const bool hasLNor = CustomData_has_layer(ldata, CD_NORMAL);
1542
1543         /* over-alloc, ngons will be skipped */
1544         mface = MEM_mallocN(sizeof(*mface) * (size_t)totpoly, __func__);
1545
1546         mpoly = CustomData_get_layer(pdata, CD_MPOLY);
1547         mloop = CustomData_get_layer(ldata, CD_MLOOP);
1548
1549         mp = mpoly;
1550         k = 0;
1551         for (i = 0; i < totpoly; i++, mp++) {
1552                 if (ELEM(mp->totloop, 3, 4)) {
1553                         const unsigned int mp_loopstart = (unsigned int)mp->loopstart;
1554                         mf = &mface[k];
1555
1556                         mf->mat_nr = mp->mat_nr;
1557                         mf->flag = mp->flag;
1558
1559                         mf->v1 = mp_loopstart + 0;
1560                         mf->v2 = mp_loopstart + 1;
1561                         mf->v3 = mp_loopstart + 2;
1562                         mf->v4 = (mp->totloop == 4) ? (mp_loopstart + 3) : 0;
1563
1564                         /* abuse edcode for temp storage and clear next loop */
1565                         mf->edcode = (char)mp->totloop; /* only ever 3 or 4 */
1566
1567                         k++;
1568                 }
1569         }
1570
1571         CustomData_free(fdata, totface);
1572
1573         totface = k;
1574
1575         CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
1576
1577         CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
1578
1579         mp = mpoly;
1580         k = 0;
1581         for (i = 0; i < totpoly; i++, mp++) {
1582                 if (ELEM(mp->totloop, 3, 4)) {
1583                         mf = &mface[k];
1584
1585                         if (mf->edcode == 3) {
1586                                 /* sort loop indices to ensure winding is correct */
1587                                 /* NO SORT - looks like we can skip this */
1588
1589                                 lindex[0] = mf->v1;
1590                                 lindex[1] = mf->v2;
1591                                 lindex[2] = mf->v3;
1592                                 lindex[3] = 0; /* unused */
1593
1594                                 /* transform loop indices to vert indices */
1595                                 mf->v1 = mloop[mf->v1].v;
1596                                 mf->v2 = mloop[mf->v2].v;
1597                                 mf->v3 = mloop[mf->v3].v;
1598
1599                                 BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
1600                                                                 lindex, k, i, 3,
1601                                                                 numTex, numCol, hasPCol, hasOrigSpace, hasLNor);
1602                                 test_index_face(mf, fdata, k, 3);
1603                         }
1604                         else {
1605                                 /* sort loop indices to ensure winding is correct */
1606                                 /* NO SORT - looks like we can skip this */
1607
1608                                 lindex[0] = mf->v1;
1609                                 lindex[1] = mf->v2;
1610                                 lindex[2] = mf->v3;
1611                                 lindex[3] = mf->v4;
1612
1613                                 /* transform loop indices to vert indices */
1614                                 mf->v1 = mloop[mf->v1].v;
1615                                 mf->v2 = mloop[mf->v2].v;
1616                                 mf->v3 = mloop[mf->v3].v;
1617                                 mf->v4 = mloop[mf->v4].v;
1618
1619                                 BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
1620                                                                 lindex, k, i, 4,
1621                                                                 numTex, numCol, hasPCol, hasOrigSpace, hasLNor);
1622                                 test_index_face(mf, fdata, k, 4);
1623                         }
1624
1625                         mf->edcode = 0;
1626
1627                         k++;
1628                 }
1629         }
1630
1631         return k;
1632 }
1633 #endif /* USE_BMESH_SAVE_AS_COMPAT */
1634
1635
1636 static void bm_corners_to_loops_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
1637                                    MFace *mface, int totloop, int findex, int loopstart, int numTex, int numCol)
1638 {
1639         MTFace *texface;
1640         MTexPoly *texpoly;
1641         MCol *mcol;
1642         MLoopCol *mloopcol;
1643         MLoopUV *mloopuv;
1644         MFace *mf;
1645         int i;
1646
1647         mf = mface + findex;
1648
1649         for (i = 0; i < numTex; i++) {
1650                 texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
1651                 texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, findex, i);
1652
1653                 ME_MTEXFACE_CPY(texpoly, texface);
1654
1655                 mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, loopstart, i);
1656                 copy_v2_v2(mloopuv->uv, texface->uv[0]); mloopuv++;
1657                 copy_v2_v2(mloopuv->uv, texface->uv[1]); mloopuv++;
1658                 copy_v2_v2(mloopuv->uv, texface->uv[2]); mloopuv++;
1659
1660                 if (mf->v4) {
1661                         copy_v2_v2(mloopuv->uv, texface->uv[3]); mloopuv++;
1662                 }
1663         }
1664
1665         for (i = 0; i < numCol; i++) {
1666                 mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, loopstart, i);
1667                 mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
1668
1669                 MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[0]); mloopcol++;
1670                 MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[1]); mloopcol++;
1671                 MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[2]); mloopcol++;
1672                 if (mf->v4) {
1673                         MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[3]); mloopcol++;
1674                 }
1675         }
1676
1677         if (CustomData_has_layer(fdata, CD_TESSLOOPNORMAL)) {
1678                 float (*lnors)[3] = CustomData_get(ldata, loopstart, CD_NORMAL);
1679                 short (*tlnors)[3] = CustomData_get(fdata, findex, CD_TESSLOOPNORMAL);
1680                 const int max = mf->v4 ? 4 : 3;
1681
1682                 for (i = 0; i < max; i++, lnors++, tlnors++) {
1683                         normal_short_to_float_v3(*lnors, *tlnors);
1684                 }
1685         }
1686
1687         if (CustomData_has_layer(fdata, CD_MDISPS)) {
1688                 MDisps *ld = CustomData_get(ldata, loopstart, CD_MDISPS);
1689                 MDisps *fd = CustomData_get(fdata, findex, CD_MDISPS);
1690                 float (*disps)[3] = fd->disps;
1691                 int tot = mf->v4 ? 4 : 3;
1692                 int corners;
1693
1694                 if (CustomData_external_test(fdata, CD_MDISPS)) {
1695                         if (id && fdata->external) {
1696                                 CustomData_external_add(ldata, id, CD_MDISPS,
1697                                                         totloop, fdata->external->filename);
1698                         }
1699                 }
1700
1701                 corners = multires_mdisp_corners(fd);
1702
1703                 if (corners == 0) {
1704                         /* Empty MDisp layers appear in at least one of the sintel.blend files.
1705                          * Not sure why this happens, but it seems fine to just ignore them here.
1706                          * If (corners == 0) for a non-empty layer though, something went wrong. */
1707                         BLI_assert(fd->totdisp == 0);
1708                 }
1709                 else {
1710                         const int side = (int)sqrtf((float)(fd->totdisp / corners));
1711                         const int side_sq = side * side;
1712                         const size_t disps_size = sizeof(float[3]) * (size_t)side_sq;
1713
1714                         for (i = 0; i < tot; i++, disps += side_sq, ld++) {
1715                                 ld->totdisp = side_sq;
1716                                 ld->level = (int)(logf((float)side - 1.0f) / (float)M_LN2) + 1;
1717
1718                                 if (ld->disps)
1719                                         MEM_freeN(ld->disps);
1720
1721                                 ld->disps = MEM_mallocN(disps_size, "converted loop mdisps");
1722                                 if (fd->disps) {
1723                                         memcpy(ld->disps, disps, disps_size);
1724                                 }
1725                                 else {
1726                                         memset(ld->disps, 0, disps_size);
1727                                 }
1728                         }
1729                 }
1730         }
1731 }
1732
1733
1734 void BKE_mesh_convert_mfaces_to_mpolys(Mesh *mesh)
1735 {
1736         BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
1737                                              mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
1738                                              mesh->medge, mesh->mface,
1739                                              &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
1740
1741         BKE_mesh_update_customdata_pointers(mesh, true);
1742 }
1743
1744 /* the same as BKE_mesh_convert_mfaces_to_mpolys but oriented to be used in do_versions from readfile.c
1745  * the difference is how active/render/clone/stencil indices are handled here
1746  *
1747  * normally thay're being set from pdata which totally makes sense for meshes which are already
1748  * converted to bmesh structures, but when loading older files indices shall be updated in other
1749  * way around, so newly added pdata and ldata would have this indices set based on fdata layer
1750  *
1751  * this is normally only needed when reading older files, in all other cases BKE_mesh_convert_mfaces_to_mpolys
1752  * shall be always used
1753  */
1754 void BKE_mesh_do_versions_convert_mfaces_to_mpolys(Mesh *mesh)
1755 {
1756         BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
1757                                              mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
1758                                              mesh->medge, mesh->mface,
1759                                              &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
1760
1761         CustomData_bmesh_do_versions_update_active_layers(&mesh->fdata, &mesh->pdata, &mesh->ldata);
1762
1763         BKE_mesh_update_customdata_pointers(mesh, true);
1764 }
1765
1766 void BKE_mesh_convert_mfaces_to_mpolys_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
1767                                           int totedge_i, int totface_i, int totloop_i, int totpoly_i,
1768                                           MEdge *medge, MFace *mface,
1769                                           int *r_totloop, int *r_totpoly,
1770                                           MLoop **r_mloop, MPoly **r_mpoly)
1771 {
1772         MFace *mf;
1773         MLoop *ml, *mloop;
1774         MPoly *mp, *mpoly;
1775         MEdge *me;
1776         EdgeHash *eh;
1777         int numTex, numCol;
1778         int i, j, totloop, totpoly, *polyindex;
1779
1780         /* old flag, clear to allow for reuse */
1781 #define ME_FGON (1 << 3)
1782
1783         /* just in case some of these layers are filled in (can happen with python created meshes) */
1784         CustomData_free(ldata, totloop_i);
1785         CustomData_free(pdata, totpoly_i);
1786
1787         totpoly = totface_i;
1788         mpoly = MEM_callocN(sizeof(MPoly) * (size_t)totpoly, "mpoly converted");
1789         CustomData_add_layer(pdata, CD_MPOLY, CD_ASSIGN, mpoly, totpoly);
1790
1791         numTex = CustomData_number_of_layers(fdata, CD_MTFACE);
1792         numCol = CustomData_number_of_layers(fdata, CD_MCOL);
1793
1794         totloop = 0;
1795         mf = mface;
1796         for (i = 0; i < totface_i; i++, mf++) {
1797                 totloop += mf->v4 ? 4 : 3;
1798         }
1799
1800         mloop = MEM_callocN(sizeof(MLoop) * (size_t)totloop, "mloop converted");
1801
1802         CustomData_add_layer(ldata, CD_MLOOP, CD_ASSIGN, mloop, totloop);
1803
1804         CustomData_to_bmeshpoly(fdata, pdata, ldata, totloop, totpoly);
1805
1806         if (id) {
1807                 /* ensure external data is transferred */
1808                 CustomData_external_read(fdata, id, CD_MASK_MDISPS, totface_i);
1809         }
1810
1811         eh = BLI_edgehash_new_ex(__func__, (unsigned int)totedge_i);
1812
1813         /* build edge hash */
1814         me = medge;
1815         for (i = 0; i < totedge_i; i++, me++) {
1816                 BLI_edgehash_insert(eh, me->v1, me->v2, SET_UINT_IN_POINTER(i));
1817
1818                 /* unrelated but avoid having the FGON flag enabled, so we can reuse it later for something else */
1819                 me->flag &= ~ME_FGON;
1820         }
1821
1822         polyindex = CustomData_get_layer(fdata, CD_ORIGINDEX);
1823
1824         j = 0; /* current loop index */
1825         ml = mloop;
1826         mf = mface;
1827         mp = mpoly;
1828         for (i = 0; i < totface_i; i++, mf++, mp++) {
1829                 mp->loopstart = j;
1830
1831                 mp->totloop = mf->v4 ? 4 : 3;
1832
1833                 mp->mat_nr = mf->mat_nr;
1834                 mp->flag = mf->flag;
1835
1836 #       define ML(v1, v2) { \
1837                         ml->v = mf->v1; \
1838                         ml->e = GET_UINT_FROM_POINTER(BLI_edgehash_lookup(eh, mf->v1, mf->v2)); \
1839                         ml++; j++; \
1840                 } (void)0
1841
1842                 ML(v1, v2);
1843                 ML(v2, v3);
1844                 if (mf->v4) {
1845                         ML(v3, v4);
1846                         ML(v4, v1);
1847                 }
1848                 else {
1849                         ML(v3, v1);
1850                 }
1851
1852 #       undef ML
1853
1854                 bm_corners_to_loops_ex(id, fdata, ldata, pdata, mface, totloop, i, mp->loopstart, numTex, numCol);
1855
1856                 if (polyindex) {
1857                         *polyindex = i;
1858                         polyindex++;
1859                 }
1860         }
1861
1862         /* note, we don't convert NGons at all, these are not even real ngons,
1863          * they have their own UV's, colors etc - its more an editing feature. */
1864
1865         BLI_edgehash_free(eh, NULL);
1866
1867         *r_totpoly = totpoly;
1868         *r_totloop = totloop;
1869         *r_mpoly = mpoly;
1870         *r_mloop = mloop;
1871
1872 #undef ME_FGON
1873
1874 }
1875 /** \} */
1876
1877
1878 /* -------------------------------------------------------------------- */
1879
1880 /** \name Mesh Flag Flushing
1881  * \{ */
1882
1883 /* update the hide flag for edges and faces from the corresponding
1884  * flag in verts */
1885 void BKE_mesh_flush_hidden_from_verts_ex(const MVert *mvert,
1886                                          const MLoop *mloop,
1887                                          MEdge *medge, const int totedge,
1888                                          MPoly *mpoly, const int totpoly)
1889 {
1890         int i, j;
1891
1892         for (i = 0; i < totedge; i++) {
1893                 MEdge *e = &medge[i];
1894                 if (mvert[e->v1].flag & ME_HIDE ||
1895                     mvert[e->v2].flag & ME_HIDE)
1896                 {
1897                         e->flag |= ME_HIDE;
1898                 }
1899                 else {
1900                         e->flag &= ~ME_HIDE;
1901                 }
1902         }
1903         for (i = 0; i < totpoly; i++) {
1904                 MPoly *p = &mpoly[i];
1905                 p->flag &= (char)~ME_HIDE;
1906                 for (j = 0; j < p->totloop; j++) {
1907                         if (mvert[mloop[p->loopstart + j].v].flag & ME_HIDE)
1908                                 p->flag |= ME_HIDE;
1909                 }
1910         }
1911 }
1912 void BKE_mesh_flush_hidden_from_verts(Mesh *me)
1913 {
1914         BKE_mesh_flush_hidden_from_verts_ex(me->mvert, me->mloop,
1915                                             me->medge, me->totedge,
1916                                             me->mpoly, me->totpoly);
1917 }
1918
1919 void BKE_mesh_flush_hidden_from_polys_ex(MVert *mvert,
1920                                          const MLoop *mloop,
1921                                          MEdge *medge, const int UNUSED(totedge),
1922                                          const MPoly *mpoly, const int totpoly)
1923 {
1924         const MPoly *mp;
1925         int i;
1926
1927         i = totpoly;
1928         for (mp = mpoly; i--; mp++) {
1929                 if (mp->flag & ME_HIDE) {
1930                         const MLoop *ml;
1931                         int j;
1932                         j = mp->totloop;
1933                         for (ml = &mloop[mp->loopstart]; j--; ml++) {
1934                                 mvert[ml->v].flag |= ME_HIDE;
1935                                 medge[ml->e].flag |= ME_HIDE;
1936                         }
1937                 }
1938         }
1939
1940         i = totpoly;
1941         for (mp = mpoly; i--; mp++) {
1942                 if ((mp->flag & ME_HIDE) == 0) {
1943                         const MLoop *ml;
1944                         int j;
1945                         j = mp->totloop;
1946                         for (ml = &mloop[mp->loopstart]; j--; ml++) {
1947                                 mvert[ml->v].flag &= (char)~ME_HIDE;
1948                                 medge[ml->e].flag &= (char)~ME_HIDE;
1949                         }
1950                 }
1951         }
1952 }
1953 void BKE_mesh_flush_hidden_from_polys(Mesh *me)
1954 {
1955         BKE_mesh_flush_hidden_from_polys_ex(me->mvert, me->mloop,
1956                                             me->medge, me->totedge,
1957                                             me->mpoly, me->totpoly);
1958 }
1959
1960 /**
1961  * simple poly -> vert/edge selection.
1962  */
1963 void BKE_mesh_flush_select_from_polys_ex(MVert *mvert,       const int totvert,
1964                                          const MLoop *mloop,
1965                                          MEdge *medge,       const int totedge,
1966                                          const MPoly *mpoly, const int totpoly)
1967 {
1968         MVert *mv;
1969         MEdge *med;
1970         const MPoly *mp;
1971         int i;
1972
1973         i = totvert;
1974         for (mv = mvert; i--; mv++) {
1975                 mv->flag &= (char)~SELECT;
1976         }
1977
1978         i = totedge;
1979         for (med = medge; i--; med++) {
1980                 med->flag &= ~SELECT;
1981         }
1982
1983         i = totpoly;
1984         for (mp = mpoly; i--; mp++) {
1985                 /* assume if its selected its not hidden and none of its verts/edges are hidden
1986                  * (a common assumption)*/
1987                 if (mp->flag & ME_FACE_SEL) {
1988                         const MLoop *ml;
1989                         int j;
1990                         j = mp->totloop;
1991                         for (ml = &mloop[mp->loopstart]; j--; ml++) {
1992                                 mvert[ml->v].flag |= SELECT;
1993                                 medge[ml->e].flag |= SELECT;
1994                         }
1995                 }
1996         }
1997 }
1998 void BKE_mesh_flush_select_from_polys(Mesh *me)
1999 {
2000         BKE_mesh_flush_select_from_polys_ex(me->mvert, me->totvert,
2001                                          me->mloop,
2002                                          me->medge, me->totedge,
2003                                          me->mpoly, me->totpoly);
2004 }
2005
2006 void BKE_mesh_flush_select_from_verts_ex(const MVert *mvert, const int UNUSED(totvert),
2007                                          const MLoop *mloop,
2008                                          MEdge *medge,       const int totedge,
2009                                          MPoly *mpoly,       const int totpoly)
2010 {
2011         MEdge *med;
2012         MPoly *mp;
2013         int i;
2014
2015         /* edges */
2016         i = totedge;
2017         for (med = medge; i--; med++) {
2018                 if ((med->flag & ME_HIDE) == 0) {
2019                         if ((mvert[med->v1].flag & SELECT) && (mvert[med->v2].flag & SELECT)) {
2020                                 med->flag |= SELECT;
2021                         }
2022                         else {
2023                                 med->flag &= ~SELECT;
2024                         }
2025                 }
2026         }
2027
2028         /* polys */
2029         i = totpoly;
2030         for (mp = mpoly; i--; mp++) {
2031                 if ((mp->flag & ME_HIDE) == 0) {
2032                         bool ok = true;
2033                         const MLoop *ml;
2034                         int j;
2035                         j = mp->totloop;
2036                         for (ml = &mloop[mp->loopstart]; j--; ml++) {
2037                                 if ((mvert[ml->v].flag & SELECT) == 0) {
2038                                         ok = false;
2039                                         break;
2040                                 }
2041                         }
2042
2043                         if (ok) {
2044                                 mp->flag |= ME_FACE_SEL;
2045                         }
2046                         else {
2047                                 mp->flag &= (char)~ME_FACE_SEL;
2048                         }
2049                 }
2050         }
2051 }
2052 void BKE_mesh_flush_select_from_verts(Mesh *me)
2053 {
2054         BKE_mesh_flush_select_from_verts_ex(me->mvert, me->totvert,
2055                                             me->mloop,
2056                                             me->medge, me->totedge,
2057                                             me->mpoly, me->totpoly);
2058 }
2059 /** \} */
2060
2061 /* -------------------------------------------------------------------- */
2062
2063 /** \name Mesh Spatial Calculation
2064  * \{ */
2065
2066 /**
2067  * This function takes the difference between 2 vertex-coord-arrays
2068  * (\a vert_cos_src, \a vert_cos_dst),
2069  * and applies the difference to \a vert_cos_new relative to \a vert_cos_org.
2070  *
2071  * \param vert_cos_src reference deform source.
2072  * \param vert_cos_dst reference deform destination.
2073  *
2074  * \param vert_cos_org reference for the output location.
2075  * \param vert_cos_new resulting coords.
2076  */
2077 void BKE_mesh_calc_relative_deform(
2078         const MPoly *mpoly, const int totpoly,
2079         const MLoop *mloop, const int totvert,
2080
2081         const float (*vert_cos_src)[3],
2082         const float (*vert_cos_dst)[3],
2083
2084         const float (*vert_cos_org)[3],
2085               float (*vert_cos_new)[3])
2086 {
2087         const MPoly *mp;
2088         int i;
2089
2090         int *vert_accum = MEM_callocN(sizeof(*vert_accum) * (size_t)totvert, __func__);
2091
2092         memset(vert_cos_new, '\0', sizeof(*vert_cos_new) * (size_t)totvert);
2093
2094         for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
2095                 const MLoop *loopstart = mloop + mp->loopstart;
2096                 int j;
2097
2098                 for (j = 0; j < mp->totloop; j++) {
2099                         unsigned int v_prev = loopstart[(mp->totloop + (j - 1)) % mp->totloop].v;
2100                         unsigned int v_curr = loopstart[j].v;
2101                         unsigned int v_next = loopstart[(j + 1) % mp->totloop].v;
2102
2103                         float tvec[3];
2104
2105                         barycentric_transform(
2106                                     tvec, vert_cos_dst[v_curr],
2107                                     vert_cos_org[v_prev], vert_cos_org[v_curr], vert_cos_org[v_next],
2108                                     vert_cos_src[v_prev], vert_cos_src[v_curr], vert_cos_src[v_next]
2109                                     );
2110
2111                         add_v3_v3(vert_cos_new[v_curr], tvec);
2112                         vert_accum[v_curr] += 1;
2113                 }
2114         }
2115
2116         for (i = 0; i < totvert; i++) {
2117                 if (vert_accum[i]) {
2118                         mul_v3_fl(vert_cos_new[i], 1.0f / (float)vert_accum[i]);
2119                 }
2120                 else {
2121                         copy_v3_v3(vert_cos_new[i], vert_cos_org[i]);
2122                 }
2123         }
2124
2125         MEM_freeN(vert_accum);
2126 }
2127 /** \} */