part 1 of cleaning up my little array macro library to be a formal API. also removed...
[blender.git] / source / blender / blenkernel / intern / editderivedbmesh.c
1 /**
2  * $Id: editderivedbmesh.c 18571 2009-01-19 06:04:57Z joeedh $
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Tbmple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2005 Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 #include <string.h>
31
32 #ifdef HAVE_CONFIG_H
33 #include <config.h>
34 #endif
35
36 #include "PIL_time.h"
37
38 #include "MEM_guardedalloc.h"
39
40 #include "DNA_effect_types.h"
41 #include "DNA_mesh_types.h"
42 #include "DNA_key_types.h"
43 #include "DNA_meshdata_types.h"
44 #include "DNA_modifier_types.h"
45 #include "DNA_object_types.h"
46 #include "DNA_object_force.h"
47 #include "DNA_object_fluidsim.h" // N_T
48 #include "DNA_scene_types.h" // N_T
49 #include "DNA_texture_types.h"
50 #include "DNA_view3d_types.h"
51 #include "DNA_screen_types.h"
52 #include "DNA_space_types.h"
53 #include "DNA_particle_types.h"
54
55 #include "BLI_arithb.h"
56 #include "BLI_blenlib.h"
57 #include "BLI_editVert.h"
58 #include "BLI_edgehash.h"
59 #include "BLI_linklist.h"
60 #include "BLI_memarena.h"
61 #include "BLI_scanfill.h"
62 #include "BLI_ghash.h"
63 #include "BLI_array.h"
64
65 #include "BKE_cdderivedmesh.h"
66 #include "BKE_customdata.h"
67 #include "BKE_DerivedMesh.h"
68 #include "BKE_deform.h"
69 #include "BKE_displist.h"
70 #include "BKE_effect.h"
71 #include "BKE_fluidsim.h"
72 #include "BKE_global.h"
73 #include "BKE_key.h"
74 #include "BKE_material.h"
75 #include "BKE_modifier.h"
76 #include "BKE_mesh.h"
77 #include "BKE_object.h"
78 #include "BKE_subsurf.h"
79 #include "BKE_texture.h"
80 #include "BKE_utildefines.h"
81 #include "BKE_particle.h"
82 #include "BKE_tessmesh.h"
83
84 #include "BLO_sys_types.h" // for intptr_t support
85
86 #include "BIF_gl.h"
87 #include "BIF_glutil.h"
88
89 #include "GPU_draw.h"
90 #include "GPU_extensions.h"
91 #include "GPU_material.h"
92
93 #include "bmesh.h"
94
95 BMEditMesh *BMEdit_Create(BMesh *bm)
96 {
97         BMEditMesh *tm = MEM_callocN(sizeof(BMEditMesh), "tm");
98         
99         tm->bm = bm;
100
101         BMEdit_RecalcTesselation(tm);
102
103         return tm;
104 }
105
106 BMEditMesh *BMEdit_Copy(BMEditMesh *tm)
107 {
108         BMEditMesh *tm2 = MEM_callocN(sizeof(BMEditMesh), "tm2");
109         *tm2 = *tm;
110         
111         tm2->derivedCage = tm2->derivedFinal = NULL;
112         
113         tm2->looptris = NULL;
114         tm2->bm = BM_Copy_Mesh(tm->bm);
115         BMEdit_RecalcTesselation(tm2);
116
117         tm2->vert_index = NULL;
118         tm2->edge_index = NULL;
119         tm2->face_index = NULL;
120
121         return tm2;
122 }
123
124 static void BMEdit_RecalcTesselation_intern(BMEditMesh *tm)
125 {
126         BMesh *bm = tm->bm;
127         BMLoop **looptris = NULL;
128         BLI_array_declare(looptris);
129         BMIter iter, liter;
130         BMFace *f;
131         BMLoop *l;
132         int i = 0, j, a, b;
133         
134         if (tm->looptris) MEM_freeN(tm->looptris);
135
136 #if 0 //simple quad/triangle code for performance testing purposes
137         looptris = MEM_callocN(sizeof(void*)*bm->totface*8, "looptris");
138
139         f = BMIter_New(&iter, bm, BM_FACES_OF_MESH, NULL);
140         for ( ; f; f=BMIter_Step(&iter)) {
141                 EditVert *v, *lastv=NULL, *firstv=NULL;
142                 EditEdge *e;
143                 EditFace *efa;
144
145                 /*don't consider two-edged faces*/
146                 if (f->len < 3) continue;
147                 
148                 //BLI_array_growone(looptris);
149                 //BLI_array_growone(looptris);
150                 //BLI_array_growone(looptris);
151
152                 looptris[i*3] = f->loopbase;
153                 looptris[i*3+1] = f->loopbase->head.next;
154                 looptris[i*3+2] = f->loopbase->head.next->next;
155                 i++;
156
157                 if (f->len > 3) {
158                         //BLI_array_growone(looptris);
159                         //BLI_array_growone(looptris);
160                         //BLI_array_growone(looptris);
161
162                         looptris[i*3] = f->loopbase;
163                         looptris[i*3+1] = f->loopbase->head.next->next;
164                         looptris[i*3+2] = f->loopbase->head.next->next->next;
165                         i++;
166                 }
167
168         }
169
170         tm->tottri = i;
171         tm->looptris = looptris;
172         return;
173 #endif
174
175         f = BMIter_New(&iter, bm, BM_FACES_OF_MESH, NULL);
176         for ( ; f; f=BMIter_Step(&iter)) {
177                 EditVert *v, *lastv=NULL, *firstv=NULL;
178                 EditEdge *e;
179                 EditFace *efa;
180
181                 /*don't consider two-edged faces*/
182                 if (f->len < 3) continue;
183                 
184                 /*scanfill time*/
185                 l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
186                 for (j=0; l; l=BMIter_Step(&liter), j++) {
187                         /*mark order*/
188                         l->head.eflag2 = j;
189
190                         v = BLI_addfillvert(l->v->co);
191                         v->tmp.p = l;
192                         
193                         if (lastv) {
194                                 e = BLI_addfilledge(lastv, v);
195                         }
196
197                         lastv = v;
198                         if (firstv==NULL) firstv = v;
199                 }
200
201                 /*complete the loop*/
202                 BLI_addfilledge(firstv, v);
203
204                 BLI_edgefill(0, 0);
205                 
206                 for (efa = fillfacebase.first; efa; efa=efa->next) {
207                         BMLoop *l1, *l2, *l3;
208
209                         BLI_array_growone(looptris);
210                         BLI_array_growone(looptris);
211                         BLI_array_growone(looptris);
212                         
213                         looptris[i*3] = l1 = efa->v1->tmp.p;
214                         looptris[i*3+1] = l2 = efa->v2->tmp.p;
215                         looptris[i*3+2] = l3 = efa->v3->tmp.p;
216                         
217                         if (l1->head.eflag2 > l2->head.eflag2) {
218                                 SWAP(BMLoop*, l1, l2);
219                         }
220                         if (l2->head.eflag2 > l3->head.eflag2) {
221                                 SWAP(BMLoop*, l2, l3);
222                         }
223                         if (l1->head.eflag2 > l2->head.eflag2) {
224                                 SWAP(BMLoop*, l1, l2);
225                         }
226                         
227                         looptris[i*3] = l1;
228                         looptris[i*3+1] = l2;
229                         looptris[i*3+2] = l3;
230
231                         i += 1;
232                 }
233
234                 BLI_end_edgefill();
235         }
236
237         tm->tottri = i;
238         tm->looptris = looptris;
239 }
240
241 void BMEdit_RecalcTesselation(BMEditMesh *tm)
242 {
243         BMEdit_RecalcTesselation_intern(tm);
244
245         if (tm->derivedFinal && tm->derivedFinal == tm->derivedCage) {
246                 if (tm->derivedFinal->recalcTesselation) 
247                         tm->derivedFinal->recalcTesselation(tm->derivedFinal);
248         } else if (tm->derivedFinal) {
249                 if (tm->derivedCage->recalcTesselation) 
250                         tm->derivedCage->recalcTesselation(tm->derivedCage);
251                 if (tm->derivedFinal->recalcTesselation) 
252                         tm->derivedFinal->recalcTesselation(tm->derivedFinal);
253         }
254 }
255
256 void BMEdit_UpdateLinkedCustomData(BMEditMesh *em)
257 {
258         BMesh *bm = em->bm;
259         int act;
260
261         if (CustomData_has_layer(&bm->pdata, CD_MTEXPOLY)) {
262                 act = CustomData_get_active_layer(&bm->pdata, CD_MTEXPOLY);
263                 CustomData_set_layer_active(&bm->ldata, CD_MLOOPUV, act);
264
265                 act = CustomData_get_render_layer(&bm->pdata, CD_MTEXPOLY);
266                 CustomData_set_layer_render(&bm->ldata, CD_MLOOPUV, act);
267
268                 act = CustomData_get_clone_layer(&bm->pdata, CD_MTEXPOLY);
269                 CustomData_set_layer_clone(&bm->ldata, CD_MLOOPUV, act);
270
271                 act = CustomData_get_mask_layer(&bm->pdata, CD_MTEXPOLY);
272                 CustomData_set_layer_mask(&bm->ldata, CD_MLOOPUV, act);
273         }
274 }
275
276 /*does not free the BMEditMesh struct itself*/
277 void BMEdit_Free(BMEditMesh *em)
278 {
279         if(em->derivedFinal) {
280                 if (em->derivedFinal!=em->derivedCage) {
281                         em->derivedFinal->needsFree= 1;
282                         em->derivedFinal->release(em->derivedFinal);
283                 }
284                 em->derivedFinal= NULL;
285         }
286         if(em->derivedCage) {
287                 em->derivedCage->needsFree= 1;
288                 em->derivedCage->release(em->derivedCage);
289                 em->derivedCage= NULL;
290         }
291
292         em->retopo_paint_data= NULL;
293
294         if (em->looptris) MEM_freeN(em->looptris);
295
296         if (em->vert_index) MEM_freeN(em->vert_index);
297         if (em->edge_index) MEM_freeN(em->edge_index);
298         if (em->face_index) MEM_freeN(em->face_index);
299
300         BM_Free_Mesh(em->bm);
301 }
302
303
304 /*
305 ok, basic design:
306
307 the bmesh derivedmesh exposes the mesh as triangles.  it stores pointers
308 to three loops per triangle.  the derivedmesh stores a cache of tesselations
309 for each face.  this cache will smartly update as needed (though at first
310 it'll simply be more brute force).  keeping track of face/edge counts may
311 be a small problbm.
312
313 this won't be the most efficient thing, considering that internal edges and
314 faces of tesselations are exposed.  looking up an edge by index in particular
315 is likely to be a little slow.
316 */
317
318 typedef struct EditDerivedBMesh {
319         DerivedMesh dm;
320
321         Object *ob;
322         BMEditMesh *tc;
323
324         float (*vertexCos)[3];
325         float (*vertexNos)[3];
326         float (*faceNos)[3];
327
328         /*lookup caches; these are rebuilt on dm->RecalcTesselation()
329           (or when the derivedmesh is created, of course)*/
330         GHash *vhash, *ehash, *fhash;
331         BMVert **vtable;
332         BMEdge **etable;
333         BMFace **ftable;
334
335         /*private variables, for number of verts/edges/faces
336           within the above hash/table members*/
337         int tv, te, tf;
338
339         /*customdata layout of the tesselated faces*/
340         CustomData tessface_layout;
341 } EditDerivedBMesh;
342
343 static void bmdm_recalc_lookups(EditDerivedBMesh *bmdm)
344 {
345         BMIter iter;
346         BMHeader *h;
347         int a, i, iters[3] = {BM_VERTS_OF_MESH, BM_EDGES_OF_MESH, BM_FACES_OF_MESH};
348         
349         bmdm->tv = bmdm->tc->bm->totvert;
350         bmdm->te = bmdm->tc->bm->totedge;
351         bmdm->tf = bmdm->tc->bm->totface;
352
353         if (bmdm->vhash) BLI_ghash_free(bmdm->vhash, NULL, NULL);
354         if (bmdm->ehash) BLI_ghash_free(bmdm->ehash, NULL, NULL);
355         if (bmdm->fhash) BLI_ghash_free(bmdm->fhash, NULL, NULL);
356
357         bmdm->vhash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
358         bmdm->ehash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
359         bmdm->fhash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
360         
361         if (bmdm->vtable) MEM_freeN(bmdm->vtable);
362         if (bmdm->etable) MEM_freeN(bmdm->etable);
363         if (bmdm->ftable) MEM_freeN(bmdm->ftable);
364         
365         if (bmdm->tc->bm->totvert)
366                 bmdm->vtable = MEM_mallocN(sizeof(void**)*bmdm->tc->bm->totvert, "bmdm->vtable");
367         else bmdm->vtable = NULL;
368
369         if (bmdm->tc->bm->totedge)
370                 bmdm->etable = MEM_mallocN(sizeof(void**)*bmdm->tc->bm->totedge, "bmdm->etable");
371         else bmdm->etable = NULL;
372         
373         if (bmdm->tc->bm->totface)
374                 bmdm->ftable = MEM_mallocN(sizeof(void**)*bmdm->tc->bm->totface, "bmdm->ftable");
375         else bmdm->ftable = NULL;
376         
377         for (a=0; a<3; a++) {
378                 h = BMIter_New(&iter, bmdm->tc->bm, iters[a], NULL);
379                 for (i=0; h; h=BMIter_Step(&iter), i++) {
380                         switch (a) {
381                                 case 0:
382                                         bmdm->vtable[i] = (BMVert*) h;
383                                         BLI_ghash_insert(bmdm->vhash, h, SET_INT_IN_POINTER(i));
384                                         break;
385                                 case 1:
386                                         bmdm->etable[i] = (BMEdge*) h;
387                                         BLI_ghash_insert(bmdm->ehash, h, SET_INT_IN_POINTER(i));
388                                         break;
389                                 case 2:
390                                         bmdm->ftable[i] = (BMFace*) h;
391                                         BLI_ghash_insert(bmdm->fhash, h, SET_INT_IN_POINTER(i));
392                                         break;
393
394                         }
395                 }
396         }
397 }
398
399 static void bmDM_recalcTesselation(DerivedMesh *dm)
400 {
401         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
402
403         //bmdm_recalc_lookups(bmdm);
404 }
405
406 static void bmDM_foreachMappedVert(DerivedMesh *dm, void (*func)(void *userData, int index, float *co, float *no_f, short *no_s), void *userData)
407 {
408         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
409         BMVert *eve;
410         BMIter iter;
411         int i;
412         
413         eve = BMIter_New(&iter, bmdm->tc->bm, BM_VERTS_OF_MESH, NULL);
414         for (i=0; eve; i++, eve=BMIter_Step(&iter)) {
415                 if (bmdm->vertexCos) {
416                         func(userData, i, bmdm->vertexCos[i], bmdm->vertexNos[i], NULL);
417                 } else {
418                         func(userData, i, eve->co, eve->no, NULL);
419                 }
420         }
421 }
422 static void bmDM_foreachMappedEdge(DerivedMesh *dm, void (*func)(void *userData, int index, float *v0co, float *v1co), void *userData)
423 {
424         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
425         BMEdge *eed;
426         BMIter iter;
427         int i;
428         
429         if (bmdm->vertexCos) {
430                 BMVert *eve;
431                 BMIter viter;
432
433                 eve = BMIter_New(&viter, bmdm->tc->bm, BM_VERTS_OF_MESH, NULL);
434                 for (i=0; eve; eve=BMIter_Step(&viter), i++) {
435                         BMINDEX_SET(eve, i);
436                 }
437
438                 eed = BMIter_New(&iter, bmdm->tc->bm, BM_EDGES_OF_MESH, NULL);
439                 for(i=0; eed; i++,eed=BMIter_Step(&iter))
440                         func(userData, i, 
441                              bmdm->vertexCos[BMINDEX_GET(eve)], 
442                              bmdm->vertexCos[BMINDEX_GET(eve)]);
443         } else {
444                 eed = BMIter_New(&iter, bmdm->tc->bm, BM_EDGES_OF_MESH, NULL);
445                 for(i=0; eed; i++,eed=BMIter_Step(&iter))
446                         func(userData, i, eed->v1->co, eed->v2->co);
447         }
448
449 }
450
451 static void bmDM_drawMappedEdges(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index), void *userData) 
452 {
453         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
454         BMEdge *eed;
455         BMIter iter;
456         int i;
457         
458         if (bmdm->vertexCos) {
459                 BMVert *eve;
460                 BMIter viter;
461
462                 eve = BMIter_New(&viter, bmdm->tc->bm, BM_VERTS_OF_MESH, NULL);
463                 for (i=0; eve; eve=BMIter_Step(&viter), i++) {
464                         BMINDEX_SET(eve, i);
465                 }
466
467                 glBegin(GL_LINES);
468                 eed = BMIter_New(&iter, bmdm->tc->bm, BM_EDGES_OF_MESH, NULL);
469                 for(i=0; eed; i++,eed=BMIter_Step(&iter)) {
470                         if(!setDrawOptions || setDrawOptions(userData, i)) {
471                                 glVertex3fv(bmdm->vertexCos[BMINDEX_GET(eed->v1)]);
472                                 glVertex3fv(bmdm->vertexCos[BMINDEX_GET(eed->v2)]);
473                         }
474                 }
475                 glEnd();
476
477         } else {
478                 glBegin(GL_LINES);
479                 eed = BMIter_New(&iter, bmdm->tc->bm, BM_EDGES_OF_MESH, NULL);
480                 for(i=0; eed; i++,eed=BMIter_Step(&iter)) {
481                         if(!setDrawOptions || setDrawOptions(userData, i)) {
482                                 glVertex3fv(eed->v1->co);
483                                 glVertex3fv(eed->v2->co);
484                         }
485                 }
486                 glEnd();
487         }
488 }
489
490 static void bmDM_drawEdges(DerivedMesh *dm, int drawLooseEdges)
491 {
492         bmDM_drawMappedEdges(dm, NULL, NULL);
493 }
494
495 static void bmDM_drawMappedEdgesInterp(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index), void (*setDrawInterpOptions)(void *userData, int index, float t), void *userData) 
496 {
497         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
498         BMEdge *eed;
499         BMIter iter;
500         int i;
501
502         if (bmdm->vertexCos) {
503                 BMVert *eve;
504
505                 eve = BMIter_New(&iter, bmdm->tc->bm, BM_VERTS_OF_MESH, NULL);
506                 for (i=0; eve; eve=BMIter_Step(&iter), i++)
507                         BMINDEX_SET(eve, i);
508
509                 glBegin(GL_LINES);
510                 eed = BMIter_New(&iter, bmdm->tc->bm, BM_EDGES_OF_MESH, NULL);
511                 for(i=0; eed; i++,eed=BMIter_Step(&iter)) {
512                         if(!setDrawOptions || setDrawOptions(userData, i)) {
513                                 setDrawInterpOptions(userData, i, 0.0);
514                                 glVertex3fv(bmdm->vertexCos[(int) BMINDEX_GET(eed->v1)]);
515                                 setDrawInterpOptions(userData, i, 1.0);
516                                 glVertex3fv(bmdm->vertexCos[(int) BMINDEX_GET(eed->v2)]);
517                         }
518                 }
519                 glEnd();
520         } else {
521                 glBegin(GL_LINES);
522                 eed = BMIter_New(&iter, bmdm->tc->bm, BM_EDGES_OF_MESH, NULL);
523                 for(i=0; eed; i++,eed=BMIter_Step(&iter)) {
524                         if(!setDrawOptions || setDrawOptions(userData, i)) {
525                                 setDrawInterpOptions(userData, i, 0.0);
526                                 glVertex3fv(eed->v1->co);
527                                 setDrawInterpOptions(userData, i, 1.0);
528                                 glVertex3fv(eed->v2->co);
529                         }
530                 }
531                 glEnd();
532         }
533 }
534
535 static void bmDM_drawUVEdges(DerivedMesh *dm)
536 {
537 #if 0
538         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
539         BMFace *efa;
540         MTFace *tf;
541
542         glBegin(GL_LINES);
543         for(efa= bmdm->tc->bm->faces.first; efa; efa= efa->next) {
544                 tf = CustomData_bm_get(&bmdm->tc->bm->pdata, efa->data, CD_MTFACE);
545
546                 if(tf && !(efa->h)) {
547                         glVertex2fv(tf->uv[0]);
548                         glVertex2fv(tf->uv[1]);
549
550                         glVertex2fv(tf->uv[1]);
551                         glVertex2fv(tf->uv[2]);
552
553                         if (!efa->v4) {
554                                 glVertex2fv(tf->uv[2]);
555                                 glVertex2fv(tf->uv[0]);
556                         } else {
557                                 glVertex2fv(tf->uv[2]);
558                                 glVertex2fv(tf->uv[3]);
559                                 glVertex2fv(tf->uv[3]);
560                                 glVertex2fv(tf->uv[0]);
561                         }
562                 }
563         }
564         glEnd();
565 #endif
566 }
567
568 static void bmDM__calcFaceCent(BMesh *bm, BMFace *efa, float cent[3],
569                                float (*vertexCos)[3])
570 {
571         BMIter iter;
572         BMLoop *l;
573         int tot = 0;
574         
575         cent[0] = cent[1] = cent[2] = 0.0f;
576         
577         /*simple (and stupid) median (average) based method :/ */
578         
579         if (vertexCos) {
580                 l = BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, efa);
581                 for (; l; l=BMIter_Step(&iter)) {
582                         VECADD(cent, cent, vertexCos[BMINDEX_GET(l->v)]);
583                         tot++;
584                 }
585         } else {
586                 l = BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, efa);
587                 for (; l; l=BMIter_Step(&iter)) {
588                         VECADD(cent, cent, l->v->co);
589                         tot++;
590                 }
591         }
592
593         if (tot==0) return;
594         VECMUL(cent, 1.0f/(float)tot);
595 }
596
597 static void bmDM_foreachMappedFaceCenter(DerivedMesh *dm, void (*func)(void *userData, int index, float *co, float *no), void *userData)
598 {
599         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
600         BMVert *eve;
601         BMFace *efa;
602         BMIter iter;
603         float cent[3];
604         int i;
605
606         if (bmdm->vertexCos) {
607                 eve = BMIter_New(&iter, bmdm->tc->bm, BM_VERTS_OF_MESH, NULL);
608                 for (i=0; eve; eve=BMIter_Step(&iter), i++)
609                         BMINDEX_SET(eve, i);
610         }
611
612         efa = BMIter_New(&iter, bmdm->tc->bm, BM_FACES_OF_MESH, NULL);
613         for (i=0; efa; efa=BMIter_Step(&iter), i++) {
614                 bmDM__calcFaceCent(bmdm->tc->bm, efa, cent, bmdm->vertexCos);
615                 func(userData, i, cent, bmdm->vertexCos?bmdm->faceNos[i]:efa->no);
616         }
617 }
618
619 static void bmDM_drawMappedFaces(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index, int *drawSmooth_r), void *userData, int useColors)
620 {
621         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
622         BMFace *efa;
623         BMIter iter;
624         int i, draw;
625
626         if (bmdm->vertexCos) {
627                 BMVert *eve;
628                 
629                 eve = BMIter_New(&iter, bmdm->tc->bm, BM_VERTS_OF_MESH, NULL);
630                 for (i=0; eve; eve=BMIter_Step(&iter), i++)
631                         BMINDEX_SET(eve, i);
632
633                 efa = BMIter_New(&iter, bmdm->tc->bm, BM_FACES_OF_MESH, NULL);
634                 for (i=0; efa; efa=BMIter_Step(&iter), i++)
635                         BMINDEX_SET(efa, i);
636
637                 for (i=0; i<bmdm->tc->tottri; i++) {
638                         BMLoop **l = bmdm->tc->looptris[i];
639                         int drawSmooth;
640                         
641                         efa = l[0]->f;
642                         drawSmooth = (efa->head.flag & BM_SMOOTH);
643
644                         draw = setDrawOptions==NULL ? 1 : setDrawOptions(userData, BMINDEX_GET(efa), &drawSmooth);
645                         if(draw) {
646                                 if (draw==2) { /* enabled with stipple */
647                                         glEnable(GL_POLYGON_STIPPLE);
648                                         glPolygonStipple(stipple_quarttone);
649                                 }
650                                 
651                                 glShadeModel(drawSmooth?GL_SMOOTH:GL_FLAT);
652
653                                 glBegin(GL_TRIANGLES);
654
655                                 if (!drawSmooth) {
656                                         glNormal3fv(bmdm->faceNos[i]);
657                                         glVertex3fv(bmdm->vertexCos[(int) BMINDEX_GET(l[0]->v)]);
658                                         glVertex3fv(bmdm->vertexCos[(int) BMINDEX_GET(l[1]->v)]);
659                                         glVertex3fv(bmdm->vertexCos[(int) BMINDEX_GET(l[2]->v)]);
660                                 } else {
661                                         glNormal3fv(bmdm->vertexNos[(int) BMINDEX_GET(l[0]->v)]);
662                                         glVertex3fv(bmdm->vertexCos[(int) BMINDEX_GET(l[0]->v)]);
663                                         glNormal3fv(bmdm->vertexNos[(int) BMINDEX_GET(l[1]->v)]);
664                                         glVertex3fv(bmdm->vertexCos[(int) BMINDEX_GET(l[1]->v)]);
665                                         glNormal3fv(bmdm->vertexNos[(int) BMINDEX_GET(l[2]->v)]);
666                                         glVertex3fv(bmdm->vertexCos[(int) BMINDEX_GET(l[2]->v)]);
667                                 }
668                                 glEnd();
669
670                                 if (draw==2)
671                                         glDisable(GL_POLYGON_STIPPLE);
672                         }
673                 }
674         } else {
675                 efa = BMIter_New(&iter, bmdm->tc->bm, BM_FACES_OF_MESH, NULL);
676                 for (i=0; efa; efa=BMIter_Step(&iter), i++)
677                         BMINDEX_SET(efa, i);
678
679                 for (i=0; i<bmdm->tc->tottri; i++) {
680                         BMLoop **l = bmdm->tc->looptris[i];
681                         int drawSmooth;
682
683                         efa = l[0]->f;
684                         drawSmooth = (efa->head.flag & BM_SMOOTH);
685                         
686                         draw = setDrawOptions==NULL ? 1 : setDrawOptions(userData, BMINDEX_GET(efa), &drawSmooth);
687                         if(draw) {
688                                 if (draw==2) { /* enabled with stipple */
689                                         glEnable(GL_POLYGON_STIPPLE);
690                                         glPolygonStipple(stipple_quarttone);
691                                 }
692                                 glShadeModel(drawSmooth?GL_SMOOTH:GL_FLAT);
693                                 
694                                 glBegin(GL_TRIANGLES);
695                                 if (!drawSmooth) {
696                                         glNormal3fv(efa->no);
697                                         glVertex3fv(l[0]->v->co);
698                                         glVertex3fv(l[1]->v->co);
699                                         glVertex3fv(l[2]->v->co);
700                                 } else {
701                                         glNormal3fv(l[0]->v->no);
702                                         glVertex3fv(l[0]->v->co);
703                                         glNormal3fv(l[1]->v->no);
704                                         glVertex3fv(l[1]->v->co);
705                                         glNormal3fv(l[2]->v->no);
706                                         glVertex3fv(l[2]->v->co);
707                                 }
708                                 glEnd();
709                                 
710                                 if (draw==2)
711                                         glDisable(GL_POLYGON_STIPPLE);
712                         }
713                 }
714         }
715 }
716
717 static void bmdm_get_tri_tex(BMesh *bm, BMLoop **ls, MLoopUV *luv[3], MLoopCol *lcol[3], 
718                              int has_uv, int has_col)
719 {
720         if (has_uv) { 
721                 luv[0] = CustomData_bmesh_get(&bm->ldata, ls[0]->head.data, CD_MLOOPUV);
722                 luv[1] = CustomData_bmesh_get(&bm->ldata, ls[1]->head.data, CD_MLOOPUV);
723                 luv[2] = CustomData_bmesh_get(&bm->ldata, ls[2]->head.data, CD_MLOOPUV);
724         }
725
726         if (has_col) {
727                 lcol[0] = CustomData_bmesh_get(&bm->ldata, ls[0]->head.data, CD_MLOOPCOL);
728                 lcol[1] = CustomData_bmesh_get(&bm->ldata, ls[1]->head.data, CD_MLOOPCOL);
729                 lcol[2] = CustomData_bmesh_get(&bm->ldata, ls[2]->head.data, CD_MLOOPCOL);
730         }
731
732
733 }
734
735 static void bmDM_drawFacesTex_common(DerivedMesh *dm,
736                int (*drawParams)(MTFace *tface, int has_vcol, int matnr),
737                int (*drawParamsMapped)(void *userData, int index),
738                void *userData) 
739 {
740         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
741         BMEditMesh *em = bmdm->tc;
742         BMesh *bm= bmdm->tc->bm;
743         float (*vertexCos)[3]= bmdm->vertexCos;
744         float (*vertexNos)[3]= bmdm->vertexNos;
745         BMFace *efa;
746         BMVert *eve;
747         BMIter iter;
748         MLoopUV *luv[3], dummyluv = {0};
749         MLoopCol *lcol[3], dummylcol = {0};
750         int i, has_vcol = CustomData_has_layer(&bm->ldata, CD_MLOOPCOL);
751         int has_uv = CustomData_has_layer(&bm->pdata, CD_MTEXPOLY);
752         
753         luv[0] = luv[1] = luv[2] = &dummyluv;
754         lcol[0] = lcol[1] = lcol[2] = &dummylcol;
755
756         dummylcol.a = dummylcol.r = dummylcol.g = dummylcol.b = 255;
757
758         /* always use smooth shading even for flat faces, else vertex colors wont interpolate */
759         glShadeModel(GL_SMOOTH);
760         
761         i = 0;
762         BM_ITER(efa, &iter, bm, BM_FACES_OF_MESH, NULL)
763                 BMINDEX_SET(efa, i++);
764
765         if (vertexCos) {
766                 i = 0;
767                 BM_ITER(eve, &iter, bm, BM_VERTS_OF_MESH, NULL)
768                         BMINDEX_SET(eve, i++);
769                                 
770                 glBegin(GL_TRIANGLES);
771                 for (i=0; i<em->tottri; i++) {
772                         BMLoop **ls = em->looptris[i];
773                         MTexPoly *tp= CustomData_bmesh_get(&bm->pdata, ls[0]->f->head.data, CD_MTEXPOLY);
774                         MTFace mtf = {0};
775                         unsigned char *cp= NULL;
776                         int drawSmooth= BM_TestHFlag(ls[0]->f, BM_SMOOTH);
777                         int flag;
778
779                         efa = ls[0]->f;
780                         
781                         if (has_uv) {
782                                 mtf.flag = tp->flag;
783                                 mtf.tpage = tp->tpage;
784                                 mtf.transp = tp->transp;
785                                 mtf.mode = tp->mode;
786                                 mtf.tile = tp->tile;
787                                 mtf.unwrap = tp->unwrap;
788                         }
789
790                         if(drawParams)
791                                 flag= drawParams(&mtf, has_vcol, efa->mat_nr);
792                         else if(drawParamsMapped)
793                                 flag= drawParamsMapped(userData, BMINDEX_GET(efa));
794                         else
795                                 flag= 1;
796
797                         if(flag != 0) { /* flag 0 == the face is hidden or invisible */
798                                 
799                                 /* we always want smooth here since otherwise vertex colors dont interpolate */
800                                 if (!has_vcol) {
801                                         glShadeModel(drawSmooth?GL_SMOOTH:GL_FLAT);
802                                 } 
803                                 
804                                 if (!drawSmooth) {
805                                         glNormal3fv(bmdm->faceNos[i]);
806                                         
807                                         bmdm_get_tri_tex(bm, ls, luv, lcol, has_uv, has_vcol);
808                                         
809                                         glTexCoord2fv(luv[0]->uv);
810                                         glColor3ub(lcol[0]->r, lcol[0]->g, lcol[0]->b);
811                                         glVertex3fv(vertexCos[BMINDEX_GET(ls[0]->v)]);
812
813                                         glTexCoord2fv(luv[1]->uv);
814                                         glColor3ub(lcol[1]->r, lcol[1]->g, lcol[1]->b);
815                                         glVertex3fv(vertexCos[BMINDEX_GET(ls[1]->v)]);
816
817                                         glTexCoord2fv(luv[2]->uv);
818                                         glColor3ub(lcol[2]->r, lcol[2]->g, lcol[2]->b);
819                                         glVertex3fv(vertexCos[BMINDEX_GET(ls[2]->v)]);
820                                 } else {
821                                         bmdm_get_tri_tex(bm, ls, luv, lcol, has_uv, has_vcol);
822                                         
823                                         glTexCoord2fv(luv[0]->uv);
824                                         glColor3ub(lcol[0]->r, lcol[0]->g, lcol[0]->b);
825                                         glNormal3fv(vertexNos[BMINDEX_GET(ls[0]->v)]);
826                                         glVertex3fv(vertexCos[BMINDEX_GET(ls[0]->v)]);
827
828                                         glTexCoord2fv(luv[1]->uv);
829                                         glColor3ub(lcol[1]->r, lcol[1]->g, lcol[1]->b);
830                                         glNormal3fv(vertexNos[BMINDEX_GET(ls[1]->v)]);
831                                         glVertex3fv(vertexCos[BMINDEX_GET(ls[1]->v)]);
832
833                                         glTexCoord2fv(luv[2]->uv);
834                                         glColor3ub(lcol[2]->r, lcol[2]->g, lcol[2]->b);
835                                         glNormal3fv(vertexNos[BMINDEX_GET(ls[2]->v)]);
836                                         glVertex3fv(vertexCos[BMINDEX_GET(ls[2]->v)]);
837                                 }
838                         }
839                 }
840                 glEnd();
841         } else {
842                 i = 0;
843                 BM_ITER(eve, &iter, bm, BM_VERTS_OF_MESH, NULL)
844                         BMINDEX_SET(eve, i++);
845                                 
846                 for (i=0; i<em->tottri; i++) {
847                         BMLoop **ls = em->looptris[i];
848                         MTexPoly *tp= CustomData_bmesh_get(&bm->pdata, ls[0]->f->head.data, CD_MTEXPOLY);
849                         MTFace mtf = {0};
850                         unsigned char *cp= NULL;
851                         int drawSmooth= BM_TestHFlag(ls[0]->f, BM_SMOOTH);
852                         int flag;
853
854                         efa = ls[0]->f;
855                         
856                         if (has_uv) {
857                                 mtf.flag = tp->flag;
858                                 mtf.tpage = tp->tpage;
859                                 mtf.transp = tp->transp;
860                                 mtf.mode = tp->mode;
861                                 mtf.tile = tp->tile;
862                                 mtf.unwrap = tp->unwrap;
863                         }
864
865                         if(drawParams)
866                                 flag= drawParams(&mtf, has_vcol, efa->mat_nr);
867                         else if(drawParamsMapped)
868                                 flag= drawParamsMapped(userData, BMINDEX_GET(efa));
869                         else
870                                 flag= 1;
871
872                         if(flag != 0) { /* flag 0 == the face is hidden or invisible */
873                                 
874                                 /* we always want smooth here since otherwise vertex colors dont interpolate */
875                                 if (!has_vcol) {
876                                         glShadeModel(drawSmooth?GL_SMOOTH:GL_FLAT);
877                                 } 
878                                 
879                                 glBegin(GL_TRIANGLES);
880                                 if (!drawSmooth) {
881                                         glNormal3fv(efa->no);
882                                         
883                                         bmdm_get_tri_tex(bm, ls, luv, lcol, has_uv, has_vcol);
884                                         
885                                         glTexCoord2fv(luv[0]->uv);
886                                         glColor3ub(lcol[0]->r, lcol[0]->g, lcol[0]->b);
887                                         glVertex3fv(ls[0]->v->co);
888
889                                         glTexCoord2fv(luv[1]->uv);
890                                         glColor3ub(lcol[1]->r, lcol[1]->g, lcol[1]->b);
891                                         glVertex3fv(ls[1]->v->co);
892
893                                         glTexCoord2fv(luv[2]->uv);
894                                         glColor3ub(lcol[2]->r, lcol[2]->g, lcol[2]->b);
895                                         glVertex3fv(ls[2]->v->co);
896                                 } else {
897                                         bmdm_get_tri_tex(bm, ls, luv, lcol, has_uv, has_vcol);
898                                         
899                                         glTexCoord2fv(luv[0]->uv);
900                                         glColor3ub(lcol[0]->r, lcol[0]->g, lcol[0]->b);
901                                         glNormal3fv(ls[0]->v->no);
902                                         glVertex3fv(ls[0]->v->co);
903
904                                         glTexCoord2fv(luv[1]->uv);
905                                         glColor3ub(lcol[1]->r, lcol[1]->g, lcol[1]->b);
906                                         glNormal3fv(ls[1]->v->no);
907                                         glVertex3fv(ls[1]->v->co);
908
909                                         glTexCoord2fv(luv[2]->uv);
910                                         glColor3ub(lcol[2]->r, lcol[2]->g, lcol[2]->b);
911                                         glNormal3fv(ls[2]->v->no);
912                                         glVertex3fv(ls[2]->v->co);
913                                 }
914                                 glEnd();
915                         }
916                 }
917         }
918 }
919
920 static void bmDM_drawFacesTex(DerivedMesh *dm, int (*setDrawOptions)(MTFace *tface, int has_vcol, int matnr))
921 {
922         bmDM_drawFacesTex_common(dm, setDrawOptions, NULL, NULL);
923 }
924
925 static void bmDM_drawMappedFacesTex(DerivedMesh *dm, int (*setDrawOptions)(void *userData, int index), void *userData)
926 {
927         bmDM_drawFacesTex_common(dm, NULL, setDrawOptions, userData);
928 }
929
930 static void bmDM_drawMappedFacesGLSL(DerivedMesh *dm,
931                int (*setMaterial)(int, void *attribs),
932                int (*setDrawOptions)(void *userData, int index), void *userData) 
933 {
934 #if 0
935         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
936         BMesh *bm= bmdm->tc->bm;
937         float (*vertexCos)[3]= bmdm->vertexCos;
938         float (*vertexNos)[3]= bmdm->vertexNos;
939         BMVert *eve;
940         BMFace *efa;
941         DMVertexAttribs attribs;
942         GPUVertexAttribs gattribs;
943         MTFace *tf;
944         int transp, new_transp, orig_transp, tfoffset;
945         int i, b, matnr, new_matnr, dodraw, layer;
946
947         dodraw = 0;
948         matnr = -1;
949
950         transp = GPU_get_material_blend_mode();
951         orig_transp = transp;
952         layer = CustomData_get_layer_index(&bm->pdata, CD_MTFACE);
953         tfoffset = (layer == -1)? -1: bm->pdata.layers[layer].offset;
954
955         memset(&attribs, 0, sizeof(attribs));
956
957         /* always use smooth shading even for flat faces, else vertex colors wont interpolate */
958         glShadeModel(GL_SMOOTH);
959
960         for (i=0,eve=bm->verts.first; eve; eve= eve->next)
961                 BMINDEX_SET(eve, i++);
962
963 #define PASSATTRIB(efa, eve, vert) {                                                                                    \
964         if(attribs.totorco) {                                                                                                           \
965                 float *orco = attribs.orco.array[BMINDEX_GET(eve)];                                                     \
966                 glVertexAttrib3fvARB(attribs.orco.glIndex, orco);                                               \
967         }                                                                                                                                                       \
968         for(b = 0; b < attribs.tottface; b++) {                                                                         \
969                 MTFace *_tf = (MTFace*)((char*)efa->data + attribs.tface[b].bmOffset);  \
970                 glVertexAttrib2fvARB(attribs.tface[b].glIndex, _tf->uv[vert]);                  \
971         }                                                                                                                                                       \
972         for(b = 0; b < attribs.totmcol; b++) {                                                                          \
973                 MCol *cp = (MCol*)((char*)efa->data + attribs.mcol[b].bmOffset);                \
974                 GLubyte col[4];                                                                                                                 \
975                 col[0]= cp->b; col[1]= cp->g; col[2]= cp->r; col[3]= cp->a;                             \
976                 glVertexAttrib4ubvARB(attribs.mcol[b].glIndex, col);                                    \
977         }                                                                                                                                                       \
978         if(attribs.tottang) {                                                                                                           \
979                 float *tang = attribs.tang.array[i*4 + vert];                                                   \
980                 glVertexAttrib3fvARB(attribs.tang.glIndex, tang);                                               \
981         }                                                                                                                                                       \
982 }
983
984         for (i=0,efa= bm->faces.first; efa; i++,efa= efa->next) {
985                 int drawSmooth= (efa->flag & ME_SMOOTH);
986
987                 if(setDrawOptions && !setDrawOptions(userData, i))
988                         continue;
989
990                 new_matnr = efa->mat_nr + 1;
991                 if(new_matnr != matnr) {
992                         dodraw = setMaterial(matnr = new_matnr, &gattribs);
993                         if(dodraw)
994                                 DM_vertex_attributes_from_gpu(dm, &gattribs, &attribs);
995                 }
996
997                 if(tfoffset != -1) {
998                         tf = (MTFace*)((char*)efa->data)+tfoffset;
999                         new_transp = tf->transp;
1000
1001                         if(new_transp != transp) {
1002                                 if(new_transp == GPU_BLEND_SOLID && orig_transp != GPU_BLEND_SOLID)
1003                                         GPU_set_material_blend_mode(orig_transp);
1004                                 else
1005                                         GPU_set_material_blend_mode(new_transp);
1006                                 transp = new_transp;
1007                         }
1008                 }
1009
1010                 if(dodraw) {
1011                         glBegin(efa->v4?GL_QUADS:GL_TRIANGLES);
1012                         if (!drawSmooth) {
1013                                 if(vertexCos) glNormal3fv(bmdm->faceNos[i]);
1014                                 else glNormal3fv(efa->n);
1015
1016                                 PASSATTRIB(efa, efa->v1, 0);
1017                                 if(vertexCos) glVertex3fv(vertexCos[(int) efa->v1->tmp.l]);
1018                                 else glVertex3fv(efa->v1->co);
1019
1020                                 PASSATTRIB(efa, efa->v2, 1);
1021                                 if(vertexCos) glVertex3fv(vertexCos[(int) efa->v2->tmp.l]);
1022                                 else glVertex3fv(efa->v2->co);
1023
1024                                 PASSATTRIB(efa, efa->v3, 2);
1025                                 if(vertexCos) glVertex3fv(vertexCos[(int) efa->v3->tmp.l]);
1026                                 else glVertex3fv(efa->v3->co);
1027
1028                                 if(efa->v4) {
1029                                         PASSATTRIB(efa, efa->v4, 3);
1030                                         if(vertexCos) glVertex3fv(vertexCos[(int) efa->v4->tmp.l]);
1031                                         else glVertex3fv(efa->v4->co);
1032                                 }
1033                         } else {
1034                                 PASSATTRIB(efa, efa->v1, 0);
1035                                 if(vertexCos) {
1036                                         glNormal3fv(vertexNos[(int) efa->v1->tmp.l]);
1037                                         glVertex3fv(vertexCos[(int) efa->v1->tmp.l]);
1038                                 }
1039                                 else {
1040                                         glNormal3fv(efa->v1->no);
1041                                         glVertex3fv(efa->v1->co);
1042                                 }
1043
1044                                 PASSATTRIB(efa, efa->v2, 1);
1045                                 if(vertexCos) {
1046                                         glNormal3fv(vertexNos[(int) efa->v2->tmp.l]);
1047                                         glVertex3fv(vertexCos[(int) efa->v2->tmp.l]);
1048                                 }
1049                                 else {
1050                                         glNormal3fv(efa->v2->no);
1051                                         glVertex3fv(efa->v2->co);
1052                                 }
1053
1054                                 PASSATTRIB(efa, efa->v3, 2);
1055                                 if(vertexCos) {
1056                                         glNormal3fv(vertexNos[(int) efa->v3->tmp.l]);
1057                                         glVertex3fv(vertexCos[(int) efa->v3->tmp.l]);
1058                                 }
1059                                 else {
1060                                         glNormal3fv(efa->v3->no);
1061                                         glVertex3fv(efa->v3->co);
1062                                 }
1063
1064                                 if(efa->v4) {
1065                                         PASSATTRIB(efa, efa->v4, 3);
1066                                         if(vertexCos) {
1067                                                 glNormal3fv(vertexNos[(int) efa->v4->tmp.l]);
1068                                                 glVertex3fv(vertexCos[(int) efa->v4->tmp.l]);
1069                                         }
1070                                         else {
1071                                                 glNormal3fv(efa->v4->no);
1072                                                 glVertex3fv(efa->v4->co);
1073                                         }
1074                                 }
1075                         }
1076                         glEnd();
1077                 }
1078         }
1079 #endif
1080 }
1081
1082 static void bmDM_drawFacesGLSL(DerivedMesh *dm,
1083                int (*setMaterial)(int, void *attribs))
1084 {
1085         dm->drawMappedFacesGLSL(dm, setMaterial, NULL, NULL);
1086 }
1087
1088 static void bmDM_getMinMax(DerivedMesh *dm, float min_r[3], float max_r[3])
1089 {
1090         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
1091         BMVert *eve;
1092         BMIter iter;
1093         int i;
1094
1095         if (bmdm->tc->bm->verts.first) {
1096                 eve = BMIter_New(&iter, bmdm->tc->bm, BM_VERTS_OF_MESH, NULL);
1097                 for (i=0; eve; eve=BMIter_Step(&iter), i++) {
1098                         if (bmdm->vertexCos) {
1099                                 DO_MINMAX(bmdm->vertexCos[i], min_r, max_r);
1100                         } else {
1101                                 DO_MINMAX(eve->co, min_r, max_r);
1102                         }
1103                 }
1104         } else {
1105                 min_r[0] = min_r[1] = min_r[2] = max_r[0] = max_r[1] = max_r[2] = 0.0;
1106         }
1107 }
1108 static int bmDM_getNumVerts(DerivedMesh *dm)
1109 {
1110         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
1111
1112         return bmdm->tc->bm->totvert;
1113 }
1114
1115 static int bmDM_getNumEdges(DerivedMesh *dm)
1116 {
1117         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
1118
1119         return bmdm->tc->bm->totedge;
1120 }
1121
1122 static int bmDM_getNumTessFaces(DerivedMesh *dm)
1123 {
1124         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
1125         
1126         return bmdm->tc->tottri;
1127 }
1128
1129 static int bmDM_getNumFaces(DerivedMesh *dm)
1130 {
1131         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
1132         
1133         return bmdm->tc->bm->totface;
1134 }
1135
1136 static int bmvert_to_mvert(BMVert *ev, MVert *vert_r)
1137 {
1138         VECCOPY(vert_r->co, ev->co);
1139
1140         vert_r->no[0] = (short)(ev->no[0] * 32767.0f);
1141         vert_r->no[1] = (short)(ev->no[1] * 32767.0f);
1142         vert_r->no[2] = (short)(ev->no[2] * 32767.0f);
1143
1144         /* TODO what to do with vert_r->flag and vert_r->mat_nr? */
1145         vert_r->flag = BMFlags_To_MEFlags(ev);
1146         vert_r->mat_nr = 0;
1147         vert_r->bweight = (unsigned char) (ev->bweight*255.0f);
1148 }
1149
1150 static void bmDM_getVert(DerivedMesh *dm, int index, MVert *vert_r)
1151 {
1152         BMVert *ev;
1153         BMIter iter;
1154         int i;
1155
1156         if (index < 0 || index >= ((EditDerivedBMesh *)dm)->tv) {
1157                 printf("error in bmDM_getVert.\n");
1158                 return;
1159         }
1160
1161         ev = ((EditDerivedBMesh *)dm)->vtable[index];
1162         bmvert_to_mvert(ev, vert_r);
1163 }
1164
1165 static void bmDM_getEdge(DerivedMesh *dm, int index, MEdge *edge_r)
1166 {
1167         EditDerivedBMesh *bmdm = (EditDerivedBMesh *)dm;
1168         BMesh *bm = ((EditDerivedBMesh *)dm)->tc->bm;
1169         BMEdge *e;
1170         BMVert *ev, *v1, *v2;
1171         BMIter iter;
1172         int i;
1173
1174         if (index < 0 || index >= ((EditDerivedBMesh *)dm)->te) {
1175                 printf("error in bmDM_getEdge.\n");
1176                 return;
1177         }
1178
1179         e = bmdm->etable[index];
1180
1181         edge_r->crease = (unsigned char) (e->crease*255.0f);
1182         edge_r->bweight = (unsigned char) (e->bweight*255.0f);
1183         /* TODO what to do with edge_r->flag? */
1184         edge_r->flag = ME_EDGEDRAW|ME_EDGERENDER;
1185         edge_r->flag |= BMFlags_To_MEFlags(e);
1186 #if 0
1187         /* this needs setup of f2 field */
1188         if (!ee->f2) edge_r->flag |= ME_LOOSEEDGE;
1189 #endif
1190         
1191         edge_r->v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(bmdm->vhash, e->v1));
1192         edge_r->v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(bmdm->vhash, e->v2));
1193 }
1194
1195 static void bmDM_getTessFace(DerivedMesh *dm, int index, MFace *face_r)
1196 {
1197         EditDerivedBMesh *bmdm = (EditDerivedBMesh *)dm;
1198         BMesh *bm = bmdm->tc->bm;
1199         BMFace *ef;
1200         BMIter iter;
1201         BMLoop **l;
1202         int i;
1203         
1204         if (index < 0 || index >= ((EditDerivedBMesh *)dm)->tf) {
1205                 printf("error in bmDM_getTessFace.\n");
1206                 return;
1207         }
1208
1209         l = ((EditDerivedBMesh *)dm)->tc->looptris[index];
1210
1211         ef = l[0]->f;
1212
1213         face_r->mat_nr = (unsigned char) ef->mat_nr;
1214         face_r->flag = BMFlags_To_MEFlags(ef);
1215
1216         face_r->v1 = GET_INT_FROM_POINTER(BLI_ghash_lookup(bmdm->vhash, l[0]->v));
1217         face_r->v2 = GET_INT_FROM_POINTER(BLI_ghash_lookup(bmdm->vhash, l[1]->v));
1218         face_r->v3 = GET_INT_FROM_POINTER(BLI_ghash_lookup(bmdm->vhash, l[2]->v));
1219         face_r->v4 = 0;
1220
1221         test_index_face(face_r, NULL, 0, 3);
1222 }
1223
1224 static void bmDM_copyVertArray(DerivedMesh *dm, MVert *vert_r)
1225 {
1226         BMesh *bm = ((EditDerivedBMesh *)dm)->tc->bm;
1227         BMVert *ev;
1228         BMIter iter;
1229
1230         ev = BMIter_New(&iter, bm, BM_VERTS_OF_MESH, NULL);
1231         for( ; ev; ev = BMIter_Step(&iter), ++vert_r) {
1232                 VECCOPY(vert_r->co, ev->co);
1233
1234                 vert_r->no[0] = (short) (ev->no[0] * 32767.0);
1235                 vert_r->no[1] = (short) (ev->no[1] * 32767.0);
1236                 vert_r->no[2] = (short) (ev->no[2] * 32767.0);
1237
1238                 /* TODO what to do with vert_r->flag and vert_r->mat_nr? */
1239                 vert_r->mat_nr = 0;
1240                 vert_r->flag = BMFlags_To_MEFlags(ev);
1241                 vert_r->bweight = (unsigned char) (ev->bweight*255.0f);
1242         }
1243 }
1244
1245 static void bmDM_copyEdgeArray(DerivedMesh *dm, MEdge *edge_r)
1246 {
1247         BMesh *bm = ((EditDerivedBMesh *)dm)->tc->bm;
1248         BMEdge *ee;
1249         BMIter iter;
1250         BMVert *ev;
1251         int i;
1252
1253         /* store vertex indices in tmp union */
1254         ev = BMIter_New(&iter, bm, BM_VERTS_OF_MESH, NULL);
1255         for (i=0; ev; ev=BMIter_Step(&iter), i++)
1256                 BMINDEX_SET(ev, i);
1257
1258         ee = BMIter_New(&iter, bm, BM_EDGES_OF_MESH, NULL);
1259         for( ; ee; ee=BMIter_Step(&iter)) {
1260                 edge_r->crease = (unsigned char) (ee->crease*255.0f);
1261                 edge_r->bweight = (unsigned char) (ee->bweight*255.0f);
1262                 /* TODO what to do with edge_r->flag? */
1263                 edge_r->flag = ME_EDGEDRAW|ME_EDGERENDER;
1264                 if (ee->head.flag & BM_SEAM) edge_r->flag |= ME_SEAM;
1265                 if (ee->head.flag & BM_SHARP) edge_r->flag |= ME_SHARP;
1266 #if 0
1267                 /* this needs setup of f2 field */
1268                 if (!ee->f2) edge_r->flag |= ME_LOOSEEDGE;
1269 #endif
1270
1271                 edge_r->v1 = (int)BMINDEX_GET(ee->v1);
1272                 edge_r->v2 = (int)BMINDEX_GET(ee->v2);
1273         }
1274 }
1275
1276 static void bmDM_copyFaceArray(DerivedMesh *dm, MFace *face_r)
1277 {
1278         EditDerivedBMesh *bmdm = (EditDerivedBMesh *)dm;
1279         BMesh *bm = ((EditDerivedBMesh *)dm)->tc->bm;
1280         BMFace *ef;
1281         BMVert *ev;
1282         BMIter iter;
1283         BMLoop **l;
1284         int i;
1285
1286         /* store vertexes indices in tmp union */
1287         ev = BMIter_New(&iter, bm, BM_VERTS_OF_MESH, NULL);
1288         for (i=0; ev; ev=BMIter_Step(&iter), i++)
1289                 BMINDEX_SET(ev, i);
1290
1291         for (i=0; i<bmdm->tc->tottri; i++) {
1292                 l = bmdm->tc->looptris[i];
1293                 ef = l[0]->f;
1294
1295                 face_r->mat_nr = (unsigned char) ef->mat_nr;
1296
1297                 /*HACK/TODO: need to convert this*/
1298                 face_r->flag = ef->head.flag;
1299
1300                 face_r->v1 = BMINDEX_GET(l[0]->v);
1301                 face_r->v2 = BMINDEX_GET(l[1]->v);
1302                 face_r->v3 = BMINDEX_GET(l[2]->v);
1303                 face_r->v4 = 0;
1304
1305                 test_index_face(face_r, NULL, 0, 3);
1306         }
1307 }
1308
1309 static void *bmDM_getFaceDataArray(DerivedMesh *dm, int type)
1310 {
1311         EditDerivedBMesh *bmdm= (EditDerivedBMesh*) dm;
1312         BMesh *bm= bmdm->tc->bm;
1313         BMFace *efa;
1314         char *data, *bmdata;
1315         void *datalayer;
1316         int index, offset, size, i;
1317
1318         datalayer = DM_get_tessface_data_layer(dm, type);
1319         if(datalayer)
1320                 return datalayer;
1321
1322         /* layers are store per face for editmesh, we convert to a tbmporary
1323          * data layer array in the derivedmesh when these are requested */
1324         if(type == CD_MTFACE || type == CD_MCOL) {
1325                 index = CustomData_get_layer_index(&bm->pdata, type);
1326
1327                 if(index != -1) {
1328                         offset = bm->pdata.layers[index].offset;
1329                         size = CustomData_sizeof(type);
1330
1331                         DM_add_tessface_layer(dm, type, CD_CALLOC, NULL);
1332                         index = CustomData_get_layer_index(&dm->faceData, type);
1333                         dm->faceData.layers[index].flag |= CD_FLAG_TEMPORARY;
1334
1335                         data = datalayer = DM_get_tessface_data_layer(dm, type);
1336                         for (i=0; i<bmdm->tc->tottri; i++, data+=size) {
1337                                 efa = bmdm->tc->looptris[i][0]->f;
1338                                 /*BMESH_TODO: need to still add tface data,
1339                                   derived from the loops.*/
1340                                 bmdata = CustomData_bmesh_get(&bm->pdata, efa->head.data, type);
1341                                 memcpy(data, bmdata, size);
1342                         }
1343                 }
1344         }
1345
1346         return datalayer;
1347 }
1348
1349 typedef struct bmDM_loopIter {
1350         DMLoopIter head;
1351
1352         BMFace *f;
1353         BMLoop *l, *nextl;
1354         BMIter iter;
1355         BMesh *bm;
1356 } bmDM_loopIter;
1357
1358 typedef struct bmDM_faceIter {
1359         DMFaceIter head;
1360
1361         BMFace *f, *nextf;
1362         BMIter iter;
1363         BMesh *bm;
1364
1365         bmDM_loopIter loopiter;
1366 } bmDM_faceIter;
1367
1368 void bmDM_faceIterStep(void *self)
1369 {
1370         bmDM_faceIter *iter = self;
1371         
1372         iter->f = iter->nextf;
1373
1374         iter->head.mat_nr = iter->f->mat_nr;
1375         iter->head.flags = BMFlags_To_MEFlags(iter->f);
1376         iter->head.index++;
1377
1378         iter->head.len = iter->f->len;
1379
1380         iter->nextf = BMIter_Step(&iter->iter);
1381
1382         if (!iter->nextf) iter->head.done = 1;
1383 }
1384
1385 void *bmDM_getFaceCDData(void *self, int type, int layer)
1386 {
1387         bmDM_faceIter *iter = self;
1388
1389         if (layer == -1) 
1390                 return CustomData_bmesh_get(&iter->bm->pdata, iter->f->head.data, type);
1391         else return CustomData_bmesh_get_n(&iter->bm->pdata, iter->f->head.data, type, layer);
1392 }
1393
1394 void bmDM_loopIterStep(void *self)
1395 {
1396         bmDM_loopIter *iter = self;
1397
1398         iter->l = BMIter_Step(&iter->iter);
1399         if (!iter->l) {
1400                 iter->head.done = 1;
1401                 return;
1402         }
1403
1404         bmvert_to_mvert(iter->l->v, &iter->head.v);
1405         iter->head.index++;
1406         iter->head.vindex = BMINDEX_GET(iter->l->v);
1407         iter->head.eindex = BMINDEX_GET(iter->l->e);
1408 }
1409
1410 void *bmDM_getLoopCDData(void *self, int type, int layer)
1411 {
1412         bmDM_loopIter *iter = self;
1413
1414         if (layer == -1) 
1415                 return CustomData_bmesh_get(&iter->bm->ldata, iter->l->head.data, type);
1416         else return CustomData_bmesh_get_n(&iter->bm->ldata, iter->l->head.data, type, layer);
1417 }
1418
1419 void *bmDM_getVertCDData(void *self, int type, int layer)
1420 {
1421         bmDM_loopIter *iter = self;
1422
1423         if (layer == -1) 
1424                 return CustomData_bmesh_get(&iter->bm->vdata, iter->l->v->head.data, type);
1425         else return CustomData_bmesh_get_n(&iter->bm->vdata, iter->l->v->head.data, type, layer);
1426 }
1427
1428 void bmDM_iterFree(void *self)
1429 {
1430         MEM_freeN(self);
1431 }
1432
1433 void bmDM_nulliterFree(void *self)
1434 {
1435 }
1436
1437 DMLoopIter *bmDM_newLoopsIter(void *faceiter)
1438 {
1439         bmDM_faceIter *fiter = faceiter;
1440         bmDM_loopIter *iter = &fiter->loopiter;
1441
1442         memset(&fiter->loopiter, 0, sizeof(bmDM_loopIter));
1443
1444         iter->bm = fiter->bm;
1445         iter->f = fiter->f;
1446         iter->l = BMIter_New(&iter->iter, iter->bm, BM_LOOPS_OF_FACE, iter->f);
1447
1448         iter->head.step = bmDM_loopIterStep;
1449         iter->head.getLoopCDData = bmDM_getLoopCDData;
1450         iter->head.getVertCDData = bmDM_getVertCDData;
1451
1452         bmvert_to_mvert(iter->l->v, &iter->head.v);
1453         iter->head.vindex = BMINDEX_GET(iter->l->v);
1454         iter->head.eindex = BMINDEX_GET(iter->l->e);
1455
1456         return (DMLoopIter*) iter;
1457 }
1458
1459 static DMFaceIter *bmDM_getFaceIter(void *dm)
1460 {
1461         EditDerivedBMesh *bmdm= dm;
1462         bmDM_faceIter *iter = MEM_callocN(sizeof(bmDM_faceIter), "bmDM_faceIter");
1463         BMIter biter;
1464         BMVert *v;
1465         BMEdge *e;
1466         int i;
1467
1468         iter->bm = bmdm->tc->bm;
1469         iter->f = iter->nextf = BMIter_New(&iter->iter, iter->bm, BM_FACES_OF_MESH, NULL);
1470         
1471         iter->head.step = bmDM_faceIterStep;
1472         iter->head.free = bmDM_iterFree;
1473         iter->head.getCDData = bmDM_getFaceCDData;
1474         iter->head.getLoopsIter = bmDM_newLoopsIter;
1475         
1476         iter->head.mat_nr = iter->f->mat_nr;
1477         iter->head.flags = BMFlags_To_MEFlags(iter->f);
1478
1479         /*set up vert/edge indices*/
1480         i = 0;
1481         BM_ITER(v, &biter, iter->bm, BM_VERTS_OF_MESH, NULL) {
1482                 BMINDEX_SET(v, i);
1483                 i++;
1484         }
1485
1486         i = 0;
1487         BM_ITER(e, &biter, iter->bm, BM_EDGES_OF_MESH, NULL) {
1488                 BMINDEX_SET(e, i);
1489                 i++;
1490         }
1491
1492         return (DMFaceIter*) iter;
1493 }
1494
1495 static void bmDM_release(void *dm)
1496 {
1497         EditDerivedBMesh *bmdm= dm;
1498
1499         if (DM_release(dm)) {
1500                 if (bmdm->vertexCos) {
1501                         MEM_freeN(bmdm->vertexCos);
1502                         MEM_freeN(bmdm->vertexNos);
1503                         MEM_freeN(bmdm->faceNos);
1504                 }
1505                 
1506                 if (bmdm->fhash) BLI_ghash_free(bmdm->fhash, NULL, NULL);
1507                 if (bmdm->ehash) BLI_ghash_free(bmdm->ehash, NULL, NULL);
1508                 if (bmdm->vhash) BLI_ghash_free(bmdm->vhash, NULL, NULL);
1509
1510                 if (bmdm->vtable) MEM_freeN(bmdm->vtable);
1511                 if (bmdm->etable) MEM_freeN(bmdm->etable);
1512                 if (bmdm->ftable) MEM_freeN(bmdm->ftable);
1513                 
1514                 MEM_freeN(bmdm);
1515         }
1516 }
1517
1518 CustomData *bmDm_getVertDataLayout(DerivedMesh *dm)
1519 {
1520         EditDerivedBMesh *bmdm = (EditDerivedBMesh*)dm;
1521
1522         return &bmdm->tc->bm->vdata;
1523 }
1524
1525 CustomData *bmDm_getEdgeDataLayout(DerivedMesh *dm)
1526 {
1527         EditDerivedBMesh *bmdm = (EditDerivedBMesh*)dm;
1528
1529         return &bmdm->tc->bm->edata;
1530 }
1531
1532 CustomData *bmDm_getTessFaceDataLayout(DerivedMesh *dm)
1533 {
1534         EditDerivedBMesh *bmdm = (EditDerivedBMesh*)dm;
1535
1536         return &bmdm->tessface_layout;
1537 }
1538
1539 CustomData *bmDm_getLoopDataLayout(DerivedMesh *dm)
1540 {
1541         EditDerivedBMesh *bmdm = (EditDerivedBMesh*)dm;
1542
1543         return &bmdm->tc->bm->ldata;
1544 }
1545
1546 CustomData *bmDm_getFaceDataLayout(DerivedMesh *dm)
1547 {
1548         EditDerivedBMesh *bmdm = (EditDerivedBMesh*)dm;
1549
1550         return &bmdm->tc->bm->pdata;
1551 }
1552
1553
1554 DerivedMesh *getEditDerivedBMesh(BMEditMesh *em, Object *ob,
1555                                            float (*vertexCos)[3])
1556 {
1557         EditDerivedBMesh *bmdm = MEM_callocN(sizeof(*bmdm), "bmdm");
1558         BMesh *bm = em->bm;
1559         int i;
1560         
1561         bmdm->tc = em;
1562
1563         DM_init((DerivedMesh*)bmdm, em->bm->totvert, em->bm->totedge, em->tottri,
1564                  em->bm->totloop, em->bm->totface);
1565         
1566         for (i=0; i<bm->ldata.totlayer; i++) {
1567                 if (bm->ldata.layers[i].type == CD_MLOOPCOL) {
1568                         CustomData_add_layer(&bmdm->tessface_layout, CD_MCOL, CD_ASSIGN, NULL, 0);
1569                 } else if (bm->ldata.layers[i].type == CD_MLOOPUV) {
1570                         CustomData_add_layer(&bmdm->tessface_layout, CD_MTFACE, CD_ASSIGN, NULL, 0);
1571                 }
1572         }
1573
1574         bmdm->dm.numVertData = bm->totvert;
1575         bmdm->dm.numEdgeData = bm->totedge;
1576         bmdm->dm.numFaceData = em->tottri;
1577         bmdm->dm.numLoopData = bm->totloop;
1578         bmdm->dm.numPolyData = bm->totface;
1579
1580         bmdm->dm.getMinMax = bmDM_getMinMax;
1581
1582         bmdm->dm.getVertDataLayout = bmDm_getVertDataLayout;
1583         bmdm->dm.getEdgeDataLayout = bmDm_getEdgeDataLayout;
1584         bmdm->dm.getTessFaceDataLayout = bmDm_getTessFaceDataLayout;
1585         bmdm->dm.getLoopDataLayout = bmDm_getLoopDataLayout;
1586         bmdm->dm.getFaceDataLayout = bmDm_getFaceDataLayout;
1587
1588         bmdm->dm.getNumVerts = bmDM_getNumVerts;
1589         bmdm->dm.getNumEdges = bmDM_getNumEdges;
1590         bmdm->dm.getNumTessFaces = bmDM_getNumTessFaces;
1591         bmdm->dm.getNumFaces = bmDM_getNumFaces;
1592
1593         bmdm->dm.getVert = bmDM_getVert;
1594         bmdm->dm.getEdge = bmDM_getEdge;
1595         bmdm->dm.getTessFace = bmDM_getTessFace;
1596         bmdm->dm.copyVertArray = bmDM_copyVertArray;
1597         bmdm->dm.copyEdgeArray = bmDM_copyEdgeArray;
1598         bmdm->dm.copyTessFaceArray = bmDM_copyFaceArray;
1599         bmdm->dm.getTessFaceDataArray = bmDM_getFaceDataArray;
1600
1601         bmdm->dm.newFaceIter = bmDM_getFaceIter;
1602         bmdm->dm.recalcTesselation = bmDM_recalcTesselation;
1603
1604         bmdm->dm.foreachMappedVert = bmDM_foreachMappedVert;
1605         bmdm->dm.foreachMappedEdge = bmDM_foreachMappedEdge;
1606         bmdm->dm.foreachMappedFaceCenter = bmDM_foreachMappedFaceCenter;
1607
1608         bmdm->dm.drawEdges = bmDM_drawEdges;
1609         bmdm->dm.drawMappedEdges = bmDM_drawMappedEdges;
1610         bmdm->dm.drawMappedEdgesInterp = bmDM_drawMappedEdgesInterp;
1611         bmdm->dm.drawMappedFaces = bmDM_drawMappedFaces;
1612         bmdm->dm.drawMappedFacesTex = bmDM_drawMappedFacesTex;
1613         bmdm->dm.drawMappedFacesGLSL = bmDM_drawMappedFacesGLSL;
1614         bmdm->dm.drawFacesTex = bmDM_drawFacesTex;
1615         bmdm->dm.drawFacesGLSL = bmDM_drawFacesGLSL;
1616         bmdm->dm.drawUVEdges = bmDM_drawUVEdges;
1617
1618         bmdm->dm.release = bmDM_release;
1619         
1620         bmdm->vertexCos = vertexCos;
1621
1622         if(CustomData_has_layer(&bm->vdata, CD_MDEFORMVERT)) {
1623                 BMIter iter;
1624                 BMVert *eve;
1625                 int i;
1626
1627                 DM_add_vert_layer(&bmdm->dm, CD_MDEFORMVERT, CD_CALLOC, NULL);
1628                 
1629                 eve = BMIter_New(&iter, bmdm->tc->bm, BM_VERTS_OF_MESH, NULL);
1630                 for (i=0; eve; eve=BMIter_Step(&iter), i++)
1631                         DM_set_vert_data(&bmdm->dm, i, CD_MDEFORMVERT,
1632                                          CustomData_bmesh_get(&bm->vdata, eve->head.data, CD_MDEFORMVERT));
1633         }
1634
1635         if(vertexCos) {
1636                 BMVert *eve;
1637                 BMIter iter;
1638                 int totface = bmdm->tc->tottri;
1639                 int i;
1640                 
1641                 eve=BMIter_New(&iter, bm, BM_VERTS_OF_MESH, NULL);
1642                 for (i=0; eve; eve=BMIter_Step(&iter), i++)
1643                         BMINDEX_SET(eve, i);
1644
1645                 bmdm->vertexNos = MEM_callocN(sizeof(*bmdm->vertexNos)*i, "bmdm_vno");
1646                 bmdm->faceNos = MEM_mallocN(sizeof(*bmdm->faceNos)*totface, "bmdm_vno");
1647
1648                 for (i=0; i<bmdm->tc->tottri; i++) {
1649                         BMLoop **l = bmdm->tc->looptris[i];
1650                         float *v1 = vertexCos[(int) BMINDEX_GET(l[0]->v)];
1651                         float *v2 = vertexCos[(int) BMINDEX_GET(l[1]->v)];
1652                         float *v3 = vertexCos[(int) BMINDEX_GET(l[2]->v)];
1653                         float *no = bmdm->faceNos[i];
1654                         
1655                         CalcNormFloat(v1, v2, v3, no);
1656                         VecAddf(bmdm->vertexNos[BMINDEX_GET(l[0]->v)], bmdm->vertexNos[BMINDEX_GET(l[0]->v)], no);
1657                         VecAddf(bmdm->vertexNos[BMINDEX_GET(l[1]->v)], bmdm->vertexNos[BMINDEX_GET(l[1]->v)], no);
1658                         VecAddf(bmdm->vertexNos[BMINDEX_GET(l[2]->v)], bmdm->vertexNos[BMINDEX_GET(l[2]->v)], no);
1659                 }
1660
1661                 eve=BMIter_New(&iter, bm, BM_VERTS_OF_MESH, NULL);
1662                 for (i=0; eve; eve=BMIter_Step(&iter), i++) {
1663                         float *no = bmdm->vertexNos[i];
1664                         /* following Mesh convention; we use vertex coordinate itself
1665                          * for normal in this case */
1666                         if (Normalize(no)==0.0) {
1667                                 VECCOPY(no, vertexCos[i]);
1668                                 Normalize(no);
1669                         }
1670                 }
1671         }
1672
1673         //bmdm_recalc_lookups(bmdm);
1674
1675         return (DerivedMesh*) bmdm;
1676 }