Saturday morning first cup of coffee hack (yeah, its a late
[blender.git] / source / blender / src / booleanops.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL/BL DUAL 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. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  * CSG operations. 
32  */
33
34 #include <string.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_ghash.h"
39
40 #include "DNA_material_types.h"
41 #include "DNA_mesh_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_object_types.h"
44 #include "DNA_scene_types.h"
45
46 #include "CSG_BooleanOps.h"
47
48 #include "BKE_booleanops.h"
49 #include "BKE_depsgraph.h"
50 #include "BKE_displist.h"
51 #include "BKE_global.h"
52 #include "BKE_library.h"
53 #include "BKE_material.h"
54 #include "BKE_mesh.h"
55 #include "BKE_object.h"
56 #include "BKE_utildefines.h"
57
58 #include <math.h>
59
60 // TODO check to see how many of these includes are necessary
61
62 #include "BLI_blenlib.h"
63 #include "BLI_arithb.h"
64 #include "BLI_linklist.h"
65 #include "BLI_memarena.h"
66
67 static void ConvertCSGDescriptorsToDLM(
68         DispListMesh *dlm,
69         Object *ob,
70         CSG_MeshPropertyDescriptor *props,
71         CSG_FaceIteratorDescriptor *face_it,
72         CSG_VertexIteratorDescriptor *vertex_it,
73         float parinv[][4]);
74
75 #ifdef HAVE_CONFIG_H
76 #include <config.h>
77 #endif
78
79 /**
80  * Here's the vertex iterator structure used to walk through
81  * the blender vertex structure.
82  */
83
84 typedef struct {
85         Object *ob;
86         Mesh *mesh;
87         int pos;
88 } VertexIt;
89
90 /**
91  * Implementations of local vertex iterator functions.
92  * These describe a blender mesh to the CSG module.
93  */
94
95 static
96         void
97 VertexIt_Destruct(
98         CSG_VertexIteratorDescriptor * iterator
99 ){
100         if (iterator->it) {
101                 // deallocate memory for iterator
102                 MEM_freeN(iterator->it);
103                 iterator->it = 0;
104         }
105         iterator->Done = NULL;
106         iterator->Fill = NULL;
107         iterator->Reset = NULL;
108         iterator->Step = NULL;
109         iterator->num_elements = 0;
110
111 }               
112
113 static
114         int
115 VertexIt_Done(
116         CSG_IteratorPtr it
117 ){
118         VertexIt * iterator = (VertexIt *)it;
119         return(iterator->pos >= iterator->mesh->totvert);
120 }
121         
122
123 static
124         void
125 VertexIt_Fill(
126         CSG_IteratorPtr it,
127         CSG_IVertex *vert
128 ){
129         VertexIt * iterator = (VertexIt *)it;
130         MVert *verts = iterator->mesh->mvert;
131
132         float global_pos[3];
133
134         VecMat4MulVecfl(
135                 global_pos,
136                 iterator->ob->obmat, 
137                 verts[iterator->pos].co
138         );
139
140         vert->position[0] = global_pos[0];
141         vert->position[1] = global_pos[1];
142         vert->position[2] = global_pos[2];
143 }
144
145 static
146         void
147 VertexIt_Step(
148         CSG_IteratorPtr it
149 ){
150         VertexIt * iterator = (VertexIt *)it;
151         iterator->pos ++;
152
153  
154 static
155         void
156 VertexIt_Reset(
157         CSG_IteratorPtr it
158 ){
159         VertexIt * iterator = (VertexIt *)it;
160         iterator->pos = 0;
161 }
162
163 static
164         void
165 VertexIt_Construct(
166         CSG_VertexIteratorDescriptor * output,
167         Object *ob
168 ){
169
170         VertexIt *it;
171         if (output == 0) return;
172
173         // allocate some memory for blender iterator
174         it = (VertexIt *)(MEM_mallocN(sizeof(VertexIt),"Boolean_VIt"));
175         if (it == 0) {
176                 return;
177         }
178         // assign blender specific variables
179         it->ob = ob;
180         it->mesh = ob->data;
181         
182         it->pos = 0;
183
184         // assign iterator function pointers.
185         output->Step = VertexIt_Step;
186         output->Fill = VertexIt_Fill;
187         output->Done = VertexIt_Done;
188         output->Reset = VertexIt_Reset;
189         output->num_elements = it->mesh->totvert;
190         output->it = it;
191 }
192
193 /**
194  * Blender Face iterator
195  */
196
197 typedef struct {
198         Object *ob;
199         Mesh *mesh;
200         int pos;
201 } FaceIt;
202
203
204 static
205         void
206 FaceIt_Destruct(
207         CSG_FaceIteratorDescriptor * iterator
208 ) {
209         MEM_freeN(iterator->it);
210         iterator->Done = NULL;
211         iterator->Fill = NULL;
212         iterator->Reset = NULL;
213         iterator->Step = NULL;
214         iterator->num_elements = 0;
215 }
216
217
218 static
219         int
220 FaceIt_Done(
221         CSG_IteratorPtr it
222 ) {
223         // assume CSG_IteratorPtr is of the correct type.
224         FaceIt * iterator = (FaceIt *)it;
225         return(iterator->pos >= iterator->mesh->totface);
226 }
227
228 static
229         void
230 FaceIt_Fill(
231         CSG_IteratorPtr it,
232         CSG_IFace *face
233 ){
234         // assume CSG_IteratorPtr is of the correct type.
235         FaceIt * face_it = (FaceIt *)it;
236         Object *ob = face_it->ob;
237         MFace *mfaces = face_it->mesh->mface;
238         TFace *tfaces = face_it->mesh->tface;
239         int f_index = face_it->pos;
240         MFace *mface = &mfaces[f_index];
241         FaceData *fdata = face->user_face_data;
242         
243         // ignore lines (faces with mface->v3==0)
244         face->vertex_index[0] = mface->v1;
245         face->vertex_index[1] = mface->v2;
246         face->vertex_index[2] = mface->v3;
247         if (mface->v4) {
248                 face->vertex_index[3] = mface->v4;
249                 face->vertex_number = 4;
250         } else {
251                 face->vertex_number = 3;
252         }
253
254         fdata->faceflag = mface->flag;
255         fdata->material = give_current_material(ob, mface->mat_nr+1);
256
257                 // pack rgba colors.
258         if (tfaces) {
259                 TFace *tface= &tfaces[f_index];
260                 int i;
261
262                 fdata->tpage = tface->tpage;
263                 fdata->flag = tface->flag;
264                 fdata->transp = tface->transp;
265                 fdata->mode = tface->mode;
266                 fdata->tile = tface->tile;
267
268                 for (i=0; i<4; i++) {
269                         FaceVertexData *fvdata= face->user_face_vertex_data[i];
270
271                         fvdata->uv[0] = tface->uv[i][0];
272                         fvdata->uv[1] = tface->uv[i][1];
273                         fvdata->color[0] = (float) ((tface->col[i] >> 24) & 0xff);
274                         fvdata->color[1] = (float) ((tface->col[i] >> 16) & 0xff);
275                         fvdata->color[2] = (float) ((tface->col[i] >> 8) & 0xff);
276                         fvdata->color[3] = (float) ((tface->col[i] >> 0) & 0xff);
277                 }
278         }
279 }
280
281
282 static
283         void
284 FaceIt_Step(
285         CSG_IteratorPtr it
286 ) {
287         FaceIt * face_it = (FaceIt *)it;                
288         face_it->pos ++;
289 }
290
291 static
292         void
293 FaceIt_Reset(
294         CSG_IteratorPtr it
295 ) {
296         FaceIt * face_it = (FaceIt *)it;                
297         face_it->pos = 0;
298 }       
299
300 static
301         void
302 FaceIt_Construct(
303         CSG_FaceIteratorDescriptor * output,
304         Object * ob
305 ){
306
307         FaceIt *it;
308         if (output == 0) return;
309
310         // allocate some memory for blender iterator
311         it = (FaceIt *)(MEM_mallocN(sizeof(FaceIt),"Boolean_FIt"));
312         if (it == 0) {
313                 return ;
314         }
315         // assign blender specific variables
316         it->ob = ob;
317         it->mesh = ob->data;
318         it->pos = 0;
319
320         // assign iterator function pointers.
321         output->Step = FaceIt_Step;
322         output->Fill = FaceIt_Fill;
323         output->Done = FaceIt_Done;
324         output->Reset = FaceIt_Reset;
325         output->num_elements = it->mesh->totface;
326         output->it = it;
327 }
328
329
330 /**
331  * Interpolation functions for various user data types.
332  */
333         
334         int
335 InterpNoUserData(
336         void *d1,
337         void *d2,
338         void *dnew,
339         float epsilon
340 ) {
341         // nothing to do of course.
342         return 0;
343 }
344
345         int
346 InterpFaceVertexData(
347         void *d1,
348         void *d2,
349         void *dnew,
350         float epsilon
351 ) {
352         /* XXX, passed backwards, should be fixed inside
353          * BSP lib I guess.
354          */
355         FaceVertexData *fv1 = d2;
356         FaceVertexData *fv2 = d1;
357         FaceVertexData *fvO = dnew;
358
359         fvO->uv[0] = (fv2->uv[0] - fv1->uv[0]) * epsilon + fv1->uv[0]; 
360         fvO->uv[1] = (fv2->uv[1] - fv1->uv[1]) * epsilon + fv1->uv[1]; 
361         fvO->color[0] = (fv2->color[0] - fv1->color[0]) * epsilon + fv1->color[0]; 
362         fvO->color[1] = (fv2->color[1] - fv1->color[1]) * epsilon + fv1->color[1]; 
363         fvO->color[2] = (fv2->color[2] - fv1->color[2]) * epsilon + fv1->color[2]; 
364         fvO->color[3] = (fv2->color[3] - fv1->color[3]) * epsilon + fv1->color[3]; 
365
366         return 0;
367 }
368
369 /**
370  * Assumes mesh is valid and forms part of a fresh
371  * blender object.
372  */
373 DispListMesh *NewBooleanMeshDLM(Object *ob, Object *ob_select, int int_op_type)
374 {
375         Mesh *me2 = get_mesh(ob_select);
376         Mesh *me = get_mesh(ob);
377         int free_tface1,free_tface2;
378         DispListMesh *dlm = NULL;
379
380         float inv_mat[4][4];
381         int success = 0;
382         // build and fill new descriptors for these meshes
383         CSG_VertexIteratorDescriptor vd_1;
384         CSG_VertexIteratorDescriptor vd_2;
385         CSG_FaceIteratorDescriptor fd_1;
386         CSG_FaceIteratorDescriptor fd_2;
387
388         CSG_MeshPropertyDescriptor mpd1,mpd2;
389
390         // work out the operation they chose and pick the appropriate 
391         // enum from the csg module.
392
393         CSG_OperationType op_type;
394
395         if (me == NULL || me2 == NULL) return 0;
396
397         if(!me->totface || !me2->totface) return 0;
398         
399         success = 0;
400
401         switch (int_op_type) {
402                 case 1 : op_type = e_csg_intersection; break;
403                 case 2 : op_type = e_csg_union; break;
404                 case 3 : op_type = e_csg_difference; break;
405                 case 4 : op_type = e_csg_classify; break;
406                 default : op_type = e_csg_intersection;
407         }
408
409         // Here is the section where we describe the properties of
410         // both meshes to the bsp module.
411
412         if (me->mcol != NULL) {
413                 // Then this mesh has vertex colors only 
414                 // well this is awkward because there is no equivalent 
415                 // test_index_mface just for vertex colors!
416                 // as a temporary hack we can convert these vertex colors 
417                 // into tfaces do the operation and turn them back again.
418
419                 // create some memory for the tfaces.
420                 me->tface = (TFace *)MEM_callocN(sizeof(TFace)*me->totface,"BooleanOps_TempTFace");
421                 mcol_to_tface(me,1);
422                 free_tface1 = 1;
423         } else {
424                 free_tface1 = 0;
425         }
426
427         mpd1.user_face_vertex_data_size = 0;
428         mpd1.user_data_size = sizeof(FaceData);
429
430         if (me->tface) {
431                 mpd1.user_face_vertex_data_size = sizeof(FaceVertexData);
432         }
433         
434         // same for mesh2
435
436         if (me2->mcol != NULL) {
437                 // create some memory for the tfaces.
438                 me2->tface = (TFace *)MEM_callocN(sizeof(TFace)*me2->totface,"BooleanOps_TempTFace");
439                 mcol_to_tface(me2,1);
440                 free_tface2 = 1;
441         } else {
442                 free_tface2 = 0;
443         }
444
445         mpd2.user_face_vertex_data_size = 0;
446         mpd2.user_data_size = sizeof(FaceData);
447
448         if (me2->tface) {
449                 mpd2.user_face_vertex_data_size = sizeof(FaceVertexData);
450         }
451
452         // we map the final object back into object 1's (ob)
453         // local coordinate space. For this we need to compute
454         // the inverse transform from global to local.  
455         
456         Mat4Invert(inv_mat,ob_select->obmat);
457
458         // make a boolean operation;
459         {
460                 CSG_BooleanOperation * bool_op = CSG_NewBooleanFunction();
461                 CSG_MeshPropertyDescriptor output_mpd = CSG_DescibeOperands(bool_op,mpd1,mpd2);
462                 // analyse the result and choose mesh descriptors accordingly
463                 int output_type;                        
464                 if (output_mpd.user_face_vertex_data_size) {
465                         output_type = 1;
466                 } else {
467                         output_type = 0;
468                 }
469                 
470                 BuildMeshDescriptors(
471                         ob,
472                         &fd_1,
473                         &vd_1
474                 );
475                 BuildMeshDescriptors(
476                         ob_select,
477                         &fd_2,
478                         &vd_2
479                 );
480
481                 // perform the operation
482
483                 if (output_type == 0) {
484
485                         success = 
486                         CSG_PerformBooleanOperation(
487                                 bool_op,
488                                 op_type,
489                                 fd_1,vd_1,fd_2,vd_2,
490                                 InterpNoUserData        
491                         );
492                 } else {
493                         success = 
494                         CSG_PerformBooleanOperation(
495                                 bool_op,
496                                 op_type,
497                                 fd_1,vd_1,fd_2,vd_2,
498                                 InterpFaceVertexData    
499                         );
500                 }
501                 
502                 if (success) {
503                         // descriptions of the output;
504                         CSG_VertexIteratorDescriptor vd_o;
505                         CSG_FaceIteratorDescriptor fd_o;
506                         
507                         dlm = MEM_callocN(sizeof(*dlm),"dlm");
508
509                         CSG_OutputFaceDescriptor(bool_op,&fd_o);
510                         CSG_OutputVertexDescriptor(bool_op,&vd_o);
511
512                         // iterate through results of operation and insert into new object
513
514                         ConvertCSGDescriptorsToDLM(
515                                 dlm,
516                                 NULL,
517                                 &output_mpd,
518                                 &fd_o,
519                                 &vd_o,
520                                 inv_mat
521                         );
522
523                         // free up the memory
524
525                         CSG_FreeVertexDescriptor(&vd_o);
526                         CSG_FreeFaceDescriptor(&fd_o);
527                 }
528
529                 CSG_FreeBooleanOperation(bool_op);
530                 bool_op = NULL;
531
532         }
533
534         // We may need to map back the tfaces to mcols here.
535         if (free_tface1) {
536                 tface_to_mcol(me);
537                 MEM_freeN(me->tface);
538                 me->tface = NULL;
539         }
540         if (free_tface2) {
541                 tface_to_mcol(me2);
542                 MEM_freeN(me2->tface);
543                 me2->tface = NULL;
544         }
545
546         if (free_tface1 && free_tface2) {
547                 // then we need to map the output tfaces into mcols
548                 if (dlm) {
549                         dlm->mcol = tface_to_mcol_p(dlm->tface, dlm->totface);
550                         MEM_freeN(dlm->tface);
551                         dlm->tface = NULL;
552                 }
553         }
554         
555         FreeMeshDescriptors(&fd_1,&vd_1);
556         FreeMeshDescriptors(&fd_2,&vd_2);
557
558         return dlm;
559 }
560
561         int
562 NewBooleanMesh(
563         struct Base * base,
564         struct Base * base_select,
565         int int_op_type
566 ){
567         Mesh *me2 = get_mesh(base_select->object);
568         Mesh *me = get_mesh(base->object);
569         Mesh *me_new = NULL;
570         Object *ob, *ob_new = NULL;
571         int free_tface1,free_tface2;
572
573         float inv_mat[4][4];
574         int success = 0;
575         // build and fill new descriptors for these meshes
576         CSG_VertexIteratorDescriptor vd_1;
577         CSG_VertexIteratorDescriptor vd_2;
578         CSG_FaceIteratorDescriptor fd_1;
579         CSG_FaceIteratorDescriptor fd_2;
580
581         CSG_MeshPropertyDescriptor mpd1,mpd2;
582
583         // work out the operation they chose and pick the appropriate 
584         // enum from the csg module.
585
586         CSG_OperationType op_type;
587
588         if (me == NULL || me2 == NULL) return 0;
589
590         if(!me->totface || !me2->totface) return -1;
591         
592         success = 0;
593
594         switch (int_op_type) {
595                 case 1 : op_type = e_csg_intersection; break;
596                 case 2 : op_type = e_csg_union; break;
597                 case 3 : op_type = e_csg_difference; break;
598                 case 4 : op_type = e_csg_classify; break;
599                 default : op_type = e_csg_intersection;
600         }
601
602         // Here is the section where we describe the properties of
603         // both meshes to the bsp module.
604
605         if (me->mcol != NULL) {
606                 // Then this mesh has vertex colors only 
607                 // well this is awkward because there is no equivalent 
608                 // test_index_mface just for vertex colors!
609                 // as a temporary hack we can convert these vertex colors 
610                 // into tfaces do the operation and turn them back again.
611
612                 // create some memory for the tfaces.
613                 me->tface = (TFace *)MEM_callocN(sizeof(TFace)*me->totface,"BooleanOps_TempTFace");
614                 mcol_to_tface(me,1);
615                 free_tface1 = 1;
616         } else {
617                 free_tface1 = 0;
618         }
619
620         mpd1.user_face_vertex_data_size = 0;
621         mpd1.user_data_size = sizeof(FaceData);
622
623         if (me->tface) {
624                 mpd1.user_face_vertex_data_size = sizeof(FaceVertexData);
625         }
626         
627         // same for mesh2
628
629         if (me2->mcol != NULL) {
630                 // create some memory for the tfaces.
631                 me2->tface = (TFace *)MEM_callocN(sizeof(TFace)*me2->totface,"BooleanOps_TempTFace");
632                 mcol_to_tface(me2,1);
633                 free_tface2 = 1;
634         } else {
635                 free_tface2 = 0;
636         }
637
638         mpd2.user_face_vertex_data_size = 0;
639         mpd2.user_data_size = sizeof(FaceData);
640
641         if (me2->tface) {
642                 mpd2.user_face_vertex_data_size = sizeof(FaceVertexData);
643         }
644
645         ob = base->object;
646
647         // we map the final object back into object 1's (ob)
648         // local coordinate space. For this we need to compute
649         // the inverse transform from global to local.  
650         
651         Mat4Invert(inv_mat,ob->obmat);
652
653         // make a boolean operation;
654         {
655                 CSG_BooleanOperation * bool_op = CSG_NewBooleanFunction();
656                 CSG_MeshPropertyDescriptor output_mpd = CSG_DescibeOperands(bool_op,mpd1,mpd2);
657                 // analyse the result and choose mesh descriptors accordingly
658                 int output_type;                        
659                 if (output_mpd.user_face_vertex_data_size) {
660                         output_type = 1;
661                 } else {
662                         output_type = 0;
663                 }
664                 
665                 BuildMeshDescriptors(
666                         base->object,
667                         &fd_1,
668                         &vd_1
669                 );
670                 BuildMeshDescriptors(
671                         base_select->object,
672                         &fd_2,
673                         &vd_2
674                 );
675
676                 // perform the operation
677
678                 if (output_type == 0) {
679
680                         success = 
681                         CSG_PerformBooleanOperation(
682                                 bool_op,
683                                 op_type,
684                                 fd_1,vd_1,fd_2,vd_2,
685                                 InterpNoUserData        
686                         );
687                 } else {
688                         success = 
689                         CSG_PerformBooleanOperation(
690                                 bool_op,
691                                 op_type,
692                                 fd_1,vd_1,fd_2,vd_2,
693                                 InterpFaceVertexData    
694                         );
695                 }
696                 
697                 if (success) {
698                         // descriptions of the output;
699                         CSG_VertexIteratorDescriptor vd_o;
700                         CSG_FaceIteratorDescriptor fd_o;
701                         DispListMesh dlm;
702
703                         // Create a new blender mesh object - using 'base' as 
704                         // a template for the new object.
705                         ob_new=  AddNewBlenderMesh(base);
706
707                         // get the output descriptors
708
709                         CSG_OutputFaceDescriptor(bool_op,&fd_o);
710                         CSG_OutputVertexDescriptor(bool_op,&vd_o);
711
712                         me_new = ob_new->data;
713                         // iterate through results of operation and insert into new object
714                         // see subsurf.c 
715
716                         ConvertCSGDescriptorsToDLM(
717                                 &dlm,
718                                 ob,
719                                 &output_mpd,
720                                 &fd_o,
721                                 &vd_o,
722                                 inv_mat
723                         );
724
725                         if (dlm.nors) MEM_freeN(dlm.nors);
726
727                         me->mvert = dlm.mvert;
728                         me->medge = dlm.medge;
729                         me->mface = dlm.mface;
730                         me->tface = dlm.tface;
731                         me->mcol = dlm.mcol;
732                         me->totvert = dlm.totvert;
733                         me->totedge = dlm.totedge;
734                         me->totface = dlm.totface;
735
736
737                         // free up the memory
738
739                         CSG_FreeVertexDescriptor(&vd_o);
740                         CSG_FreeFaceDescriptor(&fd_o);
741                 }
742
743                 CSG_FreeBooleanOperation(bool_op);
744                 bool_op = NULL;
745
746         }
747
748         // We may need to map back the tfaces to mcols here.
749         if (free_tface1) {
750                 tface_to_mcol(me);
751                 MEM_freeN(me->tface);
752                 me->tface = NULL;
753         }
754         if (free_tface2) {
755                 tface_to_mcol(me2);
756                 MEM_freeN(me2->tface);
757                 me2->tface = NULL;
758         }
759
760         if (free_tface1 && free_tface2) {
761                 // then we need to map the output tfaces into mcols
762                 if (me_new) {
763                         tface_to_mcol(me_new);
764                         MEM_freeN(me_new->tface);
765                         me_new->tface = NULL;
766                 }
767         }
768         
769         FreeMeshDescriptors(&fd_1,&vd_1);
770         FreeMeshDescriptors(&fd_2,&vd_2);
771
772         if (ob_new) {
773                 DAG_object_flush_update(G.scene, ob_new, OB_RECALC_DATA);
774         }
775
776         return success;
777 }
778
779
780         Object *
781 AddNewBlenderMesh(
782         Base *base
783 ){
784         Mesh *old_me;
785         Base *basen;
786         Object *ob_new;
787
788         // now create a new blender object.
789         // duplicating all the settings from the previous object
790         // to the new one.
791         ob_new= copy_object(base->object);
792
793         // Ok we don't want to use the actual data from the
794         // last object, the above function incremented the 
795         // number of users, so decrement it here.
796         old_me= ob_new->data;
797         old_me->id.us--;
798
799         // Now create a new base to add into the linked list of 
800         // vase objects.
801         
802         basen= MEM_mallocN(sizeof(Base), "duplibase");
803         *basen= *base;
804         BLI_addhead(&G.scene->base, basen);     /* addhead: anders oneindige lus */
805         basen->object= ob_new;
806         basen->flag &= ~SELECT;
807                                 
808         // Initialize the mesh data associated with this object.                                                
809         ob_new->data= add_mesh();
810         G.totmesh++;
811
812         // Finally assign the object type.
813         ob_new->type= OB_MESH;
814
815         return ob_new;
816 }
817
818 /**
819  *
820  * External interface
821  *
822  * This function builds a blender mesh using the output information from
823  * the CSG module. It declares all the necessary blender cruft and 
824  * fills in the vertex and face arrays.
825  */
826         static void 
827 ConvertCSGDescriptorsToDLM(
828         DispListMesh *dlm,
829         Object *ob,
830         CSG_MeshPropertyDescriptor *props,
831         CSG_FaceIteratorDescriptor *face_it,
832         CSG_VertexIteratorDescriptor *vertex_it,
833         float parinv[][4]
834 ){
835         FaceVertexData *user_face_vertex_data;
836         GHash *material_hash;
837         CSG_IVertex vert;
838         CSG_IFace face;
839         MVert *insert_pos;
840         MFace *mfaces;
841         TFace *tfaces;
842         int fi_insert_pos, nmaterials;
843
844         // create some memory for the Iface according to output mesh props.
845
846         // initialize the face structure for readback
847         
848         face.user_face_data = MEM_callocN(sizeof(FaceData),"BooleanOp_IFaceData");
849         
850         if (props->user_face_vertex_data_size) {
851                 user_face_vertex_data = MEM_callocN(sizeof(FaceVertexData)*4,"BooleanOp_IFaceData");
852                 face.user_face_vertex_data[0] = &user_face_vertex_data[0];
853                 face.user_face_vertex_data[1] = &user_face_vertex_data[1];
854                 face.user_face_vertex_data[2] = &user_face_vertex_data[2];
855                 face.user_face_vertex_data[3] = &user_face_vertex_data[3];
856         } else {
857                 user_face_vertex_data = NULL;
858         }
859         
860         // create memory for the vertex array.
861
862         dlm->mvert = MEM_callocN(sizeof(MVert) * vertex_it->num_elements,"BooleanOp_VertexArray");
863         dlm->mface = MEM_callocN(sizeof(MFace) * face_it->num_elements,"BooleanOp_FaceArray");
864
865         if (user_face_vertex_data) {
866                 dlm->tface = MEM_callocN(sizeof(TFace) * face_it->num_elements,"BooleanOp_TFaceArray");
867         } else {
868                 dlm->tface = NULL;
869         }
870
871         insert_pos = dlm->mvert;
872         mfaces = dlm->mface;
873         tfaces = dlm->tface;
874
875         fi_insert_pos = 0;
876
877         // step through the iterators.
878
879         while (!vertex_it->Done(vertex_it->it)) {
880                 vertex_it->Fill(vertex_it->it,&vert);
881
882                 // map output vertex into insert_pos 
883                 // and transform at by parinv at the same time.
884
885                 VecMat4MulVecfl(
886                         insert_pos->co,
887                         parinv,
888                         vert.position
889                 );
890                 insert_pos ++;
891                 vertex_it->Step(vertex_it->it);
892         }
893
894         dlm->totvert = vertex_it->num_elements;
895
896         // a hash table to remap materials to indices with
897         material_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
898         nmaterials = 0;
899
900         while (!face_it->Done(face_it->it)) {
901                 MFace *mface = &mfaces[fi_insert_pos];
902                 FaceData *fdata;
903                 
904                 face_it->Fill(face_it->it,&face);
905                 fdata = face.user_face_data;
906
907                 // cheat CSG never dumps out quads.
908
909                 mface->v1 = face.vertex_index[0];
910                 mface->v2 = face.vertex_index[1];
911                 mface->v3 = face.vertex_index[2];
912                 mface->v4 = 0;
913                 mface->mat_nr = 0;
914                 mface->flag = fdata->faceflag;
915                 
916                 /* HACK, perform material to index mapping using a general
917                  * hash table, just tuck the int into a void *.
918                  */
919                 
920                 if (ob && !BLI_ghash_haskey(material_hash, fdata->material)) {
921                         int matnr = nmaterials++;
922                         BLI_ghash_insert(material_hash, fdata->material, (void*) matnr);
923                         assign_material(ob, fdata->material, matnr+1);
924                 }
925                 mface->mat_nr = (int) BLI_ghash_lookup(material_hash, fdata->material);
926
927                 // grab the vertex colors and texture cos and dump them into the tface.
928
929                 if (tfaces) {
930                         TFace *tface= &tfaces[fi_insert_pos];
931                         int i;
932                         
933                         // copy all the tface settings back
934                         tface->tpage = fdata->tpage;
935                         tface->flag = fdata->flag;
936                         tface->transp = fdata->transp;
937                         tface->mode = fdata->mode;
938                         tface->tile = fdata->tile;
939                         
940                         for (i=0; i<4; i++) {
941                                 FaceVertexData *fvdata = face.user_face_vertex_data[i];
942                                 float *color = fvdata->color;
943
944                                 tface->uv[i][0] = fvdata->uv[0];
945                                 tface->uv[i][1] = fvdata->uv[1];
946                                 tface->col[i] = 
947                                         ((((unsigned int)floor(color[0] + 0.5f)) & 0xff) << 24) |
948                                         ((((unsigned int)floor(color[1] + 0.5f)) & 0xff) << 16) |
949                                         ((((unsigned int)floor(color[2] + 0.5f)) & 0xff) << 8) |
950                                         ((((unsigned int)floor(color[3] + 0.5f)) & 0xff) << 0);
951                         }
952
953                         test_index_face(mface, NULL, tface, 3);
954                 } else {
955                         test_index_face(mface, NULL, NULL, 3);
956                 }
957
958                 fi_insert_pos++;
959                 face_it->Step(face_it->it);
960         }
961
962         BLI_ghash_free(material_hash, NULL, NULL);
963
964         dlm->totface = face_it->num_elements;
965
966         displistmesh_add_edges(dlm);
967
968         mesh_calc_normals(dlm->mvert, dlm->totvert, dlm->mface, dlm->totface, &dlm->nors);
969                 
970         // thats it!
971         if (user_face_vertex_data) {
972                 MEM_freeN(user_face_vertex_data);
973         }
974         MEM_freeN(face.user_face_data);
975 }       
976         
977         void
978 BuildMeshDescriptors(
979         struct Object *ob,
980         struct CSG_FaceIteratorDescriptor * face_it,
981         struct CSG_VertexIteratorDescriptor * vertex_it
982 ){      
983         VertexIt_Construct(vertex_it,ob);
984         FaceIt_Construct(face_it,ob);
985 }
986         
987         void
988 FreeMeshDescriptors(
989         struct CSG_FaceIteratorDescriptor *face_it,
990         struct CSG_VertexIteratorDescriptor *vertex_it
991 ){
992         VertexIt_Destruct(vertex_it);
993         FaceIt_Destruct(face_it);
994 }
995