Merge branch 'blender2.7'
[blender.git] / source / blender / bmesh / bmesh_class.h
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 #ifndef __BMESH_CLASS_H__
18 #define __BMESH_CLASS_H__
19
20 /** \file
21  * \ingroup bmesh
22  */
23
24 /* bmesh data structures */
25
26 /* dissable holes for now,
27  * these are ifdef'd because they use more memory and cant be saved in DNA currently */
28 // #define USE_BMESH_HOLES
29
30 struct BMEdge;
31 struct BMFace;
32 struct BMLoop;
33 struct BMVert;
34 struct BMesh;
35
36 struct MLoopNorSpaceArray;
37
38 struct BLI_mempool;
39
40 /* note: it is very important for BMHeader to start with two
41  * pointers. this is a requirement of mempool's method of
42  * iteration.
43  *
44  * hrm. it doesn't but still works ok, remove the comment above? - campbell.
45  */
46
47 // #pragma GCC diagnostic error "-Wpadded"
48
49 /**
50  * BMHeader
51  *
52  * All mesh elements begin with a BMHeader. This structure
53  * hold several types of data
54  *
55  * 1: The type of the element (vert, edge, loop or face)
56  * 2: Persistent "header" flags/markings (smooth, seam, select, hidden, etc)
57  *     note that this is different from the "tool" flags.
58  * 3: Unique ID in the bmesh.
59  * 4: some elements for internal record keeping.
60  */
61 typedef struct BMHeader {
62   /** Customdata layers. */
63   void *data;
64
65   /**
66    * \note
67    * - Use BM_elem_index_get/set macros for index
68    * - Uninitialized to -1 so we can easily tell its not set.
69    * - Used for edge/vert/face/loop, check BMesh.elem_index_dirty for valid index values,
70    *   this is abused by various tools which set it dirty.
71    * - For loops this is used for sorting during tessellation.
72    */
73   int index;
74
75   /** Element geometric type (verts/edges/loops/faces). */
76   char htype;
77   /** This would be a CD layer, see below. */
78   char hflag;
79
80   /**
81    * Internal use only!
82    * \note We are very picky about not bloating this struct
83    * but in this case its padded up to 16 bytes anyway,
84    * so adding a flag here gives no increase in size.
85    */
86   char api_flag;
87   // char _pad;
88 } BMHeader;
89
90 BLI_STATIC_ASSERT((sizeof(BMHeader) <= 16), "BMHeader size has grown!");
91
92 /* note: need some way to specify custom locations for custom data layers.  so we can
93  * make them point directly into structs.  and some way to make it only happen to the
94  * active layer, and properly update when switching active layers.*/
95
96 typedef struct BMVert {
97   BMHeader head;
98
99   float co[3]; /* vertex coordinates */
100   float no[3]; /* vertex normal */
101
102   /**
103    * Pointer to (any) edge using this vertex (for disk cycles).
104    *
105    * \note Some higher level functions set this to different edges that use this vertex,
106    * which is a bit of an abuse of internal bmesh data but also works OK for now
107    * (use with care!).
108    */
109   struct BMEdge *e;
110 } BMVert;
111
112 typedef struct BMVert_OFlag {
113   BMVert base;
114   struct BMFlagLayer *oflags;
115 } BMVert_OFlag;
116
117 /* disk link structure, only used by edges */
118 typedef struct BMDiskLink {
119   struct BMEdge *next, *prev;
120 } BMDiskLink;
121
122 typedef struct BMEdge {
123   BMHeader head;
124
125   struct BMVert *v1, *v2; /* vertices (unordered) */
126
127   /* the list of loops around the edge (use l->radial_prev/next)
128    * to access the other loops using the edge */
129   struct BMLoop *l;
130
131   /**
132    * Disk Cycle Pointers
133    *
134    * relative data: d1 indicates indicates the next/prev
135    * edge around vertex v1 and d2 does the same for v2.
136    */
137   BMDiskLink v1_disk_link, v2_disk_link;
138 } BMEdge;
139
140 typedef struct BMEdge_OFlag {
141   BMEdge base;
142   struct BMFlagLayer *oflags;
143 } BMEdge_OFlag;
144
145 typedef struct BMLoop {
146   BMHeader head;
147   /* notice no flags layer */
148
149   struct BMVert *v;
150   struct BMEdge *e; /* edge, using verts (v, next->v) */
151   struct BMFace *f;
152
153   /* circular linked list of loops which all use the same edge as this one '->e',
154    * but not necessarily the same vertex (can be either v1 or v2 of our own '->e') */
155   struct BMLoop *radial_next, *radial_prev;
156
157   /* these were originally commented as private but are used all over the code */
158   /* can't use ListBase API, due to head */
159   struct BMLoop *next, *prev; /* next/prev verts around the face */
160 } BMLoop;
161
162 /* can cast BMFace/BMEdge/BMVert, but NOT BMLoop, since these don't have a flag layer */
163 typedef struct BMElemF {
164   BMHeader head;
165 } BMElemF;
166
167 /* can cast anything to this, including BMLoop */
168 typedef struct BMElem {
169   BMHeader head;
170 } BMElem;
171
172 #ifdef USE_BMESH_HOLES
173 /* eventually, this structure will be used for supporting holes in faces */
174 typedef struct BMLoopList {
175   struct BMLoopList *next, *prev;
176   struct BMLoop *first, *last;
177 } BMLoopList;
178 #endif
179
180 typedef struct BMFace {
181   BMHeader head;
182
183 #ifdef USE_BMESH_HOLES
184   int totbounds; /*total boundaries, is one plus the number of holes in the face*/
185   ListBase loops;
186 #else
187   BMLoop *l_first;
188 #endif
189   int len;      /* number of vertices in the face */
190   float no[3];  /* face normal */
191   short mat_nr; /* material index */
192   //  short _pad[3];
193 } BMFace;
194
195 typedef struct BMFace_OFlag {
196   BMFace base;
197   struct BMFlagLayer *oflags;
198 } BMFace_OFlag;
199
200 typedef struct BMFlagLayer {
201   short f; /* flags */
202 } BMFlagLayer;
203
204 // #pragma GCC diagnostic ignored "-Wpadded"
205
206 typedef struct BMesh {
207   int totvert, totedge, totloop, totface;
208   int totvertsel, totedgesel, totfacesel;
209
210   /* flag index arrays as being dirty so we can check if they are clean and
211    * avoid looping over the entire vert/edge/face/loop array in those cases.
212    * valid flags are - BM_VERT | BM_EDGE | BM_FACE | BM_LOOP. */
213   char elem_index_dirty;
214
215   /* flag array table as being dirty so we know when its safe to use it,
216    * or when it needs to be re-created */
217   char elem_table_dirty;
218
219   /* element pools */
220   struct BLI_mempool *vpool, *epool, *lpool, *fpool;
221
222   /* mempool lookup tables (optional)
223    * index tables, to map indices to elements via
224    * BM_mesh_elem_table_ensure and associated functions.  don't
225    * touch this or read it directly.\
226    * Use BM_mesh_elem_table_ensure(), BM_vert/edge/face_at_index() */
227   BMVert **vtable;
228   BMEdge **etable;
229   BMFace **ftable;
230
231   /* size of allocated tables */
232   int vtable_tot;
233   int etable_tot;
234   int ftable_tot;
235
236   /* operator api stuff (must be all NULL or all alloc'd) */
237   struct BLI_mempool *vtoolflagpool, *etoolflagpool, *ftoolflagpool;
238
239   uint use_toolflags : 1;
240
241   int toolflag_index;
242   struct BMOperator *currentop;
243
244   CustomData vdata, edata, ldata, pdata;
245
246 #ifdef USE_BMESH_HOLES
247   struct BLI_mempool *looplistpool;
248 #endif
249
250   struct MLoopNorSpaceArray *lnor_spacearr;
251   char spacearr_dirty;
252
253   /* should be copy of scene select mode */
254   /* stored in BMEditMesh too, this is a bit confusing,
255    * make sure they're in sync!
256    * Only use when the edit mesh cant be accessed - campbell */
257   short selectmode;
258
259   /* ID of the shape key this bmesh came from */
260   int shapenr;
261
262   int totflags;
263   ListBase selected;
264
265   BMFace *act_face;
266
267   ListBase errorstack;
268
269   void *py_handle;
270 } BMesh;
271
272 /* BMHeader->htype (char) */
273 enum {
274   BM_VERT = 1,
275   BM_EDGE = 2,
276   BM_LOOP = 4,
277   BM_FACE = 8,
278 };
279
280 typedef struct BMLoopNorEditData {
281   int loop_index;
282   BMLoop *loop;
283   float niloc[3];
284   float nloc[3];
285   float *loc;
286   short *clnors_data;
287 } BMLoopNorEditData;
288
289 typedef struct BMLoopNorEditDataArray {
290   BMLoopNorEditData *lnor_editdata;
291   /**
292    * This one has full amount of loops,
293    * used to map loop index to actual BMLoopNorEditData struct.
294    */
295   BMLoopNorEditData **lidx_to_lnor_editdata;
296
297   int cd_custom_normal_offset;
298   int totloop;
299 } BMLoopNorEditDataArray;
300
301 #define BM_ALL (BM_VERT | BM_EDGE | BM_LOOP | BM_FACE)
302 #define BM_ALL_NOLOOP (BM_VERT | BM_EDGE | BM_FACE)
303
304 enum {
305   BM_SPACEARR_DIRTY = 1 << 0,
306   BM_SPACEARR_DIRTY_ALL = 1 << 1,
307   BM_SPACEARR_BMO_SET = 1 << 2,
308 };
309
310 /* args for _Generic */
311 #define _BM_GENERIC_TYPE_ELEM_NONCONST \
312   void *, BMVert *, BMEdge *, BMLoop *, BMFace *, BMVert_OFlag *, BMEdge_OFlag *, BMFace_OFlag *, \
313       BMElem *, BMElemF *, BMHeader *
314
315 #define _BM_GENERIC_TYPE_ELEM_CONST \
316   const void *, const BMVert *, const BMEdge *, const BMLoop *, const BMFace *, \
317       const BMVert_OFlag *, const BMEdge_OFlag *, const BMFace_OFlag *, const BMElem *, \
318       const BMElemF *, const BMHeader *, void *const, BMVert *const, BMEdge *const, \
319       BMLoop *const, BMFace *const, BMElem *const, BMElemF *const, BMHeader *const
320
321 #define BM_CHECK_TYPE_ELEM_CONST(ele) CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPES_CONST)
322
323 #define BM_CHECK_TYPE_ELEM_NONCONST(ele) CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_ELEM_NONCONST)
324
325 #define BM_CHECK_TYPE_ELEM(ele) \
326   CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_ELEM_NONCONST, _BM_GENERIC_TYPE_ELEM_CONST)
327
328 /* vert */
329 #define _BM_GENERIC_TYPE_VERT_NONCONST BMVert *, BMVert_OFlag *
330 #define _BM_GENERIC_TYPE_VERT_CONST const BMVert *, const BMVert_OFlag *
331 #define BM_CHECK_TYPE_VERT_CONST(ele) CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_VERT_CONST)
332 #define BM_CHECK_TYPE_VERT_NONCONST(ele) CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_ELEM_NONCONST)
333 #define BM_CHECK_TYPE_VERT(ele) \
334   CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_VERT_NONCONST, _BM_GENERIC_TYPE_VERT_CONST)
335 /* edge */
336 #define _BM_GENERIC_TYPE_EDGE_NONCONST BMEdge *, BMEdge_OFlag *
337 #define _BM_GENERIC_TYPE_EDGE_CONST const BMEdge *, const BMEdge_OFlag *
338 #define BM_CHECK_TYPE_EDGE_CONST(ele) CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_EDGE_CONST)
339 #define BM_CHECK_TYPE_EDGE_NONCONST(ele) CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_ELEM_NONCONST)
340 #define BM_CHECK_TYPE_EDGE(ele) \
341   CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_EDGE_NONCONST, _BM_GENERIC_TYPE_EDGE_CONST)
342 /* face */
343 #define _BM_GENERIC_TYPE_FACE_NONCONST BMFace *, BMFace_OFlag *
344 #define _BM_GENERIC_TYPE_FACE_CONST const BMFace *, const BMFace_OFlag *
345 #define BM_CHECK_TYPE_FACE_CONST(ele) CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_FACE_CONST)
346 #define BM_CHECK_TYPE_FACE_NONCONST(ele) CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_ELEM_NONCONST)
347 #define BM_CHECK_TYPE_FACE(ele) \
348   CHECK_TYPE_ANY(ele, _BM_GENERIC_TYPE_FACE_NONCONST, _BM_GENERIC_TYPE_FACE_CONST)
349
350 /* Assignment from a void* to a typed pointer is not allowed in C++,
351  * casting the LHS to void works fine though.
352  */
353 #ifdef __cplusplus
354 #  define BM_CHECK_TYPE_ELEM_ASSIGN(ele) (BM_CHECK_TYPE_ELEM(ele)), *((void **)&ele)
355 #else
356 #  define BM_CHECK_TYPE_ELEM_ASSIGN(ele) (BM_CHECK_TYPE_ELEM(ele)), ele
357 #endif
358
359 /* BMHeader->hflag (char) */
360 enum {
361   BM_ELEM_SELECT = (1 << 0),
362   BM_ELEM_HIDDEN = (1 << 1),
363   BM_ELEM_SEAM = (1 << 2),
364   /**
365    * used for faces and edges, note from the user POV,
366    * this is a sharp edge when disabled */
367   BM_ELEM_SMOOTH = (1 << 3),
368   /**
369    * internal flag, used for ensuring correct normals
370    * during multires interpolation, and any other time
371    * when temp tagging is handy.
372    * always assume dirty & clear before use. */
373   BM_ELEM_TAG = (1 << 4),
374
375   BM_ELEM_DRAW = (1 << 5), /* edge display */
376
377   /* spare tag, assumed dirty, use define in each function to name based on use */
378   // _BM_ELEM_TAG_ALT = (1 << 6),  // UNUSED
379   /**
380    * For low level internal API tagging,
381    * since tools may want to tag verts and not have functions clobber them.
382    * Leave cleared! */
383   BM_ELEM_INTERNAL_TAG = (1 << 7),
384 };
385
386 struct BPy_BMGeneric;
387 extern void bpy_bm_generic_invalidate(struct BPy_BMGeneric *self);
388
389 typedef bool (*BMElemFilterFunc)(const BMElem *, void *user_data);
390 typedef bool (*BMVertFilterFunc)(const BMVert *, void *user_data);
391 typedef bool (*BMEdgeFilterFunc)(const BMEdge *, void *user_data);
392 typedef bool (*BMFaceFilterFunc)(const BMFace *, void *user_data);
393 typedef bool (*BMLoopFilterFunc)(const BMLoop *, void *user_data);
394
395 /* defines */
396 #define BM_ELEM_CD_SET_INT(ele, offset, f) \
397   { \
398     CHECK_TYPE_NONCONST(ele); \
399     assert(offset != -1); \
400     *((int *)((char *)(ele)->head.data + (offset))) = (f); \
401   } \
402   (void)0
403
404 #define BM_ELEM_CD_GET_INT(ele, offset) \
405   (assert(offset != -1), *((int *)((char *)(ele)->head.data + (offset))))
406
407 #if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L)
408 #  define BM_ELEM_CD_GET_VOID_P(ele, offset) \
409     (assert(offset != -1), \
410      _Generic(ele, \
411               GENERIC_TYPE_ANY(POINTER_OFFSET((ele)->head.data, offset), \
412                                _BM_GENERIC_TYPE_ELEM_NONCONST), \
413               GENERIC_TYPE_ANY((const void *)POINTER_OFFSET((ele)->head.data, offset), \
414                                _BM_GENERIC_TYPE_ELEM_CONST)))
415 #else
416 #  define BM_ELEM_CD_GET_VOID_P(ele, offset) \
417     (assert(offset != -1), (void *)((char *)(ele)->head.data + (offset)))
418 #endif
419
420 #define BM_ELEM_CD_SET_FLOAT(ele, offset, f) \
421   { \
422     CHECK_TYPE_NONCONST(ele); \
423     assert(offset != -1); \
424     *((float *)((char *)(ele)->head.data + (offset))) = (f); \
425   } \
426   (void)0
427
428 #define BM_ELEM_CD_GET_FLOAT(ele, offset) \
429   (assert(offset != -1), *((float *)((char *)(ele)->head.data + (offset))))
430
431 #define BM_ELEM_CD_GET_FLOAT_AS_UCHAR(ele, offset) \
432   (assert(offset != -1), (uchar)(BM_ELEM_CD_GET_FLOAT(ele, offset) * 255.0f))
433
434 /*forward declarations*/
435
436 #ifdef USE_BMESH_HOLES
437 #  define BM_FACE_FIRST_LOOP(p) (((BMLoopList *)((p)->loops.first))->first)
438 #else
439 #  define BM_FACE_FIRST_LOOP(p) ((p)->l_first)
440 #endif
441
442 #define BM_DISK_EDGE_NEXT(e, v) \
443   (CHECK_TYPE_INLINE(e, BMEdge *), \
444    CHECK_TYPE_INLINE(v, BMVert *), \
445    BLI_assert(BM_vert_in_edge(e, v)), \
446    (((&e->v1_disk_link)[v == e->v2]).next))
447 #define BM_DISK_EDGE_PREV(e, v) \
448   (CHECK_TYPE_INLINE(e, BMEdge *), \
449    CHECK_TYPE_INLINE(v, BMVert *), \
450    BLI_assert(BM_vert_in_edge(e, v)), \
451    (((&e->v1_disk_link)[v == e->v2]).prev))
452
453 /**
454  * size to use for stack arrays when dealing with NGons,
455  * alloc after this limit is reached.
456  * this value is rather arbitrary */
457 #define BM_DEFAULT_NGON_STACK_SIZE 32
458 /**
459  * size to use for stack arrays dealing with connected mesh data
460  * verts of faces, edges of vert - etc.
461  * often used with #BM_iter_as_arrayN() */
462 #define BM_DEFAULT_ITER_STACK_SIZE 16
463
464 /* avoid inf loop, this value is arbitrary
465  * but should not error on valid cases */
466 #define BM_LOOP_RADIAL_MAX 10000
467 #define BM_NGON_MAX 100000
468
469 /* setting zero so we can catch bugs in OpenMP/BMesh */
470 #ifdef DEBUG
471 #  define BM_OMP_LIMIT 0
472 #else
473 #  define BM_OMP_LIMIT 10000
474 #endif
475
476 #endif /* __BMESH_CLASS_H__ */