Code cleanup: use r_ prefix for return args
[blender.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 /** \name Mesh Tangent Calculations
583  * \{ */
584
585 /* Tangent space utils. */
586
587 /* User data. */
588 typedef struct {
589         MPoly *mpolys;         /* faces */
590         MLoop *mloops;         /* faces's vertices */
591         MVert *mverts;         /* vertices */
592         MLoopUV *luvs;         /* texture coordinates */
593         float (*lnors)[3];     /* loops' normals */
594         float (*tangents)[4];  /* output tangents */
595         int num_polys;         /* number of polygons */
596 } BKEMeshToTangent;
597
598 /* Mikktspace's API */
599 static int get_num_faces(const SMikkTSpaceContext *pContext)
600 {
601         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
602         return p_mesh->num_polys;
603 }
604
605 static int get_num_verts_of_face(const SMikkTSpaceContext *pContext, const int face_idx)
606 {
607         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
608         return p_mesh->mpolys[face_idx].totloop;
609 }
610
611 static void get_position(const SMikkTSpaceContext *pContext, float r_co[3], const int face_idx, const int vert_idx)
612 {
613         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
614         const int loop_idx = p_mesh->mpolys[face_idx].loopstart + vert_idx;
615         copy_v3_v3(r_co, p_mesh->mverts[p_mesh->mloops[loop_idx].v].co);
616 }
617
618 static void get_texture_coordinate(const SMikkTSpaceContext *pContext, float r_uv[2], const int face_idx,
619                                    const int vert_idx)
620 {
621         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
622         copy_v2_v2(r_uv, p_mesh->luvs[p_mesh->mpolys[face_idx].loopstart + vert_idx].uv);
623 }
624
625 static void get_normal(const SMikkTSpaceContext *pContext, float r_no[3], const int face_idx, const int vert_idx)
626 {
627         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
628         copy_v3_v3(r_no, p_mesh->lnors[p_mesh->mpolys[face_idx].loopstart + vert_idx]);
629 }
630
631 static void set_tspace(const SMikkTSpaceContext *pContext, const float fv_tangent[3], const float face_sign,
632                        const int face_idx, const int vert_idx)
633 {
634         BKEMeshToTangent *p_mesh = (BKEMeshToTangent *)pContext->m_pUserData;
635         float *p_res = p_mesh->tangents[p_mesh->mpolys[face_idx].loopstart + vert_idx];
636         copy_v3_v3(p_res, fv_tangent);
637         p_res[3] = face_sign;
638 }
639
640 /**
641  * Compute simplified tangent space normals, i.e. tangent vector + sign of bi-tangent one, which combined with
642  * split normals can be used to recreate the full tangent space.
643  * Note: * The mesh should be made of only tris and quads!
644  */
645 void BKE_mesh_loop_tangents_ex(MVert *mverts, const int UNUSED(numVerts), MLoop *mloops,
646                                float (*r_looptangent)[4], float (*loopnors)[3], MLoopUV *loopuvs,
647                                const int UNUSED(numLoops), MPoly *mpolys, const int numPolys, ReportList *reports)
648 {
649         BKEMeshToTangent mesh_to_tangent = {NULL};
650         SMikkTSpaceContext s_context = {NULL};
651         SMikkTSpaceInterface s_interface = {NULL};
652
653         MPoly *mp;
654         int mp_index;
655
656         /* First check we do have a tris/quads only mesh. */
657         for (mp = mpolys, mp_index = 0; mp_index < numPolys; mp++, mp_index++) {
658                 if (mp->totloop > 4) {
659                         BKE_report(reports, RPT_ERROR, "Tangent space can only be computed for tris/quads, aborting");
660                         return;
661                 }
662         }
663
664         /* Compute Mikktspace's tangent normals. */
665         mesh_to_tangent.mpolys = mpolys;
666         mesh_to_tangent.mloops = mloops;
667         mesh_to_tangent.mverts = mverts;
668         mesh_to_tangent.luvs = loopuvs;
669         mesh_to_tangent.lnors = loopnors;
670         mesh_to_tangent.tangents = r_looptangent;
671         mesh_to_tangent.num_polys = numPolys;
672
673         s_context.m_pUserData = &mesh_to_tangent;
674         s_context.m_pInterface = &s_interface;
675         s_interface.m_getNumFaces = get_num_faces;
676         s_interface.m_getNumVerticesOfFace = get_num_verts_of_face;
677         s_interface.m_getPosition = get_position;
678         s_interface.m_getTexCoord = get_texture_coordinate;
679         s_interface.m_getNormal = get_normal;
680         s_interface.m_setTSpaceBasic = set_tspace;
681
682         /* 0 if failed */
683         if (genTangSpaceDefault(&s_context) == false) {
684                 BKE_report(reports, RPT_ERROR, "Mikktspace failed to generate tangents for this mesh!");
685         }
686 }
687
688 /**
689  * Wrapper around BKE_mesh_loop_tangents_ex, which takes care of most boiling code.
690  * Note: * There must be a valid loop's CD_NORMALS available.
691  *       * The mesh should be made of only tris and quads!
692  */
693 void BKE_mesh_loop_tangents(Mesh *mesh, const char *uvmap, float (*r_looptangents)[4], ReportList *reports)
694 {
695         MLoopUV *loopuvs;
696         float (*loopnors)[3];
697
698         /* Check we have valid texture coordinates first! */
699         if (uvmap) {
700                 loopuvs = CustomData_get_layer_named(&mesh->ldata, CD_MLOOPUV, uvmap);
701         }
702         else {
703                 loopuvs = CustomData_get_layer(&mesh->ldata, CD_MLOOPUV);
704         }
705         if (!loopuvs) {
706                 BKE_reportf(reports, RPT_ERROR, "Tangent space computation needs an UVMap, \"%s\" not found, aborting", uvmap);
707                 return;
708         }
709
710         loopnors = CustomData_get_layer(&mesh->ldata, CD_NORMAL);
711         if (!loopnors) {
712                 BKE_report(reports, RPT_ERROR, "Tangent space computation needs loop normals, none found, aborting");
713                 return;
714         }
715
716         BKE_mesh_loop_tangents_ex(mesh->mvert, mesh->totvert, mesh->mloop, r_looptangents,
717                               loopnors, loopuvs, mesh->totloop, mesh->mpoly, mesh->totpoly, reports);
718 }
719
720 /** \} */
721
722
723 /* -------------------------------------------------------------------- */
724
725 /** \name Polygon Calculations
726  * \{ */
727
728 /*
729  * COMPUTE POLY NORMAL
730  *
731  * Computes the normal of a planar
732  * polygon See Graphics Gems for
733  * computing newell normal.
734  *
735  */
736 static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart,
737                                   MVert *mvert, float normal[3])
738 {
739         const int nverts = mpoly->totloop;
740         float const *v_prev = mvert[loopstart[nverts - 1].v].co;
741         float const *v_curr;
742         int i;
743
744         zero_v3(normal);
745
746         /* Newell's Method */
747         for (i = 0; i < nverts; i++) {
748                 v_curr = mvert[loopstart[i].v].co;
749                 add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
750                 v_prev = v_curr;
751         }
752
753         if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
754                 normal[2] = 1.0f; /* other axis set to 0.0 */
755         }
756 }
757
758 void BKE_mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart,
759                                MVert *mvarray, float no[3])
760 {
761         if (mpoly->totloop > 4) {
762                 mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no);
763         }
764         else if (mpoly->totloop == 3) {
765                 normal_tri_v3(no,
766                               mvarray[loopstart[0].v].co,
767                               mvarray[loopstart[1].v].co,
768                               mvarray[loopstart[2].v].co
769                               );
770         }
771         else if (mpoly->totloop == 4) {
772                 normal_quad_v3(no,
773                                mvarray[loopstart[0].v].co,
774                                mvarray[loopstart[1].v].co,
775                                mvarray[loopstart[2].v].co,
776                                mvarray[loopstart[3].v].co
777                                );
778         }
779         else { /* horrible, two sided face! */
780                 no[0] = 0.0;
781                 no[1] = 0.0;
782                 no[2] = 1.0;
783         }
784 }
785 /* duplicate of function above _but_ takes coords rather then mverts */
786 static void mesh_calc_ngon_normal_coords(MPoly *mpoly, MLoop *loopstart,
787                                          const float (*vertex_coords)[3], float normal[3])
788 {
789         const int nverts = mpoly->totloop;
790         float const *v_prev = vertex_coords[loopstart[nverts - 1].v];
791         float const *v_curr;
792         int i;
793
794         zero_v3(normal);
795
796         /* Newell's Method */
797         for (i = 0; i < nverts; i++) {
798                 v_curr = vertex_coords[loopstart[i].v];
799                 add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
800                 v_prev = v_curr;
801         }
802
803         if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
804                 normal[2] = 1.0f; /* other axis set to 0.0 */
805         }
806 }
807
808 void BKE_mesh_calc_poly_normal_coords(MPoly *mpoly, MLoop *loopstart,
809                                       const float (*vertex_coords)[3], float no[3])
810 {
811         if (mpoly->totloop > 4) {
812                 mesh_calc_ngon_normal_coords(mpoly, loopstart, vertex_coords, no);
813         }
814         else if (mpoly->totloop == 3) {
815                 normal_tri_v3(no,
816                               vertex_coords[loopstart[0].v],
817                               vertex_coords[loopstart[1].v],
818                               vertex_coords[loopstart[2].v]
819                               );
820         }
821         else if (mpoly->totloop == 4) {
822                 normal_quad_v3(no,
823                                vertex_coords[loopstart[0].v],
824                                vertex_coords[loopstart[1].v],
825                                vertex_coords[loopstart[2].v],
826                                vertex_coords[loopstart[3].v]
827                                );
828         }
829         else { /* horrible, two sided face! */
830                 no[0] = 0.0;
831                 no[1] = 0.0;
832                 no[2] = 1.0;
833         }
834 }
835
836 static void mesh_calc_ngon_center(MPoly *mpoly, MLoop *loopstart,
837                                   MVert *mvert, float cent[3])
838 {
839         const float w = 1.0f / (float)mpoly->totloop;
840         int i;
841
842         zero_v3(cent);
843
844         for (i = 0; i < mpoly->totloop; i++) {
845                 madd_v3_v3fl(cent, mvert[(loopstart++)->v].co, w);
846         }
847 }
848
849 void BKE_mesh_calc_poly_center(MPoly *mpoly, MLoop *loopstart,
850                                MVert *mvarray, float cent[3])
851 {
852         if (mpoly->totloop == 3) {
853                 cent_tri_v3(cent,
854                             mvarray[loopstart[0].v].co,
855                             mvarray[loopstart[1].v].co,
856                             mvarray[loopstart[2].v].co
857                             );
858         }
859         else if (mpoly->totloop == 4) {
860                 cent_quad_v3(cent,
861                              mvarray[loopstart[0].v].co,
862                              mvarray[loopstart[1].v].co,
863                              mvarray[loopstart[2].v].co,
864                              mvarray[loopstart[3].v].co
865                              );
866         }
867         else {
868                 mesh_calc_ngon_center(mpoly, loopstart, mvarray, cent);
869         }
870 }
871
872 /* note, passing polynormal is only a speedup so we can skip calculating it */
873 float BKE_mesh_calc_poly_area(MPoly *mpoly, MLoop *loopstart,
874                               MVert *mvarray, const float polynormal[3])
875 {
876         if (mpoly->totloop == 3) {
877                 return area_tri_v3(mvarray[loopstart[0].v].co,
878                                    mvarray[loopstart[1].v].co,
879                                    mvarray[loopstart[2].v].co
880                                    );
881         }
882         else if (mpoly->totloop == 4) {
883                 return area_quad_v3(mvarray[loopstart[0].v].co,
884                                     mvarray[loopstart[1].v].co,
885                                     mvarray[loopstart[2].v].co,
886                                     mvarray[loopstart[3].v].co
887                                     );
888         }
889         else {
890                 int i;
891                 MLoop *l_iter = loopstart;
892                 float area, polynorm_local[3];
893                 float (*vertexcos)[3] = BLI_array_alloca(vertexcos, (size_t)mpoly->totloop);
894                 const float *no = polynormal ? polynormal : polynorm_local;
895
896                 /* pack vertex cos into an array for area_poly_v3 */
897                 for (i = 0; i < mpoly->totloop; i++, l_iter++) {
898                         copy_v3_v3(vertexcos[i], mvarray[l_iter->v].co);
899                 }
900
901                 /* need normal for area_poly_v3 as well */
902                 if (polynormal == NULL) {
903                         BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, polynorm_local);
904                 }
905
906                 /* finally calculate the area */
907                 area = area_poly_v3(mpoly->totloop, vertexcos, no);
908
909                 return area;
910         }
911 }
912
913 /* note, results won't be correct if polygon is non-planar */
914 static float mesh_calc_poly_planar_area_centroid(MPoly *mpoly, MLoop *loopstart, MVert *mvarray, float cent[3])
915 {
916         int i;
917         float tri_area;
918         float total_area = 0.0f;
919         float v1[3], v2[3], v3[3], normal[3], tri_cent[3];
920
921         BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, normal);
922         copy_v3_v3(v1, mvarray[loopstart[0].v].co);
923         copy_v3_v3(v2, mvarray[loopstart[1].v].co);
924         zero_v3(cent);
925
926         for (i = 2; i < mpoly->totloop; i++) {
927                 copy_v3_v3(v3, mvarray[loopstart[i].v].co);
928
929                 tri_area = area_tri_signed_v3(v1, v2, v3, normal);
930                 total_area += tri_area;
931
932                 cent_tri_v3(tri_cent, v1, v2, v3);
933                 madd_v3_v3fl(cent, tri_cent, tri_area);
934
935                 copy_v3_v3(v2, v3);
936         }
937
938         mul_v3_fl(cent, 1.0f / total_area);
939
940         return total_area;
941 }
942
943 #if 0 /* slow version of the function below */
944 void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart,
945                                MVert *mvarray, float angles[])
946 {
947         MLoop *ml;
948         MLoop *mloop = &loopstart[-mpoly->loopstart];
949
950         int j;
951         for (j = 0, ml = loopstart; j < mpoly->totloop; j++, ml++) {
952                 MLoop *ml_prev = ME_POLY_LOOP_PREV(mloop, mpoly, j);
953                 MLoop *ml_next = ME_POLY_LOOP_NEXT(mloop, mpoly, j);
954
955                 float e1[3], e2[3];
956
957                 sub_v3_v3v3(e1, mvarray[ml_next->v].co, mvarray[ml->v].co);
958                 sub_v3_v3v3(e2, mvarray[ml_prev->v].co, mvarray[ml->v].co);
959
960                 angles[j] = (float)M_PI - angle_v3v3(e1, e2);
961         }
962 }
963
964 #else /* equivalent the function above but avoid multiple subtractions + normalize */
965
966 void BKE_mesh_calc_poly_angles(MPoly *mpoly, MLoop *loopstart,
967                                MVert *mvarray, float angles[])
968 {
969         float nor_prev[3];
970         float nor_next[3];
971
972         int i_this = mpoly->totloop - 1;
973         int i_next = 0;
974
975         sub_v3_v3v3(nor_prev, mvarray[loopstart[i_this - 1].v].co, mvarray[loopstart[i_this].v].co);
976         normalize_v3(nor_prev);
977
978         while (i_next < mpoly->totloop) {
979                 sub_v3_v3v3(nor_next, mvarray[loopstart[i_this].v].co, mvarray[loopstart[i_next].v].co);
980                 normalize_v3(nor_next);
981                 angles[i_this] = angle_normalized_v3v3(nor_prev, nor_next);
982
983                 /* step */
984                 copy_v3_v3(nor_prev, nor_next);
985                 i_this = i_next;
986                 i_next++;
987         }
988 }
989 #endif
990
991 void BKE_mesh_poly_edgehash_insert(EdgeHash *ehash, const MPoly *mp, const MLoop *mloop)
992 {
993         const MLoop *ml, *ml_next;
994         int i = mp->totloop;
995
996         ml_next = mloop;       /* first loop */
997         ml = &ml_next[i - 1];  /* last loop */
998
999         while (i-- != 0) {
1000                 BLI_edgehash_reinsert(ehash, ml->v, ml_next->v, NULL);
1001
1002                 ml = ml_next;
1003                 ml_next++;
1004         }
1005 }
1006
1007 void BKE_mesh_poly_edgebitmap_insert(unsigned int *edge_bitmap, const MPoly *mp, const MLoop *mloop)
1008 {
1009         const MLoop *ml;
1010         int i = mp->totloop;
1011
1012         ml = mloop;
1013
1014         while (i-- != 0) {
1015                 BLI_BITMAP_SET(edge_bitmap, ml->e);
1016                 ml++;
1017         }
1018 }
1019
1020 /** \} */
1021
1022
1023 /* -------------------------------------------------------------------- */
1024
1025 /** \name Mesh Center Calculation
1026  * \{ */
1027
1028 bool BKE_mesh_center_median(Mesh *me, float cent[3])
1029 {
1030         int i = me->totvert;
1031         MVert *mvert;
1032         zero_v3(cent);
1033         for (mvert = me->mvert; i--; mvert++) {
1034                 add_v3_v3(cent, mvert->co);
1035         }
1036         /* otherwise we get NAN for 0 verts */
1037         if (me->totvert) {
1038                 mul_v3_fl(cent, 1.0f / (float)me->totvert);
1039         }
1040
1041         return (me->totvert != 0);
1042 }
1043
1044 bool BKE_mesh_center_bounds(Mesh *me, float cent[3])
1045 {
1046         float min[3], max[3];
1047         INIT_MINMAX(min, max);
1048         if (BKE_mesh_minmax(me, min, max)) {
1049                 mid_v3_v3v3(cent, min, max);
1050                 return true;
1051         }
1052
1053         return false;
1054 }
1055
1056 bool BKE_mesh_center_centroid(Mesh *me, float cent[3])
1057 {
1058         int i = me->totpoly;
1059         MPoly *mpoly;
1060         float poly_area;
1061         float total_area = 0.0f;
1062         float poly_cent[3];
1063
1064         zero_v3(cent);
1065
1066         /* calculate a weighted average of polygon centroids */
1067         for (mpoly = me->mpoly; i--; mpoly++) {
1068                 poly_area = mesh_calc_poly_planar_area_centroid(mpoly, me->mloop + mpoly->loopstart, me->mvert, poly_cent);
1069
1070                 madd_v3_v3fl(cent, poly_cent, poly_area);
1071                 total_area += poly_area;
1072         }
1073         /* otherwise we get NAN for 0 polys */
1074         if (me->totpoly) {
1075                 mul_v3_fl(cent, 1.0f / total_area);
1076         }
1077
1078         /* zero area faces cause this, fallback to median */
1079         if (UNLIKELY(!is_finite_v3(cent))) {
1080                 return BKE_mesh_center_median(me, cent);
1081         }
1082
1083         return (me->totpoly != 0);
1084 }
1085 /** \} */
1086
1087
1088 /* -------------------------------------------------------------------- */
1089
1090 /** \name NGon Tessellation (NGon/Tessface Conversion)
1091  * \{ */
1092
1093 /**
1094  * Convert a triangle or quadrangle of loop/poly data to tessface data
1095  */
1096 void BKE_mesh_loops_to_mface_corners(
1097         CustomData *fdata, CustomData *ldata,
1098         CustomData *pdata, unsigned int lindex[4], int findex,
1099         const int polyindex,
1100         const int mf_len, /* 3 or 4 */
1101
1102         /* cache values to avoid lookups every time */
1103         const int numTex, /* CustomData_number_of_layers(pdata, CD_MTEXPOLY) */
1104         const int numCol, /* CustomData_number_of_layers(ldata, CD_MLOOPCOL) */
1105         const bool hasPCol, /* CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL) */
1106         const bool hasOrigSpace /* CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP) */
1107 )
1108 {
1109         MTFace *texface;
1110         MTexPoly *texpoly;
1111         MCol *mcol;
1112         MLoopCol *mloopcol;
1113         MLoopUV *mloopuv;
1114         int i, j;
1115
1116         for (i = 0; i < numTex; i++) {
1117                 texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
1118                 texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i);
1119
1120                 ME_MTEXFACE_CPY(texface, texpoly);
1121
1122                 for (j = 0; j < mf_len; j++) {
1123                         mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, (int)lindex[j], i);
1124                         copy_v2_v2(texface->uv[j], mloopuv->uv);
1125                 }
1126         }
1127
1128         for (i = 0; i < numCol; i++) {
1129                 mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
1130
1131                 for (j = 0; j < mf_len; j++) {
1132                         mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, (int)lindex[j], i);
1133                         MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
1134                 }
1135         }
1136
1137         if (hasPCol) {
1138                 mcol = CustomData_get(fdata,  findex, CD_PREVIEW_MCOL);
1139
1140                 for (j = 0; j < mf_len; j++) {
1141                         mloopcol = CustomData_get(ldata, (int)lindex[j], CD_PREVIEW_MLOOPCOL);
1142                         MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
1143                 }
1144         }
1145
1146         if (hasOrigSpace) {
1147                 OrigSpaceFace *of = CustomData_get(fdata, findex, CD_ORIGSPACE);
1148                 OrigSpaceLoop *lof;
1149
1150                 for (j = 0; j < mf_len; j++) {
1151                         lof = CustomData_get(ldata, (int)lindex[j], CD_ORIGSPACE_MLOOP);
1152                         copy_v2_v2(of->uv[j], lof->uv);
1153                 }
1154         }
1155 }
1156
1157 /**
1158  * Convert all CD layers from loop/poly to tessface data.
1159  *
1160  * @loopindices is an array of an int[4] per tessface, mapping tessface's verts to loops indices.
1161  *
1162  * Note when mface is not NULL, mface[face_index].v4 is used to test quads, else, loopindices[face_index][3] is used.
1163  */
1164 void BKE_mesh_loops_to_tessdata(CustomData *fdata, CustomData *ldata, CustomData *pdata, MFace *mface,
1165                                 int *polyindices, unsigned int (*loopindices)[4], const int num_faces)
1166 {
1167         /* Note: performances are sub-optimal when we get a NULL mface, we could be ~25% quicker with dedicated code...
1168          *       Issue is, unless having two different functions with nearly the same code, there's not much ways to solve
1169          *       this. Better imho to live with it for now. :/ --mont29
1170          */
1171         const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
1172         const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
1173         const bool hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
1174         const bool hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
1175         int findex, i, j;
1176         int *pidx;
1177         unsigned int (*lidx)[4];
1178
1179         for (i = 0; i < numTex; i++) {
1180                 MTFace *texface = CustomData_get_layer_n(fdata, CD_MTFACE, i);
1181                 MTexPoly *texpoly = CustomData_get_layer_n(pdata, CD_MTEXPOLY, i);
1182                 MLoopUV *mloopuv = CustomData_get_layer_n(ldata, CD_MLOOPUV, i);
1183
1184                 for (findex = 0, pidx = polyindices, lidx = loopindices;
1185                      findex < num_faces;
1186                      pidx++, lidx++, findex++, texface++)
1187                 {
1188                         ME_MTEXFACE_CPY(texface, &texpoly[*pidx]);
1189
1190                         for (j = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) {
1191                                 copy_v2_v2(texface->uv[j], mloopuv[(*lidx)[j]].uv);
1192                         }
1193                 }
1194         }
1195
1196         for (i = 0; i < numCol; i++) {
1197                 MCol (*mcol)[4] = CustomData_get_layer_n(fdata, CD_MCOL, i);
1198                 MLoopCol *mloopcol = CustomData_get_layer_n(ldata, CD_MLOOPCOL, i);
1199
1200                 for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, mcol++) {
1201                         for (j = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) {
1202                                 MESH_MLOOPCOL_TO_MCOL(&mloopcol[(*lidx)[j]], &(*mcol)[j]);
1203                         }
1204                 }
1205         }
1206
1207         if (hasPCol) {
1208                 MCol (*mcol)[4] = CustomData_get_layer(fdata, CD_PREVIEW_MCOL);
1209                 MLoopCol *mloopcol = CustomData_get_layer(ldata, CD_PREVIEW_MLOOPCOL);
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 (hasOrigSpace) {
1219                 OrigSpaceFace *of = CustomData_get_layer(fdata, CD_ORIGSPACE);
1220                 OrigSpaceLoop *lof = CustomData_get_layer(ldata, CD_ORIGSPACE_MLOOP);
1221
1222                 for (findex = 0, lidx = loopindices; findex < num_faces; lidx++, findex++, of++) {
1223                         for (j = (mface ? mface[findex].v4 : (*lidx)[3]) ? 4 : 3; j--;) {
1224                                 copy_v2_v2(of->uv[j], lof[(*lidx)[j]].uv);
1225                         }
1226                 }
1227         }
1228 }
1229
1230 /**
1231  * Recreate tessellation.
1232  *
1233  * @do_face_nor_copy controls whether the normals from the poly are copied to the tessellated faces.
1234  *
1235  * \return number of tessellation faces.
1236  */
1237 int BKE_mesh_recalc_tessellation(CustomData *fdata, CustomData *ldata, CustomData *pdata,
1238                                  MVert *mvert, int totface, int totloop, int totpoly, const bool do_face_nor_cpy)
1239 {
1240         /* use this to avoid locking pthread for _every_ polygon
1241          * and calling the fill function */
1242
1243 #define USE_TESSFACE_SPEEDUP
1244 #define USE_TESSFACE_QUADS  /* NEEDS FURTHER TESTING */
1245
1246 /* We abuse MFace->edcode to tag quad faces. See below for details. */
1247 #define TESSFACE_IS_QUAD 1
1248
1249         const int looptris_tot = poly_to_tri_count(totpoly, totloop);
1250
1251         MPoly *mp, *mpoly;
1252         MLoop *ml, *mloop;
1253         MFace *mface, *mf;
1254         MemArena *arena = NULL;
1255         int *mface_to_poly_map;
1256         unsigned int (*lindices)[4];
1257         int poly_index, mface_index;
1258         unsigned int j;
1259
1260         mpoly = CustomData_get_layer(pdata, CD_MPOLY);
1261         mloop = CustomData_get_layer(ldata, CD_MLOOP);
1262
1263         /* allocate the length of totfaces, avoid many small reallocs,
1264          * if all faces are tri's it will be correct, quads == 2x allocs */
1265         /* take care. we are _not_ calloc'ing so be sure to initialize each field */
1266         mface_to_poly_map = MEM_mallocN(sizeof(*mface_to_poly_map) * (size_t)looptris_tot, __func__);
1267         mface             = MEM_mallocN(sizeof(*mface) *             (size_t)looptris_tot, __func__);
1268         lindices          = MEM_mallocN(sizeof(*lindices) *          (size_t)looptris_tot, __func__);
1269
1270         mface_index = 0;
1271         mp = mpoly;
1272         for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) {
1273                 const unsigned int mp_loopstart = (unsigned int)mp->loopstart;
1274                 const unsigned int mp_totloop = (unsigned int)mp->totloop;
1275                 unsigned int l1, l2, l3, l4;
1276                 unsigned int *lidx;
1277                 if (mp_totloop < 3) {
1278                         /* do nothing */
1279                 }
1280
1281 #ifdef USE_TESSFACE_SPEEDUP
1282
1283 #define ML_TO_MF(i1, i2, i3)                                                  \
1284                 mface_to_poly_map[mface_index] = poly_index;                          \
1285                 mf = &mface[mface_index];                                             \
1286                 lidx = lindices[mface_index];                                         \
1287                 /* set loop indices, transformed to vert indices later */             \
1288                 l1 = mp_loopstart + i1;                                               \
1289                 l2 = mp_loopstart + i2;                                               \
1290                 l3 = mp_loopstart + i3;                                               \
1291                 mf->v1 = mloop[l1].v;                                                 \
1292                 mf->v2 = mloop[l2].v;                                                 \
1293                 mf->v3 = mloop[l3].v;                                                 \
1294                 mf->v4 = 0;                                                           \
1295                 lidx[0] = l1;                                                         \
1296                 lidx[1] = l2;                                                         \
1297                 lidx[2] = l3;                                                         \
1298                 lidx[3] = 0;                                                          \
1299                 mf->mat_nr = mp->mat_nr;                                              \
1300                 mf->flag = mp->flag;                                                  \
1301                 mf->edcode = 0;                                                       \
1302                 (void)0
1303
1304 /* ALMOST IDENTICAL TO DEFINE ABOVE (see EXCEPTION) */
1305 #define ML_TO_MF_QUAD()                                                       \
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 + 0; /* EXCEPTION */                                \
1311                 l2 = mp_loopstart + 1; /* EXCEPTION */                                \
1312                 l3 = mp_loopstart + 2; /* EXCEPTION */                                \
1313                 l4 = mp_loopstart + 3; /* EXCEPTION */                                \
1314                 mf->v1 = mloop[l1].v;                                                 \
1315                 mf->v2 = mloop[l2].v;                                                 \
1316                 mf->v3 = mloop[l3].v;                                                 \
1317                 mf->v4 = mloop[l4].v;                                                 \
1318                 lidx[0] = l1;                                                         \
1319                 lidx[1] = l2;                                                         \
1320                 lidx[2] = l3;                                                         \
1321                 lidx[3] = l4;                                                         \
1322                 mf->mat_nr = mp->mat_nr;                                              \
1323                 mf->flag = mp->flag;                                                  \
1324                 mf->edcode = TESSFACE_IS_QUAD;                                        \
1325                 (void)0
1326
1327
1328                 else if (mp_totloop == 3) {
1329                         ML_TO_MF(0, 1, 2);
1330                         mface_index++;
1331                 }
1332                 else if (mp_totloop == 4) {
1333 #ifdef USE_TESSFACE_QUADS
1334                         ML_TO_MF_QUAD();
1335                         mface_index++;
1336 #else
1337                         ML_TO_MF(0, 1, 2);
1338                         mface_index++;
1339                         ML_TO_MF(0, 2, 3);
1340                         mface_index++;
1341 #endif
1342                 }
1343 #endif /* USE_TESSFACE_SPEEDUP */
1344                 else {
1345                         const float *co_curr, *co_prev;
1346
1347                         float normal[3];
1348
1349                         float axis_mat[3][3];
1350                         float (*projverts)[2];
1351                         unsigned int (*tris)[3];
1352
1353                         const unsigned int totfilltri = mp_totloop - 2;
1354
1355                         if (UNLIKELY(arena == NULL)) {
1356                                 arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1357                         }
1358
1359                         tris = BLI_memarena_alloc(arena, sizeof(*tris) * (size_t)totfilltri);
1360                         projverts = BLI_memarena_alloc(arena, sizeof(*projverts) * (size_t)mp_totloop);
1361
1362                         zero_v3(normal);
1363
1364                         /* calc normal */
1365                         ml = mloop + mp_loopstart;
1366                         co_prev = mvert[ml[mp_totloop - 1].v].co;
1367                         for (j = 0; j < mp_totloop; j++, ml++) {
1368                                 co_curr = mvert[ml->v].co;
1369                                 add_newell_cross_v3_v3v3(normal, co_prev, co_curr);
1370                                 co_prev = co_curr;
1371                         }
1372                         if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
1373                                 normal[2] = 1.0f;
1374                         }
1375
1376                         /* project verts to 2d */
1377                         axis_dominant_v3_to_m3(axis_mat, normal);
1378
1379                         ml = mloop + mp_loopstart;
1380                         for (j = 0; j < mp_totloop; j++, ml++) {
1381                                 mul_v2_m3v3(projverts[j], axis_mat, mvert[ml->v].co);
1382                         }
1383
1384                         BLI_polyfill_calc_arena((const float (*)[2])projverts, mp_totloop, tris, arena);
1385
1386                         /* apply fill */
1387                         for (j = 0; j < totfilltri; j++) {
1388                                 unsigned int *tri = tris[j];
1389                                 lidx = lindices[mface_index];
1390
1391                                 mface_to_poly_map[mface_index] = poly_index;
1392                                 mf = &mface[mface_index];
1393
1394                                 /* set loop indices, transformed to vert indices later */
1395                                 l1 = mp_loopstart + tri[0];
1396                                 l2 = mp_loopstart + tri[1];
1397                                 l3 = mp_loopstart + tri[2];
1398
1399                                 /* sort loop indices to ensure winding is correct */
1400                                 if (l1 > l2) SWAP(unsigned int, l1, l2);
1401                                 if (l2 > l3) SWAP(unsigned int, l2, l3);
1402                                 if (l1 > l2) SWAP(unsigned int, l1, l2);
1403
1404                                 mf->v1 = mloop[l1].v;
1405                                 mf->v2 = mloop[l2].v;
1406                                 mf->v3 = mloop[l3].v;
1407                                 mf->v4 = 0;
1408
1409                                 lidx[0] = l1;
1410                                 lidx[1] = l2;
1411                                 lidx[2] = l3;
1412                                 lidx[3] = 0;
1413
1414                                 mf->mat_nr = mp->mat_nr;
1415                                 mf->flag = mp->flag;
1416                                 mf->edcode = 0;
1417
1418                                 mface_index++;
1419                         }
1420
1421                         BLI_memarena_clear(arena);
1422                 }
1423         }
1424
1425         if (arena) {
1426                 BLI_memarena_free(arena);
1427                 arena = NULL;
1428         }
1429
1430         CustomData_free(fdata, totface);
1431         totface = mface_index;
1432
1433         BLI_assert(totface <= looptris_tot);
1434
1435         /* not essential but without this we store over-alloc'd memory in the CustomData layers */
1436         if (LIKELY(looptris_tot != totface)) {
1437                 mface = MEM_reallocN(mface, sizeof(*mface) * (size_t)totface);
1438                 mface_to_poly_map = MEM_reallocN(mface_to_poly_map, sizeof(*mface_to_poly_map) * (size_t)totface);
1439         }
1440
1441         CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
1442
1443         /* CD_ORIGINDEX will contain an array of indices from tessfaces to the polygons
1444          * they are directly tessellated from */
1445         CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, mface_to_poly_map, totface);
1446         CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
1447
1448         if (do_face_nor_cpy) {
1449                 /* If polys have a normals layer, copying that to faces can help
1450                  * avoid the need to recalculate normals later */
1451                 if (CustomData_has_layer(pdata, CD_NORMAL)) {
1452                         float (*pnors)[3] = CustomData_get_layer(pdata, CD_NORMAL);
1453                         float (*fnors)[3] = CustomData_add_layer(fdata, CD_NORMAL, CD_CALLOC, NULL, totface);
1454                         for (mface_index = 0; mface_index < totface; mface_index++) {
1455                                 copy_v3_v3(fnors[mface_index], pnors[mface_to_poly_map[mface_index]]);
1456                         }
1457                 }
1458         }
1459
1460         /* NOTE: quad detection issue - forth vertidx vs forth loopidx:
1461          * Polygons take care of their loops ordering, hence not of their vertices ordering.
1462          * Currently, our tfaces' forth vertex index might be 0 even for a quad. However, we know our forth loop index is
1463          * never 0 for quads (because they are sorted for polygons, and our quads are still mere copies of their polygons).
1464          * So we pass NULL as MFace pointer, and BKE_mesh_loops_to_tessdata will use the forth loop index as quad test.
1465          * ...
1466          */
1467         BKE_mesh_loops_to_tessdata(fdata, ldata, pdata, NULL, mface_to_poly_map, lindices, totface);
1468
1469         /* NOTE: quad detection issue - forth vertidx vs forth loopidx:
1470          * ...However, most TFace code uses 'MFace->v4 == 0' test to check whether it is a tri or quad.
1471          * test_index_face() will check this and rotate the tessellated face if needed.
1472          */
1473 #ifdef USE_TESSFACE_QUADS
1474         mf = mface;
1475         for (mface_index = 0; mface_index < totface; mface_index++, mf++) {
1476                 if (mf->edcode == TESSFACE_IS_QUAD) {
1477                         test_index_face(mf, fdata, mface_index, 4);
1478                         mf->edcode = 0;
1479                 }
1480         }
1481 #endif
1482
1483         MEM_freeN(lindices);
1484
1485         return totface;
1486
1487 #undef USE_TESSFACE_SPEEDUP
1488 #undef USE_TESSFACE_QUADS
1489
1490 #undef ML_TO_MF
1491 #undef ML_TO_MF_QUAD
1492
1493 }
1494
1495 #ifdef USE_BMESH_SAVE_AS_COMPAT
1496
1497 /**
1498  * This function recreates a tessellation.
1499  * returns number of tessellation faces.
1500  *
1501  * for forwards compat only quad->tri polys to mface, skip ngons.
1502  */
1503 int BKE_mesh_mpoly_to_mface(struct CustomData *fdata, struct CustomData *ldata,
1504                             struct CustomData *pdata, int totface, int UNUSED(totloop), int totpoly)
1505 {
1506         MLoop *mloop;
1507
1508         unsigned int lindex[4];
1509         int i;
1510         int k;
1511
1512         MPoly *mp, *mpoly;
1513         MFace *mface, *mf;
1514
1515         const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
1516         const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
1517         const bool hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
1518         const bool hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
1519
1520         /* over-alloc, ngons will be skipped */
1521         mface = MEM_mallocN(sizeof(*mface) * (size_t)totpoly, __func__);
1522
1523         mpoly = CustomData_get_layer(pdata, CD_MPOLY);
1524         mloop = CustomData_get_layer(ldata, CD_MLOOP);
1525
1526         mp = mpoly;
1527         k = 0;
1528         for (i = 0; i < totpoly; i++, mp++) {
1529                 if (ELEM(mp->totloop, 3, 4)) {
1530                         const unsigned int mp_loopstart = (unsigned int)mp->loopstart;
1531                         mf = &mface[k];
1532
1533                         mf->mat_nr = mp->mat_nr;
1534                         mf->flag = mp->flag;
1535
1536                         mf->v1 = mp_loopstart + 0;
1537                         mf->v2 = mp_loopstart + 1;
1538                         mf->v3 = mp_loopstart + 2;
1539                         mf->v4 = (mp->totloop == 4) ? (mp_loopstart + 3) : 0;
1540
1541                         /* abuse edcode for temp storage and clear next loop */
1542                         mf->edcode = (char)mp->totloop; /* only ever 3 or 4 */
1543
1544                         k++;
1545                 }
1546         }
1547
1548         CustomData_free(fdata, totface);
1549
1550         totface = k;
1551
1552         CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
1553
1554         CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
1555
1556         mp = mpoly;
1557         k = 0;
1558         for (i = 0; i < totpoly; i++, mp++) {
1559                 if (ELEM(mp->totloop, 3, 4)) {
1560                         mf = &mface[k];
1561
1562                         if (mf->edcode == 3) {
1563                                 /* sort loop indices to ensure winding is correct */
1564                                 /* NO SORT - looks like we can skip this */
1565
1566                                 lindex[0] = mf->v1;
1567                                 lindex[1] = mf->v2;
1568                                 lindex[2] = mf->v3;
1569                                 lindex[3] = 0; /* unused */
1570
1571                                 /* transform loop indices to vert indices */
1572                                 mf->v1 = mloop[mf->v1].v;
1573                                 mf->v2 = mloop[mf->v2].v;
1574                                 mf->v3 = mloop[mf->v3].v;
1575
1576                                 BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
1577                                                                 lindex, k, i, 3,
1578                                                                 numTex, numCol, hasPCol, hasOrigSpace);
1579                                 test_index_face(mf, fdata, k, 3);
1580                         }
1581                         else {
1582                                 /* sort loop indices to ensure winding is correct */
1583                                 /* NO SORT - looks like we can skip this */
1584
1585                                 lindex[0] = mf->v1;
1586                                 lindex[1] = mf->v2;
1587                                 lindex[2] = mf->v3;
1588                                 lindex[3] = mf->v4;
1589
1590                                 /* transform loop indices to vert indices */
1591                                 mf->v1 = mloop[mf->v1].v;
1592                                 mf->v2 = mloop[mf->v2].v;
1593                                 mf->v3 = mloop[mf->v3].v;
1594                                 mf->v4 = mloop[mf->v4].v;
1595
1596                                 BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
1597                                                                 lindex, k, i, 4,
1598                                                                 numTex, numCol, hasPCol, hasOrigSpace);
1599                                 test_index_face(mf, fdata, k, 4);
1600                         }
1601
1602                         mf->edcode = 0;
1603
1604                         k++;
1605                 }
1606         }
1607
1608         return k;
1609 }
1610 #endif /* USE_BMESH_SAVE_AS_COMPAT */
1611
1612
1613 static void bm_corners_to_loops_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
1614                                    MFace *mface, int totloop, int findex, int loopstart, int numTex, int numCol)
1615 {
1616         MTFace *texface;
1617         MTexPoly *texpoly;
1618         MCol *mcol;
1619         MLoopCol *mloopcol;
1620         MLoopUV *mloopuv;
1621         MFace *mf;
1622         int i;
1623
1624         mf = mface + findex;
1625
1626         for (i = 0; i < numTex; i++) {
1627                 texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
1628                 texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, findex, i);
1629
1630                 ME_MTEXFACE_CPY(texpoly, texface);
1631
1632                 mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, loopstart, i);
1633                 copy_v2_v2(mloopuv->uv, texface->uv[0]); mloopuv++;
1634                 copy_v2_v2(mloopuv->uv, texface->uv[1]); mloopuv++;
1635                 copy_v2_v2(mloopuv->uv, texface->uv[2]); mloopuv++;
1636
1637                 if (mf->v4) {
1638                         copy_v2_v2(mloopuv->uv, texface->uv[3]); mloopuv++;
1639                 }
1640         }
1641
1642         for (i = 0; i < numCol; i++) {
1643                 mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, loopstart, i);
1644                 mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
1645
1646                 MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[0]); mloopcol++;
1647                 MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[1]); mloopcol++;
1648                 MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[2]); mloopcol++;
1649                 if (mf->v4) {
1650                         MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[3]); mloopcol++;
1651                 }
1652         }
1653
1654         if (CustomData_has_layer(fdata, CD_MDISPS)) {
1655                 MDisps *ld = CustomData_get(ldata, loopstart, CD_MDISPS);
1656                 MDisps *fd = CustomData_get(fdata, findex, CD_MDISPS);
1657                 float (*disps)[3] = fd->disps;
1658                 int tot = mf->v4 ? 4 : 3;
1659                 int corners;
1660
1661                 if (CustomData_external_test(fdata, CD_MDISPS)) {
1662                         if (id && fdata->external) {
1663                                 CustomData_external_add(ldata, id, CD_MDISPS,
1664                                                         totloop, fdata->external->filename);
1665                         }
1666                 }
1667
1668                 corners = multires_mdisp_corners(fd);
1669
1670                 if (corners == 0) {
1671                         /* Empty MDisp layers appear in at least one of the sintel.blend files.
1672                          * Not sure why this happens, but it seems fine to just ignore them here.
1673                          * If (corners == 0) for a non-empty layer though, something went wrong. */
1674                         BLI_assert(fd->totdisp == 0);
1675                 }
1676                 else {
1677                         const int side = (int)sqrtf((float)(fd->totdisp / corners));
1678                         const int side_sq = side * side;
1679                         const size_t disps_size = sizeof(float[3]) * (size_t)side_sq;
1680
1681                         for (i = 0; i < tot; i++, disps += side_sq, ld++) {
1682                                 ld->totdisp = side_sq;
1683                                 ld->level = (int)(logf((float)side - 1.0f) / (float)M_LN2) + 1;
1684
1685                                 if (ld->disps)
1686                                         MEM_freeN(ld->disps);
1687
1688                                 ld->disps = MEM_mallocN(disps_size, "converted loop mdisps");
1689                                 if (fd->disps) {
1690                                         memcpy(ld->disps, disps, disps_size);
1691                                 }
1692                                 else {
1693                                         memset(ld->disps, 0, disps_size);
1694                                 }
1695                         }
1696                 }
1697         }
1698 }
1699
1700
1701 void BKE_mesh_convert_mfaces_to_mpolys(Mesh *mesh)
1702 {
1703         BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
1704                                              mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
1705                                              mesh->medge, mesh->mface,
1706                                              &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
1707
1708         BKE_mesh_update_customdata_pointers(mesh, true);
1709 }
1710
1711 /* the same as BKE_mesh_convert_mfaces_to_mpolys but oriented to be used in do_versions from readfile.c
1712  * the difference is how active/render/clone/stencil indices are handled here
1713  *
1714  * normally thay're being set from pdata which totally makes sense for meshes which are already
1715  * converted to bmesh structures, but when loading older files indices shall be updated in other
1716  * way around, so newly added pdata and ldata would have this indices set based on fdata layer
1717  *
1718  * this is normally only needed when reading older files, in all other cases BKE_mesh_convert_mfaces_to_mpolys
1719  * shall be always used
1720  */
1721 void BKE_mesh_do_versions_convert_mfaces_to_mpolys(Mesh *mesh)
1722 {
1723         BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
1724                                              mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
1725                                              mesh->medge, mesh->mface,
1726                                              &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
1727
1728         CustomData_bmesh_do_versions_update_active_layers(&mesh->fdata, &mesh->pdata, &mesh->ldata);
1729
1730         BKE_mesh_update_customdata_pointers(mesh, true);
1731 }
1732
1733 void BKE_mesh_convert_mfaces_to_mpolys_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
1734                                           int totedge_i, int totface_i, int totloop_i, int totpoly_i,
1735                                           MEdge *medge, MFace *mface,
1736                                           int *r_totloop, int *r_totpoly,
1737                                           MLoop **r_mloop, MPoly **r_mpoly)
1738 {
1739         MFace *mf;
1740         MLoop *ml, *mloop;
1741         MPoly *mp, *mpoly;
1742         MEdge *me;
1743         EdgeHash *eh;
1744         int numTex, numCol;
1745         int i, j, totloop, totpoly, *polyindex;
1746
1747         /* just in case some of these layers are filled in (can happen with python created meshes) */
1748         CustomData_free(ldata, totloop_i);
1749         CustomData_free(pdata, totpoly_i);
1750
1751         totpoly = totface_i;
1752         mpoly = MEM_callocN(sizeof(MPoly) * (size_t)totpoly, "mpoly converted");
1753         CustomData_add_layer(pdata, CD_MPOLY, CD_ASSIGN, mpoly, totpoly);
1754
1755         numTex = CustomData_number_of_layers(fdata, CD_MTFACE);
1756         numCol = CustomData_number_of_layers(fdata, CD_MCOL);
1757
1758         totloop = 0;
1759         mf = mface;
1760         for (i = 0; i < totface_i; i++, mf++) {
1761                 totloop += mf->v4 ? 4 : 3;
1762         }
1763
1764         mloop = MEM_callocN(sizeof(MLoop) * (size_t)totloop, "mloop converted");
1765
1766         CustomData_add_layer(ldata, CD_MLOOP, CD_ASSIGN, mloop, totloop);
1767
1768         CustomData_to_bmeshpoly(fdata, pdata, ldata, totloop, totpoly);
1769
1770         if (id) {
1771                 /* ensure external data is transferred */
1772                 CustomData_external_read(fdata, id, CD_MASK_MDISPS, totface_i);
1773         }
1774
1775         eh = BLI_edgehash_new_ex(__func__, (unsigned int)totedge_i);
1776
1777         /* build edge hash */
1778         me = medge;
1779         for (i = 0; i < totedge_i; i++, me++) {
1780                 BLI_edgehash_insert(eh, me->v1, me->v2, SET_UINT_IN_POINTER(i));
1781
1782                 /* unrelated but avoid having the FGON flag enabled, so we can reuse it later for something else */
1783                 me->flag &= ~ME_FGON;
1784         }
1785
1786         polyindex = CustomData_get_layer(fdata, CD_ORIGINDEX);
1787
1788         j = 0; /* current loop index */
1789         ml = mloop;
1790         mf = mface;
1791         mp = mpoly;
1792         for (i = 0; i < totface_i; i++, mf++, mp++) {
1793                 mp->loopstart = j;
1794
1795                 mp->totloop = mf->v4 ? 4 : 3;
1796
1797                 mp->mat_nr = mf->mat_nr;
1798                 mp->flag = mf->flag;
1799
1800 #       define ML(v1, v2) { \
1801                         ml->v = mf->v1; \
1802                         ml->e = GET_UINT_FROM_POINTER(BLI_edgehash_lookup(eh, mf->v1, mf->v2)); \
1803                         ml++; j++; \
1804                 } (void)0
1805
1806                 ML(v1, v2);
1807                 ML(v2, v3);
1808                 if (mf->v4) {
1809                         ML(v3, v4);
1810                         ML(v4, v1);
1811                 }
1812                 else {
1813                         ML(v3, v1);
1814                 }
1815
1816 #       undef ML
1817
1818                 bm_corners_to_loops_ex(id, fdata, ldata, pdata, mface, totloop, i, mp->loopstart, numTex, numCol);
1819
1820                 if (polyindex) {
1821                         *polyindex = i;
1822                         polyindex++;
1823                 }
1824         }
1825
1826         /* note, we don't convert NGons at all, these are not even real ngons,
1827          * they have their own UV's, colors etc - its more an editing feature. */
1828
1829         BLI_edgehash_free(eh, NULL);
1830
1831         *r_totpoly = totpoly;
1832         *r_totloop = totloop;
1833         *r_mpoly = mpoly;
1834         *r_mloop = mloop;
1835 }
1836 /** \} */
1837
1838
1839 /* -------------------------------------------------------------------- */
1840
1841 /** \name Mesh Flag Flushing
1842  * \{ */
1843
1844 /* update the hide flag for edges and faces from the corresponding
1845  * flag in verts */
1846 void BKE_mesh_flush_hidden_from_verts_ex(const MVert *mvert,
1847                                          const MLoop *mloop,
1848                                          MEdge *medge, const int totedge,
1849                                          MPoly *mpoly, const int totpoly)
1850 {
1851         int i, j;
1852
1853         for (i = 0; i < totedge; i++) {
1854                 MEdge *e = &medge[i];
1855                 if (mvert[e->v1].flag & ME_HIDE ||
1856                     mvert[e->v2].flag & ME_HIDE)
1857                 {
1858                         e->flag |= ME_HIDE;
1859                 }
1860                 else {
1861                         e->flag &= ~ME_HIDE;
1862                 }
1863         }
1864         for (i = 0; i < totpoly; i++) {
1865                 MPoly *p = &mpoly[i];
1866                 p->flag &= (char)~ME_HIDE;
1867                 for (j = 0; j < p->totloop; j++) {
1868                         if (mvert[mloop[p->loopstart + j].v].flag & ME_HIDE)
1869                                 p->flag |= ME_HIDE;
1870                 }
1871         }
1872 }
1873 void BKE_mesh_flush_hidden_from_verts(Mesh *me)
1874 {
1875         BKE_mesh_flush_hidden_from_verts_ex(me->mvert, me->mloop,
1876                                             me->medge, me->totedge,
1877                                             me->mpoly, me->totpoly);
1878 }
1879
1880 void BKE_mesh_flush_hidden_from_polys_ex(MVert *mvert,
1881                                          const MLoop *mloop,
1882                                          MEdge *medge, const int UNUSED(totedge),
1883                                          const MPoly *mpoly, const int totpoly)
1884 {
1885         const MPoly *mp;
1886         int i;
1887
1888         i = totpoly;
1889         for (mp = mpoly; i--; mp++) {
1890                 if (mp->flag & ME_HIDE) {
1891                         const MLoop *ml;
1892                         int j;
1893                         j = mp->totloop;
1894                         for (ml = &mloop[mp->loopstart]; j--; ml++) {
1895                                 mvert[ml->v].flag |= ME_HIDE;
1896                                 medge[ml->e].flag |= ME_HIDE;
1897                         }
1898                 }
1899         }
1900
1901         i = totpoly;
1902         for (mp = mpoly; i--; mp++) {
1903                 if ((mp->flag & ME_HIDE) == 0) {
1904                         const MLoop *ml;
1905                         int j;
1906                         j = mp->totloop;
1907                         for (ml = &mloop[mp->loopstart]; j--; ml++) {
1908                                 mvert[ml->v].flag &= (char)~ME_HIDE;
1909                                 medge[ml->e].flag &= (char)~ME_HIDE;
1910                         }
1911                 }
1912         }
1913 }
1914 void BKE_mesh_flush_hidden_from_polys(Mesh *me)
1915 {
1916         BKE_mesh_flush_hidden_from_polys_ex(me->mvert, me->mloop,
1917                                             me->medge, me->totedge,
1918                                             me->mpoly, me->totpoly);
1919 }
1920
1921 /**
1922  * simple poly -> vert/edge selection.
1923  */
1924 void BKE_mesh_flush_select_from_polys_ex(MVert *mvert,       const int totvert,
1925                                          const MLoop *mloop,
1926                                          MEdge *medge,       const int totedge,
1927                                          const MPoly *mpoly, const int totpoly)
1928 {
1929         MVert *mv;
1930         MEdge *med;
1931         const MPoly *mp;
1932         int i;
1933
1934         i = totvert;
1935         for (mv = mvert; i--; mv++) {
1936                 mv->flag &= (char)~SELECT;
1937         }
1938
1939         i = totedge;
1940         for (med = medge; i--; med++) {
1941                 med->flag &= ~SELECT;
1942         }
1943
1944         i = totpoly;
1945         for (mp = mpoly; i--; mp++) {
1946                 /* assume if its selected its not hidden and none of its verts/edges are hidden
1947                  * (a common assumption)*/
1948                 if (mp->flag & ME_FACE_SEL) {
1949                         const MLoop *ml;
1950                         int j;
1951                         j = mp->totloop;
1952                         for (ml = &mloop[mp->loopstart]; j--; ml++) {
1953                                 mvert[ml->v].flag |= SELECT;
1954                                 medge[ml->e].flag |= SELECT;
1955                         }
1956                 }
1957         }
1958 }
1959 void BKE_mesh_flush_select_from_polys(Mesh *me)
1960 {
1961         BKE_mesh_flush_select_from_polys_ex(me->mvert, me->totvert,
1962                                          me->mloop,
1963                                          me->medge, me->totedge,
1964                                          me->mpoly, me->totpoly);
1965 }
1966
1967 void BKE_mesh_flush_select_from_verts_ex(const MVert *mvert, const int UNUSED(totvert),
1968                                          const MLoop *mloop,
1969                                          MEdge *medge,       const int totedge,
1970                                          MPoly *mpoly,       const int totpoly)
1971 {
1972         MEdge *med;
1973         MPoly *mp;
1974         int i;
1975
1976         /* edges */
1977         i = totedge;
1978         for (med = medge; i--; med++) {
1979                 if ((med->flag & ME_HIDE) == 0) {
1980                         if ((mvert[med->v1].flag & SELECT) && (mvert[med->v2].flag & SELECT)) {
1981                                 med->flag |= SELECT;
1982                         }
1983                         else {
1984                                 med->flag &= ~SELECT;
1985                         }
1986                 }
1987         }
1988
1989         /* polys */
1990         i = totpoly;
1991         for (mp = mpoly; i--; mp++) {
1992                 if ((mp->flag & ME_HIDE) == 0) {
1993                         int ok = TRUE;
1994                         const MLoop *ml;
1995                         int j;
1996                         j = mp->totloop;
1997                         for (ml = &mloop[mp->loopstart]; j--; ml++) {
1998                                 if ((mvert[ml->v].flag & SELECT) == 0) {
1999                                         ok = FALSE;
2000                                         break;
2001                                 }
2002                         }
2003
2004                         if (ok) {
2005                                 mp->flag |= ME_FACE_SEL;
2006                         }
2007                         else {
2008                                 mp->flag &= (char)~ME_FACE_SEL;
2009                         }
2010                 }
2011         }
2012 }
2013 void BKE_mesh_flush_select_from_verts(Mesh *me)
2014 {
2015         BKE_mesh_flush_select_from_verts_ex(me->mvert, me->totvert,
2016                                             me->mloop,
2017                                             me->medge, me->totedge,
2018                                             me->mpoly, me->totpoly);
2019 }
2020 /** \} */
2021
2022 /* -------------------------------------------------------------------- */
2023
2024 /** \name Mesh Spatial Calculation
2025  * \{ */
2026
2027 /**
2028  * This function takes the difference between 2 vertex-coord-arrays
2029  * (\a vert_cos_src, \a vert_cos_dst),
2030  * and applies the difference to \a vert_cos_new relative to \a vert_cos_org.
2031  *
2032  * \param vert_cos_src reference deform source.
2033  * \param vert_cos_dst reference deform destination.
2034  *
2035  * \param vert_cos_org reference for the output location.
2036  * \param vert_cos_new resulting coords.
2037  */
2038 void BKE_mesh_calc_relative_deform(
2039         const MPoly *mpoly, const int totpoly,
2040         const MLoop *mloop, const int totvert,
2041
2042         const float (*vert_cos_src)[3],
2043         const float (*vert_cos_dst)[3],
2044
2045         const float (*vert_cos_org)[3],
2046               float (*vert_cos_new)[3])
2047 {
2048         const MPoly *mp;
2049         int i;
2050
2051         int *vert_accum = MEM_callocN(sizeof(*vert_accum) * (size_t)totvert, __func__);
2052
2053         memset(vert_cos_new, '\0', sizeof(*vert_cos_new) * (size_t)totvert);
2054
2055         for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
2056                 const MLoop *loopstart = mloop + mp->loopstart;
2057                 int j;
2058
2059                 for (j = 0; j < mp->totloop; j++) {
2060                         unsigned int v_prev = loopstart[(mp->totloop + (j - 1)) % mp->totloop].v;
2061                         unsigned int v_curr = loopstart[j].v;
2062                         unsigned int v_next = loopstart[(j + 1) % mp->totloop].v;
2063
2064                         float tvec[3];
2065
2066                         barycentric_transform(
2067                                     tvec, vert_cos_dst[v_curr],
2068                                     vert_cos_org[v_prev], vert_cos_org[v_curr], vert_cos_org[v_next],
2069                                     vert_cos_src[v_prev], vert_cos_src[v_curr], vert_cos_src[v_next]
2070                                     );
2071
2072                         add_v3_v3(vert_cos_new[v_curr], tvec);
2073                         vert_accum[v_curr] += 1;
2074                 }
2075         }
2076
2077         for (i = 0; i < totvert; i++) {
2078                 if (vert_accum[i]) {
2079                         mul_v3_fl(vert_cos_new[i], 1.0f / (float)vert_accum[i]);
2080                 }
2081                 else {
2082                         copy_v3_v3(vert_cos_new[i], vert_cos_org[i]);
2083                 }
2084         }
2085
2086         MEM_freeN(vert_accum);
2087 }
2088 /** \} */