diff options
author | Ken Hughes <khughes@pacific.edu> | 2006-09-07 21:22:57 +0400 |
---|---|---|
committer | Ken Hughes <khughes@pacific.edu> | 2006-09-07 21:22:57 +0400 |
commit | d731945f015bd6c51be28d422abb4216a82d8b03 (patch) | |
tree | 95e56c799ed7bc68552255647eb34fce32bccd85 /intern/boolop | |
parent | 352d8cd02d7d77282b2ebd525bef46872373d798 (diff) |
===Tools===
Experimental boolean tool optimization: for very large meshes a significant
amount of time is spend performing linear searches of edges. This patch
implements a "hash" table (really more of a bucket table) to narrow the
search space.
If someone should need to disable this, just remove the "#define HASH" at
the beginning of BOP_Mesh.h
Diffstat (limited to 'intern/boolop')
-rw-r--r-- | intern/boolop/intern/BOP_Mesh.cpp | 213 | ||||
-rw-r--r-- | intern/boolop/intern/BOP_Mesh.h | 29 |
2 files changed, 238 insertions, 4 deletions
diff --git a/intern/boolop/intern/BOP_Mesh.cpp b/intern/boolop/intern/BOP_Mesh.cpp index 6afd1caabaf..3b194ef72d4 100644 --- a/intern/boolop/intern/BOP_Mesh.cpp +++ b/intern/boolop/intern/BOP_Mesh.cpp @@ -1,4 +1,7 @@ /** + * + * $Id$ + * * ***** BEGIN GPL/BL DUAL LICENSE BLOCK ***** * * This program is free software; you can redistribute it and/or @@ -33,8 +36,19 @@ #include <iostream> #include <fstream> +#include "MEM_guardedalloc.h" +#include "BLI_blenlib.h" -BOP_Mesh::BOP_Mesh() {} +BOP_Mesh::BOP_Mesh() +{ +#ifdef HASH +#ifdef HASH_PRINTF_DEBUG + printf ("has hashing\n"); +#endif + hash = NULL; + hashsize = 0; +#endif +} /** * Destroys a mesh. @@ -58,6 +72,15 @@ BOP_Mesh::~BOP_Mesh() delete *itf; } m_faces.clear(); + +#ifdef HASH + while( hashsize ) { + --hashsize; + BLI_freelistN( &hash[hashsize] ); + } + MEM_freeN( hash ); + hash = NULL; +#endif } /** @@ -79,10 +102,129 @@ BOP_Index BOP_Mesh::addVertex(MT_Point3 p) */ BOP_Index BOP_Mesh::addEdge(BOP_Index v1, BOP_Index v2) { +#ifdef HASH + /* prepare a new hash entry for the edge */ + int minv; + EdgeEntry *h = (EdgeEntry *)MEM_callocN( sizeof( EdgeEntry ), "edgehash" ); + + /* store sorted, smallest vert first */ + if( v1 < v2 ) { + minv = HASH(v1); + h->v1 = v1; + h->v2 = v2; + } else { + minv = HASH(v2); + h->v1 = v2; + h->v2 = v1; + } + h->index = m_edges.size(); + + /* if hash index larger than hash list, extend the list */ + if( minv >= hashsize ) { + int newsize = (minv + 8) & ~7; + ListBase *nhash = (ListBase *)MEM_mallocN( + newsize * sizeof( ListBase ), + "edgehashtable" ); + /* copy old entries */ + memcpy( nhash, hash, sizeof( ListBase ) * hashsize ); + /* clear new ones */ + while( hashsize < newsize ) { + nhash[hashsize].first = nhash[hashsize].last = NULL; + ++hashsize; + } + if( hash ) + MEM_freeN( hash ); + hash = nhash; + } + + /* add the entry to tail of the right hash list */ + BLI_addtail( &hash[minv], h ); +#endif m_edges.push_back(new BOP_Edge(v1,v2)); - return (m_edges.size()-1); + return m_edges.size()-1; } +#ifdef HASH +/** + * replace one vertex with another in the hash list + * @param o old mesh vertex index + * @param n new mesh vertex index + * @param x edge's other mesh vertex index + */ +void BOP_Mesh::rehashVertex(BOP_Index o, BOP_Index n, BOP_Index x) +{ + EdgeEntry *edge; + int minv = HASH(o); + BOP_Index v1, v2; + + /* figure out where and what to look for */ + if( o < x ) { + minv = HASH(o); + v1 = o; v2 = x; + } else { + minv = HASH(x); + v1 = x; v2 = o; + } + + /* if hash is valid, search for the match */ + if( minv < hashsize ) { + for(edge = (EdgeEntry *)hash[minv].first; + edge; edge = edge->next ) { + if(edge->v1 == v1 && edge->v2 == v2) + break; + } + + /* NULL edge == no match */ + if(!edge) { +#ifdef HASH_PRINTF_DEBUG + printf ("OOPS! didn't find edge (%d %d)\n",v1,v2); +#endif + return; + } +#ifdef HASH_PRINTF_DEBUG + printf ("found edge (%d %d)\n",v1,v2); +#endif + /* remove the edge from the old hash list */ + BLI_remlink( &hash[minv], edge ); + + /* decide where the new edge should go */ + if( n < x ) { + minv = HASH(n); + v1 = n; v2 = x; + } else { + minv = HASH(x); + edge->v1 = x; edge->v2 = n; + } + + /* if necessary, extend the hash list */ + if( minv >= hashsize ) { +#ifdef HASH_PRINTF_DEBUG + printf ("OOPS! new vertex too large! (%d->%d)\n",o,n); +#endif + int newsize = (minv + 8) & ~7; + ListBase *nhash = (ListBase *)MEM_mallocN( + newsize * sizeof( ListBase ), + "edgehashtable" ); + memcpy( nhash, hash, sizeof( ListBase ) * hashsize ); + while( hashsize < newsize ) { + nhash[hashsize].first = nhash[hashsize].last = NULL; + ++hashsize; + } + if( hash ) + MEM_freeN( hash ); + hash = nhash; + } + + /* add the entry to tail of the right hash list */ + BLI_addtail( &hash[minv], edge ); + } else { +#ifdef HASH_PRINTF_DEBUG + printf ("OOPS! hash not large enough for (%d %d)\n",minv,hashsize); +#endif + } +} +#endif + /** * Adds a new face. * @param face mesh face @@ -240,12 +382,36 @@ BOP_Edge* BOP_Mesh::getEdge(BOP_Indexs edges, BOP_Index v) */ BOP_Edge* BOP_Mesh::getEdge(BOP_Index v1, BOP_Index v2) { +#ifdef HASH + int minv; + EdgeEntry *edge; + + /* figure out where and what to search for */ + if( v1 < v2 ) { + minv = HASH(v1); + } else { + minv = HASH(v2); + BOP_Index tmp = v1; + v1 = v2; + v2 = tmp; + } + + /* if hash index valid, search the list and return match if found */ + if( minv < hashsize ) { + for(edge = (EdgeEntry *)hash[minv].first; + edge; edge = edge->next ) { + if(edge->v1 == v1 && edge->v2 == v2) + return m_edges[edge->index]; + } + } +#else const BOP_IT_Edges edgesEnd = m_edges.end(); for(BOP_IT_Edges edge=m_edges.begin();edge!=edgesEnd;edge++) { if (((*edge)->getVertex1() == v1 && (*edge)->getVertex2() == v2) || ((*edge)->getVertex1() == v2 && (*edge)->getVertex2() == v1)) return *edge; } +#endif return NULL; } @@ -258,6 +424,42 @@ BOP_Edge* BOP_Mesh::getEdge(BOP_Index v1, BOP_Index v2) */ bool BOP_Mesh::getIndexEdge(BOP_Index v1, BOP_Index v2, BOP_Index &e) { +#ifdef HASH + int minv; + EdgeEntry *edge; + + /* figure out what and where to look */ + if( v1 < v2 ) { + minv = HASH(v1); + } else { + minv = HASH(v2); + BOP_Index tmp = v1; + v1 = v2; + v2 = tmp; + } + + /* if hash index is valid, look for a match */ + if( minv < hashsize ) { + for(edge = (EdgeEntry *)hash[minv].first; + edge; edge = edge->next ) { + if(edge->v1 == v1 && edge->v2 == v2) + break; + } + + /* edge != NULL means match */ + if(edge) { +#ifdef HASH_PRINTF_DEBUG + printf ("found edge (%d %d)\n",v1,v2); +#endif + e = edge->index; + return true; + } +#ifdef HASH_PRINTF_DEBUG + else + printf ("didn't find edge (%d %d)\n",v1,v2); +#endif + } +#else BOP_Index pos=0; const BOP_IT_Edges edgesEnd = m_edges.end(); for(BOP_IT_Edges edge=m_edges.begin();edge!=edgesEnd;edge++,pos++) { @@ -267,6 +469,7 @@ bool BOP_Mesh::getIndexEdge(BOP_Index v1, BOP_Index v2, BOP_Index &e) return true; } } +#endif return false; } @@ -536,6 +739,9 @@ BOP_Index BOP_Mesh::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex) v1 = (v1==oldIndex?edge->getVertex2():v1); if ((edge2 = getEdge(newIndex,v1)) == NULL) { edge->replaceVertexIndex(oldIndex,newIndex); +#ifdef HASH + rehashVertex(oldIndex,newIndex,v1); +#endif newVertex->addEdge(*oldEdgeIndex); } else { @@ -548,6 +754,9 @@ BOP_Index BOP_Mesh::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex) BOP_Vertex *oppositeVertex = m_vertexs[v1]; oppositeVertex->removeEdge(*oldEdgeIndex); edge->replaceVertexIndex(oldIndex,newIndex); +#ifdef HASH + rehashVertex(oldIndex,newIndex,v1); +#endif } } oldVertex->setTAG(BROKEN); diff --git a/intern/boolop/intern/BOP_Mesh.h b/intern/boolop/intern/BOP_Mesh.h index e863f9a502c..557939441fc 100644 --- a/intern/boolop/intern/BOP_Mesh.h +++ b/intern/boolop/intern/BOP_Mesh.h @@ -1,4 +1,14 @@ +/* + * TEMPORARY defines to enable hashing support + */ + +#define HASH(x) ((x) >> 5) /* each "hash" covers 32 indices */ +// #define HASH_PRINTF_DEBUG /* uncomment to enable debug output */ + /** + * + * $Id$ + * * ***** BEGIN GPL/BL DUAL LICENSE BLOCK ***** * * This program is free software; you can redistribute it and/or @@ -34,20 +44,31 @@ #include "BOP_Vertex.h" #include "BOP_Edge.h" #include "BOP_Face.h" +#include "DNA_listBase.h" typedef vector<BOP_Vertex *> BOP_Vertexs; typedef vector<BOP_Edge *> BOP_Edges; - typedef vector<BOP_Vertex *>::iterator BOP_IT_Vertexs; typedef vector<BOP_Edge *>::iterator BOP_IT_Edges; +#ifdef HASH +typedef struct EdgeEntry { + struct EdgeEntry *next, *pref; + BOP_Index v1, v2, index; +} EdgeEntry; +#endif + class BOP_Mesh { private: BOP_Vertexs m_vertexs; BOP_Edges m_edges; BOP_Faces m_faces; - +#ifdef HASH + ListBase *hash; + int hashsize; +#endif + BOP_Index addEdge(BOP_Index v1, BOP_Index v2); BOP_Edge *getEdge(BOP_Indexs edges, BOP_Index v2); bool containsFace(BOP_Faces *faces, BOP_Face *face); @@ -83,6 +104,10 @@ public: unsigned int getNumVertexs(BOP_TAG tag); unsigned int getNumFaces(BOP_TAG tag); BOP_Index replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex); +#ifdef HASH + void rehashVertex(BOP_Index oldIndex, BOP_Index newIndex, + BOP_Index otherIndex); +#endif bool isClosedMesh(); // Debug functions |