Spelling Cleanup
[blender.git] / source / blender / bmesh / bmesh.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Geoffrey Bantle, Levi Schooley.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 #ifndef __BMESH_H__
24 #define __BMESH_H__
25
26 /** \file blender/bmesh/bmesh.h
27  *  \ingroup bmesh
28  *
29  * \addtogroup bmesh BMesh
30  *
31  * \brief BMesh is a non-manifold boundary representation designed to replace the current, limited EditMesh structure,
32  * solving many of the design limitations and maintenance issues of EditMesh.
33  *
34  *
35  * \section bm_structure The Structure
36  *
37  * BMesh stores topology in four main element structures:
38  *
39  * - Faces - BMFace
40  * - Loops - BMLoop, (stores per-face-vertex data, UV's, vertex-colors, etc)
41  * - Edges - BMEdge
42  * - Verts - BMVert
43  *
44  *
45  * \subsection bm_header_flags Header Flags
46  * Each element (vertex/edge/face/loop) in a mesh has an associated bit-field called "header flags".
47  *
48  * BMHeader flags should <b>never</b> be read or written to by bmesh operators (see Operators below).
49  *
50  * Access to header flags is done with BM_elem_flag_*() functions.
51  *
52  *
53  * \subsection bm_faces Faces
54  *
55  * Faces in BMesh are stored as a circular linked list of loops. Loops store per-face-vertex data
56  * (amongst other things outlined later in this document), and define the face boundary.
57  *
58  *
59  * \subsection bm_loop The Loop
60  *
61  * Loops define the boundary loop of a face. Each loop logically corresponds to an edge,
62  * which is defined by the loop and next loop's vertices.
63  *
64  * Loops store several handy pointers:
65  *
66  * - BMLoop#v - pointer to the vertex associated with this loop.
67  * - BMLoop#e - pointer to the edge associated with this loop.
68  * - BMLoop#f - pointer to the face associated with this loop.
69  *
70  *
71  * \subsection bm_two_side_face 2-Sided Faces
72  *
73  * There are some situations where you need 2-sided faces (e.g. a face of two vertices).
74  * This is supported by BMesh, but note that such faces should only be used as intermediary steps,
75  * and should not end up in the final mesh.
76  *
77  *
78  * \subsection bm_edges_and_verts Edges and Vertices
79  *
80  * Edges and Vertices in BMesh are much like their counterparts in EditMesh,
81  * except for some members private to the BMesh api.
82  *
83  * \note There can be more then one edge between two vertices in bmesh,
84  * though the rest of blender (e.g. DerivedMesh, CDDM, CCGSubSurf, etc) does not support this.
85  *
86  *
87  * \subsection bm_queries Queries
88  *
89  * The following topological queries are available:
90  *
91  * - Edges/Faces/Loops around a vertex.
92  * - Faces around an edge.
93  * - Loops around an edge.
94  *
95  * These are accessible through the iterator api, which is covered later in this document
96  *
97  * See source/blender/bmesh/bmesh_queries.h for more misc. queries.
98  *
99  *
100  * \section bm_api The BMesh API
101  *
102  * One of the goals of the BMesh API is to make it easy and natural to produce highly maintainable code.
103  * Code duplication, etc are avoided where possible.
104  *
105  *
106  * \subsection bm_iter_api Iterator API
107  *
108  * Most topological queries in BMesh go through an iterator API (see Queries above).
109  * These are defined in bmesh_iterators.h.  If you can, please use the #BM_ITER macro in bmesh_iterators.h
110  *
111  *
112  * \subsection bm_walker_api Walker API
113  *
114  * Topological queries that require a stack (e.g. recursive queries) go through the Walker API,
115  * which is defined in bmesh_walkers.h. Currently the "walkers" are hard-coded into the API,
116  * though a mechanism for plugging in new walkers needs to be added at some point.
117  *
118  * Most topological queries should go through these two APIs;
119  * there are additional functions you can use for topological iteration, but their meant for internal bmesh code.
120  *
121  * Note that the walker API supports delimiter flags, to allow the caller to flag elements not to walk past.
122  *
123  *
124  * \subsection bm_ops Operators
125  *
126  * Operators are an integral part of BMesh. Unlike regular blender operators,
127  * BMesh operators <b>bmo's</b> are designed to be nested (e.g. call other operators).
128  *
129  * Each operator has a number of input/output "slots" which are used to pass settings & data into/out of the operator
130  * (and allows for chaining operators together).
131  *
132  * These slots are identified by name, using strings.
133  *
134  * Access to slots is done with BMO_slot_*() functions.
135  *
136  *
137  * \subsection bm_tool_flags Tool Flags
138  *
139  * The BMesh API provides a set of flags for faces, edges and vertices, which are private to an operator.
140  * These flags may be used by the client operator code as needed
141  * (a common example is flagging elements for use in another operator).
142  * Each call to an operator allocates it's own set of tool flags when it's executed,
143  * avoiding flag conflicts between operators.
144  *
145  * These flags should not be confused with header flags, which are used to store persistent flags
146  * (e.g. selection, hide status, etc).
147  *
148  * Access to tool flags is done with BMO_elem_flag_*() functions.
149  *
150  * \warning Operators are never allowed to read or write to header flags.
151  * They act entirely on the data inside their input slots.
152  * For example an operator should not check the selected state of an element,
153  * there are some exceptions to this - some operators check of a face is smooth.
154  *
155  *
156  * \subsection bm_slot_types Slot Types
157  *
158  * The following slot types are available:
159  *
160  * - integer - #BMO_OP_SLOT_INT
161  * - boolean - #BMO_OP_SLOT_BOOL
162  * - float   - #BMO_OP_SLOT_FLT
163  * - pointer - #BMO_OP_SLOT_PNT
164  * - element buffer - #BMO_OP_SLOT_ELEMENT_BUF - a list of verts/edges/faces
165  * - map     - BMO_OP_SLOT_MAPPING - simple hash map
166  *
167  *
168  * \subsection bm_slot_iter Slot Iterators
169  *
170  * Access to element buffers or maps must go through the slot iterator api, defined in bmesh_operators.h.
171  * Use #BMO_ITER where ever possible.
172  *
173  *
174  * \subsection bm_elem_buf Element Buffers
175  *
176  * The element buffer slot type is used to feed elements (verts/edges/faces) to operators.
177  * Internally they are stored as pointer arrays (which happily has not caused any problems so far).
178  * Many operators take in a buffer of elements, process it,
179  * then spit out a new one; this allows operators to be chained together.
180  *
181  * \note Element buffers may have elements of different types within the same buffer (this is supported by the API.
182  *
183  *
184  * \section bm_fname Function Naming Conventions
185  *
186  * These conventions should be used throughout the bmesh module.
187  *
188  * - BM_xxx() -     High level BMesh API function for use anywhere.
189  * - bmesh_xxx() -  Low level API function.
190  * - bm_xxx() -     'static' functions, not apart of the API at all, but use prefix since they operate on BMesh data.
191  * - BMO_xxx() -    High level operator API function for use anywhere.
192  * - bmo_xxx() -    Low level / internal operator API functions.
193  * - _bm_xxx() -    Functions which are called via macros only.
194  *
195  */
196
197 #ifdef __cplusplus
198 extern "C" {
199 #endif
200
201 #include "DNA_listBase.h"
202 #include "DNA_customdata_types.h"
203
204 #include "BLI_utildefines.h"
205
206 #include "bmesh_class.h"
207
208 /*forward declarations*/
209
210 /*
211  * BMHeader
212  *
213  * All mesh elements begin with a BMHeader. This structure
214  * hold several types of data
215  *
216  * 1: The type of the element (vert, edge, loop or face)
217  * 2: Persistant "header" flags/markings (sharp, seam, select, hidden, ect)
218       note that this is different from the "tool" flags.
219  * 3: Unique ID in the bmesh.
220  * 4: some elements for internal record keeping.
221  *
222 */
223
224 /* BMHeader->htype (char) */
225 enum {
226         BM_VERT = 1,
227         BM_EDGE = 2,
228         BM_LOOP = 4,
229         BM_FACE = 8
230 };
231
232 #define BM_ALL (BM_VERT | BM_EDGE | BM_LOOP | BM_FACE)
233
234 /* BMHeader->hflag (char) */
235 enum {
236         BM_ELEM_SELECT  = (1 << 0),
237         BM_ELEM_HIDDEN  = (1 << 1),
238         BM_ELEM_SEAM    = (1 << 2),
239         BM_ELEM_SMOOTH  = (1 << 3), /* used for faces and edges, note from the user POV,
240                                   * this is a sharp edge when disabled */
241
242         BM_ELEM_TAG     = (1 << 4), /* internal flag, used for ensuring correct normals
243                                  * during multires interpolation, and any other time
244                                  * when temp tagging is handy.
245                                  * always assume dirty & clear before use. */
246
247         /* we have 2 spare flags which is awesome but since we're limited to 8
248          * only add new flags with care! - campbell */
249         /* BM_ELEM_SPARE  = (1 << 5), */
250         /* BM_ELEM_SPARE  = (1 << 6), */
251
252         BM_ELEM_INTERNAL_TAG = (1 << 7) /* for low level internal API tagging,
253                                      * since tools may want to tag verts and
254                                      * not have functions clobber them */
255 };
256
257 /* Mesh Level Ops */
258 extern int bm_mesh_allocsize_default[4];
259
260
261 /* ------------------------------------------------------------------------- */
262 /* bmesh_inline.c */
263
264 /* stuff for dealing with header flags */
265 #define BM_elem_flag_test(   ele, hflag)      _bm_elem_flag_test    (&(ele)->head, hflag)
266 #define BM_elem_flag_enable( ele, hflag)      _bm_elem_flag_enable  (&(ele)->head, hflag)
267 #define BM_elem_flag_disable(ele, hflag)      _bm_elem_flag_disable (&(ele)->head, hflag)
268 #define BM_elem_flag_set(    ele, hflag, val) _bm_elem_flag_set     (&(ele)->head, hflag, val)
269 #define BM_elem_flag_toggle( ele, hflag)      _bm_elem_flag_toggle  (&(ele)->head, hflag)
270 #define BM_elem_flag_merge(  ele_a, ele_b)    _bm_elem_flag_merge   (&(ele_a)->head, &(ele_b)->head)
271
272 BM_INLINE char _bm_elem_flag_test(const BMHeader *head, const char hflag);
273 BM_INLINE void _bm_elem_flag_enable(BMHeader *head, const char hflag);
274 BM_INLINE void _bm_elem_flag_disable(BMHeader *head, const char hflag);
275 BM_INLINE void _bm_elem_flag_set(BMHeader *head, const char hflag, const int val);
276 BM_INLINE void _bm_elem_flag_toggle(BMHeader *head, const char hflag);
277 BM_INLINE void _bm_elem_flag_merge(BMHeader *head_a, BMHeader *head_b);
278
279 /* notes on BM_elem_index_set(...) usage,
280  * Set index is sometimes abused as temp storage, other times we cant be
281  * sure if the index values are valid because certain operations have modified
282  * the mesh structure.
283  *
284  * To set the elements to valid indices 'BM_mesh_elem_index_ensure' should be used
285  * rather then adding inline loops, however there are cases where we still
286  * set the index directly
287  *
288  * In an attempt to manage this, here are 3 tags Im adding to uses of
289  * 'BM_elem_index_set'
290  *
291  * - 'set_inline'  -- since the data is already being looped over set to a
292  *                    valid value inline.
293  *
294  * - 'set_dirty!'  -- intentionally sets the index to an invalid value,
295  *                    flagging 'bm->elem_index_dirty' so we dont use it.
296  *
297  * - 'set_ok'      -- this is valid use since the part of the code is low level.
298  *
299  * - 'set_ok_invalid'  -- set to -1 on purpose since this should not be
300  *                    used without a full array re-index, do this on
301  *                    adding new vert/edge/faces since they may be added at
302  *                    the end of the array.
303  *
304  * - 'set_loop'    -- currently loop index values are not used used much so
305  *                    assume each case they are dirty.
306  * - campbell */
307
308 #define BM_elem_index_get(ele)           _bm_elem_index_get(&(ele)->head)
309 #define BM_elem_index_set(ele, index)    _bm_elem_index_set(&(ele)->head, index)
310 BM_INLINE int  _bm_elem_index_get(const BMHeader *ele);
311 BM_INLINE void _bm_elem_index_set(BMHeader *ele, const int index);
312
313 #ifdef USE_BMESH_HOLES
314 #  define BM_FACE_FIRST_LOOP(p) (((BMLoopList *)((p)->loops.first))->first)
315 #else
316 #  define BM_FACE_FIRST_LOOP(p) ((p)->l_first)
317 #endif
318
319 /* size to use for static arrays when dealing with NGons,
320  * alloc after this limit is reached.
321  * this value is rather arbitrary */
322 #define BM_NGON_STACK_SIZE 32
323
324 /* avoid inf loop, this value is arbtrary
325  * but should not error on valid cases */
326 #define BM_LOOP_RADIAL_MAX 10000
327 #define BM_NGON_MAX 100000
328
329 /* include the rest of the API */
330 #include "bmesh_operator_api.h"
331 #include "bmesh_error.h"
332
333 #include "intern/bmesh_construct.h"
334 #include "intern/bmesh_core.h"
335 #include "intern/bmesh_interp.h"
336 #include "intern/bmesh_iterators.h"
337 #include "intern/bmesh_marking.h"
338 #include "intern/bmesh_mesh.h"
339 #include "intern/bmesh_mods.h"
340 #include "intern/bmesh_operators.h"
341 #include "intern/bmesh_polygon.h"
342 #include "intern/bmesh_queries.h"
343 #include "intern/bmesh_walkers.h"
344 #include "intern/bmesh_walkers.h"
345
346 #include "intern/bmesh_inline.c"
347 #include "intern/bmesh_operator_api_inline.c"
348
349 #ifdef __cplusplus
350 }
351 #endif
352
353 #endif /* __BMESH_H__ */