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