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