Initial revision
[blender.git] / intern / bsp / extern / CSG_BooleanOps.h
1 /**
2  * $Id$
3  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version. The Blender
9  * Foundation also sells licenses for use in proprietary software under
10  * the Blender License.  See http://www.blender.org/BL/ for information
11  * about this.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL/BL DUAL LICENSE BLOCK *****
30  */
31
32 #ifndef CSG_BOOLEANOPS_H
33
34 #define CSG_BOOLEANOPS_H
35
36 /**
37  * @section Interface structures for CSG module.
38  * This interface falls into 2 categories.
39  * The first section deals with an abstract mesh description 
40  * between blender and this module. The second deals with 
41  * the module functions. 
42  * The CSG module needs to know about the following entities:
43  */
44
45 /**
46  * CSG_IFace -- an interface polygon structure. 
47  * vertex_index is a fixed size array of 4 elements containing indices into
48  * an abstract vertex container. 3 or 4 of these elements may be used to
49  * describe either quads or triangles.
50  * vertex_number is the number of vertices in this face - either 3 or 4.
51  * vertex_colors is an array of {r,g,b} triplets one for each vertex index.
52  * tex_coords is an array of {u,v} triplets one for each vertex index.
53  * user_data is a pointer to arbitary data of fixed width ,
54  * this data is copied around with the face, and duplicated if a face is
55  * split. Contains things like material index. 
56  */
57
58 #ifdef __cplusplus
59 extern "C" {
60 #endif
61
62 typedef struct  {
63   int vertex_index[4];
64   int vertex_number;
65
66   void *user_face_vertex_data[4];
67   void *user_face_data;
68 } CSG_IFace;
69
70 /**
71  * CSG_IVertex -- an interface vertex structure.
72  * position is the location of the vertex in 3d space.
73  */
74
75 typedef struct  {
76   float position[3];
77 } CSG_IVertex;
78
79 /**
80  * The actual useful data contained in a group of faces is
81  * described by the following struct
82  */
83
84 /**
85  * Descibes the data stored in a mesh available through the 
86  * CSG_IFace interface.
87  * user_data_size is the number of bytes of user_data associated with each CSG_IFace
88  * user_face_vertex_data size is the number of bytes of user data associated with
89  * every face vertex tuple.
90  * . 
91  */
92
93 typedef struct CSG_MeshPropertyDescriptor{
94         unsigned int user_face_vertex_data_size;
95         unsigned int user_data_size;
96 } CSG_MeshPropertyDescriptor;
97
98
99
100 /**
101  * @section Iterator abstraction.
102  * 
103  * The CSG module asks blender to fill in an instance of the above
104  * structure, and requests blender to move up and down (iterate) through
105  * it's face and vertex containers.
106  * 
107  * An iterator supports the following functions.
108  * int IsDone(iterator *it)  -- returns true if the iterator has reached
109  * the end of it's container.
110  *
111  * void Fill(iterator *it,DataType *data) -- Return the contents of the
112  * container at the current iterator position.
113  *
114  * void Step(iterator *it) -- increment the iterator to the next position
115  * in the container. 
116  *
117  * The iterator is used in the following manner.
118  * 
119  *   MyIterator * iterator = ... 
120  *   DataType data; 
121  * 
122  *   while (!IsDone(iterator)) {
123  *              Fill(iterator,&data);
124  *              //process information pointed to by data 
125  *              ...
126  *              Step(iterator);
127  *       } 
128  * 
129  * The CSG module does not want to know about the implementation of these
130  * functions  so we use the c function ptr mechanism to hide them. Our
131  * iterator descriptor now looks like this.
132  */
133
134 typedef void* CSG_IteratorPtr;
135
136 typedef int (*CSG_FaceItDoneFunc)(CSG_IteratorPtr it);
137 typedef void (*CSG_FaceItFillFunc)(CSG_IteratorPtr it,CSG_IFace *face);
138 typedef void (*CSG_FaceItStepFunc)(CSG_IteratorPtr it);
139 typedef void (*CSG_FaceItResetFunc)(CSG_IteratorPtr it);
140
141 typedef struct CSG_FaceIteratorDescriptor {
142         CSG_IteratorPtr it;
143         CSG_FaceItDoneFunc Done;
144         CSG_FaceItFillFunc Fill;
145         CSG_FaceItStepFunc Step;
146         CSG_FaceItResetFunc Reset;
147         unsigned int num_elements;
148 } CSG_FaceIteratorDescriptor; 
149
150 /**
151  * Similarly to walk through the vertex arrays we have.
152  */
153 typedef int (*CSG_VertexItDoneFunc)(CSG_IteratorPtr it);
154 typedef void (*CSG_VertexItFillFunc)(CSG_IteratorPtr it,CSG_IVertex *face);
155 typedef void (*CSG_VertexItStepFunc)(CSG_IteratorPtr it);
156 typedef void (*CSG_VertexItResetFunc)(CSG_IteratorPtr it);
157
158 typedef struct CSG_VertexIteratorDescriptor {
159         CSG_IteratorPtr it;
160         CSG_VertexItDoneFunc Done;
161         CSG_VertexItFillFunc Fill;
162         CSG_VertexItStepFunc Step;
163         CSG_VertexItResetFunc Reset;
164         unsigned int num_elements;
165 } CSG_VertexIteratorDescriptor; 
166
167 /**
168  * The actual iterator structures are not exposed to the CSG module, they
169  * will contain datatypes specific to blender.
170  */
171
172 /**
173  * @section CSG Module interface functions.
174  * 
175  * The functions below are to be used in the following way:
176  * 
177  *  // Create a boolean operation handle
178  *  CSG_BooleanOperation *operation = CSG_NewBooleanFunction();
179  *  if (operation == NULL) {
180  *              // deal with low memory exception
181  *  }
182  *
183  *  // Describe each mesh operand to the module.
184  *  // NOTE: example properties!
185  *  CSG_MeshPropertyDescriptor propA,propB;
186  *  propA.user_data_size = 0;
187  *  propA.user_face_vertex_data = 0;
188  *  propB.user_face_vertex_data = 0;
189  *  propB.user_data_size = 0;
190  *
191  *  // Get the output properties of the mesh.
192  *  CSG_MeshPropertyDescriptor output_properties;
193  *  output_properties = CSG_DescibeOperands(
194  *    operation,
195  *    propA,
196  *    propB
197  *  );
198  * 
199  *  // Report to the user if they will loose any data!
200  *  ...
201  * 
202  *  // Get some mesh iterators for your mesh data structures
203  *  CSG_FaceIteratorDescriptor obA_faces = ...
204  *  CSG_VertexIteratorDescriptor obA_verts = ...
205  *  
206  *  // same for object B
207  *  CSG_FaceIteratorDescriptor obB_faces = ...
208  *  CSG_VertexIteratorDescriptor obB_verts = ...
209  *  
210  *  // perform the operation...!
211  *
212  *  int success = CSG_PerformBooleanOperation(
213  *     operation,
214  *     e_csg_intersection,
215  *     obA_faces,
216  *     obA_vertices,
217  *     obB_faces,
218  *     obB_vertices
219  *  );
220  *
221  *  // if the operation failes report miserable faiulre to user
222  *  // and clear up data structures.
223  *  if (!success) {
224  *    ...
225  *    CSG_FreeBooleanOperation(operation);
226  *    return;
227  *  }
228  *
229  *  // read the new mesh vertices back from the module
230  *  // and assign to your own mesh structure.
231  *
232  *  // First we need to create a CSG_IVertex so the module can fill it in.
233  *  CSG_IVertex vertex;
234  *  CSG_VertexIteratorDescriptor * verts_it = CSG_OutputVertexDescriptor(operation);
235  *
236  *  // initialize your vertex container with the number of verts (verts_it->num_elements)
237  * 
238  *  while (!verts_it->Done(verts_it->it)) {
239  *              verts_it->Fill(verts_it->it,&vertex);
240  *
241  *      // create a new vertex of your own type and add it
242  *      // to your mesh structure.
243  *      verts_it->Step(verts_it->it);
244  *  }
245  *  // Free the vertex iterator
246  *      CSG_FreeVertexDescriptor(verts_it);
247  * 
248  *  // similarly for faces.
249  *  CSG_IFace face;
250  *
251  *  // you may need to reserve some memory in face->user_data here.
252  * 
253  *  // initialize your face container with the number of faces (faces_it->num_elements)
254  * 
255  *  CSG_FaceIteratorDescriptor * faces_it = CSG_OutputFaceDescriptor(operation);
256  * 
257  *  while (!faces_it->Done(faces_it->it)) {
258  *              faces_it->Fill(faces_it->it,&face);
259  *
260  *      // create a new face of your own type and add it
261  *      // to your mesh structure.
262  *      faces_it->Step(&faces_it->it);
263  *  }
264  *      
265  *  // Free the face iterator
266  *      CSG_FreeVertexDescriptor(faces_it);
267  *
268  *  // that's it free the operation.
269  *
270  *  CSG_FreeBooleanOperation(operation);
271  *  return;
272  *  
273  */
274
275 /**
276  * Description of boolean operation type.
277  */
278
279 typedef enum {
280         e_csg_union,
281         e_csg_intersection,
282         e_csg_difference,
283         e_csg_classify
284 } CSG_OperationType;
285
286 /**
287  * 'Handle' into the CSG module that identifies a particular CSG operation.
288  *  the pointer CSG_info containers module specific data, and should not
289  *  be touched in anyway outside of the module.
290  */
291
292 typedef struct {
293         void *CSG_info;
294 } CSG_BooleanOperation;
295
296 /**
297  * Return a ptr to a CSG_BooleanOperation object allocated
298  * on the heap. The CSG module owns the memory associated with 
299  * the returned ptr, use CSG_FreeBooleanOperation() to free this memory.
300  */
301         CSG_BooleanOperation * 
302 CSG_NewBooleanFunction(
303         void
304 );
305
306 /**
307  * Describe the operands of a boolean function to the module.
308  * The description takes the form of a pair of CSG_MeshPropertyDescriptors
309  * one for each input mesh. The operands do not have to have the same 
310  * properties, for example operandA may have vertex colours but operandB none.
311  * In this case the CSG module will choose the lowest common denominator in
312  * mesh properies. The function returns a description of 
313  * the output mesh. You can use this to warn the user that certain properties
314  * will be lost. Of course it also describes what fields in the output mesh
315  * will contain valid data.
316  */
317         CSG_MeshPropertyDescriptor
318 CSG_DescibeOperands(
319         CSG_BooleanOperation * operation,
320         CSG_MeshPropertyDescriptor operandA_desciption,
321         CSG_MeshPropertyDescriptor operandB_desciption
322 );
323
324 /**
325  * The user data is handled by the BSP modules through
326  * the following function which is called whenever the 
327  * module needs new face vertex properties (when a face is split).
328  * d1,d2 are pointers to existing vertex face data. dnew is 
329  * a pointer to an allocated but unfilled area of user data of
330  * size user_face_vertex_data_size in the CSG_MeshPropertyDescriptor
331  * returned by a call to the above function. Epsilon is the relative 
332  * distance (between [0,1]) of the new vertex and the vertex associated
333  * with d1. Use epsilon to interpolate the face vertex data in d1 and d2
334  * and fill  dnew
335  */
336
337 typedef int (*CSG_InterpolateUserFaceVertexDataFunc)(void *d1, void * d2, void *dnew, float epsilon);
338
339
340 /**
341  * Attempt to perform a boolean operation between the 2 objects of the 
342  * desired type. This may fail due to an internal error or lack of memory.
343  * In this case 0 is returned, otehrwise 1 is returned indicating success.
344  * @param operation is a 'handle' into the CSG_Module created by CSG_NewBooleanFunction()
345  * @param op_type is the operation to perform.
346  * @param obAFaces is an iterator over the faces of objectA,
347  * @param obAVertices is an iterator over the vertices of objectA
348  * @param obAFaces is an iterator over the faces of objectB,
349  * @param obAVertices is an iterator over the vertices of objectB
350  * @param interp_func the face_vertex data interpolation function.(see above)
351  * 
352  * All iterators must be valid and pointing to the first element in their
353  * respective containers.
354  */
355         int
356 CSG_PerformBooleanOperation(
357         CSG_BooleanOperation * operation,
358         CSG_OperationType op_type,
359         CSG_FaceIteratorDescriptor obAFaces,
360         CSG_VertexIteratorDescriptor obAVertices,
361         CSG_FaceIteratorDescriptor obBFaces,
362         CSG_VertexIteratorDescriptor obBVertices,
363         CSG_InterpolateUserFaceVertexDataFunc interp_func
364 );
365
366 /**
367  * If the a boolean operation was successful, you may access the results
368  * through the following functions.
369  *
370  * CSG_OuputFaceDescriptor() returns a ptr to a CSG_FaceIteratorDesciptor 
371  * allocated on the heap and owned by the CSG module. The iterator is
372  * positioned at the start of the internal face container.
373  * CSG_OutputVertexDescriptor() returns a ptr to a CSG_VertexIteratorDescriptor
374  * allocated on the heap and owned by the CSG module. The iterator is
375  * positioned at the start of the internal vertex container.
376  * There is no function to rewind an iterator but you may obtain more
377  * than one
378  * iterator at a time. Please use the function CSG_FreeFaceIterator()
379  * and CSG_FreeVertexIterator to free internal memory allocated for these
380  * iterators.
381  * 
382  * If the last operation was not successful, these functions return NULL.
383  */
384         int
385 CSG_OutputFaceDescriptor(
386         CSG_BooleanOperation * operation,
387         CSG_FaceIteratorDescriptor * output
388 );
389
390         int
391 CSG_OutputVertexDescriptor(
392         CSG_BooleanOperation * operation,
393         CSG_VertexIteratorDescriptor *output
394 );
395
396 /**
397  * Clean up functions.
398  * Free internal memory associated with CSG interface structures. You must
399  * call these functions on any structures created by the module, even if
400  * subsequent operations did not succeed.
401  */
402         void
403 CSG_FreeVertexDescriptor(
404         CSG_VertexIteratorDescriptor * v_descriptor
405 );
406
407         void
408 CSG_FreeFaceDescriptor(
409         CSG_FaceIteratorDescriptor * f_descriptor
410 );
411
412 /**
413  * Free the memory associated with a boolean operation. 
414  * NOTE any iterator descriptor describing the output will become
415  * invalid after this call and should be freed immediately.
416  */
417         void
418 CSG_FreeBooleanOperation(
419         CSG_BooleanOperation *operation
420 );
421
422 #ifdef __cplusplus
423 }
424 #endif
425
426
427
428 #endif