diff options
Diffstat (limited to 'tool_src/BspLib/VertexChunk.cpp')
| -rw-r--r-- | tool_src/BspLib/VertexChunk.cpp | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/tool_src/BspLib/VertexChunk.cpp b/tool_src/BspLib/VertexChunk.cpp new file mode 100644 index 0000000..8bce25a --- /dev/null +++ b/tool_src/BspLib/VertexChunk.cpp @@ -0,0 +1,237 @@ +//----------------------------------------------------------------------------- +// BSPLIB MODULE: VertexChunk.cpp +// +// Copyright (c) 1997 by Markus Hadwiger +// All Rights Reserved. +//----------------------------------------------------------------------------- + +// bsplib headers +#include "Vertex.h" + + +// if this flag is set storage is increased by using lists. +// this can be very inefficient and should only be used for +// testing purposes! +// if not set, storage is expanded in realloc() style. +//#define EXPAND_STORAGE_WITH_LISTS + +// if this flag is set storage is always increased two-fold +#define EXPAND_EXPONENTIALLY + + +BSPLIB_NAMESPACE_BEGIN + + +// return number of vertices in entire vertex chunk list ---------------------- +// +int VertexChunkRep::getNumElements() const +{ + int num = 0; + for ( const VertexChunkRep *vlist = this; vlist; vlist = vlist->next ) + num += vlist->numvertices; + return num; +} + + +// fetch index to specified vertex if vertex already exists ------------------- +// +int VertexChunkRep::FindVertex( const Vertex3& vertex ) +{ + int numskipped = 0; + + VertexChunkRep *vlist = this; + while ( ( vlist != NULL ) && ( vlist->numvertices > 0 ) ) { + for ( int i = 0; i < vlist->numvertices; i++ ) + if ( vertices[ i ] == vertex ) + return i + numskipped; + numskipped += vlist->numvertices; + vlist = vlist->next; + } + + // vertex not found + return -1; +} + + +// fetch vertex-index if close enough vertex already exists ------------------- +// +int VertexChunkRep::FindCloseVertex( const Vertex3& vertex, int skip ) +{ + int numskipped = 0; + + VertexChunkRep *vlist = this; + while ( ( vlist != NULL ) && ( vlist->numvertices > 0 ) ) { + for ( int i = 0; i < vlist->numvertices; i++ ) + if ( ( i + numskipped > skip ) && vertices[ i ].IsInVicinity( vertex ) ) + return i + numskipped; + numskipped += vlist->numvertices; + vlist = vlist->next; + } + + // vertex not found + return -1; +} + + +// fetch vertex corresponding to specific index ------------------------------- +// +Vertex3& VertexChunkRep::FetchVertex( int index ) +{ + +#ifdef EXPAND_STORAGE_WITH_LISTS + + VertexChunkRep *vlist = this; + while ( ( vlist != NULL ) && ( index >= vlist->numvertices ) ) { + index -= vlist->numvertices; + vlist = vlist->next; + } + + if ( vlist == NULL ) { + // invalid index (too large) + ErrorMessage( "\n***ERROR*** Invalid index in VertexChunk.\n" ); + HandleCriticalError(); + } + + // return vertex + return vlist->vertices[ index ]; + +#else + + if ( index >= numvertices ) { + // invalid index (too large) + ErrorMessage( "\n***ERROR*** Invalid index in VertexChunk.\n" ); + HandleCriticalError(); + } + + // return vertex + return vertices[ index ]; + +#endif + +} + + +// check if multiple vertices exist for the same actual point ----------------- +// +int VertexChunkRep::CheckVertices( int verbose ) +{ + StrScratch message; + + if ( verbose ) { + InfoMessage( "\nChecking vertices...\n" ); + } + + nummultvertices = 0; + int multi = 0; + for ( int i = 0; i < getNumElements(); i++ ) { + int vertindx = FindCloseVertex( FetchVertex( i ), i ); + if ( vertindx != -1 ) { + if ( verbose ) { + if ( multi == 0 ) { + InfoMessage( "*** multiple vertices found ***\n" ); + multi++; + } + sprintf( message, "Vertex %d is same as %d\n", i + 1, vertindx + 1 ); + InfoMessage( message ); + } + nummultvertices++; + } + } + + return nummultvertices; +} + + +// insert vertex into list of vertex chunks, return index; check doublets ----- +// +int VertexChunkRep::AddVertex( Vertex3 vertex ) +{ + +#ifdef EXPAND_STORAGE_WITH_LISTS + + // if vertex contained in head-chunk return index + if ( eliminatedoublets ) + for ( int i = 0; i < numvertices; i++ ) + if ( VerticesEqual( vertices[ i ], vertex ) ) + return i; + + // if space in head-chunk insert vertex directly + if ( numvertices < maxnumvertices ) { + + vertices[ numvertices ] = vertex; + return numvertices++; + + } else { + + int numskipped = numvertices; + VertexChunkRep *vlist = this; + + // scan until non-full chunk found + while ( ( vlist->next != NULL ) && ( vlist->next->numvertices == vlist->next->maxnumvertices ) ) { + + if ( eliminatedoublets ) + for ( int i = 0; i < vlist->next->numvertices; i++ ) + if ( VerticesEqual( vlist->next->vertices[ i ], vertex ) ) + return i + numskipped; + vlist = vlist->next; + numskipped += vlist->numvertices; + } + + if ( vlist->next == NULL ) { + // insert new chunk if all existing are full +#ifdef EXPAND_EXPONENTIALLY + vlist->next = new VertexChunkRep( vlist->maxnumvertices * 2 ); +#else + vlist->next = new VertexChunkRep; +#endif + } else { + if ( eliminatedoublets ) + for ( int i = 0; i < vlist->next->numvertices; i++ ) + if ( VerticesEqual( vlist->next->vertices[ i ], vertex ) ) + return i + numskipped; + } + + // insert new vertex + vlist->next->vertices[ vlist->next->numvertices ] = vertex; + return vlist->next->numvertices++ + numskipped; + } + +#else + + // if vertex already contained in chunk return index + if ( eliminatedoublets ) + for ( int i = 0; i < numvertices; i++ ) + if ( VerticesEqual( vertices[ i ], vertex ) ) + return i; + + // expand storage if necessary + if ( numvertices == maxnumvertices ) { + +#ifdef EXPAND_EXPONENTIALLY + maxnumvertices *= 2; +#else + maxnumvertices += CHUNK_SIZE; +#endif + Vertex3 *temp = new Vertex3[ maxnumvertices ]; + memcpy( temp, vertices, numvertices * sizeof( Vertex3 ) ); + delete[] vertices; + vertices = temp; + } + + vertices[ numvertices ] = vertex; + return numvertices++; + +#endif + +} + + +// VertexChunkRep specific static variables ----------------------------------- +// +const int VertexChunkRep::CHUNK_SIZE = 256; +int VertexChunkRep::eliminatedoublets = 0; + + +BSPLIB_NAMESPACE_END + +//----------------------------------------------------------------------------- |