d52f624a91bfbc6aa70ad9cf829bfac783bf616f
[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 static DerivedMesh *arrayModifier_doArray(ArrayModifierData *amd,
224                                           Scene *scene, Object *ob, DerivedMesh *dm,
225                                           int initFlags)
226 {
227         DerivedMesh *cddm = CDDM_copy(dm);
228         BMEditMesh *em = CDDM_To_BMesh(cddm, NULL);
229         BMOperator op, oldop;
230         int i, j;
231         /* offset matrix */
232         float offset[4][4];
233         float final_offset[4][4];
234         float tmp_mat[4][4];
235         float length = amd->length;
236         int count = amd->count;
237         int numVerts, numEdges, numFaces;
238         int maxVerts, maxEdges, maxFaces;
239         int finalVerts, finalEdges, finalFaces;
240         DerivedMesh *result, *start_cap = NULL, *end_cap = NULL;
241         MVert *src_mvert;
242
243         /* need to avoid infinite recursion here */
244         if(amd->start_cap && amd->start_cap != ob)
245                 start_cap = mesh_get_derived_final(scene, amd->start_cap, CD_MASK_MESH);
246         if(amd->end_cap && amd->end_cap != ob)
247                 end_cap = mesh_get_derived_final(scene, amd->end_cap, CD_MASK_MESH);
248
249         MTC_Mat4One(offset);
250
251         src_mvert = cddm->getVertArray(dm);
252         maxVerts = cddm->getNumVerts(dm);
253
254         if(amd->offset_type & MOD_ARR_OFF_CONST)
255                 VecAddf(offset[3], offset[3], amd->offset);
256         if(amd->offset_type & MOD_ARR_OFF_RELATIVE) {
257                 for(j = 0; j < 3; j++)
258                         offset[3][j] += amd->scale[j] * vertarray_size(src_mvert,
259                                         maxVerts, j);
260         }
261
262         if((amd->offset_type & MOD_ARR_OFF_OBJ) && (amd->offset_ob)) {
263                 float obinv[4][4];
264                 float result_mat[4][4];
265
266                 if(ob)
267                         MTC_Mat4Invert(obinv, ob->obmat);
268                 else
269                         MTC_Mat4One(obinv);
270
271                 MTC_Mat4MulSerie(result_mat, offset,
272                                  obinv, amd->offset_ob->obmat,
273                                  NULL, NULL, NULL, NULL, NULL);
274                 MTC_Mat4CpyMat4(offset, result_mat);
275         }
276
277         if(amd->fit_type == MOD_ARR_FITCURVE && amd->curve_ob) {
278                 Curve *cu = amd->curve_ob->data;
279                 if(cu) {
280                         float tmp_mat[3][3];
281                         float scale;
282                         
283                         object_to_mat3(amd->curve_ob, tmp_mat);
284                         scale = Mat3ToScalef(tmp_mat);
285                                 
286                         if(!cu->path) {
287                                 cu->flag |= CU_PATH; // needed for path & bevlist
288                                 makeDispListCurveTypes(scene, amd->curve_ob, 0);
289                         }
290                         if(cu->path)
291                                 length = scale*cu->path->totdist;
292                 }
293         }
294
295         /* calculate the maximum number of copies which will fit within the
296         prescribed length */
297         if(amd->fit_type == MOD_ARR_FITLENGTH
298                   || amd->fit_type == MOD_ARR_FITCURVE)
299         {
300                 float dist = sqrt(MTC_dot3Float(offset[3], offset[3]));
301
302                 if(dist > 1e-6f)
303                         /* this gives length = first copy start to last copy end
304                         add a tiny offset for floating point rounding errors */
305                         count = (length + 1e-6f) / dist;
306                 else
307                         /* if the offset has no translation, just make one copy */
308                         count = 1;
309         }
310
311         if(count < 1)
312                 count = 1;
313
314         /* allocate memory for count duplicates (including original) plus
315                   * start and end caps
316         */
317         finalVerts = dm->getNumVerts(dm) * count;
318         finalEdges = dm->getNumEdges(dm) * count;
319         finalFaces = dm->getNumTessFaces(dm) * count;
320         if(start_cap) {
321                 finalVerts += start_cap->getNumVerts(start_cap);
322                 finalEdges += start_cap->getNumEdges(start_cap);
323                 finalFaces += start_cap->getNumTessFaces(start_cap);
324         }
325         if(end_cap) {
326                 finalVerts += end_cap->getNumVerts(end_cap);
327                 finalEdges += end_cap->getNumEdges(end_cap);
328                 finalFaces += end_cap->getNumTessFaces(end_cap);
329         }
330
331         /* calculate the offset matrix of the final copy (for merging) */ 
332         MTC_Mat4One(final_offset);
333
334         for(j=0; j < count - 1; j++) {
335                 MTC_Mat4MulMat4(tmp_mat, final_offset, offset);
336                 MTC_Mat4CpyMat4(final_offset, tmp_mat);
337         }
338
339
340         cddm->needsFree = 1;
341         cddm->release(cddm);
342         
343         BMO_InitOpf(em->bm, &op, "dupe geom=%avef");
344         oldop = op;
345         for (j=0; j < count; j++) {
346                 BMO_InitOpf(em->bm, &op, "dupe geom=%s", &oldop, j==0 ? "geom" : "newout");
347                 BMO_Exec_Op(em->bm, &op);
348
349                 BMO_Finish_Op(em->bm, &oldop);
350                 oldop = op;
351
352                 BMO_CallOpf(em->bm, "transform mat=%m4 verts=%s", offset, &op, "newout");
353
354         }
355
356         if (j > 0) BMO_Finish_Op(em->bm, &op);
357
358         BMO_CallOpf(em->bm, "removedoubles verts=%av dist=%f", amd->merge_dist);
359
360         BMEdit_RecalcTesselation(em);
361         cddm = CDDM_from_BMEditMesh(em, NULL);
362
363         BMEdit_Free(em);
364
365         return cddm;
366 }
367
368 DerivedMesh *arrayModifier_applyModifier(ModifierData *md, Object *ob, 
369                                          DerivedMesh *derivedData,
370                                          int useRenderParams, int isFinalCalc)
371 {
372         DerivedMesh *result;
373         ArrayModifierData *amd = (ArrayModifierData*) md;
374
375         result = arrayModifier_doArray(amd, md->scene, ob, derivedData, 0);
376
377         //if(result != derivedData)
378         //      CDDM_calc_normals(result);
379
380         return result;
381 }
382
383 DerivedMesh *arrayModifier_applyModifierEM(ModifierData *md, Object *ob,
384                                            BMEditMesh *editData, 
385                                            DerivedMesh *derivedData)
386 {
387         return arrayModifier_applyModifier(md, ob, derivedData, 0, 1);
388 }