svn merge -r39890:39951 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender-staging.git] / source / blender / modifiers / intern / MOD_explode.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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 */
32
33 /** \file blender/modifiers/intern/MOD_explode.c
34  *  \ingroup modifiers
35  */
36
37
38 #include "DNA_meshdata_types.h"
39 #include "DNA_scene_types.h"
40
41 #include "BLI_utildefines.h"
42 #include "BLI_kdtree.h"
43 #include "BLI_rand.h"
44 #include "BLI_math.h"
45 #include "BLI_edgehash.h"
46
47 #include "BKE_cdderivedmesh.h"
48 #include "BKE_deform.h"
49 #include "BKE_lattice.h"
50 #include "BKE_mesh.h"
51 #include "BKE_modifier.h"
52 #include "BKE_object.h"
53 #include "BKE_particle.h"
54 #include "BKE_scene.h"
55
56
57 #include "MEM_guardedalloc.h"
58
59 #include "MOD_util.h"
60
61 static void initData(ModifierData *md)
62 {
63         ExplodeModifierData *emd= (ExplodeModifierData*) md;
64
65         emd->facepa= NULL;
66         emd->flag |= eExplodeFlag_Unborn+eExplodeFlag_Alive+eExplodeFlag_Dead;
67 }
68 static void freeData(ModifierData *md)
69 {
70         ExplodeModifierData *emd= (ExplodeModifierData*) md;
71         
72         if(emd->facepa) MEM_freeN(emd->facepa);
73 }
74 static void copyData(ModifierData *md, ModifierData *target)
75 {
76         ExplodeModifierData *emd= (ExplodeModifierData*) md;
77         ExplodeModifierData *temd= (ExplodeModifierData*) target;
78
79         temd->facepa = NULL;
80         temd->flag = emd->flag;
81         temd->protect = emd->protect;
82         temd->vgroup = emd->vgroup;
83 }
84 static int dependsOnTime(ModifierData *UNUSED(md)) 
85 {
86         return 1;
87 }
88 static CustomDataMask requiredDataMask(Object *UNUSED(ob), ModifierData *md)
89 {
90         ExplodeModifierData *emd= (ExplodeModifierData*) md;
91         CustomDataMask dataMask = 0;
92
93         if(emd->vgroup)
94                 dataMask |= CD_MASK_MDEFORMVERT;
95
96         return dataMask;
97 }
98
99 static void createFacepa(ExplodeModifierData *emd,
100                                                 ParticleSystemModifierData *psmd,
101                                                 DerivedMesh *dm)
102 {
103         ParticleSystem *psys=psmd->psys;
104         MFace *fa=NULL, *mface=NULL;
105         MVert *mvert = NULL;
106         ParticleData *pa;
107         KDTree *tree;
108         float center[3], co[3];
109         int *facepa=NULL,*vertpa=NULL,totvert=0,totface=0,totpart=0;
110         int i,p,v1,v2,v3,v4=0;
111
112         mvert = dm->getVertArray(dm);
113         mface = dm->getTessFaceArray(dm);
114         totface= dm->getNumTessFaces(dm);
115         totvert= dm->getNumVerts(dm);
116         totpart= psmd->psys->totpart;
117
118         BLI_srandom(psys->seed);
119
120         if(emd->facepa)
121                 MEM_freeN(emd->facepa);
122
123         facepa = emd->facepa = MEM_callocN(sizeof(int)*totface, "explode_facepa");
124
125         vertpa = MEM_callocN(sizeof(int)*totvert, "explode_vertpa");
126
127         /* initialize all faces & verts to no particle */
128         for(i=0; i<totface; i++)
129                 facepa[i]=totpart;
130
131         for (i=0; i<totvert; i++)
132                 vertpa[i]=totpart;
133
134         /* set protected verts */
135         if(emd->vgroup){
136                 MDeformVert *dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
137                 if(dvert){
138                         const int defgrp_index= emd->vgroup-1;
139                         for(i=0; i<totvert; i++, dvert++){
140                                 float val = BLI_frand();
141                                 val = (1.0f-emd->protect)*val + emd->protect*0.5f;
142                                 if(val < defvert_find_weight(dvert, defgrp_index))
143                                         vertpa[i] = -1;
144                         }
145                 }
146         }
147
148         /* make tree of emitter locations */
149         tree=BLI_kdtree_new(totpart);
150         for(p=0,pa=psys->particles; p<totpart; p++,pa++){
151                 psys_particle_on_emitter(psmd,psys->part->from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,co,NULL,NULL,NULL,NULL,NULL);
152                 BLI_kdtree_insert(tree, p, co, NULL);
153         }
154         BLI_kdtree_balance(tree);
155
156         /* set face-particle-indexes to nearest particle to face center */
157         for(i=0,fa=mface; i<totface; i++,fa++){
158                 add_v3_v3v3(center,mvert[fa->v1].co,mvert[fa->v2].co);
159                 add_v3_v3(center, mvert[fa->v3].co);
160                 if(fa->v4){
161                         add_v3_v3(center, mvert[fa->v4].co);
162                         mul_v3_fl(center,0.25);
163                 }
164                 else
165                         mul_v3_fl(center,0.3333f);
166
167                 p= BLI_kdtree_find_nearest(tree,center,NULL,NULL);
168
169                 v1=vertpa[fa->v1];
170                 v2=vertpa[fa->v2];
171                 v3=vertpa[fa->v3];
172                 if(fa->v4)
173                         v4=vertpa[fa->v4];
174
175                 if(v1>=0 && v2>=0 && v3>=0 && (fa->v4==0 || v4>=0))
176                         facepa[i]=p;
177
178                 if(v1>=0) vertpa[fa->v1]=p;
179                 if(v2>=0) vertpa[fa->v2]=p;
180                 if(v3>=0) vertpa[fa->v3]=p;
181                 if(fa->v4 && v4>=0) vertpa[fa->v4]=p;
182         }
183
184         if(vertpa) MEM_freeN(vertpa);
185         BLI_kdtree_free(tree);
186 }
187
188 static int edgecut_get(EdgeHash *edgehash, int v1, int v2)
189 {
190         return GET_INT_FROM_POINTER(BLI_edgehash_lookup(edgehash, v1, v2));
191 }
192
193  
194 static const short add_faces[24] = {
195         0,
196         0, 0, 2, 0, 1, 2, 2, 0, 2, 1,
197         2, 2, 2, 2, 3, 0, 0, 0, 1, 0,
198         1, 1, 2
199  };
200
201 static MFace *get_dface(DerivedMesh *dm, DerivedMesh *split, int cur, int i, MFace *mf)
202 {
203         MFace *df = CDDM_get_tessface(split, cur);
204         DM_copy_tessface_data(dm, split, i, cur, 1);
205         *df = *mf;
206         return df;
207 }
208
209 #define SET_VERTS(a, b, c, d) \
210                         v[0]=mf->v##a; uv[0]=a-1; \
211                         v[1]=mf->v##b; uv[1]=b-1; \
212                         v[2]=mf->v##c; uv[2]=c-1; \
213                         v[3]=mf->v##d; uv[3]=d-1;
214
215 #define GET_ES(v1, v2) edgecut_get(eh, v1, v2);
216 #define INT_UV(uvf, c0, c1) interp_v2_v2v2(uvf, mf->uv[c0], mf->uv[c1], 0.5f);
217
218 static void remap_faces_3_6_9_12(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3, int v4)
219 {
220         MFace *df1 = get_dface(dm, split, cur, i, mf);
221         MFace *df2 = get_dface(dm, split, cur+1, i, mf);
222         MFace *df3 = get_dface(dm, split, cur+2, i, mf);
223
224         facepa[cur] = vertpa[v1];
225         df1->v1 = v1;
226         df1->v2 = GET_ES(v1, v2)
227         df1->v3 = GET_ES(v2, v3)
228         df1->v4 = v3;
229         df1->flag |= ME_FACE_SEL;
230
231         facepa[cur+1] = vertpa[v2];
232         df2->v1 = GET_ES(v1, v2)
233         df2->v2 = v2;
234         df2->v3 = GET_ES(v2, v3)
235         df2->v4 = 0;
236         df2->flag &= ~ME_FACE_SEL;
237
238         facepa[cur+2] = vertpa[v1];
239         df3->v1 = v1;
240         df3->v2 = v3;
241         df3->v3 = v4;
242         df3->v4 = 0;
243         df3->flag &= ~ME_FACE_SEL;
244 }
245
246 static void remap_uvs_3_6_9_12(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2, int c3)
247 {
248         MTFace *mf, *df1, *df2, *df3;
249         int l;
250
251         for(l=0; l<numlayer; l++) {
252                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
253                 df1 = mf+cur;
254                 df2 = df1 + 1;
255                 df3 = df1 + 2;
256                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
257                 mf += i;
258
259                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
260                 INT_UV(df1->uv[1], c0, c1)
261                 INT_UV(df1->uv[2], c1, c2)
262                 copy_v2_v2(df1->uv[3], mf->uv[c2]);
263
264                 INT_UV(df2->uv[0], c0, c1)
265                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
266                 INT_UV(df2->uv[2], c1, c2)
267
268                 copy_v2_v2(df3->uv[0], mf->uv[c0]);
269                 copy_v2_v2(df3->uv[1], mf->uv[c2]);
270                 copy_v2_v2(df3->uv[2], mf->uv[c3]);
271         }
272 }
273
274 static void remap_faces_5_10(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3, int v4)
275 {
276         MFace *df1 = get_dface(dm, split, cur, i, mf);
277         MFace *df2 = get_dface(dm, split, cur+1, i, mf);
278
279         facepa[cur] = vertpa[v1];
280         df1->v1 = v1;
281         df1->v2 = v2;
282         df1->v3 = GET_ES(v2, v3)
283         df1->v4 = GET_ES(v1, v4)
284         df1->flag |= ME_FACE_SEL;
285
286         facepa[cur+1] = vertpa[v3];
287         df2->v1 = GET_ES(v1, v4)
288         df2->v2 = GET_ES(v2, v3)
289         df2->v3 = v3;
290         df2->v4 = v4;
291         df2->flag |= ME_FACE_SEL;
292 }
293
294 static void remap_uvs_5_10(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2, int c3)
295 {
296         MTFace *mf, *df1, *df2;
297         int l;
298
299         for(l=0; l<numlayer; l++) {
300                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
301                 df1 = mf+cur;
302                 df2 = df1 + 1;
303                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
304                 mf += i;
305
306                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
307                 copy_v2_v2(df1->uv[1], mf->uv[c1]);
308                 INT_UV(df1->uv[2], c1, c2)
309                 INT_UV(df1->uv[3], c0, c3)
310
311                 INT_UV(df2->uv[0], c0, c3)
312                 INT_UV(df2->uv[1], c1, c2)
313                 copy_v2_v2(df2->uv[2], mf->uv[c2]);
314                 copy_v2_v2(df2->uv[3], mf->uv[c3]);
315
316         }
317 }
318
319 static void remap_faces_15(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3, int v4)
320 {
321         MFace *df1 = get_dface(dm, split, cur, i, mf);
322         MFace *df2 = get_dface(dm, split, cur+1, i, mf);
323         MFace *df3 = get_dface(dm, split, cur+2, i, mf);
324         MFace *df4 = get_dface(dm, split, cur+3, i, mf);
325
326         facepa[cur] = vertpa[v1];
327         df1->v1 = v1;
328         df1->v2 = GET_ES(v1, v2)
329         df1->v3 = GET_ES(v1, v3)
330         df1->v4 = GET_ES(v1, v4)
331         df1->flag |= ME_FACE_SEL;
332
333         facepa[cur+1] = vertpa[v2];
334         df2->v1 = GET_ES(v1, v2)
335         df2->v2 = v2;
336         df2->v3 = GET_ES(v2, v3)
337         df2->v4 = GET_ES(v1, v3)
338         df2->flag |= ME_FACE_SEL;
339
340         facepa[cur+2] = vertpa[v3];
341         df3->v1 = GET_ES(v1, v3)
342         df3->v2 = GET_ES(v2, v3)
343         df3->v3 = v3;
344         df3->v4 = GET_ES(v3, v4)
345         df3->flag |= ME_FACE_SEL;
346
347         facepa[cur+3] = vertpa[v4];
348         df4->v1 = GET_ES(v1, v4)
349         df4->v2 = GET_ES(v1, v3)
350         df4->v3 = GET_ES(v3, v4)
351         df4->v4 = v4;
352         df4->flag |= ME_FACE_SEL;
353 }
354
355 static void remap_uvs_15(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2, int c3)
356 {
357         MTFace *mf, *df1, *df2, *df3, *df4;
358         int l;
359
360         for(l=0; l<numlayer; l++) {
361                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
362                 df1 = mf+cur;
363                 df2 = df1 + 1;
364                 df3 = df1 + 2;
365                 df4 = df1 + 3;
366                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
367                 mf += i;
368
369                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
370                 INT_UV(df1->uv[1], c0, c1)
371                 INT_UV(df1->uv[2], c0, c2)
372                 INT_UV(df1->uv[3], c0, c3)
373
374                 INT_UV(df2->uv[0], c0, c1)
375                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
376                 INT_UV(df2->uv[2], c1, c2)
377                 INT_UV(df2->uv[3], c0, c2)
378
379                 INT_UV(df3->uv[0], c0, c2)
380                 INT_UV(df3->uv[1], c1, c2)
381                 copy_v2_v2(df3->uv[2], mf->uv[c2]);
382                 INT_UV(df3->uv[3], c2, c3)
383
384                 INT_UV(df4->uv[0], c0, c3)
385                 INT_UV(df4->uv[1], c0, c2)
386                 INT_UV(df4->uv[2], c2, c3)
387                 copy_v2_v2(df4->uv[3], mf->uv[c3]);
388         }
389 }
390
391 static void remap_faces_7_11_13_14(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3, int v4)
392 {
393         MFace *df1 = get_dface(dm, split, cur, i, mf);
394         MFace *df2 = get_dface(dm, split, cur+1, i, mf);
395         MFace *df3 = get_dface(dm, split, cur+2, i, mf);
396
397         facepa[cur] = vertpa[v1];
398         df1->v1 = v1;
399         df1->v2 = GET_ES(v1, v2)
400         df1->v3 = GET_ES(v2, v3)
401         df1->v4 = GET_ES(v1, v4)
402         df1->flag |= ME_FACE_SEL;
403
404         facepa[cur+1] = vertpa[v2];
405         df2->v1 = GET_ES(v1, v2)
406         df2->v2 = v2;
407         df2->v3 = GET_ES(v2, v3)
408         df2->v4 = 0;
409         df2->flag &= ~ME_FACE_SEL;
410
411         facepa[cur+2] = vertpa[v4];
412         df3->v1 = GET_ES(v1, v4)
413         df3->v2 = GET_ES(v2, v3)
414         df3->v3 = v3;
415         df3->v4 = v4;
416         df3->flag |= ME_FACE_SEL;
417 }
418
419 static void remap_uvs_7_11_13_14(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2, int c3)
420 {
421         MTFace *mf, *df1, *df2, *df3;
422         int l;
423
424         for(l=0; l<numlayer; l++) {
425                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
426                 df1 = mf+cur;
427                 df2 = df1 + 1;
428                 df3 = df1 + 2;
429                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
430                 mf += i;
431
432                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
433                 INT_UV(df1->uv[1], c0, c1)
434                 INT_UV(df1->uv[2], c1, c2)
435                 INT_UV(df1->uv[3], c0, c3)
436
437                 INT_UV(df2->uv[0], c0, c1)
438                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
439                 INT_UV(df2->uv[2], c1, c2)
440
441                 INT_UV(df3->uv[0], c0, c3)
442                 INT_UV(df3->uv[1], c1, c2)
443                 copy_v2_v2(df3->uv[2], mf->uv[c2]);
444                 copy_v2_v2(df3->uv[3], mf->uv[c3]);
445         }
446 }
447
448 static void remap_faces_19_21_22(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3)
449 {
450         MFace *df1 = get_dface(dm, split, cur, i, mf);
451         MFace *df2 = get_dface(dm, split, cur+1, i, mf);
452
453         facepa[cur] = vertpa[v1];
454         df1->v1 = v1;
455         df1->v2 = GET_ES(v1, v2)
456         df1->v3 = GET_ES(v1, v3)
457         df1->v4 = 0;
458         df1->flag &= ~ME_FACE_SEL;
459
460         facepa[cur+1] = vertpa[v2];
461         df2->v1 = GET_ES(v1, v2)
462         df2->v2 = v2;
463         df2->v3 = v3;
464         df2->v4 = GET_ES(v1, v3)
465         df2->flag |= ME_FACE_SEL;
466 }
467
468 static void remap_uvs_19_21_22(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2)
469 {
470         MTFace *mf, *df1, *df2;
471         int l;
472
473         for(l=0; l<numlayer; l++) {
474                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
475                 df1 = mf+cur;
476                 df2 = df1 + 1;
477                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
478                 mf += i;
479
480                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
481                 INT_UV(df1->uv[1], c0, c1)
482                 INT_UV(df1->uv[2], c0, c2)
483
484                 INT_UV(df2->uv[0], c0, c1)
485                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
486                 copy_v2_v2(df2->uv[2], mf->uv[c2]);
487                 INT_UV(df2->uv[3], c0, c2)
488         }
489 }
490
491 static void remap_faces_23(DerivedMesh *dm, DerivedMesh *split, MFace *mf, int *facepa, int *vertpa, int i, EdgeHash *eh, int cur, int v1, int v2, int v3)
492 {
493         MFace *df1 = get_dface(dm, split, cur, i, mf);
494         MFace *df2 = get_dface(dm, split, cur+1, i, mf);
495         MFace *df3 = get_dface(dm, split, cur+2, i, mf);
496
497         facepa[cur] = vertpa[v1];
498         df1->v1 = v1;
499         df1->v2 = GET_ES(v1, v2)
500         df1->v3 = GET_ES(v2, v3)
501         df1->v4 = GET_ES(v1, v3)
502         df1->flag |= ME_FACE_SEL;
503
504         facepa[cur+1] = vertpa[v2];
505         df2->v1 = GET_ES(v1, v2)
506         df2->v2 = v2;
507         df2->v3 = GET_ES(v2, v3)
508         df2->v4 = 0;
509         df2->flag &= ~ME_FACE_SEL;
510
511         facepa[cur+2] = vertpa[v3];
512         df3->v1 = GET_ES(v1, v3)
513         df3->v2 = GET_ES(v2, v3)
514         df3->v3 = v3;
515         df3->v4 = 0;
516         df3->flag &= ~ME_FACE_SEL;
517 }
518
519 static void remap_uvs_23(DerivedMesh *dm, DerivedMesh *split, int numlayer, int i, int cur, int c0, int c1, int c2)
520 {
521         MTFace *mf, *df1, *df2;
522         int l;
523
524         for(l=0; l<numlayer; l++) {
525                 mf = CustomData_get_layer_n(&split->faceData, CD_MTFACE, l);
526                 df1 = mf+cur;
527                 df2 = df1 + 1;
528                 mf = CustomData_get_layer_n(&dm->faceData, CD_MTFACE, l);
529                 mf += i;
530
531                 copy_v2_v2(df1->uv[0], mf->uv[c0]);
532                 INT_UV(df1->uv[1], c0, c1)
533                 INT_UV(df1->uv[2], c1, c2)
534                 INT_UV(df1->uv[3], c0, c2)
535
536                 INT_UV(df2->uv[0], c0, c1)
537                 copy_v2_v2(df2->uv[1], mf->uv[c1]);
538                 INT_UV(df2->uv[2], c1, c2)
539
540                 INT_UV(df2->uv[0], c0, c2)
541                 INT_UV(df2->uv[1], c1, c2)
542                 copy_v2_v2(df2->uv[2], mf->uv[c2]);
543         }
544 }
545
546 static DerivedMesh * cutEdges(ExplodeModifierData *emd, DerivedMesh *dm){
547         DerivedMesh *splitdm;
548         MFace *mf=NULL,*df1=NULL;
549         MFace *mface=dm->getTessFaceArray(dm);
550         MVert *dupve, *mv;
551         EdgeHash *edgehash;
552         EdgeHashIterator *ehi;
553         int totvert=dm->getNumVerts(dm);
554         int totface=dm->getNumTessFaces(dm);
555
556         int *facesplit = MEM_callocN(sizeof(int)*totface,"explode_facesplit");
557         int *vertpa = MEM_callocN(sizeof(int)*totvert,"explode_vertpa2");
558         int *facepa = emd->facepa;
559         int *fs, totesplit=0,totfsplit=0,curdupface=0;
560         int i,j,v1,v2,v3,v4,esplit, v[4], uv[4];
561         int numlayer;
562
563         edgehash= BLI_edgehash_new();
564
565         /* recreate vertpa from facepa calculation */
566         for (i=0,mf=mface; i<totface; i++,mf++) {
567                 vertpa[mf->v1]=facepa[i];
568                 vertpa[mf->v2]=facepa[i];
569                 vertpa[mf->v3]=facepa[i];
570                 if(mf->v4)
571                         vertpa[mf->v4]=facepa[i];
572         }
573
574         /* mark edges for splitting and how to split faces */
575         for (i=0,mf=mface,fs=facesplit; i<totface; i++,mf++,fs++) {
576                 v1=vertpa[mf->v1];
577                 v2=vertpa[mf->v2];
578                 v3=vertpa[mf->v3];
579
580                 if(v1!=v2){
581                         BLI_edgehash_insert(edgehash, mf->v1, mf->v2, NULL);
582                         (*fs) |= 1;
583                 }
584
585                 if(v2!=v3){
586                         BLI_edgehash_insert(edgehash, mf->v2, mf->v3, NULL);
587                         (*fs) |= 2;
588                 }
589
590                 if(mf->v4){
591                         v4=vertpa[mf->v4];
592
593                         if(v3!=v4){
594                                 BLI_edgehash_insert(edgehash, mf->v3, mf->v4, NULL);
595                                 (*fs) |= 4;
596                         }
597
598                         if(v1!=v4){
599                                 BLI_edgehash_insert(edgehash, mf->v1, mf->v4, NULL);
600                                 (*fs) |= 8;
601                         }
602
603                         /* mark center vertex as a fake edge split */
604                         if(*fs == 15)
605                                 BLI_edgehash_insert(edgehash, mf->v1, mf->v3, NULL);
606                 }
607                 else {
608                         (*fs) |= 16; /* mark face as tri */
609
610                         if(v1!=v3){
611                                 BLI_edgehash_insert(edgehash, mf->v1, mf->v3, NULL);
612                                 (*fs) |= 4;
613                         }
614                 }
615         }
616
617         /* count splits & create indexes for new verts */
618         ehi= BLI_edgehashIterator_new(edgehash);
619         totesplit=totvert;
620         for(; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
621                 BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(totesplit));
622                 totesplit++;
623         }
624         BLI_edgehashIterator_free(ehi);
625
626         /* count new faces due to splitting */
627         for(i=0,fs=facesplit; i<totface; i++,fs++)
628                 totfsplit += add_faces[*fs];
629         
630         splitdm= CDDM_from_template(dm, totesplit, 0, totface+totfsplit, 0, 0);
631         numlayer = CustomData_number_of_layers(&splitdm->faceData, CD_MTFACE);
632
633         /* copy new faces & verts (is it really this painful with custom data??) */
634         for(i=0; i<totvert; i++){
635                 MVert source;
636                 MVert *dest;
637                 dm->getVert(dm, i, &source);
638                 dest = CDDM_get_vert(splitdm, i);
639
640                 DM_copy_vert_data(dm, splitdm, i, i, 1);
641                 *dest = source;
642         }
643
644         /* override original facepa (original pointer is saved in caller function) */
645         facepa= MEM_callocN(sizeof(int)*(totface+totfsplit),"explode_facepa");
646         //memcpy(facepa,emd->facepa,totface*sizeof(int));
647         emd->facepa=facepa;
648
649         /* create new verts */
650         ehi= BLI_edgehashIterator_new(edgehash);
651         for(; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
652                 BLI_edgehashIterator_getKey(ehi, &i, &j);
653                 esplit= GET_INT_FROM_POINTER(BLI_edgehashIterator_getValue(ehi));
654                 mv=CDDM_get_vert(splitdm,j);
655                 dupve=CDDM_get_vert(splitdm,esplit);
656
657                 DM_copy_vert_data(splitdm,splitdm,j,esplit,1);
658
659                 *dupve=*mv;
660
661                 mv=CDDM_get_vert(splitdm,i);
662
663                 add_v3_v3(dupve->co, mv->co);
664                 mul_v3_fl(dupve->co, 0.5f);
665         }
666         BLI_edgehashIterator_free(ehi);
667
668         /* create new faces */
669         curdupface=0;//=totface;
670         //curdupin=totesplit;
671         for(i=0,fs=facesplit; i<totface; i++,fs++){
672                 mf = dm->getTessFaceData(dm, i, CD_MFACE);
673
674                 switch(*fs) {
675                 case 3:
676                 case 10:
677                 case 11:
678                 case 15:
679                         SET_VERTS(1, 2, 3, 4)
680                         break;
681                 case 5:
682                 case 6:
683                 case 7:
684                         SET_VERTS(2, 3, 4, 1)
685                         break;
686                 case 9:
687                 case 13:
688                         SET_VERTS(4, 1, 2, 3)
689                         break;
690                 case 12:
691                 case 14:
692                         SET_VERTS(3, 4, 1, 2)
693                         break;
694                 case 21:
695                 case 23:
696                         SET_VERTS(1, 2, 3, 4)
697                         break;
698                 case 19:
699                         SET_VERTS(2, 3, 1, 4)
700                         break;
701                 case 22:
702                         SET_VERTS(3, 1, 2, 4)
703                         break;
704                 }
705
706                 switch(*fs) {
707                 case 3:
708                 case 6:
709                 case 9:
710                 case 12:
711                         remap_faces_3_6_9_12(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
712                         if(numlayer)
713                                 remap_uvs_3_6_9_12(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
714                         break;
715                 case 5:
716                 case 10:
717                         remap_faces_5_10(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
718                         if(numlayer)
719                                 remap_uvs_5_10(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
720                         break;
721                 case 15:
722                         remap_faces_15(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
723                         if(numlayer)
724                                 remap_uvs_15(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
725                         break;
726                 case 7:
727                 case 11:
728                 case 13:
729                 case 14:
730                         remap_faces_7_11_13_14(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2], v[3]);
731                         if(numlayer)
732                                 remap_uvs_7_11_13_14(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2], uv[3]);
733                         break;
734                 case 19:
735                 case 21:
736                 case 22:
737                         remap_faces_19_21_22(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2]);
738                         if(numlayer)
739                                 remap_uvs_19_21_22(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2]);
740                         break;
741                 case 23:
742                         remap_faces_23(dm, splitdm, mf, facepa, vertpa, i, edgehash, curdupface, v[0], v[1], v[2]);
743                         if(numlayer)
744                                 remap_uvs_23(dm, splitdm, numlayer, i, curdupface, uv[0], uv[1], uv[2]);
745                         break;
746                 case 0:
747                 case 16:
748                         df1 = get_dface(dm, splitdm, curdupface, i, mf);
749                         facepa[curdupface] = vertpa[mf->v1];
750
751                         if(df1->v4)
752                                 df1->flag |= ME_FACE_SEL;
753                         else
754                                 df1->flag &= ~ME_FACE_SEL;
755                         break;
756                 }
757
758                 curdupface += add_faces[*fs]+1;
759         }
760
761         for(i=0; i<curdupface; i++) {
762                 mf = CDDM_get_tessface(splitdm, i);
763                 test_index_face(mf, &splitdm->faceData, i, (mf->flag & ME_FACE_SEL ? 4 : 3));
764         }
765
766         BLI_edgehash_free(edgehash, NULL);
767         MEM_freeN(facesplit);
768         MEM_freeN(vertpa);
769
770         dm = CDDM_copy(splitdm, 1); /*builds ngon faces from tess (mface) faces*/
771         splitdm->needsFree = 1;
772         splitdm->release(splitdm);
773
774         return dm;
775 }
776 static DerivedMesh * explodeMesh(ExplodeModifierData *emd, 
777                 ParticleSystemModifierData *psmd, Scene *scene, Object *ob, 
778   DerivedMesh *to_explode)
779 {
780         DerivedMesh *explode, *dm=to_explode;
781         MFace *mf= NULL, *mface;
782         /* ParticleSettings *part=psmd->psys->part; */ /* UNUSED */
783         ParticleSimulationData sim= {NULL};
784         ParticleData *pa=NULL, *pars=psmd->psys->particles;
785         ParticleKey state, birth;
786         EdgeHash *vertpahash;
787         EdgeHashIterator *ehi;
788         float *vertco= NULL, imat[4][4];
789         float rot[4];
790         float cfra;
791         /* float timestep; */
792         int *facepa=emd->facepa;
793         int totdup=0,totvert=0,totface=0,totpart=0;
794         int i, j, v, mindex=0;
795         MTFace *mtface = NULL, *mtf;
796
797         totface= dm->getNumTessFaces(dm);
798         totvert= dm->getNumVerts(dm);
799         mface= dm->getTessFaceArray(dm);
800         totpart= psmd->psys->totpart;
801
802         sim.scene= scene;
803         sim.ob= ob;
804         sim.psys= psmd->psys;
805         sim.psmd= psmd;
806
807         /* timestep= psys_get_timestep(&sim); */
808
809         //if(part->flag & PART_GLOB_TIME)
810                 cfra= BKE_curframe(scene);
811         //else
812         //      cfra=bsystem_time(scene, ob,(float)scene->r.cfra,0.0);
813
814         /* hash table for vertice <-> particle relations */
815         vertpahash= BLI_edgehash_new();
816
817         for (i=0; i<totface; i++) {
818                 /* do mindex + totvert to ensure the vertex index to be the first
819                  * with BLI_edgehashIterator_getKey */
820                 if(facepa[i]==totpart || cfra < (pars+facepa[i])->time)
821                         mindex = totvert+totpart;
822                 else 
823                         mindex = totvert+facepa[i];
824
825                 mf= &mface[i];
826
827                 /* set face vertices to exist in particle group */
828                 BLI_edgehash_insert(vertpahash, mf->v1, mindex, NULL);
829                 BLI_edgehash_insert(vertpahash, mf->v2, mindex, NULL);
830                 BLI_edgehash_insert(vertpahash, mf->v3, mindex, NULL);
831                 if(mf->v4)
832                         BLI_edgehash_insert(vertpahash, mf->v4, mindex, NULL);
833         }
834
835         /* make new vertice indexes & count total vertices after duplication */
836         ehi= BLI_edgehashIterator_new(vertpahash);
837         for(; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
838                 BLI_edgehashIterator_setValue(ehi, SET_INT_IN_POINTER(totdup));
839                 totdup++;
840         }
841         BLI_edgehashIterator_free(ehi);
842
843         /* the final duplicated vertices */
844         explode= CDDM_from_template(dm, totdup, 0,totface, 0, 0);
845         mtface = CustomData_get_layer_named(&explode->faceData, CD_MTFACE, emd->uvname);
846         /*dupvert= CDDM_get_verts(explode);*/
847
848         /* getting back to object space */
849         invert_m4_m4(imat,ob->obmat);
850
851         psmd->psys->lattice = psys_get_lattice(&sim);
852
853         /* duplicate & displace vertices */
854         ehi= BLI_edgehashIterator_new(vertpahash);
855         for(; !BLI_edgehashIterator_isDone(ehi); BLI_edgehashIterator_step(ehi)) {
856                 MVert source;
857                 MVert *dest;
858
859                 /* get particle + vertex from hash */
860                 BLI_edgehashIterator_getKey(ehi, &j, &i);
861                 i -= totvert;
862                 v= GET_INT_FROM_POINTER(BLI_edgehashIterator_getValue(ehi));
863
864                 dm->getVert(dm, j, &source);
865                 dest = CDDM_get_vert(explode,v);
866
867                 DM_copy_vert_data(dm,explode,j,v,1);
868                 *dest = source;
869
870                 if(i!=totpart) {
871                         /* get particle */
872                         pa= pars+i;
873
874                         psys_get_birth_coordinates(&sim, pa, &birth, 0, 0);
875
876                         state.time=cfra;
877                         psys_get_particle_state(&sim, i, &state, 1);
878
879                         vertco=CDDM_get_vert(explode,v)->co;
880                         mul_m4_v3(ob->obmat,vertco);
881
882                         sub_v3_v3(vertco, birth.co);
883
884                         /* apply rotation, size & location */
885                         sub_qt_qtqt(rot, state.rot, birth.rot);
886                         mul_qt_v3(rot, vertco);
887
888                         if(emd->flag & eExplodeFlag_PaSize)
889                                 mul_v3_fl(vertco,pa->size);
890
891                         add_v3_v3(vertco, state.co);
892
893                         mul_m4_v3(imat, vertco);
894                 }
895         }
896         BLI_edgehashIterator_free(ehi);
897
898         /*map new vertices to faces*/
899         for (i=0; i<totface; i++) {
900                 MFace source;
901                 int orig_v4;
902
903                 if(facepa[i]!=totpart)
904                 {
905                         pa=pars+facepa[i];
906
907                         if(pa->alive==PARS_UNBORN && (emd->flag&eExplodeFlag_Unborn)==0) continue;
908                         if(pa->alive==PARS_ALIVE && (emd->flag&eExplodeFlag_Alive)==0) continue;
909                         if(pa->alive==PARS_DEAD && (emd->flag&eExplodeFlag_Dead)==0) continue;
910                 }
911
912                 dm->getTessFace(dm,i,&source);
913                 mf=CDDM_get_tessface(explode,i);
914                 
915                 orig_v4 = source.v4;
916
917                 if(facepa[i]!=totpart && cfra < pa->time)
918                         mindex = totvert+totpart;
919                 else 
920                         mindex = totvert+facepa[i];
921
922                 source.v1 = edgecut_get(vertpahash, source.v1, mindex);
923                 source.v2 = edgecut_get(vertpahash, source.v2, mindex);
924                 source.v3 = edgecut_get(vertpahash, source.v3, mindex);
925                 if(source.v4)
926                         source.v4 = edgecut_get(vertpahash, source.v4, mindex);
927
928                 DM_copy_tessface_data(dm,explode,i,i,1);
929
930                 *mf = source;
931
932                 /* override uv channel for particle age */
933                 if(mtface) {
934                         float age = (cfra - pa->time)/pa->lifetime;
935                         /* Clamp to this range to avoid flipping to the other side of the coordinates. */
936                         CLAMP(age, 0.001f, 0.999f);
937
938                         mtf = mtface + i;
939
940                         mtf->uv[0][0] = mtf->uv[1][0] = mtf->uv[2][0] = mtf->uv[3][0] = age;
941                         mtf->uv[0][1] = mtf->uv[1][1] = mtf->uv[2][1] = mtf->uv[3][1] = 0.5f;
942                 }
943
944                 test_index_face(mf, &explode->faceData, i, (orig_v4 ? 4 : 3));
945         }
946
947         /* cleanup */
948         BLI_edgehash_free(vertpahash, NULL);
949
950         /* finalization */
951         CDDM_calc_edges(explode);
952         CDDM_tessfaces_to_faces(explode);
953         CDDM_calc_normals(explode);
954
955         if(psmd->psys->lattice){
956                 end_latt_deform(psmd->psys->lattice);
957                 psmd->psys->lattice= NULL;
958         }
959
960         return explode;
961 }
962
963 static ParticleSystemModifierData * findPrecedingParticlesystem(Object *ob, ModifierData *emd)
964 {
965         ModifierData *md;
966         ParticleSystemModifierData *psmd= NULL;
967
968         for (md=ob->modifiers.first; emd!=md; md=md->next){
969                 if(md->type==eModifierType_ParticleSystem)
970                         psmd= (ParticleSystemModifierData*) md;
971         }
972         return psmd;
973 }
974 static DerivedMesh * applyModifier(ModifierData *md, Object *ob,
975                                                 DerivedMesh *derivedData,
976                                                 int UNUSED(useRenderParams),
977                                                 int UNUSED(isFinalCalc))
978 {
979         DerivedMesh *dm = derivedData;
980         ExplodeModifierData *emd= (ExplodeModifierData*) md;
981         ParticleSystemModifierData *psmd=findPrecedingParticlesystem(ob,md);
982
983         if(psmd){
984                 ParticleSystem * psys=psmd->psys;
985
986                 if(psys==NULL || psys->totpart==0) return derivedData;
987                 if(psys->part==NULL || psys->particles==NULL) return derivedData;
988                 if(psmd->dm==NULL) return derivedData;
989
990                 /* 1. find faces to be exploded if needed */
991                 if(emd->facepa == NULL
992                                  || psmd->flag&eParticleSystemFlag_Pars
993                                  || emd->flag&eExplodeFlag_CalcFaces
994                                  || MEM_allocN_len(emd->facepa)/sizeof(int) != dm->getNumTessFaces(dm))
995                 {
996                         if(psmd->flag & eParticleSystemFlag_Pars)
997                                 psmd->flag &= ~eParticleSystemFlag_Pars;
998                         
999                         if(emd->flag & eExplodeFlag_CalcFaces)
1000                                 emd->flag &= ~eExplodeFlag_CalcFaces;
1001
1002                         createFacepa(emd,psmd,derivedData);
1003                 }
1004                 /* 2. create new mesh */
1005                 if(emd->flag & eExplodeFlag_EdgeCut){
1006                         int *facepa = emd->facepa;
1007                         DerivedMesh *splitdm=cutEdges(emd,dm);
1008                         DerivedMesh *explode=explodeMesh(emd, psmd, md->scene, ob, splitdm);
1009
1010                         MEM_freeN(emd->facepa);
1011                         emd->facepa=facepa;
1012                         splitdm->release(splitdm);
1013                         return explode;
1014                 }
1015                 else
1016                         return explodeMesh(emd, psmd, md->scene, ob, derivedData);
1017         }
1018         return derivedData;
1019 }
1020
1021
1022 ModifierTypeInfo modifierType_Explode = {
1023         /* name */              "Explode",
1024         /* structName */        "ExplodeModifierData",
1025         /* structSize */        sizeof(ExplodeModifierData),
1026         /* type */              eModifierTypeType_Constructive,
1027         /* flags */             eModifierTypeFlag_AcceptsMesh,
1028         /* copyData */          copyData,
1029         /* deformVerts */       NULL,
1030         /* deformMatrices */    NULL,
1031         /* deformVertsEM */     NULL,
1032         /* deformMatricesEM */  NULL,
1033         /* applyModifier */     applyModifier,
1034         /* applyModifierEM */   NULL,
1035         /* initData */          initData,
1036         /* requiredDataMask */  requiredDataMask,
1037         /* freeData */          freeData,
1038         /* isDisabled */        NULL,
1039         /* updateDepgraph */    NULL,
1040         /* dependsOnTime */     dependsOnTime,
1041         /* dependsOnNormals */  NULL,
1042         /* foreachObjectLink */ NULL,
1043         /* foreachIDLink */     NULL,
1044         /* foreachTexLink */    NULL,
1045 };