pre-merge commit. the mirror modifier is currently in pieces, to be picked back...
[blender.git] / source / blender / blenkernel / intern / modifiers_bmesh.c
1 /*
2 * $Id: modifier_bmesh.c 20831 2009-06-12 14:02:37Z joeedh $
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): Joseph Eagar
24 *
25 * ***** END GPL LICENSE BLOCK *****
26 *
27 * Modifier stack implementation.
28 *
29 * BKE_modifier.h contains the function prototypes for this file.
30 *
31 */
32
33 #include "string.h"
34 #include "stdarg.h"
35 #include "math.h"
36 #include "float.h"
37 #include "ctype.h"
38
39 #include "BLI_arithb.h"
40 #include "BLI_blenlib.h"
41 #include "BLI_kdopbvh.h"
42 #include "BLI_kdtree.h"
43 #include "BLI_linklist.h"
44 #include "BLI_rand.h"
45 #include "BLI_edgehash.h"
46 #include "BLI_ghash.h"
47 #include "BLI_memarena.h"
48
49 #include "MEM_guardedalloc.h"
50
51 #include "DNA_action_types.h"
52 #include "DNA_armature_types.h"
53 #include "DNA_camera_types.h"
54 #include "DNA_cloth_types.h"
55 #include "DNA_curve_types.h"
56 #include "DNA_effect_types.h"
57 #include "DNA_material_types.h"
58 #include "DNA_mesh_types.h"
59 #include "DNA_meshdata_types.h"
60 #include "DNA_modifier_types.h"
61 #include "DNA_object_types.h"
62 #include "DNA_object_force.h"
63 #include "DNA_particle_types.h"
64 #include "DNA_scene_types.h"
65 #include "DNA_texture_types.h"
66
67 #include "BLI_editVert.h"
68
69 #include "MTC_matrixops.h"
70 #include "MTC_vectorops.h"
71
72 #include "BKE_main.h"
73 #include "BKE_anim.h"
74 #include "BKE_bmesh.h"
75 // XXX #include "BKE_booleanops.h"
76 #include "BKE_cloth.h"
77 #include "BKE_collision.h"
78 #include "BKE_cdderivedmesh.h"
79 #include "BKE_curve.h"
80 #include "BKE_customdata.h"
81 #include "BKE_DerivedMesh.h"
82 #include "BKE_displist.h"
83 #include "BKE_fluidsim.h"
84 #include "BKE_global.h"
85 #include "BKE_multires.h"
86 #include "BKE_lattice.h"
87 #include "BKE_library.h"
88 #include "BKE_material.h"
89 #include "BKE_mesh.h"
90 #include "BKE_modifier.h"
91 #include "BKE_object.h"
92 #include "BKE_particle.h"
93 #include "BKE_pointcache.h"
94 #include "BKE_softbody.h"
95 #include "BKE_subsurf.h"
96 #include "BKE_texture.h"
97 #include "BKE_utildefines.h"
98 #include "BKE_tessmesh.h"
99
100 #include "depsgraph_private.h"
101 #include "BKE_deform.h"
102 #include "BKE_shrinkwrap.h"
103 #include "BKE_simple_deform.h"
104
105 #include "CCGSubSurf.h"
106 #include "RE_shader_ext.h"
107 #include "LOD_decimation.h"
108
109 /*converts a cddm to a BMEditMesh.  if existing is non-NULL, the
110   new geometry will be put in there.*/
111 BMEditMesh *CDDM_To_BMesh(DerivedMesh *dm, BMEditMesh *existing)
112 {
113         int allocsize[4] = {512, 512, 2048, 512};
114         BMesh *bm, bmold; /*bmold is for storing old customdata layout*/
115         BMEditMesh *em = existing;
116         MVert *mv;
117         MEdge *me;
118         DMFaceIter *dfiter;
119         DMLoopIter *dliter;
120         BMVert *v, **vtable, **verts=NULL;
121         BMEdge *e, **etable, **edges=NULL;
122         BMFace *f;
123         BMIter liter, iter;
124         V_DECLARE(verts);
125         V_DECLARE(edges);
126         void *tmp;
127         int numTex, numCol;
128         int i, j, k, tot, totvert, totedge, totface;
129         
130         if (em) bm = em->bm;
131         else bm = BM_Make_Mesh(allocsize);
132
133         bmold = *bm;
134
135         /*merge custom data layout*/
136         CustomData_bmesh_merge(&dm->vertData, &bm->vdata, CD_MASK_BMESH|CD_MASK_ORIGINDEX, CD_CALLOC, bm, BM_VERT);
137         CustomData_bmesh_merge(&dm->edgeData, &bm->edata, CD_MASK_BMESH|CD_MASK_ORIGINDEX, CD_CALLOC, bm, BM_EDGE);
138         CustomData_bmesh_merge(&dm->loopData, &bm->ldata, CD_MASK_BMESH|CD_MASK_ORIGINDEX, CD_CALLOC, bm, BM_LOOP);
139         CustomData_bmesh_merge(&dm->polyData, &bm->pdata, CD_MASK_BMESH|CD_MASK_ORIGINDEX, CD_CALLOC, bm, BM_FACE);
140
141         /*needed later*/
142         numTex = CustomData_number_of_layers(&bm->pdata, CD_MTEXPOLY);
143         numCol = CustomData_number_of_layers(&bm->ldata, CD_MLOOPCOL);
144
145         totvert = dm->getNumVerts(dm);
146         totedge = dm->getNumEdges(dm);
147         totface = dm->getNumFaces(dm);
148
149         vtable = MEM_callocN(sizeof(void**)*totvert, "vert table in BMDM_Copy");
150         etable = MEM_callocN(sizeof(void**)*totedge, "edge table in BMDM_Copy");
151
152         /*do verts*/
153         mv = dm->dupVertArray(dm);
154         for (i=0; i<totvert; i++, mv++) {
155                 v = BM_Make_Vert(bm, mv->co, NULL);
156                 
157                 v->bweight = mv->bweight;
158                 VECCOPY(v->no, mv->no);
159                 v->head.flag = MEFlags_To_BMFlags(mv->flag, BM_VERT);
160
161                 CustomData_to_bmesh_block(&dm->vertData, &bm->vdata, i, &v->head.data);
162                 vtable[i] = v;
163         }
164
165         /*do edges*/
166         me = dm->dupEdgeArray(dm);
167         for (i=0; i<totedge; i++, me++) {
168                 e = BM_Make_Edge(bm, vtable[me->v1], vtable[me->v2], NULL, 0);
169
170                 e->bweight = me->bweight;
171                 e->crease = me->crease;
172                 e->head.flag = MEFlags_To_BMFlags(me->flag, BM_EDGE);
173
174                 CustomData_to_bmesh_block(&dm->edgeData, &bm->edata, i, &e->head.data);
175                 etable[i] = e;
176         }
177         
178         k = 0;
179         dfiter = dm->newFaceIter(dm);
180         for (; !dfiter->done; dfiter->step(dfiter)) {
181                 BMLoop *l;
182
183                 V_RESET(verts);
184                 V_RESET(edges);
185
186                 dliter = dfiter->getLoopsIter(dfiter);
187                 for (j=0; !dliter->done; dliter->step(dliter), j++) {
188                         V_GROW(verts);
189                         V_GROW(edges);
190
191                         verts[j] = vtable[dliter->vindex];
192                         edges[j] = etable[dliter->eindex];
193                 }
194                 
195                 f = BM_Make_Ngon(bm, verts[0], verts[1], edges, dfiter->len, 0);
196                 f->head.flag = MEFlags_To_BMFlags(dfiter->flags, BM_FACE);
197
198                 if (!f) 
199                         continue;
200
201                 dliter = dfiter->getLoopsIter(dfiter);
202                 l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
203                 for (j=0; l; l=BMIter_Step(&liter)) {
204                         CustomData_to_bmesh_block(&dm->loopData, &bm->ldata, k, &l->head.data);
205                         k += 1;
206                 }
207
208                 CustomData_to_bmesh_block(&dm->polyData, &bm->pdata, 
209                         dfiter->index, &f->head.data);
210         }
211
212         MEM_freeN(vtable);
213         MEM_freeN(etable);
214         
215         if (!em) em = BMEdit_Create(bm);
216         else BMEdit_RecalcTesselation(em);
217
218         return em;
219 }
220
221 float vertarray_size(MVert *mvert, int numVerts, int axis);
222
223
224 typedef struct IndexMapEntry {
225         /* the new vert index that this old vert index maps to */
226         int new;
227         /* -1 if this vert isn't merged, otherwise the old vert index it
228         * should be replaced with
229         */
230         int merge;
231         /* 1 if this vert's first copy is merged with the last copy of its
232         * merge target, otherwise 0
233         */
234         short merge_final;
235 } IndexMapEntry;
236
237 /* indexMap - an array of IndexMap entries
238  * oldIndex - the old index to map
239  * copyNum - the copy number to map to (original = 0, first copy = 1, etc.)
240  */
241 static int calc_mapping(IndexMapEntry *indexMap, int oldIndex, int copyNum)
242 {
243         if(indexMap[oldIndex].merge < 0) {
244                 /* vert wasn't merged, so use copy of this vert */
245                 return indexMap[oldIndex].new + copyNum;
246         } else if(indexMap[oldIndex].merge == oldIndex) {
247                 /* vert was merged with itself */
248                 return indexMap[oldIndex].new;
249         } else {
250                 /* vert was merged with another vert */
251                 /* follow the chain of merges to the end, or until we've passed
252                 * a number of vertices equal to the copy number
253                 */
254                 if(copyNum <= 0)
255                         return indexMap[oldIndex].new;
256                 else
257                         return calc_mapping(indexMap, indexMap[oldIndex].merge,
258                                             copyNum - 1);
259         }
260 }
261
262 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
263                                           Scene *scene, Object *ob, DerivedMesh *dm,
264                                           int initFlags)
265 {
266         DerivedMesh *cddm = CDDM_copy(dm);
267         BMEditMesh *em = CDDM_To_BMesh(cddm, NULL);
268         BMOperator op, oldop, weldop;
269         int i, j, indexLen;
270         /* offset matrix */
271         float offset[4][4];
272         float final_offset[4][4];
273         float tmp_mat[4][4];
274         float length = amd->length;
275         int count = amd->count;
276         int numVerts, numEdges, numFaces;
277         int maxVerts, maxEdges, maxFaces;
278         int finalVerts, finalEdges, finalFaces;
279         int *indexMap;
280         DerivedMesh *result, *start_cap = NULL, *end_cap = NULL;
281         MVert *src_mvert;
282
283         /* need to avoid infinite recursion here */
284         if(amd->start_cap && amd->start_cap != ob)
285                 start_cap = mesh_get_derived_final(scene, amd->start_cap, CD_MASK_MESH);
286         if(amd->end_cap && amd->end_cap != ob)
287                 end_cap = mesh_get_derived_final(scene, amd->end_cap, CD_MASK_MESH);
288
289         MTC_Mat4One(offset);
290
291         src_mvert = cddm->getVertArray(dm);
292         maxVerts = cddm->getNumVerts(dm);
293
294         if(amd->offset_type & MOD_ARR_OFF_CONST)
295                 VecAddf(offset[3], offset[3], amd->offset);
296         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
297                 for(j = 0; j < 3; j++)
298                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
299                                         maxVerts, j);
300         }
301
302         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
303                 float obinv[4][4];
304                 float result_mat[4][4];
305
306                 if(ob)
307                         MTC_Mat4Invert(obinv, ob->obmat);
308                 else
309                         MTC_Mat4One(obinv);
310
311                 MTC_Mat4MulSerie(result_mat, offset,
312                                  obinv, amd->offset_ob->obmat,
313                                  NULL, NULL, NULL, NULL, NULL);
314                 MTC_Mat4CpyMat4(offset, result_mat);
315         }
316
317         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
318                 Curve *cu = amd->curve_ob->data;
319                 if(cu) {
320                         float tmp_mat[3][3];
321                         float scale;
322                         
323                         object_to_mat3(amd->curve_ob, tmp_mat);
324                         scale = Mat3ToScalef(tmp_mat);
325                                 
326                         if(!cu->path) {
327                                 cu->flag |= CU_PATH; // needed for path & bevlist
328                                 makeDispListCurveTypes(scene, amd->curve_ob, 0);
329                         }
330                         if(cu->path)
331                                 length = scale*cu->path->totdist;
332                 }
333         }
334
335         /* calculate the maximum number of copies which will fit within the
336         prescribed length */
337         if(amd->fit_type == MOD_ARR_FITLENGTH
338                   || amd->fit_type == MOD_ARR_FITCURVE)
339         {
340                 float dist = sqrt(MTC_dot3Float(offset[3], offset[3]));
341
342                 if(dist > 1e-6f)
343                         /* this gives length = first copy start to last copy end
344                         add a tiny offset for floating point rounding errors */
345                         count = (length + 1e-6f) / dist;
346                 else
347                         /* if the offset has no translation, just make one copy */
348                         count = 1;
349         }
350
351         if(count < 1)
352                 count = 1;
353
354         /* allocate memory for count duplicates (including original) plus
355                   * start and end caps
356         */
357         finalVerts = dm->getNumVerts(dm) * count;
358         finalEdges = dm->getNumEdges(dm) * count;
359         finalFaces = dm->getNumFaces(dm) * count;
360         if(start_cap) {
361                 finalVerts += start_cap->getNumVerts(start_cap);
362                 finalEdges += start_cap->getNumEdges(start_cap);
363                 finalFaces += start_cap->getNumFaces(start_cap);
364         }
365         if(end_cap) {
366                 finalVerts += end_cap->getNumVerts(end_cap);
367                 finalEdges += end_cap->getNumEdges(end_cap);
368                 finalFaces += end_cap->getNumFaces(end_cap);
369         }
370
371         /* calculate the offset matrix of the final copy (for merging) */ 
372         MTC_Mat4One(final_offset);
373
374         for(j=0; j < count - 1; j++) {
375                 MTC_Mat4MulMat4(tmp_mat, final_offset, offset);
376                 MTC_Mat4CpyMat4(final_offset, tmp_mat);
377         }
378
379         cddm->needsFree = 1;
380         cddm->release(cddm);
381         
382         BMO_Init_Op(&weldop, "weldverts");
383         BMO_InitOpf(em->bm, &op, "dupe geom=%avef");
384         oldop = op;
385         for (j=0; j < count; j++) {
386                 BMVert *v, *v2;
387                 BMOpSlot *s1;
388                 BMOpSlot *s2;
389
390                 BMO_InitOpf(em->bm, &op, "dupe geom=%s", &oldop, j==0 ? "geom" : "newout");
391                 BMO_Exec_Op(em->bm, &op);
392
393                 s1 = BMO_GetSlot(&op, "geom");
394                 s2 = BMO_GetSlot(&op, "newout");
395
396                 BMO_CallOpf(em->bm, "transform mat=%m4 verts=%s", offset, &op, "newout");
397
398                 #define _E(s, i) ((BMVert**)(s)->data.buf)[i]
399
400                 /*calculate merge mapping*/
401                 if (j == 0) {
402                         BMOperator findop;
403                         BMOIter oiter;
404                         BMIter iter;
405                         BMVert *v, *v2;
406                         BMHeader *h;
407
408                         BMO_InitOpf(em->bm, &findop, 
409                                 "finddoubles verts=%av dist=%f keepverts=%s", 
410                                 amd->merge_dist, &op, "geom");
411
412                         i = 0;
413                         BMO_ITER(h, &oiter, em->bm, &op, "geom", BM_ALL) {
414                                 BMINDEX_SET(h, i);
415                                 i++;
416                         }
417
418                         BMO_ITER(h, &oiter, em->bm, &op, "newout", BM_ALL) {
419                                 BMINDEX_SET(h, i);
420                                 i++;
421                         }
422
423                         BMO_Exec_Op(em->bm, &findop);
424
425                         indexLen = i;
426                         indexMap = MEM_callocN(sizeof(int)*indexLen, "indexMap");
427
428                         /*element type argument doesn't do anything here*/
429                         BMO_ITER(v, &oiter, em->bm, &findop, "targetmapout", 0) {
430                                 v2 = BMO_IterMapValp(&oiter);
431
432                                 /*make sure merge pairs are duplicate-to-duplicate*/
433                                 /*if (BMINDEX_GET(v) >= s1->len && BMINDEX_GET(v2) >= s1->len) 
434                                         continue;
435                                 else if (BMINDEX_GET(v) < s1->len && BMINDEX_GET(v2) < s1->len) 
436                                         continue;*/
437
438                                 indexMap[BMINDEX_GET(v)] = BMINDEX_GET(v2)+1;
439                         }
440
441                         BMO_Finish_Op(em->bm, &findop);
442                 } 
443
444                 /*generate merge mappping using index map.  we do this by using the
445                   operator slots as lookup arrays.*/
446                 #define E(i) (i) < s1->len ? _E(s1, i) : _E(s2, (i)-s1->len)
447
448                 for (i=0; i<indexLen; i++) {
449                         if (!indexMap[i]) continue;
450
451                         v = E(i);
452                         v2 = E(indexMap[i]-1);
453
454                         BMO_Insert_MapPointer(em->bm, &weldop, "targetmap", v, v2);
455                 }
456
457                 #undef E
458                 #undef _E
459
460                 BMO_Finish_Op(em->bm, &oldop);
461                 oldop = op;
462         }
463
464         if (j > 0) BMO_Finish_Op(em->bm, &op);
465
466         BMO_Exec_Op(em->bm, &weldop);
467         BMO_Finish_Op(em->bm, &weldop);
468
469         //BMO_CallOpf(em->bm, "removedoubles verts=%av dist=%f", amd->merge_dist);
470
471         BMEdit_RecalcTesselation(em);
472         cddm = CDDM_from_BMEditMesh(em, NULL);
473
474         BMEdit_Free(em);
475         MEM_freeN(indexMap);
476
477         return cddm;
478 }
479
480 DerivedMesh *arrayModifier_applyModifier(ModifierData *md, Object *ob, 
481                                          DerivedMesh *derivedData,
482                                          int useRenderParams, int isFinalCalc)
483 {
484         DerivedMesh *result;
485         ArrayModifierData *amd = (ArrayModifierData*) md;
486
487         result = arrayModifier_doArray(amd, md->scene, ob, derivedData, 0);
488
489         //if(result != derivedData)
490         //      CDDM_calc_normals(result);
491
492         return result;
493 }
494
495 DerivedMesh *arrayModifier_applyModifierEM(ModifierData *md, Object *ob,
496                                            BMEditMesh *editData, 
497                                            DerivedMesh *derivedData)
498 {
499         return arrayModifier_applyModifier(md, ob, derivedData, 0, 1);
500 }
501
502 /* Mirror */
503
504 DerivedMesh *doMirrorOnAxis(MirrorModifierData *mmd,
505                 Object *ob,
506                 DerivedMesh *dm,
507                 int initFlags,
508                 int axis)
509 {
510         int i;
511         float tolerance = mmd->tolerance;
512         DerivedMesh *result, *cddm;
513         BMEditMesh *em;
514         BMesh *bm;
515         int numVerts, numEdges, numFaces;
516         int maxVerts = dm->getNumVerts(dm);
517         int maxEdges = dm->getNumEdges(dm);
518         int maxFaces = dm->getNumTessFaces(dm);
519         int vector_size=0, j, a, b;
520         bDeformGroup *def, *defb;
521         bDeformGroup **vector_def = NULL;
522         int (*indexMap)[2];
523         float mtx[4][4], imtx[4][4];
524
525         cddm = CDDM_copy(dm);
526         em = CDDM_To_BMesh(dm, NULL);
527
528         cddm->needsFree = 1;
529         cddm->release(cddm);
530         
531         /*convienence variable*/
532         bm = em->bm;
533
534         numVerts = numEdges = numFaces = 0;
535         indexMap = MEM_mallocN(sizeof(*indexMap) * maxVerts, "indexmap");
536         result = CDDM_from_template(dm, maxVerts * 2, maxEdges * 2, maxFaces * 2, 0, 0);
537
538         if (mmd->flag & MOD_MIR_VGROUP) {
539                 /* calculate the number of deformedGroups */
540                 for(vector_size = 0, def = ob->defbase.first; def;
541                     def = def->next, vector_size++);
542
543                 /* load the deformedGroups for fast access */
544                 vector_def =
545                     (bDeformGroup **)MEM_mallocN(sizeof(bDeformGroup*) * vector_size,
546                                                  "group_index");
547                 for(a = 0, def = ob->defbase.first; def; def = def->next, a++) {
548                         vector_def[a] = def;
549                 }
550         }
551
552         if (mmd->mirror_ob) {
553                 float obinv[4][4];
554                 
555                 Mat4Invert(obinv, mmd->mirror_ob->obmat);
556                 Mat4MulMat4(mtx, ob->obmat, obinv);
557                 Mat4Invert(imtx, mtx);
558         }
559
560
561
562         BMEdit_RecalcTesselation(em);
563         result = CDDM_from_BMEditMesh(em, NULL);
564
565         BMEdit_Free(em);
566
567         return result;
568 }