fix [#30768] Project from View UV map tool includes hidden geometry r45323
[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 /** \file blender/modifiers/intern/MOD_array.c
32  *  \ingroup modifiers
33  */
34
35
36 /* Array modifier: duplicates the object multiple times along an axis */
37
38 #include "MEM_guardedalloc.h"
39
40 #include "BLI_math.h"
41 #include "BLI_utildefines.h"
42 #include "BLI_string.h"
43 #include "BLI_ghash.h"
44 #include "BLI_edgehash.h"
45
46 #include "DNA_curve_types.h"
47 #include "DNA_meshdata_types.h"
48 #include "DNA_object_types.h"
49 #include "DNA_scene_types.h"
50
51 #include "BKE_cdderivedmesh.h"
52 #include "BKE_displist.h"
53 #include "BKE_mesh.h"
54 #include "BKE_modifier.h"
55 #include "BKE_object.h"
56 #include "BKE_tessmesh.h"
57
58 #include "depsgraph_private.h"
59
60 #include <ctype.h>
61 #include <stdlib.h>
62 #include <string.h>
63
64 static void initData(ModifierData *md)
65 {
66         ArrayModifierData *amd = (ArrayModifierData*) md;
67
68         /* default to 2 duplicates distributed along the x-axis by an
69          * offset of 1 object-width
70          */
71         amd->start_cap = amd->end_cap = amd->curve_ob = amd->offset_ob = NULL;
72         amd->count = 2;
73         zero_v3(amd->offset);
74         amd->scale[0] = 1;
75         amd->scale[1] = amd->scale[2] = 0;
76         amd->length = 0;
77         amd->merge_dist = 0.01;
78         amd->fit_type = MOD_ARR_FIXEDCOUNT;
79         amd->offset_type = MOD_ARR_OFF_RELATIVE;
80         amd->flags = 0;
81 }
82
83 static void copyData(ModifierData *md, ModifierData *target)
84 {
85         ArrayModifierData *amd = (ArrayModifierData*) md;
86         ArrayModifierData *tamd = (ArrayModifierData*) target;
87
88         tamd->start_cap = amd->start_cap;
89         tamd->end_cap = amd->end_cap;
90         tamd->curve_ob = amd->curve_ob;
91         tamd->offset_ob = amd->offset_ob;
92         tamd->count = amd->count;
93         copy_v3_v3(tamd->offset, amd->offset);
94         copy_v3_v3(tamd->scale, amd->scale);
95         tamd->length = amd->length;
96         tamd->merge_dist = amd->merge_dist;
97         tamd->fit_type = amd->fit_type;
98         tamd->offset_type = amd->offset_type;
99         tamd->flags = amd->flags;
100 }
101
102 static void foreachObjectLink(
103                                                 ModifierData *md, Object *ob,
104          void (*walk)(void *userData, Object *ob, Object **obpoin),
105                 void *userData)
106 {
107         ArrayModifierData *amd = (ArrayModifierData*) md;
108
109         walk(userData, ob, &amd->start_cap);
110         walk(userData, ob, &amd->end_cap);
111         walk(userData, ob, &amd->curve_ob);
112         walk(userData, ob, &amd->offset_ob);
113 }
114
115 static void updateDepgraph(ModifierData *md, DagForest *forest,
116         struct Scene *UNUSED(scene), Object *UNUSED(ob), DagNode *obNode)
117 {
118         ArrayModifierData *amd = (ArrayModifierData*) md;
119
120         if (amd->start_cap) {
121                 DagNode *curNode = dag_get_node(forest, amd->start_cap);
122
123                 dag_add_relation(forest, curNode, obNode,
124                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
125         }
126         if (amd->end_cap) {
127                 DagNode *curNode = dag_get_node(forest, amd->end_cap);
128
129                 dag_add_relation(forest, curNode, obNode,
130                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
131         }
132         if (amd->curve_ob) {
133                 DagNode *curNode = dag_get_node(forest, amd->curve_ob);
134
135                 dag_add_relation(forest, curNode, obNode,
136                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
137         }
138         if (amd->offset_ob) {
139                 DagNode *curNode = dag_get_node(forest, amd->offset_ob);
140
141                 dag_add_relation(forest, curNode, obNode,
142                                  DAG_RL_DATA_DATA | DAG_RL_OB_DATA, "Array Modifier");
143         }
144 }
145
146 static float vertarray_size(MVert *mvert, int numVerts, int axis)
147 {
148         int i;
149         float min_co, max_co;
150
151         /* if there are no vertices, width is 0 */
152         if (numVerts == 0) return 0;
153
154         /* find the minimum and maximum coordinates on the desired axis */
155         min_co = max_co = mvert->co[axis];
156         ++mvert;
157         for (i = 1; i < numVerts; ++i, ++mvert) {
158                 if (mvert->co[axis] < min_co) min_co = mvert->co[axis];
159                 if (mvert->co[axis] > max_co) max_co = mvert->co[axis];
160         }
161
162         return max_co - min_co;
163 }
164
165 static int *find_doubles_index_map(BMesh *bm, BMOperator *dupe_op,
166                                                                    const ArrayModifierData *amd,
167                                                                    int *index_map_length)
168 {
169         BMOperator find_op;
170         BMOIter oiter;
171         BMVert *v, *v2;
172         BMElem *ele;
173         int *index_map, i;
174
175         BMO_op_initf(bm, &find_op,
176                                  "finddoubles verts=%av dist=%f keepverts=%s",
177                                  amd->merge_dist, dupe_op, "geom");
178
179         BMO_op_exec(bm, &find_op);
180                         
181         i = 0;
182         BMO_ITER(ele, &oiter, bm, dupe_op, "geom", BM_ALL) {
183                 BM_elem_index_set(ele, i); /* set_dirty */
184                 i++;
185         }
186
187         BMO_ITER(ele, &oiter, bm, dupe_op, "newout", BM_ALL) {
188                 BM_elem_index_set(ele, i); /* set_dirty */
189                 i++;
190         }
191         /* above loops over all, so set all to dirty, if this is somehow
192          * setting valid values, this line can be remvoed - campbell */
193         bm->elem_index_dirty |= BM_VERT | BM_EDGE | BM_FACE;
194
195         (*index_map_length) = i;
196         index_map = MEM_callocN(sizeof(int) * (*index_map_length), "index_map");
197
198         /*element type argument doesn't do anything here*/
199         BMO_ITER(v, &oiter, bm, &find_op, "targetmapout", 0) {
200                 v2 = BMO_iter_map_value_p(&oiter);
201
202                 index_map[BM_elem_index_get(v)] = BM_elem_index_get(v2) + 1;
203         }
204
205         BMO_op_finish(bm, &find_op);
206
207         return index_map;
208 }
209
210 /* Used for start/end cap.
211  *
212  * this function expects all existing vertices to be tagged,
213  * so we can know new verts are not tagged.
214  *
215  * All verts will be tagged on exit.
216  */
217 static void bm_merge_dm_transform(BMesh* bm, DerivedMesh *dm, float mat[4][4],
218                                                                   const ArrayModifierData *amd,
219                                                                   BMOperator *dupe_op,
220                                                                   const char *dupe_slot_name,
221                                                                   BMOperator *weld_op)
222 {
223         BMVert *v, *v2;
224         BMIter iter;
225
226         DM_to_bmesh_ex(dm, bm);
227
228         if (amd->flags & MOD_ARR_MERGE) {
229                 /* if merging is enabled, find doubles */
230                 
231                 BMOIter oiter;
232                 BMOperator find_op;
233
234                 BMO_op_initf(bm, &find_op,
235                                          "finddoubles verts=%Hv dist=%f keepverts=%s",
236                                          BM_ELEM_TAG, amd->merge_dist,
237                                          dupe_op, dupe_slot_name);
238
239                 /* append the dupe's geom to the findop input verts */
240                 BMO_slot_buffer_append(&find_op, "verts", dupe_op, dupe_slot_name);
241
242                 /* transform and tag verts */
243                 BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
244                         if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
245                                 mul_m4_v3(mat, v->co);
246                                 BM_elem_flag_enable(v, BM_ELEM_TAG);
247                         }
248                 }
249
250                 BMO_op_exec(bm, &find_op);
251
252                 /* add new merge targets to weld operator */
253                 BMO_ITER(v, &oiter, bm, &find_op, "targetmapout", 0) {
254                         v2 = BMO_iter_map_value_p(&oiter);
255                         BMO_slot_map_ptr_insert(bm, weld_op, "targetmap", v, v2);
256                 }
257
258                 BMO_op_finish(bm, &find_op);
259         }
260         else {
261                 /* transform and tag verts */
262                 BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
263                         if (!BM_elem_flag_test(v, BM_ELEM_TAG)) {
264                                 mul_m4_v3(mat, v->co);
265                                 BM_elem_flag_enable(v, BM_ELEM_TAG);
266                         }
267                 }
268         }
269 }
270
271 static void merge_first_last(BMesh* bm,
272                                                          const ArrayModifierData *amd,
273                                                          BMOperator *dupe_first,
274                                                          BMOperator *dupe_last,
275                                                          BMOperator *weld_op)
276 {
277         BMOperator find_op;
278         BMOIter oiter;
279         BMVert *v, *v2;
280
281         BMO_op_initf(bm, &find_op,
282                                  "finddoubles verts=%s dist=%f keepverts=%s",
283                                  dupe_first, "geom", amd->merge_dist,
284                                  dupe_first, "geom");
285
286         /* append the last dupe's geom to the findop input verts */
287         BMO_slot_buffer_append(&find_op, "verts", dupe_last, "newout");
288
289         BMO_op_exec(bm, &find_op);
290
291         /* add new merge targets to weld operator */
292         BMO_ITER(v, &oiter, bm, &find_op, "targetmapout", 0) {
293                 v2 = BMO_iter_map_value_p(&oiter);
294                 BMO_slot_map_ptr_insert(bm, weld_op, "targetmap", v, v2);
295         }
296
297         BMO_op_finish(bm, &find_op);
298 }
299
300 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
301                                           Scene *scene, Object *ob, DerivedMesh *dm,
302                                           int UNUSED(initFlags))
303 {
304         DerivedMesh *result;
305         BMEditMesh *em = DM_to_editbmesh(dm, NULL, FALSE);
306         BMOperator first_dupe_op, dupe_op, old_dupe_op, weld_op;
307         BMVert **first_geom = NULL;
308         int i, j, indexLen;
309         /* offset matrix */
310         float offset[4][4];
311         float final_offset[4][4];
312         float tmp_mat[4][4];
313         float length = amd->length;
314         int count = amd->count, maxVerts;
315         int *indexMap = NULL;
316         DerivedMesh *start_cap = NULL, *end_cap = NULL;
317         MVert *src_mvert;
318
319         /* need to avoid infinite recursion here */
320         if (amd->start_cap && amd->start_cap != ob)
321                 start_cap = mesh_get_derived_final(scene, amd->start_cap, CD_MASK_MESH);
322         if (amd->end_cap && amd->end_cap != ob)
323                 end_cap = mesh_get_derived_final(scene, amd->end_cap, CD_MASK_MESH);
324
325         unit_m4(offset);
326
327         src_mvert = dm->getVertArray(dm);
328         maxVerts = dm->getNumVerts(dm);
329
330         if (amd->offset_type & MOD_ARR_OFF_CONST)
331                 add_v3_v3v3(offset[3], offset[3], amd->offset);
332         if (amd->offset_type & MOD_ARR_OFF_RELATIVE) {
333                 for (j = 0; j < 3; j++)
334                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
335                                         maxVerts, j);
336         }
337
338         if ((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
339                 float obinv[4][4];
340                 float result_mat[4][4];
341
342                 if (ob)
343                         invert_m4_m4(obinv, ob->obmat);
344                 else
345                         unit_m4(obinv);
346
347                 mul_serie_m4(result_mat, offset,
348                              obinv, amd->offset_ob->obmat,
349                              NULL, NULL, NULL, NULL, NULL);
350                 copy_m4_m4(offset, result_mat);
351         }
352
353         if (amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
354                 Curve *cu = amd->curve_ob->data;
355                 if (cu) {
356                         float tmp_mat[3][3];
357                         float scale;
358                         
359                         object_to_mat3(amd->curve_ob, tmp_mat);
360                         scale = mat3_to_scale(tmp_mat);
361                                 
362                         if (!cu->path) {
363                                 cu->flag |= CU_PATH; // needed for path & bevlist
364                                 makeDispListCurveTypes(scene, amd->curve_ob, 0);
365                         }
366                         if (cu->path)
367                                 length = scale*cu->path->totdist;
368                 }
369         }
370
371         /* calculate the maximum number of copies which will fit within the
372          * prescribed length */
373         if (amd->fit_type == MOD_ARR_FITLENGTH
374                   || amd->fit_type == MOD_ARR_FITCURVE) {
375                 float dist = sqrt(dot_v3v3(offset[3], offset[3]));
376
377                 if (dist > 1e-6f)
378                         /* this gives length = first copy start to last copy end
379                          * add a tiny offset for floating point rounding errors */
380                         count = (length + 1e-6f) / dist;
381                 else
382                         /* if the offset has no translation, just make one copy */
383                         count = 1;
384         }
385
386         if (count < 1)
387                 count = 1;
388
389         /* calculate the offset matrix of the final copy (for merging) */
390         unit_m4(final_offset);
391
392         for (j=0; j < count - 1; j++) {
393                 mult_m4_m4m4(tmp_mat, offset, final_offset);
394                 copy_m4_m4(final_offset, tmp_mat);
395         }
396
397         /* BMESH_TODO: bumping up the stack level avoids computing the normals
398          * after every top-level operator execution (and this modifier has the
399          * potential to execute a *lot* of top-level BMOps. There should be a
400          * cleaner way to do this. One possibility: a "mirror" BMOp would
401          * certainly help by compressing it all into one top-level BMOp that
402          * executes a lot of second-level BMOps. */
403         BMO_push(em->bm, NULL);
404         bmesh_edit_begin(em->bm, 0);
405
406         if (amd->flags & MOD_ARR_MERGE)
407                 BMO_op_init(em->bm, &weld_op, "weldverts");
408
409         BMO_op_initf(em->bm, &dupe_op, "dupe geom=%avef");
410         first_dupe_op = dupe_op;
411
412         for (j=0; j < count - 1; j++) {
413                 BMVert *v, *v2, *v3;
414                 BMOpSlot *geom_slot;
415                 BMOpSlot *newout_slot;
416                 BMOIter oiter;
417
418                 if (j != 0)
419                         BMO_op_initf(em->bm, &dupe_op, "dupe geom=%s", &old_dupe_op, "newout");
420                 BMO_op_exec(em->bm, &dupe_op);
421
422                 geom_slot = BMO_slot_get(&dupe_op, "geom");
423                 newout_slot = BMO_slot_get(&dupe_op, "newout");
424
425                 if ((amd->flags & MOD_ARR_MERGEFINAL) && j == 0) {
426                         int first_geom_bytes = sizeof(BMVert*) * geom_slot->len;
427                                 
428                         /* make a copy of the initial geometry ordering so the
429                            last duplicate can be merged into it */
430                         first_geom = MEM_mallocN(first_geom_bytes, "first_geom");
431                         memcpy(first_geom, geom_slot->data.buf, first_geom_bytes);
432                 }
433
434                 /* apply transformation matrix */
435                 BMO_ITER(v, &oiter, em->bm, &dupe_op, "newout", BM_VERT) {
436                         mul_m4_v3(offset, v->co);
437                 }
438
439                 if (amd->flags & MOD_ARR_MERGE) {
440                         /*calculate merge mapping*/
441                         if (j == 0) {
442                                 indexMap = find_doubles_index_map(em->bm, &dupe_op,
443                                                                                                   amd, &indexLen);
444                         }
445
446                         #define _E(s, i) ((BMVert **)(s)->data.buf)[i]
447
448                         for (i=0; i<indexLen; i++) {
449                                 if (!indexMap[i]) continue;
450
451                                 /* merge v (from 'newout') into v2 (from old 'geom') */
452                                 v = _E(newout_slot, i - geom_slot->len);
453                                 v2 = _E(geom_slot, indexMap[i]-1);
454
455                                 /* check in case the target vertex (v2) is already marked
456                                    for merging */
457                                 while((v3 = BMO_slot_map_ptr_get(em->bm, &weld_op, "targetmap", v2)))
458                                         v2 = v3;
459
460                                 BMO_slot_map_ptr_insert(em->bm, &weld_op, "targetmap", v, v2);
461                         }
462
463                         #undef _E
464                 }
465
466                 /* already copied earlier, but after executation more slot
467                    memory may be allocated */
468                 if (j == 0)
469                         first_dupe_op = dupe_op;
470                 
471                 if (j >= 2)
472                         BMO_op_finish(em->bm, &old_dupe_op);
473                 old_dupe_op = dupe_op;
474         }
475
476         if ((amd->flags & MOD_ARR_MERGE) &&
477             (amd->flags & MOD_ARR_MERGEFINAL) &&
478             (count > 1))
479         {
480                 /* Merge first and last copies. Note that we can't use the
481                  * indexMap for this because (unless the array is forming a
482                  * loop) the offset between first and last is different from
483                  * dupe X to dupe X+1. */
484
485                 merge_first_last(em->bm, amd, &first_dupe_op, &dupe_op, &weld_op);
486         }
487
488         /* start capping */
489         if (start_cap || end_cap) {
490                 BM_mesh_elem_flag_enable_all(em->bm, BM_VERT, BM_ELEM_TAG, FALSE);
491
492                 if (start_cap) {
493                         float startoffset[4][4];
494                         invert_m4_m4(startoffset, offset);
495                         bm_merge_dm_transform(em->bm, start_cap, startoffset, amd,
496                                                   &first_dupe_op, "geom", &weld_op);
497                 }
498
499                 if (end_cap) {
500                         float endoffset[4][4];
501                         mult_m4_m4m4(endoffset, offset, final_offset);
502                         bm_merge_dm_transform(em->bm, end_cap, endoffset, amd,
503                                 &dupe_op, count == 1 ? "geom" : "newout", &weld_op);
504                 }
505         }
506         /* done capping */
507
508         /* free remaining dupe operators */
509         BMO_op_finish(em->bm, &first_dupe_op);
510         if (count > 2)
511                 BMO_op_finish(em->bm, &dupe_op);
512
513         /* run merge operator */
514         if (amd->flags & MOD_ARR_MERGE) {
515                 BMO_op_exec(em->bm, &weld_op);
516                 BMO_op_finish(em->bm, &weld_op);
517         }
518
519         /* Bump the stack level back down to match the adjustment up above */
520         BMO_pop(em->bm);
521
522         BLI_assert(em->looptris == NULL);
523         result = CDDM_from_BMEditMesh(em, NULL, FALSE, FALSE);
524
525         if ((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
526                 /* Update normals in case offset object has rotation. */
527                 
528                 /* BMESH_TODO: check if normal recalc needed under any other
529                    conditions? */
530
531                 CDDM_calc_normals(result);
532         }
533
534         BMEdit_Free(em);
535         MEM_freeN(em);
536         if (indexMap)
537                 MEM_freeN(indexMap);
538         if (first_geom)
539                 MEM_freeN(first_geom);
540
541         return result;
542 }
543
544 static DerivedMesh *applyModifier(ModifierData *md, Object *ob,
545                                                 DerivedMesh *dm,
546                                                 int UNUSED(useRenderParams),
547                                                 int UNUSED(isFinalCalc))
548 {
549         DerivedMesh *result;
550         ArrayModifierData *amd = (ArrayModifierData*) md;
551
552         result = arrayModifier_doArray(amd, md->scene, ob, dm, 0);
553
554         //if(result != dm)
555         //      CDDM_calc_normals_mapping(result);
556
557         return result;
558 }
559
560 static DerivedMesh *applyModifierEM(ModifierData *md, Object *ob,
561                                                 struct BMEditMesh *UNUSED(editData),
562                                                 DerivedMesh *dm)
563 {
564         return applyModifier(md, ob, dm, 0, 1);
565 }
566
567
568 ModifierTypeInfo modifierType_Array = {
569         /* name */              "Array",
570         /* structName */        "ArrayModifierData",
571         /* structSize */        sizeof(ArrayModifierData),
572         /* type */              eModifierTypeType_Constructive,
573         /* flags */             eModifierTypeFlag_AcceptsMesh
574                                                         | eModifierTypeFlag_SupportsMapping
575                                                         | eModifierTypeFlag_SupportsEditmode
576                                                         | eModifierTypeFlag_EnableInEditmode
577                                                         | eModifierTypeFlag_AcceptsCVs,
578
579         /* copyData */          copyData,
580         /* deformVerts */       NULL,
581         /* deformMatrices */    NULL,
582         /* deformVertsEM */     NULL,
583         /* deformMatricesEM */  NULL,
584         /* applyModifier */     applyModifier,
585         /* applyModifierEM */   applyModifierEM,
586         /* initData */          initData,
587         /* requiredDataMask */  NULL,
588         /* freeData */          NULL,
589         /* isDisabled */        NULL,
590         /* updateDepgraph */    updateDepgraph,
591         /* dependsOnTime */     NULL,
592         /* dependsOnNormals */  NULL,
593         /* foreachObjectLink */ foreachObjectLink,
594         /* foreachIDLink */     NULL,
595         /* foreachTexLink */    NULL,
596 };