Merge branch 'blender2.7'
[blender.git] / source / blender / blenlib / BLI_scanfill.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  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 #ifndef __BLI_SCANFILL_H__
29 #define __BLI_SCANFILL_H__
30
31 /** \file BLI_scanfill.h
32  *  \ingroup bli
33  *  \since March 2001
34  *  \author nzc
35  *  \brief Filling meshes.
36  */
37
38 struct ScanFillVert;
39
40 #ifdef __cplusplus
41 extern "C" {
42 #endif
43
44 typedef struct ScanFillContext {
45         ListBase fillvertbase;
46         ListBase filledgebase;
47         ListBase fillfacebase;
48
49         /* increment this value before adding each curve to skip having to calculate
50          * 'poly_nr' for edges and verts (which can take approx half scanfill time) */
51         unsigned short poly_nr;
52
53         /* private */
54         struct MemArena *arena;
55 } ScanFillContext;
56
57 #define BLI_SCANFILL_ARENA_SIZE MEM_SIZE_OPTIMAL(1 << 14)
58
59 /**
60  * \note this is USHRT_MAX so incrementing  will set to zero
61  * which happens if callers choose to increment #ScanFillContext.poly_nr before adding each curve.
62  * Nowhere else in scanfill do we make use of intentional overflow like this.
63  */
64 #define SF_POLY_UNSET ((unsigned short)-1)
65
66 typedef struct ScanFillVert {
67         struct ScanFillVert *next, *prev;
68         union {
69                 struct ScanFillVert *v;
70                 void                *p;
71                 int                  i;
72                 unsigned int         u;
73         } tmp;
74         /** vertex location */
75         float co[3];
76         /** 2D projection of vertex location */
77         float xy[2];
78         /** index, caller can use how it likes to match the scanfill result with own data */
79         unsigned int keyindex;
80         unsigned short poly_nr;
81         /** number of edges using this vertex */
82         unsigned char edge_tot;
83         /** vert status */
84         unsigned int f : 4;
85         /** flag callers can use as they like */
86         unsigned int user_flag : 4;
87 } ScanFillVert;
88
89 typedef struct ScanFillEdge {
90         struct ScanFillEdge *next, *prev;
91         struct ScanFillVert *v1, *v2;
92         unsigned short poly_nr;
93         unsigned int f : 4;  /* edge status */
94         unsigned int user_flag : 4;  /* flag callers can use as they like */
95         union {
96                 unsigned char c;
97         } tmp;
98 } ScanFillEdge;
99
100 typedef struct ScanFillFace {
101         struct ScanFillFace *next, *prev;
102         struct ScanFillVert *v1, *v2, *v3;
103 } ScanFillFace;
104
105 /* scanfill.c */
106 struct ScanFillVert *BLI_scanfill_vert_add(ScanFillContext *sf_ctx, const float vec[3]);
107 struct ScanFillEdge *BLI_scanfill_edge_add(ScanFillContext *sf_ctx, struct ScanFillVert *v1, struct ScanFillVert *v2);
108
109 enum {
110         BLI_SCANFILL_CALC_QUADTRI_FASTPATH = (1 << 0),
111
112         /* note: using BLI_SCANFILL_CALC_REMOVE_DOUBLES
113          * Assumes ordered edges, otherwise we risk an eternal loop
114          * removing double verts. - campbell */
115         BLI_SCANFILL_CALC_REMOVE_DOUBLES   = (1 << 1),
116
117         /* calculate isolated polygons */
118         BLI_SCANFILL_CALC_POLYS            = (1 << 2),
119
120         /* note: This flag removes checks for overlapping polygons.
121          * when this flag is set, we'll never get back more faces then (totvert - 2) */
122         BLI_SCANFILL_CALC_HOLES            = (1 << 3),
123
124         /* checks valid edge users - can skip for simple loops */
125         BLI_SCANFILL_CALC_LOOSE            = (1 << 4),
126 };
127 void BLI_scanfill_begin(ScanFillContext *sf_ctx);
128 unsigned int BLI_scanfill_calc(ScanFillContext *sf_ctx, const int flag);
129 unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag,
130                           const float nor_proj[3]);
131 void BLI_scanfill_end(ScanFillContext *sf_ctx);
132
133 void BLI_scanfill_begin_arena(ScanFillContext *sf_ctx, struct MemArena *arena);
134 void BLI_scanfill_end_arena(ScanFillContext *sf_ctx, struct MemArena *arena);
135
136
137 /* scanfill_utils.c */
138 bool BLI_scanfill_calc_self_isect(
139         ScanFillContext *sf_ctx,
140         ListBase *fillvertbase,
141         ListBase *filledgebase);
142
143 #ifdef __cplusplus
144 }
145 #endif
146
147 #endif