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