diff options
author | Geoffrey Bantle <hairbat@yahoo.com> | 2008-06-01 21:15:03 +0400 |
---|---|---|
committer | Geoffrey Bantle <hairbat@yahoo.com> | 2008-06-01 21:15:03 +0400 |
commit | 07b1608fbe52f729eae39c307060f92948aabf37 (patch) | |
tree | 96dcc1dde0038151362edfa437c843d042653e0d /source | |
parent | 652ee1e31baa52c8e504bfcf3759ea94c7f5ab66 (diff) |
-> New memory allocator for Bmesh
Added a new pooling allocator for Bmesh based upon
the pool allocator availible in the Boost C++ library
as described here:
http://www.boost.org/doc/libs/1_34_0/libs/pool/doc/concepts.html
Each pool allocates elements of a fixed size, so every
element type in a mesh gets its own pool. For instance
verts occupy a different pool than edges. Each pool
is comprised of multiple arrays of a fixed size and allocating
/freeing elements is simple as removing or adding a head
to a linked list. Since the list of free elements is interleaved
throughout the unused space in the arrays, the overhead
for storing the free list is only 1 pointer total per pool.
This makes building/destroying bmesh structures much faster
and saves quite a bit of memory as well.
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenkernel/BKE_bmesh.h | 19 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/BME_mesh.c | 65 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/BME_structure.c | 162 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/bmesh_private.h | 11 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/modifier.c | 2 | ||||
-rw-r--r-- | source/blender/src/editmesh_tools.c | 2 |
6 files changed, 184 insertions, 77 deletions
diff --git a/source/blender/blenkernel/BKE_bmesh.h b/source/blender/blenkernel/BKE_bmesh.h index 08ad8192688..87202ce047a 100644 --- a/source/blender/blenkernel/BKE_bmesh.h +++ b/source/blender/blenkernel/BKE_bmesh.h @@ -50,6 +50,9 @@ struct BME_Edge; struct BME_Poly; struct BME_Loop; +struct BME_mempool; +typedef struct BME_mempool BME_mempool; + typedef struct BME_CycleNode{ struct BME_CycleNode *next, *prev; void *data; @@ -57,16 +60,21 @@ typedef struct BME_CycleNode{ typedef struct BME_Mesh { - ListBase verts, edges, polys, loops; - int totvert, totedge, totpoly, totloop; /*record keeping*/ - int nextv, nexte, nextp, nextl; /*Next element ID for verts/edges/faces/loops. Never reused*/ - struct CustomData vdata, edata, pdata, ldata; /*Custom Data Layer information*/ + ListBase verts, edges, polys; + /*memory pools used for storing mesh elements*/ + struct BME_mempool *vpool; + struct BME_mempool *epool; + struct BME_mempool *ppool; + struct BME_mempool *lpool; /*some scratch arrays used by eulers*/ struct BME_Vert **vtar; struct BME_Edge **edar; struct BME_Loop **lpar; struct BME_Poly **plar; int vtarlen, edarlen, lparlen, plarlen; + int totvert, totedge, totpoly, totloop; /*record keeping*/ + int nextv, nexte, nextp, nextl; /*Next element ID for verts/edges/faces/loops. Never reused*/ + //struct CustomData vdata, edata, pdata, ldata; /*Custom Data Layer information*/ } BME_Mesh; typedef struct BME_Vert @@ -102,7 +110,6 @@ typedef struct BME_Loop struct BME_Loop *next, *prev; /*circularly linked list around face*/ int EID; struct BME_CycleNode radial; /*circularly linked list used to find faces around an edge*/ - struct BME_CycleNode *gref; /*pointer to loop ref. Nasty.*/ struct BME_Vert *v; /*vertex that this loop starts at.*/ struct BME_Edge *e; /*edge this loop belongs to*/ struct BME_Poly *f; /*face this loop belongs to*/ @@ -146,7 +153,7 @@ int BME_radial_find_face(struct BME_Edge *e,struct BME_Poly *f); struct BME_Loop *BME_loop_find_loop(struct BME_Poly *f, struct BME_Vert *v); /*MESH CREATION/DESTRUCTION*/ -struct BME_Mesh *BME_make_mesh(void); +struct BME_Mesh *BME_make_mesh(int valloc, int ealloc, int lalloc, int palloc); void BME_free_mesh(struct BME_Mesh *bm); /*FULL MESH VALIDATION*/ int BME_validate_mesh(struct BME_Mesh *bm, int halt); diff --git a/source/blender/blenkernel/intern/BME_mesh.c b/source/blender/blenkernel/intern/BME_mesh.c index d9d2354ef36..307047463cf 100644 --- a/source/blender/blenkernel/intern/BME_mesh.c +++ b/source/blender/blenkernel/intern/BME_mesh.c @@ -62,11 +62,21 @@ * Allocates a new BME_Mesh structure */ -BME_Mesh *BME_make_mesh(void){ + + +BME_Mesh *BME_make_mesh(int valloc, int ealloc, int lalloc, int palloc){ + /*allocate the structure*/ BME_Mesh *bm = MEM_callocN(sizeof(BME_Mesh),"BMesh"); + /*allocate the memory pools for the mesh elements*/ + bm->vpool = BME_mempool_create(sizeof(BME_Vert), valloc, valloc); + bm->epool = BME_mempool_create(sizeof(BME_Edge), ealloc, ealloc); + bm->ppool = BME_mempool_create(sizeof(BME_Poly), palloc, palloc); + bm->lpool = BME_mempool_create(sizeof(BME_Loop), lalloc, lalloc); + /*allocate the customdata pools*/ return bm; } + /* * BME FREE MESH * @@ -75,45 +85,13 @@ BME_Mesh *BME_make_mesh(void){ void BME_free_mesh(BME_Mesh *bm) { - BME_Poly *bf, *nextf; - BME_Edge *be, *nexte; - BME_Vert *bv, *nextv; - BME_CycleNode *loopref; - - /*destroy polygon data*/ - bf = bm->polys.first; - while(bf){ - nextf = bf->next; - BLI_remlink(&(bm->polys), bf); - BME_free_poly(bm, bf); - - bf = nextf; - } - /*destroy edge data*/ - be = bm->edges.first; - while(be){ - nexte = be->next; - BLI_remlink(&(bm->edges), be); - BME_free_edge(bm, be); - be = nexte; - } - /*destroy vert data*/ - bv = bm->verts.first; - while(bv){ - nextv = bv->next; - BLI_remlink(&(bm->verts), bv); - BME_free_vert(bm, bv); - bv = nextv; - } - - for(loopref=bm->loops.first;loopref;loopref=loopref->next) BME_delete_loop(bm,loopref->data); - BLI_freelistN(&(bm->loops)); - - //CustomData_free(&bm->vdata, 0); - //CustomData_free(&bm->edata, 0); - //CustomData_free(&bm->ldata, 0); - //CustomData_free(&bm->pdata, 0); - + /*destroy element pools*/ + BME_mempool_destroy(bm->vpool); + BME_mempool_destroy(bm->epool); + BME_mempool_destroy(bm->ppool); + BME_mempool_destroy(bm->lpool); + /*destroy custom data pools*/ + MEM_freeN(bm); } @@ -156,8 +134,7 @@ void BME_model_end(BME_Mesh *bm){ totvert = BLI_countlist(&(bm->verts)); totedge = BLI_countlist(&(bm->edges)); totpoly = BLI_countlist(&(bm->polys)); - totloop = BLI_countlist(&(bm->loops)); - + if(bm->vtar) MEM_freeN(bm->vtar); if(bm->edar) MEM_freeN(bm->edar); if(bm->lpar) MEM_freeN(bm->lpar); @@ -167,10 +144,10 @@ void BME_model_end(BME_Mesh *bm){ bm->edar = NULL; bm->lpar = NULL; bm->plar = NULL; - bm->vtarlen = bm->edarlen = bm->lparlen = bm->plarlen = 1024; + bm->vtarlen = bm->edarlen = bm->lparlen = bm->plarlen = 0; - if(bm->totvert!=totvert || bm->totedge!=totedge || bm->totpoly!=totpoly || bm->totloop!=totloop) + if(bm->totvert!=totvert || bm->totedge!=totedge || bm->totpoly!=totpoly) BME_error(); meshok = BME_validate_mesh(bm, 1); diff --git a/source/blender/blenkernel/intern/BME_structure.c b/source/blender/blenkernel/intern/BME_structure.c index d283e1df5ca..d261238d128 100644 --- a/source/blender/blenkernel/intern/BME_structure.c +++ b/source/blender/blenkernel/intern/BME_structure.c @@ -43,6 +43,105 @@ #include "BLI_ghash.h" #include "BKE_customdata.h" + +/* + Simple, fast memory allocator for allocating many elements of the same size. +*/ +typedef struct BME_mempool_chunk{ + struct BME_mempool_chunk *next, *prev; + void *data; +}BME_mempool_chunk; + +/*this is just to make things prettier*/ +typedef struct BME_freenode{ + struct BME_freenode *next; +}BME_freenode; + +typedef struct BME_mempool{ + struct ListBase chunks; + int esize, csize, pchunk; /*size of elements and chunks in bytes and number of elements per chunk*/ + struct BME_freenode *free; /*free element list. Interleaved into chunk datas.*/ +}BME_mempool; + +BME_mempool *BME_mempool_create(int esize, int tote, int pchunk) +{ BME_mempool *pool = NULL; + BME_freenode *lasttail = NULL, *curnode = NULL; + int i,j, maxchunks; + char *addr; + + /*allocate the pool structure*/ + pool = MEM_mallocN(sizeof(BME_mempool),"memory pool"); + pool->esize = esize; + pool->pchunk = pchunk; + pool->csize = esize * pchunk; + pool->chunks.first = pool->chunks.last = NULL; + + maxchunks = tote / pchunk; + + /*allocate the actual chunks*/ + for(i=0; i < maxchunks; i++){ + BME_mempool_chunk *mpchunk = MEM_mallocN(sizeof(BME_mempool_chunk), "BME_Mempool Chunk"); + mpchunk->next = mpchunk->prev = NULL; + mpchunk->data = MEM_mallocN(pool->csize, "BME Mempool Chunk Data"); + BLI_addtail(&(pool->chunks), mpchunk); + + if(i==0) pool->free = mpchunk->data; /*start of the list*/ + /*loop through the allocated data, building the pointer structures*/ + for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){ + curnode = ((BME_freenode*)addr); + addr += pool->esize; + curnode->next = (BME_freenode*)addr; + } + /*final pointer in the previously allocated chunk is wrong.*/ + if(lasttail) lasttail->next = mpchunk->data; + /*set the end of this chunks memory to the new tail for next iteration*/ + lasttail = curnode; + } + /*terminate the list*/ + curnode->next = NULL; + return pool; +} + +void *BME_mempool_alloc(BME_mempool *pool){ + void *retval=NULL; + BME_freenode *curnode=NULL; + char *addr=NULL; + int j; + + if(!(pool->free)){ + /*need to allocate a new chunk*/ + BME_mempool_chunk *mpchunk = MEM_mallocN(sizeof(BME_mempool_chunk), "BME_Mempool Chunk"); + mpchunk->next = mpchunk->prev = NULL; + mpchunk->data = MEM_mallocN(pool->csize, "BME_Mempool Chunk Data"); + BLI_addtail(&(pool->chunks), mpchunk); + + pool->free = mpchunk->data; /*start of the list*/ + for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){ + curnode = ((BME_freenode*)addr); + addr += pool->esize; + curnode->next = (BME_freenode*)addr; + } + curnode->next = NULL; /*terminate the list*/ + } + + retval = pool->free; + pool->free = pool->free->next; + //memset(retval, 0, pool->esize); + return retval; +} + +void BME_mempool_free(BME_mempool *pool, void *addr){ //doesnt protect against double frees, dont be stupid! + BME_freenode *newhead = addr; + newhead->next = pool->free; + pool->free = newhead; +} +void BME_mempool_destroy(BME_mempool *pool) +{ + BME_mempool_chunk *mpchunk=NULL; + for(mpchunk = pool->chunks.first; mpchunk; mpchunk = mpchunk->next) MEM_freeN(mpchunk->data); + BLI_freelistN(&(pool->chunks)); + MEM_freeN(pool); +} /** * MISC utility functions. * @@ -86,9 +185,17 @@ int BME_edge_swapverts(BME_Edge *e, BME_Vert *orig, BME_Vert *new){ BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){ BME_Vert *v=NULL; - v = MEM_callocN(sizeof(BME_Vert), "BME Vertex"); - BLI_addtail(&(bm->verts), v); + v = BME_mempool_alloc(bm->vpool); + v->next = v->prev = NULL; v->EID = bm->nextv; + v->co[0] = v->co[1] = v->co[2] = 0.0f; + v->no[0] = v->no[1] = v->no[2] = 0.0f; + v->edge = NULL; + v->data = NULL; + v->eflag1 = v->eflag2 = v->tflag1 = v->tflag2 = 0; + v->flag = v->h = 0; + v->bweight = 0.0f; + BLI_addtail(&(bm->verts), v); bm->nextv++; bm->totvert++; @@ -103,12 +210,19 @@ BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){ } BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *example){ BME_Edge *e=NULL; - e = MEM_callocN(sizeof(BME_Edge), "BME_Edge"); + e = BME_mempool_alloc(bm->epool); + e->next = e->prev = NULL; + e->EID = bm->nexte; e->v1 = v1; e->v2 = v2; + e->d1.next = e->d1.prev = e->d2.next = e->d2.prev = NULL; e->d1.data = e; e->d2.data = e; - e->EID = bm->nexte; + e->loop = NULL; + e->data = NULL; + e->eflag1 = e->eflag2 = e->tflag1 = e->tflag2 = 0; + e->flag = e->h = 0; + e->crease = e->bweight = 0.0f; bm->nexte++; bm->totedge++; BLI_addtail(&(bm->edges), e); @@ -124,16 +238,17 @@ BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *ex BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, BME_Loop *example){ /*allocate a BME_Loop and add it to the loophash*/ BME_Loop *l=NULL; - BME_CycleNode *loopnode = MEM_callocN(sizeof(BME_CycleNode),"BME Loop Reference"); - l = MEM_callocN(sizeof(BME_Loop), "BME_Loop"); + l = BME_mempool_alloc(bm->lpool); + l->next = l->prev = NULL; + l->EID = bm->nextl; + l->radial.next = l->radial.prev = NULL; l->radial.data = l; l->v = v; l->e = e; l->f = f; - l->EID = bm->nextl; - l->gref = loopnode; - loopnode->data = l; - BLI_addtail(&(bm->loops),loopnode); + l->data = NULL; + l->eflag1 = l->eflag2 = l->tflag1 = l->tflag2 = 0; + l->flag = l->h = 0; //stupid waste! bm->nextl++; bm->totloop++; @@ -148,9 +263,15 @@ BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, B BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){ BME_Poly *f = NULL; - f= MEM_callocN(sizeof(BME_Poly),"BME_Poly"); - BLI_addtail(&(bm->polys),f); + f = BME_mempool_alloc(bm->ppool); + f->next = f->prev = NULL; f->EID = bm->nextp; + f->loopbase = NULL; + f->len = 0; + f->data = NULL; + f->eflag1 = f->eflag2 = f->tflag1 = f->tflag2 = 0; + f->flag = f->h = f->mat_nr; + BLI_addtail(&(bm->polys),f); bm->nextp++; bm->totpoly++; @@ -169,30 +290,23 @@ BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){ void BME_free_vert(BME_Mesh *bm, BME_Vert *v){ bm->totvert--; //CustomData_em_free_block(&bm->vdata, &v->data); - MEM_freeN(v); + BME_mempool_free(bm->vpool, v); } void BME_free_edge(BME_Mesh *bm, BME_Edge *e){ bm->totedge--; //CustomData_em_free_block(&bm->edata, &e->data); - MEM_freeN(e); + BME_mempool_free(bm->epool, e); } void BME_free_poly(BME_Mesh *bm, BME_Poly *f){ bm->totpoly--; //CustomData_em_free_block(&bm->pdata, &f->data); - MEM_freeN(f); + BME_mempool_free(bm->ppool, f); } -void BME_delete_loop(BME_Mesh *bm, BME_Loop *l){ +void BME_free_loop(BME_Mesh *bm, BME_Loop *l){ bm->totloop--; //CustomData_em_free_block(&bm->ldata, &l->data); - MEM_freeN(l); + BME_mempool_free(bm->lpool, l); } -void BME_free_loop(BME_Mesh *bm, BME_Loop *l){ - BME_CycleNode *loopref = l->gref; - BLI_freelinkN(&(bm->loops),loopref); - BME_delete_loop(bm,l); -} - - /** * BMESH CYCLES * diff --git a/source/blender/blenkernel/intern/bmesh_private.h b/source/blender/blenkernel/intern/bmesh_private.h index ad90398bf66..ed58421ffb7 100644 --- a/source/blender/blenkernel/intern/bmesh_private.h +++ b/source/blender/blenkernel/intern/bmesh_private.h @@ -39,6 +39,15 @@ #include "BKE_bmesh.h" +/*MEMORY MANAGMENT*/ +struct BME_mempool; +typedef struct BME_mempool BME_mempool; + +struct BME_mempool *BME_mempool_create(int esize, int tote, int pchunk); +void BME_mempool_destroy(struct BME_mempool *pool); +void *BME_mempool_alloc(struct BME_mempool *pool); +void BME_mempool_free(struct BME_mempool *pool, void *address); + /*ALLOCATION/DEALLOCATION*/ struct BME_Vert *BME_addvertlist(struct BME_Mesh *bm, struct BME_Vert *example); struct BME_Edge *BME_addedgelist(struct BME_Mesh *bm, struct BME_Vert *v1, struct BME_Vert *v2, struct BME_Edge *example); @@ -49,7 +58,7 @@ void BME_free_vert(struct BME_Mesh *bm, struct BME_Vert *v); void BME_free_edge(struct BME_Mesh *bm, struct BME_Edge *e); void BME_free_poly(struct BME_Mesh *bm, struct BME_Poly *f); void BME_free_loop(struct BME_Mesh *bm, struct BME_Loop *l); -void BME_delete_loop(struct BME_Mesh *bm, struct BME_Loop *l); +//void BME_delete_loop(struct BME_Mesh *bm, struct BME_Loop *l); /*DOUBLE CIRCULAR LINKED LIST FUNCTIONS*/ void BME_cycle_append(void *h, void *nt); diff --git a/source/blender/blenkernel/intern/modifier.c b/source/blender/blenkernel/intern/modifier.c index f9f17e7762d..6185e249b5a 100644 --- a/source/blender/blenkernel/intern/modifier.c +++ b/source/blender/blenkernel/intern/modifier.c @@ -2754,7 +2754,7 @@ static DerivedMesh *bevelModifier_applyModifier( //~ } //~ } - bm = BME_make_mesh(); + bm = BME_make_mesh(512,512,2048,512); bm = BME_derivedmesh_to_bmesh(derivedData, bm); BME_bevel(bm,bmd->value,bmd->res,options,defgrp_index,bmd->bevel_angle,NULL); result = BME_bmesh_to_derivedmesh(bm,derivedData); diff --git a/source/blender/src/editmesh_tools.c b/source/blender/src/editmesh_tools.c index d4ebe181218..d90a7eb7c16 100644 --- a/source/blender/src/editmesh_tools.c +++ b/source/blender/src/editmesh_tools.c @@ -4497,7 +4497,7 @@ void bevel_menu() { while(G.editBMesh->options & BME_BEVEL_RUNNING) { options = G.editBMesh->options; res = G.editBMesh->res; - bm = BME_make_mesh(); + bm = BME_make_mesh(512,512,2048,512); bm = BME_editmesh_to_bmesh(G.editMesh, bm); BIF_undo_push("Pre-Bevel"); free_editMesh(G.editMesh); |