source/blender/blenkernel/intern/mesh.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.c
  27  *  \ingroup bke
  28  */
  29
  30
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include <stdio.h>
  34 #include <math.h>
  35
  36 #include "MEM_guardedalloc.h"
  37
  38 #include "DNA_scene_types.h"
  39 #include "DNA_material_types.h"
  40 #include "DNA_object_types.h"
  41 #include "DNA_key_types.h"
  42 #include "DNA_mesh_types.h"
  43 #include "DNA_meshdata_types.h"
  44 #include "DNA_ipo_types.h"
  45 #include "DNA_customdata_types.h"
  46
  47 #include "BLI_utildefines.h"
  48 #include "BLI_blenlib.h"
  49 #include "BLI_bpath.h"
  50 #include "BLI_math.h"
  51 #include "BLI_edgehash.h"
  52 #include "BLI_scanfill.h"
  53 #include "BLI_array.h"
  54
  55 #include "BKE_animsys.h"
  56 #include "BKE_main.h"
  57 #include "BKE_customdata.h"
  58 #include "BKE_DerivedMesh.h"
  59 #include "BKE_global.h"
  60 #include "BKE_mesh.h"
  61 #include "BKE_displist.h"
  62 #include "BKE_library.h"
  63 #include "BKE_material.h"
  64 #include "BKE_modifier.h"
  65 #include "BKE_multires.h"
  66 #include "BKE_key.h"
  67 /* these 2 are only used by conversion functions */
  68 #include "BKE_curve.h"
  69 /* -- */
  70 #include "BKE_object.h"
  71 #include "BKE_tessmesh.h"
  72 #include "BLI_edgehash.h"
  73
  74 #include "bmesh.h"
  75
  76 enum {
  77         MESHCMP_DVERT_WEIGHTMISMATCH = 1,
  78         MESHCMP_DVERT_GROUPMISMATCH,
  79         MESHCMP_DVERT_TOTGROUPMISMATCH,
  80         MESHCMP_LOOPCOLMISMATCH,
  81         MESHCMP_LOOPUVMISMATCH,
  82         MESHCMP_LOOPMISMATCH,
  83         MESHCMP_POLYVERTMISMATCH,
  84         MESHCMP_POLYMISMATCH,
  85         MESHCMP_EDGEUNKNOWN,
  86         MESHCMP_VERTCOMISMATCH,
  87         MESHCMP_CDLAYERS_MISMATCH
  88 };
  89
  90 static const char *cmpcode_to_str(int code)
  91 {
  92         switch (code) {
  93                 case MESHCMP_DVERT_WEIGHTMISMATCH:
  94                         return "Vertex Weight Mismatch";
  95                 case MESHCMP_DVERT_GROUPMISMATCH:
  96                         return "Vertex Group Mismatch";
  97                 case MESHCMP_DVERT_TOTGROUPMISMATCH:
  98                         return "Vertex Doesn't Belong To Same Number Of Groups";
  99                 case MESHCMP_LOOPCOLMISMATCH:
 100                         return "Vertex Color Mismatch";
 101                 case MESHCMP_LOOPUVMISMATCH:
 102                         return "UV Mismatch";
 103                 case MESHCMP_LOOPMISMATCH:
 104                         return "Loop Mismatch";
 105                 case MESHCMP_POLYVERTMISMATCH:
 106                         return "Loop Vert Mismatch In Poly Test";
 107                 case MESHCMP_POLYMISMATCH:
 108                         return "Loop Vert Mismatch";
 109                 case MESHCMP_EDGEUNKNOWN:
 110                         return "Edge Mismatch";
 111                 case MESHCMP_VERTCOMISMATCH:
 112                         return "Vertex Coordinate Mismatch";
 113                 case MESHCMP_CDLAYERS_MISMATCH:
 114                         return "CustomData Layer Count Mismatch";
 115                 default:
 116                         return "Mesh Comparison Code Unknown";
 117         }
 118 }
 119
 120 /* thresh is threshold for comparing vertices, uvs, vertex colors,
 121  * weights, etc.*/
 122 static int customdata_compare(CustomData *c1, CustomData *c2, Mesh *m1, Mesh *m2, float thresh)
 123 {
 124         CustomDataLayer *l1, *l2;
 125         int i, i1 = 0, i2 = 0, tot, j;
 126
 127         for (i = 0; i < c1->totlayer; i++) {
 128                 if (ELEM7(c1->layers[i].type, CD_MVERT, CD_MEDGE, CD_MPOLY,
 129                           CD_MLOOPUV, CD_MLOOPCOL, CD_MTEXPOLY, CD_MDEFORMVERT))
 130                 {
 131                         i1++;
 132                 }
 133         }
 134
 135         for (i = 0; i < c2->totlayer; i++) {
 136                 if (ELEM7(c2->layers[i].type, CD_MVERT, CD_MEDGE, CD_MPOLY,
 137                           CD_MLOOPUV, CD_MLOOPCOL, CD_MTEXPOLY, CD_MDEFORMVERT))
 138                 {
 139                         i2++;
 140                 }
 141         }
 142
 143         if (i1 != i2)
 144                 return MESHCMP_CDLAYERS_MISMATCH;
 145
 146         l1 = c1->layers; l2 = c2->layers;
 147         tot = i1;
 148         i1 = 0; i2 = 0;
 149         for (i = 0; i < tot; i++) {
 150                 while (i1 < c1->totlayer && !ELEM7(l1->type, CD_MVERT, CD_MEDGE, CD_MPOLY,
 151                                                    CD_MLOOPUV, CD_MLOOPCOL, CD_MTEXPOLY, CD_MDEFORMVERT))
 152                 {
 153                         i1++, l1++;
 154                 }
 155
 156                 while (i2 < c2->totlayer && !ELEM7(l2->type, CD_MVERT, CD_MEDGE, CD_MPOLY,
 157                                                    CD_MLOOPUV, CD_MLOOPCOL, CD_MTEXPOLY, CD_MDEFORMVERT))
 158                 {
 159                         i2++, l2++;
 160                 }
 161
 162                 if (l1->type == CD_MVERT) {
 163                         MVert *v1 = l1->data;
 164                         MVert *v2 = l2->data;
 165                         int vtot = m1->totvert;
 166
 167                         for (j = 0; j < vtot; j++, v1++, v2++) {
 168                                 if (len_v3v3(v1->co, v2->co) > thresh)
 169                                         return MESHCMP_VERTCOMISMATCH;
 170                                 /* I don't care about normals, let's just do coodinates */
 171                         }
 172                 }
 173
 174                 /*we're order-agnostic for edges here*/
 175                 if (l1->type == CD_MEDGE) {
 176                         MEdge *e1 = l1->data;
 177                         MEdge *e2 = l2->data;
 178                         EdgeHash *eh = BLI_edgehash_new();
 179                         int etot = m1->totedge;
 180
 181                         for (j = 0; j < etot; j++, e1++) {
 182                                 BLI_edgehash_insert(eh, e1->v1, e1->v2, e1);
 183                         }
 184
 185                         for (j = 0; j < etot; j++, e2++) {
 186                                 if (!BLI_edgehash_lookup(eh, e2->v1, e2->v2))
 187                                         return MESHCMP_EDGEUNKNOWN;
 188                         }
 189                         BLI_edgehash_free(eh, NULL);
 190                 }
 191
 192                 if (l1->type == CD_MPOLY) {
 193                         MPoly *p1 = l1->data;
 194                         MPoly *p2 = l2->data;
 195                         int ptot = m1->totpoly;
 196
 197                         for (j = 0; j < ptot; j++, p1++, p2++) {
 198                                 MLoop *lp1, *lp2;
 199                                 int k;
 200
 201                                 if (p1->totloop != p2->totloop)
 202                                         return MESHCMP_POLYMISMATCH;
 203
 204                                 lp1 = m1->mloop + p1->loopstart;
 205                                 lp2 = m2->mloop + p2->loopstart;
 206
 207                                 for (k = 0; k < p1->totloop; k++, lp1++, lp2++) {
 208                                         if (lp1->v != lp2->v)
 209                                                 return MESHCMP_POLYVERTMISMATCH;
 210                                 }
 211                         }
 212                 }
 213                 if (l1->type == CD_MLOOP) {
 214                         MLoop *lp1 = l1->data;
 215                         MLoop *lp2 = l2->data;
 216                         int ltot = m1->totloop;
 217
 218                         for (j = 0; j < ltot; j++, lp1++, lp2++) {
 219                                 if (lp1->v != lp2->v)
 220                                         return MESHCMP_LOOPMISMATCH;
 221                         }
 222                 }
 223                 if (l1->type == CD_MLOOPUV) {
 224                         MLoopUV *lp1 = l1->data;
 225                         MLoopUV *lp2 = l2->data;
 226                         int ltot = m1->totloop;
 227
 228                         for (j = 0; j < ltot; j++, lp1++, lp2++) {
 229                                 if (len_v2v2(lp1->uv, lp2->uv) > thresh)
 230                                         return MESHCMP_LOOPUVMISMATCH;
 231                         }
 232                 }
 233
 234                 if (l1->type == CD_MLOOPCOL) {
 235                         MLoopCol *lp1 = l1->data;
 236                         MLoopCol *lp2 = l2->data;
 237                         int ltot = m1->totloop;
 238
 239                         for (j = 0; j < ltot; j++, lp1++, lp2++) {
 240                                 if (ABS(lp1->r - lp2->r) > thresh ||
 241                                     ABS(lp1->g - lp2->g) > thresh ||
 242                                     ABS(lp1->b - lp2->b) > thresh ||
 243                                     ABS(lp1->a - lp2->a) > thresh)
 244                                 {
 245                                         return MESHCMP_LOOPCOLMISMATCH;
 246                                 }
 247                         }
 248                 }
 249
 250                 if (l1->type == CD_MDEFORMVERT) {
 251                         MDeformVert *dv1 = l1->data;
 252                         MDeformVert *dv2 = l2->data;
 253                         int dvtot = m1->totvert;
 254
 255                         for (j = 0; j < dvtot; j++, dv1++, dv2++) {
 256                                 int k;
 257                                 MDeformWeight *dw1 = dv1->dw, *dw2 = dv2->dw;
 258
 259                                 if (dv1->totweight != dv2->totweight)
 260                                         return MESHCMP_DVERT_TOTGROUPMISMATCH;
 261
 262                                 for (k = 0; k < dv1->totweight; k++, dw1++, dw2++) {
 263                                         if (dw1->def_nr != dw2->def_nr)
 264                                                 return MESHCMP_DVERT_GROUPMISMATCH;
 265                                         if (ABS(dw1->weight - dw2->weight) > thresh)
 266                                                 return MESHCMP_DVERT_WEIGHTMISMATCH;
 267                                 }
 268                         }
 269                 }
 270         }
 271
 272         return 0;
 273 }
 274
 275 /*used for testing.  returns an error string the two meshes don't match*/
 276 const char *BKE_mesh_cmp(Mesh *me1, Mesh *me2, float thresh)
 277 {
 278         int c;
 279
 280         if (!me1 || !me2)
 281                 return "Requires two input meshes";
 282
 283         if (me1->totvert != me2->totvert)
 284                 return "Number of verts don't match";
 285
 286         if (me1->totedge != me2->totedge)
 287                 return "Number of edges don't match";
 288
 289         if (me1->totpoly != me2->totpoly)
 290                 return "Number of faces don't match";
 291
 292         if (me1->totloop != me2->totloop)
 293                 return "Number of loops don't match";
 294
 295         if ((c = customdata_compare(&me1->vdata, &me2->vdata, me1, me2, thresh)))
 296                 return cmpcode_to_str(c);
 297
 298         if ((c = customdata_compare(&me1->edata, &me2->edata, me1, me2, thresh)))
 299                 return cmpcode_to_str(c);
 300
 301         if ((c = customdata_compare(&me1->ldata, &me2->ldata, me1, me2, thresh)))
 302                 return cmpcode_to_str(c);
 303
 304         if ((c = customdata_compare(&me1->pdata, &me2->pdata, me1, me2, thresh)))
 305                 return cmpcode_to_str(c);
 306
 307         return NULL;
 308 }
 309
 310 static void mesh_ensure_tessellation_customdata(Mesh *me)
 311 {
 312         if (UNLIKELY((me->totface != 0) && (me->totpoly == 0))) {
 313                 /* Pass, otherwise this function  clears 'mface' before
 314                  * versioning 'mface -> mpoly' code kicks in [#30583]
 315                  *
 316                  * Callers could also check but safer to do here - campbell */
 317         }
 318         else {
 319                 const int tottex_original = CustomData_number_of_layers(&me->pdata, CD_MTEXPOLY);
 320                 const int totcol_original = CustomData_number_of_layers(&me->ldata, CD_MLOOPCOL);
 321
 322                 const int tottex_tessface = CustomData_number_of_layers(&me->fdata, CD_MTFACE);
 323                 const int totcol_tessface = CustomData_number_of_layers(&me->fdata, CD_MCOL);
 324
 325                 if (tottex_tessface != tottex_original ||
 326                     totcol_tessface != totcol_original)
 327                 {
 328                         BKE_mesh_tessface_clear(me);
 329
 330                         CustomData_from_bmeshpoly(&me->fdata, &me->pdata, &me->ldata, me->totface);
 331
 332                         /* TODO - add some --debug-mesh option */
 333                         if (G.debug & G_DEBUG) {
 334                                 /* note: this warning may be un-called for if we are initializing the mesh for the
 335                                  * first time from bmesh, rather then giving a warning about this we could be smarter
 336                                  * and check if there was any data to begin with, for now just print the warning with
 337                                  * some info to help troubleshoot whats going on - campbell */
 338                                 printf("%s: warning! Tessellation uvs or vcol data got out of sync, "
 339                                        "had to reset!\n    CD_MTFACE: %d != CD_MTEXPOLY: %d || CD_MCOL: %d != CD_MLOOPCOL: %d\n",
 340                                        __func__, tottex_tessface, tottex_original, totcol_tessface, totcol_original);
 341                         }
 342                 }
 343         }
 344 }
 345
 346 /* this ensures grouped customdata (e.g. mtexpoly and mloopuv and mtface, or
 347  * mloopcol and mcol) have the same relative active/render/clone/mask indices.
 348  *
 349  * note that for undo mesh data we want to skip 'ensure_tess_cd' call since
 350  * we don't want to store memory for tessface when its only used for older
 351  * versions of the mesh. - campbell*/
 352 static void mesh_update_linked_customdata(Mesh *me, const short do_ensure_tess_cd)
 353 {
 354         if (me->edit_btmesh)
 355                 BMEdit_UpdateLinkedCustomData(me->edit_btmesh);
 356
 357         if (do_ensure_tess_cd) {
 358                 mesh_ensure_tessellation_customdata(me);
 359         }
 360
 361         CustomData_bmesh_update_active_layers(&me->fdata, &me->pdata, &me->ldata);
 362 }
 363
 364 void mesh_update_customdata_pointers(Mesh *me, const short do_ensure_tess_cd)
 365 {
 366         mesh_update_linked_customdata(me, do_ensure_tess_cd);
 367
 368         me->mvert = CustomData_get_layer(&me->vdata, CD_MVERT);
 369         me->dvert = CustomData_get_layer(&me->vdata, CD_MDEFORMVERT);
 370
 371         me->medge = CustomData_get_layer(&me->edata, CD_MEDGE);
 372
 373         me->mface = CustomData_get_layer(&me->fdata, CD_MFACE);
 374         me->mcol = CustomData_get_layer(&me->fdata, CD_MCOL);
 375         me->mtface = CustomData_get_layer(&me->fdata, CD_MTFACE);
 376
 377         me->mpoly = CustomData_get_layer(&me->pdata, CD_MPOLY);
 378         me->mloop = CustomData_get_layer(&me->ldata, CD_MLOOP);
 379
 380         me->mtpoly = CustomData_get_layer(&me->pdata, CD_MTEXPOLY);
 381         me->mloopcol = CustomData_get_layer(&me->ldata, CD_MLOOPCOL);
 382         me->mloopuv = CustomData_get_layer(&me->ldata, CD_MLOOPUV);
 383 }
 384
 385 /* Note: unlinking is called when me->id.us is 0, question remains how
 386  * much unlinking of Library data in Mesh should be done... probably
 387  * we need a more generic method, like the expand() functions in
 388  * readfile.c */
 389
 390 void BKE_mesh_unlink(Mesh *me)
 391 {
 392         int a;
 393
 394         if (me == NULL) return;
 395
 396         if (me->mat)
 397         for (a = 0; a < me->totcol; a++) {
 398                 if (me->mat[a]) me->mat[a]->id.us--;
 399                 me->mat[a] = NULL;
 400         }
 401
 402         if (me->key) {
 403                 me->key->id.us--;
 404         }
 405         me->key = NULL;
 406
 407         if (me->texcomesh) me->texcomesh = NULL;
 408 }
 409
 410 /* do not free mesh itself */
 411 void BKE_mesh_free(Mesh *me, int unlink)
 412 {
 413         if (unlink)
 414                 BKE_mesh_unlink(me);
 415
 416         CustomData_free(&me->vdata, me->totvert);
 417         CustomData_free(&me->edata, me->totedge);
 418         CustomData_free(&me->fdata, me->totface);
 419         CustomData_free(&me->ldata, me->totloop);
 420         CustomData_free(&me->pdata, me->totpoly);
 421
 422         if (me->adt) {
 423                 BKE_free_animdata(&me->id);
 424                 me->adt = NULL;
 425         }
 426
 427         if (me->mat) MEM_freeN(me->mat);
 428
 429         if (me->bb) MEM_freeN(me->bb);
 430         if (me->mselect) MEM_freeN(me->mselect);
 431         if (me->edit_btmesh) MEM_freeN(me->edit_btmesh);
 432 }
 433
 434 void copy_dverts(MDeformVert *dst, MDeformVert *src, int copycount)
 435 {
 436         /* Assumes dst is already set up */
 437         int i;
 438
 439         if (!src || !dst)
 440                 return;
 441
 442         memcpy(dst, src, copycount * sizeof(MDeformVert));
 443
 444         for (i = 0; i < copycount; i++) {
 445                 if (src[i].dw) {
 446                         dst[i].dw = MEM_callocN(sizeof(MDeformWeight) * src[i].totweight, "copy_deformWeight");
 447                         memcpy(dst[i].dw, src[i].dw, sizeof(MDeformWeight) * src[i].totweight);
 448                 }
 449         }
 450
 451 }
 452
 453 void free_dverts(MDeformVert *dvert, int totvert)
 454 {
 455         /* Instead of freeing the verts directly,
 456          * call this function to delete any special
 457          * vert data */
 458         int i;
 459
 460         if (!dvert)
 461                 return;
 462
 463         /* Free any special data from the verts */
 464         for (i = 0; i < totvert; i++) {
 465                 if (dvert[i].dw) MEM_freeN(dvert[i].dw);
 466         }
 467         MEM_freeN(dvert);
 468 }
 469
 470 static void mesh_tessface_clear_intern(Mesh *mesh, int free_customdata)
 471 {
 472         if (free_customdata)
 473                 CustomData_free(&mesh->fdata, mesh->totface);
 474
 475         mesh->mface = NULL;
 476         mesh->mtface = NULL;
 477         mesh->mcol = NULL;
 478         mesh->totface = 0;
 479
 480         memset(&mesh->fdata, 0, sizeof(mesh->fdata));
 481 }
 482
 483 Mesh *BKE_mesh_add(const char *name)
 484 {
 485         Mesh *me;
 486
 487         me = BKE_libblock_alloc(&G.main->mesh, ID_ME, name);
 488
 489         me->size[0] = me->size[1] = me->size[2] = 1.0;
 490         me->smoothresh = 30;
 491         me->texflag = ME_AUTOSPACE;
 492         me->flag = ME_TWOSIDED;
 493         me->drawflag = ME_DRAWEDGES | ME_DRAWFACES | ME_DRAWCREASES;
 494
 495         return me;
 496 }
 497
 498 Mesh *BKE_mesh_copy(Mesh *me)
 499 {
 500         Mesh *men;
 501         MTFace *tface;
 502         MTexPoly *txface;
 503         int a, i;
 504         const int do_tessface = ((me->totface != 0) && (me->totpoly == 0)); /* only do tessface if we have no polys */
 505
 506         men = BKE_libblock_copy(&me->id);
 507
 508         men->mat = MEM_dupallocN(me->mat);
 509         for (a = 0; a < men->totcol; a++) {
 510                 id_us_plus((ID *)men->mat[a]);
 511         }
 512         id_us_plus((ID *)men->texcomesh);
 513
 514         CustomData_copy(&me->vdata, &men->vdata, CD_MASK_MESH, CD_DUPLICATE, men->totvert);
 515         CustomData_copy(&me->edata, &men->edata, CD_MASK_MESH, CD_DUPLICATE, men->totedge);
 516         CustomData_copy(&me->ldata, &men->ldata, CD_MASK_MESH, CD_DUPLICATE, men->totloop);
 517         CustomData_copy(&me->pdata, &men->pdata, CD_MASK_MESH, CD_DUPLICATE, men->totpoly);
 518         if (do_tessface) {
 519                 CustomData_copy(&me->fdata, &men->fdata, CD_MASK_MESH, CD_DUPLICATE, men->totface);
 520         }
 521         else {
 522                 mesh_tessface_clear_intern(men, FALSE);
 523         }
 524
 525         mesh_update_customdata_pointers(men, do_tessface);
 526
 527         /* ensure indirect linked data becomes lib-extern */
 528         for (i = 0; i < me->fdata.totlayer; i++) {
 529                 if (me->fdata.layers[i].type == CD_MTFACE) {
 530                         tface = (MTFace *)me->fdata.layers[i].data;
 531
 532                         for (a = 0; a < me->totface; a++, tface++)
 533                                 if (tface->tpage)
 534                                         id_lib_extern((ID *)tface->tpage);
 535                 }
 536         }
 537
 538         for (i = 0; i < me->pdata.totlayer; i++) {
 539                 if (me->pdata.layers[i].type == CD_MTEXPOLY) {
 540                         txface = (MTexPoly *)me->pdata.layers[i].data;
 541
 542                         for (a = 0; a < me->totpoly; a++, txface++)
 543                                 if (txface->tpage)
 544                                         id_lib_extern((ID *)txface->tpage);
 545                 }
 546         }
 547
 548         men->mselect = NULL;
 549         men->edit_btmesh = NULL;
 550
 551         men->bb = MEM_dupallocN(men->bb);
 552
 553         men->key = BKE_key_copy(me->key);
 554         if (men->key) men->key->from = (ID *)men;
 555
 556         return men;
 557 }
 558
 559 BMesh *BKE_mesh_to_bmesh(Mesh *me, Object *ob)
 560 {
 561         BMesh *bm;
 562
 563         bm = BM_mesh_create(&bm_mesh_allocsize_default);
 564
 565         BM_mesh_bm_from_me(bm, me, TRUE, ob->shapenr);
 566
 567         return bm;
 568 }
 569
 570 static void expand_local_mesh(Mesh *me)
 571 {
 572         id_lib_extern((ID *)me->texcomesh);
 573
 574         if (me->mtface || me->mtpoly) {
 575                 int a, i;
 576
 577                 for (i = 0; i < me->pdata.totlayer; i++) {
 578                         if (me->pdata.layers[i].type == CD_MTEXPOLY) {
 579                                 MTexPoly *txface = (MTexPoly *)me->pdata.layers[i].data;
 580
 581                                 for (a = 0; a < me->totpoly; a++, txface++) {
 582                                         /* special case: ima always local immediately */
 583                                         if (txface->tpage) {
 584                                                 id_lib_extern((ID *)txface->tpage);
 585                                         }
 586                                 }
 587                         }
 588                 }
 589
 590                 for (i = 0; i < me->fdata.totlayer; i++) {
 591                         if (me->fdata.layers[i].type == CD_MTFACE) {
 592                                 MTFace *tface = (MTFace *)me->fdata.layers[i].data;
 593
 594                                 for (a = 0; a < me->totface; a++, tface++) {
 595                                         /* special case: ima always local immediately */
 596                                         if (tface->tpage) {
 597                                                 id_lib_extern((ID *)tface->tpage);
 598                                         }
 599                                 }
 600                         }
 601                 }
 602         }
 603
 604         if (me->mat) {
 605                 extern_local_matarar(me->mat, me->totcol);
 606         }
 607 }
 608
 609 void BKE_mesh_make_local(Mesh *me)
 610 {
 611         Main *bmain = G.main;
 612         Object *ob;
 613         int is_local = FALSE, is_lib = FALSE;
 614
 615         /* - only lib users: do nothing
 616          * - only local users: set flag
 617          * - mixed: make copy
 618          */
 619
 620         if (me->id.lib == NULL) return;
 621         if (me->id.us == 1) {
 622                 id_clear_lib_data(bmain, &me->id);
 623                 expand_local_mesh(me);
 624                 return;
 625         }
 626
 627         for (ob = bmain->object.first; ob && ELEM(0, is_lib, is_local); ob = ob->id.next) {
 628                 if (me == ob->data) {
 629                         if (ob->id.lib) is_lib = TRUE;
 630                         else is_local = TRUE;
 631                 }
 632         }
 633
 634         if (is_local && is_lib == FALSE) {
 635                 id_clear_lib_data(bmain, &me->id);
 636                 expand_local_mesh(me);
 637         }
 638         else if (is_local && is_lib) {
 639                 Mesh *me_new = BKE_mesh_copy(me);
 640                 me_new->id.us = 0;
 641
 642
 643                 /* Remap paths of new ID using old library as base. */
 644                 BKE_id_lib_local_paths(bmain, me->id.lib, &me_new->id);
 645
 646                 for (ob = bmain->object.first; ob; ob = ob->id.next) {
 647                         if (me == ob->data) {
 648                                 if (ob->id.lib == NULL) {
 649                                         set_mesh(ob, me_new);
 650                                 }
 651                         }
 652                 }
 653         }
 654 }
 655
 656 void BKE_mesh_boundbox_calc(Mesh *me, float r_loc[3], float r_size[3])
 657 {
 658         BoundBox *bb;
 659         float min[3], max[3];
 660         float mloc[3], msize[3];
 661
 662         if (me->bb == NULL) me->bb = MEM_callocN(sizeof(BoundBox), "boundbox");
 663         bb = me->bb;
 664
 665         if (!r_loc) r_loc = mloc;
 666         if (!r_size) r_size = msize;
 667
 668         INIT_MINMAX(min, max);
 669         if (!BKE_mesh_minmax(me, min, max)) {
 670                 min[0] = min[1] = min[2] = -1.0f;
 671                 max[0] = max[1] = max[2] = 1.0f;
 672         }
 673
 674         mid_v3_v3v3(r_loc, min, max);
 675
 676         r_size[0] = (max[0] - min[0]) / 2.0f;
 677         r_size[1] = (max[1] - min[1]) / 2.0f;
 678         r_size[2] = (max[2] - min[2]) / 2.0f;
 679
 680         BKE_boundbox_init_from_minmax(bb, min, max);
 681 }
 682
 683 void BKE_mesh_texspace_calc(Mesh *me)
 684 {
 685         float loc[3], size[3];
 686         int a;
 687
 688         BKE_mesh_boundbox_calc(me, loc, size);
 689
 690         if (me->texflag & ME_AUTOSPACE) {
 691                 for (a = 0; a < 3; a++) {
 692                         if (size[a] == 0.0f) size[a] = 1.0f;
 693                         else if (size[a] > 0.0f && size[a] < 0.00001f) size[a] = 0.00001f;
 694                         else if (size[a] < 0.0f && size[a] > -0.00001f) size[a] = -0.00001f;
 695                 }
 696
 697                 copy_v3_v3(me->loc, loc);
 698                 copy_v3_v3(me->size, size);
 699                 zero_v3(me->rot);
 700         }
 701 }
 702
 703 BoundBox *BKE_mesh_boundbox_get(Object *ob)
 704 {
 705         Mesh *me = ob->data;
 706
 707         if (ob->bb)
 708                 return ob->bb;
 709
 710         if (!me->bb)
 711                 BKE_mesh_texspace_calc(me);
 712
 713         return me->bb;
 714 }
 715
 716 void BKE_mesh_texspace_get(Mesh *me, float r_loc[3], float r_rot[3], float r_size[3])
 717 {
 718         if (!me->bb) {
 719                 BKE_mesh_texspace_calc(me);
 720         }
 721
 722         if (r_loc) copy_v3_v3(r_loc,  me->loc);
 723         if (r_rot) copy_v3_v3(r_rot,  me->rot);
 724         if (r_size) copy_v3_v3(r_size, me->size);
 725 }
 726
 727 float *BKE_mesh_orco_verts_get(Object *ob)
 728 {
 729         Mesh *me = ob->data;
 730         MVert *mvert = NULL;
 731         Mesh *tme = me->texcomesh ? me->texcomesh : me;
 732         int a, totvert;
 733         float (*vcos)[3] = NULL;
 734
 735         /* Get appropriate vertex coordinates */
 736         vcos = MEM_callocN(sizeof(*vcos) * me->totvert, "orco mesh");
 737         mvert = tme->mvert;
 738         totvert = MIN2(tme->totvert, me->totvert);
 739
 740         for (a = 0; a < totvert; a++, mvert++) {
 741                 copy_v3_v3(vcos[a], mvert->co);
 742         }
 743
 744         return (float *)vcos;
 745 }
 746
 747 void BKE_mesh_orco_verts_transform(Mesh *me, float (*orco)[3], int totvert, int invert)
 748 {
 749         float loc[3], size[3];
 750         int a;
 751
 752         BKE_mesh_texspace_get(me->texcomesh ? me->texcomesh : me, loc, NULL, size);
 753
 754         if (invert) {
 755                 for (a = 0; a < totvert; a++) {
 756                         float *co = orco[a];
 757                         madd_v3_v3v3v3(co, loc, co, size);
 758                 }
 759         }
 760         else {
 761                 for (a = 0; a < totvert; a++) {
 762                         float *co = orco[a];
 763                         co[0] = (co[0] - loc[0]) / size[0];
 764                         co[1] = (co[1] - loc[1]) / size[1];
 765                         co[2] = (co[2] - loc[2]) / size[2];
 766                 }
 767         }
 768 }
 769
 770 /* rotates the vertices of a face in case v[2] or v[3] (vertex index) is = 0.
 771  * this is necessary to make the if (mface->v4) check for quads work */
 772 int test_index_face(MFace *mface, CustomData *fdata, int mfindex, int nr)
 773 {
 774         /* first test if the face is legal */
 775         if ((mface->v3 || nr == 4) && mface->v3 == mface->v4) {
 776                 mface->v4 = 0;
 777                 nr--;
 778         }
 779         if ((mface->v2 || mface->v4) && mface->v2 == mface->v3) {
 780                 mface->v3 = mface->v4;
 781                 mface->v4 = 0;
 782                 nr--;
 783         }
 784         if (mface->v1 == mface->v2) {
 785                 mface->v2 = mface->v3;
 786                 mface->v3 = mface->v4;
 787                 mface->v4 = 0;
 788                 nr--;
 789         }
 790
 791         /* check corrupt cases, bow-tie geometry, cant handle these because edge data wont exist so just return 0 */
 792         if (nr == 3) {
 793                 if (
 794                     /* real edges */
 795                     mface->v1 == mface->v2 ||
 796                     mface->v2 == mface->v3 ||
 797                     mface->v3 == mface->v1)
 798                 {
 799                         return 0;
 800                 }
 801         }
 802         else if (nr == 4) {
 803                 if (
 804                     /* real edges */
 805                     mface->v1 == mface->v2 ||
 806                     mface->v2 == mface->v3 ||
 807                     mface->v3 == mface->v4 ||
 808                     mface->v4 == mface->v1 ||
 809                     /* across the face */
 810                     mface->v1 == mface->v3 ||
 811                     mface->v2 == mface->v4)
 812                 {
 813                         return 0;
 814                 }
 815         }
 816
 817         /* prevent a zero at wrong index location */
 818         if (nr == 3) {
 819                 if (mface->v3 == 0) {
 820                         static int corner_indices[4] = {1, 2, 0, 3};
 821
 822                         SWAP(unsigned int, mface->v1, mface->v2);
 823                         SWAP(unsigned int, mface->v2, mface->v3);
 824
 825                         if (fdata)
 826                                 CustomData_swap(fdata, mfindex, corner_indices);
 827                 }
 828         }
 829         else if (nr == 4) {
 830                 if (mface->v3 == 0 || mface->v4 == 0) {
 831                         static int corner_indices[4] = {2, 3, 0, 1};
 832
 833                         SWAP(unsigned int, mface->v1, mface->v3);
 834                         SWAP(unsigned int, mface->v2, mface->v4);
 835
 836                         if (fdata)
 837                                 CustomData_swap(fdata, mfindex, corner_indices);
 838                 }
 839         }
 840
 841         return nr;
 842 }
 843
 844 Mesh *BKE_mesh_from_object(Object *ob)
 845 {
 846
 847         if (ob == NULL) return NULL;
 848         if (ob->type == OB_MESH) return ob->data;
 849         else return NULL;
 850 }
 851
 852 void set_mesh(Object *ob, Mesh *me)
 853 {
 854         Mesh *old = NULL;
 855
 856         multires_force_update(ob);
 857
 858         if (ob == NULL) return;
 859
 860         if (ob->type == OB_MESH) {
 861                 old = ob->data;
 862                 if (old)
 863                         old->id.us--;
 864                 ob->data = me;
 865                 id_us_plus((ID *)me);
 866         }
 867
 868         test_object_materials((ID *)me);
 869
 870         test_object_modifiers(ob);
 871 }
 872
 873 /* ************** make edges in a Mesh, for outside of editmode */
 874
 875 struct edgesort {
 876         unsigned int v1, v2;
 877         short is_loose, is_draw;
 878 };
 879
 880 /* edges have to be added with lowest index first for sorting */
 881 static void to_edgesort(struct edgesort *ed,
 882                         unsigned int v1, unsigned int v2,
 883                         short is_loose, short is_draw)
 884 {
 885         if (v1 < v2) {
 886                 ed->v1 = v1; ed->v2 = v2;
 887         }
 888         else {
 889                 ed->v1 = v2; ed->v2 = v1;
 890         }
 891         ed->is_loose = is_loose;
 892         ed->is_draw = is_draw;
 893 }
 894
 895 static int vergedgesort(const void *v1, const void *v2)
 896 {
 897         const struct edgesort *x1 = v1, *x2 = v2;
 898
 899         if (x1->v1 > x2->v1) return 1;
 900         else if (x1->v1 < x2->v1) return -1;
 901         else if (x1->v2 > x2->v2) return 1;
 902         else if (x1->v2 < x2->v2) return -1;
 903
 904         return 0;
 905 }
 906
 907
 908 /* Create edges based on known verts and faces */
 909 static void make_edges_mdata(MVert *UNUSED(allvert), MFace *allface, MLoop *allloop,
 910                              MPoly *allpoly, int UNUSED(totvert), int totface, int UNUSED(totloop), int totpoly,
 911                              int old, MEdge **alledge, int *_totedge)
 912 {
 913         MPoly *mpoly;
 914         MLoop *mloop;
 915         MFace *mface;
 916         MEdge *medge;
 917         EdgeHash *hash = BLI_edgehash_new();
 918         struct edgesort *edsort, *ed;
 919         int a, b, totedge = 0, final = 0;
 920
 921         /* we put all edges in array, sort them, and detect doubles that way */
 922
 923         for (a = totface, mface = allface; a > 0; a--, mface++) {
 924                 if (mface->v4) totedge += 4;
 925                 else if (mface->v3) totedge += 3;
 926                 else totedge += 1;
 927         }
 928
 929         if (totedge == 0) {
 930                 /* flag that mesh has edges */
 931                 (*alledge) = MEM_callocN(0, "make mesh edges");
 932                 (*_totedge) = 0;
 933                 return;
 934         }
 935
 936         ed = edsort = MEM_mallocN(totedge * sizeof(struct edgesort), "edgesort");
 937
 938         for (a = totface, mface = allface; a > 0; a--, mface++) {
 939                 to_edgesort(ed++, mface->v1, mface->v2, !mface->v3, mface->edcode & ME_V1V2);
 940                 if (mface->v4) {
 941                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
 942                         to_edgesort(ed++, mface->v3, mface->v4, 0, mface->edcode & ME_V3V4);
 943                         to_edgesort(ed++, mface->v4, mface->v1, 0, mface->edcode & ME_V4V1);
 944                 }
 945                 else if (mface->v3) {
 946                         to_edgesort(ed++, mface->v2, mface->v3, 0, mface->edcode & ME_V2V3);
 947                         to_edgesort(ed++, mface->v3, mface->v1, 0, mface->edcode & ME_V3V1);
 948                 }
 949         }
 950
 951         qsort(edsort, totedge, sizeof(struct edgesort), vergedgesort);
 952
 953         /* count final amount */
 954         for (a = totedge, ed = edsort; a > 1; a--, ed++) {
 955                 /* edge is unique when it differs from next edge, or is last */
 956                 if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) final++;
 957         }
 958         final++;
 959
 960         (*alledge) = medge = MEM_callocN(sizeof(MEdge) * final, "BKE_mesh_make_edges mdge");
 961         (*_totedge) = final;
 962
 963         for (a = totedge, ed = edsort; a > 1; a--, ed++) {
 964                 /* edge is unique when it differs from next edge, or is last */
 965                 if (ed->v1 != (ed + 1)->v1 || ed->v2 != (ed + 1)->v2) {
 966                         medge->v1 = ed->v1;
 967                         medge->v2 = ed->v2;
 968                         if (old == 0 || ed->is_draw) medge->flag = ME_EDGEDRAW | ME_EDGERENDER;
 969                         if (ed->is_loose) medge->flag |= ME_LOOSEEDGE;
 970
 971                         /* order is swapped so extruding this edge as a surface wont flip face normals
 972                          * with cyclic curves */
 973                         if (ed->v1 + 1 != ed->v2) {
 974                                 SWAP(unsigned int, medge->v1, medge->v2);
 975                         }
 976                         medge++;
 977                 }
 978                 else {
 979                         /* equal edge, we merge the drawflag */
 980                         (ed + 1)->is_draw |= ed->is_draw;
 981                 }
 982         }
 983         /* last edge */
 984         medge->v1 = ed->v1;
 985         medge->v2 = ed->v2;
 986         medge->flag = ME_EDGEDRAW;
 987         if (ed->is_loose) medge->flag |= ME_LOOSEEDGE;
 988         medge->flag |= ME_EDGERENDER;
 989
 990         MEM_freeN(edsort);
 991
 992         /* set edge members of mloops */
 993         medge = *alledge;
 994         for (a = 0; a < *_totedge; a++, medge++) {
 995                 BLI_edgehash_insert(hash, medge->v1, medge->v2, SET_INT_IN_POINTER(a));
 996         }
 997
 998         mpoly = allpoly;
 999         for (a = 0; a < totpoly; a++, mpoly++) {
1000                 mloop = allloop + mpoly->loopstart;
1001                 for (b = 0; b < mpoly->totloop; b++) {
1002                         int v1, v2;
1003
1004                         v1 = mloop[b].v;
1005                         v2 = ME_POLY_LOOP_NEXT(mloop, mpoly, b)->v;
1006                         mloop[b].e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(hash, v1, v2));
1007                 }
1008         }
1009
1010         BLI_edgehash_free(hash, NULL);
1011 }
1012
1013 void BKE_mesh_make_edges(Mesh *me, int old)
1014 {
1015         MEdge *medge;
1016         int totedge = 0;
1017
1018         make_edges_mdata(me->mvert, me->mface, me->mloop, me->mpoly, me->totvert, me->totface, me->totloop, me->totpoly, old, &medge, &totedge);
1019         if (totedge == 0) {
1020                 /* flag that mesh has edges */
1021                 me->medge = medge;
1022                 me->totedge = 0;
1023                 return;
1024         }
1025
1026         medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, totedge);
1027         me->medge = medge;
1028         me->totedge = totedge;
1029
1030         BKE_mesh_strip_loose_faces(me);
1031 }
1032
1033 /* We need to keep this for edge creation (for now?), and some old readfile code... */
1034 void BKE_mesh_strip_loose_faces(Mesh *me)
1035 {
1036         MFace *f;
1037         int a, b;
1038
1039         for (a = b = 0, f = me->mface; a < me->totface; a++, f++) {
1040                 if (f->v3) {
1041                         if (a != b) {
1042                                 memcpy(&me->mface[b], f, sizeof(me->mface[b]));
1043                                 CustomData_copy_data(&me->fdata, &me->fdata, a, b, 1);
1044                         }
1045                         b++;
1046                 }
1047         }
1048         if (a != b) {
1049                 CustomData_free_elem(&me->fdata, b, a - b);
1050                 me->totface = b;
1051         }
1052 }
1053
1054 /* Works on both loops and polys! */
1055 /* Note: It won't try to guess which loops of an invalid poly to remove!
1056  *       this is the work of the caller, to mark those loops...
1057  *       See e.g. BKE_mesh_validate_arrays(). */
1058 void BKE_mesh_strip_loose_polysloops(Mesh *me)
1059 {
1060         MPoly *p;
1061         MLoop *l;
1062         int a, b;
1063         /* New loops idx! */
1064         int *new_idx = MEM_mallocN(sizeof(int) * me->totloop, __func__);
1065
1066         for (a = b = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
1067                 int invalid = FALSE;
1068                 int i = p->loopstart;
1069                 int stop = i + p->totloop;
1070
1071                 if (stop > me->totloop || stop < i) {
1072                         invalid = TRUE;
1073                 }
1074                 else {
1075                         l = &me->mloop[i];
1076                         i = stop - i;
1077                         /* If one of the poly's loops is invalid, the whole poly is invalid! */
1078                         for (; i--; l++) {
1079                                 if (l->e == INVALID_LOOP_EDGE_MARKER) {
1080                                         invalid = TRUE;
1081                                         break;
1082                                 }
1083                         }
1084                 }
1085
1086                 if (p->totloop >= 3 && !invalid) {
1087                         if (a != b) {
1088                                 memcpy(&me->mpoly[b], p, sizeof(me->mpoly[b]));
1089                                 CustomData_copy_data(&me->pdata, &me->pdata, a, b, 1);
1090                         }
1091                         b++;
1092                 }
1093         }
1094         if (a != b) {
1095                 CustomData_free_elem(&me->pdata, b, a - b);
1096                 me->totpoly = b;
1097         }
1098
1099         /* And now, get rid of invalid loops. */
1100         for (a = b = 0, l = me->mloop; a < me->totloop; a++, l++) {
1101                 if (l->e != INVALID_LOOP_EDGE_MARKER) {
1102                         if (a != b) {
1103                                 memcpy(&me->mloop[b], l, sizeof(me->mloop[b]));
1104                                 CustomData_copy_data(&me->ldata, &me->ldata, a, b, 1);
1105                         }
1106                         new_idx[a] = b;
1107                         b++;
1108                 }
1109                 else {
1110                         /* XXX Theoretically, we should be able to not do this, as no remaining poly
1111                          *     should use any stripped loop. But for security's sake... */
1112                         new_idx[a] = -a;
1113                 }
1114         }
1115         if (a != b) {
1116                 CustomData_free_elem(&me->ldata, b, a - b);
1117                 me->totloop = b;
1118         }
1119
1120         /* And now, update polys' start loop index. */
1121         /* Note: At this point, there should never be any poly using a striped loop! */
1122         for (a = 0, p = me->mpoly; a < me->totpoly; a++, p++) {
1123                 p->loopstart = new_idx[p->loopstart];
1124         }
1125
1126         MEM_freeN(new_idx);
1127 }
1128
1129 void BKE_mesh_strip_loose_edges(Mesh *me)
1130 {
1131         MEdge *e;
1132         MLoop *l;
1133         int a, b;
1134         unsigned int *new_idx = MEM_mallocN(sizeof(int) * me->totedge, __func__);
1135
1136         for (a = b = 0, e = me->medge; a < me->totedge; a++, e++) {
1137                 if (e->v1 != e->v2) {
1138                         if (a != b) {
1139                                 memcpy(&me->medge[b], e, sizeof(me->medge[b]));
1140                                 CustomData_copy_data(&me->edata, &me->edata, a, b, 1);
1141                         }
1142                         new_idx[a] = b;
1143                         b++;
1144                 }
1145                 else {
1146                         new_idx[a] = INVALID_LOOP_EDGE_MARKER;
1147                 }
1148         }
1149         if (a != b) {
1150                 CustomData_free_elem(&me->edata, b, a - b);
1151                 me->totedge = b;
1152         }
1153
1154         /* And now, update loops' edge indices. */
1155         /* XXX We hope no loop was pointing to a striped edge!
1156          *     Else, its e will be set to INVALID_LOOP_EDGE_MARKER :/ */
1157         for (a = 0, l = me->mloop; a < me->totloop; a++, l++) {
1158                 l->e = new_idx[l->e];
1159         }
1160
1161         MEM_freeN(new_idx);
1162 }
1163
1164 void BKE_mesh_from_metaball(ListBase *lb, Mesh *me)
1165 {
1166         DispList *dl;
1167         MVert *mvert;
1168         MLoop *mloop, *allloop;
1169         MPoly *mpoly;
1170         float *nors, *verts;
1171         int a, *index;
1172
1173         dl = lb->first;
1174         if (dl == NULL) return;
1175
1176         if (dl->type == DL_INDEX4) {
1177                 mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_CALLOC, NULL, dl->nr);
1178                 allloop = mloop = CustomData_add_layer(&me->ldata, CD_MLOOP, CD_CALLOC, NULL, dl->parts * 4);
1179                 mpoly = CustomData_add_layer(&me->pdata, CD_MPOLY, CD_CALLOC, NULL, dl->parts);
1180                 me->mvert = mvert;
1181                 me->mloop = mloop;
1182                 me->mpoly = mpoly;
1183                 me->totvert = dl->nr;
1184                 me->totpoly = dl->parts;
1185
1186                 a = dl->nr;
1187                 nors = dl->nors;
1188                 verts = dl->verts;
1189                 while (a--) {
1190                         copy_v3_v3(mvert->co, verts);
1191                         normal_float_to_short_v3(mvert->no, nors);
1192                         mvert++;
1193                         nors += 3;
1194                         verts += 3;
1195                 }
1196
1197                 a = dl->parts;
1198                 index = dl->index;
1199                 while (a--) {
1200                         int count = index[2] != index[3] ? 4 : 3;
1201
1202                         mloop[0].v = index[0];
1203                         mloop[1].v = index[1];
1204                         mloop[2].v = index[2];
1205                         if (count == 4)
1206                                 mloop[3].v = index[3];
1207
1208                         mpoly->totloop = count;
1209                         mpoly->loopstart = (int)(mloop - allloop);
1210                         mpoly->flag = ME_SMOOTH;
1211
1212
1213                         mpoly++;
1214                         mloop += count;
1215                         me->totloop += count;
1216                         index += 4;
1217                 }
1218
1219                 mesh_update_customdata_pointers(me, TRUE);
1220
1221                 BKE_mesh_calc_normals(me->mvert, me->totvert, me->mloop, me->mpoly, me->totloop, me->totpoly, NULL);
1222
1223                 BKE_mesh_calc_edges(me, TRUE);
1224         }
1225 }
1226
1227 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
1228 /* return non-zero on error */
1229 int BKE_mesh_nurbs_to_mdata(Object *ob, MVert **allvert, int *totvert,
1230                             MEdge **alledge, int *totedge, MLoop **allloop, MPoly **allpoly,
1231                             int *totloop, int *totpoly)
1232 {
1233         return BKE_mesh_nurbs_displist_to_mdata(ob, &ob->disp,
1234                                                 allvert, totvert,
1235                                                 alledge, totedge,
1236                                                 allloop, allpoly,
1237                                                 totloop, totpoly, NULL);
1238 }
1239
1240 /* BMESH: this doesn't calculate all edges from polygons,
1241  * only free standing edges are calculated */
1242
1243 /* Initialize mverts, medges and, faces for converting nurbs to mesh and derived mesh */
1244 /* use specified dispbase */
1245 /* TODO: orco values for non DL_SURF types */
1246 int BKE_mesh_nurbs_displist_to_mdata(Object *ob, ListBase *dispbase,
1247                                      MVert **allvert, int *_totvert,
1248                                      MEdge **alledge, int *_totedge,
1249                                      MLoop **allloop, MPoly **allpoly,
1250                                      int *_totloop, int *_totpoly,
1251                                      int **orco_index_ptr)
1252 {
1253         DispList *dl;
1254         Curve *cu;
1255         MVert *mvert;
1256         MPoly *mpoly;
1257         MLoop *mloop;
1258         MEdge *medge;
1259         float *data;
1260         int a, b, ofs, vertcount, startvert, totvert = 0, totedge = 0, totloop = 0, totvlak = 0;
1261         int p1, p2, p3, p4, *index;
1262         int conv_polys = 0;
1263         int (*orco_index)[4] = NULL;
1264
1265         cu = ob->data;
1266
1267         conv_polys |= cu->flag & CU_3D;      /* 2d polys are filled with DL_INDEX3 displists */
1268         conv_polys |= ob->type == OB_SURF;   /* surf polys are never filled */
1269
1270         /* count */
1271         dl = dispbase->first;
1272         while (dl) {
1273                 if (dl->type == DL_SEGM) {
1274                         totvert += dl->parts * dl->nr;
1275                         totedge += dl->parts * (dl->nr - 1);
1276                 }
1277                 else if (dl->type == DL_POLY) {
1278                         if (conv_polys) {
1279                                 totvert += dl->parts * dl->nr;
1280                                 totedge += dl->parts * dl->nr;
1281                         }
1282                 }
1283                 else if (dl->type == DL_SURF) {
1284                         int tot;
1285                         totvert += dl->parts * dl->nr;
1286                         tot = (dl->parts - 1 + ((dl->flag & DL_CYCL_V) == 2)) * (dl->nr - 1 + (dl->flag & DL_CYCL_U));
1287                         totvlak += tot;
1288                         totloop += tot * 4;
1289                 }
1290                 else if (dl->type == DL_INDEX3) {
1291                         int tot;
1292                         totvert += dl->nr;
1293                         tot = dl->parts;
1294                         totvlak += tot;
1295                         totloop += tot * 3;
1296                 }
1297                 dl = dl->next;
1298         }
1299
1300         if (totvert == 0) {
1301                 /* error("can't convert"); */
1302                 /* Make Sure you check ob->data is a curve */
1303                 return -1;
1304         }
1305
1306         *allvert = mvert = MEM_callocN(sizeof(MVert) * totvert, "nurbs_init mvert");
1307         *alledge = medge = MEM_callocN(sizeof(MEdge) * totedge, "nurbs_init medge");
1308         *allloop = mloop = MEM_callocN(sizeof(MLoop) * totvlak * 4, "nurbs_init mloop"); // totloop
1309         *allpoly = mpoly = MEM_callocN(sizeof(MPoly) * totvlak, "nurbs_init mloop");
1310
1311         /* verts and faces */
1312         vertcount = 0;
1313
1314         if (orco_index_ptr) {
1315                 *orco_index_ptr = MEM_callocN(sizeof(int) * totvlak * 4, "nurbs_init orco");
1316                 orco_index = (int (*)[4]) *orco_index_ptr;
1317         }
1318
1319         dl = dispbase->first;
1320         while (dl) {
1321                 int smooth = dl->rt & CU_SMOOTH ? 1 : 0;
1322
1323                 if (dl->type == DL_SEGM) {
1324                         startvert = vertcount;
1325                         a = dl->parts * dl->nr;
1326                         data = dl->verts;
1327                         while (a--) {
1328                                 copy_v3_v3(mvert->co, data);
1329                                 data += 3;
1330                                 vertcount++;
1331                                 mvert++;
1332                         }
1333
1334                         for (a = 0; a < dl->parts; a++) {
1335                                 ofs = a * dl->nr;
1336                                 for (b = 1; b < dl->nr; b++) {
1337                                         medge->v1 = startvert + ofs + b - 1;
1338                                         medge->v2 = startvert + ofs + b;
1339                                         medge->flag = ME_LOOSEEDGE | ME_EDGERENDER | ME_EDGEDRAW;
1340
1341                                         medge++;
1342                                 }
1343                         }
1344
1345                 }
1346                 else if (dl->type == DL_POLY) {
1347                         if (conv_polys) {
1348                                 startvert = vertcount;
1349                                 a = dl->parts * dl->nr;
1350                                 data = dl->verts;
1351                                 while (a--) {
1352                                         copy_v3_v3(mvert->co, data);
1353                                         data += 3;
1354                                         vertcount++;
1355                                         mvert++;
1356                                 }
1357
1358                                 for (a = 0; a < dl->parts; a++) {
1359                                         ofs = a * dl->nr;
1360                                         for (b = 0; b < dl->nr; b++) {
1361                                                 medge->v1 = startvert + ofs + b;
1362                                                 if (b == dl->nr - 1) medge->v2 = startvert + ofs;
1363                                                 else medge->v2 = startvert + ofs + b + 1;
1364                                                 medge->flag = ME_LOOSEEDGE | ME_EDGERENDER | ME_EDGEDRAW;
1365                                                 medge++;
1366                                         }
1367                                 }
1368                         }
1369                 }
1370                 else if (dl->type == DL_INDEX3) {
1371                         startvert = vertcount;
1372                         a = dl->nr;
1373                         data = dl->verts;
1374                         while (a--) {
1375                                 copy_v3_v3(mvert->co, data);
1376                                 data += 3;
1377                                 vertcount++;
1378                                 mvert++;
1379                         }
1380
1381                         a = dl->parts;
1382                         index = dl->index;
1383                         while (a--) {
1384                                 mloop[0].v = startvert + index[0];
1385                                 mloop[1].v = startvert + index[2];
1386                                 mloop[2].v = startvert + index[1];
1387                                 mpoly->loopstart = (int)(mloop - (*allloop));
1388                                 mpoly->totloop = 3;
1389                                 mpoly->mat_nr = dl->col;
1390
1391                                 if (smooth) mpoly->flag |= ME_SMOOTH;
1392                                 mpoly++;
1393                                 mloop += 3;
1394                                 index += 3;
1395                         }
1396                 }
1397                 else if (dl->type == DL_SURF) {
1398                         startvert = vertcount;
1399                         a = dl->parts * dl->nr;
1400                         data = dl->verts;
1401                         while (a--) {
1402                                 copy_v3_v3(mvert->co, data);
1403                                 data += 3;
1404                                 vertcount++;
1405                                 mvert++;
1406                         }
1407
1408                         for (a = 0; a < dl->parts; a++) {
1409
1410                                 if ( (dl->flag & DL_CYCL_V) == 0 && a == dl->parts - 1) break;
1411
1412                                 if (dl->flag & DL_CYCL_U) {         /* p2 -> p1 -> */
1413                                         p1 = startvert + dl->nr * a;    /* p4 -> p3 -> */
1414                                         p2 = p1 + dl->nr - 1;       /* -----> next row */
1415                                         p3 = p1 + dl->nr;
1416                                         p4 = p2 + dl->nr;
1417                                         b = 0;
1418                                 }
1419                                 else {
1420                                         p2 = startvert + dl->nr * a;
1421                                         p1 = p2 + 1;
1422                                         p4 = p2 + dl->nr;
1423                                         p3 = p1 + dl->nr;
1424                                         b = 1;
1425                                 }
1426                                 if ( (dl->flag & DL_CYCL_V) && a == dl->parts - 1) {
1427                                         p3 -= dl->parts * dl->nr;
1428                                         p4 -= dl->parts * dl->nr;
1429                                 }
1430
1431                                 for (; b < dl->nr; b++) {
1432                                         mloop[0].v = p1;
1433                                         mloop[1].v = p3;
1434                                         mloop[2].v = p4;
1435                                         mloop[3].v = p2;
1436                                         mpoly->loopstart = (int)(mloop - (*allloop));
1437                                         mpoly->totloop = 4;
1438                                         mpoly->mat_nr = dl->col;
1439
1440                                         if (orco_index) {
1441                                                 const int poly_index = mpoly - *allpoly;
1442                                                 const int p_orco_base = startvert + ((dl->nr + 1) * a) + b;
1443                                                 orco_index[poly_index][0] = p_orco_base + 1;
1444                                                 orco_index[poly_index][1] = p_orco_base + dl->nr + 2;
1445                                                 orco_index[poly_index][2] = p_orco_base + dl->nr + 1;
1446                                                 orco_index[poly_index][3] = p_orco_base;
1447                                         }
1448
1449                                         if (smooth) mpoly->flag |= ME_SMOOTH;
1450                                         mpoly++;
1451                                         mloop += 4;
1452
1453                                         p4 = p3;
1454                                         p3++;
1455                                         p2 = p1;
1456                                         p1++;
1457                                 }
1458                         }
1459
1460                 }
1461
1462                 dl = dl->next;
1463         }
1464
1465         *_totpoly = totvlak;
1466         *_totloop = totloop;
1467         *_totedge = totedge;
1468         *_totvert = totvert;
1469
1470         /* not uded for bmesh */
1471 #if 0
1472         make_edges_mdata(*allvert, *allface, *allloop, *allpoly, totvert, totvlak, *_totloop, *_totpoly, 0, alledge, _totedge);
1473         mfaces_strip_loose(*allface, _totface);
1474 #endif
1475
1476         return 0;
1477 }
1478
1479
1480 MINLINE void copy_uv_orco_v2_v2(float r[2], const float a[2])
1481 {
1482         r[0] = 0.5f + a[0] * 0.5f;
1483         r[1] = 0.5f + a[1] * 0.5f;
1484 }
1485
1486 /**
1487  * orco is normally from #BKE_curve_make_orco
1488  */
1489 void BKE_mesh_nurbs_to_mdata_orco(MPoly *mpoly, int totpoly,
1490                                   MLoop *mloops, MLoopUV *mloopuvs,
1491                                   float (*orco)[3], int (*orco_index)[4])
1492 {
1493         MPoly *mp;
1494
1495         int i, j;
1496         for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
1497                 MLoop *ml = mloops + mp->loopstart;
1498                 MLoopUV *mluv = mloopuvs + mp->loopstart;
1499                 for (j = 0; j < mp->totloop; j++, ml++, mluv++) {
1500                         copy_uv_orco_v2_v2(mluv->uv, orco[orco_index[i][j]]);
1501                 }
1502         }
1503 }
1504
1505 /* this may fail replacing ob->data, be sure to check ob->type */
1506 void BKE_mesh_from_nurbs_displist(Object *ob, ListBase *dispbase, int **orco_index_ptr)
1507 {
1508         Main *bmain = G.main;
1509         Object *ob1;
1510         DerivedMesh *dm = ob->derivedFinal;
1511         Mesh *me;
1512         Curve *cu;
1513         MVert *allvert = NULL;
1514         MEdge *alledge = NULL;
1515         MLoop *allloop = NULL;
1516         MPoly *allpoly = NULL;
1517         int totvert, totedge, totloop, totpoly;
1518
1519         cu = ob->data;
1520
1521         if (dm == NULL) {
1522                 if (BKE_mesh_nurbs_displist_to_mdata(ob, dispbase, &allvert, &totvert,
1523                                                      &alledge, &totedge, &allloop,
1524                                                      &allpoly, &totloop, &totpoly, orco_index_ptr) != 0)
1525                 {
1526                         /* Error initializing */
1527                         return;
1528                 }
1529
1530                 /* make mesh */
1531                 me = BKE_mesh_add("Mesh");
1532                 me->totvert = totvert;
1533                 me->totedge = totedge;
1534                 me->totloop = totloop;
1535                 me->totpoly = totpoly;
1536
1537                 me->mvert = CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, allvert, me->totvert);
1538                 me->medge = CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, alledge, me->totedge);
1539                 me->mloop = CustomData_add_layer(&me->ldata, CD_MLOOP, CD_ASSIGN, allloop, me->totloop);
1540                 me->mpoly = CustomData_add_layer(&me->pdata, CD_MPOLY, CD_ASSIGN, allpoly, me->totpoly);
1541
1542                 BKE_mesh_calc_normals(me->mvert, me->totvert, me->mloop, me->mpoly, me->totloop, me->totpoly, NULL);
1543
1544                 BKE_mesh_calc_edges(me, TRUE);
1545         }
1546         else {
1547                 me = BKE_mesh_add("Mesh");
1548                 DM_to_mesh(dm, me, ob);
1549         }
1550
1551         me->totcol = cu->totcol;
1552         me->mat = cu->mat;
1553
1554         BKE_mesh_texspace_calc(me);
1555
1556         cu->mat = NULL;
1557         cu->totcol = 0;
1558
1559         if (ob->data) {
1560                 BKE_libblock_free(&bmain->curve, ob->data);
1561         }
1562         ob->data = me;
1563         ob->type = OB_MESH;
1564
1565         /* other users */
1566         ob1 = bmain->object.first;
1567         while (ob1) {
1568                 if (ob1->data == cu) {
1569                         ob1->type = OB_MESH;
1570
1571                         ob1->data = ob->data;
1572                         id_us_plus((ID *)ob->data);
1573                 }
1574                 ob1 = ob1->id.next;
1575         }
1576 }
1577
1578 void BKE_mesh_from_nurbs(Object *ob)
1579 {
1580         BKE_mesh_from_nurbs_displist(ob, &ob->disp, NULL);
1581 }
1582
1583 typedef struct EdgeLink {
1584         Link *next, *prev;
1585         void *edge;
1586 } EdgeLink;
1587
1588 typedef struct VertLink {
1589         Link *next, *prev;
1590         unsigned int index;
1591 } VertLink;
1592
1593 static void prependPolyLineVert(ListBase *lb, unsigned int index)
1594 {
1595         VertLink *vl = MEM_callocN(sizeof(VertLink), "VertLink");
1596         vl->index = index;
1597         BLI_addhead(lb, vl);
1598 }
1599
1600 static void appendPolyLineVert(ListBase *lb, unsigned int index)
1601 {
1602         VertLink *vl = MEM_callocN(sizeof(VertLink), "VertLink");
1603         vl->index = index;
1604         BLI_addtail(lb, vl);
1605 }
1606
1607 void BKE_mesh_from_curve(Scene *scene, Object *ob)
1608 {
1609         /* make new mesh data from the original copy */
1610         DerivedMesh *dm = mesh_get_derived_final(scene, ob, CD_MASK_MESH);
1611
1612         MVert *mverts = dm->getVertArray(dm);
1613         MEdge *med, *medge = dm->getEdgeArray(dm);
1614         MFace *mf,  *mface = dm->getTessFaceArray(dm);
1615
1616         int totedge = dm->getNumEdges(dm);
1617         int totface = dm->getNumTessFaces(dm);
1618         int totedges = 0;
1619         int i, needsFree = 0;
1620
1621         /* only to detect edge polylines */
1622         EdgeHash *eh = BLI_edgehash_new();
1623         EdgeHash *eh_edge = BLI_edgehash_new();
1624
1625
1626         ListBase edges = {NULL, NULL};
1627
1628         /* create edges from all faces (so as to find edges not in any faces) */
1629         mf = mface;
1630         for (i = 0; i < totface; i++, mf++) {
1631                 if (!BLI_edgehash_haskey(eh, mf->v1, mf->v2))
1632                         BLI_edgehash_insert(eh, mf->v1, mf->v2, NULL);
1633                 if (!BLI_edgehash_haskey(eh, mf->v2, mf->v3))
1634                         BLI_edgehash_insert(eh, mf->v2, mf->v3, NULL);
1635
1636                 if (mf->v4) {
1637                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v4))
1638                                 BLI_edgehash_insert(eh, mf->v3, mf->v4, NULL);
1639                         if (!BLI_edgehash_haskey(eh, mf->v4, mf->v1))
1640                                 BLI_edgehash_insert(eh, mf->v4, mf->v1, NULL);
1641                 }
1642                 else {
1643                         if (!BLI_edgehash_haskey(eh, mf->v3, mf->v1))
1644                                 BLI_edgehash_insert(eh, mf->v3, mf->v1, NULL);
1645                 }
1646         }
1647
1648         med = medge;
1649         for (i = 0; i < totedge; i++, med++) {
1650                 if (!BLI_edgehash_haskey(eh, med->v1, med->v2)) {
1651                         EdgeLink *edl = MEM_callocN(sizeof(EdgeLink), "EdgeLink");
1652
1653                         BLI_edgehash_insert(eh_edge, med->v1, med->v2, NULL);
1654                         edl->edge = med;
1655
1656                         BLI_addtail(&edges, edl);   totedges++;
1657                 }
1658         }
1659         BLI_edgehash_free(eh_edge, NULL);
1660         BLI_edgehash_free(eh, NULL);
1661
1662         if (edges.first) {
1663                 Curve *cu = BKE_curve_add(ob->id.name + 2, OB_CURVE);
1664                 cu->flag |= CU_3D;
1665
1666                 while (edges.first) {
1667                         /* each iteration find a polyline and add this as a nurbs poly spline */
1668
1669                         ListBase polyline = {NULL, NULL}; /* store a list of VertLink's */
1670                         int closed = FALSE;
1671                         int totpoly = 0;
1672                         MEdge *med_current = ((EdgeLink *)edges.last)->edge;
1673                         unsigned int startVert = med_current->v1;
1674                         unsigned int endVert = med_current->v2;
1675                         int ok = TRUE;
1676
1677                         appendPolyLineVert(&polyline, startVert);   totpoly++;
1678                         appendPolyLineVert(&polyline, endVert);     totpoly++;
1679                         BLI_freelinkN(&edges, edges.last);          totedges--;
1680
1681                         while (ok) { /* while connected edges are found... */
1682                                 ok = FALSE;
1683                                 i = totedges;
1684                                 while (i) {
1685                                         EdgeLink *edl;
1686
1687                                         i -= 1;
1688                                         edl = BLI_findlink(&edges, i);
1689                                         med = edl->edge;
1690
1691                                         if (med->v1 == endVert) {
1692                                                 endVert = med->v2;
1693                                                 appendPolyLineVert(&polyline, med->v2); totpoly++;
1694                                                 BLI_freelinkN(&edges, edl);             totedges--;
1695                                                 ok = TRUE;
1696                                         }
1697                                         else if (med->v2 == endVert) {
1698                                                 endVert = med->v1;
1699                                                 appendPolyLineVert(&polyline, endVert); totpoly++;
1700                                                 BLI_freelinkN(&edges, edl);             totedges--;
1701                                                 ok = TRUE;
1702                                         }
1703                                         else if (med->v1 == startVert) {
1704                                                 startVert = med->v2;
1705                                                 prependPolyLineVert(&polyline, startVert);  totpoly++;
1706                                                 BLI_freelinkN(&edges, edl);                 totedges--;
1707                                                 ok = TRUE;
1708                                         }
1709                                         else if (med->v2 == startVert) {
1710                                                 startVert = med->v1;
1711                                                 prependPolyLineVert(&polyline, startVert);  totpoly++;
1712                                                 BLI_freelinkN(&edges, edl);                 totedges--;
1713                                                 ok = TRUE;
1714                                         }
1715                                 }
1716                         }
1717
1718                         /* Now we have a polyline, make into a curve */
1719                         if (startVert == endVert) {
1720                                 BLI_freelinkN(&polyline, polyline.last);
1721                                 totpoly--;
1722                                 closed = TRUE;
1723                         }
1724
1725                         /* --- nurbs --- */
1726                         {
1727                                 Nurb *nu;
1728                                 BPoint *bp;
1729                                 VertLink *vl;
1730
1731                                 /* create new 'nurb' within the curve */
1732                                 nu = (Nurb *)MEM_callocN(sizeof(Nurb), "MeshNurb");
1733
1734                                 nu->pntsu = totpoly;
1735                                 nu->pntsv = 1;
1736                                 nu->orderu = 4;
1737                                 nu->flagu = CU_NURB_ENDPOINT | (closed ? CU_NURB_CYCLIC : 0);  /* endpoint */
1738                                 nu->resolu = 12;
1739
1740                                 nu->bp = (BPoint *)MEM_callocN(sizeof(BPoint) * totpoly, "bpoints");
1741
1742                                 /* add points */
1743                                 vl = polyline.first;
1744                                 for (i = 0, bp = nu->bp; i < totpoly; i++, bp++, vl = (VertLink *)vl->next) {
1745                                         copy_v3_v3(bp->vec, mverts[vl->index].co);
1746                                         bp->f1 = SELECT;
1747                                         bp->radius = bp->weight = 1.0;
1748                                 }
1749                                 BLI_freelistN(&polyline);
1750
1751                                 /* add nurb to curve */
1752                                 BLI_addtail(&cu->nurb, nu);
1753                         }
1754                         /* --- done with nurbs --- */
1755                 }
1756
1757                 ((Mesh *)ob->data)->id.us--;
1758                 ob->data = cu;
1759                 ob->type = OB_CURVE;
1760
1761                 /* curve objects can't contain DM in usual cases, we could free memory */
1762                 needsFree = 1;
1763         }
1764
1765         dm->needsFree = needsFree;
1766         dm->release(dm);
1767
1768         if (needsFree) {
1769                 ob->derivedFinal = NULL;
1770
1771                 /* curve object could have got bounding box only in special cases */
1772                 if (ob->bb) {
1773                         MEM_freeN(ob->bb);
1774                         ob->bb = NULL;
1775                 }
1776         }
1777 }
1778
1779 void BKE_mesh_delete_material_index(Mesh *me, short index)
1780 {
1781         int i;
1782
1783         for (i = 0; i < me->totpoly; i++) {
1784                 MPoly *mp = &((MPoly *) me->mpoly)[i];
1785                 if (mp->mat_nr && mp->mat_nr >= index)
1786                         mp->mat_nr--;
1787         }
1788
1789         for (i = 0; i < me->totface; i++) {
1790                 MFace *mf = &((MFace *) me->mface)[i];
1791                 if (mf->mat_nr && mf->mat_nr >= index)
1792                         mf->mat_nr--;
1793         }
1794 }
1795
1796 void BKE_mesh_smooth_flag_set(Object *meshOb, int enableSmooth)
1797 {
1798         Mesh *me = meshOb->data;
1799         int i;
1800
1801         for (i = 0; i < me->totpoly; i++) {
1802                 MPoly *mp = &((MPoly *) me->mpoly)[i];
1803
1804                 if (enableSmooth) {
1805                         mp->flag |= ME_SMOOTH;
1806                 }
1807                 else {
1808                         mp->flag &= ~ME_SMOOTH;
1809                 }
1810         }
1811
1812         for (i = 0; i < me->totface; i++) {
1813                 MFace *mf = &((MFace *) me->mface)[i];
1814
1815                 if (enableSmooth) {
1816                         mf->flag |= ME_SMOOTH;
1817                 }
1818                 else {
1819                         mf->flag &= ~ME_SMOOTH;
1820                 }
1821         }
1822 }
1823
1824 void BKE_mesh_calc_normals_mapping(MVert *mverts, int numVerts,
1825                                    MLoop *mloop, MPoly *mpolys, int numLoops, int numPolys, float (*polyNors_r)[3],
1826                                    MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3])
1827 {
1828         BKE_mesh_calc_normals_mapping_ex(mverts, numVerts, mloop, mpolys,
1829                                          numLoops, numPolys, polyNors_r, mfaces, numFaces,
1830                                          origIndexFace, faceNors_r, FALSE);
1831 }
1832
1833 void BKE_mesh_calc_normals_mapping_ex(MVert *mverts, int numVerts,
1834                                       MLoop *mloop, MPoly *mpolys,
1835                                       int numLoops, int numPolys, float (*polyNors_r)[3],
1836                                       MFace *mfaces, int numFaces, int *origIndexFace, float (*faceNors_r)[3],
1837                                       const short only_face_normals)
1838 {
1839         float (*pnors)[3] = polyNors_r, (*fnors)[3] = faceNors_r;
1840         int i;
1841         MFace *mf;
1842         MPoly *mp;
1843
1844         if (numPolys == 0) {
1845                 return;
1846         }
1847
1848         /* if we are not calculating verts and no verts were passes then we have nothing to do */
1849         if ((only_face_normals == TRUE) && (polyNors_r == NULL) && (faceNors_r == NULL)) {
1850                 printf("%s: called with nothing to do\n", __func__);
1851                 return;
1852         }
1853
1854         if (!pnors) pnors = MEM_callocN(sizeof(float) * 3 * numPolys, "poly_nors mesh.c");
1855         /* if (!fnors) fnors = MEM_callocN(sizeof(float) * 3 * numFaces, "face nors mesh.c"); */ /* NO NEED TO ALLOC YET */
1856
1857
1858         if (only_face_normals == FALSE) {
1859                 /* vertex normals are optional, they require some extra calculations,
1860                  * so make them optional */
1861                 BKE_mesh_calc_normals(mverts, numVerts, mloop, mpolys, numLoops, numPolys, pnors);
1862         }
1863         else {
1864                 /* only calc poly normals */
1865                 mp = mpolys;
1866                 for (i = 0; i < numPolys; i++, mp++) {
1867                         BKE_mesh_calc_poly_normal(mp, mloop + mp->loopstart, mverts, pnors[i]);
1868                 }
1869         }
1870
1871         if (origIndexFace &&
1872             /* fnors == faceNors_r */ /* NO NEED TO ALLOC YET */
1873             fnors != NULL &&
1874             numFaces)
1875         {
1876                 mf = mfaces;
1877                 for (i = 0; i < numFaces; i++, mf++, origIndexFace++) {
1878                         if (*origIndexFace < numPolys) {
1879                                 copy_v3_v3(fnors[i], pnors[*origIndexFace]);
1880                         }
1881                         else {
1882                                 /* eek, we're not corresponding to polys */
1883                                 printf("error in BKE_mesh_calc_normals; tessellation face indices are incorrect.  normals may look bad.\n");
1884                         }
1885                 }
1886         }
1887
1888         if (pnors != polyNors_r) MEM_freeN(pnors);
1889         /* if (fnors != faceNors_r) MEM_freeN(fnors); */ /* NO NEED TO ALLOC YET */
1890
1891         fnors = pnors = NULL;
1892
1893 }
1894
1895 void BKE_mesh_calc_normals(MVert *mverts, int numVerts, MLoop *mloop, MPoly *mpolys,
1896                            int UNUSED(numLoops), int numPolys, float (*polyNors_r)[3])
1897 {
1898         float (*pnors)[3] = polyNors_r;
1899
1900         float (*tnorms)[3], (*edgevecbuf)[3] = NULL;
1901         float **vertcos = NULL, **vertnos = NULL;
1902         BLI_array_declare(vertcos);
1903         BLI_array_declare(vertnos);
1904         BLI_array_declare(edgevecbuf);
1905
1906         int i, j;
1907         MPoly *mp;
1908         MLoop *ml;
1909
1910         if (!pnors) pnors = MEM_callocN(sizeof(float) * 3 * numPolys, "poly_nors mesh.c");
1911
1912         /* first go through and calculate normals for all the polys */
1913         tnorms = MEM_callocN(sizeof(float) * 3 * numVerts, "tnorms mesh.c");
1914
1915         mp = mpolys;
1916         for (i = 0; i < numPolys; i++, mp++) {
1917                 BKE_mesh_calc_poly_normal(mp, mloop + mp->loopstart, mverts, pnors[i]);
1918                 ml = mloop + mp->loopstart;
1919
1920                 BLI_array_empty(vertcos);
1921                 BLI_array_empty(vertnos);
1922                 BLI_array_grow_items(vertcos, mp->totloop);
1923                 BLI_array_grow_items(vertnos, mp->totloop);
1924
1925                 for (j = 0; j < mp->totloop; j++) {
1926                         int vindex = ml[j].v;
1927                         vertcos[j] = mverts[vindex].co;
1928                         vertnos[j] = tnorms[vindex];
1929                 }
1930
1931                 BLI_array_empty(edgevecbuf);
1932                 BLI_array_grow_items(edgevecbuf, mp->totloop);
1933
1934                 accumulate_vertex_normals_poly(vertnos, pnors[i], vertcos, edgevecbuf, mp->totloop);
1935         }
1936
1937         BLI_array_free(vertcos);
1938         BLI_array_free(vertnos);
1939         BLI_array_free(edgevecbuf);
1940
1941         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
1942         for (i = 0; i < numVerts; i++) {
1943                 MVert *mv = &mverts[i];
1944                 float *no = tnorms[i];
1945
1946                 if (UNLIKELY(normalize_v3(no) == 0.0f)) {
1947                         normalize_v3_v3(no, mv->co);
1948                 }
1949
1950                 normal_float_to_short_v3(mv->no, no);
1951         }
1952
1953         MEM_freeN(tnorms);
1954
1955         if (pnors != polyNors_r) MEM_freeN(pnors);
1956 }
1957
1958 void BKE_mesh_calc_normals_tessface(MVert *mverts, int numVerts, MFace *mfaces, int numFaces, float (*faceNors_r)[3])
1959 {
1960         float (*tnorms)[3] = MEM_callocN(numVerts * sizeof(*tnorms), "tnorms");
1961         float (*fnors)[3] = (faceNors_r) ? faceNors_r : MEM_callocN(sizeof(*fnors) * numFaces, "meshnormals");
1962         int i;
1963
1964         for (i = 0; i < numFaces; i++) {
1965                 MFace *mf = &mfaces[i];
1966                 float *f_no = fnors[i];
1967                 float *n4 = (mf->v4) ? tnorms[mf->v4] : NULL;
1968                 float *c4 = (mf->v4) ? mverts[mf->v4].co : NULL;
1969
1970                 if (mf->v4)
1971                         normal_quad_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, mverts[mf->v4].co);
1972                 else
1973                         normal_tri_v3(f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co);
1974
1975                 accumulate_vertex_normals(tnorms[mf->v1], tnorms[mf->v2], tnorms[mf->v3], n4,
1976                                           f_no, mverts[mf->v1].co, mverts[mf->v2].co, mverts[mf->v3].co, c4);
1977         }
1978
1979         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
1980         for (i = 0; i < numVerts; i++) {
1981                 MVert *mv = &mverts[i];
1982                 float *no = tnorms[i];
1983
1984                 if (UNLIKELY(normalize_v3(no) == 0.0f)) {
1985                         normalize_v3_v3(no, mv->co);
1986                 }
1987
1988                 normal_float_to_short_v3(mv->no, no);
1989         }
1990
1991         MEM_freeN(tnorms);
1992
1993         if (fnors != faceNors_r)
1994                 MEM_freeN(fnors);
1995 }
1996
1997 static void bm_corners_to_loops_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
1998                                    MFace *mface, int totloop, int findex, int loopstart, int numTex, int numCol)
1999 {
2000         MTFace *texface;
2001         MTexPoly *texpoly;
2002         MCol *mcol;
2003         MLoopCol *mloopcol;
2004         MLoopUV *mloopuv;
2005         MFace *mf;
2006         int i;
2007
2008         mf = mface + findex;
2009
2010         for (i = 0; i < numTex; i++) {
2011                 texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
2012                 texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, findex, i);
2013
2014                 ME_MTEXFACE_CPY(texpoly, texface);
2015
2016                 mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, loopstart, i);
2017                 copy_v2_v2(mloopuv->uv, texface->uv[0]); mloopuv++;
2018                 copy_v2_v2(mloopuv->uv, texface->uv[1]); mloopuv++;
2019                 copy_v2_v2(mloopuv->uv, texface->uv[2]); mloopuv++;
2020
2021                 if (mf->v4) {
2022                         copy_v2_v2(mloopuv->uv, texface->uv[3]); mloopuv++;
2023                 }
2024         }
2025
2026         for (i = 0; i < numCol; i++) {
2027                 mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, loopstart, i);
2028                 mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
2029
2030                 MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[0]); mloopcol++;
2031                 MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[1]); mloopcol++;
2032                 MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[2]); mloopcol++;
2033                 if (mf->v4) {
2034                         MESH_MLOOPCOL_FROM_MCOL(mloopcol, &mcol[3]); mloopcol++;
2035                 }
2036         }
2037
2038         if (CustomData_has_layer(fdata, CD_MDISPS)) {
2039                 MDisps *ld = CustomData_get(ldata, loopstart, CD_MDISPS);
2040                 MDisps *fd = CustomData_get(fdata, findex, CD_MDISPS);
2041                 float (*disps)[3] = fd->disps;
2042                 int tot = mf->v4 ? 4 : 3;
2043                 int side, corners;
2044
2045                 if (CustomData_external_test(fdata, CD_MDISPS)) {
2046                         if (id && fdata->external) {
2047                                 CustomData_external_add(ldata, id, CD_MDISPS,
2048                                                         totloop, fdata->external->filename);
2049                         }
2050                 }
2051
2052                 corners = multires_mdisp_corners(fd);
2053
2054                 if (corners == 0) {
2055                         /* Empty MDisp layers appear in at least one of the sintel.blend files.
2056                          * Not sure why this happens, but it seems fine to just ignore them here.
2057                          * If (corners == 0) for a non-empty layer though, something went wrong. */
2058                         BLI_assert(fd->totdisp == 0);
2059                 }
2060                 else {
2061                         side = sqrt(fd->totdisp / corners);
2062
2063                         for (i = 0; i < tot; i++, disps += side * side, ld++) {
2064                                 ld->totdisp = side * side;
2065                                 ld->level = (int)(logf(side - 1.0f) / (float)M_LN2) + 1;
2066
2067                                 if (ld->disps)
2068                                         MEM_freeN(ld->disps);
2069
2070                                 ld->disps = MEM_callocN(sizeof(float) * 3 * side * side, "converted loop mdisps");
2071                                 if (fd->disps) {
2072                                         memcpy(ld->disps, disps, sizeof(float) * 3 * side * side);
2073                                 }
2074                         }
2075                 }
2076         }
2077 }
2078
2079 void BKE_mesh_convert_mfaces_to_mpolys(Mesh *mesh)
2080 {
2081         BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
2082                                              mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
2083                                              mesh->medge, mesh->mface,
2084                                              &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
2085
2086         mesh_update_customdata_pointers(mesh, TRUE);
2087 }
2088
2089 /* the same as BKE_mesh_convert_mfaces_to_mpolys but oriented to be used in do_versions from readfile.c
2090  * the difference is how active/render/clone/stencil indices are handled here
2091  *
2092  * normally thay're being set from pdata which totally makes sense for meshes which are already
2093  * converted to bmesh structures, but when loading older files indices shall be updated in other
2094  * way around, so newly added pdata and ldata would have this indices set based on fdata layer
2095  *
2096  * this is normally only needed when reading older files, in all other cases BKE_mesh_convert_mfaces_to_mpolys
2097  * shall be always used
2098  */
2099 void BKE_mesh_do_versions_convert_mfaces_to_mpolys(Mesh *mesh)
2100 {
2101         BKE_mesh_convert_mfaces_to_mpolys_ex(&mesh->id, &mesh->fdata, &mesh->ldata, &mesh->pdata,
2102                                              mesh->totedge, mesh->totface, mesh->totloop, mesh->totpoly,
2103                                              mesh->medge, mesh->mface,
2104                                              &mesh->totloop, &mesh->totpoly, &mesh->mloop, &mesh->mpoly);
2105
2106         CustomData_bmesh_do_versions_update_active_layers(&mesh->fdata, &mesh->pdata, &mesh->ldata);
2107
2108         mesh_update_customdata_pointers(mesh, TRUE);
2109 }
2110
2111 void BKE_mesh_convert_mfaces_to_mpolys_ex(ID *id, CustomData *fdata, CustomData *ldata, CustomData *pdata,
2112                                           int totedge_i, int totface_i, int totloop_i, int totpoly_i,
2113                                           MEdge *medge, MFace *mface,
2114                                           int *totloop_r, int *totpoly_r,
2115                                           MLoop **mloop_r, MPoly **mpoly_r)
2116 {
2117         MFace *mf;
2118         MLoop *ml, *mloop;
2119         MPoly *mp, *mpoly;
2120         MEdge *me;
2121         EdgeHash *eh;
2122         int numTex, numCol;
2123         int i, j, totloop, totpoly, *polyindex;
2124
2125         /* just in case some of these layers are filled in (can happen with python created meshes) */
2126         CustomData_free(ldata, totloop_i);
2127         CustomData_free(pdata, totpoly_i);
2128         memset(ldata, 0, sizeof(*ldata));
2129         memset(pdata, 0, sizeof(*pdata));
2130
2131         totpoly = totface_i;
2132         mpoly = MEM_callocN(sizeof(MPoly) * totpoly, "mpoly converted");
2133         CustomData_add_layer(pdata, CD_MPOLY, CD_ASSIGN, mpoly, totpoly);
2134
2135         numTex = CustomData_number_of_layers(fdata, CD_MTFACE);
2136         numCol = CustomData_number_of_layers(fdata, CD_MCOL);
2137
2138         totloop = 0;
2139         mf = mface;
2140         for (i = 0; i < totface_i; i++, mf++) {
2141                 totloop += mf->v4 ? 4 : 3;
2142         }
2143
2144         mloop = MEM_callocN(sizeof(MLoop) * totloop, "mloop converted");
2145
2146         CustomData_add_layer(ldata, CD_MLOOP, CD_ASSIGN, mloop, totloop);
2147
2148         CustomData_to_bmeshpoly(fdata, pdata, ldata, totloop, totpoly);
2149
2150         if (id) {
2151                 /* ensure external data is transferred */
2152                 CustomData_external_read(fdata, id, CD_MASK_MDISPS, totface_i);
2153         }
2154
2155         eh = BLI_edgehash_new();
2156
2157         /* build edge hash */
2158         me = medge;
2159         for (i = 0; i < totedge_i; i++, me++) {
2160                 BLI_edgehash_insert(eh, me->v1, me->v2, SET_INT_IN_POINTER(i));
2161
2162                 /* unrelated but avoid having the FGON flag enabled, so we can reuse it later for something else */
2163                 me->flag &= ~ME_FGON;
2164         }
2165
2166         polyindex = CustomData_get_layer(fdata, CD_POLYINDEX);
2167
2168         j = 0; /* current loop index */
2169         ml = mloop;
2170         mf = mface;
2171         mp = mpoly;
2172         for (i = 0; i < totface_i; i++, mf++, mp++) {
2173                 mp->loopstart = j;
2174
2175                 mp->totloop = mf->v4 ? 4 : 3;
2176
2177                 mp->mat_nr = mf->mat_nr;
2178                 mp->flag = mf->flag;
2179
2180 #       define ML(v1, v2) { \
2181                         ml->v = mf->v1; ml->e = GET_INT_FROM_POINTER(BLI_edgehash_lookup(eh, mf->v1, mf->v2)); ml++; j++; \
2182                 } (void)0
2183
2184                 ML(v1, v2);
2185                 ML(v2, v3);
2186                 if (mf->v4) {
2187                         ML(v3, v4);
2188                         ML(v4, v1);
2189                 }
2190                 else {
2191                         ML(v3, v1);
2192                 }
2193
2194 #       undef ML
2195
2196                 bm_corners_to_loops_ex(id, fdata, ldata, pdata, mface, totloop, i, mp->loopstart, numTex, numCol);
2197
2198                 if (polyindex) {
2199                         *polyindex = i;
2200                         polyindex++;
2201                 }
2202         }
2203
2204         /* note, we don't convert NGons at all, these are not even real ngons,
2205          * they have their own UV's, colors etc - its more an editing feature. */
2206
2207         BLI_edgehash_free(eh, NULL);
2208
2209         *totpoly_r = totpoly;
2210         *totloop_r = totloop;
2211         *mpoly_r = mpoly;
2212         *mloop_r = mloop;
2213 }
2214
2215 float (*mesh_getVertexCos(Mesh * me, int *numVerts_r))[3]
2216 {
2217         int i, numVerts = me->totvert;
2218         float (*cos)[3] = MEM_mallocN(sizeof(*cos) * numVerts, "vertexcos1");
2219
2220         if (numVerts_r) *numVerts_r = numVerts;
2221         for (i = 0; i < numVerts; i++)
2222                 copy_v3_v3(cos[i], me->mvert[i].co);
2223
2224         return cos;
2225 }
2226
2227
2228 /* ngon version wip, based on EDBM_uv_vert_map_create */
2229 /* this replaces the non bmesh function (in trunk) which takes MTFace's, if we ever need it back we could
2230  * but for now this replaces it because its unused. */
2231
2232 UvVertMap *BKE_mesh_uv_vert_map_make(struct MPoly *mpoly, struct MLoop *mloop, struct MLoopUV *mloopuv, unsigned int totpoly, unsigned int totvert, int selected, float *limit)
2233 {
2234         UvVertMap *vmap;
2235         UvMapVert *buf;
2236         MPoly *mp;
2237         unsigned int a;
2238         int i, totuv, nverts;
2239
2240         totuv = 0;
2241
2242         /* generate UvMapVert array */
2243         mp = mpoly;
2244         for (a = 0; a < totpoly; a++, mp++)
2245                 if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL)))
2246                         totuv += mp->totloop;
2247
2248         if (totuv == 0)
2249                 return NULL;
2250
2251         vmap = (UvVertMap *)MEM_callocN(sizeof(*vmap), "UvVertMap");
2252         if (!vmap)
2253                 return NULL;
2254
2255         vmap->vert = (UvMapVert **)MEM_callocN(sizeof(*vmap->vert) * totvert, "UvMapVert*");
2256         buf = vmap->buf = (UvMapVert *)MEM_callocN(sizeof(*vmap->buf) * totuv, "UvMapVert");
2257
2258         if (!vmap->vert || !vmap->buf) {
2259                 BKE_mesh_uv_vert_map_free(vmap);
2260                 return NULL;
2261         }
2262
2263         mp = mpoly;
2264         for (a = 0; a < totpoly; a++, mp++) {
2265                 if (!selected || (!(mp->flag & ME_HIDE) && (mp->flag & ME_FACE_SEL))) {
2266                         nverts = mp->totloop;
2267
2268                         for (i = 0; i < nverts; i++) {
2269                                 buf->tfindex = i;
2270                                 buf->f = a;
2271                                 buf->separate = 0;
2272                                 buf->next = vmap->vert[mloop[mp->loopstart + i].v];
2273                                 vmap->vert[mloop[mp->loopstart + i].v] = buf;
2274                                 buf++;
2275                         }
2276                 }
2277         }
2278
2279         /* sort individual uvs for each vert */
2280         for (a = 0; a < totvert; a++) {
2281                 UvMapVert *newvlist = NULL, *vlist = vmap->vert[a];
2282                 UvMapVert *iterv, *v, *lastv, *next;
2283                 float *uv, *uv2, uvdiff[2];
2284
2285                 while (vlist) {
2286                         v = vlist;
2287                         vlist = vlist->next;
2288                         v->next = newvlist;
2289                         newvlist = v;
2290
2291                         uv = mloopuv[mpoly[v->f].loopstart + v->tfindex].uv;
2292                         lastv = NULL;
2293                         iterv = vlist;
2294
2295                         while (iterv) {
2296                                 next = iterv->next;
2297
2298                                 uv2 = mloopuv[mpoly[iterv->f].loopstart + iterv->tfindex].uv;
2299                                 sub_v2_v2v2(uvdiff, uv2, uv);
2300
2301
2302                                 if (fabsf(uv[0] - uv2[0]) < limit[0] && fabsf(uv[1] - uv2[1]) < limit[1]) {
2303                                         if (lastv) lastv->next = next;
2304                                         else vlist = next;
2305                                         iterv->next = newvlist;
2306                                         newvlist = iterv;
2307                                 }
2308                                 else
2309                                         lastv = iterv;
2310
2311                                 iterv = next;
2312                         }
2313
2314                         newvlist->separate = 1;
2315                 }
2316
2317                 vmap->vert[a] = newvlist;
2318         }
2319
2320         return vmap;
2321 }
2322
2323 UvMapVert *BKE_mesh_uv_vert_map_get_vert(UvVertMap *vmap, unsigned int v)
2324 {
2325         return vmap->vert[v];
2326 }
2327
2328 void BKE_mesh_uv_vert_map_free(UvVertMap *vmap)
2329 {
2330         if (vmap) {
2331                 if (vmap->vert) MEM_freeN(vmap->vert);
2332                 if (vmap->buf) MEM_freeN(vmap->buf);
2333                 MEM_freeN(vmap);
2334         }
2335 }
2336
2337 /* Generates a map where the key is the vertex and the value is a list
2338  * of polys that use that vertex as a corner. The lists are allocated
2339  * from one memory pool. */
2340 void create_vert_poly_map(MeshElemMap **map, int **mem,
2341                           const MPoly *mpoly, const MLoop *mloop,
2342                           int totvert, int totpoly, int totloop)
2343 {
2344         int i, j;
2345         int *indices;
2346
2347         (*map) = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert poly map");
2348         (*mem) = MEM_mallocN(sizeof(int) * totloop, "vert poly map mem");
2349
2350         /* Count number of polys for each vertex */
2351         for (i = 0; i < totpoly; i++) {
2352                 const MPoly *p = &mpoly[i];
2353
2354                 for (j = 0; j < p->totloop; j++)
2355                         (*map)[mloop[p->loopstart + j].v].count++;
2356         }
2357
2358         /* Assign indices mem */
2359         indices = (*mem);
2360         for (i = 0; i < totvert; i++) {
2361                 (*map)[i].indices = indices;
2362                 indices += (*map)[i].count;
2363
2364                 /* Reset 'count' for use as index in last loop */
2365                 (*map)[i].count = 0;
2366         }
2367
2368         /* Find the users */
2369         for (i = 0; i < totpoly; i++) {
2370                 const MPoly *p = &mpoly[i];
2371
2372                 for (j = 0; j < p->totloop; j++) {
2373                         int v = mloop[p->loopstart + j].v;
2374
2375                         (*map)[v].indices[(*map)[v].count] = i;
2376                         (*map)[v].count++;
2377                 }
2378         }
2379 }
2380
2381 /* Generates a map where the key is the vertex and the value is a list
2382  * of edges that use that vertex as an endpoint. The lists are allocated
2383  * from one memory pool. */
2384 void create_vert_edge_map(MeshElemMap **map, int **mem,
2385                                                   const MEdge *medge, int totvert, int totedge)
2386 {
2387         int i, *indices;
2388
2389         (*map) = MEM_callocN(sizeof(MeshElemMap) * totvert, "vert-edge map");
2390         (*mem) = MEM_mallocN(sizeof(int) * totedge * 2, "vert-edge map mem");
2391
2392         /* Count number of edges for each vertex */
2393         for (i = 0; i < totedge; i++) {
2394                 (*map)[medge[i].v1].count++;
2395                 (*map)[medge[i].v2].count++;
2396         }
2397
2398         /* Assign indices mem */
2399         indices = (*mem);
2400         for (i = 0; i < totvert; i++) {
2401                 (*map)[i].indices = indices;
2402                 indices += (*map)[i].count;
2403
2404                 /* Reset 'count' for use as index in last loop */
2405                 (*map)[i].count = 0;
2406         }
2407
2408         /* Find the users */
2409         for (i = 0; i < totedge; i++) {
2410                 const int v[2] = {medge[i].v1, medge[i].v2};
2411
2412                 (*map)[v[0]].indices[(*map)[v[0]].count] = i;
2413                 (*map)[v[1]].indices[(*map)[v[1]].count] = i;
2414
2415                 (*map)[v[0]].count++;
2416                 (*map)[v[1]].count++;
2417         }
2418 }
2419
2420 void BKE_mesh_loops_to_mface_corners(CustomData *fdata, CustomData *ldata,
2421                                      CustomData *pdata, int lindex[4], int findex,
2422                                      const int polyindex,
2423                                      const int mf_len, /* 3 or 4 */
2424
2425                                      /* cache values to avoid lookups every time */
2426                                      const int numTex, /* CustomData_number_of_layers(pdata, CD_MTEXPOLY) */
2427                                      const int numCol, /* CustomData_number_of_layers(ldata, CD_MLOOPCOL) */
2428                                      const int hasPCol, /* CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL) */
2429                                      const int hasOrigSpace /* CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP) */
2430                                      )
2431 {
2432         MTFace *texface;
2433         MTexPoly *texpoly;
2434         MCol *mcol;
2435         MLoopCol *mloopcol;
2436         MLoopUV *mloopuv;
2437         int i, j;
2438
2439         for (i = 0; i < numTex; i++) {
2440                 texface = CustomData_get_n(fdata, CD_MTFACE, findex, i);
2441                 texpoly = CustomData_get_n(pdata, CD_MTEXPOLY, polyindex, i);
2442
2443                 ME_MTEXFACE_CPY(texface, texpoly);
2444
2445                 for (j = 0; j < mf_len; j++) {
2446                         mloopuv = CustomData_get_n(ldata, CD_MLOOPUV, lindex[j], i);
2447                         copy_v2_v2(texface->uv[j], mloopuv->uv);
2448                 }
2449         }
2450
2451         for (i = 0; i < numCol; i++) {
2452                 mcol = CustomData_get_n(fdata, CD_MCOL, findex, i);
2453
2454                 for (j = 0; j < mf_len; j++) {
2455                         mloopcol = CustomData_get_n(ldata, CD_MLOOPCOL, lindex[j], i);
2456                         MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
2457                 }
2458         }
2459
2460         if (hasPCol) {
2461                 mcol = CustomData_get(fdata,  findex, CD_PREVIEW_MCOL);
2462
2463                 for (j = 0; j < mf_len; j++) {
2464                         mloopcol = CustomData_get(ldata, lindex[j], CD_PREVIEW_MLOOPCOL);
2465                         MESH_MLOOPCOL_TO_MCOL(mloopcol, &mcol[j]);
2466                 }
2467         }
2468
2469         if (hasOrigSpace) {
2470                 OrigSpaceFace *of = CustomData_get(fdata, findex, CD_ORIGSPACE);
2471                 OrigSpaceLoop *lof;
2472
2473                 for (j = 0; j < mf_len; j++) {
2474                         lof = CustomData_get(ldata, lindex[j], CD_ORIGSPACE_MLOOP);
2475                         copy_v2_v2(of->uv[j], lof->uv);
2476                 }
2477         }
2478 }
2479
2480 /*
2481  * this function recreates a tessellation.
2482  * returns number of tessellation faces.
2483  */
2484 int BKE_mesh_recalc_tessellation(CustomData *fdata,
2485                                  CustomData *ldata, CustomData *pdata,
2486                                  MVert *mvert, int totface, int UNUSED(totloop),
2487                                  int totpoly,
2488                                  /* when tessellating to recalculate normals after
2489                                   * we can skip copying here */
2490                                  const int do_face_nor_cpy)
2491 {
2492         /* use this to avoid locking pthread for _every_ polygon
2493          * and calling the fill function */
2494
2495 #define USE_TESSFACE_SPEEDUP
2496 #define USE_TESSFACE_QUADS // NEEDS FURTHER TESTING
2497
2498 #define TESSFACE_SCANFILL (1 << 0)
2499 #define TESSFACE_IS_QUAD  (1 << 1)
2500
2501         MPoly *mp, *mpoly;
2502         MLoop *ml, *mloop;
2503         MFace *mface = NULL, *mf;
2504         BLI_array_declare(mface);
2505         ScanFillContext sf_ctx;
2506         ScanFillVert *sf_vert, *sf_vert_last, *sf_vert_first;
2507         ScanFillFace *sf_tri;
2508         int *mface_orig_index = NULL;
2509         BLI_array_declare(mface_orig_index);
2510         int *mface_to_poly_map = NULL;
2511         BLI_array_declare(mface_to_poly_map);
2512         int lindex[4]; /* only ever use 3 in this case */
2513         int *poly_orig_index;
2514         int poly_index, j, mface_index;
2515
2516         const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
2517         const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
2518         const int hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
2519         const int hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
2520
2521         mpoly = CustomData_get_layer(pdata, CD_MPOLY);
2522         mloop = CustomData_get_layer(ldata, CD_MLOOP);
2523
2524         /* allocate the length of totfaces, avoid many small reallocs,
2525          * if all faces are tri's it will be correct, quads == 2x allocs */
2526         BLI_array_reserve(mface_to_poly_map, totpoly);
2527         BLI_array_reserve(mface, totpoly);
2528
2529         mface_index = 0;
2530         mp = mpoly;
2531         poly_orig_index = CustomData_get_layer(pdata, CD_ORIGINDEX);
2532         for (poly_index = 0; poly_index < totpoly; poly_index++, mp++) {
2533                 if (mp->totloop < 3) {
2534                         /* do nothing */
2535                 }
2536
2537 #ifdef USE_TESSFACE_SPEEDUP
2538
2539 #define ML_TO_MF(i1, i2, i3)                                                  \
2540                 BLI_array_grow_one(mface_to_poly_map);                                \
2541                 BLI_array_grow_one(mface);                                            \
2542                 mface_to_poly_map[mface_index] = poly_index;                          \
2543                 mf = &mface[mface_index];                                             \
2544                 /* set loop indices, transformed to vert indices later */             \
2545                 mf->v1 = mp->loopstart + i1;                                          \
2546                 mf->v2 = mp->loopstart + i2;                                          \
2547                 mf->v3 = mp->loopstart + i3;                                          \
2548                 mf->v4 = 0;                                                           \
2549                 mf->mat_nr = mp->mat_nr;                                              \
2550                 mf->flag = mp->flag;                                                  \
2551                 if (poly_orig_index) {                                                \
2552                         BLI_array_append(mface_orig_index,                                \
2553                                      poly_orig_index[poly_index]);                    \
2554                 }                                                                     \
2555                 (void)0
2556
2557 /* ALMOST IDENTICAL TO DEFINE ABOVE (see EXCEPTION) */
2558 #define ML_TO_MF_QUAD()                                                       \
2559                 BLI_array_grow_one(mface_to_poly_map);                                \
2560                 BLI_array_grow_one(mface);                                            \
2561                 mface_to_poly_map[mface_index] = poly_index;                          \
2562                 mf = &mface[mface_index];                                             \
2563                 /* set loop indices, transformed to vert indices later */             \
2564                 mf->v1 = mp->loopstart + 0; /* EXCEPTION */                           \
2565                 mf->v2 = mp->loopstart + 1; /* EXCEPTION */                           \
2566                 mf->v3 = mp->loopstart + 2; /* EXCEPTION */                           \
2567                 mf->v4 = mp->loopstart + 3; /* EXCEPTION */                           \
2568                 mf->mat_nr = mp->mat_nr;                                              \
2569                 mf->flag = mp->flag;                                                  \
2570                 if (poly_orig_index) {                                                \
2571                         BLI_array_append(mface_orig_index,                                \
2572                                      poly_orig_index[poly_index]);                    \
2573                 }                                                                     \
2574                 mf->edcode |= TESSFACE_IS_QUAD; /* EXCEPTION */                       \
2575                 (void)0
2576
2577
2578                 else if (mp->totloop == 3) {
2579                         ML_TO_MF(0, 1, 2);
2580                         mface_index++;
2581                 }
2582                 else if (mp->totloop == 4) {
2583 #ifdef USE_TESSFACE_QUADS
2584                         ML_TO_MF_QUAD();
2585                         mface_index++;
2586 #else
2587                         ML_TO_MF(0, 1, 2);
2588                         mface_index++;
2589                         ML_TO_MF(0, 2, 3);
2590                         mface_index++;
2591 #endif
2592                 }
2593 #endif /* USE_TESSFACE_SPEEDUP */
2594                 else {
2595                         int totfilltri;
2596
2597                         ml = mloop + mp->loopstart;
2598
2599                         BLI_scanfill_begin(&sf_ctx);
2600                         sf_vert_first = NULL;
2601                         sf_vert_last = NULL;
2602                         for (j = 0; j < mp->totloop; j++, ml++) {
2603                                 sf_vert = BLI_scanfill_vert_add(&sf_ctx, mvert[ml->v].co);
2604
2605                                 sf_vert->keyindex = mp->loopstart + j;
2606
2607                                 if (sf_vert_last)
2608                                         BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
2609
2610                                 if (!sf_vert_first)
2611                                         sf_vert_first = sf_vert;
2612                                 sf_vert_last = sf_vert;
2613                         }
2614                         BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert_first);
2615
2616                         totfilltri = BLI_scanfill_calc(&sf_ctx, FALSE);
2617                         if (totfilltri) {
2618                                 BLI_array_grow_items(mface_to_poly_map, totfilltri);
2619                                 BLI_array_grow_items(mface, totfilltri);
2620                                 if (poly_orig_index) {
2621                                         BLI_array_grow_items(mface_orig_index, totfilltri);
2622                                 }
2623
2624                                 for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) {
2625                                         mface_to_poly_map[mface_index] = poly_index;
2626                                         mf = &mface[mface_index];
2627
2628                                         /* set loop indices, transformed to vert indices later */
2629                                         mf->v1 = sf_tri->v1->keyindex;
2630                                         mf->v2 = sf_tri->v2->keyindex;
2631                                         mf->v3 = sf_tri->v3->keyindex;
2632                                         mf->v4 = 0;
2633
2634                                         mf->mat_nr = mp->mat_nr;
2635                                         mf->flag = mp->flag;
2636
2637 #ifdef USE_TESSFACE_SPEEDUP
2638                                         mf->edcode |= TESSFACE_SCANFILL; /* tag for sorting loop indices */
2639 #endif
2640
2641                                         if (poly_orig_index) {
2642                                                 mface_orig_index[mface_index] = poly_orig_index[poly_index];
2643                                         }
2644
2645                                         mface_index++;
2646                                 }
2647                         }
2648
2649                         BLI_scanfill_end(&sf_ctx);
2650                 }
2651         }
2652
2653         CustomData_free(fdata, totface);
2654         memset(fdata, 0, sizeof(CustomData));
2655         totface = mface_index;
2656
2657
2658         /* not essential but without this we store over-alloc'd memory in the CustomData layers */
2659         if (LIKELY((MEM_allocN_len(mface) / sizeof(*mface)) != totface)) {
2660                 mface = MEM_reallocN(mface, sizeof(*mface) * totface);
2661                 mface_to_poly_map = MEM_reallocN(mface_to_poly_map, sizeof(*mface_to_poly_map) * totface);
2662                 if (mface_orig_index) {
2663                         mface_orig_index = MEM_reallocN(mface_orig_index, sizeof(*mface_orig_index) * totface);
2664                 }
2665         }
2666
2667         CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
2668
2669         /* CD_POLYINDEX will contain an array of indices from tessfaces to the polygons
2670          * they are directly tessellated from */
2671         CustomData_add_layer(fdata, CD_POLYINDEX, CD_ASSIGN, mface_to_poly_map, totface);
2672         if (mface_orig_index) {
2673                 /* If polys had a CD_ORIGINDEX layer, then the tessellated faces will get this
2674                  * layer as well, pointing to polys from the original mesh (not the polys
2675                  * that just got tessellated) */
2676                 CustomData_add_layer(fdata, CD_ORIGINDEX, CD_ASSIGN, mface_orig_index, totface);
2677         }
2678
2679         CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
2680
2681         if (do_face_nor_cpy) {
2682                 /* If polys have a normals layer, copying that to faces can help
2683                  * avoid the need to recalculate normals later */
2684                 if (CustomData_has_layer(pdata, CD_NORMAL)) {
2685                         float (*pnors)[3] = CustomData_get_layer(pdata, CD_NORMAL);
2686                         float (*fnors)[3] = CustomData_add_layer(fdata, CD_NORMAL, CD_CALLOC, NULL, totface);
2687                         for (mface_index = 0; mface_index < totface; mface_index++) {
2688                                 copy_v3_v3(fnors[mface_index], pnors[mface_to_poly_map[mface_index]]);
2689                         }
2690                 }
2691         }
2692
2693         mf = mface;
2694         for (mface_index = 0; mface_index < totface; mface_index++, mf++) {
2695
2696 #ifdef USE_TESSFACE_QUADS
2697                 const int mf_len = mf->edcode & TESSFACE_IS_QUAD ? 4 : 3;
2698 #endif
2699
2700 #ifdef USE_TESSFACE_SPEEDUP
2701                 /* skip sorting when not using ngons */
2702                 if (UNLIKELY(mf->edcode & TESSFACE_SCANFILL))
2703 #endif
2704                 {
2705                         /* sort loop indices to ensure winding is correct */
2706                         if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
2707                         if (mf->v2 > mf->v3) SWAP(unsigned int, mf->v2, mf->v3);
2708                         if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
2709
2710                         if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
2711                         if (mf->v2 > mf->v3) SWAP(unsigned int, mf->v2, mf->v3);
2712                         if (mf->v1 > mf->v2) SWAP(unsigned int, mf->v1, mf->v2);
2713                 }
2714
2715                 /* end abusing the edcode */
2716 #if defined(USE_TESSFACE_QUADS) || defined(USE_TESSFACE_SPEEDUP)
2717                 mf->edcode = 0;
2718 #endif
2719
2720
2721                 lindex[0] = mf->v1;
2722                 lindex[1] = mf->v2;
2723                 lindex[2] = mf->v3;
2724 #ifdef USE_TESSFACE_QUADS
2725                 if (mf_len == 4) lindex[3] = mf->v4;
2726 #endif
2727
2728                 /*transform loop indices to vert indices*/
2729                 mf->v1 = mloop[mf->v1].v;
2730                 mf->v2 = mloop[mf->v2].v;
2731                 mf->v3 = mloop[mf->v3].v;
2732 #ifdef USE_TESSFACE_QUADS
2733                 if (mf_len == 4) mf->v4 = mloop[mf->v4].v;
2734 #endif
2735
2736                 BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
2737                                                 lindex, mface_index, mface_to_poly_map[mface_index],
2738 #ifdef USE_TESSFACE_QUADS
2739                                                 mf_len,
2740 #else
2741                                                 3,
2742 #endif
2743                                                 numTex, numCol, hasPCol, hasOrigSpace);
2744
2745
2746 #ifdef USE_TESSFACE_QUADS
2747                 test_index_face(mf, fdata, mface_index, mf_len);
2748 #endif
2749
2750         }
2751
2752         return totface;
2753
2754 #undef USE_TESSFACE_SPEEDUP
2755
2756 }
2757
2758
2759 #ifdef USE_BMESH_SAVE_AS_COMPAT
2760
2761 /*
2762  * this function recreates a tessellation.
2763  * returns number of tessellation faces.
2764  */
2765 int BKE_mesh_mpoly_to_mface(struct CustomData *fdata, struct CustomData *ldata,
2766                             struct CustomData *pdata, int totface, int UNUSED(totloop), int totpoly)
2767 {
2768         MLoop *mloop;
2769
2770         int lindex[4];
2771         int i;
2772         int k;
2773
2774         MPoly *mp, *mpoly;
2775         MFace *mface = NULL, *mf;
2776         BLI_array_declare(mface);
2777
2778         const int numTex = CustomData_number_of_layers(pdata, CD_MTEXPOLY);
2779         const int numCol = CustomData_number_of_layers(ldata, CD_MLOOPCOL);
2780         const int hasPCol = CustomData_has_layer(ldata, CD_PREVIEW_MLOOPCOL);
2781         const int hasOrigSpace = CustomData_has_layer(ldata, CD_ORIGSPACE_MLOOP);
2782
2783         mpoly = CustomData_get_layer(pdata, CD_MPOLY);
2784         mloop = CustomData_get_layer(ldata, CD_MLOOP);
2785
2786         mp = mpoly;
2787         k = 0;
2788         for (i = 0; i < totpoly; i++, mp++) {
2789                 if (ELEM(mp->totloop, 3, 4)) {
2790                         BLI_array_grow_one(mface);
2791                         mf = &mface[k];
2792
2793                         mf->mat_nr = mp->mat_nr;
2794                         mf->flag = mp->flag;
2795
2796                         mf->v1 = mp->loopstart + 0;
2797                         mf->v2 = mp->loopstart + 1;
2798                         mf->v3 = mp->loopstart + 2;
2799                         mf->v4 = (mp->totloop == 4) ? (mp->loopstart + 3) : 0;
2800
2801                         /* abuse edcode for temp storage and clear next loop */
2802                         mf->edcode = (char)mp->totloop; /* only ever 3 or 4 */
2803
2804                         k++;
2805                 }
2806         }
2807
2808         CustomData_free(fdata, totface);
2809         memset(fdata, 0, sizeof(CustomData));
2810
2811         totface = k;
2812
2813         CustomData_add_layer(fdata, CD_MFACE, CD_ASSIGN, mface, totface);
2814
2815         CustomData_from_bmeshpoly(fdata, pdata, ldata, totface);
2816
2817         mp = mpoly;
2818         k = 0;
2819         for (i = 0; i < totpoly; i++, mp++) {
2820                 if (ELEM(mp->totloop, 3, 4)) {
2821                         mf = &mface[k];
2822
2823                         if (mf->edcode == 3) {
2824                                 /* sort loop indices to ensure winding is correct */
2825                                 /* NO SORT - looks like we can skip this */
2826
2827                                 lindex[0] = mf->v1;
2828                                 lindex[1] = mf->v2;
2829                                 lindex[2] = mf->v3;
2830                                 lindex[3] = 0; /* unused */
2831
2832                                 /* transform loop indices to vert indices */
2833                                 mf->v1 = mloop[mf->v1].v;
2834                                 mf->v2 = mloop[mf->v2].v;
2835                                 mf->v3 = mloop[mf->v3].v;
2836
2837                                 BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
2838                                                                 lindex, k, i, 3,
2839                                                                 numTex, numCol, hasPCol, hasOrigSpace);
2840                                 test_index_face(mf, fdata, k, 3);
2841                         }
2842                         else {
2843                                 /* sort loop indices to ensure winding is correct */
2844                                 /* NO SORT - looks like we can skip this */
2845
2846                                 lindex[0] = mf->v1;
2847                                 lindex[1] = mf->v2;
2848                                 lindex[2] = mf->v3;
2849                                 lindex[3] = mf->v4;
2850
2851                                 /* transform loop indices to vert indices */
2852                                 mf->v1 = mloop[mf->v1].v;
2853                                 mf->v2 = mloop[mf->v2].v;
2854                                 mf->v3 = mloop[mf->v3].v;
2855                                 mf->v4 = mloop[mf->v4].v;
2856
2857                                 BKE_mesh_loops_to_mface_corners(fdata, ldata, pdata,
2858                                                                 lindex, k, i, 4,
2859                                                                 numTex, numCol, hasPCol, hasOrigSpace);
2860                                 test_index_face(mf, fdata, k, 4);
2861                         }
2862
2863                         mf->edcode = 0;
2864
2865                         k++;
2866                 }
2867         }
2868
2869         return k;
2870 }
2871 #endif /* USE_BMESH_SAVE_AS_COMPAT */
2872
2873 /*
2874  * COMPUTE POLY NORMAL
2875  *
2876  * Computes the normal of a planar
2877  * polygon See Graphics Gems for
2878  * computing newell normal.
2879  *
2880  */
2881 static void mesh_calc_ngon_normal(MPoly *mpoly, MLoop *loopstart,
2882                                   MVert *mvert, float normal[3])
2883 {
2884         const int nverts = mpoly->totloop;
2885         float const *v_prev = mvert[loopstart[nverts - 1].v].co;
2886         float const *v_curr;
2887         int i;
2888
2889         zero_v3(normal);
2890
2891         /* Newell's Method */
2892         for (i = 0; i < nverts; i++) {
2893                 v_curr = mvert[loopstart[i].v].co;
2894                 add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
2895                 v_prev = v_curr;
2896         }
2897
2898         if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
2899                 normal[2] = 1.0f; /* other axis set to 0.0 */
2900         }
2901 }
2902
2903 void BKE_mesh_calc_poly_normal(MPoly *mpoly, MLoop *loopstart,
2904                                MVert *mvarray, float no[3])
2905 {
2906         if (mpoly->totloop > 4) {
2907                 mesh_calc_ngon_normal(mpoly, loopstart, mvarray, no);
2908         }
2909         else if (mpoly->totloop == 3) {
2910                 normal_tri_v3(no,
2911                               mvarray[loopstart[0].v].co,
2912                               mvarray[loopstart[1].v].co,
2913                               mvarray[loopstart[2].v].co
2914                               );
2915         }
2916         else if (mpoly->totloop == 4) {
2917                 normal_quad_v3(no,
2918                                mvarray[loopstart[0].v].co,
2919                                mvarray[loopstart[1].v].co,
2920                                mvarray[loopstart[2].v].co,
2921                                mvarray[loopstart[3].v].co
2922                                );
2923         }
2924         else { /* horrible, two sided face! */
2925                 no[0] = 0.0;
2926                 no[1] = 0.0;
2927                 no[2] = 1.0;
2928         }
2929 }
2930 /* duplicate of function above _but_ takes coords rather then mverts */
2931 static void mesh_calc_ngon_normal_coords(MPoly *mpoly, MLoop *loopstart,
2932                                          const float (*vertex_coords)[3], float normal[3])
2933 {
2934         const int nverts = mpoly->totloop;
2935         float const *v_prev = vertex_coords[loopstart[nverts - 1].v];
2936         float const *v_curr;
2937         int i;
2938
2939         zero_v3(normal);
2940
2941         /* Newell's Method */
2942         for (i = 0; i < nverts; i++) {
2943                 v_curr = vertex_coords[loopstart[i].v];
2944                 add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
2945                 v_prev = v_curr;
2946         }
2947
2948         if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
2949                 normal[2] = 1.0f; /* other axis set to 0.0 */
2950         }
2951 }
2952
2953 void BKE_mesh_calc_poly_normal_coords(MPoly *mpoly, MLoop *loopstart,
2954                                       const float (*vertex_coords)[3], float no[3])
2955 {
2956         if (mpoly->totloop > 4) {
2957                 mesh_calc_ngon_normal_coords(mpoly, loopstart, vertex_coords, no);
2958         }
2959         else if (mpoly->totloop == 3) {
2960                 normal_tri_v3(no,
2961                               vertex_coords[loopstart[0].v],
2962                               vertex_coords[loopstart[1].v],
2963                               vertex_coords[loopstart[2].v]
2964                               );
2965         }
2966         else if (mpoly->totloop == 4) {
2967                 normal_quad_v3(no,
2968                                vertex_coords[loopstart[0].v],
2969                                vertex_coords[loopstart[1].v],
2970                                vertex_coords[loopstart[2].v],
2971                                vertex_coords[loopstart[3].v]
2972                                );
2973         }
2974         else { /* horrible, two sided face! */
2975                 no[0] = 0.0;
2976                 no[1] = 0.0;
2977                 no[2] = 1.0;
2978         }
2979 }
2980
2981 static void mesh_calc_ngon_center(MPoly *mpoly, MLoop *loopstart,
2982                                   MVert *mvert, float cent[3])
2983 {
2984         const float w = 1.0f / (float)mpoly->totloop;
2985         int i;
2986
2987         zero_v3(cent);
2988
2989         for (i = 0; i < mpoly->totloop; i++) {
2990                 madd_v3_v3fl(cent, mvert[(loopstart++)->v].co, w);
2991         }
2992 }
2993
2994 void BKE_mesh_calc_poly_center(MPoly *mpoly, MLoop *loopstart,
2995                                MVert *mvarray, float cent[3])
2996 {
2997         if (mpoly->totloop == 3) {
2998                 cent_tri_v3(cent,
2999                             mvarray[loopstart[0].v].co,
3000                             mvarray[loopstart[1].v].co,
3001                             mvarray[loopstart[2].v].co
3002                             );
3003         }
3004         else if (mpoly->totloop == 4) {
3005                 cent_quad_v3(cent,
3006                              mvarray[loopstart[0].v].co,
3007                              mvarray[loopstart[1].v].co,
3008                              mvarray[loopstart[2].v].co,
3009                              mvarray[loopstart[3].v].co
3010                              );
3011         }
3012         else {
3013                 mesh_calc_ngon_center(mpoly, loopstart, mvarray, cent);
3014         }
3015 }
3016
3017 /* note, passing polynormal is only a speedup so we can skip calculating it */
3018 float BKE_mesh_calc_poly_area(MPoly *mpoly, MLoop *loopstart,
3019                               MVert *mvarray, const float polynormal[3])
3020 {
3021         if (mpoly->totloop == 3) {
3022                 return area_tri_v3(mvarray[loopstart[0].v].co,
3023                                    mvarray[loopstart[1].v].co,
3024                                    mvarray[loopstart[2].v].co
3025                                    );
3026         }
3027         else if (mpoly->totloop == 4) {
3028                 return area_quad_v3(mvarray[loopstart[0].v].co,
3029                                     mvarray[loopstart[1].v].co,
3030                                     mvarray[loopstart[2].v].co,
3031                                     mvarray[loopstart[3].v].co
3032                                     );
3033         }
3034         else {
3035                 int i;
3036                 MLoop *l_iter = loopstart;
3037                 float area, polynorm_local[3], (*vertexcos)[3];
3038                 const float *no = polynormal ? polynormal : polynorm_local;
3039                 BLI_array_fixedstack_declare(vertexcos, BM_NGON_STACK_SIZE, mpoly->totloop, __func__);
3040
3041                 /* pack vertex cos into an array for area_poly_v3 */
3042                 for (i = 0; i < mpoly->totloop; i++, l_iter++) {
3043                         copy_v3_v3(vertexcos[i], mvarray[l_iter->v].co);
3044                 }
3045
3046                 /* need normal for area_poly_v3 as well */
3047                 if (polynormal == NULL) {
3048                         BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, polynorm_local);
3049                 }
3050
3051                 /* finally calculate the area */
3052                 area = area_poly_v3(mpoly->totloop, vertexcos, no);
3053
3054                 BLI_array_fixedstack_free(vertexcos);
3055
3056                 return area;
3057         }
3058 }
3059
3060 /* Find the index of the loop in 'poly' which references vertex,
3061  * returns -1 if not found */
3062 int poly_find_loop_from_vert(const MPoly *poly, const MLoop *loopstart,
3063                              unsigned vert)
3064 {
3065         int j;
3066         for (j = 0; j < poly->totloop; j++, loopstart++) {
3067                 if (loopstart->v == vert)
3068                         return j;
3069         }
3070
3071         return -1;
3072 }
3073
3074 /* Fill 'adj_r' with the loop indices in 'poly' adjacent to the
3075  * vertex. Returns the index of the loop matching vertex, or -1 if the
3076  * vertex is not in 'poly' */
3077 int poly_get_adj_loops_from_vert(unsigned adj_r[3], const MPoly *poly,
3078                                  const MLoop *mloop, unsigned vert)
3079 {
3080         int corner = poly_find_loop_from_vert(poly,
3081                                               &mloop[poly->loopstart],
3082                                               vert);
3083
3084         if (corner != -1) {
3085                 const MLoop *ml = &mloop[poly->loopstart + corner];
3086
3087                 /* vertex was found */
3088                 adj_r[0] = ME_POLY_LOOP_PREV(mloop, poly, corner)->v;
3089                 adj_r[1] = ml->v;
3090                 adj_r[2] = ME_POLY_LOOP_NEXT(mloop, poly, corner)->v;
3091         }
3092
3093         return corner;
3094 }
3095
3096 /* Return the index of the edge vert that is not equal to 'v'. If
3097  * neither edge vertex is equal to 'v', returns -1. */
3098 int BKE_mesh_edge_other_vert(const MEdge *e, int v)
3099 {
3100         if (e->v1 == v)
3101                 return e->v2;
3102         else if (e->v2 == v)
3103                 return e->v1;
3104         else
3105                 return -1;
3106 }
3107
3108 /* update the hide flag for edges and faces from the corresponding
3109  * flag in verts */
3110 void BKE_mesh_flush_hidden_from_verts(const MVert *mvert,
3111                                       const MLoop *mloop,
3112                                       MEdge *medge, int totedge,
3113                                       MPoly *mpoly, int totpoly)<