17850d08aaa91b82037a8d66de5e7ec6372ed5e3
[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                 switch( success ) {
503                 case 1:
504                         {
505                                 // descriptions of the output;
506                                 CSG_VertexIteratorDescriptor vd_o;
507                                 CSG_FaceIteratorDescriptor fd_o;
508                                 
509                                 dlm = MEM_callocN(sizeof(*dlm),"dlm");
510
511                                 CSG_OutputFaceDescriptor(bool_op,&fd_o);
512                                 CSG_OutputVertexDescriptor(bool_op,&vd_o);
513
514                                 // iterate through results of operation and insert into new object
515
516                                 ConvertCSGDescriptorsToDLM(
517                                         dlm,
518                                         NULL,
519                                         &output_mpd,
520                                         &fd_o,
521                                         &vd_o,
522                                         inv_mat
523                                 );
524
525                                 // free up the memory
526
527                                 CSG_FreeVertexDescriptor(&vd_o);
528                                 CSG_FreeFaceDescriptor(&fd_o);
529                         }
530                         break;
531                 case -1:
532                          error("Selected meshes must have faces to perform boolean operations");
533                          break;
534                 case -2:
535                          error("Both meshes must be closed");
536                          break;
537                 default:
538                          error("unknown internal error");
539                          break;
540                 }
541
542                 CSG_FreeBooleanOperation(bool_op);
543         }
544
545         // We may need to map back the tfaces to mcols here.
546         if (free_tface1) {
547                 tface_to_mcol(me);
548                 MEM_freeN(me->tface);
549                 me->tface = NULL;
550         }
551         if (free_tface2) {
552                 tface_to_mcol(me2);
553                 MEM_freeN(me2->tface);
554                 me2->tface = NULL;
555         }
556
557         if (free_tface1 && free_tface2) {
558                 // then we need to map the output tfaces into mcols
559                 if (dlm) {
560                         dlm->mcol = tface_to_mcol_p(dlm->tface, dlm->totface);
561                         MEM_freeN(dlm->tface);
562                         dlm->tface = NULL;
563                 }
564         }
565         
566         FreeMeshDescriptors(&fd_1,&vd_1);
567         FreeMeshDescriptors(&fd_2,&vd_2);
568
569         return dlm;
570 }
571
572         int
573 NewBooleanMesh(
574         struct Base * base,
575         struct Base * base_select,
576         int int_op_type
577 ){
578         Mesh *me2 = get_mesh(base_select->object);
579         Mesh *me = get_mesh(base->object);
580         Mesh *me_new = NULL;
581         Object *ob, *ob_new = NULL;
582         int free_tface1,free_tface2;
583
584         float inv_mat[4][4];
585         int success = 0;
586         // build and fill new descriptors for these meshes
587         CSG_VertexIteratorDescriptor vd_1;
588         CSG_VertexIteratorDescriptor vd_2;
589         CSG_FaceIteratorDescriptor fd_1;
590         CSG_FaceIteratorDescriptor fd_2;
591
592         CSG_MeshPropertyDescriptor mpd1,mpd2;
593
594         // work out the operation they chose and pick the appropriate 
595         // enum from the csg module.
596
597         CSG_OperationType op_type;
598
599         if (me == NULL || me2 == NULL) return 0;
600
601         if(!me->totface || !me2->totface) return -1;
602         
603         success = 0;
604
605         switch (int_op_type) {
606                 case 1 : op_type = e_csg_intersection; break;
607                 case 2 : op_type = e_csg_union; break;
608                 case 3 : op_type = e_csg_difference; break;
609                 case 4 : op_type = e_csg_classify; break;
610                 default : op_type = e_csg_intersection;
611         }
612
613         // Here is the section where we describe the properties of
614         // both meshes to the bsp module.
615
616         if (me->mcol != NULL) {
617                 // Then this mesh has vertex colors only 
618                 // well this is awkward because there is no equivalent 
619                 // test_index_mface just for vertex colors!
620                 // as a temporary hack we can convert these vertex colors 
621                 // into tfaces do the operation and turn them back again.
622
623                 // create some memory for the tfaces.
624                 me->tface = (TFace *)MEM_callocN(sizeof(TFace)*me->totface,"BooleanOps_TempTFace");
625                 mcol_to_tface(me,1);
626                 free_tface1 = 1;
627         } else {
628                 free_tface1 = 0;
629         }
630
631         mpd1.user_face_vertex_data_size = 0;
632         mpd1.user_data_size = sizeof(FaceData);
633
634         if (me->tface) {
635                 mpd1.user_face_vertex_data_size = sizeof(FaceVertexData);
636         }
637         
638         // same for mesh2
639
640         if (me2->mcol != NULL) {
641                 // create some memory for the tfaces.
642                 me2->tface = (TFace *)MEM_callocN(sizeof(TFace)*me2->totface,"BooleanOps_TempTFace");
643                 mcol_to_tface(me2,1);
644                 free_tface2 = 1;
645         } else {
646                 free_tface2 = 0;
647         }
648
649         mpd2.user_face_vertex_data_size = 0;
650         mpd2.user_data_size = sizeof(FaceData);
651
652         if (me2->tface) {
653                 mpd2.user_face_vertex_data_size = sizeof(FaceVertexData);
654         }
655
656         ob = base->object;
657
658         // we map the final object back into object 1's (ob)
659         // local coordinate space. For this we need to compute
660         // the inverse transform from global to local.  
661         
662         Mat4Invert(inv_mat,ob->obmat);
663
664         // make a boolean operation;
665         {
666                 CSG_BooleanOperation * bool_op = CSG_NewBooleanFunction();
667                 CSG_MeshPropertyDescriptor output_mpd = CSG_DescibeOperands(bool_op,mpd1,mpd2);
668                 // analyse the result and choose mesh descriptors accordingly
669                 int output_type;                        
670                 if (output_mpd.user_face_vertex_data_size) {
671                         output_type = 1;
672                 } else {
673                         output_type = 0;
674                 }
675                 
676                 BuildMeshDescriptors(
677                         base->object,
678                         &fd_1,
679                         &vd_1
680                 );
681                 BuildMeshDescriptors(
682                         base_select->object,
683                         &fd_2,
684                         &vd_2
685                 );
686
687                 // perform the operation
688
689                 if (output_type == 0) {
690
691                         success = 
692                         CSG_PerformBooleanOperation(
693                                 bool_op,
694                                 op_type,
695                                 fd_1,vd_1,fd_2,vd_2,
696                                 InterpNoUserData        
697                         );
698                 } else {
699                         success = 
700                         CSG_PerformBooleanOperation(
701                                 bool_op,
702                                 op_type,
703                                 fd_1,vd_1,fd_2,vd_2,
704                                 InterpFaceVertexData    
705                         );
706                 }
707                 
708                 if (success==1) {
709                         // descriptions of the output;
710                         CSG_VertexIteratorDescriptor vd_o;
711                         CSG_FaceIteratorDescriptor fd_o;
712                         DispListMesh dlm;
713
714                         // need to make sure its zeroed
715                         memset (&dlm, 0, sizeof (dlm));
716                         
717                         // Create a new blender mesh object - using 'base' as 
718                         // a template for the new object.
719                         ob_new=  AddNewBlenderMesh(base);
720
721                         // get the output descriptors
722
723                         CSG_OutputFaceDescriptor(bool_op,&fd_o);
724                         CSG_OutputVertexDescriptor(bool_op,&vd_o);
725
726                         me_new = ob_new->data;
727                         // iterate through results of operation and insert into new object
728                         // see subsurf.c 
729
730                         ConvertCSGDescriptorsToDLM(
731                                 &dlm,
732                                 ob_new,
733                                 &output_mpd,
734                                 &fd_o,
735                                 &vd_o,
736                                 inv_mat
737                         );
738
739                         if (dlm.nors) MEM_freeN(dlm.nors);
740
741                         me_new->mvert = dlm.mvert;
742                         me_new->medge = dlm.medge;
743                         me_new->mface = dlm.mface;
744                         me_new->tface = dlm.tface;
745                         me_new->mcol = dlm.mcol;
746                         me_new->totvert = dlm.totvert;
747                         me_new->totedge = dlm.totedge;
748                         me_new->totface = dlm.totface;
749
750                         // free up the memory
751
752                         CSG_FreeVertexDescriptor(&vd_o);
753                         CSG_FreeFaceDescriptor(&fd_o);
754                 }
755
756                 CSG_FreeBooleanOperation(bool_op);
757                 bool_op = NULL;
758
759         }
760
761         // We may need to map back the tfaces to mcols here.
762         if (free_tface1) {
763                 tface_to_mcol(me);
764                 MEM_freeN(me->tface);
765                 me->tface = NULL;
766         }
767         if (free_tface2) {
768                 tface_to_mcol(me2);
769                 MEM_freeN(me2->tface);
770                 me2->tface = NULL;
771         }
772
773         if (free_tface1 && free_tface2) {
774                 // then we need to map the output tfaces into mcols
775                 if (me_new) {
776                         tface_to_mcol(me_new);
777                         MEM_freeN(me_new->tface);
778                         me_new->tface = NULL;
779                 }
780         }
781         
782         FreeMeshDescriptors(&fd_1,&vd_1);
783         FreeMeshDescriptors(&fd_2,&vd_2);
784
785         if (ob_new) {
786                 DAG_object_flush_update(G.scene, ob_new, OB_RECALC_DATA);
787         }
788
789         return success;
790 }
791
792
793         Object *
794 AddNewBlenderMesh(
795         Base *base
796 ){
797         Mesh *old_me;
798         Base *basen;
799         Object *ob_new;
800
801         // now create a new blender object.
802         // duplicating all the settings from the previous object
803         // to the new one.
804         ob_new= copy_object(base->object);
805
806         // Ok we don't want to use the actual data from the
807         // last object, the above function incremented the 
808         // number of users, so decrement it here.
809         old_me= ob_new->data;
810         old_me->id.us--;
811
812         // Now create a new base to add into the linked list of 
813         // vase objects.
814         
815         basen= MEM_mallocN(sizeof(Base), "duplibase");
816         *basen= *base;
817         BLI_addhead(&G.scene->base, basen);     /* addhead: anders oneindige lus */
818         basen->object= ob_new;
819         basen->flag &= ~SELECT;
820                                 
821         // Initialize the mesh data associated with this object.                                                
822         ob_new->data= add_mesh();
823         G.totmesh++;
824
825         // Finally assign the object type.
826         ob_new->type= OB_MESH;
827
828         return ob_new;
829 }
830
831 /**
832  *
833  * External interface
834  *
835  * This function builds a blender mesh using the output information from
836  * the CSG module. It declares all the necessary blender cruft and 
837  * fills in the vertex and face arrays.
838  */
839         static void 
840 ConvertCSGDescriptorsToDLM(
841         DispListMesh *dlm,
842         Object *ob,
843         CSG_MeshPropertyDescriptor *props,
844         CSG_FaceIteratorDescriptor *face_it,
845         CSG_VertexIteratorDescriptor *vertex_it,
846         float parinv[][4]
847 ){
848         FaceVertexData *user_face_vertex_data;
849         GHash *material_hash;
850         CSG_IVertex vert;
851         CSG_IFace face;
852         MVert *insert_pos;
853         MFace *mfaces;
854         TFace *tfaces;
855         int fi_insert_pos, nmaterials;
856
857         // create some memory for the Iface according to output mesh props.
858
859         // initialize the face structure for readback
860         
861         face.user_face_data = MEM_callocN(sizeof(FaceData),"BooleanOp_IFaceData");
862         
863         if (props->user_face_vertex_data_size) {
864                 user_face_vertex_data = MEM_callocN(sizeof(FaceVertexData)*4,"BooleanOp_IFaceData");
865                 face.user_face_vertex_data[0] = &user_face_vertex_data[0];
866                 face.user_face_vertex_data[1] = &user_face_vertex_data[1];
867                 face.user_face_vertex_data[2] = &user_face_vertex_data[2];
868                 face.user_face_vertex_data[3] = &user_face_vertex_data[3];
869         } else {
870                 user_face_vertex_data = NULL;
871         }
872         
873         // create memory for the vertex array.
874
875         dlm->mvert = MEM_callocN(sizeof(MVert) * vertex_it->num_elements,"BooleanOp_VertexArray");
876         dlm->mface = MEM_callocN(sizeof(MFace) * face_it->num_elements,"BooleanOp_FaceArray");
877
878         if (user_face_vertex_data) {
879                 dlm->tface = MEM_callocN(sizeof(TFace) * face_it->num_elements,"BooleanOp_TFaceArray");
880         } else {
881                 dlm->tface = NULL;
882         }
883
884         insert_pos = dlm->mvert;
885         mfaces = dlm->mface;
886         tfaces = dlm->tface;
887
888         fi_insert_pos = 0;
889
890         // step through the iterators.
891
892         while (!vertex_it->Done(vertex_it->it)) {
893                 vertex_it->Fill(vertex_it->it,&vert);
894
895                 // map output vertex into insert_pos 
896                 // and transform at by parinv at the same time.
897
898                 VecMat4MulVecfl(
899                         insert_pos->co,
900                         parinv,
901                         vert.position
902                 );
903                 insert_pos ++;
904                 vertex_it->Step(vertex_it->it);
905         }
906
907         dlm->totvert = vertex_it->num_elements;
908
909         // a hash table to remap materials to indices with
910         material_hash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
911         nmaterials = 0;
912
913         while (!face_it->Done(face_it->it)) {
914                 MFace *mface = &mfaces[fi_insert_pos];
915                 FaceData *fdata;
916                 
917                 face_it->Fill(face_it->it,&face);
918                 fdata = face.user_face_data;
919
920                 // cheat CSG never dumps out quads.
921
922                 if (face.vertex_number>3) {
923                         // QUAD
924                         mface->v1 = face.vertex_index[0];
925                         mface->v2 = face.vertex_index[1];
926                         mface->v3 = face.vertex_index[2];
927                         mface->v4 = face.vertex_index[3];
928                 }
929                 else {
930                         // TRIANGLE
931                         mface->v1 = face.vertex_index[0];
932                         mface->v2 = face.vertex_index[1];
933                         mface->v3 = face.vertex_index[2];
934                         mface->v4 = 0;
935                 }
936
937                 mface->mat_nr = 0;
938                 mface->flag = fdata->faceflag;
939                 
940                 /* HACK, perform material to index mapping using a general
941                  * hash table, just tuck the int into a void *.
942                  */
943                 
944                 if (ob && !BLI_ghash_haskey(material_hash, fdata->material)) {
945                         int matnr = nmaterials++;
946                         BLI_ghash_insert(material_hash, fdata->material, (void*) matnr);
947                         assign_material(ob, fdata->material, matnr+1);
948                 }
949                 mface->mat_nr = (int) BLI_ghash_lookup(material_hash, fdata->material);
950
951                 // grab the vertex colors and texture cos and dump them into the tface.
952
953                 if (tfaces) {
954                         TFace *tface= &tfaces[fi_insert_pos];
955                         int i;
956                         
957                         // copy all the tface settings back
958                         tface->tpage = fdata->tpage;
959                         tface->flag = fdata->flag;
960                         tface->transp = fdata->transp;
961                         tface->mode = fdata->mode;
962                         tface->tile = fdata->tile;
963                         
964                         for (i=0; i<4; i++) {
965                                 FaceVertexData *fvdata = face.user_face_vertex_data[i];
966                                 float *color = fvdata->color;
967
968                                 tface->uv[i][0] = fvdata->uv[0];
969                                 tface->uv[i][1] = fvdata->uv[1];
970                                 tface->col[i] = 
971                                         ((((unsigned int)floor(color[0] + 0.5f)) & 0xff) << 24) |
972                                         ((((unsigned int)floor(color[1] + 0.5f)) & 0xff) << 16) |
973                                         ((((unsigned int)floor(color[2] + 0.5f)) & 0xff) << 8) |
974                                         ((((unsigned int)floor(color[3] + 0.5f)) & 0xff) << 0);
975                         }
976
977                         test_index_face(mface, NULL, tface, face.vertex_number);
978                 } else {
979                         test_index_face(mface, NULL, NULL, face.vertex_number);
980                 }
981
982                 fi_insert_pos++;
983                 face_it->Step(face_it->it);
984         }
985
986         BLI_ghash_free(material_hash, NULL, NULL);
987
988         dlm->totface = face_it->num_elements;
989
990         displistmesh_add_edges(dlm);
991
992         mesh_calc_normals(dlm->mvert, dlm->totvert, dlm->mface, dlm->totface, &dlm->nors);
993                 
994         // thats it!
995         if (user_face_vertex_data) {
996                 MEM_freeN(user_face_vertex_data);
997         }
998         MEM_freeN(face.user_face_data);
999 }       
1000         
1001         void
1002 BuildMeshDescriptors(
1003         struct Object *ob,
1004         struct CSG_FaceIteratorDescriptor * face_it,
1005         struct CSG_VertexIteratorDescriptor * vertex_it
1006 ){      
1007         VertexIt_Construct(vertex_it,ob);
1008         FaceIt_Construct(face_it,ob);
1009 }
1010         
1011         void
1012 FreeMeshDescriptors(
1013         struct CSG_FaceIteratorDescriptor *face_it,
1014         struct CSG_VertexIteratorDescriptor *vertex_it
1015 ){
1016         VertexIt_Destruct(vertex_it);
1017         FaceIt_Destruct(face_it);
1018 }
1019