Cleanup: style, use braces for blenkernel
[blender.git] / source / blender / blenkernel / intern / CCGSubSurf_util.c
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 /** \file
18  * \ingroup bke
19  */
20
21 #include <stdlib.h>
22 #include <string.h>
23 #include <math.h>
24
25 #include "MEM_guardedalloc.h"
26 #include "BLI_sys_types.h"  // for intptr_t support
27
28 #include "BLI_utildefines.h" /* for BLI_assert */
29
30 #include "CCGSubSurf.h"
31 #include "CCGSubSurf_intern.h"
32
33 /**
34  * Hash implementation.
35  */
36
37 static int kHashSizes[] = {
38     1,       3,       5,       11,      17,       37,       67,       131,       257,       521,
39     1031,    2053,    4099,    8209,    16411,    32771,    65537,    131101,    262147,    524309,
40     1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
41 };
42
43 /* Generic hash functions. */
44
45 EHash *ccg_ehash_new(int estimatedNumEntries,
46                      CCGAllocatorIFC *allocatorIFC,
47                      CCGAllocatorHDL allocator)
48 {
49   EHash *eh = allocatorIFC->alloc(allocator, sizeof(*eh));
50   eh->allocatorIFC = *allocatorIFC;
51   eh->allocator = allocator;
52   eh->numEntries = 0;
53   eh->curSizeIdx = 0;
54   while (kHashSizes[eh->curSizeIdx] < estimatedNumEntries) {
55     eh->curSizeIdx++;
56   }
57   eh->curSize = kHashSizes[eh->curSizeIdx];
58   eh->buckets = EHASH_alloc(eh, eh->curSize * sizeof(*eh->buckets));
59   memset(eh->buckets, 0, eh->curSize * sizeof(*eh->buckets));
60
61   return eh;
62 }
63
64 void ccg_ehash_free(EHash *eh, EHEntryFreeFP freeEntry, void *userData)
65 {
66   int numBuckets = eh->curSize;
67
68   while (numBuckets--) {
69     EHEntry *entry = eh->buckets[numBuckets];
70
71     while (entry) {
72       EHEntry *next = entry->next;
73
74       freeEntry(entry, userData);
75
76       entry = next;
77     }
78   }
79
80   EHASH_free(eh, eh->buckets);
81   EHASH_free(eh, eh);
82 }
83
84 void ccg_ehash_insert(EHash *eh, EHEntry *entry)
85 {
86   int numBuckets = eh->curSize;
87   int hash = EHASH_hash(eh, entry->key);
88   entry->next = eh->buckets[hash];
89   eh->buckets[hash] = entry;
90   eh->numEntries++;
91
92   if (UNLIKELY(eh->numEntries > (numBuckets * 3))) {
93     EHEntry **oldBuckets = eh->buckets;
94     eh->curSize = kHashSizes[++eh->curSizeIdx];
95
96     eh->buckets = EHASH_alloc(eh, eh->curSize * sizeof(*eh->buckets));
97     memset(eh->buckets, 0, eh->curSize * sizeof(*eh->buckets));
98
99     while (numBuckets--) {
100       for (entry = oldBuckets[numBuckets]; entry;) {
101         EHEntry *next = entry->next;
102
103         hash = EHASH_hash(eh, entry->key);
104         entry->next = eh->buckets[hash];
105         eh->buckets[hash] = entry;
106
107         entry = next;
108       }
109     }
110
111     EHASH_free(eh, oldBuckets);
112   }
113 }
114
115 void *ccg_ehash_lookupWithPrev(EHash *eh, void *key, void ***prevp_r)
116 {
117   int hash = EHASH_hash(eh, key);
118   void **prevp = (void **)&eh->buckets[hash];
119   EHEntry *entry;
120
121   for (; (entry = *prevp); prevp = (void **)&entry->next) {
122     if (entry->key == key) {
123       *prevp_r = (void **)prevp;
124       return entry;
125     }
126   }
127
128   return NULL;
129 }
130
131 void *ccg_ehash_lookup(EHash *eh, void *key)
132 {
133   int hash = EHASH_hash(eh, key);
134   EHEntry *entry;
135
136   for (entry = eh->buckets[hash]; entry; entry = entry->next) {
137     if (entry->key == key) {
138       break;
139     }
140   }
141
142   return entry;
143 }
144
145 /* Hash elements iteration. */
146
147 void ccg_ehashIterator_init(EHash *eh, EHashIterator *ehi)
148 {
149   /* fill all members */
150   ehi->eh = eh;
151   ehi->curBucket = -1;
152   ehi->curEntry = NULL;
153
154   while (!ehi->curEntry) {
155     ehi->curBucket++;
156     if (ehi->curBucket == ehi->eh->curSize) {
157       break;
158     }
159     ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
160   }
161 }
162
163 void *ccg_ehashIterator_getCurrent(EHashIterator *ehi)
164 {
165   return ehi->curEntry;
166 }
167
168 void ccg_ehashIterator_next(EHashIterator *ehi)
169 {
170   if (ehi->curEntry) {
171     ehi->curEntry = ehi->curEntry->next;
172     while (!ehi->curEntry) {
173       ehi->curBucket++;
174       if (ehi->curBucket == ehi->eh->curSize) {
175         break;
176       }
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", index, co[0], co[1], co[2]);
238     }
239   }
240
241   for (i = 0, index = 0; i < ss->eMap->curSize; i++) {
242     CCGEdge *e = (CCGEdge *)ss->eMap->buckets[i];
243     for (; e; e = e->next, index++) {
244       int x;
245       float *co = VERT_getCo(e->v0, subdivLevels);
246       printf("edge index=%d, start_co=(%f, %f, %f)\n", index, co[0], co[1], co[2]);
247       for (x = 0; x < edgeSize; x++) {
248         float *co = EDGE_getCo(e, subdivLevels, x);
249         printf("edge index=%d, seg=%d, co=(%f, %f, %f)\n", index, x, co[0], co[1], co[2]);
250       }
251       co = VERT_getCo(e->v1, subdivLevels);
252       printf("edge index=%d, end_co=(%f, %f, %f)\n", index, co[0], co[1], co[2]);
253     }
254   }
255
256   for (i = 0, index = 0; i < ss->fMap->curSize; i++) {
257     CCGFace *f = (CCGFace *)ss->fMap->buckets[i];
258     for (; f; f = f->next, index++) {
259       for (S = 0; S < f->numVerts; S++) {
260         CCGVert *v = FACE_getVerts(f)[S];
261         float *co = VERT_getCo(v, subdivLevels);
262         printf("face index=%d, vertex=%d, coord=(%f, %f, %f)\n", index, S, co[0], co[1], co[2]);
263       }
264     }
265   }
266
267   for (i = 0, index = 0; i < ss->fMap->curSize; i++) {
268     CCGFace *f = (CCGFace *)ss->fMap->buckets[i];
269     for (; f; f = f->next, index++) {
270       for (S = 0; S < f->numVerts; S++) {
271         CCGEdge *e = FACE_getEdges(f)[S];
272         float *co1 = VERT_getCo(e->v0, subdivLevels);
273         float *co2 = VERT_getCo(e->v1, subdivLevels);
274         printf("face index=%d, edge=%d, coord1=(%f, %f, %f), coord2=(%f, %f, %f)\n",
275                index,
276                S,
277                co1[0],
278                co1[1],
279                co1[2],
280                co2[0],
281                co2[1],
282                co2[2]);
283       }
284     }
285   }
286
287   for (i = 0, index = 0; i < ss->fMap->curSize; i++) {
288     CCGFace *f = (CCGFace *)ss->fMap->buckets[i];
289     for (; f; f = f->next, index++) {
290       for (S = 0; S < f->numVerts; S++) {
291         int x, y;
292         for (x = 0; x < gridSize; x++) {
293           for (y = 0; y < gridSize; y++) {
294             float *co = FACE_getIFCo(f, subdivLevels, S, x, y);
295             printf("face index=%d. corner=%d, x=%d, y=%d, coord=(%f, %f, %f)\n",
296                    index,
297                    S,
298                    x,
299                    y,
300                    co[0],
301                    co[1],
302                    co[2]);
303           }
304         }
305         for (x = 0; x < gridSize; x++) {
306           float *co = FACE_getIECo(f, subdivLevels, S, x);
307           printf("face index=%d. cornder=%d, ie_index=%d, coord=(%f, %f, %f)\n",
308                  index,
309                  S,
310                  x,
311                  co[0],
312                  co[1],
313                  co[2]);
314         }
315       }
316     }
317   }
318 }
319 #endif /* DUMP_RESULT_GRIDS */