diff options
Diffstat (limited to 'source/blender/blenlib')
| -rw-r--r-- | source/blender/blenlib/BLI_array.h | 6 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_editVert.h | 3 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_scanfill.h | 6 | ||||
| -rwxr-xr-x | source/blender/blenlib/BLI_smallhash.h | 73 | ||||
| -rwxr-xr-x | source/blender/blenlib/BLI_sparsemap.h | 81 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_threads.h | 1 | ||||
| -rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | source/blender/blenlib/SConscript | 2 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 4 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/math_base_inline.c | 2 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/pbvh.c | 2 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/scanfill.c | 190 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/smallhash.c | 281 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/threads.c | 5 |
14 files changed, 589 insertions, 70 deletions
diff --git a/source/blender/blenlib/BLI_array.h b/source/blender/blenlib/BLI_array.h index a5453f1537b..9fa66e91393 100644 --- a/source/blender/blenlib/BLI_array.h +++ b/source/blender/blenlib/BLI_array.h @@ -177,11 +177,11 @@ * same purpose as BLI_array_staticdeclare() * but use when the max size is known ahead of time */ #define BLI_array_fixedstack_declare(arr, maxstatic, realsize, allocstr) \ - char _##arr##_static[maxstatic*sizeof(*arr)]; \ + char _##arr##_static[maxstatic*sizeof(*(arr))]; \ const int _##arr##_is_static= ((void *)_##arr##_static) != ( \ - arr= (realsize <= maxstatic) ? \ + arr= ((realsize) <= maxstatic) ? \ (void *)_##arr##_static : \ - MEM_mallocN(sizeof(*arr)*realsize, allocstr) \ + MEM_mallocN(sizeof(*(arr)) * (realsize), allocstr) \ ) \ #define BLI_array_fixedstack_free(arr) \ diff --git a/source/blender/blenlib/BLI_editVert.h b/source/blender/blenlib/BLI_editVert.h index b5096abc5bc..d241bfca75a 100644 --- a/source/blender/blenlib/BLI_editVert.h +++ b/source/blender/blenlib/BLI_editVert.h @@ -42,6 +42,7 @@ #include "BLO_sys_types.h" // for intptr_t support struct DerivedMesh; +struct BLI_mempool; /* note; changing this also might affect the undo copy in editmesh.c */ typedef struct EditVert @@ -155,6 +156,8 @@ typedef struct EditMesh HashEdge *hashedgetab; /* this is for the editmesh_fastmalloc */ + struct BLI_mempool *vertpool, *edgepool, *facepool; + EditVert *allverts, *curvert; EditEdge *alledges, *curedge; EditFace *allfaces, *curface; diff --git a/source/blender/blenlib/BLI_scanfill.h b/source/blender/blenlib/BLI_scanfill.h index 5c788bc6bb7..890a8c8247d 100644 --- a/source/blender/blenlib/BLI_scanfill.h +++ b/source/blender/blenlib/BLI_scanfill.h @@ -51,6 +51,12 @@ extern "C" { /* scanfill.c: used in displist only... */ struct EditVert *BLI_addfillvert(float *vec); struct EditEdge *BLI_addfilledge(struct EditVert *v1, struct EditVert *v2); + +/* Optionally set EditEdge f to this to mark original boundary edges. + Only needed if there are internal diagonal edges pased to BLI_edgefill. */ +#define FILLBOUNDARY 1 + +int BLI_begin_edgefill(void); int BLI_edgefill(short mat_nr); void BLI_end_edgefill(void); diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h new file mode 100755 index 00000000000..50631769ba9 --- /dev/null +++ b/source/blender/blenlib/BLI_smallhash.h @@ -0,0 +1,73 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2008 Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Joseph Eagar. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_SMALLHASH_H__ +#define __BLI_SMALLHASH_H__ + +/** \file BLI_smallhash.h + * \ingroup bli + */ + +/* a light stack-friendly hash library, + * (it uses stack space for smallish hash tables) */ + +/* based on a doubling non-chaining approach */ + +typedef struct { + uintptr_t key; + void *val; +} SmallHashEntry; + +/*how much stack space to use before dynamically allocating memory*/ +#define SMSTACKSIZE 521 +typedef struct SmallHash { + SmallHashEntry *table; + SmallHashEntry _stacktable[SMSTACKSIZE]; + SmallHashEntry _copytable[SMSTACKSIZE]; + SmallHashEntry *stacktable, *copytable; + int used; + int curhash; + int size; +} SmallHash; + +typedef struct { + SmallHash *hash; + int i; +} SmallHashIter; + +void BLI_smallhash_init(SmallHash *hash); +void BLI_smallhash_release(SmallHash *hash); +void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item); +void BLI_smallhash_remove(SmallHash *hash, uintptr_t key); +void * BLI_smallhash_lookup(SmallHash *hash, uintptr_t key); +int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key); +int BLI_smallhash_count(SmallHash *hash); +void * BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key); +void * BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key); +/* void BLI_smallhash_print(SmallHash *hash); */ /* UNUSED */ + +#endif /* __BLI_SMALLHASH_H__ */ diff --git a/source/blender/blenlib/BLI_sparsemap.h b/source/blender/blenlib/BLI_sparsemap.h new file mode 100755 index 00000000000..654cafbc200 --- /dev/null +++ b/source/blender/blenlib/BLI_sparsemap.h @@ -0,0 +1,81 @@ +#if 0 +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung + * All rights reserved. + * + * Contributor(s): Joseph Eagar (original author) + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_SPARSEMAP_H__ +#define __BLI_SPARSEMAP_H__ + +/** \file BLI_sparsemap.h + * \ingroup bli + */ + +#include "BLI_math_inline.h" + +typedef struct SparseMap { + int max; + int blocksize; + void **blocks; + int totblock; +} SparseMap; + +MALWAYS_INLINE SparseMap *BLI_sparsemap_new(int blocksize, char *name) +{ + SparseMap *sm = MEM_callocN(sizeof(SparseMap), name); + + sm->blocksize = blocksize; + return sm; +} + +MALWAYS_INLINE void BLI_sparsemap_free(SparseMap *sm) +{ + if (sm->blocks) + MEM_freeN(sm->blocks); + + MEM_freeN(sm); +} + +MALWAYS_INLINE void BLI_sparsemap_set(SparseMap *sm, int index, void *ptr) +{ + if (index >= sm->max || (sm->blocks && !sm->blocks[index/sm->blocksize])) { + int totblock = MAX2((index+1)/sm->blocksize, 2); + void *blocks = MEM_callocN(sizeof(void*)*totblock); + + if (sm->blocks) + memcpy(blocks, sm->blocks, sizeof(void*)*sm->totblock); + sm->totblock = totblock; + MEM_freeN(sm->blocks); + sm->blocks = blocks; + } + + if (!sm->blocks[index/sm->blocksize]) { + sm->blocks[index/sm->blocksize] = MEM_mallocN(sizeof(void*)*sm->blocksize); + } + + sm->blocks[index/sm->blocksize] = ptr; +} + +#endif /* __BLI_SPARSEMAP_H__ */ + +#endif diff --git a/source/blender/blenlib/BLI_threads.h b/source/blender/blenlib/BLI_threads.h index 8e75a2db629..03bf375a894 100644 --- a/source/blender/blenlib/BLI_threads.h +++ b/source/blender/blenlib/BLI_threads.h @@ -76,6 +76,7 @@ int BLI_system_thread_count(void); /* gets the number of threads the system can #define LOCK_OPENGL 5 #define LOCK_NODES 6 #define LOCK_MOVIECLIP 7 +#define LOCK_SCANFILL 8 void BLI_lock_thread(int type); void BLI_unlock_thread(int type); diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 03e3b8288ae..55a5be3fbc2 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -79,6 +79,7 @@ set(SRC intern/rand.c intern/rct.c intern/scanfill.c + intern/smallhash.c intern/storage.c intern/string.c intern/string_utf8.c @@ -89,6 +90,8 @@ set(SRC intern/winstuff.c BLI_array.h + BLI_smallhash.h + BLI_sparsemap.h BLI_args.h BLI_blenlib.h BLI_boxpack2d.h diff --git a/source/blender/blenlib/SConscript b/source/blender/blenlib/SConscript index 00caf8cd01d..c8172439167 100644 --- a/source/blender/blenlib/SConscript +++ b/source/blender/blenlib/SConscript @@ -5,6 +5,8 @@ sources = env.Glob('intern/*.c') cflags='' incs = '. ../makesdna ../blenkernel #/intern/guardedalloc #/intern/ghost ../editors/include ../gpu ../blenloader' +incs += ' ../windowmanager ../bmesh #/extern/glew/include' + incs += ' ' + env['BF_FREETYPE_INC'] incs += ' ' + env['BF_ZLIB_INC'] defs = [] diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index e10082348be..950acb21e17 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -47,7 +47,7 @@ #include "BLO_sys_types.h" // for intptr_t support /***/ -static unsigned int hashsizes[]= { +unsigned int hashsizes[]= { 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, @@ -61,7 +61,7 @@ GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) GHash *gh= MEM_mallocN(sizeof(*gh), info); gh->hashfp= hashfp; gh->cmpfp= cmpfp; - gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, FALSE, FALSE); + gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, TRUE, FALSE); gh->cursize= 0; gh->nentries= 0; diff --git a/source/blender/blenlib/intern/math_base_inline.c b/source/blender/blenlib/intern/math_base_inline.c index 7e04e0ae566..3977940d135 100644 --- a/source/blender/blenlib/intern/math_base_inline.c +++ b/source/blender/blenlib/intern/math_base_inline.c @@ -106,7 +106,7 @@ MINLINE float interpf(float target, float origin, float fac) * the distance gets very high, 180d would be inf, but this case isn't valid */ MINLINE float shell_angle_to_dist(const float angle) { - return (angle < SMALL_NUMBER) ? 1.0f : fabsf(1.0f / cosf(angle)); + return (1.0f + SMALL_NUMBER) / ((float)fabs(cosf(angle)) + SMALL_NUMBER); } /* used for zoom values*/ diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c index 5c7a29c6277..b7175db4ca3 100644 --- a/source/blender/blenlib/intern/pbvh.c +++ b/source/blender/blenlib/intern/pbvh.c @@ -1585,7 +1585,7 @@ void BLI_pbvh_apply_vertCos(PBVH *pbvh, float (*vertCos)[3]) } /* coordinates are new -- normals should also be updated */ - mesh_calc_normals(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL); + mesh_calc_normals_tessface(pbvh->verts, pbvh->totvert, pbvh->faces, pbvh->totprim, NULL); for (a= 0; a < pbvh->totnode; ++a) BLI_pbvh_node_mark_update(&pbvh->nodes[a]); diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c index 369984c1719..7652cc4f4af 100644 --- a/source/blender/blenlib/intern/scanfill.c +++ b/source/blender/blenlib/intern/scanfill.c @@ -30,6 +30,10 @@ * \ingroup bli */ +#include <stdio.h> +#include <math.h> +#include <stdlib.h> +#include <string.h> #include "MEM_guardedalloc.h" @@ -38,6 +42,8 @@ #include "BLI_listbase.h" #include "BLI_math.h" #include "BLI_scanfill.h" +#include "BLI_utildefines.h" +#include "BLI_threads.h" /* callbacks for errors and interrupts and some goo */ static void (*BLI_localErrorCallBack)(const char*) = NULL; @@ -137,54 +143,64 @@ struct mem_elements { only to be used within loops, and not by one function at a time free in the end, with argument '-1' */ +#define MEM_ELEM_BLOCKSIZE 16384 +static struct mem_elements * melem__cur= 0; +static int melem__offs= 0; /* the current free address */ +static ListBase melem__lb= {NULL, NULL}; -static void *new_mem_element(int size) +static void *mem_element_new(int size) { - int blocksize= 16384; - static int offs= 0; /* the current free address */ - static struct mem_elements *cur= 0; - static ListBase lb= {0, 0}; - void *adr; + BLI_assert(!(size>10000 || size==0)); /* this is invalid use! */ + + size = (size + 3 ) & ~3; /* allocate in units of 4 */ - if(size>10000 || size==0) { - printf("incorrect use of new_mem_element\n"); + if(melem__cur && (size + melem__offs < MEM_ELEM_BLOCKSIZE)) { + void *adr= (void *) (melem__cur->data+melem__offs); + melem__offs+= size; + return adr; } - else if(size== -1) { - cur= lb.first; - while(cur) { - MEM_freeN(cur->data); - cur= cur->next; - } - BLI_freelistN(&lb); - - return NULL; + else { + melem__cur= MEM_callocN( sizeof(struct mem_elements), "newmem"); + melem__cur->data= MEM_callocN(MEM_ELEM_BLOCKSIZE, "newmem"); + BLI_addtail(&melem__lb, melem__cur); + + melem__offs= size; + return melem__cur->data; } - - size= 4*( (size+3)/4 ); - - if(cur) { - if(size+offs < blocksize) { - adr= (void *) (cur->data+offs); - offs+= size; - return adr; +} +static void mem_element_reset(void) +{ + struct mem_elements *first; + /*BMESH_TODO: keep the first block, gives memory leak on exit with 'newmem' */ + + if((first= melem__lb.first)) { /* can be false if first fill fails */ + BLI_remlink(&melem__lb, first); + + melem__cur= melem__lb.first; + while(melem__cur) { + MEM_freeN(melem__cur->data); + melem__cur= melem__cur->next; } + BLI_freelistN(&melem__lb); + + /*reset the block we're keeping*/ + BLI_addtail(&melem__lb, first); + memset(first->data, 0, MEM_ELEM_BLOCKSIZE); } - - cur= MEM_callocN( sizeof(struct mem_elements), "newmem"); - cur->data= MEM_callocN(blocksize, "newmem"); - BLI_addtail(&lb, cur); - - offs= size; - return cur->data; + + melem__cur= first; + melem__offs= 0; } void BLI_end_edgefill(void) { - new_mem_element(-1); + mem_element_reset(); fillvertbase.first= fillvertbase.last= 0; filledgebase.first= filledgebase.last= 0; fillfacebase.first= fillfacebase.last= 0; + + BLI_unlock_thread(LOCK_SCANFILL); } /* **** FILL ROUTINES *************************** */ @@ -193,7 +209,7 @@ EditVert *BLI_addfillvert(float *vec) { EditVert *eve; - eve= new_mem_element(sizeof(EditVert)); + eve= mem_element_new(sizeof(EditVert)); BLI_addtail(&fillvertbase, eve); eve->co[0] = vec[0]; @@ -207,7 +223,7 @@ EditEdge *BLI_addfilledge(EditVert *v1, EditVert *v2) { EditEdge *newed; - newed= new_mem_element(sizeof(EditEdge)); + newed= mem_element_new(sizeof(EditEdge)); BLI_addtail(&filledgebase, newed); newed->v1= v1; @@ -221,7 +237,7 @@ static void addfillface(EditVert *v1, EditVert *v2, EditVert *v3, short mat_nr) /* does not make edges */ EditFace *evl; - evl= new_mem_element(sizeof(EditFace)); + evl= mem_element_new(sizeof(EditFace)); BLI_addtail(&fillfacebase, evl); evl->v1= v1; @@ -498,7 +514,7 @@ static int scanfill(PolyFill *pf, short mat_nr) EditVert *eve,*v1,*v2,*v3; EditEdge *eed,*nexted,*ed1,*ed2,*ed3; float miny = 0.0; - int a,b,verts, maxface, totface; + int a,b,verts, maxface, totface; short nr, test, twoconnected=0; nr= pf->nr; @@ -534,7 +550,7 @@ static int scanfill(PolyFill *pf, short mat_nr) } else { eed->v2->f= 255; - eed->v2->tmp.v = eed->v1->tmp.v; + eed->v2->tmp.v = eed->v1; } } } @@ -564,20 +580,22 @@ static int scanfill(PolyFill *pf, short mat_nr) eed= filledgebase.first; while(eed) { nexted= eed->next; - eed->f= 0; BLI_remlink(&filledgebase,eed); -/* commented all of this out, this I have no idea for what it is for, probably from ancient past */ -/* it does crash blender, since it uses mixed original and new vertices (ton) */ -// if(eed->v1->f==255) { -// v1= eed->v1; -// while((eed->v1->f == 255) && (eed->v1->tmp.v != v1)) -// eed->v1 = eed->v1->tmp.v; -// } -// if(eed->v2->f==255) { -// v2= eed->v2; -// while((eed->v2->f == 255) && (eed->v2->tmp.v != v2)) -// eed->v2 = eed->v2->tmp.v; -// } + /* This code is for handling zero-length edges that get + collapsed in step 0. It was removed for some time to + fix trunk bug #4544, so if that comes back, this code + may need some work, or there will have to be a better + fix to #4544. */ + if(eed->v1->f==255) { + v1= eed->v1; + while((eed->v1->f == 255) && (eed->v1->tmp.v != v1)) + eed->v1 = eed->v1->tmp.v; + } + if(eed->v2->f==255) { + v2= eed->v2; + while((eed->v2->f == 255) && (eed->v2->tmp.v != v2)) + eed->v2 = eed->v2->tmp.v; + } if(eed->v1!=eed->v2) addedgetoscanlist(eed,verts); eed= nexted; @@ -687,8 +705,8 @@ static int scanfill(PolyFill *pf, short mat_nr) ed1->v2->f= 0; ed1->v1->h--; ed1->v2->h--; - /* ed2 can be removed when it's an old one */ - if(ed2->f==0 && twoconnected) { + /* ed2 can be removed when it's a boundary edge */ + if((ed2->f == 0 && twoconnected) || (ed2->f == FILLBOUNDARY)) { BLI_remlink((ListBase *)&(sc->first),ed2); BLI_addtail(&filledgebase,ed2); ed2->v2->f= 0; @@ -706,19 +724,20 @@ static int scanfill(PolyFill *pf, short mat_nr) /* printf("add new edge %x %x\n",v1,v3); */ sc1= addedgetoscanlist(ed3, verts); - if(sc1) { /* ed3 already exists: remove */ + if(sc1) { /* ed3 already exists: remove if a boundary */ /* printf("Edge exists\n"); */ ed3->v1->h--; ed3->v2->h--; - if(twoconnected) ed3= sc1->first; - else ed3= 0; + ed3= sc1->first; while(ed3) { if( (ed3->v1==v1 && ed3->v2==v3) || (ed3->v1==v3 && ed3->v2==v1) ) { - BLI_remlink((ListBase *)&(sc1->first),ed3); - BLI_addtail(&filledgebase,ed3); - ed3->v1->h--; - ed3->v2->h--; + if (twoconnected || ed3->f==FILLBOUNDARY) { + BLI_remlink((ListBase *)&(sc1->first),ed3); + BLI_addtail(&filledgebase,ed3); + ed3->v1->h--; + ed3->v2->h--; + } break; } ed3= ed3->next; @@ -750,6 +769,12 @@ static int scanfill(PolyFill *pf, short mat_nr) } +int BLI_begin_edgefill(void) +{ + BLI_lock_thread(LOCK_SCANFILL); + + return 1; +} int BLI_edgefill(short mat_nr) { @@ -765,24 +790,55 @@ int BLI_edgefill(short mat_nr) EditVert *eve; EditEdge *eed,*nexted; PolyFill *pflist,*pf; - float *minp, *maxp, *v1, *v2, norm[3], len; + float limit, *minp, *maxp, *v1, *v2, norm[3], len; short a,c,poly=0,ok=0,toggle=0; int totfaces= 0; /* total faces added */ /* reset variables */ eve= fillvertbase.first; + a = 0; while(eve) { eve->f= 0; eve->xs= 0; eve->h= 0; eve= eve->next; + a += 1; + } + + if (a == 3 && (mat_nr & 2)) { + eve = fillvertbase.first; + + addfillface(eve, eve->next, eve->next->next, 0); + return 1; + } else if (a == 4 && (mat_nr & 2)) { + float vec1[3], vec2[3]; + + eve = fillvertbase.first; + /* no need to check 'eve->next->next->next' is valid, already counted */ + if (1) { //BMESH_TODO) { + /*use shortest diagonal for quad*/ + sub_v3_v3v3(vec1, eve->co, eve->next->next->co); + sub_v3_v3v3(vec2, eve->next->co, eve->next->next->next->co); + + if (INPR(vec1, vec1) < INPR(vec2, vec2)) { + addfillface(eve, eve->next, eve->next->next, 0); + addfillface(eve->next->next, eve->next->next->next, eve, 0); + } else{ + addfillface(eve->next, eve->next->next, eve->next->next->next, 0); + addfillface(eve->next->next->next, eve, eve->next, 0); + } + } else { + addfillface(eve, eve->next, eve->next->next, 0); + addfillface(eve->next->next, eve->next->next->next, eve, 0); + } + return 2; } /* first test vertices if they are in edges */ /* including resetting of flags */ eed= filledgebase.first; while(eed) { - eed->f= eed->f1= eed->h= 0; + eed->f1= eed->h= 0; eed->v1->f= 1; eed->v2->f= 1; @@ -810,9 +866,17 @@ int BLI_edgefill(short mat_nr) v1= eve->co; v2= 0; eve= fillvertbase.first; + limit = a < 5 ? FLT_EPSILON*200 : M_PI/24.0; while(eve) { if(v2) { if( compare_v3v3(v2, eve->co, COMPLIMIT)==0) { + float inner = angle_v3v3v3(v1, v2, eve->co); + + if (fabsf(inner-M_PI) < limit || fabsf(inner) < limit) { + eve = eve->next; + continue; + } + len= normal_tri_v3( norm,v1, v2, eve->co); if(len != 0.0f) break; } @@ -922,7 +986,7 @@ int BLI_edgefill(short mat_nr) - eve->h :amount of edges connected to vertex - eve->tmp.v :store! original vertex number - - eed->f : + - eed->f :1= boundary edge (optionally set by caller) - eed->f1 :poly number */ diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c new file mode 100644 index 00000000000..fb03849bfb3 --- /dev/null +++ b/source/blender/blenlib/intern/smallhash.c @@ -0,0 +1,281 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2008 Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Joseph Eagar. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#include <string.h> + +#include "MEM_guardedalloc.h" +#include "BLI_utildefines.h" + +#include "BLI_smallhash.h" + +/* SMHASH_CELL_UNUSED means this cell is inside a key series, + * while SMHASH_CELL_FREE means this cell terminates a key series. + * + * no chance of anyone shoving INT32_MAX-2 into a *val pointer, I + * imagine. hopefully. + * + * note: these have the SMHASH suffix because we may want to make them public. + */ +#define SMHASH_CELL_UNUSED ((void *)0x7FFFFFFF) +#define SMHASH_CELL_FREE ((void *)0x7FFFFFFD) + +#define SMHASH_NONZERO(n) ((n) + !(n)) +#define SMHASH_NEXT(h, hoff) ABS(((h) + ((hoff = SMHASH_NONZERO(hoff * 2) + 1), hoff))) + +extern unsigned int hashsizes[]; + +void BLI_smallhash_init(SmallHash *hash) +{ + int i; + + memset(hash, 0, sizeof(*hash)); + + hash->table = hash->_stacktable; + hash->curhash = 2; + hash->size = hashsizes[hash->curhash]; + + hash->copytable = hash->_copytable; + hash->stacktable = hash->_stacktable; + + for (i = 0; i < hash->size; i++) { + hash->table[i].val = SMHASH_CELL_FREE; + } +} + +/*NOTE: does *not* free *hash itself! only the direct data!*/ +void BLI_smallhash_release(SmallHash *hash) +{ + if (hash == NULL) { + return; + } + + if (hash->table != hash->stacktable) { + MEM_freeN(hash->table); + } +} + +void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item) +{ + int h, hoff=1; + + if (hash->size < hash->used * 3) { + int newsize = hashsizes[++hash->curhash]; + SmallHashEntry *tmp; + int i = 0; + + if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) { + tmp = MEM_callocN(sizeof(*hash->table) * newsize, __func__); + } + else { + SWAP(SmallHashEntry *, hash->stacktable, hash->copytable); + tmp = hash->stacktable; + } + + SWAP(SmallHashEntry *, tmp, hash->table); + + hash->size = newsize; + + for (i = 0; i < hash->size; i++) { + hash->table[i].val = SMHASH_CELL_FREE; + } + + for (i = 0; i<hashsizes[hash->curhash - 1]; i++) { + if (ELEM(tmp[i].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) { + continue; + } + + h = ABS((int)(tmp[i].key)); + hoff = 1; + while (!ELEM(hash->table[h % newsize].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) { + h = SMHASH_NEXT(h, hoff); + } + + h %= newsize; + + hash->table[h].key = tmp[i].key; + hash->table[h].val = tmp[i].val; + } + + if (tmp != hash->stacktable && tmp != hash->copytable) { + MEM_freeN(tmp); + } + } + + h = ABS((int)key); + hoff = 1; + + while (!ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) { + h = SMHASH_NEXT(h, hoff); + } + + h %= hash->size; + hash->table[h].key = key; + hash->table[h].val = item; + + hash->used++; +} + +void BLI_smallhash_remove(SmallHash *hash, uintptr_t key) +{ + int h, hoff=1; + + h = ABS((int)key); + + while ((hash->table[h % hash->size].key != key) || + (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED)) + { + if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) { + return; + } + + h = SMHASH_NEXT(h, hoff); + } + + h %= hash->size; + hash->table[h].key = 0; + hash->table[h].val = SMHASH_CELL_UNUSED; +} + +void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key) +{ + int h, hoff=1; + void *v; + + h = ABS((int)key); + + if (hash->table == NULL) { + return NULL; + } + + while ((hash->table[h % hash->size].key != key) || + (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED)) + { + if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) { + return NULL; + } + + h = SMHASH_NEXT(h, hoff); + } + + v = hash->table[h % hash->size].val; + if (ELEM(v, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) { + return NULL; + } + + return v; +} + + +int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key) +{ + int h = ABS((int)key); + int hoff =1; + + if (hash->table == NULL) { + return 0; + } + + while ((hash->table[h % hash->size].key != key) || + (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED)) + { + if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) { + return 0; + } + + h = SMHASH_NEXT(h, hoff); + } + + return !ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE); +} + +int BLI_smallhash_count(SmallHash *hash) +{ + return hash->used; +} + +void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) +{ + while (iter->i < iter->hash->size) { + if ( (iter->hash->table[iter->i].val != SMHASH_CELL_UNUSED) && + (iter->hash->table[iter->i].val != SMHASH_CELL_FREE)) + { + if (key) { + *key = iter->hash->table[iter->i].key; + } + + iter->i++; + + return iter->hash->table[iter->i - 1].val; + } + + iter->i++; + } + + return NULL; +} + +void *BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key) +{ + iter->hash = hash; + iter->i = 0; + + return BLI_smallhash_iternext(iter, key); +} + +/* note, this was called _print_smhash in knifetool.c + * it may not be intended for general use - campbell */ +#if 0 +void BLI_smallhash_print(SmallHash *hash) +{ + int i, linecol=79, c=0; + + printf("{"); + for (i=0; i<hash->size; i++) { + if (hash->table[i].val == SMHASH_CELL_UNUSED) { + printf("--u-"); + } + else if (hash->table[i].val == SMHASH_CELL_FREE) { + printf("--f-"); + } + else { + printf("%2x", (unsigned int)hash->table[i].key); + } + + if (i != hash->size-1) + printf(", "); + + c += 6; + + if (c >= linecol) { + printf("\n "); + c = 0; + } + } + + fflush(stdout); +} +#endif diff --git a/source/blender/blenlib/intern/threads.c b/source/blender/blenlib/intern/threads.c index 98d2179e2dd..e92b445c27f 100644 --- a/source/blender/blenlib/intern/threads.c +++ b/source/blender/blenlib/intern/threads.c @@ -115,6 +115,7 @@ static pthread_mutex_t _rcache_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _opengl_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _nodes_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_mutex_t _movieclip_lock = PTHREAD_MUTEX_INITIALIZER; +static pthread_mutex_t _scanfill_lock = PTHREAD_MUTEX_INITIALIZER; static pthread_t mainid; static int thread_levels= 0; /* threads can be invoked inside threads */ @@ -353,6 +354,8 @@ void BLI_lock_thread(int type) pthread_mutex_lock(&_nodes_lock); else if (type==LOCK_MOVIECLIP) pthread_mutex_lock(&_movieclip_lock); + else if (type == LOCK_SCANFILL) + pthread_mutex_lock(&_scanfill_lock); } void BLI_unlock_thread(int type) @@ -373,6 +376,8 @@ void BLI_unlock_thread(int type) pthread_mutex_unlock(&_nodes_lock); else if(type==LOCK_MOVIECLIP) pthread_mutex_unlock(&_movieclip_lock); + else if(type == LOCK_SCANFILL) + pthread_mutex_unlock(&_scanfill_lock); } /* Mutex Locks */ |