diff options
Diffstat (limited to 'source/blender/blenlib/intern')
-rw-r--r-- | source/blender/blenlib/intern/BLI_cellalloc.c | 202 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_ghash.c | 6 | ||||
-rw-r--r-- | source/blender/blenlib/intern/edgehash.c | 133 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_base_inline.c | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 55 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_vector.c | 14 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_vector_inline.c | 23 | ||||
-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 | 280 | ||||
-rw-r--r-- | source/blender/blenlib/intern/threads.c | 5 |
11 files changed, 731 insertions, 181 deletions
diff --git a/source/blender/blenlib/intern/BLI_cellalloc.c b/source/blender/blenlib/intern/BLI_cellalloc.c new file mode 100644 index 00000000000..ff77dc444af --- /dev/null +++ b/source/blender/blenlib/intern/BLI_cellalloc.c @@ -0,0 +1,202 @@ +/** + * + * ***** 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * The Original Code is Copyright (C) 2008 by Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Joseph Eagar + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/* + Simple, fast memory allocator that uses many BLI_mempools for allocation. + this is meant to be used by lots of relatively small objects. + + this is a temporary and imperfect fix for performance issues caused + by vgroups. it needs to be replaced with something better, preferably + integrated into guardedalloc. + + Basically, it's a quick fix for vgroups and MDisps (both of which + are major performance hitters). +*/ + +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" + +#include "BLI_blenlib.h" +#include "BLI_linklist.h" + +#include "DNA_listBase.h" +#include "BLI_mempool.h" + +#include "BLI_cellalloc.h" /* own include */ + +#include <string.h> + +static BLI_mempool **pools; +static int totpool = 0; +static ListBase active_mem = {NULL, NULL}; +static int celltotblock = 0; + +#define MEMIDCHECK ('a' | ('b' << 4) | ('c' << 8) | ('d' << 12)) + +typedef struct MemHeader { + struct MemHeader *next, *prev; + + int size; + const char *tag; + int idcheck; +} MemHeader; + +//#define USE_GUARDEDALLOC + +void *BLI_cellalloc_malloc(int size, const char *tag) +{ + MemHeader *memh; + int slot = size + sizeof(MemHeader); + +#ifdef USE_GUARDEDALLOC + return MEM_mallocN(size, tag); +#endif + if (!slot) + return NULL; + + /*stupid optimization trick. + round up to nearest 16 bytes boundary. + this is to reduce the number of potential + pools. hopefully it'll help.*/ + slot += 16 - (slot & 15); + + if (slot >= totpool) { + void *tmp; + + tmp = calloc(1, sizeof(void*)*(slot+1)); + if (pools) { + memcpy(tmp, pools, totpool*sizeof(void*)); + } + + pools = tmp; + totpool = slot+1; + } + + if (!pools[slot]) { + pools[slot] = BLI_mempool_create(slot, 1, 128, TRUE, FALSE); + } + + memh = BLI_mempool_alloc(pools[slot]); + memh->size = size; + memh->idcheck = MEMIDCHECK; + memh->tag = tag; + BLI_addtail(&active_mem, memh); + celltotblock++; + + return memh + 1; +} + +void *BLI_cellalloc_calloc(int size, const char *tag) +{ + void *mem = BLI_cellalloc_malloc(size, tag); + memset(mem, 0, size); + return mem; +} + +void BLI_cellalloc_free(void *mem) +{ + MemHeader *memh = mem; + int slot; + +#ifdef USE_GUARDEDALLOC + MEM_freeN(mem); + return; +#endif + if (!memh) + return; + + memh--; + if (memh->idcheck != MEMIDCHECK) { + printf("Error in BLI_cellalloc: attempt to free invalid block.\n"); + return; + } + + slot = memh->size + sizeof(MemHeader); + slot += 16 - (slot & 15); + + if (memh->size > 0 && slot < totpool) { + BLI_remlink(&active_mem, memh); + BLI_mempool_free(pools[slot], memh); + celltotblock--; + } else { + printf("Error in BLI_cellalloc: attempt to free corrupted block.\n"); + } +} + +void *BLI_cellalloc_dupalloc(void *mem) +{ + MemHeader *memh = mem; + void *tmp; + +#ifdef USE_GUARDEDALLOC + MEM_freeN(mem); + return NULL; +#endif + if (!memh) + return NULL; + + memh--; + if (memh->idcheck != MEMIDCHECK) { + printf("Error in BLI_cellalloc: attempt to free invalid block.\n"); + return NULL; + } + + tmp = BLI_cellalloc_malloc(memh->size, memh->tag); + memcpy(tmp, mem, memh->size); + + return tmp; +} + +void BLI_cellalloc_printleaks(void) +{ + MemHeader *memh; + + if (!active_mem.first) return; + + for (memh=active_mem.first; memh; memh=memh->next) { + printf("%s %d %p\n", memh->tag, memh->size, memh+1); + } +} + +int BLI_cellalloc_get_totblock(void) +{ + return celltotblock; +} + +void BLI_cellalloc_destroy(void) +{ + int i; + + for (i=0; i<totpool; i++) { + if (pools[i]) { + BLI_mempool_destroy(pools[i]); + pools[i] = NULL; + } + } +} diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 9f388b68c38..950acb21e17 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -40,14 +40,14 @@ // #include "BLI_blenlib.h" -#include "BLI_mempool.h" #include "BLI_utildefines.h" +#include "BLI_mempool.h" #include "BLI_ghash.h" #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/edgehash.c b/source/blender/blenlib/intern/edgehash.c index 7ae68101154..dbd138a3563 100644 --- a/source/blender/blenlib/intern/edgehash.c +++ b/source/blender/blenlib/intern/edgehash.c @@ -20,7 +20,7 @@ * * The Original Code is: none of this file. * - * Contributor(s): Daniel Dunbar + * Contributor(s): Daniel Dunbar, Joseph Eagar * * ***** END GPL LICENSE BLOCK ***** * A general (pointer -> pointer) hash table ADT @@ -35,118 +35,24 @@ #include <string.h> #include "MEM_guardedalloc.h" -#include "BLI_edgehash.h" - -/***/ - -static unsigned int hashsizes[]= { - 1, 3, 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, - 268435459 -}; - -#define EDGEHASH(v0,v1) ((v0*39)^(v1*31)) -/***/ - -typedef struct Entry Entry; -struct Entry { - Entry *next; - int v0, v1; - void *val; -}; - -struct EdgeHash { - Entry **buckets; - int nbuckets, nentries, cursize; -}; +#include "BLI_utildefines.h" +#include "BLI_edgehash.h" +#include "BLI_mempool.h" /***/ EdgeHash *BLI_edgehash_new(void) { - EdgeHash *eh= MEM_mallocN(sizeof(*eh), "EdgeHash"); + EdgeHash *eh= MEM_callocN(sizeof(*eh), "EdgeHash"); eh->cursize= 0; eh->nentries= 0; - eh->nbuckets= hashsizes[eh->cursize]; - - eh->buckets= malloc(eh->nbuckets*sizeof(*eh->buckets)); - memset(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets)); + eh->nbuckets= _ehash_hashsizes[eh->cursize]; - return eh; -} - -void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) -{ - unsigned int hash; - Entry *e= malloc(sizeof(*e)); + eh->buckets= MEM_callocN(eh->nbuckets*sizeof(*eh->buckets), "eh buckets 2"); + eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512, TRUE, FALSE); - if (v1<v0) { - v0 ^= v1; - v1 ^= v0; - v0 ^= v1; - } - hash = EDGEHASH(v0,v1)%eh->nbuckets; - - e->v0 = v0; - e->v1 = v1; - e->val = val; - e->next= eh->buckets[hash]; - eh->buckets[hash]= e; - - if (++eh->nentries>eh->nbuckets*3) { - Entry **old= eh->buckets; - int i, nold= eh->nbuckets; - - eh->nbuckets= hashsizes[++eh->cursize]; - eh->buckets= malloc(eh->nbuckets*sizeof(*eh->buckets)); - memset(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets)); - - for (i=0; i<nold; i++) { - for (e= old[i]; e;) { - Entry *n= e->next; - - hash= EDGEHASH(e->v0,e->v1)%eh->nbuckets; - e->next= eh->buckets[hash]; - eh->buckets[hash]= e; - - e= n; - } - } - - free(old); - } -} - -void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) -{ - unsigned int hash; - Entry *e; - - if (v1<v0) { - v0 ^= v1; - v1 ^= v0; - v0 ^= v1; - } - hash = EDGEHASH(v0,v1)%eh->nbuckets; - for (e= eh->buckets[hash]; e; e= e->next) - if (v0==e->v0 && v1==e->v1) - return &e->val; - - return NULL; -} - -void* BLI_edgehash_lookup(EdgeHash *eh, int v0, int v1) -{ - void **value_p = BLI_edgehash_lookup_p(eh,v0,v1); - - return value_p?*value_p:NULL; -} - -int BLI_edgehash_haskey(EdgeHash *eh, int v0, int v1) -{ - return BLI_edgehash_lookup_p(eh, v0, v1)!=NULL; + return eh; } int BLI_edgehash_size(EdgeHash *eh) @@ -159,13 +65,13 @@ void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) int i; for (i=0; i<eh->nbuckets; i++) { - Entry *e; + EdgeEntry *e; for (e= eh->buckets[i]; e; ) { - Entry *n= e->next; + EdgeEntry *n= e->next; if (valfreefp) valfreefp(e->val); - free(e); + BLI_mempool_free(eh->epool, e); e= n; } @@ -178,8 +84,10 @@ void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp) void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) { BLI_edgehash_clear(eh, valfreefp); - - free(eh->buckets); + + BLI_mempool_destroy(eh->epool); + + MEM_freeN(eh->buckets); MEM_freeN(eh); } @@ -189,12 +97,12 @@ void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp) struct EdgeHashIterator { EdgeHash *eh; int curBucket; - Entry *curEntry; + EdgeEntry *curEntry; }; EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) { - EdgeHashIterator *ehi= malloc(sizeof(*ehi)); + EdgeHashIterator *ehi= MEM_mallocN(sizeof(*ehi), "eh iter"); ehi->eh= eh; ehi->curEntry= NULL; ehi->curBucket= -1; @@ -208,7 +116,7 @@ EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh) } void BLI_edgehashIterator_free(EdgeHashIterator *ehi) { - free(ehi); + MEM_freeN(ehi); } void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, int *v0_r, int *v1_r) @@ -241,8 +149,7 @@ void BLI_edgehashIterator_step(EdgeHashIterator *ehi) } } } -int BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) -{ +int BLI_edgehashIterator_isDone(EdgeHashIterator *ehi) { return !ehi->curEntry; } 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/math_geom.c b/source/blender/blenlib/intern/math_geom.c index ef04e5e9bce..d7880e40626 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -2382,6 +2382,38 @@ void accumulate_vertex_normals(float n1[3], float n2[3], float n3[3], } } +/* Add weighted face normal component into normals of the face vertices. + Caller must pass pre-allocated vdiffs of nverts length. */ +void accumulate_vertex_normals_poly(float **vertnos, float polyno[3], + float **vertcos, float vdiffs[][3], int nverts) +{ + int i; + + /* calculate normalized edge directions for each edge in the poly */ + for (i = 0; i < nverts; i++) { + sub_v3_v3v3(vdiffs[i], vertcos[(i+1) % nverts], vertcos[i]); + normalize_v3(vdiffs[i]); + } + + /* accumulate angle weighted face normal */ + { + const float *prev_edge = vdiffs[nverts-1]; + int i; + + for(i=0; i<nverts; i++) { + const float *cur_edge = vdiffs[i]; + + /* calculate angle between the two poly edges incident on + this vertex */ + const float fac= saacos(-dot_v3v3(cur_edge, prev_edge)); + + /* accumulate */ + madd_v3_v3fl(vertnos[i], polyno, fac); + prev_edge = cur_edge; + } + } +} + /********************************* Tangents **********************************/ /* For normal map tangents we need to detect uv boundaries, and only average @@ -3038,3 +3070,26 @@ float form_factor_hemi_poly(float p[3], float n[3], float v1[3], float v2[3], fl return contrib; } + +/* evaluate if entire quad is a proper convex quad */ + int is_quad_convex_v3(const float *v1, const float *v2, const float *v3, const float *v4) + { + float nor[3], nor1[3], nor2[3], vec[4][2]; + int axis_a, axis_b; + + /* define projection, do both trias apart, quad is undefined! */ + normal_tri_v3(nor1, v1, v2, v3); + normal_tri_v3(nor2, v1, v3, v4); + add_v3_v3v3(nor, nor1, nor2); + + axis_dominant_v3(&axis_a, &axis_b, nor); + + vec[0][0]= v1[axis_a]; vec[0][1]= v1[axis_b]; + vec[1][0]= v2[axis_a]; vec[1][1]= v2[axis_b]; + + vec[2][0]= v3[axis_a]; vec[2][1]= v3[axis_b]; + vec[3][0]= v4[axis_a]; vec[3][1]= v4[axis_b]; + + /* linetests, the 2 diagonals have to instersect to be convex */ + return (isect_line_line_v2(vec[0], vec[2], vec[1], vec[3]) > 0) ? 1 : 0; +} diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c index a9ea90ef555..0ea9934d3b6 100644 --- a/source/blender/blenlib/intern/math_vector.c +++ b/source/blender/blenlib/intern/math_vector.c @@ -239,6 +239,20 @@ void angle_quad_v3(float angles[4], const float v1[3], const float v2[3], const angles[3]= (float)M_PI - angle_normalized_v3v3(ed4, ed1); } +void angle_poly_v3(float *angles, const float *verts[3], int len) +{ + int i; + float vec[3][3]; + + sub_v3_v3v3(vec[2], verts[len-1], verts[0]); + normalize_v3(vec[2]); + for (i = 0; i < len; i++) { + sub_v3_v3v3(vec[i%3], verts[i%len], verts[(i+1)%len]); + normalize_v3(vec[i%3]); + angles[i] = (float)M_PI - angle_normalized_v3v3(vec[(i+2)%3], vec[i%3]); + } +} + /********************************* Geometry **********************************/ /* Project v1 on v2 */ diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c index 4570bd5e99e..6f014a859db 100644 --- a/source/blender/blenlib/intern/math_vector_inline.c +++ b/source/blender/blenlib/intern/math_vector_inline.c @@ -510,6 +510,29 @@ MINLINE float normalize_v3_v3(float r[3], const float a[3]) return d; } +MINLINE double normalize_v3_d(double n[3]) +{ + double d= n[0]*n[0] + n[1]*n[1] + n[2]*n[2]; + + /* a larger value causes normalize errors in a + scaled down models with camera xtreme close */ + if(d > 1.0e-35) { + double mul; + + d= sqrt(d); + mul = 1.0 / d; + + n[0] *= mul; + n[1] *= mul; + n[2] *= mul; + } else { + n[0] = n[1] = n[2] = 0; + d= 0.0; + } + + return d; +} + MINLINE float normalize_v3(float n[3]) { return normalize_v3_v3(n, n); diff --git a/source/blender/blenlib/intern/pbvh.c b/source/blender/blenlib/intern/pbvh.c index 5c7a29c6277..ae0becc840b 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_tessface_normals(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..c78dcd415cc --- /dev/null +++ b/source/blender/blenlib/intern/smallhash.c @@ -0,0 +1,280 @@ +/** + * ***** 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 "MEM_guardedalloc.h" +#include "BLI_utildefines.h" +#include <string.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, "new hashkeys"); + } + 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 */ |