svn merge -r37028:37030 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender.git] / source / blender / modifiers / intern / MOD_edgesplit.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): Joseph Eagar
24 *
25 * ***** END GPL LICENSE BLOCK *****
26 *
27 */
28
29 /* EdgeSplit modifier: Splits edges in the mesh according to sharpness flag
30  * or edge angle (can be used to achieve autosmoothing) */
31
32 #include "DNA_meshdata_types.h"
33
34 #include "BLI_utildefines.h"
35 #include "BLI_listbase.h"
36 #include "BLI_memarena.h"
37 #include "BLI_edgehash.h"
38 #include "BLI_math.h"
39 #include "BLI_array.h"
40
41 #include "BKE_cdderivedmesh.h"
42 #include "BKE_modifier.h"
43 #include "BKE_particle.h"
44 #include "BKE_tessmesh.h"
45 #include "BKE_mesh.h"
46
47 #include "MEM_guardedalloc.h"
48
49 /* EdgeSplit */
50 /* EdgeSplit modifier: Splits edges in the mesh according to sharpness flag
51  * or edge angle (can be used to achieve autosmoothing)
52 */
53
54 /*new cddm-based edge split code*/
55 typedef struct VertUser {
56         int ov, v, done;
57         ListBase users;
58 } VertUser;
59
60 typedef struct EdgeNode {
61         struct EdgeNode *next, *prev;
62         struct EdgeData *edge;
63 } EdgeNode;
64
65 typedef struct EdgeData {
66         EdgeNode v1node, v2node;
67         VertUser *v1user, *v2user;
68         float fno[3]; /*used to calculate face angles*/
69         int has_fno;
70         int tag;
71         int v1, v2;
72         int used;
73 } EdgeData;
74
75 typedef struct MemBase {
76         BLI_mempool *vertuserpool;
77 } MemBase;
78
79 BM_INLINE EdgeData *edge_get_next(EdgeData *e, int ov) {
80         if (ov == e->v1)
81                 return e->v1node.next ? e->v1node.next->edge : NULL;
82         else return e->v2node.next ? e->v2node.next->edge : NULL;
83 }
84
85 BM_INLINE EdgeNode *edge_get_node(EdgeData *e, int ov)
86 {
87         if (ov == e->v1)
88                 return &e->v1node;
89         else return &e->v2node;
90                 return NULL;
91 }
92
93 BM_INLINE VertUser *edge_get_vuser(MemBase *UNUSED(b), EdgeData *edge, int ov)
94 {
95         if (ov == edge->v1)
96                 return edge->v1user;
97         else if (ov == edge->v2)
98                 return edge->v2user;
99         else {
100                 printf("yeek!!\n");
101                 return NULL;
102         }
103 }
104
105 BM_INLINE void edge_set_vuser(MemBase *b, EdgeData *e, int ov, VertUser *vu)
106
107 {
108         VertUser *olduser = edge_get_vuser(b, e, ov);
109
110         if (vu == olduser)
111                 return;
112
113         if (olduser)
114                 BLI_remlink(&olduser->users, ov==e->v1 ? &e->v1node : &e->v2node);
115         BLI_addtail(&vu->users, ov==e->v1 ? &e->v1node : &e->v2node);
116
117         if (ov == e->v1)
118                 e->v1user = vu;
119         else e->v2user = vu;
120 }
121
122 BM_INLINE VertUser *new_vuser(MemBase *base)
123 {
124         VertUser *vusr = BLI_mempool_calloc(base->vertuserpool);
125
126         return vusr;
127 }
128
129 BM_INLINE MemBase *new_membase(void)
130 {
131         MemBase *b = MEM_callocN(sizeof(MemBase), "MemBase for edgesplit in modifier.c");
132         b->vertuserpool = BLI_mempool_create(sizeof(VertUser), 1, 2048, 1, 0);
133
134         return b;
135 }
136
137 BM_INLINE void free_membase(MemBase *b)
138 {
139         BLI_mempool_destroy(b->vertuserpool);
140         MEM_freeN(b);
141 }
142
143 BM_INLINE EdgeData *edge_get_first(VertUser *vu)
144 {
145         return vu->users.first ? ((EdgeNode*)vu->users.first)->edge : NULL;
146 }
147
148 DerivedMesh *doEdgeSplit(DerivedMesh *dm, EdgeSplitModifierData *emd)
149 {
150         DerivedMesh *cddm = CDDM_copy(dm, 0);
151         MEdge *medge;
152         BLI_array_declare(medge);
153         MLoop *mloop, *ml, *prevl;
154         MPoly *mpoly, *mp;
155         MVert *mvert;
156         BLI_array_declare(mvert);
157         EdgeData *etags, *e, *enext;
158         BLI_array_declare(etags);
159         VertUser *vu, *vu2;
160         MemBase *membase;
161         CustomData edata, vdata;
162         int i, j, curv, cure;
163         float threshold = cos((emd->split_angle + 0.00001) * M_PI / 180.0);
164         float no[3], edge_angle_cos;
165
166         if (!cddm->numVertData || !cddm->numEdgeData)
167                 return cddm;
168
169         membase = new_membase();
170
171         etags = MEM_callocN(sizeof(EdgeData)*cddm->numEdgeData, "edgedata tag thingies");
172         BLI_array_set_length(etags, cddm->numEdgeData);
173
174         mvert = cddm->getVertArray(cddm);
175         BLI_array_set_length(mvert, cddm->numVertData);
176         medge = cddm->getEdgeArray(cddm);
177         BLI_array_set_length(medge, cddm->numEdgeData);
178         mloop = CustomData_get_layer(&cddm->loopData, CD_MLOOP);
179         mpoly = CustomData_get_layer(&cddm->polyData, CD_MPOLY);
180
181         for (i=0; i<cddm->numEdgeData; i++) {
182                 etags[i].v1 = medge[i].v1;
183                 etags[i].v2 = medge[i].v2;
184
185                 etags[i].tag = (medge[i].flag & ME_SHARP) != 0;
186
187                 etags[i].v1node.edge = etags+i;
188                 etags[i].v2node.edge = etags+i;
189         }
190
191         if (emd->flags & MOD_EDGESPLIT_FROMANGLE) {
192                 mp = mpoly;
193                 for (i=0; i<cddm->numPolyData; i++, mp++) {
194                         mesh_calc_poly_normal(mp, mloop+mp->loopstart, mvert, no);
195
196                         ml = mloop + mp->loopstart;
197                         for (j=0; j<mp->totloop; j++, ml++) {
198                                 if (!etags[ml->e].has_fno) {
199                                         VECCOPY(etags[ml->e].fno, no);
200                                         etags[ml->e].has_fno = 1;
201                                 } else if (!etags[ml->e].tag) {
202                                         edge_angle_cos = INPR(etags[ml->e].fno, no);
203                                         if (edge_angle_cos < threshold) {
204                                                 etags[ml->e].tag = 1;
205                                         }
206                                 }
207                         }
208                 }
209         }
210
211         mp = mpoly;
212         for (i=0; i<cddm->numPolyData; i++, mp++) {
213                 ml = mloop + mp->loopstart;
214                 for (j=0; j<mp->totloop; j++, ml++) {
215                         if (etags[ml->e].tag)
216                                 continue;
217
218                         prevl = mloop + mp->loopstart + ((j-1)+mp->totloop) % mp->totloop;
219
220                         if (!edge_get_vuser(membase, etags+prevl->e, ml->v)) {
221                                 vu = new_vuser(membase);
222                                 vu->ov = vu->v = ml->v;
223                                 edge_set_vuser(membase, etags+prevl->e, ml->v, vu);
224                         }
225
226                         if (!edge_get_vuser(membase, etags+ml->e, ml->v)) {
227                                 vu = new_vuser(membase);
228                                 vu->ov = vu->v = ml->v;
229                                 edge_set_vuser(membase, etags+ml->e, ml->v, vu);
230                         }
231
232                         /*continue if previous edge is tagged*/
233                         if (etags[prevl->e].tag)
234                                 continue;
235
236                         /*merge together adjacent split vert users*/
237                         if (edge_get_vuser(membase, etags+prevl->e, ml->v)
238                                 != edge_get_vuser(membase, etags+ml->e, ml->v))
239                         {
240                                 vu = edge_get_vuser(membase, etags+prevl->e, ml->v);
241                                 vu2 = edge_get_vuser(membase, etags+ml->e, ml->v);
242
243                                 /*remove from vu2's users list and add to vu's*/
244                                 for (e=edge_get_first(vu2); e; e=enext) {
245                                         enext = edge_get_next(e, ml->v);
246                                         edge_set_vuser(membase, e, ml->v, vu);
247                                 }
248                         }
249                 }
250         }
251
252         mp = mpoly;
253         for (i=0; i<cddm->numPolyData; i++, mp++) {
254                 ml = mloop + mp->loopstart;
255                 for (j=0; j<mp->totloop; j++, ml++) {
256                         if (!etags[ml->e].tag)
257                                 continue;
258
259                         prevl = mloop + mp->loopstart + ((j-1)+mp->totloop) % mp->totloop;
260
261                         if (!etags[prevl->e].tag) {
262                                 vu = edge_get_vuser(membase, etags+prevl->e, ml->v);
263                                 if (!vu) {
264                                         vu = new_vuser(membase);
265                                         vu->ov = vu->v = ml->v;
266                                         edge_set_vuser(membase, etags+prevl->e, ml->v, vu);
267                                 }
268
269                                 edge_set_vuser(membase, etags+ml->e, ml->v, vu);
270                         } else {
271                                 vu = new_vuser(membase);
272                                 vu->ov = vu->v = ml->v;
273                                 edge_set_vuser(membase, etags+ml->e, ml->v, vu);
274                         }
275                 }
276         }
277
278         curv = cddm->numVertData;
279         cure = cddm->numEdgeData;
280         mp = mpoly;
281         for (i=0; i<cddm->numPolyData; i++, mp++) {
282                 ml = mloop + mp->loopstart;
283                 for (j=0; j<mp->totloop; j++, ml++) {
284                         e = etags + ml->e;
285                         if (e->v1user && !e->v1user->done) {
286                                 e->v1user->done = 1;
287                                 BLI_array_growone(mvert);
288
289                                 mvert[curv] = mvert[e->v1user->ov];
290                                 e->v1user->v = curv;
291
292                                 curv++;
293                         }
294
295                         if (e->v2user && !e->v2user->done) {
296                                 e->v2user->done = 1;
297                                 BLI_array_growone(mvert);
298
299                                 mvert[curv] = mvert[e->v2user->ov];
300                                 e->v2user->v = curv;
301
302                                 curv++;
303                         }
304
305                         vu = edge_get_vuser(membase, e, ml->v);
306                         if (!vu)
307                                 continue;
308                         ml->v = vu->v;
309                 }
310         }
311
312
313         /*resize customdata arrays and add new medge/mvert arrays*/
314         vdata = cddm->vertData;
315         edata = cddm->edgeData;
316
317         /*make sure we don't copy over mvert/medge layers*/
318         CustomData_set_layer(&vdata, CD_MVERT, NULL);
319         CustomData_set_layer(&edata, CD_MEDGE, NULL);
320         CustomData_free_layer_active(&vdata, CD_MVERT, cddm->numVertData);
321         CustomData_free_layer_active(&edata, CD_MEDGE, cddm->numEdgeData);
322
323         memset(&cddm->vertData, 0, sizeof(CustomData));
324         memset(&cddm->edgeData, 0, sizeof(CustomData));
325
326         CustomData_copy(&vdata, &cddm->vertData, CD_MASK_DERIVEDMESH, CD_CALLOC, curv);
327         CustomData_copy_data(&vdata, &cddm->vertData, 0, 0, cddm->numVertData);
328         CustomData_free(&vdata, cddm->numVertData);
329         cddm->numVertData = curv;
330
331         CustomData_copy(&edata, &cddm->edgeData, CD_MASK_DERIVEDMESH, CD_CALLOC, cure);
332         CustomData_copy_data(&edata, &cddm->edgeData, 0, 0, cddm->numEdgeData);
333         CustomData_free(&edata, cddm->numEdgeData);
334         cddm->numEdgeData = cure;
335
336         CDDM_set_mvert(cddm, mvert);
337         CDDM_set_medge(cddm, medge);
338         
339         CustomData_set_layer(&cddm->vertData, CD_MVERT, mvert);
340         CustomData_set_layer(&cddm->edgeData, CD_MEDGE, medge);
341         
342         free_membase(membase);
343         BLI_array_free(etags);
344         BLI_array_fake_user(mvert);
345         BLI_array_fake_user(medge);
346
347         /*edge calculation isn't working correctly, so just brute force it*/
348         cddm->numEdgeData = 0;
349         CDDM_calc_edges_poly(cddm);
350
351         cddm->numFaceData = mesh_recalcTesselation(&cddm->faceData,
352                 &cddm->loopData, &cddm->polyData,
353                 mvert, cddm->numFaceData,
354                 cddm->numLoopData, cddm->numPolyData, 1, 0);
355
356         CDDM_set_mface(cddm, DM_get_tessface_data_layer(cddm, CD_MFACE));
357         CDDM_calc_normals(cddm);
358
359         return cddm;
360 }
361
362 static void initData(ModifierData *md)
363 {
364         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
365
366         /* default to 30-degree split angle, sharpness from both angle & flag
367         */
368         emd->split_angle = 30;
369         emd->flags = MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG;
370 }
371
372 static void copyData(ModifierData *md, ModifierData *target)
373 {
374         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
375         EdgeSplitModifierData *temd = (EdgeSplitModifierData*) target;
376
377         temd->split_angle = emd->split_angle;
378         temd->flags = emd->flags;
379 }
380
381 static DerivedMesh *edgesplitModifier_do(EdgeSplitModifierData *emd,
382                                          Object *UNUSED(ob), DerivedMesh *dm)
383 {
384         if(!(emd->flags & (MOD_EDGESPLIT_FROMANGLE | MOD_EDGESPLIT_FROMFLAG)))
385                 return dm;
386
387         return doEdgeSplit(dm, emd);
388 }
389
390 static DerivedMesh *applyModifier(
391                 ModifierData *md, Object *ob, DerivedMesh *derivedData,
392                 int UNUSED(useRenderParams), int UNUSED(isFinalCalc))
393 {
394         DerivedMesh *result;
395         EdgeSplitModifierData *emd = (EdgeSplitModifierData*) md;
396
397         result = edgesplitModifier_do(emd, ob, derivedData);
398
399         if(result != derivedData)
400                 CDDM_calc_normals(result);
401
402         return result;
403 }
404
405 static DerivedMesh *applyModifierEM(ModifierData *md, Object *ob,
406                                                                         BMEditMesh *UNUSED(editData), DerivedMesh *derivedData)
407 {
408         return applyModifier(md, ob, derivedData, 0, 1);
409 }
410
411
412 ModifierTypeInfo modifierType_EdgeSplit = {
413         /* name */              "EdgeSplit",
414         /* structName */        "EdgeSplitModifierData",
415         /* structSize */        sizeof(EdgeSplitModifierData),
416         /* type */              eModifierTypeType_Constructive,
417         /* flags */             eModifierTypeFlag_AcceptsMesh
418                                                         | eModifierTypeFlag_AcceptsCVs
419                                                         | eModifierTypeFlag_SupportsMapping
420                                                         | eModifierTypeFlag_SupportsEditmode
421                                                         | eModifierTypeFlag_EnableInEditmode,
422
423         /* copyData */          copyData,
424         /* deformVerts */       NULL,
425         /* deformMatrices */    NULL,
426         /* deformVertsEM */     NULL,
427         /* deformMatricesEM */  NULL,
428         /* applyModifier */     applyModifier,
429         /* applyModifierEM */   applyModifierEM,
430         /* initData */          initData,
431         /* requiredDataMask */  NULL,
432         /* freeData */          NULL,
433         /* isDisabled */        NULL,
434         /* updateDepgraph */    NULL,
435         /* dependsOnTime */     NULL,
436         /* dependsOnNormals */  NULL,
437         /* foreachObjectLink */ NULL,
438         /* foreachIDLink */     NULL,
439 };