Merge branch 'blender2.7'
[blender.git] / source / blender / blenkernel / intern / CCGSubSurf_util.c
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  * ***** END GPL LICENSE BLOCK *****
19  */
20
21 /** \file blender/blenkernel/intern/CCGSubSurf_util.c
22  *  \ingroup bke
23  */
24
25 #include <stdlib.h>
26 #include <string.h>
27 #include <math.h>
28
29 #include "MEM_guardedalloc.h"
30 #include "BLI_sys_types.h" // for intptr_t support
31
32 #include "BLI_utildefines.h" /* for BLI_assert */
33
34 #include "CCGSubSurf.h"
35 #include "CCGSubSurf_intern.h"
36
37 /**
38  * Hash implementation.
39  */
40
41 static int kHashSizes[] = {
42         1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
43         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
44         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459
45 };
46
47 /* Generic hash functions. */
48
49 EHash *ccg_ehash_new(int estimatedNumEntries,
50                      CCGAllocatorIFC *allocatorIFC,
51                      CCGAllocatorHDL allocator)
52 {
53         EHash *eh = allocatorIFC->alloc(allocator, sizeof(*eh));
54         eh->allocatorIFC = *allocatorIFC;
55         eh->allocator = allocator;
56         eh->numEntries = 0;
57         eh->curSizeIdx = 0;
58         while (kHashSizes[eh->curSizeIdx] < estimatedNumEntries)
59                 eh->curSizeIdx++;
60         eh->curSize = kHashSizes[eh->curSizeIdx];
61         eh->buckets = EHASH_alloc(eh, eh->curSize * sizeof(*eh->buckets));
62         memset(eh->buckets, 0, eh->curSize * sizeof(*eh->buckets));
63
64         return eh;
65 }
66
67 void ccg_ehash_free(EHash *eh, EHEntryFreeFP freeEntry, void *userData)
68 {
69         int numBuckets = eh->curSize;
70
71         while (numBuckets--) {
72                 EHEntry *entry = eh->buckets[numBuckets];
73
74                 while (entry) {
75                         EHEntry *next = entry->next;
76
77                         freeEntry(entry, userData);
78
79                         entry = next;
80                 }
81         }
82
83         EHASH_free(eh, eh->buckets);
84         EHASH_free(eh, eh);
85 }
86
87 void ccg_ehash_insert(EHash *eh, EHEntry *entry)
88 {
89         int numBuckets = eh->curSize;
90         int hash = EHASH_hash(eh, entry->key);
91         entry->next = eh->buckets[hash];
92         eh->buckets[hash] = entry;
93         eh->numEntries++;
94
95         if (UNLIKELY(eh->numEntries > (numBuckets * 3))) {
96                 EHEntry **oldBuckets = eh->buckets;
97                 eh->curSize = kHashSizes[++eh->curSizeIdx];
98
99                 eh->buckets = EHASH_alloc(eh, eh->curSize * sizeof(*eh->buckets));
100                 memset(eh->buckets, 0, eh->curSize * sizeof(*eh->buckets));
101
102                 while (numBuckets--) {
103                         for (entry = oldBuckets[numBuckets]; entry; ) {
104                                 EHEntry *next = entry->next;
105
106                                 hash = EHASH_hash(eh, entry->key);
107                                 entry->next = eh->buckets[hash];
108                                 eh->buckets[hash] = entry;
109
110                                 entry = next;
111                         }
112                 }
113
114                 EHASH_free(eh, oldBuckets);
115         }
116 }
117
118 void *ccg_ehash_lookupWithPrev(EHash *eh, void *key, void ***prevp_r)
119 {
120         int hash = EHASH_hash(eh, key);
121         void **prevp = (void **) &eh->buckets[hash];
122         EHEntry *entry;
123
124         for (; (entry = *prevp); prevp = (void **) &entry->next) {
125                 if (entry->key == key) {
126                         *prevp_r = (void **) prevp;
127                         return entry;
128                 }
129         }
130
131         return NULL;
132 }
133
134 void *ccg_ehash_lookup(EHash *eh, void *key)
135 {
136         int hash = EHASH_hash(eh, key);
137         EHEntry *entry;
138
139         for (entry = eh->buckets[hash]; entry; entry = entry->next) {
140                 if (entry->key == key)
141                         break;
142         }
143
144         return entry;
145 }
146
147 /* Hash elements iteration. */
148
149 void ccg_ehashIterator_init(EHash *eh, EHashIterator *ehi)
150 {
151         /* fill all members */
152         ehi->eh = eh;
153         ehi->curBucket = -1;
154         ehi->curEntry = NULL;
155
156         while (!ehi->curEntry) {
157                 ehi->curBucket++;
158                 if (ehi->curBucket == ehi->eh->curSize)
159                         break;
160                 ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
161         }
162 }
163
164 void *ccg_ehashIterator_getCurrent(EHashIterator *ehi)
165 {
166         return ehi->curEntry;
167 }
168
169 void ccg_ehashIterator_next(EHashIterator *ehi)
170 {
171         if (ehi->curEntry) {
172                 ehi->curEntry = ehi->curEntry->next;
173                 while (!ehi->curEntry) {
174                         ehi->curBucket++;
175                         if (ehi->curBucket == ehi->eh->curSize)
176                                 break;
177                         ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
178                 }
179         }
180 }
181 int ccg_ehashIterator_isStopped(EHashIterator *ehi)
182 {
183         return !ehi->curEntry;
184 }
185
186 /**
187  * Standard allocator implementation.
188  */
189
190 static void *_stdAllocator_alloc(CCGAllocatorHDL UNUSED(a), int numBytes)
191 {
192         return MEM_mallocN(numBytes, "CCG standard alloc");
193 }
194
195 static void *_stdAllocator_realloc(CCGAllocatorHDL UNUSED(a),
196                                    void *ptr,
197                                    int newSize,
198                                    int UNUSED(oldSize))
199 {
200         return MEM_reallocN(ptr, newSize);
201 }
202
203 static void _stdAllocator_free(CCGAllocatorHDL UNUSED(a), void *ptr)
204 {
205         MEM_freeN(ptr);
206 }
207
208 CCGAllocatorIFC *ccg_getStandardAllocatorIFC(void)
209 {
210         static CCGAllocatorIFC ifc;
211
212         ifc.alloc = _stdAllocator_alloc;
213         ifc.realloc = _stdAllocator_realloc;
214         ifc.free = _stdAllocator_free;
215         ifc.release = NULL;
216
217         return &ifc;
218 }
219
220 /**
221  * Catmull-Clark Gridding Subdivision Surface.
222  */
223
224 #ifdef DUMP_RESULT_GRIDS
225 void ccgSubSurf__dumpCoords(CCGSubSurf *ss)
226 {
227         int vertDataSize = ss->meshIFC.vertDataSize;
228         int subdivLevels = ss->subdivLevels;
229         int gridSize = ccg_gridsize(subdivLevels);
230         int edgeSize = ccg_edgesize(subdivLevels);
231         int i, index, S;
232
233         for (i = 0, index = 0; i < ss->vMap->curSize; i++) {
234                 CCGVert *v = (CCGVert *) ss->vMap->buckets[i];
235                 for (; v; v = v->next, index++) {
236                         float *co = VERT_getCo(v, subdivLevels);
237                         printf("vertex index=%d, co=(%f, %f, %f)\n",
238                                index, co[0], co[1], co[2]);
239                 }
240         }
241
242         for (i = 0, index = 0; i < ss->eMap->curSize; i++) {
243                 CCGEdge *e = (CCGEdge *) ss->eMap->buckets[i];
244                 for (; e; e = e->next, index++) {
245                         int x;
246                         float *co = VERT_getCo(e->v0, subdivLevels);
247                         printf("edge index=%d, start_co=(%f, %f, %f)\n",
248                                index, co[0], co[1], co[2]);
249                         for (x = 0; x < edgeSize; x++) {
250                                 float *co = EDGE_getCo(e, subdivLevels, x);
251                                 printf("edge index=%d, seg=%d, co=(%f, %f, %f)\n",
252                                        index, x, co[0], co[1], co[2]);
253                         }
254                         co = VERT_getCo(e->v1, subdivLevels);
255                         printf("edge index=%d, end_co=(%f, %f, %f)\n",
256                                index, co[0], co[1], co[2]);
257                 }
258         }
259
260         for (i = 0, index = 0; i < ss->fMap->curSize; i++) {
261                 CCGFace *f = (CCGFace *) ss->fMap->buckets[i];
262                 for (; f; f = f->next, index++) {
263                         for (S = 0; S < f->numVerts; S++) {
264                                 CCGVert *v = FACE_getVerts(f)[S];
265                                 float *co = VERT_getCo(v, subdivLevels);
266                                 printf("face index=%d, vertex=%d, coord=(%f, %f, %f)\n",
267                                        index, S, co[0], co[1], co[2]);
268                         }
269                 }
270         }
271
272         for (i = 0, index = 0; i < ss->fMap->curSize; i++) {
273                 CCGFace *f = (CCGFace *) ss->fMap->buckets[i];
274                 for (; f; f = f->next, index++) {
275                         for (S = 0; S < f->numVerts; S++) {
276                                 CCGEdge *e = FACE_getEdges(f)[S];
277                                 float *co1 = VERT_getCo(e->v0, subdivLevels);
278                                 float *co2 = VERT_getCo(e->v1, subdivLevels);
279                                 printf("face index=%d, edge=%d, coord1=(%f, %f, %f), coord2=(%f, %f, %f)\n",
280                                        index, S, co1[0], co1[1], co1[2], co2[0], co2[1], co2[2]);
281                         }
282                 }
283         }
284
285         for (i = 0, index = 0; i < ss->fMap->curSize; i++) {
286                 CCGFace *f = (CCGFace *) ss->fMap->buckets[i];
287                 for (; f; f = f->next, index++) {
288                         for (S = 0; S < f->numVerts; S++) {
289                                 int x, y;
290                                 for (x = 0; x < gridSize; x++) {
291                                         for (y = 0; y < gridSize; y++) {
292                                                 float *co = FACE_getIFCo(f, subdivLevels, S, x, y);
293                                                 printf("face index=%d. corner=%d, x=%d, y=%d, coord=(%f, %f, %f)\n",
294                                                         index, S, x, y, co[0], co[1], co[2]);
295                                         }
296                                 }
297                                 for (x = 0; x < gridSize; x++) {
298                                         float *co = FACE_getIECo(f, subdivLevels, S, x);
299                                         printf("face index=%d. cornder=%d, ie_index=%d, coord=(%f, %f, %f)\n",
300                                                index, S, x, co[0], co[1], co[2]);
301                                 }
302                         }
303                 }
304         }
305 }
306 #endif  /* DUMP_RESULT_GRIDS */