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