source/blender/blenkernel/intern/modifier.c

   1 /*
   2 * $Id$
   3 *
   4 * ***** BEGIN GPL LICENSE BLOCK *****
   5 *
   6 * This program is free software; you can redistribute it and/or
   7 * modify it under the terms of the GNU General Public License
   8 * as published by the Free Software Foundation; either version 2
   9 * of the License, or (at your option) any later version.
  10 *
  11 * This program is distributed in the hope that it will be useful,
  12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 * GNU General Public License for more details.
  15 *
  16 * You should have received a copy of the GNU General Public License
  17 * along with this program; if not, write to the Free Software  Foundation,
  18 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  19 *
  20 * The Original Code is Copyright (C) 2005 by the Blender Foundation.
  21 * All rights reserved.
  22 *
  23 * The Original Code is: all of this file.
  24 *
  25 * Contributor(s): Daniel Dunbar
  26 *                 Ton Roosendaal,
  27 *                 Ben Batt,
  28 *                 Brecht Van Lommel,
  29 *                 Campbell Barton
  30 *
  31 * ***** END GPL LICENSE BLOCK *****
  32 *
  33 * Modifier stack implementation.
  34 *
  35 * BKE_modifier.h contains the function prototypes for this file.
  36 *
  37 */
  38
  39 #include "string.h"
  40 #include "stdarg.h"
  41 #include "math.h"
  42 #include "float.h"
  43 #include "ctype.h"
  44
  45 #include "BLI_arithb.h"
  46 #include "BLI_blenlib.h"
  47 #include "BLI_kdopbvh.h"
  48 #include "BLI_kdtree.h"
  49 #include "BLI_linklist.h"
  50 #include "BLI_rand.h"
  51 #include "BLI_edgehash.h"
  52 #include "BLI_ghash.h"
  53 #include "BLI_memarena.h"
  54
  55 #include "MEM_guardedalloc.h"
  56
  57 #include "DNA_action_types.h"
  58 #include "DNA_armature_types.h"
  59 #include "DNA_camera_types.h"
  60 #include "DNA_cloth_types.h"
  61 #include "DNA_curve_types.h"
  62 #include "DNA_effect_types.h"
  63 #include "DNA_material_types.h"
  64 #include "DNA_mesh_types.h"
  65 #include "DNA_meshdata_types.h"
  66 #include "DNA_modifier_types.h"
  67 #include "DNA_object_types.h"
  68 #include "DNA_object_force.h"
  69 #include "DNA_particle_types.h"
  70 #include "DNA_scene_types.h"
  71 #include "DNA_texture_types.h"
  72
  73 #include "BLI_editVert.h"
  74
  75 #include "MTC_matrixops.h"
  76 #include "MTC_vectorops.h"
  77
  78 #include "BKE_main.h"
  79 #include "BKE_anim.h"
  80 #include "BKE_bad_level_calls.h"
  81 #include "BKE_bmesh.h"
  82 #include "BKE_booleanops.h"
  83 #include "BKE_cloth.h"
  84 #include "BKE_collision.h"
  85 #include "BKE_cdderivedmesh.h"
  86 #include "BKE_curve.h"
  87 #include "BKE_customdata.h"
  88 #include "BKE_DerivedMesh.h"
  89 #include "BKE_displist.h"
  90 #include "BKE_fluidsim.h"
  91 #include "BKE_global.h"
  92 #include "BKE_lattice.h"
  93 #include "BKE_library.h"
  94 #include "BKE_material.h"
  95 #include "BKE_mesh.h"
  96 #include "BKE_modifier.h"
  97 #include "BKE_object.h"
  98 #include "BKE_particle.h"
  99 #include "BKE_pointcache.h"
 100 #include "BKE_softbody.h"
 101 #include "BKE_subsurf.h"
 102 #include "BKE_texture.h"
 103 #include "BKE_utildefines.h"
 104
 105 #include "depsgraph_private.h"
 106 #include "BKE_deform.h"
 107 #include "BKE_shrinkwrap.h"
 108 #include "BKE_simple_deform.h"
 109
 110 #include "LOD_DependKludge.h"
 111 #include "LOD_decimation.h"
 112
 113 #include "CCGSubSurf.h"
 114
 115 #include "RE_shader_ext.h"
 116
 117 /***/
 118
 119 static int noneModifier_isDisabled(ModifierData *md)
 120 {
 121         return 1;
 122 }
 123
 124 /* Curve */
 125
 126 static void curveModifier_initData(ModifierData *md)
 127 {
 128         CurveModifierData *cmd = (CurveModifierData*) md;
 129
 130         cmd->defaxis = MOD_CURVE_POSX;
 131 }
 132
 133 static void curveModifier_copyData(ModifierData *md, ModifierData *target)
 134 {
 135         CurveModifierData *cmd = (CurveModifierData*) md;
 136         CurveModifierData *tcmd = (CurveModifierData*) target;
 137
 138         tcmd->defaxis = cmd->defaxis;
 139         tcmd->object = cmd->object;
 140         strncpy(tcmd->name, cmd->name, 32);
 141 }
 142
 143 CustomDataMask curveModifier_requiredDataMask(ModifierData *md)
 144 {
 145         CurveModifierData *cmd = (CurveModifierData *)md;
 146         CustomDataMask dataMask = 0;
 147
 148         /* ask for vertexgroups if we need them */
 149         if(cmd->name[0]) dataMask |= (1 << CD_MDEFORMVERT);
 150
 151         return dataMask;
 152 }
 153
 154 static int curveModifier_isDisabled(ModifierData *md)
 155 {
 156         CurveModifierData *cmd = (CurveModifierData*) md;
 157
 158         return !cmd->object;
 159 }
 160
 161 static void curveModifier_foreachObjectLink(
 162                                             ModifierData *md, Object *ob,
 163          void (*walk)(void *userData, Object *ob, Object **obpoin),
 164                 void *userData)
 165 {
 166         CurveModifierData *cmd = (CurveModifierData*) md;
 167
 168         walk(userData, ob, &cmd->object);
 169 }
 170
 171 static void curveModifier_updateDepgraph(
 172                                          ModifierData *md, DagForest *forest,
 173       Object *ob, DagNode *obNode)
 174 {
 175         CurveModifierData *cmd = (CurveModifierData*) md;
 176
 177         if (cmd->object) {
 178                 DagNode *curNode = dag_get_node(forest, cmd->object);
 179
 180                 dag_add_relation(forest, curNode, obNode,
 181                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Curve Modifier");
 182         }
 183 }
 184
 185 static void curveModifier_deformVerts(
 186                                       ModifierData *md, Object *ob, DerivedMesh *derivedData,
 187           float (*vertexCos)[3], int numVerts)
 188 {
 189         CurveModifierData *cmd = (CurveModifierData*) md;
 190
 191         curve_deform_verts(cmd->object, ob, derivedData, vertexCos, numVerts,
 192                            cmd->name, cmd->defaxis);
 193 }
 194
 195 static void curveModifier_deformVertsEM(
 196                                         ModifierData *md, Object *ob, EditMesh *editData,
 197      DerivedMesh *derivedData, float (*vertexCos)[3], int numVerts)
 198 {
 199         DerivedMesh *dm = derivedData;
 200
 201         if(!derivedData) dm = CDDM_from_editmesh(editData, ob->data);
 202
 203         curveModifier_deformVerts(md, ob, dm, vertexCos, numVerts);
 204
 205         if(!derivedData) dm->release(dm);
 206 }
 207
 208 /* Lattice */
 209
 210 static void latticeModifier_copyData(ModifierData *md, ModifierData *target)
 211 {
 212         LatticeModifierData *lmd = (LatticeModifierData*) md;
 213         LatticeModifierData *tlmd = (LatticeModifierData*) target;
 214
 215         tlmd->object = lmd->object;
 216         strncpy(tlmd->name, lmd->name, 32);
 217 }
 218
 219 CustomDataMask latticeModifier_requiredDataMask(ModifierData *md)
 220 {
 221         LatticeModifierData *lmd = (LatticeModifierData *)md;
 222         CustomDataMask dataMask = 0;
 223
 224         /* ask for vertexgroups if we need them */
 225         if(lmd->name[0]) dataMask |= (1 << CD_MDEFORMVERT);
 226
 227         return dataMask;
 228 }
 229
 230 static int latticeModifier_isDisabled(ModifierData *md)
 231 {
 232         LatticeModifierData *lmd = (LatticeModifierData*) md;
 233
 234         return !lmd->object;
 235 }
 236
 237 static void latticeModifier_foreachObjectLink(
 238                                               ModifierData *md, Object *ob,
 239            void (*walk)(void *userData, Object *ob, Object **obpoin),
 240                   void *userData)
 241 {
 242         LatticeModifierData *lmd = (LatticeModifierData*) md;
 243
 244         walk(userData, ob, &lmd->object);
 245 }
 246
 247 static void latticeModifier_updateDepgraph(ModifierData *md, DagForest *forest,
 248                                            Object *ob, DagNode *obNode)
 249 {
 250         LatticeModifierData *lmd = (LatticeModifierData*) md;
 251
 252         if(lmd->object) {
 253                 DagNode *latNode = dag_get_node(forest, lmd->object);
 254
 255                 dag_add_relation(forest, latNode, obNode,
 256                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Lattice Modifier");
 257         }
 258 }
 259
 260 static void modifier_vgroup_cache(ModifierData *md, float (*vertexCos)[3])
 261 {
 262         md= md->next;
 263         if(md) {
 264                 if(md->type==eModifierType_Armature) {
 265                         ArmatureModifierData *amd = (ArmatureModifierData*) md;
 266                         if(amd->multi)
 267                                 amd->prevCos= MEM_dupallocN(vertexCos);
 268                 }
 269                 /* lattice/mesh modifier too */
 270         }
 271 }
 272
 273
 274 static void latticeModifier_deformVerts(
 275                                         ModifierData *md, Object *ob, DerivedMesh *derivedData,
 276      float (*vertexCos)[3], int numVerts)
 277 {
 278         LatticeModifierData *lmd = (LatticeModifierData*) md;
 279
 280
 281         modifier_vgroup_cache(md, vertexCos); /* if next modifier needs original vertices */
 282
 283         lattice_deform_verts(lmd->object, ob, derivedData,
 284                              vertexCos, numVerts, lmd->name);
 285 }
 286
 287 static void latticeModifier_deformVertsEM(
 288                                           ModifierData *md, Object *ob, EditMesh *editData,
 289        DerivedMesh *derivedData, float (*vertexCos)[3], int numVerts)
 290 {
 291         DerivedMesh *dm = derivedData;
 292
 293         if(!derivedData) dm = CDDM_from_editmesh(editData, ob->data);
 294
 295         latticeModifier_deformVerts(md, ob, dm, vertexCos, numVerts);
 296
 297         if(!derivedData) dm->release(dm);
 298 }
 299
 300 /* Subsurf */
 301
 302 static void subsurfModifier_initData(ModifierData *md)
 303 {
 304         SubsurfModifierData *smd = (SubsurfModifierData*) md;
 305
 306         smd->levels = 1;
 307         smd->renderLevels = 2;
 308         smd->flags |= eSubsurfModifierFlag_SubsurfUv;
 309 }
 310
 311 static void subsurfModifier_copyData(ModifierData *md, ModifierData *target)
 312 {
 313         SubsurfModifierData *smd = (SubsurfModifierData*) md;
 314         SubsurfModifierData *tsmd = (SubsurfModifierData*) target;
 315
 316         tsmd->flags = smd->flags;
 317         tsmd->levels = smd->levels;
 318         tsmd->renderLevels = smd->renderLevels;
 319         tsmd->subdivType = smd->subdivType;
 320 }
 321
 322 static void subsurfModifier_freeData(ModifierData *md)
 323 {
 324         SubsurfModifierData *smd = (SubsurfModifierData*) md;
 325
 326         if(smd->mCache) {
 327                 ccgSubSurf_free(smd->mCache);
 328         }
 329         if(smd->emCache) {
 330                 ccgSubSurf_free(smd->emCache);
 331         }
 332 }
 333
 334 static DerivedMesh *subsurfModifier_applyModifier(
 335                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
 336   int useRenderParams, int isFinalCalc)
 337 {
 338         SubsurfModifierData *smd = (SubsurfModifierData*) md;
 339         DerivedMesh *result;
 340
 341         result = subsurf_make_derived_from_derived(derivedData, smd,
 342                         useRenderParams, NULL,
 343    isFinalCalc, 0);
 344
 345         return result;
 346 }
 347
 348 static DerivedMesh *subsurfModifier_applyModifierEM(
 349                 ModifierData *md, Object *ob, EditMesh *editData,
 350   DerivedMesh *derivedData)
 351 {
 352         SubsurfModifierData *smd = (SubsurfModifierData*) md;
 353         DerivedMesh *result;
 354
 355         result = subsurf_make_derived_from_derived(derivedData, smd, 0,
 356                         NULL, 0, 1);
 357
 358         return result;
 359 }
 360
 361 /* Build */
 362
 363 static void buildModifier_initData(ModifierData *md)
 364 {
 365         BuildModifierData *bmd = (BuildModifierData*) md;
 366
 367         bmd->start = 1.0;
 368         bmd->length = 100.0;
 369 }
 370
 371 static void buildModifier_copyData(ModifierData *md, ModifierData *target)
 372 {
 373         BuildModifierData *bmd = (BuildModifierData*) md;
 374         BuildModifierData *tbmd = (BuildModifierData*) target;
 375
 376         tbmd->start = bmd->start;
 377         tbmd->length = bmd->length;
 378         tbmd->randomize = bmd->randomize;
 379         tbmd->seed = bmd->seed;
 380 }
 381
 382 static int buildModifier_dependsOnTime(ModifierData *md)
 383 {
 384         return 1;
 385 }
 386
 387 static DerivedMesh *buildModifier_applyModifier(ModifierData *md, Object *ob,
 388                 DerivedMesh *derivedData,
 389   int useRenderParams, int isFinalCalc)
 390 {
 391         DerivedMesh *dm = derivedData;
 392         DerivedMesh *result;
 393         BuildModifierData *bmd = (BuildModifierData*) md;
 394         int i;
 395         int numFaces, numEdges;
 396         int maxVerts, maxEdges, maxFaces;
 397         int *vertMap, *edgeMap, *faceMap;
 398         float frac;
 399         GHashIterator *hashIter;
 400         /* maps vert indices in old mesh to indices in new mesh */
 401         GHash *vertHash = BLI_ghash_new(BLI_ghashutil_inthash,
 402                                         BLI_ghashutil_intcmp);
 403         /* maps edge indices in new mesh to indices in old mesh */
 404         GHash *edgeHash = BLI_ghash_new(BLI_ghashutil_inthash,
 405                                         BLI_ghashutil_intcmp);
 406
 407         maxVerts = dm->getNumVerts(dm);
 408         vertMap = MEM_callocN(sizeof(*vertMap) * maxVerts,
 409                               "build modifier vertMap");
 410         for(i = 0; i < maxVerts; ++i) vertMap[i] = i;
 411
 412         maxEdges = dm->getNumEdges(dm);
 413         edgeMap = MEM_callocN(sizeof(*edgeMap) * maxEdges,
 414                               "build modifier edgeMap");
 415         for(i = 0; i < maxEdges; ++i) edgeMap[i] = i;
 416
 417         maxFaces = dm->getNumFaces(dm);
 418         faceMap = MEM_callocN(sizeof(*faceMap) * maxFaces,
 419                               "build modifier faceMap");
 420         for(i = 0; i < maxFaces; ++i) faceMap[i] = i;
 421
 422         if (ob) {
 423                 frac = bsystem_time(ob, (float)G.scene->r.cfra,
 424                                     bmd->start - 1.0f) / bmd->length;
 425         } else {
 426                 frac = G.scene->r.cfra - bmd->start / bmd->length;
 427         }
 428         CLAMP(frac, 0.0, 1.0);
 429
 430         numFaces = dm->getNumFaces(dm) * frac;
 431         numEdges = dm->getNumEdges(dm) * frac;
 432
 433         /* if there's at least one face, build based on faces */
 434         if(numFaces) {
 435                 int maxEdges;
 436
 437                 if(bmd->randomize)
 438                         BLI_array_randomize(faceMap, sizeof(*faceMap),
 439                                             maxFaces, bmd->seed);
 440
 441                 /* get the set of all vert indices that will be in the final mesh,
 442                 * mapped to the new indices
 443                 */
 444                 for(i = 0; i < numFaces; ++i) {
 445                         MFace mf;
 446                         dm->getFace(dm, faceMap[i], &mf);
 447
 448                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1)))
 449                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v1),
 450                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
 451                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2)))
 452                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v2),
 453                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
 454                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3)))
 455                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v3),
 456                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
 457                         if(mf.v4 && !BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4)))
 458                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(mf.v4),
 459                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
 460                 }
 461
 462                 /* get the set of edges that will be in the new mesh (i.e. all edges
 463                 * that have both verts in the new mesh)
 464                 */
 465                 maxEdges = dm->getNumEdges(dm);
 466                 for(i = 0; i < maxEdges; ++i) {
 467                         MEdge me;
 468                         dm->getEdge(dm, i, &me);
 469
 470                         if(BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1))
 471                                                 && BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
 472                                 BLI_ghash_insert(edgeHash,
 473                                         SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)), SET_INT_IN_POINTER(i));
 474                 }
 475         } else if(numEdges) {
 476                 if(bmd->randomize)
 477                         BLI_array_randomize(edgeMap, sizeof(*edgeMap),
 478                                             maxEdges, bmd->seed);
 479
 480                 /* get the set of all vert indices that will be in the final mesh,
 481                 * mapped to the new indices
 482                 */
 483                 for(i = 0; i < numEdges; ++i) {
 484                         MEdge me;
 485                         dm->getEdge(dm, edgeMap[i], &me);
 486
 487                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)))
 488                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v1),
 489                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
 490                         if(!BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)))
 491                                 BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(me.v2),
 492                                         SET_INT_IN_POINTER(BLI_ghash_size(vertHash)));
 493                 }
 494
 495                 /* get the set of edges that will be in the new mesh
 496                 */
 497                 for(i = 0; i < numEdges; ++i) {
 498                         MEdge me;
 499                         dm->getEdge(dm, edgeMap[i], &me);
 500
 501                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(BLI_ghash_size(edgeHash)),
 502                                          SET_INT_IN_POINTER(edgeMap[i]));
 503                 }
 504         } else {
 505                 int numVerts = dm->getNumVerts(dm) * frac;
 506
 507                 if(bmd->randomize)
 508                         BLI_array_randomize(vertMap, sizeof(*vertMap),
 509                                             maxVerts, bmd->seed);
 510
 511                 /* get the set of all vert indices that will be in the final mesh,
 512                 * mapped to the new indices
 513                 */
 514                 for(i = 0; i < numVerts; ++i)
 515                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(vertMap[i]), SET_INT_IN_POINTER(i));
 516         }
 517
 518         /* now we know the number of verts, edges and faces, we can create
 519         * the mesh
 520         */
 521         result = CDDM_from_template(dm, BLI_ghash_size(vertHash),
 522                                     BLI_ghash_size(edgeHash), numFaces);
 523
 524         /* copy the vertices across */
 525         for(hashIter = BLI_ghashIterator_new(vertHash);
 526                    !BLI_ghashIterator_isDone(hashIter);
 527                    BLI_ghashIterator_step(hashIter)) {
 528                            MVert source;
 529                            MVert *dest;
 530                            int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
 531                            int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
 532
 533                            dm->getVert(dm, oldIndex, &source);
 534                            dest = CDDM_get_vert(result, newIndex);
 535
 536                            DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
 537                            *dest = source;
 538                    }
 539                    BLI_ghashIterator_free(hashIter);
 540
 541                    /* copy the edges across, remapping indices */
 542                    for(i = 0; i < BLI_ghash_size(edgeHash); ++i) {
 543                            MEdge source;
 544                            MEdge *dest;
 545                            int oldIndex = GET_INT_FROM_POINTER(BLI_ghash_lookup(edgeHash, SET_INT_IN_POINTER(i)));
 546
 547                            dm->getEdge(dm, oldIndex, &source);
 548                            dest = CDDM_get_edge(result, i);
 549
 550                            source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
 551                            source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
 552
 553                            DM_copy_edge_data(dm, result, oldIndex, i, 1);
 554                            *dest = source;
 555                    }
 556
 557                    /* copy the faces across, remapping indices */
 558                    for(i = 0; i < numFaces; ++i) {
 559                            MFace source;
 560                            MFace *dest;
 561                            int orig_v4;
 562
 563                            dm->getFace(dm, faceMap[i], &source);
 564                            dest = CDDM_get_face(result, i);
 565
 566                            orig_v4 = source.v4;
 567
 568                            source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
 569                            source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
 570                            source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
 571                            if(source.v4)
 572                                    source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
 573
 574                            DM_copy_face_data(dm, result, faceMap[i], i, 1);
 575                            *dest = source;
 576
 577                            test_index_face(dest, &result->faceData, i, (orig_v4 ? 4 : 3));
 578                    }
 579
 580                    CDDM_calc_normals(result);
 581
 582                    BLI_ghash_free(vertHash, NULL, NULL);
 583                    BLI_ghash_free(edgeHash, NULL, NULL);
 584
 585                    MEM_freeN(vertMap);
 586                    MEM_freeN(edgeMap);
 587                    MEM_freeN(faceMap);
 588
 589                    return result;
 590 }
 591
 592 /* Mask */
 593
 594 static void maskModifier_copyData(ModifierData *md, ModifierData *target)
 595 {
 596         MaskModifierData *mmd = (MaskModifierData*) md;
 597         MaskModifierData *tmmd = (MaskModifierData*) target;
 598
 599         strcpy(tmmd->vgroup, mmd->vgroup);
 600 }
 601
 602 static CustomDataMask maskModifier_requiredDataMask(ModifierData *md)
 603 {
 604         return (1 << CD_MDEFORMVERT);
 605 }
 606
 607 static void maskModifier_foreachObjectLink(
 608                                               ModifierData *md, Object *ob,
 609            void (*walk)(void *userData, Object *ob, Object **obpoin),
 610                   void *userData)
 611 {
 612         MaskModifierData *mmd = (MaskModifierData *)md;
 613         walk(userData, ob, &mmd->ob_arm);
 614 }
 615
 616 static void maskModifier_updateDepgraph(ModifierData *md, DagForest *forest,
 617                                            Object *ob, DagNode *obNode)
 618 {
 619         MaskModifierData *mmd = (MaskModifierData *)md;
 620
 621         if (mmd->ob_arm)
 622         {
 623                 DagNode *armNode = dag_get_node(forest, mmd->ob_arm);
 624
 625                 dag_add_relation(forest, armNode, obNode,
 626                                 DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Mask Modifier");
 627         }
 628 }
 629
 630 static DerivedMesh *maskModifier_applyModifier(ModifierData *md, Object *ob,
 631                 DerivedMesh *derivedData,
 632   int useRenderParams, int isFinalCalc)
 633 {
 634         MaskModifierData *mmd= (MaskModifierData *)md;
 635         DerivedMesh *dm= derivedData, *result= NULL;
 636         GHash *vertHash=NULL, *edgeHash, *faceHash;
 637         GHashIterator *hashIter;
 638         MDeformVert *dvert= NULL;
 639         int numFaces=0, numEdges=0, numVerts=0;
 640         int maxVerts, maxEdges, maxFaces;
 641         int i;
 642
 643         /* Overview of Method:
 644          *      1. Get the vertices that are in the vertexgroup of interest
 645          *      2. Filter out unwanted geometry (i.e. not in vertexgroup), by populating mappings with new vs old indices
 646          *      3. Make a new mesh containing only the mapping data
 647          */
 648
 649         /* get original number of verts, edges, and faces */
 650         maxVerts= dm->getNumVerts(dm);
 651         maxEdges= dm->getNumEdges(dm);
 652         maxFaces= dm->getNumFaces(dm);
 653
 654         /* check if we can just return the original mesh
 655          *      - must have verts and therefore verts assigned to vgroups to do anything useful
 656          */
 657         if ( !(ELEM(mmd->mode, MOD_MASK_MODE_ARM, MOD_MASK_MODE_VGROUP)) ||
 658                  (maxVerts == 0) || (ob->defbase.first == NULL) )
 659         {
 660                 return derivedData;
 661         }
 662
 663         /* if mode is to use selected armature bones, aggregate the bone groups */
 664         if (mmd->mode == MOD_MASK_MODE_ARM) /* --- using selected bones --- */
 665         {
 666                 GHash *vgroupHash, *boneHash;
 667                 Object *oba= mmd->ob_arm;
 668                 bPoseChannel *pchan;
 669                 bDeformGroup *def;
 670
 671                 /* check that there is armature object with bones to use, otherwise return original mesh */
 672                 if (ELEM(NULL, mmd->ob_arm, mmd->ob_arm->pose))
 673                         return derivedData;
 674
 675                 /* hashes for finding mapping of:
 676                  *      - vgroups to indicies -> vgroupHash  (string, int)
 677                  *      - bones to vgroup indices -> boneHash (index of vgroup, dummy)
 678                  */
 679                 vgroupHash= BLI_ghash_new(BLI_ghashutil_strhash, BLI_ghashutil_strcmp);
 680                 boneHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
 681
 682                 /* build mapping of names of vertex groups to indices */
 683                 for (i = 0, def = ob->defbase.first; def; def = def->next, i++)
 684                         BLI_ghash_insert(vgroupHash, def->name, SET_INT_IN_POINTER(i));
 685
 686                 /* get selected-posechannel <-> vertexgroup index mapping */
 687                 for (pchan= oba->pose->chanbase.first; pchan; pchan= pchan->next)
 688                 {
 689                         /* check if bone is selected */
 690                         // TODO: include checks for visibility too?
 691                         // FIXME: the depsgraph needs extensions to make this work in realtime...
 692                         if ( (pchan->bone) && (pchan->bone->flag & BONE_SELECTED) )
 693                         {
 694                                 /* check if hash has group for this bone */
 695                                 if (BLI_ghash_haskey(vgroupHash, pchan->name))
 696                                 {
 697                                         int defgrp_index= GET_INT_FROM_POINTER(BLI_ghash_lookup(vgroupHash, pchan->name));
 698
 699                                         /* add index to hash (store under key only) */
 700                                         BLI_ghash_insert(boneHash, SET_INT_IN_POINTER(defgrp_index), pchan);
 701                                 }
 702                         }
 703                 }
 704
 705                 /* if no bones selected, free hashes and return original mesh */
 706                 if (BLI_ghash_size(boneHash) == 0)
 707                 {
 708                         BLI_ghash_free(vgroupHash, NULL, NULL);
 709                         BLI_ghash_free(boneHash, NULL, NULL);
 710
 711                         return derivedData;
 712                 }
 713
 714                 /* repeat the previous check, but for dverts */
 715                 dvert= dm->getVertDataArray(dm, CD_MDEFORMVERT);
 716                 if (dvert == NULL)
 717                 {
 718                         BLI_ghash_free(vgroupHash, NULL, NULL);
 719                         BLI_ghash_free(boneHash, NULL, NULL);
 720
 721                         return derivedData;
 722                 }
 723
 724                 /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
 725                 vertHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
 726
 727                 /* add vertices which exist in vertexgroups into vertHash for filtering */
 728                 for (i = 0; i < maxVerts; i++)
 729                 {
 730                         MDeformWeight *def_weight = NULL;
 731                         int j;
 732
 733                         for (j= 0; j < dvert[i].totweight; j++)
 734                         {
 735                                 if (BLI_ghash_haskey(boneHash, SET_INT_IN_POINTER(dvert[i].dw[j].def_nr)))
 736                                 {
 737                                         def_weight = &dvert[i].dw[j];
 738                                         break;
 739                                 }
 740                         }
 741
 742                         /* check if include vert in vertHash */
 743                         if (mmd->flag & MOD_MASK_INV) {
 744                                 /* if this vert is in the vgroup, don't include it in vertHash */
 745                                 if (def_weight) continue;
 746                         }
 747                         else {
 748                                 /* if this vert isn't in the vgroup, don't include it in vertHash */
 749                                 if (!def_weight) continue;
 750                         }
 751
 752                         /* add to ghash for verts (numVerts acts as counter for mapping) */
 753                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
 754                         numVerts++;
 755                 }
 756
 757                 /* free temp hashes */
 758                 BLI_ghash_free(vgroupHash, NULL, NULL);
 759                 BLI_ghash_free(boneHash, NULL, NULL);
 760         }
 761         else            /* --- Using Nominated VertexGroup only --- */
 762         {
 763                 int defgrp_index = -1;
 764
 765                 /* get index of vertex group */
 766                 if (mmd->vgroup[0])
 767                 {
 768                         bDeformGroup *def;
 769
 770                         /* find index by comparing names - SLOW... */
 771                         for (i = 0, def = ob->defbase.first; def; def = def->next, i++)
 772                         {
 773                                 if (!strcmp(def->name, mmd->vgroup))
 774                                 {
 775                                         defgrp_index = i;
 776                                         break;
 777                                 }
 778                         }
 779                 }
 780
 781                 /* get dverts */
 782                 if (defgrp_index >= 0)
 783                         dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
 784
 785                 /* if no vgroup (i.e. dverts) found, return the initial mesh */
 786                 if ((defgrp_index < 0) || (dvert == NULL))
 787                         return dm;
 788
 789                 /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
 790                 vertHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
 791
 792                 /* add vertices which exist in vertexgroup into ghash for filtering */
 793                 for (i = 0; i < maxVerts; i++)
 794                 {
 795                         MDeformWeight *def_weight = NULL;
 796                         int j;
 797
 798                         for (j= 0; j < dvert[i].totweight; j++)
 799                         {
 800                                 if (dvert[i].dw[j].def_nr == defgrp_index)
 801                                 {
 802                                         def_weight = &dvert[i].dw[j];
 803                                         break;
 804                                 }
 805                         }
 806
 807                         /* check if include vert in vertHash */
 808                         if (mmd->flag & MOD_MASK_INV) {
 809                                 /* if this vert is in the vgroup, don't include it in vertHash */
 810                                 if (def_weight) continue;
 811                         }
 812                         else {
 813                                 /* if this vert isn't in the vgroup, don't include it in vertHash */
 814                                 if (!def_weight) continue;
 815                         }
 816
 817                         /* add to ghash for verts (numVerts acts as counter for mapping) */
 818                         BLI_ghash_insert(vertHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numVerts));
 819                         numVerts++;
 820                 }
 821         }
 822
 823         /* hashes for quickly providing a mapping from old to new - use key=oldindex, value=newindex */
 824         edgeHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
 825         faceHash= BLI_ghash_new(BLI_ghashutil_inthash, BLI_ghashutil_intcmp);
 826
 827         /* loop over edges and faces, and do the same thing to
 828          * ensure that they only reference existing verts
 829          */
 830         for (i = 0; i < maxEdges; i++)
 831         {
 832                 MEdge me;
 833                 dm->getEdge(dm, i, &me);
 834
 835                 /* only add if both verts will be in new mesh */
 836                 if ( BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v1)) &&
 837                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(me.v2)) )
 838                 {
 839                         BLI_ghash_insert(edgeHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numEdges));
 840                         numEdges++;
 841                 }
 842         }
 843         for (i = 0; i < maxFaces; i++)
 844         {
 845                 MFace mf;
 846                 dm->getFace(dm, i, &mf);
 847
 848                 /* all verts must be available */
 849                 if ( BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v1)) &&
 850                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v2)) &&
 851                          BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v3)) &&
 852                         (mf.v4==0 || BLI_ghash_haskey(vertHash, SET_INT_IN_POINTER(mf.v4))) )
 853                 {
 854                         BLI_ghash_insert(faceHash, SET_INT_IN_POINTER(i), SET_INT_IN_POINTER(numFaces));
 855                         numFaces++;
 856                 }
 857         }
 858
 859
 860         /* now we know the number of verts, edges and faces,
 861          * we can create the new (reduced) mesh
 862          */
 863         result = CDDM_from_template(dm, numVerts, numEdges, numFaces);
 864
 865
 866         /* using ghash-iterators, map data into new mesh */
 867                 /* vertices */
 868         for ( hashIter = BLI_ghashIterator_new(vertHash);
 869                   !BLI_ghashIterator_isDone(hashIter);
 870                   BLI_ghashIterator_step(hashIter) )
 871         {
 872                 MVert source;
 873                 MVert *dest;
 874                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
 875                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
 876
 877                 dm->getVert(dm, oldIndex, &source);
 878                 dest = CDDM_get_vert(result, newIndex);
 879
 880                 DM_copy_vert_data(dm, result, oldIndex, newIndex, 1);
 881                 *dest = source;
 882         }
 883         BLI_ghashIterator_free(hashIter);
 884
 885                 /* edges */
 886         for ( hashIter = BLI_ghashIterator_new(edgeHash);
 887                   !BLI_ghashIterator_isDone(hashIter);
 888                   BLI_ghashIterator_step(hashIter) )
 889         {
 890                 MEdge source;
 891                 MEdge *dest;
 892                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
 893                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
 894
 895                 dm->getEdge(dm, oldIndex, &source);
 896                 dest = CDDM_get_edge(result, newIndex);
 897
 898                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
 899                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
 900
 901                 DM_copy_edge_data(dm, result, oldIndex, newIndex, 1);
 902                 *dest = source;
 903         }
 904         BLI_ghashIterator_free(hashIter);
 905
 906                 /* faces */
 907         for ( hashIter = BLI_ghashIterator_new(faceHash);
 908                   !BLI_ghashIterator_isDone(hashIter);
 909                   BLI_ghashIterator_step(hashIter) )
 910         {
 911                 MFace source;
 912                 MFace *dest;
 913                 int oldIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getKey(hashIter));
 914                 int newIndex = GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(hashIter));
 915                 int orig_v4;
 916
 917                 dm->getFace(dm, oldIndex, &source);
 918                 dest = CDDM_get_face(result, newIndex);
 919
 920                 orig_v4 = source.v4;
 921
 922                 source.v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v1)));
 923                 source.v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v2)));
 924                 source.v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v3)));
 925                 if (source.v4)
 926                    source.v4 = GET_INT_FROM_POINTER(BLI_ghash_lookup(vertHash, SET_INT_IN_POINTER(source.v4)));
 927
 928                 DM_copy_face_data(dm, result, oldIndex, newIndex, 1);
 929                 *dest = source;
 930
 931                 test_index_face(dest, &result->faceData, newIndex, (orig_v4 ? 4 : 3));
 932         }
 933         BLI_ghashIterator_free(hashIter);
 934
 935         /* recalculate normals */
 936         CDDM_calc_normals(result);
 937
 938         /* free hashes */
 939         BLI_ghash_free(vertHash, NULL, NULL);
 940         BLI_ghash_free(edgeHash, NULL, NULL);
 941         BLI_ghash_free(faceHash, NULL, NULL);
 942
 943         /* return the new mesh */
 944         return result;
 945 }
 946
 947 /* Array */
 948 /* Array modifier: duplicates the object multiple times along an axis
 949 */
 950
 951 static void arrayModifier_initData(ModifierData *md)
 952 {
 953         ArrayModifierData *amd = (ArrayModifierData*) md;
 954
 955         /* default to 2 duplicates distributed along the x-axis by an
 956         offset of 1 object-width
 957         */
 958         amd->start_cap = amd->end_cap = amd->curve_ob = amd->offset_ob = NULL;
 959         amd->count = 2;
 960         amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
 961         amd->scale[0] = 1;
 962         amd->scale[1] = amd->scale[2] = 0;
 963         amd->length = 0;
 964         amd->merge_dist = 0.01;
 965         amd->fit_type = MOD_ARR_FIXEDCOUNT;
 966         amd->offset_type = MOD_ARR_OFF_RELATIVE;
 967         amd->flags = 0;
 968 }
 969
 970 static void arrayModifier_copyData(ModifierData *md, ModifierData *target)
 971 {
 972         ArrayModifierData *amd = (ArrayModifierData*) md;
 973         ArrayModifierData *tamd = (ArrayModifierData*) target;
 974
 975         tamd->start_cap = amd->start_cap;
 976         tamd->end_cap = amd->end_cap;
 977         tamd->curve_ob = amd->curve_ob;
 978         tamd->offset_ob = amd->offset_ob;
 979         tamd->count = amd->count;
 980         VECCOPY(tamd->offset, amd->offset);
 981         VECCOPY(tamd->scale, amd->scale);
 982         tamd->length = amd->length;
 983         tamd->merge_dist = amd->merge_dist;
 984         tamd->fit_type = amd->fit_type;
 985         tamd->offset_type = amd->offset_type;
 986         tamd->flags = amd->flags;
 987 }
 988
 989 static void arrayModifier_foreachObjectLink(
 990                                             ModifierData *md, Object *ob,
 991          void (*walk)(void *userData, Object *ob, Object **obpoin),
 992                 void *userData)
 993 {
 994         ArrayModifierData *amd = (ArrayModifierData*) md;
 995
 996         walk(userData, ob, &amd->start_cap);
 997         walk(userData, ob, &amd->end_cap);
 998         walk(userData, ob, &amd->curve_ob);
 999         walk(userData, ob, &amd->offset_ob);
1000 }
1001
1002 static void arrayModifier_updateDepgraph(ModifierData *md, DagForest *forest,
1003                                          Object *ob, DagNode *obNode)
1004 {
1005         ArrayModifierData *amd = (ArrayModifierData*) md;
1006
1007         if (amd->start_cap) {
1008                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
1009
1010                 dag_add_relation(forest, curNode, obNode,
1011                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1012         }
1013         if (amd->end_cap) {
1014                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
1015
1016                 dag_add_relation(forest, curNode, obNode,
1017                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1018         }
1019         if (amd->curve_ob) {
1020                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
1021
1022                 dag_add_relation(forest, curNode, obNode,
1023                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1024         }
1025         if (amd->offset_ob) {
1026                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
1027
1028                 dag_add_relation(forest, curNode, obNode,
1029                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
1030         }
1031 }
1032
1033 float vertarray_size(MVert *mvert, int numVerts, int axis)
1034 {
1035         int i;
1036         float min_co, max_co;
1037
1038         /* if there are no vertices, width is 0 */
1039         if(numVerts == 0) return 0;
1040
1041         /* find the minimum and maximum coordinates on the desired axis */
1042         min_co = max_co = mvert->co[axis];
1043         ++mvert;
1044         for(i = 1; i < numVerts; ++i, ++mvert) {
1045                 if(mvert->co[axis] < min_co) min_co = mvert->co[axis];
1046                 if(mvert->co[axis] > max_co) max_co = mvert->co[axis];
1047         }
1048
1049         return max_co - min_co;
1050 }
1051
1052 typedef struct IndexMapEntry {
1053         /* the new vert index that this old vert index maps to */
1054         int new;
1055         /* -1 if this vert isn't merged, otherwise the old vert index it
1056         * should be replaced with
1057         */
1058         int merge;
1059         /* 1 if this vert's first copy is merged with the last copy of its
1060         * merge target, otherwise 0
1061         */
1062         short merge_final;
1063 } IndexMapEntry;
1064
1065 /* indexMap - an array of IndexMap entries
1066  * oldIndex - the old index to map
1067  * copyNum - the copy number to map to (original = 0, first copy = 1, etc.)
1068  */
1069 static int calc_mapping(IndexMapEntry *indexMap, int oldIndex, int copyNum)
1070 {
1071         if(indexMap[oldIndex].merge < 0) {
1072                 /* vert wasn't merged, so use copy of this vert */
1073                 return indexMap[oldIndex].new + copyNum;
1074         } else if(indexMap[oldIndex].merge == oldIndex) {
1075                 /* vert was merged with itself */
1076                 return indexMap[oldIndex].new;
1077         } else {
1078                 /* vert was merged with another vert */
1079                 /* follow the chain of merges to the end, or until we've passed
1080                 * a number of vertices equal to the copy number
1081                 */
1082                 if(copyNum <= 0)
1083                         return indexMap[oldIndex].new;
1084                 else
1085                         return calc_mapping(indexMap, indexMap[oldIndex].merge,
1086                                             copyNum - 1);
1087         }
1088 }
1089
1090 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
1091                                           Object *ob, DerivedMesh *dm,
1092        int initFlags)
1093 {
1094         int i, j;
1095         /* offset matrix */
1096         float offset[4][4];
1097         float final_offset[4][4];
1098         float tmp_mat[4][4];
1099         float length = amd->length;
1100         int count = amd->count;
1101         int numVerts, numEdges, numFaces;
1102         int maxVerts, maxEdges, maxFaces;
1103         int finalVerts, finalEdges, finalFaces;
1104         DerivedMesh *result, *start_cap = NULL, *end_cap = NULL;
1105         MVert *mvert, *src_mvert;
1106         MEdge *medge;
1107         MFace *mface;
1108
1109         IndexMapEntry *indexMap;
1110
1111         EdgeHash *edges;
1112
1113         /* need to avoid infinite recursion here */
1114         if(amd->start_cap && amd->start_cap != ob)
1115                 start_cap = mesh_get_derived_final(amd->start_cap, CD_MASK_MESH);
1116         if(amd->end_cap && amd->end_cap != ob)
1117                 end_cap = mesh_get_derived_final(amd->end_cap, CD_MASK_MESH);
1118
1119         MTC_Mat4One(offset);
1120
1121         indexMap = MEM_callocN(sizeof(*indexMap) * dm->getNumVerts(dm),
1122                                "indexmap");
1123
1124         src_mvert = dm->getVertArray(dm);
1125
1126         maxVerts = dm->getNumVerts(dm);
1127
1128         if(amd->offset_type & MOD_ARR_OFF_CONST)
1129                 VecAddf(offset[3], offset[3], amd->offset);
1130         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
1131                 for(j = 0; j < 3; j++)
1132                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
1133                                         maxVerts, j);
1134         }
1135
1136         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
1137                 float obinv[4][4];
1138                 float result_mat[4][4];
1139
1140                 if(ob)
1141                         MTC_Mat4Invert(obinv, ob->obmat);
1142                 else
1143                         MTC_Mat4One(obinv);
1144
1145                 MTC_Mat4MulSerie(result_mat, offset,
1146                                  obinv, amd->offset_ob->obmat,
1147      NULL, NULL, NULL, NULL, NULL);
1148                 MTC_Mat4CpyMat4(offset, result_mat);
1149         }
1150
1151         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
1152                 Curve *cu = amd->curve_ob->data;
1153                 if(cu) {
1154                         float tmp_mat[3][3];
1155                         float scale;
1156
1157                         object_to_mat3(amd->curve_ob, tmp_mat);
1158                         scale = Mat3ToScalef(tmp_mat);
1159
1160                         if(!cu->path) {
1161                                 cu->flag |= CU_PATH; // needed for path & bevlist
1162                                 makeDispListCurveTypes(amd->curve_ob, 0);
1163                         }
1164                         if(cu->path)
1165                                 length = scale*cu->path->totdist;
1166                 }
1167         }
1168
1169         /* calculate the maximum number of copies which will fit within the
1170         prescribed length */
1171         if(amd->fit_type == MOD_ARR_FITLENGTH
1172                   || amd->fit_type == MOD_ARR_FITCURVE) {
1173                 float dist = sqrt(MTC_dot3Float(offset[3], offset[3]));
1174
1175                 if(dist > 1e-6f)
1176                         /* this gives length = first copy start to last copy end
1177                         add a tiny offset for floating point rounding errors */
1178                         count = (length + 1e-6f) / dist;
1179                 else
1180                         /* if the offset has no translation, just make one copy */
1181                         count = 1;
1182                   }
1183
1184                   if(count < 1)
1185                           count = 1;
1186
1187         /* allocate memory for count duplicates (including original) plus
1188                   * start and end caps
1189         */
1190                   finalVerts = dm->getNumVerts(dm) * count;
1191                   finalEdges = dm->getNumEdges(dm) * count;
1192                   finalFaces = dm->getNumFaces(dm) * count;
1193                   if(start_cap) {
1194                           finalVerts += start_cap->getNumVerts(start_cap);
1195                           finalEdges += start_cap->getNumEdges(start_cap);
1196                           finalFaces += start_cap->getNumFaces(start_cap);
1197                   }
1198                   if(end_cap) {
1199                           finalVerts += end_cap->getNumVerts(end_cap);
1200                           finalEdges += end_cap->getNumEdges(end_cap);
1201                           finalFaces += end_cap->getNumFaces(end_cap);
1202                   }
1203                   result = CDDM_from_template(dm, finalVerts, finalEdges, finalFaces);
1204
1205                   /* calculate the offset matrix of the final copy (for merging) */
1206                   MTC_Mat4One(final_offset);
1207
1208                   for(j=0; j < count - 1; j++) {
1209                           MTC_Mat4MulMat4(tmp_mat, final_offset, offset);
1210                           MTC_Mat4CpyMat4(final_offset, tmp_mat);
1211                   }
1212
1213                   numVerts = numEdges = numFaces = 0;
1214                   mvert = CDDM_get_verts(result);
1215
1216                   for (i = 0; i < maxVerts; i++) {
1217                           indexMap[i].merge = -1; /* default to no merge */
1218                           indexMap[i].merge_final = 0; /* default to no merge */
1219                   }
1220
1221                   for (i = 0; i < maxVerts; i++) {
1222                           MVert *inMV;
1223                           MVert *mv = &mvert[numVerts];
1224                           MVert *mv2;
1225                           float co[3];
1226
1227                           inMV = &src_mvert[i];
1228
1229                           DM_copy_vert_data(dm, result, i, numVerts, 1);
1230                           *mv = *inMV;
1231                           numVerts++;
1232
1233                           indexMap[i].new = numVerts - 1;
1234
1235                           VECCOPY(co, mv->co);
1236
1237                 /* Attempts to merge verts from one duplicate with verts from the
1238                           * next duplicate which are closer than amd->merge_dist.
1239                           * Only the first such vert pair is merged.
1240                           * If verts are merged in the first duplicate pair, they are merged
1241                           * in all pairs.
1242                 */
1243                           if((count > 1) && (amd->flags & MOD_ARR_MERGE)) {
1244                                   float tmp_co[3];
1245                                   VECCOPY(tmp_co, mv->co);
1246                                   MTC_Mat4MulVecfl(offset, tmp_co);
1247
1248                                   for(j = 0; j < maxVerts; j++) {
1249                                           /* if vertex already merged, don't use it */
1250                                           if( indexMap[j].merge != -1 ) continue;
1251
1252                                           inMV = &src_mvert[j];
1253                                           /* if this vert is within merge limit, merge */
1254                                           if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist)) {
1255                                                   indexMap[i].merge = j;
1256
1257                                                   /* test for merging with final copy of merge target */
1258                                                   if(amd->flags & MOD_ARR_MERGEFINAL) {
1259                                                           VECCOPY(tmp_co, inMV->co);
1260                                                           inMV = &src_mvert[i];
1261                                                           MTC_Mat4MulVecfl(final_offset, tmp_co);
1262                                                           if(VecLenCompare(tmp_co, inMV->co, amd->merge_dist))
1263                                                                   indexMap[i].merge_final = 1;
1264                                                   }
1265                                                   break;
1266                                           }
1267                                   }
1268                           }
1269
1270                           /* if no merging, generate copies of this vert */
1271                           if(indexMap[i].merge < 0) {
1272                                   for(j=0; j < count - 1; j++) {
1273                                           mv2 = &mvert[numVerts];
1274
1275                                           DM_copy_vert_data(result, result, numVerts - 1, numVerts, 1);
1276                                           *mv2 = *mv;
1277                                           numVerts++;
1278
1279                                           MTC_Mat4MulVecfl(offset, co);
1280                                           VECCOPY(mv2->co, co);
1281                                   }
1282                           } else if(indexMap[i].merge != i && indexMap[i].merge_final) {
1283                         /* if this vert is not merging with itself, and it is merging
1284                                   * with the final copy of its merge target, remove the first copy
1285                         */
1286                                   numVerts--;
1287                                   DM_free_vert_data(result, numVerts, 1);
1288                           }
1289                   }
1290
1291                   /* make a hashtable so we can avoid duplicate edges from merging */
1292                   edges = BLI_edgehash_new();
1293
1294                   maxEdges = dm->getNumEdges(dm);
1295                   medge = CDDM_get_edges(result);
1296                   for(i = 0; i < maxEdges; i++) {
1297                           MEdge inMED;
1298                           MEdge med;
1299                           MEdge *med2;
1300                           int vert1, vert2;
1301
1302                           dm->getEdge(dm, i, &inMED);
1303
1304                           med = inMED;
1305                           med.v1 = indexMap[inMED.v1].new;
1306                           med.v2 = indexMap[inMED.v2].new;
1307
1308                 /* if vertices are to be merged with the final copies of their
1309                           * merge targets, calculate that final copy
1310                 */
1311                           if(indexMap[inMED.v1].merge_final) {
1312                                   med.v1 = calc_mapping(indexMap, indexMap[inMED.v1].merge,
1313                                                   count - 1);
1314                           }
1315                           if(indexMap[inMED.v2].merge_final) {
1316                                   med.v2 = calc_mapping(indexMap, indexMap[inMED.v2].merge,
1317                                                   count - 1);
1318                           }
1319
1320                           if(med.v1 == med.v2) continue;
1321
1322                           if (initFlags) {
1323                                   med.flag |= ME_EDGEDRAW | ME_EDGERENDER;
1324                           }
1325
1326                           if(!BLI_edgehash_haskey(edges, med.v1, med.v2)) {
1327                                   DM_copy_edge_data(dm, result, i, numEdges, 1);
1328                                   medge[numEdges] = med;
1329                                   numEdges++;
1330
1331                                   BLI_edgehash_insert(edges, med.v1, med.v2, NULL);
1332                           }
1333
1334                           for(j = 1; j < count; j++)
1335                           {
1336                                   vert1 = calc_mapping(indexMap, inMED.v1, j);
1337                                   vert2 = calc_mapping(indexMap, inMED.v2, j);
1338                                   /* avoid duplicate edges */
1339                                   if(!BLI_edgehash_haskey(edges, vert1, vert2)) {
1340                                           med2 = &medge[numEdges];
1341
1342                                           DM_copy_edge_data(dm, result, i, numEdges, 1);
1343                                           *med2 = med;
1344                                           numEdges++;
1345
1346                                           med2->v1 = vert1;
1347                                           med2->v2 = vert2;
1348
1349                                           BLI_edgehash_insert(edges, med2->v1, med2->v2, NULL);
1350                                   }
1351                           }
1352                   }
1353
1354                   maxFaces = dm->getNumFaces(dm);
1355                   mface = CDDM_get_faces(result);
1356                   for (i=0; i < maxFaces; i++) {
1357                           MFace inMF;
1358                           MFace *mf = &mface[numFaces];
1359
1360                           dm->getFace(dm, i, &inMF);
1361
1362                           DM_copy_face_data(dm, result, i, numFaces, 1);
1363                           *mf = inMF;
1364
1365                           mf->v1 = indexMap[inMF.v1].new;
1366                           mf->v2 = indexMap[inMF.v2].new;
1367                           mf->v3 = indexMap[inMF.v3].new;
1368                           if(inMF.v4)
1369                                   mf->v4 = indexMap[inMF.v4].new;
1370
1371                 /* if vertices are to be merged with the final copies of their
1372                           * merge targets, calculate that final copy
1373                 */
1374                           if(indexMap[inMF.v1].merge_final)
1375                                   mf->v1 = calc_mapping(indexMap, indexMap[inMF.v1].merge, count-1);
1376                           if(indexMap[inMF.v2].merge_final)
1377                                   mf->v2 = calc_mapping(indexMap, indexMap[inMF.v2].merge, count-1);
1378                           if(indexMap[inMF.v3].merge_final)
1379                                   mf->v3 = calc_mapping(indexMap, indexMap[inMF.v3].merge, count-1);
1380                           if(inMF.v4 && indexMap[inMF.v4].merge_final)
1381                                   mf->v4 = calc_mapping(indexMap, indexMap[inMF.v4].merge, count-1);
1382
1383                           if(test_index_face(mf, &result->faceData, numFaces, inMF.v4?4:3) < 3)
1384                                   continue;
1385
1386                           numFaces++;
1387
1388                           /* if the face has fewer than 3 vertices, don't create it */
1389                           if(mf->v3 == 0 || (mf->v1 && (mf->v1 == mf->v3 || mf->v1 == mf->v4))) {
1390                                   numFaces--;
1391                                   DM_free_face_data(result, numFaces, 1);
1392                           }
1393
1394                           for(j = 1; j < count; j++)
1395                           {
1396                                   MFace *mf2 = &mface[numFaces];
1397
1398                                   DM_copy_face_data(dm, result, i, numFaces, 1);
1399                                   *mf2 = *mf;
1400
1401                                   mf2->v1 = calc_mapping(indexMap, inMF.v1, j);
1402                                   mf2->v2 = calc_mapping(indexMap, inMF.v2, j);
1403                                   mf2->v3 = calc_mapping(indexMap, inMF.v3, j);
1404                                   if (inMF.v4)
1405                                           mf2->v4 = calc_mapping(indexMap, inMF.v4, j);
1406
1407                                   test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
1408                                   numFaces++;
1409
1410                                   /* if the face has fewer than 3 vertices, don't create it */
1411                                   if(mf2->v3 == 0 || (mf2->v1 && (mf2->v1 == mf2->v3 || mf2->v1 ==
1412                                                                  mf2->v4))) {
1413                                           numFaces--;
1414                                           DM_free_face_data(result, numFaces, 1);
1415                                                                  }
1416                           }
1417                   }
1418
1419                   /* add start and end caps */
1420                   if(start_cap) {
1421                           float startoffset[4][4];
1422                           MVert *cap_mvert;
1423                           MEdge *cap_medge;
1424                           MFace *cap_mface;
1425                           int *origindex;
1426                           int *vert_map;
1427                           int capVerts, capEdges, capFaces;
1428
1429                           capVerts = start_cap->getNumVerts(start_cap);
1430                           capEdges = start_cap->getNumEdges(start_cap);
1431                           capFaces = start_cap->getNumFaces(start_cap);
1432                           cap_mvert = start_cap->getVertArray(start_cap);
1433                           cap_medge = start_cap->getEdgeArray(start_cap);
1434                           cap_mface = start_cap->getFaceArray(start_cap);
1435
1436                           Mat4Invert(startoffset, offset);
1437
1438                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
1439                                           "arrayModifier_doArray vert_map");
1440
1441                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
1442                           for(i = 0; i < capVerts; i++) {
1443                                   MVert *mv = &cap_mvert[i];
1444                                   short merged = 0;
1445
1446                                   if(amd->flags & MOD_ARR_MERGE) {
1447                                           float tmp_co[3];
1448                                           MVert *in_mv;
1449                                           int j;
1450
1451                                           VECCOPY(tmp_co, mv->co);
1452                                           Mat4MulVecfl(startoffset, tmp_co);
1453
1454                                           for(j = 0; j < maxVerts; j++) {
1455                                                   in_mv = &src_mvert[j];
1456                                                   /* if this vert is within merge limit, merge */
1457                                                   if(VecLenCompare(tmp_co, in_mv->co, amd->merge_dist)) {
1458                                                           vert_map[i] = calc_mapping(indexMap, j, 0);
1459                                                           merged = 1;
1460                                                           break;
1461                                                   }
1462                                           }
1463                                   }
1464
1465                                   if(!merged) {
1466                                           DM_copy_vert_data(start_cap, result, i, numVerts, 1);
1467                                           mvert[numVerts] = *mv;
1468                                           Mat4MulVecfl(startoffset, mvert[numVerts].co);
1469                                           origindex[numVerts] = ORIGINDEX_NONE;
1470
1471                                           vert_map[i] = numVerts;
1472
1473                                           numVerts++;
1474                                   }
1475                           }
1476                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
1477                           for(i = 0; i < capEdges; i++) {
1478                                   int v1, v2;
1479
1480                                   v1 = vert_map[cap_medge[i].v1];
1481                                   v2 = vert_map[cap_medge[i].v2];
1482
1483                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
1484                                           DM_copy_edge_data(start_cap, result, i, numEdges, 1);
1485                                           medge[numEdges] = cap_medge[i];
1486                                           medge[numEdges].v1 = v1;
1487                                           medge[numEdges].v2 = v2;
1488                                           origindex[numEdges] = ORIGINDEX_NONE;
1489
1490                                           numEdges++;
1491                                   }
1492                           }
1493                           origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
1494                           for(i = 0; i < capFaces; i++) {
1495                                   DM_copy_face_data(start_cap, result, i, numFaces, 1);
1496                                   mface[numFaces] = cap_mface[i];
1497                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
1498                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
1499                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
1500                                   if(mface[numFaces].v4) {
1501                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
1502
1503                                           test_index_face(&mface[numFaces], &result->faceData,
1504                                                           numFaces, 4);
1505                                   }
1506                                   else
1507                                   {
1508                                           test_index_face(&mface[numFaces], &result->faceData,
1509                                                           numFaces, 3);
1510                                   }
1511
1512                                   origindex[numFaces] = ORIGINDEX_NONE;
1513
1514                                   numFaces++;
1515                           }
1516
1517                           MEM_freeN(vert_map);
1518                           start_cap->release(start_cap);
1519                   }
1520
1521                   if(end_cap) {
1522                           float endoffset[4][4];
1523                           MVert *cap_mvert;
1524                           MEdge *cap_medge;
1525                           MFace *cap_mface;
1526                           int *origindex;
1527                           int *vert_map;
1528                           int capVerts, capEdges, capFaces;
1529
1530                           capVerts = end_cap->getNumVerts(end_cap);
1531                           capEdges = end_cap->getNumEdges(end_cap);
1532                           capFaces = end_cap->getNumFaces(end_cap);
1533                           cap_mvert = end_cap->getVertArray(end_cap);
1534                           cap_medge = end_cap->getEdgeArray(end_cap);
1535                           cap_mface = end_cap->getFaceArray(end_cap);
1536
1537                           Mat4MulMat4(endoffset, final_offset, offset);
1538
1539                           vert_map = MEM_callocN(sizeof(*vert_map) * capVerts,
1540                                           "arrayModifier_doArray vert_map");
1541
1542                           origindex = result->getVertDataArray(result, CD_ORIGINDEX);
1543                           for(i = 0; i < capVerts; i++) {
1544                                   MVert *mv = &cap_mvert[i];
1545                                   short merged = 0;
1546
1547                                   if(amd->flags & MOD_ARR_MERGE) {
1548                                           float tmp_co[3];
1549                                           MVert *in_mv;
1550                                           int j;
1551
1552                                           VECCOPY(tmp_co, mv->co);
1553                                           Mat4MulVecfl(offset, tmp_co);
1554
1555                                           for(j = 0; j < maxVerts; j++) {
1556                                                   in_mv = &src_mvert[j];
1557                                                   /* if this vert is within merge limit, merge */
1558                                                   if(VecLenCompare(tmp_co, in_mv->co, amd->merge_dist)) {
1559                                                           vert_map[i] = calc_mapping(indexMap, j, count - 1);
1560                                                           merged = 1;
1561                                                           break;
1562                                                   }
1563                                           }
1564                                   }
1565
1566                                   if(!merged) {
1567                                           DM_copy_vert_data(end_cap, result, i, numVerts, 1);
1568                                           mvert[numVerts] = *mv;
1569                                           Mat4MulVecfl(endoffset, mvert[numVerts].co);
1570                                           origindex[numVerts] = ORIGINDEX_NONE;
1571
1572                                           vert_map[i] = numVerts;
1573
1574                                           numVerts++;
1575                                   }
1576                           }
1577                           origindex = result->getEdgeDataArray(result, CD_ORIGINDEX);
1578                           for(i = 0; i < capEdges; i++) {
1579                                   int v1, v2;
1580
1581                                   v1 = vert_map[cap_medge[i].v1];
1582                                   v2 = vert_map[cap_medge[i].v2];
1583
1584                                   if(!BLI_edgehash_haskey(edges, v1, v2)) {
1585                                           DM_copy_edge_data(end_cap, result, i, numEdges, 1);
1586                                           medge[numEdges] = cap_medge[i];
1587                                           medge[numEdges].v1 = v1;
1588                                           medge[numEdges].v2 = v2;
1589                                           origindex[numEdges] = ORIGINDEX_NONE;
1590
1591                                           numEdges++;
1592                                   }
1593                           }
1594                           origindex = result->getFaceDataArray(result, CD_ORIGINDEX);
1595                           for(i = 0; i < capFaces; i++) {
1596                                   DM_copy_face_data(end_cap, result, i, numFaces, 1);
1597                                   mface[numFaces] = cap_mface[i];
1598                                   mface[numFaces].v1 = vert_map[mface[numFaces].v1];
1599                                   mface[numFaces].v2 = vert_map[mface[numFaces].v2];
1600                                   mface[numFaces].v3 = vert_map[mface[numFaces].v3];
1601                                   if(mface[numFaces].v4) {
1602                                           mface[numFaces].v4 = vert_map[mface[numFaces].v4];
1603
1604                                           test_index_face(&mface[numFaces], &result->faceData,
1605                                                           numFaces, 4);
1606                                   }
1607                                   else
1608                                   {
1609                                           test_index_face(&mface[numFaces], &result->faceData,
1610                                                           numFaces, 3);
1611                                   }
1612                                   origindex[numFaces] = ORIGINDEX_NONE;
1613
1614                                   numFaces++;
1615                           }
1616
1617                           MEM_freeN(vert_map);
1618                           end_cap->release(end_cap);
1619                   }
1620
1621                   BLI_edgehash_free(edges, NULL);
1622                   MEM_freeN(indexMap);
1623
1624                   CDDM_lower_num_verts(result, numVerts);
1625                   CDDM_lower_num_edges(result, numEdges);
1626                   CDDM_lower_num_faces(result, numFaces);
1627
1628                   return result;
1629 }
1630
1631 static DerivedMesh *arrayModifier_applyModifier(
1632                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
1633   int useRenderParams, int isFinalCalc)
1634 {
1635         DerivedMesh *result;
1636         ArrayModifierData *amd = (ArrayModifierData*) md;
1637
1638         result = arrayModifier_doArray(amd, ob, derivedData, 0);
1639
1640         if(result != derivedData)
1641                 CDDM_calc_normals(result);
1642
1643         return result;
1644 }
1645
1646 static DerivedMesh *arrayModifier_applyModifierEM(
1647                 ModifierData *md, Object *ob, EditMesh *editData,
1648   DerivedMesh *derivedData)
1649 {
1650         return arrayModifier_applyModifier(md, ob, derivedData, 0, 1);
1651 }
1652
1653 /* Mirror */
1654
1655 static void mirrorModifier_initData(ModifierData *md)
1656 {
1657         MirrorModifierData *mmd = (MirrorModifierData*) md;
1658
1659         mmd->flag |= (MOD_MIR_AXIS_X | MOD_MIR_VGROUP);
1660         mmd->tolerance = 0.001;
1661         mmd->mirror_ob = NULL;
1662 }
1663
1664 static void mirrorModifier_copyData(ModifierData *md, ModifierData *target)
1665 {
1666         MirrorModifierData *mmd = (MirrorModifierData*) md;
1667         MirrorModifierData *tmmd = (MirrorModifierData*) target;
1668
1669         tmmd->axis = mmd->axis;
1670         tmmd->flag = mmd->flag;
1671         tmmd->tolerance = mmd->tolerance;
1672         tmmd->mirror_ob = mmd->mirror_ob;;
1673 }
1674
1675 static void mirrorModifier_foreachObjectLink(
1676                                              ModifierData *md, Object *ob,
1677           void (*walk)(void *userData, Object *ob, Object **obpoin),
1678                  void *userData)
1679 {
1680         MirrorModifierData *mmd = (MirrorModifierData*) md;
1681
1682         walk(userData, ob, &mmd->mirror_ob);
1683 }
1684
1685 static void mirrorModifier_updateDepgraph(ModifierData *md, DagForest *forest,
1686                                           Object *ob, DagNode *obNode)
1687 {
1688         MirrorModifierData *mmd = (MirrorModifierData*) md;
1689
1690         if(mmd->mirror_ob) {
1691                 DagNode *latNode = dag_get_node(forest, mmd->mirror_ob);
1692
1693                 dag_add_relation(forest, latNode, obNode,
1694                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Mirror Modifier");
1695         }
1696 }
1697
1698 /* finds the best possible flipped name. For renaming; check for unique names afterwards */
1699 /* if strip_number: removes number extensions */
1700 void vertgroup_flip_name (char *name, int strip_number)
1701 {
1702         int     len;
1703         char    prefix[128]={""};   /* The part before the facing */
1704         char    suffix[128]={""};   /* The part after the facing */
1705         char    replace[128]={""};  /* The replacement string */
1706         char    number[128]={""};   /* The number extension string */
1707         char    *index=NULL;
1708
1709         len= strlen(name);
1710         if(len<3) return; // we don't do names like .R or .L
1711
1712         /* We first check the case with a .### extension, let's find the last period */
1713         if(isdigit(name[len-1])) {
1714                 index= strrchr(name, '.'); // last occurrance
1715                 if (index && isdigit(index[1]) ) { // doesnt handle case bone.1abc2 correct..., whatever!
1716                         if(strip_number==0)
1717                                 strcpy(number, index);
1718                         *index= 0;
1719                         len= strlen(name);
1720                 }
1721         }
1722
1723         strcpy (prefix, name);
1724
1725 #define IS_SEPARATOR(a) ((a)=='.' || (a)==' ' || (a)=='-' || (a)=='_')
1726
1727         /* first case; separator . - _ with extensions r R l L  */
1728         if( IS_SEPARATOR(name[len-2]) ) {
1729                 switch(name[len-1]) {
1730                         case 'l':
1731                                 prefix[len-1]= 0;
1732                                 strcpy(replace, "r");
1733                                 break;
1734                         case 'r':
1735                                 prefix[len-1]= 0;
1736                                 strcpy(replace, "l");
1737                                 break;
1738                         case 'L':
1739                                 prefix[len-1]= 0;
1740                                 strcpy(replace, "R");
1741                                 break;
1742                         case 'R':
1743                                 prefix[len-1]= 0;
1744                                 strcpy(replace, "L");
1745                                 break;
1746                 }
1747         }
1748         /* case; beginning with r R l L , with separator after it */
1749         else if( IS_SEPARATOR(name[1]) ) {
1750                 switch(name[0]) {
1751                         case 'l':
1752                                 strcpy(replace, "r");
1753                                 strcpy(suffix, name+1);
1754                                 prefix[0]= 0;
1755                                 break;
1756                         case 'r':
1757                                 strcpy(replace, "l");
1758                                 strcpy(suffix, name+1);
1759                                 prefix[0]= 0;
1760                                 break;
1761                         case 'L':
1762                                 strcpy(replace, "R");
1763                                 strcpy(suffix, name+1);
1764                                 prefix[0]= 0;
1765                                 break;
1766                         case 'R':
1767                                 strcpy(replace, "L");
1768                                 strcpy(suffix, name+1);
1769                                 prefix[0]= 0;
1770                                 break;
1771                 }
1772         }
1773         else if(len > 5) {
1774                 /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */
1775                 index = BLI_strcasestr(prefix, "right");
1776                 if (index==prefix || index==prefix+len-5) {
1777                         if(index[0]=='r')
1778                                 strcpy (replace, "left");
1779                         else {
1780                                 if(index[1]=='I')
1781                                         strcpy (replace, "LEFT");
1782                                 else
1783                                         strcpy (replace, "Left");
1784                         }
1785                         *index= 0;
1786                         strcpy (suffix, index+5);
1787                 }
1788                 else {
1789                         index = BLI_strcasestr(prefix, "left");
1790                         if (index==prefix || index==prefix+len-4) {
1791                                 if(index[0]=='l')
1792                                         strcpy (replace, "right");
1793                                 else {
1794                                         if(index[1]=='E')
1795                                                 strcpy (replace, "RIGHT");
1796                                         else
1797                                                 strcpy (replace, "Right");
1798                                 }
1799                                 *index= 0;
1800                                 strcpy (suffix, index+4);
1801                         }
1802                 }
1803         }
1804
1805 #undef IS_SEPARATOR
1806
1807         sprintf (name, "%s%s%s%s", prefix, replace, suffix, number);
1808 }
1809
1810 static DerivedMesh *doMirrorOnAxis(MirrorModifierData *mmd,
1811                 Object *ob,
1812                 DerivedMesh *dm,
1813                 int initFlags,
1814                 int axis)
1815 {
1816         int i;
1817         float tolerance = mmd->tolerance;
1818         DerivedMesh *result;
1819         int numVerts, numEdges, numFaces;
1820         int maxVerts = dm->getNumVerts(dm);
1821         int maxEdges = dm->getNumEdges(dm);
1822         int maxFaces = dm->getNumFaces(dm);
1823         int vector_size=0, j, a, b;
1824         bDeformGroup *def, *defb;
1825         bDeformGroup **vector_def = NULL;
1826         int (*indexMap)[2];
1827         float mtx[4][4], imtx[4][4];
1828
1829         numVerts = numEdges = numFaces = 0;
1830
1831         indexMap = MEM_mallocN(sizeof(*indexMap) * maxVerts, "indexmap");
1832
1833         result = CDDM_from_template(dm, maxVerts * 2, maxEdges * 2, maxFaces * 2);
1834
1835
1836         if (mmd->flag & MOD_MIR_VGROUP) {
1837                 /* calculate the number of deformedGroups */
1838                 for(vector_size = 0, def = ob->defbase.first; def;
1839                     def = def->next, vector_size++);
1840
1841                 /* load the deformedGroups for fast access */
1842                 vector_def =
1843                     (bDeformGroup **)MEM_mallocN(sizeof(bDeformGroup*) * vector_size,
1844                                                  "group_index");
1845                 for(a = 0, def = ob->defbase.first; def; def = def->next, a++) {
1846                         vector_def[a] = def;
1847                 }
1848         }
1849
1850         if (mmd->mirror_ob) {
1851                 float obinv[4][4];
1852
1853                 Mat4Invert(obinv, mmd->mirror_ob->obmat);
1854                 Mat4MulMat4(mtx, ob->obmat, obinv);
1855                 Mat4Invert(imtx, mtx);
1856         }
1857
1858         for(i = 0; i < maxVerts; i++) {
1859                 MVert inMV;
1860                 MVert *mv = CDDM_get_vert(result, numVerts);
1861                 int isShared;
1862                 float co[3];
1863
1864                 dm->getVert(dm, i, &inMV);
1865
1866                 VecCopyf(co, inMV.co);
1867
1868                 if (mmd->mirror_ob) {
1869                         VecMat4MulVecfl(co, mtx, co);
1870                 }
1871                 isShared = ABS(co[axis])<=tolerance;
1872
1873                 /* Because the topology result (# of vertices) must be the same if
1874                 * the mesh data is overridden by vertex cos, have to calc sharedness
1875                 * based on original coordinates. This is why we test before copy.
1876                 */
1877                 DM_copy_vert_data(dm, result, i, numVerts, 1);
1878                 *mv = inMV;
1879                 numVerts++;
1880
1881                 indexMap[i][0] = numVerts - 1;
1882                 indexMap[i][1] = !isShared;
1883
1884                 if(isShared) {
1885                         co[axis] = 0;
1886                         if (mmd->mirror_ob) {
1887                                 VecMat4MulVecfl(co, imtx, co);
1888                         }
1889                         VecCopyf(mv->co, co);
1890
1891                         mv->flag |= ME_VERT_MERGED;
1892                 } else {
1893                         MVert *mv2 = CDDM_get_vert(result, numVerts);
1894                         MDeformVert *dvert = NULL;
1895
1896                         DM_copy_vert_data(dm, result, i, numVerts, 1);
1897                         *mv2 = *mv;
1898
1899                         co[axis] = -co[axis];
1900                         if (mmd->mirror_ob) {
1901                                 VecMat4MulVecfl(co, imtx, co);
1902                         }
1903                         VecCopyf(mv2->co, co);
1904
1905                         if (mmd->flag & MOD_MIR_VGROUP){
1906                                 dvert = DM_get_vert_data(result, numVerts, CD_MDEFORMVERT);
1907
1908                                 if (dvert)
1909                                 {
1910                                         for(j = 0; j < dvert[0].totweight; ++j)
1911                                         {
1912                                                 char tmpname[32];
1913
1914                                                 if(dvert->dw[j].def_nr < 0 ||
1915                                                    dvert->dw[j].def_nr >= vector_size)
1916                                                         continue;
1917
1918                                                 def = vector_def[dvert->dw[j].def_nr];
1919                                                 strcpy(tmpname, def->name);
1920                                                 vertgroup_flip_name(tmpname,0);
1921
1922                                                 for(b = 0, defb = ob->defbase.first; defb;
1923                                                     defb = defb->next, b++)
1924                                                 {
1925                                                         if(!strcmp(defb->name, tmpname))
1926                                                         {
1927                                                                 dvert->dw[j].def_nr = b;
1928                                                                 break;
1929                                                         }
1930                                                 }
1931                                         }
1932                                 }
1933                         }
1934
1935                         numVerts++;
1936                 }
1937         }
1938
1939         for(i = 0; i < maxEdges; i++) {
1940                 MEdge inMED;
1941                 MEdge *med = CDDM_get_edge(result, numEdges);
1942
1943                 dm->getEdge(dm, i, &inMED);
1944
1945                 DM_copy_edge_data(dm, result, i, numEdges, 1);
1946                 *med = inMED;
1947                 numEdges++;
1948
1949                 med->v1 = indexMap[inMED.v1][0];
1950                 med->v2 = indexMap[inMED.v2][0];
1951                 if(initFlags)
1952                         med->flag |= ME_EDGEDRAW | ME_EDGERENDER;
1953
1954                 if(indexMap[inMED.v1][1] || indexMap[inMED.v2][1]) {
1955                         MEdge *med2 = CDDM_get_edge(result, numEdges);
1956
1957                         DM_copy_edge_data(dm, result, i, numEdges, 1);
1958                         *med2 = *med;
1959                         numEdges++;
1960
1961                         med2->v1 += indexMap[inMED.v1][1];
1962                         med2->v2 += indexMap[inMED.v2][1];
1963                 }
1964         }
1965
1966         for(i = 0; i < maxFaces; i++) {
1967                 MFace inMF;
1968                 MFace *mf = CDDM_get_face(result, numFaces);
1969
1970                 dm->getFace(dm, i, &inMF);
1971
1972                 DM_copy_face_data(dm, result, i, numFaces, 1);
1973                 *mf = inMF;
1974                 numFaces++;
1975
1976                 mf->v1 = indexMap[inMF.v1][0];
1977                 mf->v2 = indexMap[inMF.v2][0];
1978                 mf->v3 = indexMap[inMF.v3][0];
1979                 mf->v4 = indexMap[inMF.v4][0];
1980
1981                 if(indexMap[inMF.v1][1]
1982                                  || indexMap[inMF.v2][1]
1983                                  || indexMap[inMF.v3][1]
1984                                  || (mf->v4 && indexMap[inMF.v4][1])) {
1985                         MFace *mf2 = CDDM_get_face(result, numFaces);
1986                         static int corner_indices[4] = {2, 1, 0, 3};
1987
1988                         DM_copy_face_data(dm, result, i, numFaces, 1);
1989                         *mf2 = *mf;
1990
1991                         mf2->v1 += indexMap[inMF.v1][1];
1992                         mf2->v2 += indexMap[inMF.v2][1];
1993                         mf2->v3 += indexMap[inMF.v3][1];
1994                         if(inMF.v4) mf2->v4 += indexMap[inMF.v4][1];
1995
1996                         /* mirror UVs if enabled */
1997                         if(mmd->flag & (MOD_MIR_MIRROR_U | MOD_MIR_MIRROR_V)) {
1998                                 MTFace *tf = result->getFaceData(result, numFaces, CD_MTFACE);
1999                                 if(tf) {
2000                                         int j;
2001                                         for(j = 0; j < 4; ++j) {
2002                                                 if(mmd->flag & MOD_MIR_MIRROR_U)
2003                                                         tf->uv[j][0] = 1.0f - tf->uv[j][0];
2004                                                 if(mmd->flag & MOD_MIR_MIRROR_V)
2005                                                         tf->uv[j][1] = 1.0f - tf->uv[j][1];
2006                                         }
2007                                 }
2008                         }
2009
2010                         /* Flip face normal */
2011                         SWAP(int, mf2->v1, mf2->v3);
2012                         DM_swap_face_data(result, numFaces, corner_indices);
2013
2014                         test_index_face(mf2, &result->faceData, numFaces, inMF.v4?4:3);
2015                         numFaces++;
2016                 }
2017         }
2018
2019         if (vector_def) MEM_freeN(vector_def);
2020
2021         MEM_freeN(indexMap);
2022
2023         CDDM_lower_num_verts(result, numVerts);
2024         CDDM_lower_num_edges(result, numEdges);
2025         CDDM_lower_num_faces(result, numFaces);
2026
2027         return result;
2028 }
2029
2030 static DerivedMesh *mirrorModifier__doMirror(MirrorModifierData *mmd,
2031                                             Object *ob, DerivedMesh *dm,
2032                                                 int initFlags)
2033 {
2034         DerivedMesh *result = dm;
2035
2036         /* check which axes have been toggled and mirror accordingly */
2037         if(mmd->flag & MOD_MIR_AXIS_X) {
2038                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 0);
2039         }
2040         if(mmd->flag & MOD_MIR_AXIS_Y) {
2041                 DerivedMesh *tmp = result;
2042                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 1);
2043                 if(tmp != dm) tmp->release(tmp); /* free intermediate results */
2044         }
2045         if(mmd->flag & MOD_MIR_AXIS_Z) {
2046                 DerivedMesh *tmp = result;
2047                 result = doMirrorOnAxis(mmd, ob, result, initFlags, 2);
2048                 if(tmp != dm) tmp->release(tmp); /* free intermediate results */
2049         }
2050
2051         return result;
2052 }
2053
2054 static DerivedMesh *mirrorModifier_applyModifier(
2055                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
2056   int useRenderParams, int isFinalCalc)
2057 {
2058         DerivedMesh *result;
2059         MirrorModifierData *mmd = (MirrorModifierData*) md;
2060
2061         result = mirrorModifier__doMirror(mmd, ob, derivedData, 0);
2062
2063         if(result != derivedData)
2064                 CDDM_calc_normals(result);
2065
2066         return result;
2067 }
2068
2069 static DerivedMesh *mirrorModifier_applyModifierEM(
2070                 ModifierData *md, Object *ob, EditMesh *editData,
2071   DerivedMesh *derivedData)
2072 {
2073         return mirrorModifier_applyModifier(md, ob, derivedData, 0, 1);
2074 }
2075
2076 /* EdgeSplit */
2077 /* EdgeSplit modifier: Splits edges in the mesh according to sharpness flag
2078  * or edge angle (can be used to achieve autosmoothing)
2079 */
2080 #if 0
2081 #define EDGESPLIT_DEBUG_3
2082 #define EDGESPLIT_DEBUG_2
2083 #define EDGESPLIT_DEBUG_1
2084 #define EDGESPLIT_DEBUG_0
2085 #endif
2086
2087 static void edgesplitModifier_initData(ModifierData *md)
2088 {
2089         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
2090
2091         /* default to 30-degree split angle, sharpness from both angle & flag
2092         */
2093         emd->split_angle = 30;
2094         emd->flags = MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG;
2095 }
2096
2097 static void edgesplitModifier_copyData(ModifierData *md, ModifierData *target)
2098 {
2099         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
2100         EdgeSplitModifierData *temd = (EdgeSplitModifierData*) target;
2101
2102         temd->split_angle = emd->split_angle;
2103         temd->flags = emd->flags;
2104 }
2105
2106 /* Mesh data for edgesplit operation */
2107 typedef struct SmoothVert {
2108         LinkNode *faces;     /* all faces which use this vert */
2109         int oldIndex; /* the index of the original DerivedMesh vert */
2110         int newIndex; /* the index of the new DerivedMesh vert */
2111 } SmoothVert;
2112
2113 #define SMOOTHEDGE_NUM_VERTS 2
2114
2115 typedef struct SmoothEdge {
2116         SmoothVert *verts[SMOOTHEDGE_NUM_VERTS]; /* the verts used by this edge */
2117         LinkNode *faces;     /* all faces which use this edge */
2118         int oldIndex; /* the index of the original DerivedMesh edge */
2119         int newIndex; /* the index of the new DerivedMesh edge */
2120         short flag; /* the flags from the original DerivedMesh edge */
2121 } SmoothEdge;
2122
2123 #define SMOOTHFACE_MAX_EDGES 4
2124
2125 typedef struct SmoothFace {
2126         SmoothEdge *edges[SMOOTHFACE_MAX_EDGES]; /* nonexistent edges == NULL */
2127         int flip[SMOOTHFACE_MAX_EDGES]; /* 1 = flip edge dir, 0 = don't flip */
2128         float normal[3]; /* the normal of this face */
2129         int oldIndex; /* the index of the original DerivedMesh face */
2130         int newIndex; /* the index of the new DerivedMesh face */
2131 } SmoothFace;
2132
2133 typedef struct SmoothMesh {
2134         SmoothVert *verts;
2135         SmoothEdge *edges;
2136         SmoothFace *faces;
2137         int num_verts, num_edges, num_faces;
2138         int max_verts, max_edges, max_faces;
2139         DerivedMesh *dm;
2140         float threshold; /* the cosine of the smoothing angle */
2141         int flags;
2142         MemArena *arena;
2143         ListBase propagatestack, reusestack;
2144 } SmoothMesh;
2145
2146 static SmoothVert *smoothvert_copy(SmoothVert *vert, SmoothMesh *mesh)
2147 {
2148         SmoothVert *copy = &mesh->verts[mesh->num_verts];
2149
2150         if(mesh->num_verts >= mesh->max_verts) {
2151                 printf("Attempted to add a SmoothMesh vert beyond end of array\n");
2152                 return NULL;
2153         }
2154
2155         *copy = *vert;
2156         copy->faces = NULL;
2157         copy->newIndex = mesh->num_verts;
2158         ++mesh->num_verts;
2159
2160 #ifdef EDGESPLIT_DEBUG_2
2161         printf("copied vert %4d to vert %4d\n", vert->newIndex, copy->newIndex);
2162 #endif
2163         return copy;
2164 }
2165
2166 static SmoothEdge *smoothedge_copy(SmoothEdge *edge, SmoothMesh *mesh)
2167 {
2168         SmoothEdge *copy = &mesh->edges[mesh->num_edges];
2169
2170         if(mesh->num_edges >= mesh->max_edges) {
2171                 printf("Attempted to add a SmoothMesh edge beyond end of array\n");
2172                 return NULL;
2173         }
2174
2175         *copy = *edge;
2176         copy->faces = NULL;
2177         copy->newIndex = mesh->num_edges;
2178         ++mesh->num_edges;
2179
2180 #ifdef EDGESPLIT_DEBUG_2
2181         printf("copied edge %4d to edge %4d\n", edge->newIndex, copy->newIndex);
2182 #endif
2183         return copy;
2184 }
2185
2186 static int smoothedge_has_vert(SmoothEdge *edge, SmoothVert *vert)
2187 {
2188         int i;
2189         for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++)
2190                 if(edge->verts[i] == vert) return 1;
2191
2192         return 0;
2193 }
2194
2195 static SmoothMesh *smoothmesh_new(int num_verts, int num_edges, int num_faces,
2196                                   int max_verts, int max_edges, int max_faces)
2197 {
2198         SmoothMesh *mesh = MEM_callocN(sizeof(*mesh), "smoothmesh");
2199         mesh->verts = MEM_callocN(sizeof(*mesh->verts) * max_verts,
2200                                   "SmoothMesh.verts");
2201         mesh->edges = MEM_callocN(sizeof(*mesh->edges) * max_edges,
2202                                   "SmoothMesh.edges");
2203         mesh->faces = MEM_callocN(sizeof(*mesh->faces) * max_faces,
2204                                   "SmoothMesh.faces");
2205
2206         mesh->num_verts = num_verts;
2207         mesh->num_edges = num_edges;
2208         mesh->num_faces = num_faces;
2209
2210         mesh->max_verts = max_verts;
2211         mesh->max_edges = max_edges;
2212         mesh->max_faces = max_faces;
2213
2214         return mesh;
2215 }
2216
2217 static void smoothmesh_free(SmoothMesh *mesh)
2218 {
2219         int i;
2220
2221         for(i = 0; i < mesh->num_verts; ++i)
2222                 BLI_linklist_free(mesh->verts[i].faces, NULL);
2223
2224         for(i = 0; i < mesh->num_edges; ++i)
2225                 BLI_linklist_free(mesh->edges[i].faces, NULL);
2226
2227         if(mesh->arena)
2228                 BLI_memarena_free(mesh->arena);
2229
2230         MEM_freeN(mesh->verts);
2231         MEM_freeN(mesh->edges);
2232         MEM_freeN(mesh->faces);
2233         MEM_freeN(mesh);
2234 }
2235
2236 static void smoothmesh_resize_verts(SmoothMesh *mesh, int max_verts)
2237 {
2238         int i;
2239         SmoothVert *tmp;
2240
2241         if(max_verts <= mesh->max_verts) return;
2242
2243         tmp = MEM_callocN(sizeof(*tmp) * max_verts, "SmoothMesh.verts");
2244
2245         memcpy(tmp, mesh->verts, sizeof(*tmp) * mesh->num_verts);
2246
2247         /* remap vert pointers in edges */
2248         for(i = 0; i < mesh->num_edges; ++i) {
2249                 int j;
2250                 SmoothEdge *edge = &mesh->edges[i];
2251
2252                 for(j = 0; j < SMOOTHEDGE_NUM_VERTS; ++j)
2253                         /* pointer arithmetic to get vert array index */
2254                         edge->verts[j] = &tmp[edge->verts[j] - mesh->verts];
2255         }
2256
2257         MEM_freeN(mesh->verts);
2258         mesh->verts = tmp;
2259         mesh->max_verts = max_verts;
2260 }
2261
2262 static void smoothmesh_resize_edges(SmoothMesh *mesh, int max_edges)
2263 {
2264         int i;
2265         SmoothEdge *tmp;
2266
2267         if(max_edges <= mesh->max_edges) return;
2268
2269         tmp = MEM_callocN(sizeof(*tmp) * max_edges, "SmoothMesh.edges");
2270
2271         memcpy(tmp, mesh->edges, sizeof(*tmp) * mesh->num_edges);
2272
2273         /* remap edge pointers in faces */
2274         for(i = 0; i < mesh->num_faces; ++i) {
2275                 int j;
2276                 SmoothFace *face = &mesh->faces[i];
2277
2278                 for(j = 0; j < SMOOTHFACE_MAX_EDGES; ++j)
2279                         if(face->edges[j])
2280                                 /* pointer arithmetic to get edge array index */
2281                                 face->edges[j] = &tmp[face->edges[j] - mesh->edges];
2282         }
2283
2284         MEM_freeN(mesh->edges);
2285         mesh->edges = tmp;
2286         mesh->max_edges = max_edges;
2287 }
2288
2289 #ifdef EDGESPLIT_DEBUG_0
2290 static void smoothmesh_print(SmoothMesh *mesh)
2291 {
2292         int i, j;
2293         DerivedMesh *dm = mesh->dm;
2294
2295         printf("--- SmoothMesh ---\n");
2296         printf("--- Vertices ---\n");
2297         for(i = 0; i < mesh->num_verts; i++) {
2298                 SmoothVert *vert = &mesh->verts[i];
2299                 LinkNode *node;
2300                 MVert mv;
2301
2302                 dm->getVert(dm, vert->oldIndex, &mv);
2303
2304                 printf("%3d: ind={%3d, %3d}, pos={% 5.1f, % 5.1f, % 5.1f}",
2305                        i, vert->oldIndex, vert->newIndex,
2306          mv.co[0], mv.co[1], mv.co[2]);
2307                 printf(", faces={");
2308                 for(node = vert->faces; node != NULL; node = node->next) {
2309                         printf(" %d", ((SmoothFace *)node->link)->newIndex);
2310                 }
2311                 printf("}\n");
2312         }
2313
2314         printf("\n--- Edges ---\n");
2315         for(i = 0; i < mesh->num_edges; i++) {
2316                 SmoothEdge *edge = &mesh->edges[i];
2317                 LinkNode *node;
2318
2319                 printf("%4d: indices={%4d, %4d}, verts={%4d, %4d}",
2320                        i,
2321          edge->oldIndex, edge->newIndex,
2322   edge->verts[0]->newIndex, edge->verts[1]->newIndex);
2323                 if(edge->verts[0] == edge->verts[1]) printf(" <- DUPLICATE VERTEX");
2324                 printf(", faces={");
2325                 for(node = edge->faces; node != NULL; node = node->next) {
2326                         printf(" %d", ((SmoothFace *)node->link)->newIndex);
2327                 }
2328                 printf("}\n");
2329         }
2330
2331         printf("\n--- Faces ---\n");
2332         for(i = 0; i < mesh->num_faces; i++) {
2333                 SmoothFace *face = &mesh->faces[i];
2334
2335                 printf("%4d: indices={%4d, %4d}, edges={", i,
2336                        face->oldIndex, face->newIndex);
2337                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
2338                         if(face->flip[j])
2339                                 printf(" -%-2d", face->edges[j]->newIndex);
2340                         else
2341                                 printf("  %-2d", face->edges[j]->newIndex);
2342                 }
2343                 printf("}, verts={");
2344                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
2345                         printf(" %d", face->edges[j]->verts[face->flip[j]]->newIndex);
2346                 }
2347                 printf("}\n");
2348         }
2349 }
2350 #endif
2351
2352 static SmoothMesh *smoothmesh_from_derivedmesh(DerivedMesh *dm)
2353 {
2354         SmoothMesh *mesh;
2355         EdgeHash *edges = BLI_edgehash_new();
2356         int i;
2357         int totvert, totedge, totface;
2358
2359         totvert = dm->getNumVerts(dm);
2360         totedge = dm->getNumEdges(dm);
2361         totface = dm->getNumFaces(dm);
2362
2363         mesh = smoothmesh_new(totvert, totedge, totface,
2364                               totvert, totedge, totface);
2365
2366         mesh->dm = dm;
2367
2368         for(i = 0; i < totvert; i++) {
2369                 SmoothVert *vert = &mesh->verts[i];
2370
2371                 vert->oldIndex = vert->newIndex = i;
2372         }
2373
2374         for(i = 0; i < totedge; i++) {
2375                 SmoothEdge *edge = &mesh->edges[i];
2376                 MEdge med;
2377
2378                 dm->getEdge(dm, i, &med);
2379                 edge->verts[0] = &mesh->verts[med.v1];
2380                 edge->verts[1] = &mesh->verts[med.v2];
2381                 edge->oldIndex = edge->newIndex = i;
2382                 edge->flag = med.flag;
2383
2384                 BLI_edgehash_insert(edges, med.v1, med.v2, edge);
2385         }
2386
2387         for(i = 0; i < totface; i++) {
2388                 SmoothFace *face = &mesh->faces[i];
2389                 MFace mf;
2390                 MVert v1, v2, v3;
2391                 int j;
2392
2393                 dm->getFace(dm, i, &mf);
2394
2395                 dm->getVert(dm, mf.v1, &v1);
2396                 dm->getVert(dm, mf.v2, &v2);
2397                 dm->getVert(dm, mf.v3, &v3);
2398                 face->edges[0] = BLI_edgehash_lookup(edges, mf.v1, mf.v2);
2399                 if(face->edges[0]->verts[1]->oldIndex == mf.v1) face->flip[0] = 1;
2400                 face->edges[1] = BLI_edgehash_lookup(edges, mf.v2, mf.v3);
2401                 if(face->edges[1]->verts[1]->oldIndex == mf.v2) face->flip[1] = 1;
2402                 if(mf.v4) {
2403                         MVert v4;
2404                         dm->getVert(dm, mf.v4, &v4);
2405                         face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v4);
2406                         if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
2407                         face->edges[3] = BLI_edgehash_lookup(edges, mf.v4, mf.v1);
2408                         if(face->edges[3]->verts[1]->oldIndex == mf.v4) face->flip[3] = 1;
2409                         CalcNormFloat4(v1.co, v2.co, v3.co, v4.co, face->normal);
2410                 } else {
2411                         face->edges[2] = BLI_edgehash_lookup(edges, mf.v3, mf.v1);
2412                         if(face->edges[2]->verts[1]->oldIndex == mf.v3) face->flip[2] = 1;
2413                         face->edges[3] = NULL;
2414                         CalcNormFloat(v1.co, v2.co, v3.co, face->normal);
2415                 }
2416
2417                 for(j = 0; j < SMOOTHFACE_MAX_EDGES && face->edges[j]; j++) {
2418                         SmoothEdge *edge = face->edges[j];
2419                         BLI_linklist_prepend(&edge->faces, face);
2420                         BLI_linklist_prepend(&edge->verts[face->flip[j]]->faces, face);
2421                 }
2422
2423                 face->oldIndex = face->newIndex = i;
2424         }
2425
2426         BLI_edgehash_free(edges, NULL);
2427
2428         return mesh;
2429 }
2430
2431 static DerivedMesh *CDDM_from_smoothmesh(SmoothMesh *mesh)
2432 {
2433         DerivedMesh *result = CDDM_from_template(mesh->dm,
2434                         mesh->num_verts,
2435    mesh->num_edges,
2436    mesh->num_faces);
2437         MVert *new_verts = CDDM_get_verts(result);
2438         MEdge *new_edges = CDDM_get_edges(result);
2439         MFace *new_faces = CDDM_get_faces(result);
2440         int i;
2441
2442         for(i = 0; i < mesh->num_verts; ++i) {
2443                 SmoothVert *vert = &mesh->verts[i];
2444                 MVert *newMV = &new_verts[vert->newIndex];
2445
2446                 DM_copy_vert_data(mesh->dm, result,
2447                                   vert->oldIndex, vert->newIndex, 1);
2448                 mesh->dm->getVert(mesh->dm, vert->oldIndex, newMV);
2449         }
2450
2451         for(i = 0; i < mesh->num_edges; ++i) {
2452                 SmoothEdge *edge = &mesh->edges[i];
2453                 MEdge *newME = &new_edges[edge->newIndex];
2454
2455                 DM_copy_edge_data(mesh->dm, result,
2456                                   edge->oldIndex, edge->newIndex, 1);
2457                 mesh->dm->getEdge(mesh->dm, edge->oldIndex, newME);
2458                 newME->v1 = edge->verts[0]->newIndex;
2459                 newME->v2 = edge->verts[1]->newIndex;
2460         }
2461
2462         for(i = 0; i < mesh->num_faces; ++i) {
2463                 SmoothFace *face = &mesh->faces[i];
2464                 MFace *newMF = &new_faces[face->newIndex];
2465
2466                 DM_copy_face_data(mesh->dm, result,
2467                                   face->oldIndex, face->newIndex, 1);
2468                 mesh->dm->getFace(mesh->dm, face->oldIndex, newMF);
2469
2470                 newMF->v1 = face->edges[0]->verts[face->flip[0]]->newIndex;
2471                 newMF->v2 = face->edges[1]->verts[face->flip[1]]->newIndex;
2472                 newMF->v3 = face->edges[2]->verts[face->flip[2]]->newIndex;
2473
2474                 if(face->edges[3]) {
2475                         newMF->v4 = face->edges[3]->verts[face->flip[3]]->newIndex;
2476                 } else {
2477                         newMF->v4 = 0;
2478                 }
2479         }
2480
2481         return result;
2482 }
2483
2484 /* returns the other vert in the given edge
2485  */
2486 static SmoothVert *other_vert(SmoothEdge *edge, SmoothVert *vert)
2487 {
2488         if(edge->verts[0] == vert) return edge->verts[1];
2489         else return edge->verts[0];
2490 }
2491
2492 /* returns the other edge in the given face that uses the given vert
2493  * returns NULL if no other edge in the given face uses the given vert
2494  * (this should never happen)
2495  */
2496 static SmoothEdge *other_edge(SmoothFace *face, SmoothVert *vert,
2497                               SmoothEdge *edge)
2498 {
2499         int i,j;
2500         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
2501                 SmoothEdge *tmp_edge = face->edges[i];
2502                 if(tmp_edge == edge) continue;
2503
2504                 for(j = 0; j < SMOOTHEDGE_NUM_VERTS; j++)
2505                         if(tmp_edge->verts[j] == vert) return tmp_edge;
2506         }
2507
2508         /* if we get to here, something's wrong (there should always be 2 edges
2509         * which use the same vert in a face)
2510         */
2511         return NULL;
2512 }
2513
2514 /* returns a face attached to the given edge which is not the given face.
2515  * returns NULL if no other faces use this edge.
2516  */
2517 static SmoothFace *other_face(SmoothEdge *edge, SmoothFace *face)
2518 {
2519         LinkNode *node;
2520
2521         for(node = edge->faces; node != NULL; node = node->next)
2522                 if(node->link != face) return node->link;
2523
2524         return NULL;
2525 }
2526
2527 #if 0
2528 /* copies source list to target, overwriting target (target is not freed)
2529  * nodes in the copy will be in the same order as in source
2530  */
2531 static void linklist_copy(LinkNode **target, LinkNode *source)
2532 {
2533         LinkNode *node = NULL;
2534         *target = NULL;
2535
2536         for(; source; source = source->next) {
2537                 if(node) {
2538                         node->next = MEM_mallocN(sizeof(*node->next), "nlink_copy");
2539                                                                                 node = node->next;
2540 } else {
2541                                                                                 node = *target = MEM_mallocN(sizeof(**target), "nlink_copy");
2542 }
2543                                                                                 node->link = source->link;
2544                                                                                 node->next = NULL;
2545 }
2546 }
2547 #endif
2548
2549                                                                                 /* appends source to target if it's not already in target */
2550                                                                                 static void linklist_append_unique(LinkNode **target, void *source)
2551 {
2552         LinkNode *node;
2553         LinkNode *prev = NULL;
2554
2555         /* check if source value is already in the list */
2556         for(node = *target; node; prev = node, node = node->next)
2557                 if(node->link == source) return;
2558
2559         node = MEM_mallocN(sizeof(*node), "nlink");
2560         node->next = NULL;
2561         node->link = source;
2562
2563         if(prev) prev->next = node;
2564         else *target = node;
2565 }
2566
2567 /* appends elements of source which aren't already in target to target */
2568 static void linklist_append_list_unique(LinkNode **target, LinkNode *source)
2569 {
2570         for(; source; source = source->next)
2571                 linklist_append_unique(target, source->link);
2572 }
2573
2574 #if 0 /* this is no longer used, it should possibly be removed */
2575 /* prepends prepend to list - doesn't copy nodes, just joins the lists */
2576 static void linklist_prepend_linklist(LinkNode **list, LinkNode *prepend)
2577 {
2578         if(prepend) {
2579                 LinkNode *node = prepend;
2580                 while(node->next) node = node->next;
2581
2582                 node->next = *list;
2583                 *list = prepend;
2584 }
2585 }
2586 #endif
2587
2588 /* returns 1 if the linked list contains the given pointer, 0 otherwise
2589  */
2590 static int linklist_contains(LinkNode *list, void *ptr)
2591 {
2592         LinkNode *node;
2593
2594         for(node = list; node; node = node->next)
2595                 if(node->link == ptr) return 1;
2596
2597         return 0;
2598 }
2599
2600 /* returns 1 if the first linked list is a subset of the second (comparing
2601  * pointer values), 0 if not
2602  */
2603 static int linklist_subset(LinkNode *list1, LinkNode *list2)
2604 {
2605         for(; list1; list1 = list1->next)
2606                 if(!linklist_contains(list2, list1->link))
2607                         return 0;
2608
2609         return 1;
2610 }
2611
2612 #if 0
2613 /* empties the linked list
2614  * frees pointers with freefunc if freefunc is not NULL
2615  */
2616 static void linklist_empty(LinkNode **list, LinkNodeFreeFP freefunc)
2617 {
2618         BLI_linklist_free(*list, freefunc);
2619         *list = NULL;
2620 }
2621 #endif
2622
2623 /* removes the first instance of value from the linked list
2624  * frees the pointer with freefunc if freefunc is not NULL
2625  */
2626 static void linklist_remove_first(LinkNode **list, void *value,
2627                                   LinkNodeFreeFP freefunc)
2628 {
2629         LinkNode *node = *list;
2630         LinkNode *prev = NULL;
2631
2632         while(node && node->link != value) {
2633                 prev = node;
2634                 node = node->next;
2635         }
2636
2637         if(node) {
2638                 if(prev)
2639                         prev->next = node->next;
2640                 else
2641                         *list = node->next;
2642
2643                 if(freefunc)
2644                         freefunc(node->link);
2645
2646                 MEM_freeN(node);
2647         }
2648 }
2649
2650 /* removes all elements in source from target */
2651 static void linklist_remove_list(LinkNode **target, LinkNode *source,
2652                                  LinkNodeFreeFP freefunc)
2653 {
2654         for(; source; source = source->next)
2655                 linklist_remove_first(target, source->link, freefunc);
2656 }
2657
2658 #ifdef EDGESPLIT_DEBUG_0
2659 static void print_ptr(void *ptr)
2660 {
2661         printf("%p\n", ptr);
2662 }
2663
2664 static void print_edge(void *ptr)
2665 {
2666         SmoothEdge *edge = ptr;
2667         printf(" %4d", edge->newIndex);
2668 }
2669
2670 static void print_face(void *ptr)
2671 {
2672         SmoothFace *face = ptr;
2673         printf(" %4d", face->newIndex);
2674 }
2675 #endif
2676
2677 typedef struct ReplaceData {
2678         void *find;
2679         void *replace;
2680 } ReplaceData;
2681
2682 static void edge_replace_vert(void *ptr, void *userdata)
2683 {
2684         SmoothEdge *edge = ptr;
2685         SmoothVert *find = ((ReplaceData *)userdata)->find;
2686         SmoothVert *replace = ((ReplaceData *)userdata)->replace;
2687         int i;
2688
2689 #ifdef EDGESPLIT_DEBUG_3
2690         printf("replacing vert %4d with %4d in edge %4d",
2691                find->newIndex, replace->newIndex, edge->newIndex);
2692         printf(": {%4d, %4d}", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
2693 #endif
2694
2695         for(i = 0; i < SMOOTHEDGE_NUM_VERTS; i++) {
2696                 if(edge->verts[i] == find) {
2697                         linklist_append_list_unique(&replace->faces, edge->faces);
2698                         linklist_remove_list(&find->faces, edge->faces, NULL);
2699
2700                         edge->verts[i] = replace;
2701                 }
2702         }
2703
2704 #ifdef EDGESPLIT_DEBUG_3
2705         printf(" -> {%4d, %4d}\n", edge->verts[0]->newIndex, edge->verts[1]->newIndex);
2706 #endif
2707 }
2708
2709 static void face_replace_vert(void *ptr, void *userdata)
2710 {
2711         SmoothFace *face = ptr;
2712         int i;
2713
2714         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++)
2715                 edge_replace_vert(face->edges[i], userdata);
2716 }
2717
2718 static void face_replace_edge(void *ptr, void *userdata)
2719 {
2720         SmoothFace *face = ptr;
2721         SmoothEdge *find = ((ReplaceData *)userdata)->find;
2722         SmoothEdge *replace = ((ReplaceData *)userdata)->replace;
2723         int i;
2724
2725 #ifdef EDGESPLIT_DEBUG_3
2726         printf("replacing edge %4d with %4d in face %4d",
2727                find->newIndex, replace->newIndex, face->newIndex);
2728         if(face->edges[3])
2729                 printf(": {%2d %2d %2d %2d}",
2730                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2731          face->edges[2]->newIndex, face->edges[3]->newIndex);
2732         else
2733                 printf(": {%2d %2d %2d}",
2734                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2735          face->edges[2]->newIndex);
2736 #endif
2737
2738         for(i = 0; i < SMOOTHFACE_MAX_EDGES && face->edges[i]; i++) {
2739                 if(face->edges[i] == find) {
2740                         linklist_remove_first(&face->edges[i]->faces, face, NULL);
2741                         BLI_linklist_prepend(&replace->faces, face);
2742                         face->edges[i] = replace;
2743                 }
2744         }
2745
2746 #ifdef EDGESPLIT_DEBUG_3
2747         if(face->edges[3])
2748                 printf(" -> {%2d %2d %2d %2d}\n",
2749                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2750          face->edges[2]->newIndex, face->edges[3]->newIndex);
2751         else
2752                 printf(" -> {%2d %2d %2d}\n",
2753                        face->edges[0]->newIndex, face->edges[1]->newIndex,
2754          face->edges[2]->newIndex);
2755 #endif
2756 }
2757
2758 static int edge_is_loose(SmoothEdge *edge)
2759 {
2760         return !(edge->faces && edge->faces->next);
2761 }
2762
2763 static int edge_is_sharp(SmoothEdge *edge, int flags,
2764                          float threshold)
2765 {
2766 #ifdef EDGESPLIT_DEBUG_1
2767         printf("edge %d: ", edge->newIndex);
2768 #endif
2769         if(edge->flag & ME_SHARP) {
2770                 /* edge can only be sharp if it has at least 2 faces */
2771                 if(!edge_is_loose(edge)) {
2772 #ifdef EDGESPLIT_DEBUG_1
2773                         printf("sharp\n");
2774 #endif
2775                         return 1;
2776                 } else {
2777                         /* edge is loose, so it can't be sharp */
2778                         edge->flag &= ~ME_SHARP;
2779                 }
2780         }
2781
2782 #ifdef EDGESPLIT_DEBUG_1
2783         printf("not sharp\n");
2784 #endif
2785         return 0;
2786 }
2787
2788 /* finds another sharp edge which uses vert, by traversing faces around the
2789  * vert until it does one of the following:
2790  * - hits a loose edge (the edge is returned)
2791  * - hits a sharp edge (the edge is returned)
2792  * - returns to the start edge (NULL is returned)
2793  */
2794 static SmoothEdge *find_other_sharp_edge(SmoothVert *vert, SmoothEdge *edge,
2795                                          LinkNode **visited_faces, float threshold, int flags)
2796 {
2797         SmoothFace *face = NULL;
2798         SmoothEdge *edge2 = NULL;
2799         /* holds the edges we've seen so we can avoid looping indefinitely */
2800         LinkNode *visited_edges = NULL;
2801 #ifdef EDGESPLIT_DEBUG_1
2802         printf("=== START === find_other_sharp_edge(edge = %4d, vert = %4d)\n",
2803                edge->newIndex, vert->newIndex);
2804 #endif
2805
2806         /* get a face on which to start */
2807         if(edge->faces) face = edge->faces->link;
2808         else return NULL;
2809
2810         /* record this edge as visited */
2811         BLI_linklist_prepend(&visited_edges, edge);
2812
2813         /* get the next edge */
2814         edge2 = other_edge(face, vert, edge);
2815
2816         /* record this face as visited */
2817         if(visited_faces)
2818                 BLI_linklist_prepend(visited_faces, face);
2819
2820         /* search until we hit a loose edge or a sharp edge or an edge we've
2821         * seen before
2822         */
2823         while(face && !edge_is_sharp(edge2, flags, threshold)
2824                      && !linklist_contains(visited_edges, edge2)) {
2825 #ifdef EDGESPLIT_DEBUG_3
2826                 printf("current face %4d; current edge %4d\n", face->newIndex,
2827                        edge2->newIndex);
2828 #endif
2829                 /* get the next face */
2830                 face = other_face(edge2, face);
2831
2832                 /* if face == NULL, edge2 is a loose edge */
2833                 if(face) {
2834                         /* record this face as visited */
2835                         if(visited_faces)
2836                                 BLI_linklist_prepend(visited_faces, face);
2837
2838                         /* record this edge as visited */
2839                         BLI_linklist_prepend(&visited_edges, edge2);
2840
2841                         /* get the next edge */
2842                         edge2 = other_edge(face, vert, edge2);
2843 #ifdef EDGESPLIT_DEBUG_3
2844                         printf("next face %4d; next edge %4d\n",
2845                                face->newIndex, edge2->newIndex);
2846                 } else {
2847                         printf("loose edge: %4d\n", edge2->newIndex);
2848 #endif
2849                 }
2850                      }
2851
2852                      /* either we came back to the start edge or we found a sharp/loose edge */
2853                      if(linklist_contains(visited_edges, edge2))
2854                              /* we came back to the start edge */
2855                              edge2 = NULL;
2856
2857                      BLI_linklist_free(visited_edges, NULL);
2858
2859 #ifdef EDGESPLIT_DEBUG_1
2860                      printf("=== END === find_other_sharp_edge(edge = %4d, vert = %4d), "
2861                                      "returning edge %d\n",
2862          edge->newIndex, vert->newIndex, edge2 ? edge2->newIndex : -1);
2863 #endif
2864                      return edge2;
2865 }
2866
2867 static void split_single_vert(SmoothVert *vert, SmoothFace *face,
2868                               SmoothMesh *mesh)
2869 {
2870         SmoothVert *copy_vert;
2871         ReplaceData repdata;
2872
2873         copy_vert = smoothvert_copy(vert, mesh);
2874
2875         repdata.find = vert;
2876         repdata.replace = copy_vert;
2877         face_replace_vert(face, &repdata);
2878 }
2879
2880 typedef struct PropagateEdge {
2881         struct PropagateEdge *next, *prev;
2882         SmoothEdge *edge;
2883         SmoothVert *vert;
2884 } PropagateEdge;
2885
2886 static void push_propagate_stack(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
2887 {
2888         PropagateEdge *pedge = mesh->reusestack.first;
2889
2890         if(pedge) {
2891                 BLI_remlink(&mesh->reusestack, pedge);
2892         }
2893         else {
2894                 if(!mesh->arena) {
2895                         mesh->arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE);
2896                         BLI_memarena_use_calloc(mesh->arena);
2897                 }
2898
2899                 pedge = BLI_memarena_alloc(mesh->arena, sizeof(PropagateEdge));
2900         }
2901
2902         pedge->edge = edge;
2903         pedge->vert = vert;
2904         BLI_addhead(&mesh->propagatestack, pedge);
2905 }
2906
2907 static void pop_propagate_stack(SmoothEdge **edge, SmoothVert **vert, SmoothMesh *mesh)
2908 {
2909         PropagateEdge *pedge = mesh->propagatestack.first;
2910
2911         if(pedge) {
2912                 *edge = pedge->edge;
2913                 *vert = pedge->vert;
2914                 BLI_remlink(&mesh->propagatestack, pedge);
2915                 BLI_addhead(&mesh->reusestack, pedge);
2916         }
2917         else {
2918                 *edge = NULL;
2919                 *vert = NULL;
2920         }
2921 }
2922
2923 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh);
2924
2925 static void propagate_split(SmoothEdge *edge, SmoothVert *vert,
2926                             SmoothMesh *mesh)
2927 {
2928         SmoothEdge *edge2;
2929         LinkNode *visited_faces = NULL;
2930 #ifdef EDGESPLIT_DEBUG_1
2931         printf("=== START === propagate_split(edge = %4d, vert = %4d)\n",
2932                edge->newIndex, vert->newIndex);
2933 #endif
2934
2935         edge2 = find_other_sharp_edge(vert, edge, &visited_faces,
2936                                       mesh->threshold, mesh->flags);
2937
2938         if(!edge2) {
2939                 /* didn't find a sharp or loose edge, so we've hit a dead end */
2940         } else if(!edge_is_loose(edge2)) {
2941                 /* edge2 is not loose, so it must be sharp */
2942                 if(edge_is_loose(edge)) {
2943                         /* edge is loose, so we can split edge2 at this vert */
2944                         split_edge(edge2, vert, mesh);
2945                 } else if(edge_is_sharp(edge, mesh->flags, mesh->threshold)) {
2946                         /* both edges are sharp, so we can split the pair at vert */
2947                         split_edge(edge, vert, mesh);
2948                 } else {
2949                         /* edge is not sharp, so try to split edge2 at its other vert */
2950                         split_edge(edge2, other_vert(edge2, vert), mesh);
2951                 }
2952         } else { /* edge2 is loose */
2953                 if(edge_is_loose(edge)) {
2954                         SmoothVert *vert2;
2955                         ReplaceData repdata;
2956
2957                         /* can't split edge, what should we do with vert? */
2958                         if(linklist_subset(vert->faces, visited_faces)) {
2959                                 /* vert has only one fan of faces attached; don't split it */
2960                         } else {
2961                                 /* vert has more than one fan of faces attached; split it */
2962                                 vert2 = smoothvert_copy(vert, mesh);
2963
2964                                 /* replace vert with its copy in visited_faces */
2965                                 repdata.find = vert;
2966                                 repdata.replace = vert2;
2967                                 BLI_linklist_apply(visited_faces, face_replace_vert, &repdata);
2968                         }
2969                 } else {
2970                         /* edge is not loose, so it must be sharp; split it */
2971                         split_edge(edge, vert, mesh);
2972                 }
2973         }
2974
2975         BLI_linklist_free(visited_faces, NULL);
2976 #ifdef EDGESPLIT_DEBUG_1
2977         printf("=== END === propagate_split(edge = %4d, vert = %4d)\n",
2978                edge->newIndex, vert->newIndex);
2979 #endif
2980 }
2981
2982 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
2983 {
2984         SmoothEdge *edge2;
2985         SmoothVert *vert2;
2986         ReplaceData repdata;
2987         /* the list of faces traversed while looking for a sharp edge */
2988         LinkNode *visited_faces = NULL;
2989 #ifdef EDGESPLIT_DEBUG_1
2990         printf("=== START === split_edge(edge = %4d, vert = %4d)\n",
2991                edge->newIndex, vert->newIndex);
2992 #endif
2993
2994         edge2 = find_other_sharp_edge(vert, edge, &visited_faces,
2995                                       mesh->threshold, mesh->flags);
2996
2997         if(!edge2) {
2998                 /* didn't find a sharp or loose edge, so try the other vert */
2999                 vert2 = other_vert(edge, vert);
3000                 push_propagate_stack(edge, vert2, mesh);
3001         } else if(!edge_is_loose(edge2)) {
3002                 /* edge2 is not loose, so it must be sharp */
3003                 SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
3004                 SmoothEdge *copy_edge2 = smoothedge_copy(edge2, mesh);
3005                 SmoothVert *vert2;
3006
3007                 /* replace edge with its copy in visited_faces */
3008                 repdata.find = edge;
3009                 repdata.replace = copy_edge;
3010                 BLI_linklist_apply(visited_faces, face_replace_edge, &repdata);
3011
3012                 /* replace edge2 with its copy in visited_faces */
3013                &