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