svn merge ^/trunk/blender -r41226:41227 .
[blender.git] / source / blender / modifiers / intern / MOD_array.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software  Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2005 by the Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Daniel Dunbar
22  *                 Ton Roosendaal,
23  *                 Ben Batt,
24  *                 Brecht Van Lommel,
25  *                 Campbell Barton
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  *
29  */
30
31 /* Array modifier: duplicates the object multiple times along an axis */
32
33 #include "MEM_guardedalloc.h"
34
35 #include "BLI_utildefines.h"
36 #include "BLI_math.h"
37 #include "BLI_ghash.h"
38 #include "BLI_edgehash.h"
39
40 #include "DNA_curve_types.h"
41 #include "DNA_meshdata_types.h"
42 #include "DNA_object_types.h"
43
44 #include "BKE_cdderivedmesh.h"
45 #include "BKE_displist.h"
46 #include "BKE_mesh.h"
47 #include "BKE_modifier.h"
48 #include "BKE_object.h"
49 #include "BKE_tessmesh.h"
50
51 #include "depsgraph_private.h"
52
53 #include <ctype.h>
54 #include <stdlib.h>
55 #include <string.h>
56
57 static void initData(ModifierData *md)
58 {
59         ArrayModifierData *amd = (ArrayModifierData*) md;
60
61         /* default to 2 duplicates distributed along the x-axis by an
62         offset of 1 object-width
63         */
64         amd->start_cap = amd->end_cap = amd->curve_ob = amd->offset_ob = NULL;
65         amd->count = 2;
66         amd->offset[0] = amd->offset[1] = amd->offset[2] = 0;
67         amd->scale[0] = 1;
68         amd->scale[1] = amd->scale[2] = 0;
69         amd->length = 0;
70         amd->merge_dist = 0.01;
71         amd->fit_type = MOD_ARR_FIXEDCOUNT;
72         amd->offset_type = MOD_ARR_OFF_RELATIVE;
73         amd->flags = 0;
74 }
75
76 static void copyData(ModifierData *md, ModifierData *target)
77 {
78         ArrayModifierData *amd = (ArrayModifierData*) md;
79         ArrayModifierData *tamd = (ArrayModifierData*) target;
80
81         tamd->start_cap = amd->start_cap;
82         tamd->end_cap = amd->end_cap;
83         tamd->curve_ob = amd->curve_ob;
84         tamd->offset_ob = amd->offset_ob;
85         tamd->count = amd->count;
86         copy_v3_v3(tamd->offset, amd->offset);
87         copy_v3_v3(tamd->scale, amd->scale);
88         tamd->length = amd->length;
89         tamd->merge_dist = amd->merge_dist;
90         tamd->fit_type = amd->fit_type;
91         tamd->offset_type = amd->offset_type;
92         tamd->flags = amd->flags;
93 }
94
95 static void foreachObjectLink(
96                                                 ModifierData *md, Object *ob,
97          void (*walk)(void *userData, Object *ob, Object **obpoin),
98                 void *userData)
99 {
100         ArrayModifierData *amd = (ArrayModifierData*) md;
101
102         walk(userData, ob, &amd->start_cap);
103         walk(userData, ob, &amd->end_cap);
104         walk(userData, ob, &amd->curve_ob);
105         walk(userData, ob, &amd->offset_ob);
106 }
107
108 static void updateDepgraph(ModifierData *md, DagForest *forest, struct Scene *UNUSED(scene),
109                                          Object *UNUSED(ob), DagNode *obNode)
110 {
111         ArrayModifierData *amd = (ArrayModifierData*) md;
112
113         if (amd->start_cap) {
114                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
115
116                 dag_add_relation(forest, curNode, obNode,
117                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
118         }
119         if (amd->end_cap) {
120                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
121
122                 dag_add_relation(forest, curNode, obNode,
123                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
124         }
125         if (amd->curve_ob) {
126                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
127
128                 dag_add_relation(forest, curNode, obNode,
129                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
130         }
131         if (amd->offset_ob) {
132                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
133
134                 dag_add_relation(forest, curNode, obNode,
135                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
136         }
137 }
138
139 static float vertarray_size(MVert *mvert, int numVerts, int axis)
140 {
141         int i;
142         float min_co, max_co;
143
144         /* if there are no vertices, width is 0 */
145         if(numVerts == 0) return 0;
146
147         /* find the minimum and maximum coordinates on the desired axis */
148         min_co = max_co = mvert->co[axis];
149         ++mvert;
150         for(i = 1; i < numVerts; ++i, ++mvert) {
151                 if(mvert->co[axis] < min_co) min_co = mvert->co[axis];
152                 if(mvert->co[axis] > max_co) max_co = mvert->co[axis];
153         }
154
155         return max_co - min_co;
156 }
157
158 /* finds the best possible flipped name. For renaming; check for unique names afterwards */
159 /* if strip_number: removes number extensions */
160 void vertgroup_flip_name (char *name, int strip_number)
161 {
162         int     len;
163         char    prefix[128]={""};   /* The part before the facing */
164         char    suffix[128]={""};   /* The part after the facing */
165         char    replace[128]={""};  /* The replacement string */
166         char    number[128]={""};   /* The number extension string */
167         char    *index=NULL;
168
169         len= strlen(name);
170         if(len<3) return; // we don't do names like .R or .L
171
172         /* We first check the case with a .### extension, let's find the last period */
173         if(isdigit(name[len-1])) {
174                 index= strrchr(name, '.'); // last occurrance
175                 if (index && isdigit(index[1]) ) { // doesnt handle case bone.1abc2 correct..., whatever!
176                         if(strip_number==0)
177                                 strcpy(number, index);
178                         *index= 0;
179                         len= strlen(name);
180                 }
181         }
182
183         strcpy (prefix, name);
184
185 #define IS_SEPARATOR(a) ((a)=='.' || (a)==' ' || (a)=='-' || (a)=='_')
186
187         /* first case; separator . - _ with extensions r R l L  */
188         if( IS_SEPARATOR(name[len-2]) ) {
189                 switch(name[len-1]) {
190                         case 'l':
191                                 prefix[len-1]= 0;
192                                 strcpy(replace, "r");
193                                 break;
194                         case 'r':
195                                 prefix[len-1]= 0;
196                                 strcpy(replace, "l");
197                                 break;
198                         case 'L':
199                                 prefix[len-1]= 0;
200                                 strcpy(replace, "R");
201                                 break;
202                         case 'R':
203                                 prefix[len-1]= 0;
204                                 strcpy(replace, "L");
205                                 break;
206                 }
207         }
208         /* case; beginning with r R l L , with separator after it */
209         else if( IS_SEPARATOR(name[1]) ) {
210                 switch(name[0]) {
211                         case 'l':
212                                 strcpy(replace, "r");
213                                 strcpy(suffix, name+1);
214                                 prefix[0]= 0;
215                                 break;
216                         case 'r':
217                                 strcpy(replace, "l");
218                                 strcpy(suffix, name+1);
219                                 prefix[0]= 0;
220                                 break;
221                         case 'L':
222                                 strcpy(replace, "R");
223                                 strcpy(suffix, name+1);
224                                 prefix[0]= 0;
225                                 break;
226                         case 'R':
227                                 strcpy(replace, "L");
228                                 strcpy(suffix, name+1);
229                                 prefix[0]= 0;
230                                 break;
231                 }
232         }
233         else if(len > 5) {
234                 /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */
235                 index = BLI_strcasestr(prefix, "right");
236                 if (index==prefix || index==prefix+len-5) {
237                         if(index[0]=='r')
238                                 strcpy (replace, "left");
239                         else {
240                                 if(index[1]=='I')
241                                         strcpy (replace, "LEFT");
242                                 else
243                                         strcpy (replace, "Left");
244                         }
245                         *index= 0;
246                         strcpy (suffix, index+5);
247                 }
248                 else {
249                         index = BLI_strcasestr(prefix, "left");
250                         if (index==prefix || index==prefix+len-4) {
251                                 if(index[0]=='l')
252                                         strcpy (replace, "right");
253                                 else {
254                                         if(index[1]=='E')
255                                                 strcpy (replace, "RIGHT");
256                                         else
257                                                 strcpy (replace, "Right");
258                                 }
259                                 *index= 0;
260                                 strcpy (suffix, index+4);
261                         }
262                 }
263         }
264
265 #undef IS_SEPARATOR
266
267         sprintf (name, "%s%s%s%s", prefix, replace, suffix, number);
268 }
269
270 typedef struct IndexMapEntry {
271         /* the new vert index that this old vert index maps to */
272         int new;
273         /* -1 if this vert isn't merged, otherwise the old vert index it
274         * should be replaced with
275         */
276         int merge;
277         /* 1 if this vert's first copy is merged with the last copy of its
278         * merge target, otherwise 0
279         */
280         short merge_final;
281 } IndexMapEntry;
282
283 /* indexMap - an array of IndexMap entries
284  * oldIndex - the old index to map
285  * copyNum - the copy number to map to (original = 0, first copy = 1, etc.)
286  */
287 static int calc_mapping(IndexMapEntry *indexMap, int oldIndex, int copyNum)
288 {
289         if(indexMap[oldIndex].merge < 0) {
290                 /* vert wasn't merged, so use copy of this vert */
291                 return indexMap[oldIndex].new + copyNum;
292         } else if(indexMap[oldIndex].merge == oldIndex) {
293                 /* vert was merged with itself */
294                 return indexMap[oldIndex].new;
295         } else {
296                 /* vert was merged with another vert */
297                 /* follow the chain of merges to the end, or until we've passed
298                 * a number of vertices equal to the copy number
299                 */
300                 if(copyNum <= 0)
301                         return indexMap[oldIndex].new;
302                 else
303                         return calc_mapping(indexMap, indexMap[oldIndex].merge,
304                                                 copyNum - 1);
305         }
306 }
307
308 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
309                                           Scene *scene, Object *ob, DerivedMesh *dm,
310                                                                                   int UNUSED(initFlags))
311 {
312         DerivedMesh *cddm = dm; //copying shouldn't be necassary here, as all modifiers return CDDM's
313         BMEditMesh *em = CDDM_To_BMesh(ob, cddm, NULL);
314         BMOperator op, oldop, weldop;
315         int i, j, indexLen;
316         /* offset matrix */
317         float offset[4][4];
318         float length = amd->length;
319         int count = amd->count, maxVerts;
320         int *indexMap = NULL;
321         DerivedMesh *start_cap = NULL, *end_cap = NULL;
322         MVert *src_mvert;
323
324         /* need to avoid infinite recursion here */
325         if(amd->start_cap && amd->start_cap != ob)
326                 start_cap = mesh_get_derived_final(scene, amd->start_cap, CD_MASK_MESH);
327         if(amd->end_cap && amd->end_cap != ob)
328                 end_cap = mesh_get_derived_final(scene, amd->end_cap, CD_MASK_MESH);
329
330         unit_m4(offset);
331
332         src_mvert = cddm->getVertArray(dm);
333         maxVerts = cddm->getNumVerts(dm);
334
335         if(amd->offset_type & MOD_ARR_OFF_CONST)
336                 add_v3_v3v3(offset[3], offset[3], amd->offset);
337         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
338                 for(j = 0; j < 3; j++)
339                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
340                                         maxVerts, j);
341         }
342
343         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
344                 float obinv[4][4];
345                 float result_mat[4][4];
346
347                 if(ob)
348                         invert_m4_m4(obinv, ob->obmat);
349                 else
350                         unit_m4(obinv);
351
352                 mul_serie_m4(result_mat, offset,
353                                  obinv, amd->offset_ob->obmat,
354                                                                  NULL, NULL, NULL, NULL, NULL);
355                 copy_m4_m4(offset, result_mat);
356         }
357
358         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
359                 Curve *cu = amd->curve_ob->data;
360                 if(cu) {
361                         float tmp_mat[3][3];
362                         float scale;
363
364                         object_to_mat3(amd->curve_ob, tmp_mat);
365                         scale = mat3_to_scale(tmp_mat);
366
367                         if(!cu->path) {
368                                 cu->flag |= CU_PATH; // needed for path & bevlist
369                                 makeDispListCurveTypes(scene, amd->curve_ob, 0);
370                         }
371                         if(cu->path)
372                                 length = scale*cu->path->totdist;
373                 }
374         }
375
376         /* calculate the maximum number of copies which will fit within the
377         prescribed length */
378         if(amd->fit_type == MOD_ARR_FITLENGTH
379                   || amd->fit_type == MOD_ARR_FITCURVE)
380         {
381                 float dist = sqrt(INPR(offset[3], offset[3]));
382
383                 if(dist > 1e-6f)
384                         /* this gives length = first copy start to last copy end
385                         add a tiny offset for floating point rounding errors */
386                         count = (length + 1e-6f) / dist;
387                 else
388                         /* if the offset has no translation, just make one copy */
389                         count = 1;
390         }
391
392         if(count < 1)
393                 count = 1;
394
395         BMO_Init_Op(&weldop, "weldverts");
396         BMO_InitOpf(em->bm, &op, "dupe geom=%avef");
397         oldop = op;
398         for (j=0; j < count - 1; j++) {
399                 BMVert *v, *v2;
400                 BMOpSlot *s1;
401                 BMOpSlot *s2;
402
403                 BMO_InitOpf(em->bm, &op, "dupe geom=%s", &oldop, j==0 ? "geom" : "newout");
404                 BMO_Exec_Op(em->bm, &op);
405
406                 s1 = BMO_GetSlot(&op, "geom");
407                 s2 = BMO_GetSlot(&op, "newout");
408
409                 BMO_CallOpf(em->bm, "transform mat=%m4 verts=%s", offset, &op, "newout");
410
411                 #define _E(s, i) ((BMVert**)(s)->data.buf)[i]
412
413                 /*calculate merge mapping*/
414                 if (j == 0) {
415                         BMOperator findop;
416                         BMOIter oiter;
417                         BMVert *v, *v2;
418                         BMHeader *h;
419
420                         BMO_InitOpf(em->bm, &findop,
421                                 "finddoubles verts=%av dist=%f keepverts=%s",
422                                 amd->merge_dist, &op, "geom");
423
424                         i = 0;
425                         BMO_ITER(h, &oiter, em->bm, &op, "geom", BM_ALL) {
426                                 BM_SetIndex(h, i);
427                                 i++;
428                         }
429
430                         BMO_ITER(h, &oiter, em->bm, &op, "newout", BM_ALL) {
431                                 BM_SetIndex(h, i);
432                                 i++;
433                         }
434
435                         BMO_Exec_Op(em->bm, &findop);
436
437                         indexLen = i;
438                         indexMap = MEM_callocN(sizeof(int)*indexLen, "indexMap");
439
440                         /*element type argument doesn't do anything here*/
441                         BMO_ITER(v, &oiter, em->bm, &findop, "targetmapout", 0) {
442                                 v2 = BMO_IterMapValp(&oiter);
443
444                                 indexMap[BM_GetIndex(v)] = BM_GetIndex(v2)+1;
445                         }
446
447                         BMO_Finish_Op(em->bm, &findop);
448                 }
449
450                 /*generate merge mappping using index map.  we do this by using the
451                   operator slots as lookup arrays.*/
452                 #define E(i) (i) < s1->len ? _E(s1, i) : _E(s2, (i)-s1->len)
453
454                 for (i=0; i<indexLen; i++) {
455                         if (!indexMap[i]) continue;
456
457                         v = E(i);
458                         v2 = E(indexMap[i]-1);
459
460                         BMO_Insert_MapPointer(em->bm, &weldop, "targetmap", v, v2);
461                 }
462
463                 #undef E
464                 #undef _E
465
466                 BMO_Finish_Op(em->bm, &oldop);
467                 oldop = op;
468         }
469
470         if (j > 0) BMO_Finish_Op(em->bm, &op);
471
472         if (amd->flags & MOD_ARR_MERGE)
473                 BMO_Exec_Op(em->bm, &weldop);
474
475         BMO_Finish_Op(em->bm, &weldop);
476
477         BMEdit_RecalcTesselation(em);
478         cddm = CDDM_from_BMEditMesh(em, NULL, 0);
479
480         BMEdit_Free(em);
481         MEM_freeN(em);
482         MEM_freeN(indexMap);
483
484         return cddm;
485 }
486
487 static DerivedMesh *applyModifier(
488                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
489                 int UNUSED(useRenderParams), int UNUSED(isFinalCalc))
490 {
491         DerivedMesh *result;
492         ArrayModifierData *amd = (ArrayModifierData*) md;
493
494         result = arrayModifier_doArray(amd, md->scene, ob, derivedData, 0);
495
496         //if(result != derivedData)
497         //      CDDM_calc_normals(result);
498
499         return result;
500 }
501
502 static DerivedMesh *applyModifierEM(
503                 ModifierData *md, Object *ob, struct BMEditMesh *UNUSED(editData),
504   DerivedMesh *derivedData)
505 {
506         return applyModifier(md, ob, derivedData, 0, 1);
507 }
508
509
510 ModifierTypeInfo modifierType_Array = {
511         /* name */              "Array",
512         /* structName */        "ArrayModifierData",
513         /* structSize */        sizeof(ArrayModifierData),
514         /* type */              eModifierTypeType_Constructive,
515         /* flags */             eModifierTypeFlag_AcceptsMesh
516                                                         | eModifierTypeFlag_SupportsMapping
517                                                         | eModifierTypeFlag_SupportsEditmode
518                                                         | eModifierTypeFlag_EnableInEditmode
519                                                         | eModifierTypeFlag_AcceptsCVs,
520
521         /* copyData */          copyData,
522         /* deformVerts */       NULL,
523         /* deformMatrices */    NULL,
524         /* deformVertsEM */     NULL,
525         /* deformMatricesEM */  NULL,
526         /* applyModifier */     applyModifier,
527         /* applyModifierEM */   applyModifierEM,
528         /* initData */          initData,
529         /* requiredDataMask */  NULL,
530         /* freeData */          NULL,
531         /* isDisabled */        NULL,
532         /* updateDepgraph */    updateDepgraph,
533         /* dependsOnTime */     NULL,
534         /* dependsOnNormals */  NULL,
535         /* foreachObjectLink */ foreachObjectLink,
536         /* foreachIDLink */     NULL,
537         /* foreachTexLink */    NULL,
538 };