Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNicholas Bishop <nicholasbishop@gmail.com>2012-02-18 15:34:53 +0400
committerNicholas Bishop <nicholasbishop@gmail.com>2012-02-18 15:34:53 +0400
commit850636e0e4a3ad1d7d5cbb74d9984acbfd821e49 (patch)
tree76cdabbe1774d089e9dfa8a1d77a2970bebdc4d4
parentf3bef40b0cf2a10bcffedae6c5235e3f5537670f (diff)
Remesh modifier: extensive refactoring of the Octree class.
The changes mostly center around two new structures, InternalNode and LeafNode. These provide an explicit representation of the Octree nodes, which formerly were manipulated as opaque byte arrays. A fair amount of commented out/unused code was also removed. This includes the "CINDY" code, which may yet be useful, easy to bring back if so. There should be no difference in the output of the remesh modifier, but memory usage may be slightly different. The flood fill bytes are no longer optional; they will be allocated whether or not the 'remove disconnect components' flag is set. The leaf node is probably not as tightly packed due to alignment issues; this could be fixed with the __attribute__((packed)) flag in gcc (probably there's an MSVC equivalent), but not sure it's worth it. The internal nodes should take up less space on 32-bit systems, allocating sizeof(pointer) now rather than constant eight bytes. These changes were made in persuit of bug #30158 (remesh crashes on PowerPC). There's still a fair amount of bitwise stuff in the Octree, so may still be endian issues and not yet sure if this fixes the bug, but should be much easier to track down problems now.
-rw-r--r--intern/dualcon/intern/MemoryAllocator.h12
-rw-r--r--intern/dualcon/intern/octree.cpp4259
-rw-r--r--intern/dualcon/intern/octree.h1551
3 files changed, 2235 insertions, 3587 deletions
diff --git a/intern/dualcon/intern/MemoryAllocator.h b/intern/dualcon/intern/MemoryAllocator.h
index de9dca175a4..a1be0978409 100644
--- a/intern/dualcon/intern/MemoryAllocator.h
+++ b/intern/dualcon/intern/MemoryAllocator.h
@@ -43,8 +43,8 @@
class VirtualMemoryAllocator
{
public:
- virtual UCHAR * allocate( ) = 0 ;
- virtual void deallocate( UCHAR * obj ) = 0 ;
+ virtual void * allocate( ) = 0 ;
+ virtual void deallocate( void * obj ) = 0 ;
virtual void destroy( ) = 0 ;
virtual void printInfo( ) = 0 ;
@@ -161,7 +161,7 @@ public:
/**
* Allocation method
*/
- UCHAR * allocate ( )
+ void * allocate ( )
{
if ( available == 0 )
{
@@ -170,13 +170,13 @@ public:
// printf("Allocating %d\n", header[ allocated ]) ;
available -- ;
- return stack[ available >> HEAP_BASE ][ available & HEAP_MASK ] ;
+ return (void*)stack[ available >> HEAP_BASE ][ available & HEAP_MASK ] ;
}
/**
* De-allocation method
*/
- void deallocate ( UCHAR * obj )
+ void deallocate ( void * obj )
{
if ( available == stacksize )
{
@@ -184,7 +184,7 @@ public:
}
// printf("De-allocating %d\n", ( obj - data ) / N ) ;
- stack[ available >> HEAP_BASE ][ available & HEAP_MASK ] = obj ;
+ stack[ available >> HEAP_BASE ][ available & HEAP_MASK ] = (UCHAR*)obj ;
available ++ ;
// printf("%d %d\n", allocated, header[ allocated ]) ;
}
diff --git a/intern/dualcon/intern/octree.cpp b/intern/dualcon/intern/octree.cpp
index 90dbf5376a2..38b130f979b 100644
--- a/intern/dualcon/intern/octree.cpp
+++ b/intern/dualcon/intern/octree.cpp
@@ -15,7 +15,7 @@
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
- * Contributor(s): Tao Ju
+ * Contributor(s): Tao Ju, Nicholas Bishop
*
* ***** END GPL LICENSE BLOCK *****
*/
@@ -42,12 +42,12 @@
#define dc_printf(...) do {} while(0)
#endif
-Octree::Octree( ModelReader* mr,
+Octree::Octree(ModelReader* mr,
DualConAllocOutput alloc_output_func,
DualConAddVert add_vert_func,
DualConAddQuad add_quad_func,
DualConFlags flags, DualConMode dualcon_mode, int depth,
- float threshold, float sharpness )
+ float threshold, float sharpness)
: use_flood_fill(flags & DUALCON_FLOOD_FILL),
/* note on `use_manifold':
@@ -72,956 +72,574 @@ Octree::Octree( ModelReader* mr,
add_vert(add_vert_func),
add_quad(add_quad_func)
{
- this->thresh = threshold ;
- this->reader = mr ;
- this->dimen = 1 << GRID_DIMENSION ;
- this->range = reader->getBoundingBox( this->origin ) ;
- this->nodeCount = this->nodeSpace = 0;
- this->maxDepth = depth ;
- this->mindimen = ( dimen >> maxDepth ) ;
- this->minshift = ( GRID_DIMENSION - maxDepth ) ;
- this->buildTable( ) ;
-
- flood_bytes = use_flood_fill ? FLOOD_FILL_BYTES : 0;
- leaf_extra_bytes = flood_bytes + CINDY_BYTES;
-
-#ifdef USE_HERMIT
- leaf_node_bytes = 7 + leaf_extra_bytes;
-#else
- leaf_node_bytes = 3 + leaf_extra_bytes;
-#endif
+ thresh = threshold;
+ reader = mr;
+ dimen = 1 << GRID_DIMENSION;
+ range = reader->getBoundingBox(origin);
+ nodeCount = nodeSpace = 0;
+ maxDepth = depth;
+ mindimen =(dimen >> maxDepth);
+ minshift =(GRID_DIMENSION - maxDepth);
+ buildTable();
-#ifdef QIANYI
- dc_printf("Origin: (%f %f %f), Dimension: %f\n", origin[0], origin[1], origin[2], range) ;
-#endif
-
- this->maxTrianglePerCell = 0 ;
+ maxTrianglePerCell = 0;
// Initialize memory
#ifdef IN_VERBOSE_MODE
- dc_printf("Range: %f origin: %f, %f,%f \n", range, origin[0], origin[1], origin[2] ) ;
- dc_printf("Initialize memory...\n") ;
+ dc_printf("Range: %f origin: %f, %f,%f \n", range, origin[0], origin[1], origin[2]);
+ dc_printf("Initialize memory...\n");
#endif
- initMemory( ) ;
- this->root = createInternal( 0 ) ;
+ initMemory();
+ root = (Node*)createInternal(0);
// Read MC table
#ifdef IN_VERBOSE_MODE
- dc_printf("Reading contour table...\n") ;
+ dc_printf("Reading contour table...\n");
#endif
- this->cubes = new Cubes();
+ cubes = new Cubes();
}
-Octree::~Octree( )
+Octree::~Octree()
{
- freeMemory( ) ;
+ freeMemory();
}
void Octree::scanConvert()
{
// Scan triangles
#if DC_DEBUG
- clock_t start, finish ;
- start = clock( ) ;
+ clock_t start, finish;
+ start = clock();
#endif
- this->addTrian( ) ;
- this->resetMinimalEdges( ) ;
- this->preparePrimalEdgesMask( this->root ) ;
+ addTrian();
+ resetMinimalEdges();
+ preparePrimalEdgesMask(&root->internal);
#if DC_DEBUG
- finish = clock( ) ;
+ finish = clock();
dc_printf("Time taken: %f seconds \n",
- (double)(finish - start) / CLOCKS_PER_SEC ) ;
+ (double)(finish - start) / CLOCKS_PER_SEC);
#endif
// Generate signs
// Find holes
#if DC_DEBUG
- dc_printf("Patching...\n") ;
- start = clock( ) ;
+ dc_printf("Patching...\n");
+ start = clock();
#endif
- this->trace( ) ;
+ trace();
#if DC_DEBUG
- finish = clock( ) ;
- dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC ) ;
+ finish = clock();
+ dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC);
#ifdef IN_VERBOSE_MODE
- dc_printf("Holes: %d Average Length: %f Max Length: %d \n", numRings, (float)totRingLengths / (float) numRings, maxRingLength ) ;
+ dc_printf("Holes: %d Average Length: %f Max Length: %d \n", numRings,(float)totRingLengths /(float) numRings, maxRingLength);
#endif
#endif
// Check again
- int tnumRings = numRings ;
- this->trace( ) ;
+ int tnumRings = numRings;
+ trace();
#ifdef IN_VERBOSE_MODE
- dc_printf("Holes after patching: %d \n", numRings) ;
+ dc_printf("Holes after patching: %d \n", numRings);
#endif
- numRings = tnumRings ;
+ numRings = tnumRings;
#if DC_DEBUG
- dc_printf("Building signs...\n") ;
- start = clock( ) ;
+ dc_printf("Building signs...\n");
+ start = clock();
#endif
- this->buildSigns( ) ;
+ buildSigns();
#if DC_DEBUG
- finish = clock( ) ;
- dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC ) ;
+ finish = clock();
+ dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC);
#endif
if(use_flood_fill) {
/*
- start = clock( ) ;
- this->floodFill( ) ;
+ start = clock();
+ floodFill();
// Check again
- tnumRings = numRings ;
- this->trace( ) ;
- dc_printf("Holes after filling: %d \n", numRings) ;
- numRings = tnumRings ;
- this->buildSigns( ) ;
- finish = clock( ) ;
- dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC ) ;
+ tnumRings = numRings;
+ trace();
+ dc_printf("Holes after filling: %d \n", numRings);
+ numRings = tnumRings;
+ buildSigns();
+ finish = clock();
+ dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC);
*/
#if DC_DEBUG
- start = clock( ) ;
+ start = clock();
dc_printf("Removing components...\n");
#endif
- this->floodFill( ) ;
- this->buildSigns( ) ;
+ floodFill();
+ buildSigns();
// dc_printf("Checking...\n");
- // this->floodFill( ) ;
+ // floodFill();
#if DC_DEBUG
- finish = clock( ) ;
- dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC ) ;
+ finish = clock();
+ dc_printf("Time taken: %f seconds \n",(double)(finish - start) / CLOCKS_PER_SEC);
#endif
}
// Output
-#ifdef OUTPUT_REPAIRED
#if DC_DEBUG
- start = clock( ) ;
+ start = clock();
#endif
writeOut();
#if DC_DEBUG
- finish = clock( ) ;
-#endif
- // dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC ) ;
-#ifdef CINDY
- this->writeTags( "tags.txt" ) ;
- dc_printf("Tags output to tags.txt\n") ;
-#endif
-
+ finish = clock();
#endif
+ // dc_printf("Time taken: %f seconds \n", (double)(finish - start) / CLOCKS_PER_SEC);
// Print info
#ifdef IN_VERBOSE_MODE
- printMemUsage( ) ;
+ printMemUsage();
#endif
}
-#if 0
-void Octree::writeOut( char* fname )
+void Octree::initMemory()
{
- dc_printf( "\n" ) ;
- if ( strstr( fname, ".ply" ) != NULL )
- {
- dc_printf("Writing PLY file format.\n") ;
- this->outType = 1 ;
- writePLY( fname ) ;
- }
- else if ( strstr( fname, ".off" ) != NULL )
- {
- dc_printf("Writing OFF file format.\n") ;
- this->outType = 0 ;
- writeOFF( fname ) ;
- }
- else if ( strstr( fname, ".sof" ) != NULL )
- {
- dc_printf("Writing Signed Octree File format.\n") ;
- this->outType = 2 ;
- writeOctree( fname ) ;
- }
- else if ( strstr( fname, ".dcf" ) != NULL )
- {
-#ifdef USE_HERMIT
- dc_printf("Writing Dual Contouring File format.\n") ;
- this->outType = 3 ;
- writeDCF( fname ) ;
-#else
- dc_printf("Can not write Dual Contouring File format in non-DC mode.\n") ;
-#endif
- }
-#ifdef USE_HERMIT
- else if ( strstr( fname, ".sog" ) != NULL )
- {
- dc_printf("Writing signed octree with geometry.\n") ;
- this->outType = 4 ;
- writeOctreeGeom( fname ) ;
- }
-#endif
- /*
- else if ( strstr( fname, ".sof" ) != NULL )
- {
- dc_printf("Writing SOF file format.\n") ;
- this->outType = 2 ;
- writeOctree( fname ) ;
- }
- */
- else
- {
- dc_printf("Unknown output format.\n") ;
- }
+ leafalloc[0] = new MemoryAllocator<sizeof(LeafNode)>();
+ leafalloc[1] = new MemoryAllocator<sizeof(LeafNode) + sizeof(float) * EDGE_FLOATS>();
+ leafalloc[2] = new MemoryAllocator<sizeof(LeafNode) + sizeof(float) * EDGE_FLOATS * 2>();
+ leafalloc[3] = new MemoryAllocator<sizeof(LeafNode) + sizeof(float) * EDGE_FLOATS * 3>();
+ alloc[0] = new MemoryAllocator<sizeof(InternalNode)>();
+ alloc[1] = new MemoryAllocator<sizeof(InternalNode) + sizeof(Node*)>();
+ alloc[2] = new MemoryAllocator<sizeof(InternalNode) + sizeof(Node*) * 2>();
+ alloc[3] = new MemoryAllocator<sizeof(InternalNode) + sizeof(Node*) * 3>();
+ alloc[4] = new MemoryAllocator<sizeof(InternalNode) + sizeof(Node*) * 4>();
+ alloc[5] = new MemoryAllocator<sizeof(InternalNode) + sizeof(Node*) * 5>();
+ alloc[6] = new MemoryAllocator<sizeof(InternalNode) + sizeof(Node*) * 6>();
+ alloc[7] = new MemoryAllocator<sizeof(InternalNode) + sizeof(Node*) * 7>();
+ alloc[8] = new MemoryAllocator<sizeof(InternalNode) + sizeof(Node*) * 8>();
}
-#endif
-void Octree::initMemory( )
+void Octree::freeMemory()
{
-#ifdef USE_HERMIT
- const int leaf_node_bytes = 7;
-#else
- const int leaf_node_bytes = 3;
-#endif
-
- if(use_flood_fill) {
- const int bytes = leaf_node_bytes + CINDY_BYTES + FLOOD_FILL_BYTES;
- this->leafalloc[ 0 ] = new MemoryAllocator< bytes > ( ) ;
- this->leafalloc[ 1 ] = new MemoryAllocator< bytes + EDGE_BYTES > ( ) ;
- this->leafalloc[ 2 ] = new MemoryAllocator< bytes + EDGE_BYTES * 2 > ( ) ;
- this->leafalloc[ 3 ] = new MemoryAllocator< bytes + EDGE_BYTES * 3 > ( ) ;
- }
- else {
- const int bytes = leaf_node_bytes + CINDY_BYTES;
- this->leafalloc[ 0 ] = new MemoryAllocator< bytes > ( ) ;
- this->leafalloc[ 1 ] = new MemoryAllocator< bytes + EDGE_BYTES > ( ) ;
- this->leafalloc[ 2 ] = new MemoryAllocator< bytes + EDGE_BYTES * 2 > ( ) ;
- this->leafalloc[ 3 ] = new MemoryAllocator< bytes + EDGE_BYTES * 3 > ( ) ;
- }
-
- this->alloc[ 0 ] = new MemoryAllocator< INTERNAL_NODE_BYTES > ( ) ;
- this->alloc[ 1 ] = new MemoryAllocator< INTERNAL_NODE_BYTES + POINTER_BYTES > ( ) ;
- this->alloc[ 2 ] = new MemoryAllocator< INTERNAL_NODE_BYTES + POINTER_BYTES*2 > ( ) ;
- this->alloc[ 3 ] = new MemoryAllocator< INTERNAL_NODE_BYTES + POINTER_BYTES*3 > ( ) ;
- this->alloc[ 4 ] = new MemoryAllocator< INTERNAL_NODE_BYTES + POINTER_BYTES*4 > ( ) ;
- this->alloc[ 5 ] = new MemoryAllocator< INTERNAL_NODE_BYTES + POINTER_BYTES*5 > ( ) ;
- this->alloc[ 6 ] = new MemoryAllocator< INTERNAL_NODE_BYTES + POINTER_BYTES*6 > ( ) ;
- this->alloc[ 7 ] = new MemoryAllocator< INTERNAL_NODE_BYTES + POINTER_BYTES*7 > ( ) ;
- this->alloc[ 8 ] = new MemoryAllocator< INTERNAL_NODE_BYTES + POINTER_BYTES*8 > ( ) ;
-}
-
-void Octree::freeMemory( )
-{
- for ( int i = 0 ; i < 9 ; i ++ )
+ for(int i = 0; i < 9; i ++)
{
- alloc[i]->destroy() ;
- delete alloc[i] ;
+ alloc[i]->destroy();
+ delete alloc[i];
}
- for ( int i = 0 ; i < 4 ; i ++ )
+ for(int i = 0; i < 4; i ++)
{
- leafalloc[i]->destroy() ;
- delete leafalloc[i] ;
+ leafalloc[i]->destroy();
+ delete leafalloc[i];
}
}
-void Octree::printMemUsage( )
+void Octree::printMemUsage()
{
- int totalbytes = 0 ;
- dc_printf("********* Internal nodes: \n") ;
- for ( int i = 0 ; i < 9 ; i ++ )
+ int totalbytes = 0;
+ dc_printf("********* Internal nodes: \n");
+ for(int i = 0; i < 9; i ++)
{
- this->alloc[ i ]->printInfo() ;
+ alloc[i]->printInfo();
- totalbytes += alloc[i]->getAll( ) * alloc[i]->getBytes() ;
+ totalbytes += alloc[i]->getAll() * alloc[i]->getBytes();
}
- dc_printf("********* Leaf nodes: \n") ;
- int totalLeafs = 0 ;
- for ( int i = 0 ; i < 4 ; i ++ )
+ dc_printf("********* Leaf nodes: \n");
+ int totalLeafs = 0;
+ for(int i = 0; i < 4; i ++)
{
- this->leafalloc[ i ]->printInfo() ;
+ leafalloc[i]->printInfo();
- totalbytes += leafalloc[i]->getAll( ) * leafalloc[i]->getBytes() ;
- totalLeafs += leafalloc[i]->getAllocated() ;
+ totalbytes += leafalloc[i]->getAll() * leafalloc[i]->getBytes();
+ totalLeafs += leafalloc[i]->getAllocated();
}
- dc_printf("Total allocated bytes on disk: %d \n", totalbytes) ;
- dc_printf("Total leaf nodes: %d\n", totalLeafs ) ;
-}
-
-void Octree::resetMinimalEdges( )
-{
- this->cellProcParity( this->root, 0, maxDepth ) ;
-}
-
-void Octree::writeModel( char* fname )
-{
- reader->reset() ;
-
- int nFace = reader->getNumTriangles() ;
- Triangle* trian ;
- // int unitcount = 10000;
- int count = 0 ;
- int nVert = nFace * 3 ;
- FILE* modelfout = fopen( "model.off", "w" ) ;
- fprintf( modelfout, "OFF\n" ) ;
- fprintf( modelfout, "%d %d 0\n", nVert, nFace ) ;
-
- //int total = this->reader->getNumTriangles() ;
- dc_printf( "Start writing model to OFF...\n" ) ;
- srand(0) ;
- while ( ( trian = reader->getNextTriangle() ) != NULL )
- {
- // Drop polygons
- {
- int i, j ;
-
- // Blow up the triangle
- float mid[3] = {0, 0, 0} ;
- for ( i = 0 ; i < 3 ; i ++ )
- for ( j = 0 ; j < 3 ; j ++ )
- {
- trian->vt[i][j] = dimen * ( trian->vt[i][j] - origin[j] ) / range ;
-
- mid[j] += trian->vt[i][j] / 3 ;
- }
-
- // Generate projections
- // LONG cube[2][3] = { { 0, 0, 0 }, { dimen, dimen, dimen } } ;
- int trig[3][3] ;
-
- // Blowing up the triangle to the grid
- for ( i = 0 ; i < 3 ; i ++ )
- for ( j = 0 ; j < 3 ; j ++ )
- {
- trig[i][j] = (int) (trian->vt[i][j]) ;
- // Perturb end points, if set so
- }
-
-
- for ( i = 0 ; i < 3 ; i ++ )
- {
- fprintf( modelfout, "%f %f %f\n",
- (float)(((double) trig[i][0] / dimen) * range + origin[0]) ,
- (float)(((double) trig[i][1] / dimen) * range + origin[1]) ,
- (float)(((double) trig[i][2] / dimen) * range + origin[2]) ) ;
- }
- }
- delete trian ;
-
- count ++ ;
-
- }
-
- for ( int i = 0 ; i < nFace ; i ++ )
- {
- fprintf( modelfout, "3 %d %d %d\n", 3 * i + 2, 3 * i + 1, 3 * i ) ;
- }
-
- fclose( modelfout ) ;
-
-}
-
-#ifdef CINDY
-void Octree::writeTags( char* fname )
-{
- FILE* fout = fopen( fname, "w" ) ;
-
- clearCindyBits( root, maxDepth ) ;
- readVertices() ;
- outputTags( root, maxDepth, fout ) ;
-
- fclose ( fout ) ;
-}
-
-void Octree::readVertices( )
-{
- int total = this->reader->getNumVertices() ;
- reader->reset() ;
- float v[3] ;
- int st[3] = {0,0,0};
- int unitcount = 1000 ;
- dc_printf( "\nRead in original %d vertices...\n", total ) ;
-
- for ( int i = 0 ; i < total ; i ++ )
- {
- reader->getNextVertex( v ) ;
- // Blowing up the triangle to the grid
- float mid[3] = {0, 0, 0} ;
- for ( int j = 0 ; j < 3 ; j ++ )
- {
- v[j] = dimen * ( v[j] - origin[j] ) / range ;
- }
-
-// dc_printf("vertex: %f %f %f, dimen: %d\n", v[0], v[1], v[2], dimen ) ;
- readVertex ( root, st, dimen, maxDepth, v, i ) ;
-
-
- if ( i % unitcount == 0 )
- {
- putchar ( 13 ) ;
-
- switch ( ( i / unitcount ) % 4 )
- {
- case 0 : dc_printf("-");
- break ;
- case 1 : dc_printf("/") ;
- break ;
- case 2 : dc_printf("|");
- break ;
- case 3 : dc_printf("\\") ;
- break ;
- }
-
- float percent = (float) i / total ;
- /*
- int totbars = 50 ;
- int bars = (int)( percent * totbars ) ;
- for ( int i = 0 ; i < bars ; i ++ )
- {
- putchar( 219 ) ;
- }
- for ( i = bars ; i < totbars ; i ++ )
- {
- putchar( 176 ) ;
- }
- */
-
- dc_printf(" %d vertices: ", i ) ;
- dc_printf( " %f%% complete.", 100 * percent ) ;
- }
-
- }
- putchar ( 13 ) ;
- dc_printf(" \n");
-}
-
-void Octree::readVertex( UCHAR* node, int st[3], int len, int height, float v[3], int index )
-{
- int nst[3] ;
- nst[0] = ( (int) v[0] / mindimen ) * mindimen ;
- nst[1] = ( (int) v[1] / mindimen ) * mindimen ;
- nst[2] = ( (int) v[2] / mindimen ) * mindimen ;
-
- UCHAR* cell = this->locateLeafCheck( nst ) ;
- if ( cell == NULL )
- {
- dc_printf("Cell %d %d %d is not found!\n", nst[0]/ mindimen, nst[1]/ mindimen, nst[2]/ mindimen) ;
- return ;
- }
-
- setOriginalIndex( cell, index ) ;
-
-
- /*
- int i ;
- if ( height == 0 )
- {
- // Leaf cell, assign index
- dc_printf("Setting: %d\n", index ) ;
- setOriginalIndex( node, index ) ;
- }
- else
- {
- len >>= 1 ;
- // Internal cell, check and recur
- int x = ( v[0] > st[0] + len ) ? 1 : 0 ;
- int y = ( v[1] > st[1] + len ) ? 1 : 0 ;
- int z = ( v[2] > st[2] + len ) ? 1 : 0 ;
- int child = x * 4 + y * 2 + z ;
-
- int count = 0 ;
- for ( i = 0 ; i < 8 ; i ++ )
- {
- if ( i == child && hasChild( node, i ) )
- {
- int nst[3] ;
- nst[0] = st[0] + vertmap[i][0] * len ;
- nst[1] = st[1] + vertmap[i][1] * len ;
- nst[2] = st[2] + vertmap[i][2] * len ;
-
- dc_printf("Depth: %d -- child %d vertex: %f %f %f in %f %f %f\n", height - 1, child, v[0]/mindimen, v[1]/mindimen, v[2]/mindimen,
- nst[0]/mindimen, nst[1]/mindimen, nst[2]/mindimen, len/mindimen ) ;
-
- readVertex( getChild( node, count ), nst, len, height - 1, v, index ) ;
- count ++ ;
- }
- }
- }
- */
-}
-
-void Octree::outputTags( UCHAR* node, int height, FILE* fout )
-{
- int i ;
-
- if ( height == 0 )
- {
- // Leaf cell, generate
- int smask = getSignMask( node ) ;
-
- if(use_manifold) {
- int comps = manifold_table[ smask ].comps ;
- if ( comps != 1 )
- {
- return ;
- }
- }
- else
- {
- if ( smask == 0 || smask == 255 )
- {
- return ;
- }
- }
-
- int rindex = getMinimizerIndex( node ) ;
- int oindex = getOriginalIndex( node ) ;
-
- if ( oindex >= 0 )
- {
- fprintf( fout, "%d: %d\n", rindex, oindex ) ;
- }
-
- }
- else
- {
- // Internal cell, recur
- int count = 0 ;
- for ( i = 0 ; i < 8 ; i ++ )
- {
- if ( hasChild( node, i ) )
- {
- outputTags( getChild( node, count ), height - 1, fout ) ;
- count ++ ;
- }
- }
- }
+ dc_printf("Total allocated bytes on disk: %d \n", totalbytes);
+ dc_printf("Total leaf nodes: %d\n", totalLeafs);
}
-void Octree::clearCindyBits( UCHAR* node, int height )
+void Octree::resetMinimalEdges()
{
- int i;
-
- if ( height == 0 )
- {
- // Leaf cell,
- {
- setOriginalIndex( node, - 1 ) ;
- }
- }
- else
- {
- // Internal cell, recur
- int count = 0 ;
- for ( i = 0 ; i < 8 ; i ++ )
- {
- if ( hasChild( node, i ) )
- {
- clearCindyBits( getChild( node, count ), height - 1 ) ;
- count ++ ;
- }
- }
- }
+ cellProcParity(root, 0, maxDepth);
}
-#endif
-void Octree::addTrian( )
+void Octree::addTrian()
{
- Triangle* trian ;
- int count = 0 ;
+ Triangle* trian;
+ int count = 0;
#if DC_DEBUG
- int total = this->reader->getNumTriangles() ;
- int unitcount = 1000 ;
- dc_printf( "\nScan converting to depth %d...\n", maxDepth ) ;
+ int total = reader->getNumTriangles();
+ int unitcount = 1000;
+ dc_printf("\nScan converting to depth %d...\n", maxDepth);
#endif
- srand(0) ;
+ srand(0);
- while ( ( trian = reader->getNextTriangle() ) != NULL )
+ while((trian = reader->getNextTriangle()) != NULL)
{
// Drop triangles
{
- addTrian ( trian, count ) ;
+ addTrian(trian, count);
}
- delete trian ;
+ delete trian;
- count ++ ;
+ count ++;
#if DC_DEBUG
- if ( count % unitcount == 0 )
+ if(count % unitcount == 0)
{
- putchar ( 13 ) ;
+ putchar(13);
- switch ( ( count / unitcount ) % 4 )
+ switch((count / unitcount) % 4)
{
case 0 : dc_printf("-");
- break ;
- case 1 : dc_printf("/") ;
- break ;
+ break;
+ case 1 : dc_printf("/");
+ break;
case 2 : dc_printf("|");
- break ;
- case 3 : dc_printf("\\") ;
- break ;
+ break;
+ case 3 : dc_printf("\\");
+ break;
}
- float percent = (float) count / total ;
+ float percent =(float) count / total;
/*
- int totbars = 50 ;
- int bars = (int)( percent * totbars ) ;
- for ( int i = 0 ; i < bars ; i ++ )
+ int totbars = 50;
+ int bars =(int)(percent * totbars);
+ for(int i = 0; i < bars; i ++)
{
- putchar( 219 ) ;
+ putchar(219);
}
- for ( i = bars ; i < totbars ; i ++ )
+ for(i = bars; i < totbars; i ++)
{
- putchar( 176 ) ;
+ putchar(176);
}
*/
- dc_printf(" %d triangles: ", count ) ;
- dc_printf( " %f%% complete.", 100 * percent ) ;
+ dc_printf(" %d triangles: ", count);
+ dc_printf(" %f%% complete.", 100 * percent);
}
#endif
}
- putchar ( 13 ) ;
+ putchar(13);
}
-void Octree::addTrian( Triangle* trian, int triind )
+void Octree::addTrian(Triangle* trian, int triind)
{
- int i, j ;
+ int i, j;
// Blowing up the triangle to the grid
- float mid[3] = {0, 0, 0} ;
- for ( i = 0 ; i < 3 ; i ++ )
- for ( j = 0 ; j < 3 ; j ++ )
+ float mid[3] = {0, 0, 0};
+ for(i = 0; i < 3; i ++)
+ for(j = 0; j < 3; j ++)
{
- trian->vt[i][j] = dimen * ( trian->vt[i][j] - origin[j] ) / range ;
- mid[j] += trian->vt[i][j] / 3 ;
+ trian->vt[i][j] = dimen *(trian->vt[i][j] - origin[j]) / range;
+ mid[j] += trian->vt[i][j] / 3;
}
// Generate projections
- LONG cube[2][3] = { { 0, 0, 0 }, { dimen, dimen, dimen } } ;
- LONG trig[3][3] ;
+ LONG cube[2][3] = {{0, 0, 0}, {dimen, dimen, dimen}};
+ LONG trig[3][3];
- for ( i = 0 ; i < 3 ; i ++ )
- for ( j = 0 ; j < 3 ; j ++ )
+ for(i = 0; i < 3; i ++)
+ for( j = 0; j < 3; j ++)
{
- trig[i][j] = (LONG) (trian->vt[i][j]) ;
+ trig[i][j] =(LONG)(trian->vt[i][j]);
// Perturb end points, if set so
}
// Add to the octree
- // int start[3] = { 0, 0, 0 } ;
- LONG errorvec = (LONG) ( 0 ) ;
- Projections* proj = new Projections( cube, trig, errorvec, triind ) ;
- root = addTrian( root, proj, maxDepth ) ;
+ // int start[3] = {0, 0, 0};
+ LONG errorvec =(LONG)(0);
+ Projections* proj = new Projections(cube, trig, errorvec, triind);
+ root = (Node*)addTrian(&root->internal, proj, maxDepth);
- delete proj->inherit ;
- delete proj ;
+ delete proj->inherit;
+ delete proj;
}
-UCHAR* Octree::addTrian( UCHAR* node, Projections* p, int height )
+InternalNode* Octree::addTrian(InternalNode* node, Projections* p, int height)
{
- int i ;
- int vertdiff[8][3] = {{0,0,0},{0,0,1},{0,1,-1},{0,0,1},{1,-1,-1},{0,0,1},{0,1,-1},{0,0,1}} ;
- UCHAR boxmask = p->getBoxMask( ) ;
- Projections* subp = new Projections( p ) ;
+ int i;
+ int vertdiff[8][3] = {{0,0,0},{0,0,1},{0,1,-1},{0,0,1},{1,-1,-1},{0,0,1},{0,1,-1},{0,0,1}};
+ UCHAR boxmask = p->getBoxMask();
+ Projections* subp = new Projections(p);
- int count = 0 ;
- int tempdiff[3] = {0,0,0} ;
- for ( i = 0 ; i < 8 ; i ++ )
+ int count = 0;
+ int tempdiff[3] = {0,0,0};
+ for(i = 0; i < 8; i ++)
{
- tempdiff[0] += vertdiff[i][0] ;
- tempdiff[1] += vertdiff[i][1] ;
- tempdiff[2] += vertdiff[i][2] ;
+ tempdiff[0] += vertdiff[i][0];
+ tempdiff[1] += vertdiff[i][1];
+ tempdiff[2] += vertdiff[i][2];
/* Quick pruning using bounding box */
- if ( boxmask & ( 1 << i ) )
+ if(boxmask &(1 << i))
{
- subp->shift( tempdiff ) ;
- tempdiff[0] = tempdiff[1] = tempdiff[2] = 0 ;
+ subp->shift(tempdiff);
+ tempdiff[0] = tempdiff[1] = tempdiff[2] = 0;
/* Pruning using intersection test */
- if ( subp->isIntersecting() )
- // if ( subp->getIntersectionMasks( cedgemask, edgemask ) )
+ if(subp->isIntersecting())
+ // if(subp->getIntersectionMasks(cedgemask, edgemask))
{
- if ( ! hasChild( node, i ) )
+ if(! hasChild(node, i))
{
- if ( height == 1 )
+ if(height == 1)
{
- node = addLeafChild( node, i, count, createLeaf(0) ) ;
+ node = addLeafChild(node, i, count, createLeaf(0));
}
else
{
- node = addInternalChild( node, i, count, createInternal(0) ) ;
+ node = addInternalChild(node, i, count, createInternal(0));
}
}
- UCHAR* chd = getChild( node, count ) ;
+ Node* chd = getChild(node, count);
- if ( ! isLeaf( node, i ) )
+ if(! isLeaf(node, i))
{
- // setChild( node, count, addTrian ( chd, subp, height - 1, vertmask[i], edgemask ) ) ;
- setChild( node, count, addTrian ( chd, subp, height - 1 ) ) ;
+ // setChild(node, count, addTrian(chd, subp, height - 1, vertmask[i], edgemask));
+ setChild(node, count, (Node*)addTrian(&chd->internal, subp, height - 1));
}
else
{
- setChild( node, count, updateCell( chd, subp ) ) ;
+ setChild(node, count, (Node*)updateCell(&chd->leaf, subp));
}
}
}
- if ( hasChild( node, i ) )
+ if(hasChild(node, i))
{
- count ++ ;
+ count ++;
}
}
- delete subp ;
- return node ;
+ delete subp;
+
+ return node;
}
-UCHAR* Octree::updateCell( UCHAR* node, Projections* p )
+LeafNode* Octree::updateCell(LeafNode* node, Projections* p)
{
- int i ;
+ int i;
// Edge connectivity
- int mask[3] = { 0, 4, 8 } ;
- int oldc = 0, newc = 0 ;
- float offs[3] ;
-#ifdef USE_HERMIT
- float a[3], b[3], c[3] ;
-#endif
+ int mask[3] = {0, 4, 8 };
+ int oldc = 0, newc = 0;
+ float offs[3];
+ float a[3], b[3], c[3];
- for ( i = 0 ; i < 3 ; i ++ )
+ for(i = 0; i < 3; i ++)
{
- if ( ! getEdgeParity( node, mask[i] ) )
+ if(! getEdgeParity(node, mask[i]))
{
- if ( p->isIntersectingPrimary( i ) )
+ if(p->isIntersectingPrimary(i))
{
- // this->actualQuads ++ ;
- setEdge( node, mask[i] ) ;
- offs[ newc ] = p->getIntersectionPrimary( i ) ;
-#ifdef USE_HERMIT
- a[ newc ] = (float) p->inherit->norm[0] ;
- b[ newc ] = (float) p->inherit->norm[1] ;
- c[ newc ] = (float) p->inherit->norm[2] ;
-#endif
- newc ++ ;
+ // actualQuads ++;
+ setEdge(node, mask[i]);
+ offs[newc] = p->getIntersectionPrimary(i);
+ a[newc] =(float) p->inherit->norm[0];
+ b[newc] =(float) p->inherit->norm[1];
+ c[newc] =(float) p->inherit->norm[2];
+ newc ++;
}
}
else
{
-#ifndef USE_HERMIT
- offs[ newc ] = getEdgeOffset( node, oldc ) ;
-#else
- offs[ newc ] = getEdgeOffsetNormal( node, oldc, a[ newc ], b[ newc ], c[ newc ] ) ;
-#endif
+ offs[newc] = getEdgeOffsetNormal(node, oldc, a[newc], b[newc], c[newc]);
-// if ( p->isIntersectingPrimary( i ) )
+// if(p->isIntersectingPrimary(i))
{
- // dc_printf("Multiple intersections!\n") ;
+ // dc_printf("Multiple intersections!\n");
-// setPatchEdge( node, i ) ;
+// setPatchEdge(node, i);
}
- oldc ++ ;
- newc ++ ;
+ oldc ++;
+ newc ++;
}
}
- if ( newc > oldc )
+ if(newc > oldc)
{
// New offsets added, update this node
-#ifndef USE_HERMIT
- node = updateEdgeOffsets( node, oldc, newc, offs ) ;
-#else
- node = updateEdgeOffsetsNormals( node, oldc, newc, offs, a, b, c ) ;
-#endif
+ node = updateEdgeOffsetsNormals(node, oldc, newc, offs, a, b, c);
}
-
-
- return node ;
+ return node;
}
-void Octree::preparePrimalEdgesMask( UCHAR* node )
+void Octree::preparePrimalEdgesMask(InternalNode* node)
{
- int count = 0 ;
- for ( int i = 0 ; i < 8 ; i ++ )
+ int count = 0;
+ for(int i = 0; i < 8; i ++)
{
- if ( hasChild( node, i ) )
+ if(hasChild(node, i))
{
- if ( isLeaf( node, i ) )
- {
- createPrimalEdgesMask( getChild( node, count ) ) ;
- }
+ if(isLeaf(node, i))
+ createPrimalEdgesMask(&getChild(node, count)->leaf);
else
- {
- preparePrimalEdgesMask( getChild( node, count ) ) ;
- }
+ preparePrimalEdgesMask(&getChild(node, count)->internal);
- count ++ ;
+ count ++;
}
}
}
-void Octree::trace( )
+void Octree::trace()
{
- int st[3] = { 0, 0, 0, } ;
- this->numRings = 0 ;
- this->totRingLengths = 0 ;
- this->maxRingLength = 0 ;
+ int st[3] = {0, 0, 0,};
+ numRings = 0;
+ totRingLengths = 0;
+ maxRingLength = 0;
- PathList* chdpath = NULL ;
- this->root = trace( this->root, st, dimen, maxDepth, chdpath ) ;
+ PathList* chdpath = NULL;
+ root = trace(root, st, dimen, maxDepth, chdpath);
- if ( chdpath != NULL )
+ if(chdpath != NULL)
{
- dc_printf("there are incomplete rings.\n") ;
- printPaths( chdpath ) ;
+ dc_printf("there are incomplete rings.\n");
+ printPaths(chdpath);
};
}
-UCHAR* Octree::trace( UCHAR* node, int* st, int len, int depth, PathList*& paths)
+Node* Octree::trace(Node* newnode, int* st, int len, int depth, PathList*& paths)
{
- UCHAR* newnode = node ;
- len >>= 1 ;
- PathList* chdpaths[ 8 ] ;
- UCHAR* chd[ 8 ] ;
- int nst[ 8 ][ 3 ] ;
- int i, j ;
+ len >>= 1;
+ PathList* chdpaths[8];
+ Node* chd[8];
+ int nst[8][3];
+ int i, j;
// Get children paths
- int chdleaf[ 8 ] ;
- fillChildren( newnode, chd, chdleaf ) ;
+ int chdleaf[8];
+ fillChildren(&newnode->internal, chd, chdleaf);
- // int count = 0 ;
- for ( i = 0 ; i < 8 ; i ++ )
+ // int count = 0;
+ for(i = 0; i < 8; i ++)
{
- for ( j = 0 ; j < 3 ; j ++ )
+ for(j = 0; j < 3; j ++)
{
- nst[ i ][ j ] = st[ j ] + len * vertmap[ i ][ j ] ;
+ nst[i][j] = st[j] + len * vertmap[i][j];
}
- if ( chd[ i ] == NULL || isLeaf( node, i ) )
+ if(chd[i] == NULL || isLeaf(&newnode->internal, i))
{
- chdpaths[ i ] = NULL ;
+ chdpaths[i] = NULL;
}
else
{
- trace( chd[ i ], nst[i], len, depth - 1, chdpaths[ i ] ) ;
+ trace(chd[i], nst[i], len, depth - 1, chdpaths[i]);
}
}
// Get connectors on the faces
- PathList* conn[ 12 ] ;
- UCHAR* nf[2] ;
- int lf[2] ;
- int df[2] = { depth - 1, depth - 1 } ;
- int* nstf[ 2 ];
+ PathList* conn[12];
+ Node* nf[2];
+ int lf[2];
+ int df[2] = {depth - 1, depth - 1};
+ int* nstf[2];
- fillChildren( newnode, chd, chdleaf ) ;
+ fillChildren(&newnode->internal, chd, chdleaf);
- for ( i = 0 ; i < 12 ; i ++ )
+ for(i = 0; i < 12; i ++)
{
- int c[ 2 ] = { cellProcFaceMask[ i ][ 0 ], cellProcFaceMask[ i ][ 1 ] };
+ int c[2] = {cellProcFaceMask[i][0], cellProcFaceMask[i][1]};
- for ( int j = 0 ; j < 2 ; j ++ )
+ for(int j = 0; j < 2; j ++)
{
- lf[j] = chdleaf[ c[j] ] ;
- nf[j] = chd[ c[j] ] ;
- nstf[j] = nst[ c[j] ] ;
+ lf[j] = chdleaf[c[j]];
+ nf[j] = chd[c[j]];
+ nstf[j] = nst[c[j]];
}
- conn[ i ] = NULL ;
+ conn[i] = NULL;
- findPaths( nf, lf, df, nstf, depth - 1, cellProcFaceMask[ i ][ 2 ], conn[ i ] ) ;
+ findPaths((Node**)nf, lf, df, nstf, depth - 1, cellProcFaceMask[i][2], conn[i]);
- //if ( conn[i] )
+ //if(conn[i])
//{
- // printPath( conn[i] ) ;
+ // printPath(conn[i]);
//}
}
// Connect paths
- PathList* rings = NULL ;
- combinePaths( chdpaths[0], chdpaths[1], conn[8], rings ) ;
- combinePaths( chdpaths[2], chdpaths[3], conn[9], rings ) ;
- combinePaths( chdpaths[4], chdpaths[5], conn[10], rings ) ;
- combinePaths( chdpaths[6], chdpaths[7], conn[11], rings ) ;
-
- combinePaths( chdpaths[0], chdpaths[2], conn[4], rings ) ;
- combinePaths( chdpaths[4], chdpaths[6], conn[5], rings ) ;
- combinePaths( chdpaths[0], NULL, conn[6], rings ) ;
- combinePaths( chdpaths[4], NULL, conn[7], rings ) ;
-
- combinePaths( chdpaths[0], chdpaths[4], conn[0], rings ) ;
- combinePaths( chdpaths[0], NULL, conn[1], rings ) ;
- combinePaths( chdpaths[0], NULL, conn[2], rings ) ;
- combinePaths( chdpaths[0], NULL, conn[3], rings ) ;
+ PathList* rings = NULL;
+ combinePaths(chdpaths[0], chdpaths[1], conn[8], rings);
+ combinePaths(chdpaths[2], chdpaths[3], conn[9], rings);
+ combinePaths(chdpaths[4], chdpaths[5], conn[10], rings);
+ combinePaths(chdpaths[6], chdpaths[7], conn[11], rings);
+
+ combinePaths(chdpaths[0], chdpaths[2], conn[4], rings);
+ combinePaths(chdpaths[4], chdpaths[6], conn[5], rings);
+ combinePaths(chdpaths[0], NULL, conn[6], rings);
+ combinePaths(chdpaths[4], NULL, conn[7], rings);
+
+ combinePaths(chdpaths[0], chdpaths[4], conn[0], rings);
+ combinePaths(chdpaths[0], NULL, conn[1], rings);
+ combinePaths(chdpaths[0], NULL, conn[2], rings);
+ combinePaths(chdpaths[0], NULL, conn[3], rings);
// By now, only chdpaths[0] and rings have contents
// Process rings
- if ( rings )
+ if(rings)
{
- // printPath( rings ) ;
+ // printPath(rings);
/* Let's count first */
- PathList* trings = rings ;
- while ( trings )
+ PathList* trings = rings;
+ while(trings)
{
- this->numRings ++ ;
- this->totRingLengths += trings->length ;
- if ( trings->length > this->maxRingLength )
+ numRings ++;
+ totRingLengths += trings->length;
+ if(trings->length > maxRingLength)
{
- this->maxRingLength = trings->length ;
+ maxRingLength = trings->length;
}
- trings = trings->next ;
+ trings = trings->next;
}
- // printPath( rings ) ;
- newnode = patch( newnode, st, ( len << 1 ), rings ) ;
+ // printPath(rings);
+ newnode = patch(newnode, st,(len << 1), rings);
}
// Return incomplete paths
- paths = chdpaths[0] ;
- return newnode ;
+ paths = chdpaths[0];
+ return newnode;
}
-void Octree::findPaths( UCHAR* node[2], int leaf[2], int depth[2], int* st[2], int maxdep, int dir, PathList*& paths )
+void Octree::findPaths(Node* node[2], int leaf[2], int depth[2], int* st[2], int maxdep, int dir, PathList*& paths)
{
- if ( ! ( node[0] && node[1] ) )
+ if(!(node[0] && node[1]))
{
- return ;
+ return;
}
- if ( ! ( leaf[0] && leaf[1] ) )
+ if(!(leaf[0] && leaf[1]))
{
// Not at the bottom, recur
// Fill children nodes
- int i, j ;
- UCHAR* chd[ 2 ][ 8 ] ;
- int chdleaf[ 2 ][ 8 ] ;
- int nst[ 2 ][ 8 ][ 3 ] ;
+ int i, j;
+ Node* chd[2][8];
+ int chdleaf[2][8];
+ int nst[2][8][3];
- for ( j = 0 ; j < 2 ; j ++ )
+ for(j = 0; j < 2; j ++)
{
- if ( ! leaf[j] )
+ if(! leaf[j])
{
- fillChildren( node[j], chd[j], chdleaf[j] ) ;
+ fillChildren(&node[j]->internal, chd[j], chdleaf[j]);
- int len = ( dimen >> ( maxDepth - depth[j] + 1 ) ) ;
- for ( i = 0 ; i < 8 ; i ++ )
+ int len =(dimen >>(maxDepth - depth[j] + 1));
+ for(i = 0; i < 8; i ++)
{
- for ( int k = 0 ; k < 3 ; k ++ )
+ for(int k = 0; k < 3; k ++)
{
- nst[ j ][ i ][ k ] = st[ j ][ k ] + len * vertmap[ i ][ k ] ;
+ nst[j][i][k] = st[j][k] + len * vertmap[i][k];
}
}
@@ -1029,2428 +647,1626 @@ void Octree::findPaths( UCHAR* node[2], int leaf[2], int depth[2], int* st[2], i
}
// 4 face calls
- UCHAR* nf[2] ;
- int df[2] ;
- int lf[2] ;
- int* nstf[2] ;
- for ( i = 0 ; i < 4 ; i ++ )
+ Node* nf[2];
+ int df[2];
+ int lf[2];
+ int* nstf[2];
+ for(i = 0; i < 4; i ++)
{
- int c[2] = { faceProcFaceMask[ dir ][ i ][ 0 ], faceProcFaceMask[ dir ][ i ][ 1 ] };
- for ( int j = 0 ; j < 2 ; j ++ )
+ int c[2] = {faceProcFaceMask[dir][i][0], faceProcFaceMask[dir][i][1]};
+ for(int j = 0; j < 2; j ++)
{
- if ( leaf[j] )
+ if(leaf[j])
{
- lf[j] = leaf[j] ;
- nf[j] = node[j] ;
- df[j] = depth[j] ;
- nstf[j] = st[j] ;
+ lf[j] = leaf[j];
+ nf[j] = node[j];
+ df[j] = depth[j];
+ nstf[j] = st[j];
}
else
{
- lf[j] = chdleaf[ j ][ c[j] ] ;
- nf[j] = chd[ j ][ c[j] ] ;
- df[j] = depth[j] - 1 ;
- nstf[j] = nst[ j ][ c[j] ] ;
+ lf[j] = chdleaf[j][c[j]];
+ nf[j] = chd[j][c[j]];
+ df[j] = depth[j] - 1;
+ nstf[j] = nst[j][c[j]];
}
}
- findPaths( nf, lf, df, nstf, maxdep - 1, faceProcFaceMask[ dir ][ i ][ 2 ], paths ) ;
+ findPaths(nf, lf, df, nstf, maxdep - 1, faceProcFaceMask[dir][i][2], paths);
}
}
else
{
// At the bottom, check this face
- int ind = ( depth[0] == maxdep ? 0 : 1 ) ;
- int fcind = 2 * dir + ( 1 - ind ) ;
- if ( getFaceParity( node[ ind ], fcind ) )
+ int ind =(depth[0] == maxdep ? 0 : 1);
+ int fcind = 2 * dir +(1 - ind);
+ if(getFaceParity((LeafNode*)node[ind], fcind))
{
// Add into path
- PathElement* ele1 = new PathElement ;
- PathElement* ele2 = new PathElement ;
+ PathElement* ele1 = new PathElement;
+ PathElement* ele2 = new PathElement;
- ele1->pos[0] = st[0][0] ;
- ele1->pos[1] = st[0][1] ;
- ele1->pos[2] = st[0][2] ;
+ ele1->pos[0] = st[0][0];
+ ele1->pos[1] = st[0][1];
+ ele1->pos[2] = st[0][2];
- ele2->pos[0] = st[1][0] ;
- ele2->pos[1] = st[1][1] ;
- ele2->pos[2] = st[1][2] ;
+ ele2->pos[0] = st[1][0];
+ ele2->pos[1] = st[1][1];
+ ele2->pos[2] = st[1][2];
- ele1->next = ele2 ;
- ele2->next = NULL ;
+ ele1->next = ele2;
+ ele2->next = NULL;
- PathList* lst = new PathList ;
- lst->head = ele1 ;
- lst->tail = ele2 ;
- lst->length = 2 ;
- lst->next = paths ;
- paths = lst ;
+ PathList* lst = new PathList;
+ lst->head = ele1;
+ lst->tail = ele2;
+ lst->length = 2;
+ lst->next = paths;
+ paths = lst;
- // int l = ( dimen >> maxDepth ) ;
+ // int l =(dimen >> maxDepth);
}
}
}
-void Octree::combinePaths( PathList*& list1, PathList* list2, PathList* paths, PathList*& rings )
+void Octree::combinePaths(PathList*& list1, PathList* list2, PathList* paths, PathList*& rings)
{
// Make new list of paths
- PathList* nlist = NULL ;
+ PathList* nlist = NULL;
// Search for each connectors in paths
- PathList* tpaths = paths ;
- PathList* tlist, * pre ;
- while ( tpaths )
+ PathList* tpaths = paths;
+ PathList* tlist, * pre;
+ while(tpaths)
{
- PathList* singlist = tpaths ;
- PathList* templist ;
- tpaths = tpaths->next ;
- singlist->next = NULL ;
+ PathList* singlist = tpaths;
+ PathList* templist;
+ tpaths = tpaths->next;
+ singlist->next = NULL;
// Look for hookup in list1
- tlist = list1 ;
- pre = NULL ;
- while ( tlist )
+ tlist = list1;
+ pre = NULL;
+ while(tlist)
{
- if ( (templist = combineSinglePath( list1, pre, tlist, singlist, NULL, singlist )) != NULL )
+ if((templist = combineSinglePath(list1, pre, tlist, singlist, NULL, singlist)) != NULL)
{
- singlist = templist ;
- continue ;
+ singlist = templist;
+ continue;
}
- pre = tlist ;
- tlist = tlist->next ;
+ pre = tlist;
+ tlist = tlist->next;
}
// Look for hookup in list2
- tlist = list2 ;
- pre = NULL ;
- while ( tlist )
+ tlist = list2;
+ pre = NULL;
+ while(tlist)
{
- if ( (templist = combineSinglePath( list2, pre, tlist, singlist, NULL, singlist )) != NULL )
+ if((templist = combineSinglePath(list2, pre, tlist, singlist, NULL, singlist)) != NULL)
{
- singlist = templist ;
- continue ;
+ singlist = templist;
+ continue;
}
- pre = tlist ;
- tlist = tlist->next ;
+ pre = tlist;
+ tlist = tlist->next;
}
// Look for hookup in nlist
- tlist = nlist ;
- pre = NULL ;
- while ( tlist )
+ tlist = nlist;
+ pre = NULL;
+ while(tlist)
{
- if ( (templist = combineSinglePath( nlist, pre, tlist, singlist, NULL, singlist )) != NULL )
+ if((templist = combineSinglePath(nlist, pre, tlist, singlist, NULL, singlist)) != NULL)
{
- singlist = templist ;
- continue ;
+ singlist = templist;
+ continue;
}
- pre = tlist ;
- tlist = tlist->next ;
+ pre = tlist;
+ tlist = tlist->next;
}
// Add to nlist or rings
- if ( isEqual( singlist->head, singlist->tail ) )
+ if(isEqual(singlist->head, singlist->tail))
{
- PathElement* temp = singlist->head ;
- singlist->head = temp->next ;
- delete temp ;
- singlist->length -- ;
- singlist->tail->next = singlist->head ;
-
- singlist->next = rings ;
- rings = singlist ;
+ PathElement* temp = singlist->head;
+ singlist->head = temp->next;
+ delete temp;
+ singlist->length --;
+ singlist->tail->next = singlist->head;
+
+ singlist->next = rings;
+ rings = singlist;
}
else
{
- singlist->next = nlist ;
- nlist = singlist ;
+ singlist->next = nlist;
+ nlist = singlist;
}
}
// Append list2 and nlist to the end of list1
- tlist = list1 ;
- if ( tlist != NULL )
+ tlist = list1;
+ if(tlist != NULL)
{
- while ( tlist->next != NULL )
+ while(tlist->next != NULL)
{
- tlist = tlist->next ;
+ tlist = tlist->next;
}
- tlist->next = list2 ;
+ tlist->next = list2;
}
else
{
- tlist = list2 ;
- list1 = list2 ;
+ tlist = list2;
+ list1 = list2;
}
- if ( tlist != NULL )
+ if(tlist != NULL)
{
- while ( tlist->next != NULL )
+ while(tlist->next != NULL)
{
- tlist = tlist->next ;
+ tlist = tlist->next;
}
- tlist->next = nlist ;
+ tlist->next = nlist;
}
else
{
- tlist = nlist ;
- list1 = nlist ;
+ tlist = nlist;
+ list1 = nlist;
}
}
-PathList* Octree::combineSinglePath( PathList*& head1, PathList* pre1, PathList*& list1, PathList*& head2, PathList* pre2, PathList*& list2 )
+PathList* Octree::combineSinglePath(PathList*& head1, PathList* pre1, PathList*& list1, PathList*& head2, PathList* pre2, PathList*& list2)
{
- if ( isEqual( list1->head, list2->head ) || isEqual( list1->tail, list2->tail ) )
+ if(isEqual(list1->head, list2->head) || isEqual(list1->tail, list2->tail))
{
// Reverse the list
- if ( list1->length < list2->length )
+ if(list1->length < list2->length)
{
// Reverse list1
- PathElement* prev = list1->head ;
- PathElement* next = prev->next ;
- prev->next = NULL ;
- while ( next != NULL )
+ PathElement* prev = list1->head;
+ PathElement* next = prev->next;
+ prev->next = NULL;
+ while(next != NULL)
{
- PathElement* tnext = next->next ;
- next->next = prev ;
+ PathElement* tnext = next->next;
+ next->next = prev;
- prev = next ;
- next = tnext ;
+ prev = next;
+ next = tnext;
}
- list1->tail = list1->head ;
- list1->head = prev ;
+ list1->tail = list1->head;
+ list1->head = prev;
}
else
{
// Reverse list2
- PathElement* prev = list2->head ;
- PathElement* next = prev->next ;
- prev->next = NULL ;
- while ( next != NULL )
+ PathElement* prev = list2->head;
+ PathElement* next = prev->next;
+ prev->next = NULL;
+ while(next != NULL)
{
- PathElement* tnext = next->next ;
- next->next = prev ;
+ PathElement* tnext = next->next;
+ next->next = prev;
- prev = next ;
- next = tnext ;
+ prev = next;
+ next = tnext;
}
- list2->tail = list2->head ;
- list2->head = prev ;
+ list2->tail = list2->head;
+ list2->head = prev;
}
}
- if ( isEqual( list1->head, list2->tail ) )
+ if(isEqual(list1->head, list2->tail))
{
// Easy case
- PathElement* temp = list1->head->next ;
- delete list1->head ;
- list2->tail->next = temp ;
+ PathElement* temp = list1->head->next;
+ delete list1->head;
+ list2->tail->next = temp;
- PathList* nlist = new PathList ;
- nlist->length = list1->length + list2->length - 1 ;
- nlist->head = list2->head ;
- nlist->tail = list1->tail ;
- nlist->next = NULL ;
+ PathList* nlist = new PathList;
+ nlist->length = list1->length + list2->length - 1;
+ nlist->head = list2->head;
+ nlist->tail = list1->tail;
+ nlist->next = NULL;
- deletePath( head1, pre1, list1 ) ;
- deletePath( head2, pre2, list2 ) ;
+ deletePath(head1, pre1, list1);
+ deletePath(head2, pre2, list2);
- return nlist ;
+ return nlist;
}
- else if ( isEqual( list1->tail, list2->head ) )
+ else if(isEqual(list1->tail, list2->head))
{
// Easy case
- PathElement* temp = list2->head->next ;
- delete list2->head ;
- list1->tail->next = temp ;
+ PathElement* temp = list2->head->next;
+ delete list2->head;
+ list1->tail->next = temp;
- PathList* nlist = new PathList ;
- nlist->length = list1->length + list2->length - 1 ;
- nlist->head = list1->head ;
- nlist->tail = list2->tail ;
- nlist->next = NULL ;
+ PathList* nlist = new PathList;
+ nlist->length = list1->length + list2->length - 1;
+ nlist->head = list1->head;
+ nlist->tail = list2->tail;
+ nlist->next = NULL;
- deletePath( head1, pre1, list1 ) ;
- deletePath( head2, pre2, list2 ) ;
+ deletePath(head1, pre1, list1);
+ deletePath(head2, pre2, list2);
- return nlist ;
+ return nlist;
}
- return NULL ;
+ return NULL;
}
-void Octree::deletePath( PathList*& head, PathList* pre, PathList*& curr )
+void Octree::deletePath(PathList*& head, PathList* pre, PathList*& curr)
{
- PathList* temp = curr ;
- curr = temp->next ;
- delete temp ;
+ PathList* temp = curr;
+ curr = temp->next;
+ delete temp;
- if ( pre == NULL )
+ if(pre == NULL)
{
- head = curr ;
+ head = curr;
}
else
{
- pre->next = curr ;
+ pre->next = curr;
}
}
-void Octree::printElement( PathElement* ele )
+void Octree::printElement(PathElement* ele)
{
- if ( ele != NULL )
+ if(ele != NULL)
{
- dc_printf( " (%d %d %d)", ele->pos[0], ele->pos[1], ele->pos[2] ) ;
+ dc_printf("(%d %d %d)", ele->pos[0], ele->pos[1], ele->pos[2]);
}
}
-void Octree::printPath( PathList* path )
+void Octree::printPath(PathList* path)
{
PathElement* n = path->head;
- int same = 0 ;
+ int same = 0;
#if DC_DEBUG
- int len = ( dimen >> maxDepth ) ;
+ int len =(dimen >> maxDepth);
#endif
- while ( n && ( same == 0 || n != path->head ) )
+ while(n &&(same == 0 || n != path->head))
{
- same ++ ;
- dc_printf( " (%d %d %d)", n->pos[0] / len, n->pos[1] / len, n->pos[2] / len ) ;
- n = n->next ;
+ same ++;
+ dc_printf("(%d %d %d)", n->pos[0] / len, n->pos[1] / len, n->pos[2] / len);
+ n = n->next;
}
- if ( n == path->head )
+ if(n == path->head)
{
- dc_printf(" Ring!\n") ;
+ dc_printf(" Ring!\n");
}
else
{
- dc_printf(" %p end!\n", n) ;
+ dc_printf(" %p end!\n", n);
}
}
-void Octree::printPath( PathElement* path )
+void Octree::printPath(PathElement* path)
{
PathElement *n = path;
- int same = 0 ;
+ int same = 0;
#if DC_DEBUG
- int len = ( dimen >> maxDepth ) ;
+ int len =(dimen >> maxDepth);
#endif
- while ( n && ( same == 0 || n != path ) )
+ while(n &&(same == 0 || n != path))
{
- same ++ ;
- dc_printf( " (%d %d %d)", n->pos[0] / len, n->pos[1] / len, n->pos[2] / len ) ;
- n = n->next ;
+ same ++;
+ dc_printf("(%d %d %d)", n->pos[0] / len, n->pos[1] / len, n->pos[2] / len);
+ n = n->next;
}
- if ( n == path )
+ if(n == path)
{
- dc_printf(" Ring!\n") ;
+ dc_printf(" Ring!\n");
}
else
{
- dc_printf(" %p end!\n", n) ;
+ dc_printf(" %p end!\n", n);
}
}
-void Octree::printPaths( PathList* path )
+void Octree::printPaths(PathList* path)
{
- PathList* iter = path ;
- int i = 0 ;
- while ( iter != NULL )
+ PathList* iter = path;
+ int i = 0;
+ while(iter != NULL)
{
- dc_printf("Path %d:\n", i) ;
- printPath( iter ) ;
- iter = iter->next ;
- i ++ ;
+ dc_printf("Path %d:\n", i);
+ printPath(iter);
+ iter = iter->next;
+ i ++;
}
}
-UCHAR* Octree::patch( UCHAR* node, int st[3], int len, PathList* rings )
+Node* Octree::patch(Node* newnode, int st[3], int len, PathList* rings)
{
#ifdef IN_DEBUG_MODE
dc_printf("Call to PATCH with rings: \n");
- printPaths( rings ) ;
+ printPaths(rings);
#endif
/* Do nothing but couting
- PathList* tlist = rings ;
- PathList* ttlist ;
- PathElement* telem, * ttelem ;
- while ( tlist!= NULL )
+ PathList* tlist = rings;
+ PathList* ttlist;
+ PathElement* telem, * ttelem;
+ while(tlist!= NULL)
{
- // printPath( tlist ) ;
- this->numRings ++ ;
- this->totRingLengths += tlist->length ;
- if ( tlist->length > this->maxRingLength )
+ // printPath(tlist);
+ numRings ++;
+ totRingLengths += tlist->length;
+ if(tlist->length > maxRingLength)
{
- this->maxRingLength = tlist->length ;
+ maxRingLength = tlist->length;
}
- ttlist = tlist ;
- tlist = tlist->next ;
+ ttlist = tlist;
+ tlist = tlist->next;
}
- return node ;
+ return node;
*/
/* Pass onto separate calls in each direction */
- UCHAR* newnode = node ;
- if ( len == mindimen )
+ if(len == mindimen)
{
- dc_printf("Error! should have no list by now.\n") ;
- exit(0) ;
+ dc_printf("Error! should have no list by now.\n");
+ exit(0);
}
// YZ plane
- PathList* xlists[2] ;
- newnode = patchSplit( newnode, st, len, rings, 0, xlists[0], xlists[1] ) ;
+ PathList* xlists[2];
+ newnode = patchSplit(newnode, st, len, rings, 0, xlists[0], xlists[1]);
// XZ plane
- PathList* ylists[4] ;
- newnode = patchSplit( newnode, st, len, xlists[0], 1, ylists[0], ylists[1] ) ;
- newnode = patchSplit( newnode, st, len, xlists[1], 1, ylists[2], ylists[3] ) ;
+ PathList* ylists[4];
+ newnode = patchSplit(newnode, st, len, xlists[0], 1, ylists[0], ylists[1]);
+ newnode = patchSplit(newnode, st, len, xlists[1], 1, ylists[2], ylists[3]);
// XY plane
- PathList* zlists[8] ;
- newnode = patchSplit( newnode, st, len, ylists[0], 2, zlists[0], zlists[1] ) ;
- newnode = patchSplit( newnode, st, len, ylists[1], 2, zlists[2], zlists[3] ) ;
- newnode = patchSplit( newnode, st, len, ylists[2], 2, zlists[4], zlists[5] ) ;
- newnode = patchSplit( newnode, st, len, ylists[3], 2, zlists[6], zlists[7] ) ;
+ PathList* zlists[8];
+ newnode = patchSplit(newnode, st, len, ylists[0], 2, zlists[0], zlists[1]);
+ newnode = patchSplit(newnode, st, len, ylists[1], 2, zlists[2], zlists[3]);
+ newnode = patchSplit(newnode, st, len, ylists[2], 2, zlists[4], zlists[5]);
+ newnode = patchSplit(newnode, st, len, ylists[3], 2, zlists[6], zlists[7]);
// Recur
- len >>= 1 ;
- int count = 0 ;
- for ( int i = 0 ; i < 8 ; i ++ )
+ len >>= 1;
+ int count = 0;
+ for(int i = 0; i < 8; i ++)
{
- if ( zlists[i] != NULL )
+ if(zlists[i] != NULL)
{
- int nori[3] = {
+ int nori[3] = {
st[0] + len * vertmap[i][0] ,
st[1] + len * vertmap[i][1] ,
- st[2] + len * vertmap[i][2] } ;
- patch( getChild( newnode , count ), nori, len, zlists[i] ) ;
+ st[2] + len * vertmap[i][2]};
+ patch(getChild(&newnode->internal , count), nori, len, zlists[i]);
}
- if ( hasChild( newnode, i ) )
+ if(hasChild(&newnode->internal, i))
{
- count ++ ;
+ count ++;
}
}
#ifdef IN_DEBUG_MODE
- dc_printf("Return from PATCH\n") ;
+ dc_printf("Return from PATCH\n");
#endif
- return newnode ;
+ return newnode;
}
-UCHAR* Octree::patchSplit( UCHAR* node, int st[3], int len, PathList* rings, int dir, PathList*& nrings1, PathList*& nrings2 )
+Node* Octree::patchSplit(Node* newnode, int st[3], int len, PathList* rings,
+ int dir, PathList*& nrings1, PathList*& nrings2)
{
#ifdef IN_DEBUG_MODE
dc_printf("Call to PATCHSPLIT with direction %d and rings: \n", dir);
- printPaths( rings ) ;
+ printPaths(rings);
#endif
- UCHAR* newnode = node ;
- nrings1 = NULL ;
- nrings2 = NULL ;
- PathList* tmp ;
- while ( rings != NULL )
+ nrings1 = NULL;
+ nrings2 = NULL;
+ PathList* tmp;
+ while(rings != NULL)
{
// Process this ring
- newnode = patchSplitSingle( newnode, st, len, rings->head, dir, nrings1, nrings2 ) ;
+ newnode = patchSplitSingle(newnode, st, len, rings->head, dir, nrings1, nrings2);
// Delete this ring from the group
- tmp = rings ;
- rings = rings->next ;
- delete tmp ;
+ tmp = rings;
+ rings = rings->next;
+ delete tmp;
}
#ifdef IN_DEBUG_MODE
dc_printf("Return from PATCHSPLIT with \n");
- dc_printf("Rings gourp 1:\n") ;
- printPaths( nrings1 ) ;
- dc_printf("Rings group 2:\n") ;
- printPaths( nrings2 ) ;
+ dc_printf("Rings gourp 1:\n");
+ printPaths(nrings1);
+ dc_printf("Rings group 2:\n");
+ printPaths(nrings2);
#endif
- return newnode ;
+ return newnode;
}
-UCHAR* Octree::patchSplitSingle( UCHAR* node, int st[3], int len, PathElement* head, int dir, PathList*& nrings1, PathList*& nrings2 )
+Node* Octree::patchSplitSingle(Node* newnode, int st[3], int len, PathElement* head, int dir, PathList*& nrings1, PathList*& nrings2)
{
#ifdef IN_DEBUG_MODE
- dc_printf("Call to PATCHSPLITSINGLE with direction %d and path: \n", dir );
- printPath( head ) ;
+ dc_printf("Call to PATCHSPLITSINGLE with direction %d and path: \n", dir);
+ printPath(head);
#endif
- UCHAR* newnode = node ;
-
- if ( head == NULL )
+ if(head == NULL)
{
#ifdef IN_DEBUG_MODE
- dc_printf("Return from PATCHSPLITSINGLE with head==NULL.\n") ;
+ dc_printf("Return from PATCHSPLITSINGLE with head==NULL.\n");
#endif
return newnode;
}
else
{
- // printPath( head ) ;
+ // printPath(head);
}
// Walk along the ring to find pair of intersections
- PathElement* pre1 = NULL ;
- PathElement* pre2 = NULL ;
- int side = findPair ( head, st[ dir ] + len / 2 , dir, pre1, pre2 ) ;
+ PathElement* pre1 = NULL;
+ PathElement* pre2 = NULL;
+ int side = findPair(head, st[dir] + len / 2 , dir, pre1, pre2);
/*
- if ( pre1 == pre2 )
+ if(pre1 == pre2)
{
- int edgelen = ( dimen >> maxDepth ) ;
- dc_printf("Location: %d %d %d Direction: %d Reso: %d\n", st[0]/edgelen, st[1]/edgelen, st[2]/edgelen, dir, len/edgelen) ;
- printPath( head ) ;
- exit( 0 ) ;
+ int edgelen =(dimen >> maxDepth);
+ dc_printf("Location: %d %d %d Direction: %d Reso: %d\n", st[0]/edgelen, st[1]/edgelen, st[2]/edgelen, dir, len/edgelen);
+ printPath(head);
+ exit(0);
}
*/
- if ( side )
+ if(side)
{
// Entirely on one side
- PathList* nring = new PathList( ) ;
- nring->head = head ;
+ PathList* nring = new PathList();
+ nring->head = head;
- if ( side == -1 )
+ if(side == -1)
{
- nring->next = nrings1 ;
- nrings1 = nring ;
+ nring->next = nrings1;
+ nrings1 = nring;
}
else
{
- nring->next = nrings2 ;
- nrings2 = nring ;
+ nring->next = nrings2;
+ nrings2 = nring;
}
}
else
{
// Break into two parts
- PathElement* nxt1 = pre1->next ;
- PathElement* nxt2 = pre2->next ;
- pre1->next = nxt2 ;
- pre2->next = nxt1 ;
+ PathElement* nxt1 = pre1->next;
+ PathElement* nxt2 = pre2->next;
+ pre1->next = nxt2;
+ pre2->next = nxt1;
- newnode = connectFace( newnode, st, len, dir, pre1, pre2 ) ;
+ newnode = connectFace(newnode, st, len, dir, pre1, pre2);
- if ( isEqual( pre1, pre1->next ) )
+ if(isEqual(pre1, pre1->next))
{
- if ( pre1 == pre1->next )
+ if(pre1 == pre1->next)
{
- delete pre1 ;
- pre1 = NULL ;
+ delete pre1;
+ pre1 = NULL;
}
else
{
- PathElement* temp = pre1->next ;
- pre1->next = temp->next ;
- delete temp ;
+ PathElement* temp = pre1->next;
+ pre1->next = temp->next;
+ delete temp;
}
}
- if ( isEqual( pre2, pre2->next ) )
+ if(isEqual(pre2, pre2->next))
{
- if ( pre2 == pre2->next )
+ if(pre2 == pre2->next)
{
- delete pre2 ;
- pre2 = NULL ;
+ delete pre2;
+ pre2 = NULL;
}
else
{
- PathElement* temp = pre2->next ;
- pre2->next = temp->next ;
- delete temp ;
+ PathElement* temp = pre2->next;
+ pre2->next = temp->next;
+ delete temp;
}
}
- compressRing ( pre1 ) ;
- compressRing ( pre2 ) ;
+ compressRing(pre1);
+ compressRing(pre2);
// Recur
- newnode = patchSplitSingle( newnode, st, len, pre1, dir, nrings1, nrings2 ) ;
- newnode = patchSplitSingle( newnode, st, len, pre2, dir, nrings1, nrings2 ) ;
+ newnode = patchSplitSingle(newnode, st, len, pre1, dir, nrings1, nrings2);
+ newnode = patchSplitSingle(newnode, st, len, pre2, dir, nrings1, nrings2);
}
#ifdef IN_DEBUG_MODE
dc_printf("Return from PATCHSPLITSINGLE with \n");
- dc_printf("Rings gourp 1:\n") ;
- printPaths( nrings1 ) ;
- dc_printf("Rings group 2:\n") ;
- printPaths( nrings2 ) ;
+ dc_printf("Rings gourp 1:\n");
+ printPaths(nrings1);
+ dc_printf("Rings group 2:\n");
+ printPaths(nrings2);
#endif
- return newnode ;
+ return newnode;
}
-UCHAR* Octree::connectFace( UCHAR* node, int st[3], int len, int dir, PathElement* f1, PathElement* f2 )
+Node* Octree::connectFace(Node* newnode, int st[3], int len, int dir,
+ PathElement* f1, PathElement* f2)
{
#ifdef IN_DEBUG_MODE
- dc_printf("Call to CONNECTFACE with direction %d and length %d path: \n", dir, len );
- dc_printf("Path (low side): \n" ) ;
- printPath( f1 ) ;
-// checkPath( f1 ) ;
- dc_printf("Path (high side): \n" ) ;
- printPath( f2 ) ;
-// checkPath( f2 ) ;
+ dc_printf("Call to CONNECTFACE with direction %d and length %d path: \n", dir, len);
+ dc_printf("Path(low side): \n");
+ printPath(f1);
+// checkPath(f1);
+ dc_printf("Path(high side): \n");
+ printPath(f2);
+// checkPath(f2);
#endif
- UCHAR* newnode = node ;
-
// Setup 2D
- int pos = st[ dir ] + len / 2 ;
- int xdir = ( dir + 1 ) % 3 ;
- int ydir = ( dir + 2 ) % 3 ;
+ int pos = st[dir] + len / 2;
+ int xdir =(dir + 1) % 3;
+ int ydir =(dir + 2) % 3;
// Use existing intersections on f1 and f2
- int x1, y1, x2, y2 ;
- float p1, q1, p2, q2 ;
+ int x1, y1, x2, y2;
+ float p1, q1, p2, q2;
- getFacePoint( f2->next, dir, x1, y1, p1, q1 ) ;
- getFacePoint( f2, dir, x2, y2, p2, q2 ) ;
+ getFacePoint(f2->next, dir, x1, y1, p1, q1);
+ getFacePoint(f2, dir, x2, y2, p2, q2);
- float dx = x2 + p2 - x1 - p1 ;
- float dy = y2 + q2 - y1 - q1 ;
+ float dx = x2 + p2 - x1 - p1;
+ float dy = y2 + q2 - y1 - q1;
// Do adapted Bresenham line drawing
- float rx = p1, ry = q1 ;
- int incx = 1, incy = 1 ;
- int lx = x1, ly = y1 ;
- int hx = x2, hy = y2 ;
- int choice ;
- if ( x2 < x1 )
+ float rx = p1, ry = q1;
+ int incx = 1, incy = 1;
+ int lx = x1, ly = y1;
+ int hx = x2, hy = y2;
+ int choice;
+ if(x2 < x1)
{
- incx = -1 ;
- rx = 1 - rx ;
- lx = x2 ;
- hx = x1 ;
+ incx = -1;
+ rx = 1 - rx;
+ lx = x2;
+ hx = x1;
}
- if ( y2 < y1 )
+ if(y2 < y1)
{
- incy = -1 ;
- ry = 1 - ry ;
- ly = y2 ;
- hy = y1 ;
+ incy = -1;
+ ry = 1 - ry;
+ ly = y2;
+ hy = y1;
}
- float sx = dx * incx ;
- float sy = dy * incy ;
+ float sx = dx * incx;
+ float sy = dy * incy;
- int ori[3] ;
- ori[ dir ] = pos / mindimen ;
- ori[ xdir ] = x1 ;
- ori[ ydir ] = y1 ;
- int walkdir ;
- int inc ;
- float alpha ;
-
- PathElement* curEleN = f1 ;
- PathElement* curEleP = f2->next ;
- UCHAR *nodeN = NULL, *nodeP = NULL ;
- UCHAR *curN = locateLeaf( newnode, len, f1->pos ) ;
- UCHAR *curP = locateLeaf( newnode, len, f2->next->pos ) ;
- if ( curN == NULL || curP == NULL )
- {
- exit(0) ;
- }
- int stN[3], stP[3] ;
- int lenN, lenP ;
+ int ori[3];
+ ori[dir] = pos / mindimen;
+ ori[xdir] = x1;
+ ori[ydir] = y1;
+ int walkdir;
+ int inc;
+ float alpha;
+
+ PathElement* curEleN = f1;
+ PathElement* curEleP = f2->next;
+ Node *nodeN = NULL, *nodeP = NULL;
+ LeafNode *curN = locateLeaf(&newnode->internal, len, f1->pos);
+ LeafNode *curP = locateLeaf(&newnode->internal, len, f2->next->pos);
+ if(curN == NULL || curP == NULL)
+ {
+ exit(0);
+ }
+ int stN[3], stP[3];
+ int lenN, lenP;
/* Unused code, leaving for posterity
- float stpt[3], edpt[3] ;
- stpt[ dir ] = edpt[ dir ] = (float) pos ;
- stpt[ xdir ] = ( x1 + p1 ) * mindimen ;
- stpt[ ydir ] = ( y1 + q1 ) * mindimen ;
- edpt[ xdir ] = ( x2 + p2 ) * mindimen ;
- edpt[ ydir ] = ( y2 + q2 ) * mindimen ;
+ float stpt[3], edpt[3];
+ stpt[dir] = edpt[dir] =(float) pos;
+ stpt[xdir] =(x1 + p1) * mindimen;
+ stpt[ydir] =(y1 + q1) * mindimen;
+ edpt[xdir] =(x2 + p2) * mindimen;
+ edpt[ydir] =(y2 + q2) * mindimen;
*/
- while( ori[ xdir ] != x2 || ori[ ydir ] != y2 )
+ while(ori[xdir] != x2 || ori[ydir] != y2)
{
- int next ;
- if ( sy * (1 - rx) > sx * (1 - ry) )
+ int next;
+ if(sy *(1 - rx) > sx *(1 - ry))
{
- choice = 1 ;
- next = ori[ ydir ] + incy ;
- if ( next < ly || next > hy )
+ choice = 1;
+ next = ori[ydir] + incy;
+ if(next < ly || next > hy)
{
- choice = 4 ;
- next = ori[ xdir ] + incx ;
+ choice = 4;
+ next = ori[xdir] + incx;
}
}
else
{
- choice = 2 ;
- next = ori[ xdir ] + incx ;
- if ( next < lx || next > hx )
+ choice = 2;
+ next = ori[xdir] + incx;
+ if(next < lx || next > hx)
{
- choice = 3 ;
- next = ori[ ydir ] + incy ;
+ choice = 3;
+ next = ori[ydir] + incy;
}
}
- if ( choice & 1 )
+ if(choice & 1)
{
- ori[ ydir ] = next ;
- if ( choice == 1 )
+ ori[ydir] = next;
+ if(choice == 1)
{
- rx += ( sy == 0 ? 0 : (1 - ry) * sx / sy ) ;
- ry = 0 ;
+ rx +=(sy == 0 ? 0 :(1 - ry) * sx / sy );
+ ry = 0;
}
- walkdir = 2 ;
- inc = incy ;
- alpha = x2 < x1 ? 1 - rx : rx ;
+ walkdir = 2;
+ inc = incy;
+ alpha = x2 < x1 ? 1 - rx : rx;
}
else
{
- ori[ xdir ] = next ;
- if ( choice == 2 )
+ ori[xdir] = next;
+ if(choice == 2)
{
- ry += ( sx == 0 ? 0 : (1 - rx) * sy / sx ) ;
- rx = 0 ;
+ ry +=(sx == 0 ? 0 :(1 - rx) * sy / sx);
+ rx = 0;
}
- walkdir = 1 ;
- inc = incx ;
- alpha = y2 < y1 ? 1 - ry : ry ;
+ walkdir = 1;
+ inc = incx;
+ alpha = y2 < y1 ? 1 - ry : ry;
}
// Get the exact location of the marcher
- int nori[3] = { ori[0] * mindimen, ori[1] * mindimen, ori[2] * mindimen } ;
- float spt[3] = { (float) nori[0], (float) nori[1], (float) nori[2] } ;
- spt[ ( dir + ( 3 - walkdir ) ) % 3 ] += alpha * mindimen ;
- if ( inc < 0 )
+ int nori[3] = {ori[0] * mindimen, ori[1] * mindimen, ori[2] * mindimen};
+ float spt[3] = {(float) nori[0],(float) nori[1],(float) nori[2]};
+ spt[(dir +(3 - walkdir)) % 3] += alpha * mindimen;
+ if(inc < 0)
{
- spt[ ( dir + walkdir ) % 3 ] += mindimen ;
+ spt[(dir + walkdir) % 3] += mindimen;
}
- // dc_printf("new x,y: %d %d\n", ori[ xdir ] / edgelen, ori[ ydir ] / edgelen ) ;
- // dc_printf("nori: %d %d %d alpha: %f walkdir: %d\n", nori[0], nori[1], nori[2], alpha, walkdir ) ;
- // dc_printf("%f %f %f\n", spt[0], spt[1], spt[2] ) ;
+ // dc_printf("new x,y: %d %d\n", ori[xdir] / edgelen, ori[ydir] / edgelen);
+ // dc_printf("nori: %d %d %d alpha: %f walkdir: %d\n", nori[0], nori[1], nori[2], alpha, walkdir);
+ // dc_printf("%f %f %f\n", spt[0], spt[1], spt[2]);
// Locate the current cells on both sides
- newnode = locateCell( newnode, st, len, nori, dir, 1, nodeN, stN, lenN ) ;
- newnode = locateCell( newnode, st, len, nori, dir, 0, nodeP, stP, lenP ) ;
+ newnode = locateCell(&newnode->internal, st, len, nori, dir, 1, nodeN, stN, lenN);
+ newnode = locateCell(&newnode->internal, st, len, nori, dir, 0, nodeP, stP, lenP);
- updateParent( newnode, len, st ) ;
+ updateParent(&newnode->internal, len, st);
- int flag = 0 ;
+ int flag = 0;
// Add the cells to the rings and fill in the patch
- PathElement* newEleN ;
- if ( curEleN->pos[0] != stN[0] || curEleN->pos[1] != stN[1] || curEleN->pos[2] != stN[2] )
+ PathElement* newEleN;
+ if(curEleN->pos[0] != stN[0] || curEleN->pos[1] != stN[1] || curEleN->pos[2] != stN[2])
{
- if ( curEleN->next->pos[0] != stN[0] || curEleN->next->pos[1] != stN[1] || curEleN->next->pos[2] != stN[2] )
+ if(curEleN->next->pos[0] != stN[0] || curEleN->next->pos[1] != stN[1] || curEleN->next->pos[2] != stN[2])
{
- newEleN = new PathElement ;
- newEleN->next = curEleN->next ;
- newEleN->pos[0] = stN[0] ;
- newEleN->pos[1] = stN[1] ;
- newEleN->pos[2] = stN[2] ;
+ newEleN = new PathElement;
+ newEleN->next = curEleN->next;
+ newEleN->pos[0] = stN[0];
+ newEleN->pos[1] = stN[1];
+ newEleN->pos[2] = stN[2];
- curEleN->next = newEleN ;
+ curEleN->next = newEleN;
}
else
{
- newEleN = curEleN->next ;
+ newEleN = curEleN->next;
}
- curN = patchAdjacent( newnode, len, curEleN->pos, curN, newEleN->pos, nodeN, walkdir, inc, dir, 1, alpha ) ;
+ curN = patchAdjacent(&newnode->internal, len, curEleN->pos, curN,
+ newEleN->pos, (LeafNode*)nodeN, walkdir,
+ inc, dir, 1, alpha);
- curEleN = newEleN ;
- flag ++ ;
+ curEleN = newEleN;
+ flag ++;
}
- PathElement* newEleP ;
- if ( curEleP->pos[0] != stP[0] || curEleP->pos[1] != stP[1] || curEleP->pos[2] != stP[2] )
+ PathElement* newEleP;
+ if(curEleP->pos[0] != stP[0] || curEleP->pos[1] != stP[1] || curEleP->pos[2] != stP[2])
{
- if ( f2->pos[0] != stP[0] || f2->pos[1] != stP[1] || f2->pos[2] != stP[2] )
+ if(f2->pos[0] != stP[0] || f2->pos[1] != stP[1] || f2->pos[2] != stP[2])
{
- newEleP = new PathElement ;
- newEleP->next = curEleP ;
- newEleP->pos[0] = stP[0] ;
- newEleP->pos[1] = stP[1] ;
- newEleP->pos[2] = stP[2] ;
+ newEleP = new PathElement;
+ newEleP->next = curEleP;
+ newEleP->pos[0] = stP[0];
+ newEleP->pos[1] = stP[1];
+ newEleP->pos[2] = stP[2];
- f2->next = newEleP ;
+ f2->next = newEleP;
}
else
{
- newEleP = f2 ;
+ newEleP = f2;
}
- curP = patchAdjacent( newnode, len, curEleP->pos, curP, newEleP->pos, nodeP, walkdir, inc, dir, 0, alpha ) ;
+ curP = patchAdjacent(&newnode->internal, len, curEleP->pos, curP,
+ newEleP->pos, (LeafNode*)nodeP, walkdir,
+ inc, dir, 0, alpha);
- curEleP = newEleP ;
- flag ++ ;
+ curEleP = newEleP;
+ flag ++;
}
/*
- if ( flag == 0 )
+ if(flag == 0)
{
- dc_printf("error: non-synchronized patching! at \n") ;
+ dc_printf("error: non-synchronized patching! at \n");
}
*/
}
#ifdef IN_DEBUG_MODE
dc_printf("Return from CONNECTFACE with \n");
- dc_printf("Path (low side):\n") ;
- printPath( f1 ) ;
- checkPath( f1 ) ;
- dc_printf("Path (high side):\n") ;
- printPath( f2 ) ;
- checkPath( f2 ) ;
+ dc_printf("Path(low side):\n");
+ printPath(f1);
+ checkPath(f1);
+ dc_printf("Path(high side):\n");
+ printPath(f2);
+ checkPath(f2);
#endif
- return newnode ;
+ return newnode;
}
-UCHAR* Octree::patchAdjacent( UCHAR* node, int len, int st1[3], UCHAR* leaf1, int st2[3], UCHAR* leaf2, int walkdir, int inc, int dir, int side, float alpha )
+LeafNode* Octree::patchAdjacent(InternalNode* node, int len, int st1[3],
+ LeafNode* leaf1, int st2[3], LeafNode* leaf2,
+ int walkdir, int inc, int dir, int side,
+ float alpha)
{
#ifdef IN_DEBUG_MODE
- dc_printf("Before patching.\n") ;
- printInfo( st1 ) ;
- printInfo( st2 ) ;
- dc_printf("-----------------%d %d %d ; %d %d %d\n", st1[0], st2[1], st1[2], st2[0], st2[1], st2[2] ) ;
+ dc_printf("Before patching.\n");
+ printInfo(st1);
+ printInfo(st2);
+ dc_printf("-----------------%d %d %d; %d %d %d\n", st1[0], st2[1], st1[2], st2[0], st2[1], st2[2]);
#endif
// Get edge index on each leaf
- int edgedir = ( dir + ( 3 - walkdir ) ) % 3 ;
- int incdir = ( dir + walkdir ) % 3 ;
- int ind1 = ( edgedir == 1 ? ( dir + 3 - edgedir ) % 3 - 1 : 2 - ( dir + 3 - edgedir ) % 3 ) ;
- int ind2 = ( edgedir == 1 ? ( incdir + 3 - edgedir ) % 3 - 1 : 2 - ( incdir + 3 - edgedir ) % 3 ) ;
+ int edgedir =(dir +(3 - walkdir)) % 3;
+ int incdir =(dir + walkdir) % 3;
+ int ind1 =(edgedir == 1 ?(dir + 3 - edgedir) % 3 - 1 : 2 -(dir + 3 - edgedir) % 3);
+ int ind2 =(edgedir == 1 ?(incdir + 3 - edgedir) % 3 - 1 : 2 -(incdir + 3 - edgedir) % 3);
- int eind1 = ( ( edgedir << 2 ) | ( side << ind1 ) | ( ( inc > 0 ? 1 : 0 ) << ind2 ) ) ;
- int eind2 = ( ( edgedir << 2 ) | ( side << ind1 ) | ( ( inc > 0 ? 0 : 1 ) << ind2 ) ) ;
+ int eind1 =((edgedir << 2) |(side << ind1) |((inc > 0 ? 1 : 0) << ind2));
+ int eind2 =((edgedir << 2) |(side << ind1) |((inc > 0 ? 0 : 1) << ind2));
#ifdef IN_DEBUG_MODE
- dc_printf("Index 1: %d Alpha 1: %f Index 2: %d Alpha 2: %f\n", eind1, alpha, eind2, alpha ) ;
+ dc_printf("Index 1: %d Alpha 1: %f Index 2: %d Alpha 2: %f\n", eind1, alpha, eind2, alpha);
/*
- if ( alpha < 0 || alpha > 1 )
+ if(alpha < 0 || alpha > 1)
{
- dc_printf("Index 1: %d Alpha 1: %f Index 2: %d Alpha 2: %f\n", eind1, alpha, eind2, alpha ) ;
- printInfo( st1 ) ;
- printInfo( st2 ) ;
+ dc_printf("Index 1: %d Alpha 1: %f Index 2: %d Alpha 2: %f\n", eind1, alpha, eind2, alpha);
+ printInfo(st1);
+ printInfo(st2);
}
*/
#endif
// Flip edge parity
- UCHAR* nleaf1 = flipEdge( leaf1, eind1, alpha ) ;
- UCHAR* nleaf2 = flipEdge( leaf2, eind2, alpha ) ;
+ LeafNode* nleaf1 = flipEdge(leaf1, eind1, alpha);
+ LeafNode* nleaf2 = flipEdge(leaf2, eind2, alpha);
// Update parent link
- updateParent( node, len, st1, nleaf1 ) ;
- updateParent( node, len, st2, nleaf2 ) ;
- // updateParent( nleaf1, mindimen, st1 ) ;
- // updateParent( nleaf2, mindimen, st2 ) ;
+ updateParent(node, len, st1, nleaf1);
+ updateParent(node, len, st2, nleaf2);
+ // updateParent(nleaf1, mindimen, st1);
+ // updateParent(nleaf2, mindimen, st2);
/*
- float m[3] ;
- dc_printf("Adding new point: %f %f %f\n", spt[0], spt[1], spt[2] ) ;
- getMinimizer( leaf1, m ) ;
- dc_printf("Cell %d now has minimizer %f %f %f\n", leaf1, m[0], m[1], m[2] ) ;
- getMinimizer( leaf2, m ) ;
- dc_printf("Cell %d now has minimizer %f %f %f\n", leaf2, m[0], m[1], m[2] ) ;
+ float m[3];
+ dc_printf("Adding new point: %f %f %f\n", spt[0], spt[1], spt[2]);
+ getMinimizer(leaf1, m);
+ dc_printf("Cell %d now has minimizer %f %f %f\n", leaf1, m[0], m[1], m[2]);
+ getMinimizer(leaf2, m);
+ dc_printf("Cell %d now has minimizer %f %f %f\n", leaf2, m[0], m[1], m[2]);
*/
#ifdef IN_DEBUG_MODE
- dc_printf("After patching.\n") ;
- printInfo( st1 ) ;
- printInfo( st2 ) ;
+ dc_printf("After patching.\n");
+ printInfo(st1);
+ printInfo(st2);
#endif
- return nleaf2 ;
+ return nleaf2;
}
-UCHAR* Octree::locateCell( UCHAR* node, int st[3], int len, int ori[3], int dir, int side, UCHAR*& rleaf, int rst[3], int& rlen )
+Node* Octree::locateCell(InternalNode* node, int st[3], int len, int ori[3], int dir, int side, Node*& rleaf, int rst[3], int& rlen)
{
#ifdef IN_DEBUG_MODE
- // dc_printf("Call to LOCATECELL with node ") ;
- // printNode( node ) ;
+ // dc_printf("Call to LOCATECELL with node ");
+ // printNode(node);
#endif
- UCHAR* newnode = node ;
- int i ;
- len >>= 1 ;
- int ind = 0 ;
- for ( i = 0 ; i < 3 ; i ++ )
+
+ int i;
+ len >>= 1;
+ int ind = 0;
+ for(i = 0; i < 3; i ++)
{
- ind <<= 1 ;
- if ( i == dir && side == 1 )
+ ind <<= 1;
+ if(i == dir && side == 1)
{
- ind |= ( ori[ i ] <= ( st[ i ] + len ) ? 0 : 1 ) ;
+ ind |=(ori[i] <=(st[i] + len) ? 0 : 1);
}
else
{
- ind |= ( ori[ i ] < ( st[ i ] + len ) ? 0 : 1 ) ;
+ ind |=(ori[i] <(st[i] + len) ? 0 : 1);
}
}
#ifdef IN_DEBUG_MODE
- // dc_printf("In LOCATECELL index of ori (%d %d %d) with dir %d side %d in st (%d %d %d, %d) is: %d\n",
- // ori[0], ori[1], ori[2], dir, side, st[0], st[1], st[2], len, ind ) ;
+ // dc_printf("In LOCATECELL index of ori(%d %d %d) with dir %d side %d in st(%d %d %d, %d) is: %d\n",
+ // ori[0], ori[1], ori[2], dir, side, st[0], st[1], st[2], len, ind);
#endif
- rst[0] = st[0] + vertmap[ ind ][ 0 ] * len ;
- rst[1] = st[1] + vertmap[ ind ][ 1 ] * len ;
- rst[2] = st[2] + vertmap[ ind ][ 2 ] * len ;
+ rst[0] = st[0] + vertmap[ind][0] * len;
+ rst[1] = st[1] + vertmap[ind][1] * len;
+ rst[2] = st[2] + vertmap[ind][2] * len;
- if ( hasChild( newnode, ind ) )
+ if(hasChild(node, ind))
{
- int count = getChildCount( newnode, ind ) ;
- UCHAR* chd = getChild( newnode, count ) ;
- if ( isLeaf( newnode, ind ) )
+ int count = getChildCount(node, ind);
+ Node* chd = getChild(node, count);
+ if(isLeaf(node, ind))
{
- rleaf = chd ;
- rlen = len ;
+ rleaf = chd;
+ rlen = len;
}
else
{
// Recur
- setChild( newnode, count, locateCell( chd, rst, len, ori, dir, side, rleaf, rst, rlen ) ) ;
+ setChild(node, count, locateCell(&chd->internal, rst, len, ori, dir, side, rleaf, rst, rlen));
}
}
else
{
// Create a new child here
- if ( len == this->mindimen )
+ if(len == mindimen)
{
- UCHAR* chd = createLeaf( 0 ) ;
- newnode = addChild( newnode, ind, chd, 1 ) ;
- rleaf = chd ;
- rlen = len ;
+ LeafNode* chd = createLeaf(0);
+ node = addChild(node, ind, (Node*)chd, 1);
+ rleaf = (Node*)chd;
+ rlen = len;
}
else
{
// Subdivide the empty cube
- UCHAR* chd = createInternal( 0 ) ;
- newnode = addChild( newnode, ind, locateCell( chd, rst, len, ori, dir, side, rleaf, rst, rlen ), 0 ) ;
+ InternalNode* chd = createInternal(0);
+ node = addChild(node, ind,
+ locateCell(chd, rst, len, ori, dir, side, rleaf, rst, rlen), 0);
}
}
#ifdef IN_DEBUG_MODE
- // dc_printf("Return from LOCATECELL with node ") ;
- // printNode( newnode ) ;
+ // dc_printf("Return from LOCATECELL with node ");
+ // printNode(newnode);
#endif
- return newnode ;
+ return (Node*)node;
}
-void Octree::checkElement( PathElement* ele )
+void Octree::checkElement(PathElement* ele)
{
/*
- if ( ele != NULL && locateLeafCheck( ele->pos ) != ele->node )
+ if(ele != NULL && locateLeafCheck(ele->pos) != ele->node)
{
dc_printf("Screwed! at pos: %d %d %d\n", ele->pos[0]>>minshift, ele->pos[1]>>minshift, ele->pos[2]>>minshift);
- exit( 0 ) ;
+ exit(0);
}
*/
}
-void Octree::checkPath( PathElement* path )
+void Octree::checkPath(PathElement* path)
{
- PathElement *n = path ;
- int same = 0 ;
- while ( n && ( same == 0 || n != path ) )
+ PathElement *n = path;
+ int same = 0;
+ while(n &&(same == 0 || n != path))
{
- same ++ ;
- checkElement( n ) ;
- n = n->next ;
+ same ++;
+ checkElement(n);
+ n = n->next;
}
}
-void Octree::testFacePoint( PathElement* e1, PathElement* e2 )
+void Octree::testFacePoint(PathElement* e1, PathElement* e2)
{
- int i ;
- PathElement * e = NULL ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int i;
+ PathElement * e = NULL;
+ for(i = 0; i < 3; i ++)
{
- if ( e1->pos[i] != e2->pos[i] )
+ if(e1->pos[i] != e2->pos[i])
{
- if ( e1->pos[i] < e2->pos[i] )
+ if(e1->pos[i] < e2->pos[i])
{
- e = e2 ;
+ e = e2;
}
else
{
- e = e1 ;
+ e = e1;
}
- break ;
+ break;
}
}
- int x, y ;
- float p, q ;
- dc_printf("Test.") ;
- getFacePoint( e, i, x, y, p, q ) ;
+ int x, y;
+ float p, q;
+ dc_printf("Test.");
+ getFacePoint(e, i, x, y, p, q);
}
-void Octree::getFacePoint( PathElement* leaf, int dir, int& x, int& y, float& p, float& q )
+void Octree::getFacePoint(PathElement* leaf, int dir, int& x, int& y, float& p, float& q)
{
// Find average intersections
- float avg[3] = {0, 0, 0} ;
- float off[3] ;
- int num = 0, num2 = 0 ;
+ float avg[3] = {0, 0, 0};
+ float off[3];
+ int num = 0, num2 = 0;
- UCHAR* leafnode = locateLeaf( leaf->pos ) ;
- for ( int i = 0 ; i < 4 ; i ++ )
+ LeafNode* leafnode = locateLeaf(leaf->pos);
+ for(int i = 0; i < 4; i ++)
{
- int edgeind = faceMap[ dir * 2 ][ i ] ;
- int nst[3] ;
- for ( int j = 0 ; j < 3 ; j ++ )
+ int edgeind = faceMap[dir * 2][i];
+ int nst[3];
+ for(int j = 0; j < 3; j ++)
{
- nst[j] = leaf->pos[j] + mindimen * vertmap[ edgemap[ edgeind][ 0 ] ][ j ] ;
+ nst[j] = leaf->pos[j] + mindimen * vertmap[edgemap[edgeind][0]][j];
}
- if ( getEdgeIntersectionByIndex( nst, edgeind / 4, off, 1 ) )
+ if(getEdgeIntersectionByIndex(nst, edgeind / 4, off, 1))
{
- avg[0] += off[0] ;
- avg[1] += off[1] ;
- avg[2] += off[2] ;
- num ++ ;
+ avg[0] += off[0];
+ avg[1] += off[1];
+ avg[2] += off[2];
+ num ++;
}
- if ( getEdgeParity( leafnode, edgeind ) )
+ if(getEdgeParity(leafnode, edgeind))
{
- num2 ++ ;
+ num2 ++;
}
}
- if ( num == 0 )
+ if(num == 0)
{
dc_printf("Wrong! dir: %d pos: %d %d %d num: %d\n", dir, leaf->pos[0]>>minshift, leaf->pos[1]>>minshift, leaf->pos[2]>>minshift, num2);
- avg[0] = (float) leaf->pos[0] ;
- avg[1] = (float) leaf->pos[1] ;
- avg[2] = (float) leaf->pos[2] ;
+ avg[0] =(float) leaf->pos[0];
+ avg[1] =(float) leaf->pos[1];
+ avg[2] =(float) leaf->pos[2];
}
else
{
- avg[0] /= num ;
- avg[1] /= num ;
- avg[2] /= num ;
+ avg[0] /= num;
+ avg[1] /= num;
+ avg[2] /= num;
- //avg[0] = (float) leaf->pos[0];
- //avg[1] = (float) leaf->pos[1];
- //avg[2] = (float) leaf->pos[2];
+ //avg[0] =(float) leaf->pos[0];
+ //avg[1] =(float) leaf->pos[1];
+ //avg[2] =(float) leaf->pos[2];
}
- int xdir = ( dir + 1 ) % 3 ;
- int ydir = ( dir + 2 ) % 3 ;
+ int xdir =(dir + 1) % 3;
+ int ydir =(dir + 2) % 3;
- float xf = avg[ xdir ] ;
- float yf = avg[ ydir ] ;
+ float xf = avg[xdir];
+ float yf = avg[ydir];
#ifdef IN_DEBUG_MODE
// Is it outside?
- // PathElement* leaf = leaf1->len < leaf2->len ? leaf1 : leaf2 ;
+ // PathElement* leaf = leaf1->len < leaf2->len ? leaf1 : leaf2;
/*
- float* m = ( leaf == leaf1 ? m1 : m2 ) ;
- if ( xf < leaf->pos[ xdir ] ||
- yf < leaf->pos[ ydir ] ||
- xf > leaf->pos[ xdir ] + leaf->len ||
- yf > leaf->pos[ ydir ] + leaf->len)
+ float* m =(leaf == leaf1 ? m1 : m2);
+ if(xf < leaf->pos[xdir] ||
+ yf < leaf->pos[ydir] ||
+ xf > leaf->pos[xdir] + leaf->len ||
+ yf > leaf->pos[ydir] + leaf->len)
{
- dc_printf("Outside cube (%d %d %d), %d : %d %d %f %f\n", leaf->pos[ 0 ], leaf->pos[1], leaf->pos[2], leaf->len,
- pos, dir, xf, yf) ;
+ dc_printf("Outside cube(%d %d %d), %d : %d %d %f %f\n", leaf->pos[0], leaf->pos[1], leaf->pos[2], leaf->len,
+ pos, dir, xf, yf);
// For now, snap to cell
- xf = m[ xdir ] ;
- yf = m[ ydir ] ;
+ xf = m[xdir];
+ yf = m[ydir];
}
*/
/*
- if ( alpha < 0 || alpha > 1 ||
+ if(alpha < 0 || alpha > 1 ||
xf < leaf->pos[xdir] || xf > leaf->pos[xdir] + leaf->len ||
- yf < leaf->pos[ydir] || yf > leaf->pos[ydir] + leaf->len )
+ yf < leaf->pos[ydir] || yf > leaf->pos[ydir] + leaf->len)
{
- dc_printf("Alpha: %f Address: %d and %d\n", alpha, leaf1->node, leaf2->node ) ;
- dc_printf("GETFACEPOINT result: (%d %d %d) %d min: (%f %f %f) ;(%d %d %d) %d min: (%f %f %f).\n",
+ dc_printf("Alpha: %f Address: %d and %d\n", alpha, leaf1->node, leaf2->node);
+ dc_printf("GETFACEPOINT result:(%d %d %d) %d min:(%f %f %f);(%d %d %d) %d min:(%f %f %f).\n",
leaf1->pos[0], leaf1->pos[1], leaf1->pos[2], leaf1->len, m1[0], m1[1], m1[2],
leaf2->pos[0], leaf2->pos[1], leaf2->pos[2], leaf2->len, m2[0], m2[1], m2[2]);
- dc_printf("Face point at dir %d pos %d: %f %f\n", dir, pos, xf, yf ) ;
+ dc_printf("Face point at dir %d pos %d: %f %f\n", dir, pos, xf, yf);
}
*/
#endif
// Get the integer and float part
- x = ( ( leaf->pos[ xdir ] ) >> minshift ) ;
- y = ( ( leaf->pos[ ydir ] ) >> minshift ) ;
+ x =((leaf->pos[xdir]) >> minshift);
+ y =((leaf->pos[ydir]) >> minshift);
- p = ( xf - leaf->pos[ xdir ] ) / mindimen ;
- q = ( yf - leaf->pos[ ydir ] ) / mindimen ;
+ p =(xf - leaf->pos[xdir]) / mindimen;
+ q =(yf - leaf->pos[ydir]) / mindimen;
#ifdef IN_DEBUG_MODE
- dc_printf("Face point at dir %d : %f %f\n", dir, xf, yf ) ;
+ dc_printf("Face point at dir %d : %f %f\n", dir, xf, yf);
#endif
}
-int Octree::findPair( PathElement* head, int pos, int dir, PathElement*& pre1, PathElement*& pre2 )
+int Octree::findPair(PathElement* head, int pos, int dir, PathElement*& pre1, PathElement*& pre2)
{
- int side = getSide ( head, pos, dir ) ;
- PathElement* cur = head ;
- PathElement* anchor ;
- PathElement* ppre1, *ppre2 ;
+ int side = getSide(head, pos, dir);
+ PathElement* cur = head;
+ PathElement* anchor;
+ PathElement* ppre1, *ppre2;
// Start from this face, find a pair
- anchor = cur ;
- ppre1 = cur ;
- cur = cur->next ;
- while ( cur != anchor && ( getSide( cur, pos, dir ) == side ) )
+ anchor = cur;
+ ppre1 = cur;
+ cur = cur->next;
+ while(cur != anchor &&(getSide(cur, pos, dir) == side))
{
- ppre1 = cur ;
- cur = cur->next ;
+ ppre1 = cur;
+ cur = cur->next;
}
- if ( cur == anchor )
+ if(cur == anchor)
{
// No pair found
- return side ;
+ return side;
}
- side = getSide( cur, pos, dir ) ;
- ppre2 = cur ;
- cur = cur->next ;
- while ( getSide( cur, pos, dir ) == side )
+ side = getSide(cur, pos, dir);
+ ppre2 = cur;
+ cur = cur->next;
+ while(getSide(cur, pos, dir) == side)
{
- ppre2 = cur ;
- cur = cur->next ;
+ ppre2 = cur;
+ cur = cur->next;
}
// Switch pre1 and pre2 if we start from the higher side
- if ( side == -1 )
+ if(side == -1)
{
- cur = ppre1 ;
- ppre1 = ppre2 ;
- ppre2 = cur ;
+ cur = ppre1;
+ ppre1 = ppre2;
+ ppre2 = cur;
}
- pre1 = ppre1 ;
- pre2 = ppre2 ;
+ pre1 = ppre1;
+ pre2 = ppre2;
- return 0 ;
+ return 0;
}
-int Octree::getSide( PathElement* e, int pos, int dir )
+int Octree::getSide(PathElement* e, int pos, int dir)
{
- return ( e->pos[ dir ] < pos ? -1 : 1 ) ;
+ return (e->pos[dir] < pos ? -1 : 1);
}
-int Octree::isEqual( PathElement* e1, PathElement* e2 )
+int Octree::isEqual(PathElement* e1, PathElement* e2)
{
- return ( e1->pos[0] == e2->pos[0] && e1->pos[1] == e2->pos[1] && e1->pos[2] == e2->pos[2] ) ;
+ return (e1->pos[0] == e2->pos[0] && e1->pos[1] == e2->pos[1] && e1->pos[2] == e2->pos[2]);
}
-void Octree::compressRing( PathElement*& ring )
+void Octree::compressRing(PathElement*& ring)
{
- if ( ring == NULL )
+ if(ring == NULL)
{
- return ;
+ return;
}
#ifdef IN_DEBUG_MODE
- dc_printf("Call to COMPRESSRING with path: \n" );
- printPath( ring ) ;
+ dc_printf("Call to COMPRESSRING with path: \n");
+ printPath(ring);
#endif
- PathElement* cur = ring->next->next ;
- PathElement* pre = ring->next ;
- PathElement* prepre = ring ;
- PathElement* anchor = prepre ;
+ PathElement* cur = ring->next->next;
+ PathElement* pre = ring->next;
+ PathElement* prepre = ring;
+ PathElement* anchor = prepre;
do
{
- while ( isEqual( cur, prepre ) )
+ while(isEqual(cur, prepre))
{
// Delete
- if ( cur == prepre )
+ if(cur == prepre)
{
// The ring has shrinked to a point
- delete pre ;
- delete cur ;
- anchor = NULL ;
- break ;
+ delete pre;
+ delete cur;
+ anchor = NULL;
+ break;
}
else
{
- prepre->next = cur->next ;
- delete pre ;
- delete cur ;
- pre = prepre->next ;
- cur = pre->next ;
- anchor = prepre ;
+ prepre->next = cur->next;
+ delete pre;
+ delete cur;
+ pre = prepre->next;
+ cur = pre->next;
+ anchor = prepre;
}
}
- if ( anchor == NULL )
+ if(anchor == NULL)
{
- break ;
+ break;
}
- prepre = pre ;
- pre = cur ;
- cur = cur->next ;
- } while ( prepre != anchor ) ;
+ prepre = pre;
+ pre = cur;
+ cur = cur->next;
+ } while(prepre != anchor);
- ring = anchor ;
+ ring = anchor;
#ifdef IN_DEBUG_MODE
- dc_printf("Return from COMPRESSRING with path: \n" );
- printPath( ring ) ;
+ dc_printf("Return from COMPRESSRING with path: \n");
+ printPath(ring);
#endif
}
-void Octree::buildSigns( )
+void Octree::buildSigns()
{
// First build a lookup table
- // dc_printf("Building up look up table...\n") ;
- int size = 1 << 12 ;
- unsigned char table[ 1 << 12 ] ;
- for ( int i = 0 ; i < size ; i ++ )
+ // dc_printf("Building up look up table...\n");
+ int size = 1 << 12;
+ unsigned char table[1 << 12];
+ for(int i = 0; i < size; i ++)
{
- table[i] = 0 ;
+ table[i] = 0;
}
- for ( int i = 0 ; i < 256 ; i ++ )
+ for(int i = 0; i < 256; i ++)
{
- int ind = 0 ;
- for ( int j = 11 ; j >= 0 ; j -- )
+ int ind = 0;
+ for(int j = 11; j >= 0; j --)
{
- ind <<= 1 ;
- if ( ( ( i >> edgemap[j][0] ) & 1 ) ^ ( ( i >> edgemap[j][1] ) & 1 ) )
+ ind <<= 1;
+ if(((i >> edgemap[j][0]) & 1) ^((i >> edgemap[j][1]) & 1))
{
- ind |= 1 ;
+ ind |= 1;
}
}
- table[ ind ] = i ;
+ table[ind] = i;
}
// Next, traverse the grid
- int sg = 1 ;
- int cube[8] ;
- buildSigns( table, this->root, 0, sg, cube ) ;
+ int sg = 1;
+ int cube[8];
+ buildSigns(table, root, 0, sg, cube);
}
-void Octree::buildSigns( unsigned char table[], UCHAR* node, int isLeaf, int sg, int rvalue[8] )
+void Octree::buildSigns(unsigned char table[], Node* node, int isLeaf, int sg, int rvalue[8])
{
- if ( node == NULL )
+ if(node == NULL)
{
- for ( int i = 0 ; i < 8 ; i ++ )
+ for(int i = 0; i < 8; i ++)
{
- rvalue[i] = sg ;
+ rvalue[i] = sg;
}
- return ;
+ return;
}
- if ( isLeaf == 0 )
+ if(isLeaf == 0)
{
// Internal node
- UCHAR* chd[8] ;
- int leaf[8] ;
- fillChildren( node, chd, leaf ) ;
+ Node* chd[8];
+ int leaf[8];
+ fillChildren(&node->internal, chd, leaf);
// Get the signs at the corners of the first cube
- rvalue[0] = sg ;
- int oris[8] ;
- buildSigns( table, chd[0], leaf[0], sg, oris ) ;
+ rvalue[0] = sg;
+ int oris[8];
+ buildSigns(table, chd[0], leaf[0], sg, oris);
// Get the rest
- int cube[8] ;
- for ( int i = 1 ; i < 8 ; i ++ )
+ int cube[8];
+ for(int i = 1; i < 8; i ++)
{
- buildSigns( table, chd[i], leaf[i], oris[i], cube ) ;
- rvalue[i] = cube[i] ;
+ buildSigns(table, chd[i], leaf[i], oris[i], cube);
+ rvalue[i] = cube[i];
}
}
else
{
// Leaf node
- generateSigns( node, table, sg ) ;
+ generateSigns(&node->leaf, table, sg);
- for ( int i = 0 ; i < 8 ; i ++ )
+ for(int i = 0; i < 8; i ++)
{
- rvalue[i] = getSign( node, i ) ;
+ rvalue[i] = getSign(&node->leaf, i);
}
}
}
-void Octree::floodFill( )
+void Octree::floodFill()
{
- // int threshold = (int) ((dimen/mindimen) * (dimen/mindimen) * 0.5f) ;
- int st[3] = { 0, 0, 0 } ;
+ // int threshold =(int)((dimen/mindimen) *(dimen/mindimen) * 0.5f);
+ int st[3] = {0, 0, 0};
// First, check for largest component
// size stored in -threshold
- this->clearProcessBits( root, maxDepth ) ;
- int threshold = this->floodFill( root, st, dimen, maxDepth, 0 ) ;
+ clearProcessBits(root, maxDepth);
+ int threshold = floodFill(root, st, dimen, maxDepth, 0);
// Next remove
dc_printf("Largest component: %d\n", threshold);
- threshold *= thresh ;
- dc_printf("Removing all components smaller than %d\n", threshold) ;
+ threshold *= thresh;
+ dc_printf("Removing all components smaller than %d\n", threshold);
- int st2[3] = { 0, 0, 0 } ;
- this->clearProcessBits( root, maxDepth ) ;
- this->floodFill( root, st2, dimen, maxDepth, threshold ) ;
+ int st2[3] = {0, 0, 0};
+ clearProcessBits(root, maxDepth);
+ floodFill(root, st2, dimen, maxDepth, threshold);
}
-void Octree::clearProcessBits( UCHAR* node, int height )
+void Octree::clearProcessBits(Node* node, int height)
{
int i;
- if ( height == 0 )
+ if(height == 0)
{
// Leaf cell,
- for ( i = 0 ; i < 12 ; i ++ )
+ for(i = 0; i < 12; i ++)
{
- setOutProcess( node, i ) ;
+ setOutProcess(&node->leaf, i);
}
}
else
{
// Internal cell, recur
- int count = 0 ;
- for ( i = 0 ; i < 8 ; i ++ )
+ int count = 0;
+ for(i = 0; i < 8; i ++)
{
- if ( hasChild( node, i ) )
+ if(hasChild(&node->internal, i))
{
- clearProcessBits( getChild( node, count ), height - 1 ) ;
- count ++ ;
+ clearProcessBits(getChild(&node->internal, count), height - 1);
+ count ++;
}
}
}
}
-/*
-void Octree::floodFill( UCHAR* node, int st[3], int len, int height, int threshold )
+int Octree::floodFill(LeafNode* leaf, int st[3], int len, int height, int threshold)
{
int i, j;
-
- if ( height == 0 )
- {
- // Leaf cell,
- int par, inp ;
-
- // Test if the leaf has intersection edges
- for ( i = 0 ; i < 12 ; i ++ )
- {
- par = getEdgeParity( node, i ) ;
- inp = isInProcess( node, i ) ;
-
- if ( par == 1 && inp == 0 )
- {
- // Intersection edge, hasn't been processed
- // Let's start filling
- GridQueue* queue = new GridQueue() ;
- int total = 1 ;
-
- // Set to in process
- int mst[3] ;
- mst[0] = st[0] + vertmap[edgemap[i][0]][0] * len ;
- mst[1] = st[1] + vertmap[edgemap[i][0]][1] * len ;
- mst[2] = st[2] + vertmap[edgemap[i][0]][2] * len;
- int mdir = i / 4 ;
- setInProcessAll( mst, mdir ) ;
-
- // Put this edge into queue
- queue->pushQueue( mst, mdir ) ;
-
- // Queue processing
- int nst[3], dir ;
- while ( queue->popQueue( nst, dir ) == 1 )
- {
- // dc_printf("nst: %d %d %d, dir: %d\n", nst[0]/mindimen, nst[1]/mindimen, nst[2]/mindimen, dir) ;
- // locations
- int stMask[3][3] = {
- { 0, 0 - len, 0 - len },
- { 0 - len, 0, 0 - len },
- { 0 - len, 0 - len, 0 }
- };
- int cst[2][3] ;
- for ( j = 0 ; j < 3 ; j ++ )
- {
- cst[0][j] = nst[j] ;
- cst[1][j] = nst[j] + stMask[ dir ][ j ] ;
- }
-
- // cells
- UCHAR* cs[2] ;
- for ( j = 0 ; j < 2 ; j ++ )
- {
- cs[ j ] = locateLeaf( cst[j] ) ;
- }
-
- // Middle sign
- int s = getSign( cs[0], 0 ) ;
-
- // Masks
- int fcCells[4] = {1,0,1,0};
- int fcEdges[3][4][3] = {
- {{9,2,11},{8,1,10},{5,1,7},{4,2,6}},
- {{10,6,11},{8,5,9},{1,5,3},{0,6,2}},
- {{6,10,7},{4,9,5},{2,9,3},{0,10,1}}
- };
-
- // Search for neighboring connected intersection edges
- for ( int find = 0 ; find < 4 ; find ++ )
- {
- int cind = fcCells[find] ;
- int eind, edge ;
- if ( s == 0 )
- {
- // Original order
- for ( eind = 0 ; eind < 3 ; eind ++ )
- {
- edge = fcEdges[dir][find][eind] ;
- if ( getEdgeParity( cs[cind], edge ) == 1 )
- {
- break ;
- }
- }
- }
- else
- {
- // Inverse order
- for ( eind = 2 ; eind >= 0 ; eind -- )
- {
- edge = fcEdges[dir][find][eind] ;
- if ( getEdgeParity( cs[cind], edge ) == 1 )
- {
- break ;
- }
- }
- }
-
- if ( eind == 3 || eind == -1 )
- {
- dc_printf("Wrong! this is not a consistent sign. %d\n", eind );
- }
- else
- {
- int est[3] ;
- est[0] = cst[cind][0] + vertmap[edgemap[edge][0]][0] * len ;
- est[1] = cst[cind][1] + vertmap[edgemap[edge][0]][1] * len ;
- est[2] = cst[cind][2] + vertmap[edgemap[edge][0]][2] * len ;
- int edir = edge / 4 ;
-
- if ( isInProcess( cs[cind], edge ) == 0 )
- {
- setInProcessAll( est, edir ) ;
- queue->pushQueue( est, edir ) ;
- // dc_printf("Pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir) ;
- total ++ ;
- }
- else
- {
- // dc_printf("Processed, not pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir) ;
- }
- }
-
- }
-
+ int maxtotal = 0;
+
+ // Leaf cell,
+ int par, inp;
+
+ // Test if the leaf has intersection edges
+ for(i = 0; i < 12; i ++) {
+ par = getEdgeParity(leaf, i);
+ inp = isInProcess(leaf, i);
+
+ if(par == 1 && inp == 0) {
+ // Intersection edge, hasn't been processed
+ // Let's start filling
+ GridQueue* queue = new GridQueue();
+ int total = 1;
+
+ // Set to in process
+ int mst[3];
+ mst[0] = st[0] + vertmap[edgemap[i][0]][0] * len;
+ mst[1] = st[1] + vertmap[edgemap[i][0]][1] * len;
+ mst[2] = st[2] + vertmap[edgemap[i][0]][2] * len;
+ int mdir = i / 4;
+ setInProcessAll(mst, mdir);
+
+ // Put this edge into queue
+ queue->pushQueue(mst, mdir);
+
+ // Queue processing
+ int nst[3], dir;
+ while(queue->popQueue(nst, dir) == 1) {
+ // dc_printf("nst: %d %d %d, dir: %d\n", nst[0]/mindimen, nst[1]/mindimen, nst[2]/mindimen, dir);
+ // locations
+ int stMask[3][3] = {
+ {0, 0 - len, 0 - len},
+ {0 - len, 0, 0 - len},
+ {0 - len, 0 - len, 0}
+ };
+ int cst[2][3];
+ for(j = 0; j < 3; j ++) {
+ cst[0][j] = nst[j];
+ cst[1][j] = nst[j] + stMask[dir][j];
}
- dc_printf("Size of component: %d ", total) ;
-
- if ( total > threshold )
- {
- dc_printf("Maintained.\n") ;
- continue ;
+ // cells
+ LeafNode* cs[2];
+ for(j = 0; j < 2; j ++) {
+ cs[j] = locateLeaf(cst[j]);
}
- dc_printf("Less then %d, removing...\n", threshold) ;
-
- // We have to remove this noise
-
- // Flip parity
- // setOutProcessAll( mst, mdir ) ;
- flipParityAll( mst, mdir ) ;
-
- // Put this edge into queue
- queue->pushQueue( mst, mdir ) ;
-
- // Queue processing
- while ( queue->popQueue( nst, dir ) == 1 )
- {
- // dc_printf("nst: %d %d %d, dir: %d\n", nst[0]/mindimen, nst[1]/mindimen, nst[2]/mindimen, dir) ;
- // locations
- int stMask[3][3] = {
- { 0, 0 - len, 0 - len },
- { 0 - len, 0, 0 - len },
- { 0 - len, 0 - len, 0 }
- };
- int cst[2][3] ;
- for ( j = 0 ; j < 3 ; j ++ )
- {
- cst[0][j] = nst[j] ;
- cst[1][j] = nst[j] + stMask[ dir ][ j ] ;
- }
- // cells
- UCHAR* cs[2] ;
- for ( j = 0 ; j < 2 ; j ++ )
- {
- cs[ j ] = locateLeaf( cst[j] ) ;
- }
-
- // Middle sign
- int s = getSign( cs[0], 0 ) ;
-
- // Masks
- int fcCells[4] = {1,0,1,0};
- int fcEdges[3][4][3] = {
- {{9,2,11},{8,1,10},{5,1,7},{4,2,6}},
- {{10,6,11},{8,5,9},{1,5,3},{0,6,2}},
- {{6,10,7},{4,9,5},{2,9,3},{0,10,1}}
- };
-
- // Search for neighboring connected intersection edges
- for ( int find = 0 ; find < 4 ; find ++ )
- {
- int cind = fcCells[find] ;
- int eind, edge ;
- if ( s == 0 )
- {
- // Original order
- for ( eind = 0 ; eind < 3 ; eind ++ )
- {
- edge = fcEdges[dir][find][eind] ;
- if ( isInProcess( cs[cind], edge ) == 1 )
- {
- break ;
- }
- }
- }
- else
- {
- // Inverse order
- for ( eind = 2 ; eind >= 0 ; eind -- )
- {
- edge = fcEdges[dir][find][eind] ;
- if ( isInProcess( cs[cind], edge ) == 1 )
- {
- break ;
- }
- }
- }
-
- if ( eind == 3 || eind == -1 )
- {
- dc_printf("Wrong! this is not a consistent sign. %d\n", eind );
- }
- else
- {
- int est[3] ;
- est[0] = cst[cind][0] + vertmap[edgemap[edge][0]][0] * len ;
- est[1] = cst[cind][1] + vertmap[edgemap[edge][0]][1] * len ;
- est[2] = cst[cind][2] + vertmap[edgemap[edge][0]][2] * len ;
- int edir = edge / 4 ;
-
- if ( getEdgeParity( cs[cind], edge ) == 1 )
- {
- flipParityAll( est, edir ) ;
- queue->pushQueue( est, edir ) ;
- // dc_printf("Pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir) ;
- total ++ ;
- }
- else
- {
- // dc_printf("Processed, not pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir) ;
+ // Middle sign
+ int s = getSign(cs[0], 0);
+
+ // Masks
+ int fcCells[4] = {1,0,1,0};
+ int fcEdges[3][4][3] = {
+ {{9,2,11},{8,1,10},{5,1,7},{4,2,6}},
+ {{10,6,11},{8,5,9},{1,5,3},{0,6,2}},
+ {{6,10,7},{4,9,5},{2,9,3},{0,10,1}}
+ };
+
+ // Search for neighboring connected intersection edges
+ for(int find = 0; find < 4; find ++) {
+ int cind = fcCells[find];
+ int eind, edge;
+ if(s == 0) {
+ // Original order
+ for(eind = 0; eind < 3; eind ++) {
+ edge = fcEdges[dir][find][eind];
+ if(getEdgeParity(cs[cind], edge) == 1) {
+ break;
}
}
-
}
-
- }
-
- }
- }
- }
- else
- {
- // Internal cell, recur
- int count = 0 ;
- len >>= 1 ;
- for ( i = 0 ; i < 8 ; i ++ )
- {
- if ( hasChild( node, i ) )
- {
- int nst[3] ;
- nst[0] = st[0] + vertmap[i][0] * len ;
- nst[1] = st[1] + vertmap[i][1] * len ;
- nst[2] = st[2] + vertmap[i][2] * len ;
-
- floodFill( getChild( node, count ), nst, len, height - 1, threshold ) ;
- count ++ ;
- }
- }
- }
-}
-*/
-
-int Octree::floodFill( UCHAR* node, int st[3], int len, int height, int threshold )
-{
- int i, j;
- int maxtotal = 0 ;
-
- if ( height == 0 )
- {
- // Leaf cell,
- int par, inp ;
-
- // Test if the leaf has intersection edges
- for ( i = 0 ; i < 12 ; i ++ )
- {
- par = getEdgeParity( node, i ) ;
- inp = isInProcess( node, i ) ;
-
- if ( par == 1 && inp == 0 )
- {
- // Intersection edge, hasn't been processed
- // Let's start filling
- GridQueue* queue = new GridQueue() ;
- int total = 1 ;
-
- // Set to in process
- int mst[3] ;
- mst[0] = st[0] + vertmap[edgemap[i][0]][0] * len ;
- mst[1] = st[1] + vertmap[edgemap[i][0]][1] * len ;
- mst[2] = st[2] + vertmap[edgemap[i][0]][2] * len;
- int mdir = i / 4 ;
- setInProcessAll( mst, mdir ) ;
-
- // Put this edge into queue
- queue->pushQueue( mst, mdir ) ;
-
- // Queue processing
- int nst[3], dir ;
- while ( queue->popQueue( nst, dir ) == 1 )
- {
- // dc_printf("nst: %d %d %d, dir: %d\n", nst[0]/mindimen, nst[1]/mindimen, nst[2]/mindimen, dir) ;
- // locations
- int stMask[3][3] = {
- { 0, 0 - len, 0 - len },
- { 0 - len, 0, 0 - len },
- { 0 - len, 0 - len, 0 }
- };
- int cst[2][3] ;
- for ( j = 0 ; j < 3 ; j ++ )
- {
- cst[0][j] = nst[j] ;
- cst[1][j] = nst[j] + stMask[ dir ][ j ] ;
- }
-
- // cells
- UCHAR* cs[2] ;
- for ( j = 0 ; j < 2 ; j ++ )
- {
- cs[ j ] = locateLeaf( cst[j] ) ;
- }
-
- // Middle sign
- int s = getSign( cs[0], 0 ) ;
-
- // Masks
- int fcCells[4] = {1,0,1,0};
- int fcEdges[3][4][3] = {
- {{9,2,11},{8,1,10},{5,1,7},{4,2,6}},
- {{10,6,11},{8,5,9},{1,5,3},{0,6,2}},
- {{6,10,7},{4,9,5},{2,9,3},{0,10,1}}
- };
-
- // Search for neighboring connected intersection edges
- for ( int find = 0 ; find < 4 ; find ++ )
- {
- int cind = fcCells[find] ;
- int eind, edge ;
- if ( s == 0 )
- {
- // Original order
- for ( eind = 0 ; eind < 3 ; eind ++ )
- {
- edge = fcEdges[dir][find][eind] ;
- if ( getEdgeParity( cs[cind], edge ) == 1 )
- {
- break ;
- }
- }
- }
- else
- {
- // Inverse order
- for ( eind = 2 ; eind >= 0 ; eind -- )
- {
- edge = fcEdges[dir][find][eind] ;
- if ( getEdgeParity( cs[cind], edge ) == 1 )
- {
- break ;
- }
+ else {
+ // Inverse order
+ for(eind = 2; eind >= 0; eind --) {
+ edge = fcEdges[dir][find][eind];
+ if(getEdgeParity(cs[cind], edge) == 1) {
+ break;
}
}
+ }
- if ( eind == 3 || eind == -1 )
- {
- dc_printf("Wrong! this is not a consistent sign. %d\n", eind );
- }
- else
- {
- int est[3] ;
- est[0] = cst[cind][0] + vertmap[edgemap[edge][0]][0] * len ;
- est[1] = cst[cind][1] + vertmap[edgemap[edge][0]][1] * len ;
- est[2] = cst[cind][2] + vertmap[edgemap[edge][0]][2] * len ;
- int edir = edge / 4 ;
+ if(eind == 3 || eind == -1) {
+ dc_printf("Wrong! this is not a consistent sign. %d\n", eind);
+ }
+ else {
+ int est[3];
+ est[0] = cst[cind][0] + vertmap[edgemap[edge][0]][0] * len;
+ est[1] = cst[cind][1] + vertmap[edgemap[edge][0]][1] * len;
+ est[2] = cst[cind][2] + vertmap[edgemap[edge][0]][2] * len;
+ int edir = edge / 4;
- if ( isInProcess( cs[cind], edge ) == 0 )
- {
- setInProcessAll( est, edir ) ;
- queue->pushQueue( est, edir ) ;
- // dc_printf("Pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir) ;
- total ++ ;
- }
- else
- {
- // dc_printf("Processed, not pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir) ;
- }
+ if(isInProcess(cs[cind], edge) == 0) {
+ setInProcessAll(est, edir);
+ queue->pushQueue(est, edir);
+ // dc_printf("Pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir);
+ total ++;
}
-
}
-
}
+ }
- dc_printf("Size of component: %d ", total) ;
+ dc_printf("Size of component: %d ", total);
- if ( threshold == 0 )
- {
- // Measuring stage
- if ( total > maxtotal )
- {
- maxtotal = total ;
- }
- dc_printf(".\n") ;
- continue ;
+ if(threshold == 0) {
+ // Measuring stage
+ if(total > maxtotal) {
+ maxtotal = total;
}
+ dc_printf(".\n");
+ continue;
+ }
- if ( total >= threshold )
- {
- dc_printf("Maintained.\n") ;
- continue ;
+ if(total >= threshold) {
+ dc_printf("Maintained.\n");
+ continue;
+ }
+ dc_printf("Less then %d, removing...\n", threshold);
+
+ // We have to remove this noise
+
+ // Flip parity
+ // setOutProcessAll(mst, mdir);
+ flipParityAll(mst, mdir);
+
+ // Put this edge into queue
+ queue->pushQueue(mst, mdir);
+
+ // Queue processing
+ while(queue->popQueue(nst, dir) == 1) {
+ // dc_printf("nst: %d %d %d, dir: %d\n", nst[0]/mindimen, nst[1]/mindimen, nst[2]/mindimen, dir);
+ // locations
+ int stMask[3][3] = {
+ {0, 0 - len, 0 - len},
+ {0 - len, 0, 0 - len},
+ {0 - len, 0 - len, 0}
+ };
+ int cst[2][3];
+ for(j = 0; j < 3; j ++) {
+ cst[0][j] = nst[j];
+ cst[1][j] = nst[j] + stMask[dir][j];
}
- dc_printf("Less then %d, removing...\n", threshold) ;
- // We have to remove this noise
-
- // Flip parity
- // setOutProcessAll( mst, mdir ) ;
- flipParityAll( mst, mdir ) ;
-
- // Put this edge into queue
- queue->pushQueue( mst, mdir ) ;
-
- // Queue processing
- while ( queue->popQueue( nst, dir ) == 1 )
- {
- // dc_printf("nst: %d %d %d, dir: %d\n", nst[0]/mindimen, nst[1]/mindimen, nst[2]/mindimen, dir) ;
- // locations
- int stMask[3][3] = {
- { 0, 0 - len, 0 - len },
- { 0 - len, 0, 0 - len },
- { 0 - len, 0 - len, 0 }
- };
- int cst[2][3] ;
- for ( j = 0 ; j < 3 ; j ++ )
- {
- cst[0][j] = nst[j] ;
- cst[1][j] = nst[j] + stMask[ dir ][ j ] ;
- }
-
- // cells
- UCHAR* cs[2] ;
- for ( j = 0 ; j < 2 ; j ++ )
- {
- cs[ j ] = locateLeaf( cst[j] ) ;
- }
-
- // Middle sign
- int s = getSign( cs[0], 0 ) ;
-
- // Masks
- int fcCells[4] = {1,0,1,0};
- int fcEdges[3][4][3] = {
- {{9,2,11},{8,1,10},{5,1,7},{4,2,6}},
- {{10,6,11},{8,5,9},{1,5,3},{0,6,2}},
- {{6,10,7},{4,9,5},{2,9,3},{0,10,1}}
- };
-
- // Search for neighboring connected intersection edges
- for ( int find = 0 ; find < 4 ; find ++ )
- {
- int cind = fcCells[find] ;
- int eind, edge ;
- if ( s == 0 )
- {
- // Original order
- for ( eind = 0 ; eind < 3 ; eind ++ )
- {
- edge = fcEdges[dir][find][eind] ;
- if ( isInProcess( cs[cind], edge ) == 1 )
- {
- break ;
- }
+ // cells
+ LeafNode* cs[2];
+ for(j = 0; j < 2; j ++)
+ cs[j] = locateLeaf(cst[j]);
+
+ // Middle sign
+ int s = getSign(cs[0], 0);
+
+ // Masks
+ int fcCells[4] = {1,0,1,0};
+ int fcEdges[3][4][3] = {
+ {{9,2,11},{8,1,10},{5,1,7},{4,2,6}},
+ {{10,6,11},{8,5,9},{1,5,3},{0,6,2}},
+ {{6,10,7},{4,9,5},{2,9,3},{0,10,1}}
+ };
+
+ // Search for neighboring connected intersection edges
+ for(int find = 0; find < 4; find ++) {
+ int cind = fcCells[find];
+ int eind, edge;
+ if(s == 0) {
+ // Original order
+ for(eind = 0; eind < 3; eind ++) {
+ edge = fcEdges[dir][find][eind];
+ if(isInProcess(cs[cind], edge) == 1) {
+ break;
}
}
- else
- {
- // Inverse order
- for ( eind = 2 ; eind >= 0 ; eind -- )
- {
- edge = fcEdges[dir][find][eind] ;
- if ( isInProcess( cs[cind], edge ) == 1 )
- {
- break ;
- }
+ }
+ else {
+ // Inverse order
+ for(eind = 2; eind >= 0; eind --) {
+ edge = fcEdges[dir][find][eind];
+ if(isInProcess(cs[cind], edge) == 1) {
+ break;
}
}
+ }
- if ( eind == 3 || eind == -1 )
- {
- dc_printf("Wrong! this is not a consistent sign. %d\n", eind );
- }
- else
- {
- int est[3] ;
- est[0] = cst[cind][0] + vertmap[edgemap[edge][0]][0] * len ;
- est[1] = cst[cind][1] + vertmap[edgemap[edge][0]][1] * len ;
- est[2] = cst[cind][2] + vertmap[edgemap[edge][0]][2] * len ;
- int edir = edge / 4 ;
+ if(eind == 3 || eind == -1) {
+ dc_printf("Wrong! this is not a consistent sign. %d\n", eind);
+ }
+ else {
+ int est[3];
+ est[0] = cst[cind][0] + vertmap[edgemap[edge][0]][0] * len;
+ est[1] = cst[cind][1] + vertmap[edgemap[edge][0]][1] * len;
+ est[2] = cst[cind][2] + vertmap[edgemap[edge][0]][2] * len;
+ int edir = edge / 4;
- if ( getEdgeParity( cs[cind], edge ) == 1 )
- {
- flipParityAll( est, edir ) ;
- queue->pushQueue( est, edir ) ;
- // dc_printf("Pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir) ;
- total ++ ;
- }
- else
- {
- // dc_printf("Processed, not pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir) ;
- }
+ if(getEdgeParity(cs[cind], edge) == 1) {
+ flipParityAll(est, edir);
+ queue->pushQueue(est, edir);
+ // dc_printf("Pushed: est: %d %d %d, edir: %d\n", est[0]/len, est[1]/len, est[2]/len, edir);
+ total ++;
}
-
}
-
}
-
}
}
-
}
- else
- {
- // Internal cell, recur
- int count = 0 ;
- len >>= 1 ;
- for ( i = 0 ; i < 8 ; i ++ )
- {
- if ( hasChild( node, i ) )
- {
- int nst[3] ;
- nst[0] = st[0] + vertmap[i][0] * len ;
- nst[1] = st[1] + vertmap[i][1] * len ;
- nst[2] = st[2] + vertmap[i][2] * len ;
-
- int d = floodFill( getChild( node, count ), nst, len, height - 1, threshold ) ;
- if ( d > maxtotal)
- {
- maxtotal = d ;
- }
- count ++ ;
- }
- }
- }
-
-
- return maxtotal ;
-
-}
-
-void Octree::writeOut()
-{
- int numQuads = 0 ;
- int numVertices = 0 ;
- int numEdges = 0 ;
-#ifdef USE_HERMIT
- countIntersection( root, maxDepth, numQuads, numVertices, numEdges ) ;
-#else
- countIntersection( root, maxDepth, numQuads, numVertices ) ;
- numEdges = numQuads * 3 / 2 ;
-#endif
- dc_printf("Vertices counted: %d Polys counted: %d \n", numVertices, numQuads ) ;
- output_mesh = alloc_output(numVertices, numQuads);
- int offset = 0 ;
- int st[3] = { 0, 0, 0 } ;
-
- // First, output vertices
- offset = 0 ;
- actualVerts = 0 ;
- actualQuads = 0 ;
-#ifdef USE_HERMIT
- generateMinimizer( root, st, dimen, maxDepth, offset ) ;
- cellProcContour( this->root, 0, maxDepth ) ;
- dc_printf("Vertices written: %d Quads written: %d \n", offset, actualQuads ) ;
-#else
- writeVertex( root, st, dimen, maxDepth, offset, out ) ;
- writeQuad( root, st, dimen, maxDepth, out ) ;
- dc_printf("Vertices written: %d Triangles written: %d \n", offset, actualQuads ) ;
-#endif
-}
-
-#if 0
-void Octree::writePLY( char* fname )
-{
- int numQuads = 0 ;
- int numVertices = 0 ;
- int numEdges = 0 ;
-#ifdef USE_HERMIT
- countIntersection( root, maxDepth, numQuads, numVertices, numEdges ) ;
-#else
- countIntersection( root, maxDepth, numQuads, numVertices ) ;
- numEdges = numQuads * 3 / 2 ;
-#endif
- // int euler = numVertices + numQuads - numEdges ;
- // int genus = ( 2 - euler ) / 2 ;
- // dc_printf("%d vertices %d quads %d edges\n", numVertices, numQuads, numEdges ) ;
- // dc_printf("Genus: %d Euler: %d\n", genus, euler ) ;
-
- FILE* fout = fopen ( fname, "wb" ) ;
- dc_printf("Vertices counted: %d Polys counted: %d \n", numVertices, numQuads ) ;
- PLYWriter::writeHeader( fout, numVertices, numQuads ) ;
- int offset = 0 ;
- int st[3] = { 0, 0, 0 } ;
-
- // First, output vertices
- offset = 0 ;
- actualVerts = 0 ;
- actualQuads = 0 ;
-#ifdef USE_HERMIT
- generateMinimizer( root, st, dimen, maxDepth, offset, fout ) ;
-#ifdef TESTMANIFOLD
- testfout = fopen("test.txt", "w");
- fprintf(testfout, "{");
-#endif
- cellProcContour( this->root, 0, maxDepth, fout ) ;
-#ifdef TESTMANIFOLD
- fprintf(testfout, "}");
- fclose( testfout ) ;
-#endif
- dc_printf("Vertices written: %d Quads written: %d \n", offset, actualQuads ) ;
-#else
- writeVertex( root, st, dimen, maxDepth, offset, fout ) ;
- writeQuad( root, st, dimen, maxDepth, fout ) ;
- dc_printf("Vertices written: %d Triangles written: %d \n", offset, actualQuads ) ;
-#endif
-
-
- fclose( fout ) ;
-}
-#endif
-
-void Octree::writeOctree( char* fname )
-{
- FILE* fout = fopen ( fname, "wb" ) ;
- int sized = ( 1 << maxDepth ) ;
- fwrite( &sized, sizeof( int ), 1, fout ) ;
- writeOctree( fout, root, maxDepth ) ;
- dc_printf("Grid dimension: %d\n", sized ) ;
-
-
- fclose( fout ) ;
-}
-void Octree::writeOctree( FILE* fout, UCHAR* node, int depth )
-{
- char type ;
- if ( depth > 0 )
- {
- type = 0 ;
- fwrite( &type, sizeof( char ), 1, fout ) ;
-
- // Get sign at the center
- char sg = (char) getSign( getChild( node, 0 ), depth - 1, 7 - getChildIndex( node, 0 ) ) ;
-
- int t = 0 ;
- for ( int i = 0 ; i < 8 ; i ++ )
- {
- if ( hasChild( node, i ) )
- {
- writeOctree( fout, getChild( node, t ), depth - 1 ) ;
- t ++ ;
- }
- else
- {
- type = 1 ;
- fwrite( &type, sizeof( char ), 1, fout ) ;
- fwrite( &sg, sizeof( char ), 1, fout ) ;
- }
- }
- }
- else
- {
- type = 2 ;
- fwrite( &type, sizeof( char ), 1, fout ) ;
- fwrite( &(node[2]), sizeof ( UCHAR ), 1, fout );
- }
+ return maxtotal;
}
-#ifdef USE_HERMIT
-#if 0
-void Octree::writeOctreeGeom( char* fname )
+int Octree::floodFill(Node* node, int st[3], int len, int height, int threshold)
{
- FILE* fout = fopen ( fname, "wb" ) ;
-
- // Write header
- char header[]="SOG.Format 1.0";
- int nlen = 128 - 4 * 4 - strlen(header) - 1 ;
- char* header2 = new char[ nlen ];
- for ( int i = 0 ; i < nlen ; i ++ )
- {
- header2[i] = '\0';
- }
- fwrite( header, sizeof( char ), strlen(header) + 1, fout ) ;
- fwrite( origin, sizeof( float ), 3, fout ) ;
- fwrite( &range, sizeof( float ), 1, fout ) ;
- fwrite( header2, sizeof( char ), nlen, fout ) ;
-
-
- int sized = ( 1 << maxDepth ) ;
- int st[3] = {0,0,0};
- fwrite( &sized, sizeof( int ), 1, fout ) ;
-
- writeOctreeGeom( fout, root, st, dimen, maxDepth ) ;
- dc_printf("Grid dimension: %d\n", sized ) ;
-
-
- fclose( fout ) ;
-}
-#endif
-void Octree::writeOctreeGeom( FILE* fout, UCHAR* node, int st[3], int len, int depth )
-{
- char type ;
- if ( depth > 0 )
- {
- type = 0 ;
- fwrite( &type, sizeof( char ), 1, fout ) ;
-
- // Get sign at the center
- char sg = (char) getSign( getChild( node, 0 ), depth - 1, 7 - getChildIndex( node, 0 ) ) ;
-
- int t = 0 ;
- len >>= 1 ;
- for ( int i = 0 ; i < 8 ; i ++ )
- {
- if ( hasChild( node, i ) )
- {
- int nst[3] ;
- nst[0] = st[0] + vertmap[i][0] * len ;
- nst[1] = st[1] + vertmap[i][1] * len ;
- nst[2] = st[2] + vertmap[i][2] * len ;
- writeOctreeGeom( fout, getChild( node, t ), nst, len, depth - 1 ) ;
- t ++ ;
- }
- else
- {
- type = 1 ;
- fwrite( &type, sizeof( char ), 1, fout ) ;
- fwrite( &sg, sizeof( char ), 1, fout ) ;
- }
- }
- }
- else
- {
- type = 2 ;
- fwrite( &type, sizeof( char ), 1, fout ) ;
- fwrite( &(node[2]), sizeof ( UCHAR ), 1, fout );
-
- // Compute minimizer
- // First, find minimizer
- float rvalue[3] ;
- rvalue[0] = (float) st[0] + len / 2 ;
- rvalue[1] = (float) st[1] + len / 2 ;
- rvalue[2] = (float) st[2] + len / 2 ;
- computeMinimizer( node, st, len, rvalue ) ;
-
- // Update
- // float flen = len * range / dimen ;
- for ( int j = 0 ; j < 3 ; j ++ )
- {
- rvalue[ j ] = rvalue[ j ] * range / dimen + origin[ j ] ;
- }
-
- fwrite( rvalue, sizeof ( float ), 3, fout );
- }
-}
-#endif
-
-#ifdef USE_HERMIT
-void Octree::writeDCF( char* fname )
-{
- FILE* fout = fopen ( fname, "wb" ) ;
-
- // Writing out version
- char version[10] = "multisign";
- fwrite ( &version, sizeof ( char ), 10, fout );
-
- // Writing out size
- int sized = ( 1 << maxDepth ) ;
- fwrite( &sized, sizeof( int ), 1, fout ) ;
- fwrite( &sized, sizeof( int ), 1, fout ) ;
- fwrite( &sized, sizeof( int ), 1, fout ) ;
-
- int st[3] = {0, 0, 0} ;
- writeDCF( fout, root, maxDepth, st, dimen ) ;
-
- dc_printf("Grid dimension: %d\n", sized ) ;
- fclose( fout ) ;
-}
+ int i;
+ int maxtotal = 0;
-void Octree::writeDCF( FILE* fout, UCHAR* node, int height, int st[3], int len )
-{
- nodetype type ;
- if ( height > 0 )
+ if(height == 0)
{
- type = 0 ;
- len >>= 1 ;
- fwrite( &type, sizeof( nodetype ), 1, fout ) ;
-
- // Get sign at the center
- signtype sg = 1 - (signtype) getSign( getChild( node, 0 ), height - 1, 7 - getChildIndex( node, 0 ) ) ;
-
- int t = 0 ;
- for ( int i = 0 ; i < 8 ; i ++ )
- {
- if ( hasChild( node, i ) )
- {
- int nst[3] ;
- nst[0] = st[0] + vertmap[i][0] * len ;
- nst[1] = st[1] + vertmap[i][1] * len ;
- nst[2] = st[2] + vertmap[i][2] * len ;
-
-
- writeDCF( fout, getChild( node, t ), height - 1, nst, len ) ;
- t ++ ;
- }
- else
- {
- type = 1 ;
- fwrite( &type, sizeof( nodetype ), 1, fout ) ;
- fwrite ( &(sg), sizeof ( signtype ), 1, fout );
- }
- }
+ maxtotal = floodFill(&node->leaf, st, len, height, threshold);
}
else
{
- type = 2 ;
- fwrite( &type, sizeof( nodetype ), 1, fout ) ;
-
- // Write signs
- signtype sgn[8] ;
- for ( int i = 0 ; i < 8 ; i ++ )
- {
- sgn[ i ] = 1 - (signtype) getSign( node, i ) ;
- }
- fwrite (sgn, sizeof (signtype), 8, fout );
-
- // Write edge data
- float pts[12], norms[12][3] ;
- int parity[12] ;
- fillEdgeOffsetsNormals( node, st, len, pts, norms, parity ) ;
-
- numtype zero = 0, one = 1 ;
- for ( int i = 0 ; i < 12 ; i ++ )
+ // Internal cell, recur
+ int count = 0;
+ len >>= 1;
+ for(i = 0; i < 8; i ++)
{
- int par = getEdgeParity( node, i ) ;
- // Let's check first
- if ( par )
- {
- if ( sgn[ edgemap[i][0] ] == sgn[ edgemap[i][1] ] )
- {
- dc_printf("Wrong! Parity: %d Sign: %d %d\n", parity[i], sgn[ edgemap[i][0] ], sgn[ edgemap[i][1] ]);
- exit(0) ;
- }
- if ( parity[ i ] == 0 )
- {
- dc_printf("Wrong! No intersection found.\n");
- exit(0) ;
- }
- fwrite( &one, sizeof ( numtype ) , 1, fout ) ;
- fwrite( &(pts[i]), sizeof( float ), 1, fout ) ;
- fwrite( norms[i], sizeof( float ), 3, fout ) ;
-
- }
- else
+ if(hasChild((InternalNode*)node, i))
{
- if ( sgn[ edgemap[i][0] ] != sgn[ edgemap[i][1] ] )
+ int nst[3];
+ nst[0] = st[0] + vertmap[i][0] * len;
+ nst[1] = st[1] + vertmap[i][1] * len;
+ nst[2] = st[2] + vertmap[i][2] * len;
+
+ int d = floodFill(getChild((InternalNode*)node, count), nst, len, height - 1, threshold);
+ if(d > maxtotal)
{
- dc_printf("Wrong! Parity: %d Sign: %d %d\n", parity[i], sgn[ edgemap[i][0] ], sgn[ edgemap[i][1] ]);
- exit(0) ;
+ maxtotal = d;
}
- fwrite ( &zero, sizeof ( numtype ) , 1, fout );
+ count ++;
}
}
}
-}
-#endif
-
-void Octree::writeOpenEdges( FILE* fout )
-{
- // Total number of rings
- fprintf( fout, "%d\n", numRings ) ;
- dc_printf("Number of rings to write: %d\n", numRings) ;
-
- // Write each ring
- PathList* tlist = ringList ;
- for ( int i = 0 ; i < numRings ; i ++ )
- {
- fprintf(fout, "%d\n", tlist->length) ;
- // dc_printf("Ring length: %d\n", tlist->length ) ;
- PathElement* cur = tlist->head ;
- for ( int j = 0 ; j < tlist->length ; j ++ )
- {
- float cent[3] ;
- float flen = mindimen * range / dimen ;
- for ( int k = 0 ; k < 3 ; k ++ )
- {
- cent[ k ] = cur->pos[ k ] * range / dimen + origin[ k ] + flen / 2 ;
- }
- fprintf(fout, "%f %f %f\n", cent[0], cent[1], cent[2]) ;
- cur = cur->next ;
- }
-
- tlist = tlist->next ;
- }
-}
-#ifndef USE_HERMIT
-void Octree::countIntersection( UCHAR* node, int height, int& nquad, int& nvert )
-{
- if ( height > 0 )
- {
- int total = getNumChildren( node ) ;
- for ( int i = 0 ; i < total ; i ++ )
- {
- countIntersection( getChild( node, i ), height - 1, nquad, nvert ) ;
- }
- }
- else
- {
- int mask = getSignMask( node ) ;
- nvert += getNumEdges2( node ) ;
- nquad += cubes->getNumTriangle( mask ) ;
+ return maxtotal;
- }
}
-void Octree::writeVertex( UCHAR* node, int st[3], int len, int height, int& offset, FILE* fout )
+void Octree::writeOut()
{
- int i ;
-
- if ( height == 0 )
- {
- // Leaf cell, generate
- int emap[] = { 0, 4, 8 } ;
- for ( int i = 0 ; i < 3 ; i ++ )
- {
- if ( getEdgeParity( node, emap[i] ) )
- {
- // Get intersection location
- int count = getEdgeCount( node, i ) ;
- float off = getEdgeOffset( node, count ) ;
-
- float rvalue[3] ;
- rvalue[0] = (float) st[0] ;
- rvalue[1] = (float) st[1] ;
- rvalue[2] = (float) st[2] ;
- rvalue[i] += off * mindimen ;
-
- // Update
- float fnst[3] ;
- float flen = len * range / dimen ;
- for ( int j = 0 ; j < 3 ; j ++ )
- {
- rvalue[ j ] = rvalue[ j ] * range / dimen + origin[ j ] ;
- fnst[ j ] = st[ j ] * range / dimen + origin[ j ] ;
- }
-
- if ( this->outType == 0 )
- {
- fprintf( fout, "%f %f %f\n", rvalue[0], rvalue[1], rvalue[2] ) ;
- }
- else if ( this->outType == 1 )
- {
- PLYWriter::writeVertex( fout, rvalue ) ;
- }
-
- // Store the index
- setEdgeIntersectionIndex( node, count, offset ) ;
- offset ++ ;
- }
- }
+ int numQuads = 0;
+ int numVertices = 0;
+ int numEdges = 0;
- }
- else
- {
- // Internal cell, recur
- int count = 0 ;
- len >>= 1 ;
- for ( i = 0 ; i < 8 ; i ++ )
- {
- if ( hasChild( node, i ) )
- {
- int nst[3] ;
- nst[0] = st[0] + vertmap[i][0] * len ;
- nst[1] = st[1] + vertmap[i][1] * len ;
- nst[2] = st[2] + vertmap[i][2] * len ;
-
- writeVertex( getChild( node, count ), nst, len, height - 1, offset, fout ) ;
- count ++ ;
- }
- }
- }
-}
+ countIntersection(root, maxDepth, numQuads, numVertices, numEdges);
-void Octree::writeQuad( UCHAR* node, int st[3], int len, int height, FILE* fout )
-{
- int i ;
- if ( height == 0 )
- {
- int mask = getSignMask( node ) ;
- int num = cubes->getNumTriangle( mask ) ;
- int indices[12] ;
- fillEdgeIntersectionIndices( node, st, len, indices ) ;
- int einds[3], ind[3] ;
-
- //int flag1 = 0 ;
- //int flag2 = 0 ;
- for ( i = 0 ; i < num ; i ++ )
- {
- int color = 0 ;
- cubes->getTriangle( mask, i, einds ) ;
- // dc_printf("(%d %d %d) ", einds[0], einds[1], einds[2] ) ;
-
- for ( int j = 0 ; j < 3 ; j ++ )
- {
- ind[j] = indices[ einds[j] ] ;
- /*
- if ( ind[j] == 78381 )
- {
- flag1 = 1 ;
- }
- if ( ind[j] == 78384 )
- {
- flag2 = 1 ;
- }
- */
- }
+ dc_printf("Vertices counted: %d Polys counted: %d \n", numVertices, numQuads);
+ output_mesh = alloc_output(numVertices, numQuads);
+ int offset = 0;
+ int st[3] = {0, 0, 0};
- if ( this->outType == 0 )
- {
- // OFF
- int numpoly = ( color ? -3 : 3 ) ;
- fprintf(fout, "%d %d %d %d\n", numpoly, ind[0], ind[1], ind[2] ) ;
- actualQuads ++ ;
- }
- else if ( this->outType == 1 )
- {
- // PLY
- PLYWriter::writeFace( fout, 3, ind ) ;
- actualQuads ++ ;
- }
- }
+ // First, output vertices
+ offset = 0;
+ actualVerts = 0;
+ actualQuads = 0;
- /*
- if (flag1 && flag2)
- {
- dc_printf("%d\n", mask);
- cubes->printTriangles( mask ) ;
- }
- */
- }
- else
- {
- // Internal cell, recur
- int count = 0 ;
- len >>= 1 ;
- for ( i = 0 ; i < 8 ; i ++ )
- {
- if ( hasChild( node, i ) )
- {
- int nst[3] ;
- nst[0] = st[0] + vertmap[i][0] * len ;
- nst[1] = st[1] + vertmap[i][1] * len ;
- nst[2] = st[2] + vertmap[i][2] * len ;
-
- writeQuad( getChild( node, count ), nst, len, height - 1, fout ) ;
- count ++ ;
- }
- }
- }
+ generateMinimizer(root, st, dimen, maxDepth, offset);
+ cellProcContour(root, 0, maxDepth);
+ dc_printf("Vertices written: %d Quads written: %d \n", offset, actualQuads);
}
-#endif
-
-
-#ifdef USE_HERMIT
-void Octree::countIntersection( UCHAR* node, int height, int& nedge, int& ncell, int& nface )
+void Octree::countIntersection(Node* node, int height, int& nedge, int& ncell, int& nface)
{
- if ( height > 0 )
+ if(height > 0)
{
- int total = getNumChildren( node ) ;
- for ( int i = 0 ; i < total ; i ++ )
+ int total = getNumChildren(&node->internal);
+ for(int i = 0; i < total; i ++)
{
- countIntersection( getChild( node, i ), height - 1, nedge, ncell, nface ) ;
+ countIntersection(getChild(&node->internal, i), height - 1, nedge, ncell, nface);
}
}
else
{
- nedge += getNumEdges2( node ) ;
+ nedge += getNumEdges2(&node->leaf);
- int smask = getSignMask( node ) ;
+ int smask = getSignMask(&node->leaf);
if(use_manifold)
{
- int comps = manifold_table[ smask ].comps ;
- ncell += comps ;
+ int comps = manifold_table[smask].comps;
+ ncell += comps;
}
else {
- if ( smask > 0 && smask < 255 )
+ if(smask > 0 && smask < 255)
{
- ncell ++ ;
+ ncell ++;
}
}
- for ( int i = 0 ; i < 3 ; i ++ )
+ for(int i = 0; i < 3; i ++)
{
- if ( getFaceEdgeNum( node, i * 2 ) )
+ if(getFaceEdgeNum(&node->leaf, i * 2))
{
- nface ++ ;
+ nface ++;
}
}
}
@@ -3497,213 +2313,203 @@ void solve_least_squares(const float halfA[], const float b[],
void minimize(float rvalue[3], float mp[3], const float pts[12][3],
const float norms[12][3], const int parity[12])
{
- float ata[6] = { 0, 0, 0, 0, 0, 0 };
- float atb[3] = { 0, 0, 0 } ;
- int ec = 0 ;
+ float ata[6] = {0, 0, 0, 0, 0, 0};
+ float atb[3] = {0, 0, 0};
+ int ec = 0;
- for ( int i = 0 ; i < 12 ; i ++ )
+ for(int i = 0; i < 12; i ++)
{
- // if ( getEdgeParity( leaf, i) )
- if ( parity[ i ] )
+ // if(getEdgeParity(leaf, i))
+ if(parity[i])
{
- const float* norm = norms[i] ;
- const float* p = pts[i] ;
+ const float* norm = norms[i];
+ const float* p = pts[i];
// QEF
- ata[ 0 ] += (float) ( norm[ 0 ] * norm[ 0 ] );
- ata[ 1 ] += (float) ( norm[ 0 ] * norm[ 1 ] );
- ata[ 2 ] += (float) ( norm[ 0 ] * norm[ 2 ] );
- ata[ 3 ] += (float) ( norm[ 1 ] * norm[ 1 ] );
- ata[ 4 ] += (float) ( norm[ 1 ] * norm[ 2 ] );
- ata[ 5 ] += (float) ( norm[ 2 ] * norm[ 2 ] );
+ ata[0] +=(float)(norm[0] * norm[0]);
+ ata[1] +=(float)(norm[0] * norm[1]);
+ ata[2] +=(float)(norm[0] * norm[2]);
+ ata[3] +=(float)(norm[1] * norm[1]);
+ ata[4] +=(float)(norm[1] * norm[2]);
+ ata[5] +=(float)(norm[2] * norm[2]);
- double pn = p[0] * norm[0] + p[1] * norm[1] + p[2] * norm[2] ;
+ double pn = p[0] * norm[0] + p[1] * norm[1] + p[2] * norm[2];
- atb[ 0 ] += (float) ( norm[ 0 ] * pn ) ;
- atb[ 1 ] += (float) ( norm[ 1 ] * pn ) ;
- atb[ 2 ] += (float) ( norm[ 2 ] * pn ) ;
+ atb[0] +=(float)(norm[0] * pn);
+ atb[1] +=(float)(norm[1] * pn);
+ atb[2] +=(float)(norm[2] * pn);
// Minimizer
- mp[0] += p[0] ;
- mp[1] += p[1] ;
- mp[2] += p[2] ;
+ mp[0] += p[0];
+ mp[1] += p[1];
+ mp[2] += p[2];
- ec ++ ;
+ ec ++;
}
}
- if ( ec == 0 )
+ if(ec == 0)
{
- return ;
+ return;
}
- mp[0] /= ec ;
- mp[1] /= ec ;
- mp[2] /= ec ;
+ mp[0] /= ec;
+ mp[1] /= ec;
+ mp[2] /= ec;
// Solve least squares
solve_least_squares(ata, atb, mp, rvalue);
}
-void Octree::computeMinimizer( UCHAR* leaf, int st[3], int len, float rvalue[3] )
+void Octree::computeMinimizer(LeafNode* leaf, int st[3], int len, float rvalue[3])
{
// First, gather all edge intersections
- float pts[12][3], norms[12][3] ;
- // fillEdgeIntersections( leaf, st, len, pts, norms ) ;
- int parity[12] ;
- fillEdgeIntersections( leaf, st, len, pts, norms, parity ) ;
+ float pts[12][3], norms[12][3];
+ int parity[12];
+ fillEdgeIntersections(leaf, st, len, pts, norms, parity);
// Next, construct QEF and minimizer
float mp[3] = {0, 0, 0};
minimize(rvalue, mp, pts, norms, parity);
/* Restraining the location of the minimizer */
- float nh1 = hermite_num * len ;
- float nh2 = ( 1 + hermite_num ) * len ;
+ float nh1 = hermite_num * len;
+ float nh2 =(1 + hermite_num) * len;
if((mode == DUALCON_MASS_POINT || mode == DUALCON_CENTROID) ||
- ( rvalue[0] < st[0] - nh1 || rvalue[1] < st[1] - nh1 || rvalue[2] < st[2] - nh1 ||
- rvalue[0] > st[0] + nh2 || rvalue[1] > st[1] + nh2 || rvalue[2] > st[2] + nh2 ))
+ (rvalue[0] < st[0] - nh1 || rvalue[1] < st[1] - nh1 || rvalue[2] < st[2] - nh1 ||
+ rvalue[0] > st[0] + nh2 || rvalue[1] > st[1] + nh2 || rvalue[2] > st[2] + nh2))
{
if(mode == DUALCON_CENTROID) {
// Use centroids
- rvalue[0] = (float) st[0] + len / 2 ;
- rvalue[1] = (float) st[1] + len / 2 ;
- rvalue[2] = (float) st[2] + len / 2 ;
+ rvalue[0] =(float) st[0] + len / 2;
+ rvalue[1] =(float) st[1] + len / 2;
+ rvalue[2] =(float) st[2] + len / 2;
}
else {
// Use mass point instead
- rvalue[0] = mp[0] ;
- rvalue[1] = mp[1] ;
- rvalue[2] = mp[2] ;
+ rvalue[0] = mp[0];
+ rvalue[1] = mp[1];
+ rvalue[2] = mp[2];
}
}
}
-void Octree::generateMinimizer( UCHAR* node, int st[3], int len, int height, int& offset )
+void Octree::generateMinimizer(Node* node, int st[3], int len, int height, int& offset)
{
- int i, j ;
+ int i, j;
- if ( height == 0 )
+ if(height == 0)
{
// Leaf cell, generate
// First, find minimizer
- float rvalue[3] ;
- rvalue[0] = (float) st[0] + len / 2 ;
- rvalue[1] = (float) st[1] + len / 2 ;
- rvalue[2] = (float) st[2] + len / 2 ;
- computeMinimizer( node, st, len, rvalue ) ;
+ float rvalue[3];
+ rvalue[0] =(float) st[0] + len / 2;
+ rvalue[1] =(float) st[1] + len / 2;
+ rvalue[2] =(float) st[2] + len / 2;
+ computeMinimizer(&node->leaf, st, len, rvalue);
// Update
- //float fnst[3] ;
- for ( j = 0 ; j < 3 ; j ++ )
+ //float fnst[3];
+ for(j = 0; j < 3; j ++)
{
- rvalue[ j ] = rvalue[ j ] * range / dimen + origin[ j ] ;
- //fnst[ j ] = st[ j ] * range / dimen + origin[ j ] ;
+ rvalue[j] = rvalue[j] * range / dimen + origin[j];
+ //fnst[j] = st[j] * range / dimen + origin[j];
}
- int mult = 0, smask = getSignMask( node ) ;
+ int mult = 0, smask = getSignMask(&node->leaf);
if(use_manifold)
{
- mult = manifold_table[ smask ].comps ;
+ mult = manifold_table[smask].comps;
}
else
{
- if ( smask > 0 && smask < 255 )
+ if(smask > 0 && smask < 255)
{
- mult = 1 ;
+ mult = 1;
}
}
- for ( j = 0 ; j < mult ; j ++ )
+ for(j = 0; j < mult; j ++)
{
add_vert(output_mesh, rvalue);
}
// Store the index
- setMinimizerIndex( node, offset ) ;
+ setMinimizerIndex(&node->leaf, offset);
- offset += mult ;
+ offset += mult;
}
else
{
// Internal cell, recur
- int count = 0 ;
- len >>= 1 ;
- for ( i = 0 ; i < 8 ; i ++ )
+ int count = 0;
+ len >>= 1;
+ for(i = 0; i < 8; i ++)
{
- if ( hasChild( node, i ) )
+ if(hasChild(&node->internal, i))
{
- int nst[3] ;
- nst[0] = st[0] + vertmap[i][0] * len ;
- nst[1] = st[1] + vertmap[i][1] * len ;
- nst[2] = st[2] + vertmap[i][2] * len ;
+ int nst[3];
+ nst[0] = st[0] + vertmap[i][0] * len;
+ nst[1] = st[1] + vertmap[i][1] * len;
+ nst[2] = st[2] + vertmap[i][2] * len;
- generateMinimizer( getChild( node, count ), nst, len, height - 1, offset ) ;
- count ++ ;
+ generateMinimizer(getChild(&node->internal, count),
+ nst, len, height - 1, offset);
+ count ++;
}
}
}
}
-void Octree::processEdgeWrite( UCHAR* node[4], int depth[4], int maxdep, int dir )
+void Octree::processEdgeWrite(Node* node[4], int depth[4], int maxdep, int dir)
{
- //int color = 0 ;
+ //int color = 0;
- int i = 3 ;
+ int i = 3;
{
- if ( getEdgeParity( node[i], processEdgeMask[dir][i] ) )
+ if(getEdgeParity((LeafNode*)(node[i]), processEdgeMask[dir][i]))
{
- int flip = 0 ;
- int edgeind = processEdgeMask[dir][i] ;
- if ( getSign( node[i], edgemap[ edgeind ][ 1 ] ) > 0 )
+ int flip = 0;
+ int edgeind = processEdgeMask[dir][i];
+ if(getSign((LeafNode*)node[i], edgemap[edgeind][1]) > 0)
{
- flip = 1 ;
+ flip = 1;
}
- int num = 0 ;
+ int num = 0;
{
int ind[8];
if(use_manifold)
{
/* Deprecated
int ind[4] = {
- getMinimizerIndex( node[0], processEdgeMask[dir][0] ),
- getMinimizerIndex( node[1], processEdgeMask[dir][1] ),
- getMinimizerIndex( node[3], processEdgeMask[dir][3] ),
- getMinimizerIndex( node[2], processEdgeMask[dir][2] )
- } ;
- num = 4 ;
+ getMinimizerIndex(node[0], processEdgeMask[dir][0]),
+ getMinimizerIndex(node[1], processEdgeMask[dir][1]),
+ getMinimizerIndex(node[3], processEdgeMask[dir][3]),
+ getMinimizerIndex(node[2], processEdgeMask[dir][2])
+ };
+ num = 4;
*/
- int vind[2] ;
+ int vind[2];
int seq[4] = {0,1,3,2};
- for ( int k = 0 ; k < 4 ; k ++ )
+ for(int k = 0; k < 4; k ++)
{
- getMinimizerIndices( node[seq[k]], processEdgeMask[dir][seq[k]], vind ) ;
- ind[num] = vind[0] ;
- num ++ ;
+ getMinimizerIndices((LeafNode*)(node[seq[k]]), processEdgeMask[dir][seq[k]], vind);
+ ind[num] = vind[0];
+ num ++;
- if ( vind[1] != -1 )
+ if(vind[1] != -1)
{
- ind[num] = vind[1] ;
- num ++ ;
- if ( flip == 0 )
+ ind[num] = vind[1];
+ num ++;
+ if(flip == 0)
{
- ind[num-1] = vind[0] ;
- ind[num-2] = vind[1] ;
+ ind[num-1] = vind[0];
+ ind[num-2] = vind[1];
}
}
}
-#ifdef TESTMANIFOLD
- if ( num != 4 )
- {
- dc_printf("Polygon: %d\n", num);
- }
- for ( k = 0 ; k < num ; k ++ )
- {
- fprintf(testfout, "{%d,%d},", ind[k], ind[(k+1)%num] );
- }
-#endif
/* we don't use the manifold option, but if it is
ever enabled again note that it can output
@@ -3711,498 +2517,505 @@ void Octree::processEdgeWrite( UCHAR* node[4], int depth[4], int maxdep, int dir
}
else {
if(flip) {
- ind[0] = getMinimizerIndex( node[2] );
- ind[1] = getMinimizerIndex( node[3] );
- ind[2] = getMinimizerIndex( node[1] );
- ind[3] = getMinimizerIndex( node[0] );
+ ind[0] = getMinimizerIndex((LeafNode*)(node[2]));
+ ind[1] = getMinimizerIndex((LeafNode*)(node[3]));
+ ind[2] = getMinimizerIndex((LeafNode*)(node[1]));
+ ind[3] = getMinimizerIndex((LeafNode*)(node[0]));
}
else {
- ind[0] = getMinimizerIndex( node[0] );
- ind[1] = getMinimizerIndex( node[1] );
- ind[2] = getMinimizerIndex( node[3] );
- ind[3] = getMinimizerIndex( node[2] );
+ ind[0] = getMinimizerIndex((LeafNode*)(node[0]));
+ ind[1] = getMinimizerIndex((LeafNode*)(node[1]));
+ ind[2] = getMinimizerIndex((LeafNode*)(node[3]));
+ ind[3] = getMinimizerIndex((LeafNode*)(node[2]));
}
add_quad(output_mesh, ind);
}
/*
- if ( this->outType == 0 )
+ if(outType == 0)
{
// OFF
- num = ( color ? -num : num ) ;
+ num =(color ? -num : num);
fprintf(fout, "%d ", num);
- if ( flip )
+ if(flip)
{
- for ( int k = num - 1 ; k >= 0 ; k -- )
+ for(int k = num - 1; k >= 0; k --)
{
- fprintf(fout, "%d ", ind[k] ) ;
+ fprintf(fout, "%d ", ind[k]);
}
}
else
{
- for ( int k = 0 ; k < num ; k ++ )
+ for(int k = 0; k < num; k ++)
{
- fprintf(fout, "%d ", ind[k] ) ;
+ fprintf(fout, "%d ", ind[k]);
}
}
- fprintf( fout, "\n") ;
+ fprintf(fout, "\n");
- actualQuads ++ ;
+ actualQuads ++;
}
- else if ( this->outType == 1 )
+ else if(outType == 1)
{
// PLY
- if ( flip )
+ if(flip)
{
int tind[8];
- for ( int k = num - 1 ; k >= 0 ; k -- )
+ for(int k = num - 1; k >= 0; k --)
{
- tind[k] = ind[num-1-k] ;
+ tind[k] = ind[num-1-k];
}
- // PLYWriter::writeFace( fout, num, tind ) ;
+ // PLYWriter::writeFace(fout, num, tind);
}
else
{
- // PLYWriter::writeFace( fout, num, ind ) ;
+ // PLYWriter::writeFace(fout, num, ind);
}
- actualQuads ++ ;
+ actualQuads ++;
}*/
}
- return ;
+ return;
}
else
{
- return ;
+ return;
}
}
}
-void Octree::edgeProcContour( UCHAR* node[4], int leaf[4], int depth[4], int maxdep, int dir )
+void Octree::edgeProcContour(Node* node[4], int leaf[4], int depth[4], int maxdep, int dir)
{
- if ( ! ( node[0] && node[1] && node[2] && node[3] ) )
+ if(!(node[0] && node[1] && node[2] && node[3]))
{
- return ;
+ return;
}
- if ( leaf[0] && leaf[1] && leaf[2] && leaf[3] )
+ if(leaf[0] && leaf[1] && leaf[2] && leaf[3])
{
- processEdgeWrite( node, depth, maxdep, dir ) ;
+ processEdgeWrite(node, depth, maxdep, dir);
}
else
{
- int i, j ;
- UCHAR* chd[ 4 ][ 8 ] ;
- for ( j = 0 ; j < 4 ; j ++ )
+ int i, j;
+ Node* chd[4][8];
+ for(j = 0; j < 4; j ++)
{
- for ( i = 0 ; i < 8 ; i ++ )
+ for(i = 0; i < 8; i ++)
{
- chd[ j ][ i ] = ((!leaf[j]) && hasChild( node[j], i ) )? getChild( node[j], getChildCount( node[j], i ) ) : NULL ;
+ chd[j][i] = ((!leaf[j]) && hasChild(&node[j]->internal, i)) ?
+ getChild(&node[j]->internal,
+ getChildCount(&node[j]->internal, i)) : NULL;
}
}
// 2 edge calls
- UCHAR* ne[4] ;
- int le[4] ;
- int de[4] ;
- for ( i = 0 ; i < 2 ; i ++ )
+ Node* ne[4];
+ int le[4];
+ int de[4];
+ for(i = 0; i < 2; i ++)
{
- int c[ 4 ] = { edgeProcEdgeMask[ dir ][ i ][ 0 ],
- edgeProcEdgeMask[ dir ][ i ][ 1 ],
- edgeProcEdgeMask[ dir ][ i ][ 2 ],
- edgeProcEdgeMask[ dir ][ i ][ 3 ] } ;
+ int c[4] = {edgeProcEdgeMask[dir][i][0],
+ edgeProcEdgeMask[dir][i][1],
+ edgeProcEdgeMask[dir][i][2],
+ edgeProcEdgeMask[dir][i][3]};
- for ( int j = 0 ; j < 4 ; j ++ )
+ for(int j = 0; j < 4; j ++)
{
- if ( leaf[j] )
+ if(leaf[j])
{
- le[j] = leaf[j] ;
- ne[j] = node[j] ;
- de[j] = depth[j] ;
+ le[j] = leaf[j];
+ ne[j] = node[j];
+ de[j] = depth[j];
}
else
{
- le[j] = isLeaf( node[j], c[j] ) ;
- ne[j] = chd[ j ][ c[j] ] ;
- de[j] = depth[j] - 1 ;
+ le[j] = isLeaf(&node[j]->internal, c[j]);
+ ne[j] = chd[j][c[j]];
+ de[j] = depth[j] - 1;
}
}
- edgeProcContour( ne, le, de, maxdep - 1, edgeProcEdgeMask[ dir ][ i ][ 4 ] ) ;
+ edgeProcContour(ne, le, de, maxdep - 1, edgeProcEdgeMask[dir][i][4]);
}
}
}
-void Octree::faceProcContour( UCHAR* node[2], int leaf[2], int depth[2], int maxdep, int dir )
+void Octree::faceProcContour(Node* node[2], int leaf[2], int depth[2], int maxdep, int dir)
{
- if ( ! ( node[0] && node[1] ) )
+ if(!(node[0] && node[1]))
{
- return ;
+ return;
}
- if ( ! ( leaf[0] && leaf[1] ) )
+ if(!(leaf[0] && leaf[1]))
{
- int i, j ;
+ int i, j;
// Fill children nodes
- UCHAR* chd[ 2 ][ 8 ] ;
- for ( j = 0 ; j < 2 ; j ++ )
+ Node* chd[2][8];
+ for(j = 0; j < 2; j ++)
{
- for ( i = 0 ; i < 8 ; i ++ )
+ for(i = 0; i < 8; i ++)
{
- chd[ j ][ i ] = ((!leaf[j]) && hasChild( node[j], i )) ? getChild( node[j], getChildCount( node[j], i ) ) : NULL ;
+ chd[j][i] =((!leaf[j]) && hasChild(&node[j]->internal, i)) ?
+ getChild(&node[j]->internal,
+ getChildCount(&node[j]->internal, i)) : NULL;
}
}
// 4 face calls
- UCHAR* nf[2] ;
- int df[2] ;
- int lf[2] ;
- for ( i = 0 ; i < 4 ; i ++ )
+ Node* nf[2];
+ int df[2];
+ int lf[2];
+ for(i = 0; i < 4; i ++)
{
- int c[2] = { faceProcFaceMask[ dir ][ i ][ 0 ], faceProcFaceMask[ dir ][ i ][ 1 ] };
- for ( int j = 0 ; j < 2 ; j ++ )
+ int c[2] = {faceProcFaceMask[dir][i][0], faceProcFaceMask[dir][i][1]};
+ for(int j = 0; j < 2; j ++)
{
- if ( leaf[j] )
+ if(leaf[j])
{
- lf[j] = leaf[j] ;
- nf[j] = node[j] ;
- df[j] = depth[j] ;
+ lf[j] = leaf[j];
+ nf[j] = node[j];
+ df[j] = depth[j];
}
else
{
- lf[j] = isLeaf( node[j], c[j] ) ;
- nf[j] = chd[ j ][ c[j] ] ;
- df[j] = depth[j] - 1 ;
+ lf[j] = isLeaf(&node[j]->internal, c[j]);
+ nf[j] = chd[j][c[j]];
+ df[j] = depth[j] - 1;
}
}
- faceProcContour( nf, lf, df, maxdep - 1, faceProcFaceMask[ dir ][ i ][ 2 ] ) ;
+ faceProcContour(nf, lf, df, maxdep - 1, faceProcFaceMask[dir][i][2]);
}
// 4 edge calls
- int orders[2][4] = {{ 0, 0, 1, 1 }, { 0, 1, 0, 1 }} ;
- UCHAR* ne[4] ;
- int le[4] ;
- int de[4] ;
+ int orders[2][4] = {{0, 0, 1, 1}, {0, 1, 0, 1}};
+ Node* ne[4];
+ int le[4];
+ int de[4];
- for ( i = 0 ; i < 4 ; i ++ )
+ for(i = 0; i < 4; i ++)
{
- int c[4] = { faceProcEdgeMask[ dir ][ i ][ 1 ], faceProcEdgeMask[ dir ][ i ][ 2 ],
- faceProcEdgeMask[ dir ][ i ][ 3 ], faceProcEdgeMask[ dir ][ i ][ 4 ] };
- int* order = orders[ faceProcEdgeMask[ dir ][ i ][ 0 ] ] ;
+ int c[4] = {faceProcEdgeMask[dir][i][1], faceProcEdgeMask[dir][i][2],
+ faceProcEdgeMask[dir][i][3], faceProcEdgeMask[dir][i][4]};
+ int* order = orders[faceProcEdgeMask[dir][i][0]];
- for ( int j = 0 ; j < 4 ; j ++ )
+ for(int j = 0; j < 4; j ++)
{
- if ( leaf[order[j]] )
+ if(leaf[order[j]])
{
- le[j] = leaf[order[j]] ;
- ne[j] = node[order[j]] ;
- de[j] = depth[order[j]] ;
+ le[j] = leaf[order[j]];
+ ne[j] = node[order[j]];
+ de[j] = depth[order[j]];
}
else
{
- le[j] = isLeaf( node[order[j]], c[j] ) ;
- ne[j] = chd[ order[ j ] ][ c[j] ] ;
- de[j] = depth[order[j]] - 1 ;
+ le[j] = isLeaf(&node[order[j]]->internal, c[j]);
+ ne[j] = chd[order[j]][c[j]];
+ de[j] = depth[order[j]] - 1;
}
}
- edgeProcContour( ne, le, de, maxdep - 1, faceProcEdgeMask[ dir ][ i ][ 5 ] ) ;
+ edgeProcContour(ne, le, de, maxdep - 1, faceProcEdgeMask[dir][i][5]);
}
}
}
-void Octree::cellProcContour( UCHAR* node, int leaf, int depth )
+void Octree::cellProcContour(Node* node, int leaf, int depth)
{
- if ( node == NULL )
+ if(node == NULL)
{
- return ;
+ return;
}
- if ( ! leaf )
+ if(! leaf)
{
- int i ;
+ int i;
// Fill children nodes
- UCHAR* chd[ 8 ] ;
- for ( i = 0 ; i < 8 ; i ++ )
+ Node* chd[8];
+ for(i = 0; i < 8; i ++)
{
- chd[ i ] = ((!leaf) && hasChild( node, i )) ? getChild( node, getChildCount( node, i ) ) : NULL ;
+ chd[i] =((!leaf) && hasChild(&node->internal, i)) ?
+ getChild(&node->internal,
+ getChildCount(&node->internal, i)) : NULL;
}
// 8 Cell calls
- for ( i = 0 ; i < 8 ; i ++ )
+ for(i = 0; i < 8; i ++)
{
- cellProcContour( chd[ i ], isLeaf( node, i ), depth - 1 ) ;
+ cellProcContour(chd[i], isLeaf(&node->internal, i), depth - 1);
}
// 12 face calls
- UCHAR* nf[2] ;
- int lf[2] ;
- int df[2] = { depth - 1, depth - 1 } ;
- for ( i = 0 ; i < 12 ; i ++ )
+ Node* nf[2];
+ int lf[2];
+ int df[2] = {depth - 1, depth - 1};
+ for(i = 0; i < 12; i ++)
{
- int c[ 2 ] = { cellProcFaceMask[ i ][ 0 ], cellProcFaceMask[ i ][ 1 ] };
+ int c[2] = {cellProcFaceMask[i][0], cellProcFaceMask[i][1]};
- lf[0] = isLeaf( node, c[0] ) ;
- lf[1] = isLeaf( node, c[1] ) ;
+ lf[0] = isLeaf(&node->internal, c[0]);
+ lf[1] = isLeaf(&node->internal, c[1]);
- nf[0] = chd[ c[0] ] ;
- nf[1] = chd[ c[1] ] ;
+ nf[0] = chd[c[0]];
+ nf[1] = chd[c[1]];
- faceProcContour( nf, lf, df, depth - 1, cellProcFaceMask[ i ][ 2 ] ) ;
+ faceProcContour(nf, lf, df, depth - 1, cellProcFaceMask[i][2]);
}
// 6 edge calls
- UCHAR* ne[4] ;
- int le[4] ;
- int de[4] = { depth - 1, depth - 1, depth - 1, depth - 1 } ;
- for ( i = 0 ; i < 6 ; i ++ )
+ Node* ne[4];
+ int le[4];
+ int de[4] = {depth - 1, depth - 1, depth - 1, depth - 1};
+ for(i = 0; i < 6; i ++)
{
- int c[ 4 ] = { cellProcEdgeMask[ i ][ 0 ], cellProcEdgeMask[ i ][ 1 ], cellProcEdgeMask[ i ][ 2 ], cellProcEdgeMask[ i ][ 3 ] };
+ int c[4] = {cellProcEdgeMask[i][0], cellProcEdgeMask[i][1], cellProcEdgeMask[i][2], cellProcEdgeMask[i][3]};
- for ( int j = 0 ; j < 4 ; j ++ )
+ for(int j = 0; j < 4; j ++)
{
- le[j] = isLeaf( node, c[j] ) ;
- ne[j] = chd[ c[j] ] ;
+ le[j] = isLeaf(&node->internal, c[j]);
+ ne[j] = chd[c[j]];
}
- edgeProcContour( ne, le, de, depth - 1, cellProcEdgeMask[ i ][ 4 ] ) ;
+ edgeProcContour(ne, le, de, depth - 1, cellProcEdgeMask[i][4]);
}
}
}
-#endif
-
-
-
-void Octree::processEdgeParity( UCHAR* node[4], int depth[4], int maxdep, int dir )
+void Octree::processEdgeParity(LeafNode* node[4], int depth[4], int maxdep, int dir)
{
- int con = 0 ;
- for ( int i = 0 ; i < 4 ; i ++ )
+ int con = 0;
+ for(int i = 0; i < 4; i ++)
{
// Minimal cell
- // if ( op == 0 )
+ // if(op == 0)
{
- if ( getEdgeParity( node[i], processEdgeMask[dir][i] ) )
+ if(getEdgeParity(node[i], processEdgeMask[dir][i]))
{
- con = 1 ;
- break ;
+ con = 1;
+ break;
}
}
}
- if ( con == 1 )
+ if(con == 1)
{
- for ( int i = 0 ; i < 4 ; i ++ )
+ for(int i = 0; i < 4; i ++)
{
- setEdge( node[ i ], processEdgeMask[dir][i] ) ;
+ setEdge(node[i], processEdgeMask[dir][i]);
}
}
}
-void Octree::edgeProcParity( UCHAR* node[4], int leaf[4], int depth[4], int maxdep, int dir )
+void Octree::edgeProcParity(Node* node[4], int leaf[4], int depth[4], int maxdep, int dir)
{
- if ( ! ( node[0] && node[1] && node[2] && node[3] ) )
+ if(!(node[0] && node[1] && node[2] && node[3]))
{
- return ;
+ return;
}
- if ( leaf[0] && leaf[1] && leaf[2] && leaf[3] )
+ if(leaf[0] && leaf[1] && leaf[2] && leaf[3])
{
- processEdgeParity( node, depth, maxdep, dir ) ;
+ processEdgeParity((LeafNode**)node, depth, maxdep, dir);
}
else
{
- int i, j ;
- UCHAR* chd[ 4 ][ 8 ] ;
- for ( j = 0 ; j < 4 ; j ++ )
+ int i, j;
+ Node* chd[4][8];
+ for(j = 0; j < 4; j ++)
{
- for ( i = 0 ; i < 8 ; i ++ )
+ for(i = 0; i < 8; i ++)
{
- chd[ j ][ i ] = ((!leaf[j]) && hasChild( node[j], i ) )? getChild( node[j], getChildCount( node[j], i ) ) : NULL ;
+ chd[j][i] =((!leaf[j]) && hasChild(&node[j]->internal, i)) ?
+ getChild(&node[j]->internal, getChildCount(&node[j]->internal, i)) : NULL;
}
}
// 2 edge calls
- UCHAR* ne[4] ;
- int le[4] ;
- int de[4] ;
- for ( i = 0 ; i < 2 ; i ++ )
+ Node* ne[4];
+ int le[4];
+ int de[4];
+ for(i = 0; i < 2; i ++)
{
- int c[ 4 ] = { edgeProcEdgeMask[ dir ][ i ][ 0 ],
- edgeProcEdgeMask[ dir ][ i ][ 1 ],
- edgeProcEdgeMask[ dir ][ i ][ 2 ],
- edgeProcEdgeMask[ dir ][ i ][ 3 ] } ;
+ int c[4] = {edgeProcEdgeMask[dir][i][0],
+ edgeProcEdgeMask[dir][i][1],
+ edgeProcEdgeMask[dir][i][2],
+ edgeProcEdgeMask[dir][i][3]};
- // int allleaf = 1 ;
- for ( int j = 0 ; j < 4 ; j ++ )
+ // int allleaf = 1;
+ for(int j = 0; j < 4; j ++)
{
- if ( leaf[j] )
+ if(leaf[j])
{
- le[j] = leaf[j] ;
- ne[j] = node[j] ;
- de[j] = depth[j] ;
+ le[j] = leaf[j];
+ ne[j] = node[j];
+ de[j] = depth[j];
}
else
{
- le[j] = isLeaf( node[j], c[j] ) ;
- ne[j] = chd[ j ][ c[j] ] ;
- de[j] = depth[j] - 1 ;
+ le[j] = isLeaf(&node[j]->internal, c[j]);
+ ne[j] = chd[j][c[j]];
+ de[j] = depth[j] - 1;
}
}
- edgeProcParity( ne, le, de, maxdep - 1, edgeProcEdgeMask[ dir ][ i ][ 4 ] ) ;
+ edgeProcParity(ne, le, de, maxdep - 1, edgeProcEdgeMask[dir][i][4]);
}
}
}
-void Octree::faceProcParity( UCHAR* node[2], int leaf[2], int depth[2], int maxdep, int dir )
+void Octree::faceProcParity(Node* node[2], int leaf[2], int depth[2], int maxdep, int dir)
{
- if ( ! ( node[0] && node[1] ) )
+ if(!(node[0] && node[1]))
{
- return ;
+ return;
}
- if ( ! ( leaf[0] && leaf[1] ) )
+ if(!(leaf[0] && leaf[1]))
{
- int i, j ;
+ int i, j;
// Fill children nodes
- UCHAR* chd[ 2 ][ 8 ] ;
- for ( j = 0 ; j < 2 ; j ++ )
+ Node* chd[2][8];
+ for(j = 0; j < 2; j ++)
{
- for ( i = 0 ; i < 8 ; i ++ )
+ for(i = 0; i < 8; i ++)
{
- chd[ j ][ i ] = ((!leaf[j]) && hasChild( node[j], i )) ? getChild( node[j], getChildCount( node[j], i ) ) : NULL ;
+ chd[j][i] =((!leaf[j]) && hasChild(&node[j]->internal, i)) ?
+ getChild(&node[j]->internal,
+ getChildCount(&node[j]->internal, i)) : NULL;
}
}
// 4 face calls
- UCHAR* nf[2] ;
- int df[2] ;
- int lf[2] ;
- for ( i = 0 ; i < 4 ; i ++ )
+ Node* nf[2];
+ int df[2];
+ int lf[2];
+ for(i = 0; i < 4; i ++)
{
- int c[2] = { faceProcFaceMask[ dir ][ i ][ 0 ], faceProcFaceMask[ dir ][ i ][ 1 ] };
- for ( int j = 0 ; j < 2 ; j ++ )
+ int c[2] = {faceProcFaceMask[dir][i][0], faceProcFaceMask[dir][i][1]};
+ for(int j = 0; j < 2; j ++)
{
- if ( leaf[j] )
+ if(leaf[j])
{
- lf[j] = leaf[j] ;
- nf[j] = node[j] ;
- df[j] = depth[j] ;
+ lf[j] = leaf[j];
+ nf[j] = node[j];
+ df[j] = depth[j];
}
else
{
- lf[j] = isLeaf( node[j], c[j] ) ;
- nf[j] = chd[ j ][ c[j] ] ;
- df[j] = depth[j] - 1 ;
+ lf[j] = isLeaf(&node[j]->internal, c[j]);
+ nf[j] = chd[j][c[j]];
+ df[j] = depth[j] - 1;
}
}
- faceProcParity( nf, lf, df, maxdep - 1, faceProcFaceMask[ dir ][ i ][ 2 ] ) ;
+ faceProcParity(nf, lf, df, maxdep - 1, faceProcFaceMask[dir][i][2]);
}
// 4 edge calls
- int orders[2][4] = {{ 0, 0, 1, 1 }, { 0, 1, 0, 1 }} ;
- UCHAR* ne[4] ;
- int le[4] ;
- int de[4] ;
+ int orders[2][4] = {{0, 0, 1, 1}, {0, 1, 0, 1}};
+ Node* ne[4];
+ int le[4];
+ int de[4];
- for ( i = 0 ; i < 4 ; i ++ )
+ for(i = 0; i < 4; i ++)
{
- int c[4] = { faceProcEdgeMask[ dir ][ i ][ 1 ], faceProcEdgeMask[ dir ][ i ][ 2 ],
- faceProcEdgeMask[ dir ][ i ][ 3 ], faceProcEdgeMask[ dir ][ i ][ 4 ] };
- int* order = orders[ faceProcEdgeMask[ dir ][ i ][ 0 ] ] ;
+ int c[4] = {faceProcEdgeMask[dir][i][1], faceProcEdgeMask[dir][i][2],
+ faceProcEdgeMask[dir][i][3], faceProcEdgeMask[dir][i][4]};
+ int* order = orders[faceProcEdgeMask[dir][i][0]];
- for ( int j = 0 ; j < 4 ; j ++ )
+ for(int j = 0; j < 4; j ++)
{
- if ( leaf[order[j]] )
+ if(leaf[order[j]])
{
- le[j] = leaf[order[j]] ;
- ne[j] = node[order[j]] ;
- de[j] = depth[order[j]] ;
+ le[j] = leaf[order[j]];
+ ne[j] = node[order[j]];
+ de[j] = depth[order[j]];
}
else
{
- le[j] = isLeaf( node[order[j]], c[j] ) ;
- ne[j] = chd[ order[ j ] ][ c[j] ] ;
- de[j] = depth[order[j]] - 1 ;
+ le[j] = isLeaf((InternalNode*)(node[order[j]]), c[j]);
+ ne[j] = chd[order[j]][c[j]];
+ de[j] = depth[order[j]] - 1;
}
}
- edgeProcParity( ne, le, de, maxdep - 1, faceProcEdgeMask[ dir ][ i ][ 5 ] ) ;
+ edgeProcParity(ne, le, de, maxdep - 1, faceProcEdgeMask[dir][i][5]);
}
}
}
-void Octree::cellProcParity( UCHAR* node, int leaf, int depth )
+void Octree::cellProcParity(Node* node, int leaf, int depth)
{
- if ( node == NULL )
+ if(node == NULL)
{
- return ;
+ return;
}
- if ( ! leaf )
+ if(! leaf)
{
- int i ;
+ int i;
// Fill children nodes
- UCHAR* chd[ 8 ] ;
- for ( i = 0 ; i < 8 ; i ++ )
+ Node* chd[8];
+ for(i = 0; i < 8; i ++)
{
- chd[ i ] = ((!leaf) && hasChild( node, i )) ? getChild( node, getChildCount( node, i ) ) : NULL ;
+ chd[i] =((!leaf) && hasChild((InternalNode*)node, i)) ?
+ getChild((InternalNode*)node,
+ getChildCount((InternalNode*)node, i)) : NULL;
}
// 8 Cell calls
- for ( i = 0 ; i < 8 ; i ++ )
+ for(i = 0; i < 8; i ++)
{
- cellProcParity( chd[ i ], isLeaf( node, i ), depth - 1 ) ;
+ cellProcParity(chd[i], isLeaf((InternalNode*)node, i), depth - 1);
}
// 12 face calls
- UCHAR* nf[2] ;
- int lf[2] ;
- int df[2] = { depth - 1, depth - 1 } ;
- for ( i = 0 ; i < 12 ; i ++ )
+ Node* nf[2];
+ int lf[2];
+ int df[2] = {depth - 1, depth - 1};
+ for(i = 0; i < 12; i ++)
{
- int c[ 2 ] = { cellProcFaceMask[ i ][ 0 ], cellProcFaceMask[ i ][ 1 ] };
+ int c[2] = {cellProcFaceMask[i][0], cellProcFaceMask[i][1]};
- lf[0] = isLeaf( node, c[0] ) ;
- lf[1] = isLeaf( node, c[1] ) ;
+ lf[0] = isLeaf((InternalNode*)node, c[0]);
+ lf[1] = isLeaf((InternalNode*)node, c[1]);
- nf[0] = chd[ c[0] ] ;
- nf[1] = chd[ c[1] ] ;
+ nf[0] = chd[c[0]];
+ nf[1] = chd[c[1]];
- faceProcParity( nf, lf, df, depth - 1, cellProcFaceMask[ i ][ 2 ] ) ;
+ faceProcParity(nf, lf, df, depth - 1, cellProcFaceMask[i][2]);
}
// 6 edge calls
- UCHAR* ne[4] ;
- int le[4] ;
- int de[4] = { depth - 1, depth - 1, depth - 1, depth - 1 } ;
- for ( i = 0 ; i < 6 ; i ++ )
+ Node* ne[4];
+ int le[4];
+ int de[4] = {depth - 1, depth - 1, depth - 1, depth - 1};
+ for(i = 0; i < 6; i ++)
{
- int c[ 4 ] = { cellProcEdgeMask[ i ][ 0 ], cellProcEdgeMask[ i ][ 1 ], cellProcEdgeMask[ i ][ 2 ], cellProcEdgeMask[ i ][ 3 ] };
+ int c[4] = {cellProcEdgeMask[i][0], cellProcEdgeMask[i][1], cellProcEdgeMask[i][2], cellProcEdgeMask[i][3]};
- for ( int j = 0 ; j < 4 ; j ++ )
+ for(int j = 0; j < 4; j ++)
{
- le[j] = isLeaf( node, c[j] ) ;
- ne[j] = chd[ c[j] ] ;
+ le[j] = isLeaf((InternalNode*)node, c[j]);
+ ne[j] = chd[c[j]];
}
- edgeProcParity( ne, le, de, depth - 1, cellProcEdgeMask[ i ][ 4 ] ) ;
+ edgeProcParity(ne, le, de, depth - 1, cellProcEdgeMask[i][4]);
}
}
diff --git a/intern/dualcon/intern/octree.h b/intern/dualcon/intern/octree.h
index 7b5a626bddc..aac09549ee6 100644
--- a/intern/dualcon/intern/octree.h
+++ b/intern/dualcon/intern/octree.h
@@ -15,7 +15,7 @@
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
- * Contributor(s): Tao Ju
+ * Contributor(s): Tao Ju, Nicholas Bishop
*
* ***** END GPL LICENSE BLOCK *****
*/
@@ -23,6 +23,8 @@
#ifndef OCTREE_H
#define OCTREE_H
+#include <cassert>
+#include <cstring>
#include <stdio.h>
#include <math.h>
#include "GeoCommon.h"
@@ -50,52 +52,56 @@
// #define IN_VERBOSE_MODE
/* Set scan convert params */
-// Uncomment to use Dual Contouring on Hermit representation
-// for better sharp feature reproduction, but more mem is required
-// The number indicates how far do we allow the minimizer to shoot
-// outside the cell
-#define USE_HERMIT 1.0f
-
-#ifdef USE_HERMIT
-//#define CINDY
-#endif
-///#define QIANYI
+#define EDGE_FLOATS 4
-//#define TESTMANIFOLD
+union Node;
+struct InternalNode {
+ /* Treat as bitfield, bit N indicates whether child N exists or not */
+ unsigned char has_child;
+ /* Treat as bitfield, bit N indicates whether child N is a leaf or not */
+ unsigned char child_is_leaf;
-/* Set output options */
-// Comment out to prevent writing output files
-#define OUTPUT_REPAIRED
+ /* Can have up to eight children */
+ Node *children[0];
+};
-/* Set node bytes */
-#ifdef USE_HERMIT
-#define EDGE_BYTES 16
-#define EDGE_FLOATS 4
-#else
-#define EDGE_BYTES 4
-#define EDGE_FLOATS 1
-#endif
+/**
+ * Bits order
+ *
+ * Leaf node:
+ * Byte 0,1(0-11): edge parity
+ * Byte 1(4,5,6): mask of primary edges intersections stored
+ * Byte 1(7): in flood fill mode, whether the cell is in process
+ * Byte 2(0-8): signs
+ * Byte 3,4: in coloring mode, the mask for edges
+ * Byte 5: edge intersections(4 bytes per inter, or 12 bytes if USE_HERMIT)
+ */
+struct LeafNode /* TODO: remove this attribute once everything is fixed */ {
+ unsigned short edge_parity : 12;
+ unsigned short primary_edge_intersections : 3;
-#define CINDY_BYTES 0
+ /* XXX: maybe actually unused? */
+ unsigned short in_process : 1;
-/*#define LEAF_EXTRA_BYTES FLOOD_BYTES + CINDY_BYTES
+ /* bitfield */
+ char signs;
-#ifdef USE_HERMIT
-#define LEAF_NODE_BYTES 7 + LEAF_EXTRA_BYTES
-#else
-#define LEAF_NODE_BYTES 3 + LEAF_EXTRA_BYTES
-#endif*/
+ int minimizer_index;
+
+ unsigned short flood_fill;
-#define INTERNAL_NODE_BYTES 2
-#define POINTER_BYTES 8
-#define FLOOD_FILL_BYTES 2
+ float edge_intersections[0];
+};
-#define signtype short
-#define nodetype int
-#define numtype int
+/* Doesn't get directly allocated anywhere, just used for passing
+ pointers to nodes that could be internal or leaf. */
+union Node {
+ InternalNode internal;
+ LeafNode leaf;
+};
/* Global variables */
extern const int edgemask[3];
@@ -116,23 +122,23 @@ extern const int dirEdge[3][4];
struct PathElement
{
// Origin
- int pos[3] ;
+ int pos[3];
// link
- PathElement* next ;
+ PathElement* next;
};
struct PathList
{
// Head
- PathElement* head ;
- PathElement* tail ;
+ PathElement* head;
+ PathElement* tail;
// Length of the list
- int length ;
+ int length;
// Next list
- PathList* next ;
+ PathList* next;
};
@@ -145,78 +151,71 @@ public:
/* Public members */
/// Memory allocators
- VirtualMemoryAllocator * alloc[ 9 ] ;
- VirtualMemoryAllocator * leafalloc[ 4 ] ;
+ VirtualMemoryAllocator * alloc[9];
+ VirtualMemoryAllocator * leafalloc[4];
/// Root node
- UCHAR* root ;
+ Node* root;
/// Model reader
- ModelReader* reader ;
+ ModelReader* reader;
/// Marching cubes table
- Cubes* cubes ;
+ Cubes* cubes;
/// Length of grid
- int dimen ;
- int mindimen, minshift ;
+ int dimen;
+ int mindimen, minshift;
/// Maximum depth
- int maxDepth ;
+ int maxDepth;
/// The lower corner of the bounding box and the size
float origin[3];
float range;
/// Counting information
- int nodeCount ;
- int nodeSpace ;
- int nodeCounts[ 9 ] ;
+ int nodeCount;
+ int nodeSpace;
+ int nodeCounts[9];
- int actualQuads, actualVerts ;
+ int actualQuads, actualVerts;
- PathList* ringList ;
+ PathList* ringList;
- int maxTrianglePerCell ;
- int outType ; // 0 for OFF, 1 for PLY, 2 for VOL
+ int maxTrianglePerCell;
+ int outType; // 0 for OFF, 1 for PLY, 2 for VOL
// For flood filling
int use_flood_fill;
- float thresh ;
+ float thresh;
int use_manifold;
- // testing
- FILE* testfout ;
-
float hermite_num;
DualConMode mode;
- int leaf_node_bytes;
- int leaf_extra_bytes;
- int flood_bytes;
-
public:
/**
* Construtor
*/
- Octree ( ModelReader* mr,
+ Octree(ModelReader* mr,
DualConAllocOutput alloc_output_func,
DualConAddVert add_vert_func,
DualConAddQuad add_quad_func,
DualConFlags flags, DualConMode mode, int depth,
- float threshold, float hermite_num ) ;
+ float threshold, float hermite_num);
/**
* Destructor
*/
- ~Octree ( ) ;
+ ~Octree();
/**
* Scan convert
*/
- void scanConvert() ;
+ void scanConvert();
void *getOutputMesh() { return output_mesh; }
@@ -226,164 +225,129 @@ private:
/**
* Initialize memory allocators
*/
- void initMemory ( ) ;
+ void initMemory();
/**
* Release memory
*/
- void freeMemory ( ) ;
+ void freeMemory();
/**
* Print memory usage
*/
- void printMemUsage( ) ;
+ void printMemUsage();
/**
* Methods to set / restore minimum edges
*/
- void resetMinimalEdges( ) ;
+ void resetMinimalEdges();
- void cellProcParity ( UCHAR* node, int leaf, int depth ) ;
- void faceProcParity ( UCHAR* node[2], int leaf[2], int depth[2], int maxdep, int dir ) ;
- void edgeProcParity ( UCHAR* node[4], int leaf[4], int depth[4], int maxdep, int dir ) ;
+ void cellProcParity(Node* node, int leaf, int depth);
+ void faceProcParity(Node* node[2], int leaf[2], int depth[2], int maxdep, int dir);
+ void edgeProcParity(Node* node[4], int leaf[4], int depth[4], int maxdep, int dir);
- void processEdgeParity ( UCHAR* node[4], int depths[4], int maxdep, int dir ) ;
+ void processEdgeParity(LeafNode* node[4], int depths[4], int maxdep, int dir);
/**
* Add triangles to the tree
*/
- void addTrian ( );
- void addTrian ( Triangle* trian, int triind );
- UCHAR* addTrian ( UCHAR* node, Projections* p, int height );
+ void addTrian();
+ void addTrian(Triangle* trian, int triind);
+ InternalNode* addTrian(InternalNode* node, Projections* p, int height);
/**
* Method to update minimizer in a cell: update edge intersections instead
*/
- UCHAR* updateCell( UCHAR* node, Projections* p ) ;
+ LeafNode* updateCell(LeafNode* node, Projections* p);
/* Routines to detect and patch holes */
- int numRings ;
- int totRingLengths ;
- int maxRingLength ;
+ int numRings;
+ int totRingLengths;
+ int maxRingLength;
/**
* Entry routine.
*/
- void trace ( ) ;
+ void trace();
/**
* Trace the given node, find patches and fill them in
*/
- UCHAR* trace ( UCHAR* node, int* st, int len, int depth, PathList*& paths ) ;
+ Node* trace(Node* node, int* st, int len, int depth, PathList*& paths);
/**
* Look for path on the face and add to paths
*/
- void findPaths ( UCHAR* node[2], int leaf[2], int depth[2], int* st[2], int maxdep, int dir, PathList*& paths ) ;
+ void findPaths(Node* node[2], int leaf[2], int depth[2], int* st[2], int maxdep, int dir, PathList*& paths);
/**
* Combine two list1 and list2 into list1 using connecting paths list3,
* while closed paths are appended to rings
*/
- void combinePaths ( PathList*& list1, PathList* list2, PathList* paths, PathList*& rings ) ;
+ void combinePaths(PathList*& list1, PathList* list2, PathList* paths, PathList*& rings);
/**
* Helper function: combine current paths in list1 and list2 to a single path and append to list3
*/
- PathList* combineSinglePath ( PathList*& head1, PathList* pre1, PathList*& list1, PathList*& head2, PathList* pre2, PathList*& list2 ) ;
+ PathList* combineSinglePath(PathList*& head1, PathList* pre1, PathList*& list1, PathList*& head2, PathList* pre2, PathList*& list2);
/**
* Functions to patch rings in a node
*/
- UCHAR* patch ( UCHAR* node, int st[3], int len, PathList* rings ) ;
- UCHAR* patchSplit ( UCHAR* node, int st[3], int len, PathList* rings, int dir, PathList*& nrings1, PathList*& nrings2 ) ;
- UCHAR* patchSplitSingle ( UCHAR* node, int st[3], int len, PathElement* head, int dir, PathList*& nrings1, PathList*& nrings2 ) ;
- UCHAR* connectFace ( UCHAR* node, int st[3], int len, int dir, PathElement* f1, PathElement* f2 ) ;
- UCHAR* locateCell( UCHAR* node, int st[3], int len, int ori[3], int dir, int side, UCHAR*& rleaf, int rst[3], int& rlen ) ;
- void compressRing ( PathElement*& ring ) ;
- void getFacePoint( PathElement* leaf, int dir, int& x, int& y, float& p, float& q ) ;
- UCHAR* patchAdjacent( UCHAR* node, int len, int st1[3], UCHAR* leaf1, int st2[3], UCHAR* leaf2, int walkdir, int inc, int dir, int side, float alpha ) ;
- int findPair ( PathElement* head, int pos, int dir, PathElement*& pre1, PathElement*& pre2 ) ;
- int getSide( PathElement* e, int pos, int dir ) ;
- int isEqual( PathElement* e1, PathElement* e2 ) ;
- void preparePrimalEdgesMask( UCHAR* node ) ;
- void testFacePoint( PathElement* e1, PathElement* e2 ) ;
+ Node* patch(Node* node, int st[3], int len, PathList* rings);
+ Node* patchSplit(Node* node, int st[3], int len, PathList* rings, int dir, PathList*& nrings1, PathList*& nrings2);
+ Node* patchSplitSingle(Node* node, int st[3], int len, PathElement* head, int dir, PathList*& nrings1, PathList*& nrings2);
+ Node* connectFace(Node* node, int st[3], int len, int dir, PathElement* f1, PathElement* f2);
+ Node* locateCell(InternalNode* node, int st[3], int len, int ori[3], int dir, int side, Node*& rleaf, int rst[3], int& rlen);
+ void compressRing(PathElement*& ring);
+ void getFacePoint(PathElement* leaf, int dir, int& x, int& y, float& p, float& q);
+ LeafNode* patchAdjacent(InternalNode* node, int len, int st1[3], LeafNode* leaf1, int st2[3], LeafNode* leaf2, int walkdir, int inc, int dir, int side, float alpha);
+ int findPair(PathElement* head, int pos, int dir, PathElement*& pre1, PathElement*& pre2);
+ int getSide(PathElement* e, int pos, int dir);
+ int isEqual(PathElement* e1, PathElement* e2) ;
+ void preparePrimalEdgesMask(InternalNode* node);
+ void testFacePoint(PathElement* e1, PathElement* e2);
/**
* Path-related functions
*/
- void deletePath ( PathList*& head, PathList* pre, PathList*& curr ) ;
- void printPath( PathList* path ) ;
- void printPath( PathElement* path ) ;
- void printElement( PathElement* ele ) ;
- void printPaths( PathList* path ) ;
- void checkElement ( PathElement* ele ) ;
- void checkPath( PathElement* path ) ;
+ void deletePath(PathList*& head, PathList* pre, PathList*& curr);
+ void printPath(PathList* path);
+ void printPath(PathElement* path);
+ void printElement(PathElement* ele);
+ void printPaths(PathList* path);
+ void checkElement(PathElement* ele);
+ void checkPath(PathElement* path);
/**
* Routines to build signs to create a partitioned volume
- * (after patching rings)
+ *(after patching rings)
*/
- void buildSigns( ) ;
- void buildSigns( unsigned char table[], UCHAR* node, int isLeaf, int sg, int rvalue[8] ) ;
+ void buildSigns();
+ void buildSigns(unsigned char table[], Node* node, int isLeaf, int sg, int rvalue[8]);
/************************************************************************/
/* To remove disconnected components */
/************************************************************************/
- void floodFill( ) ;
- void clearProcessBits( UCHAR* node, int height ) ;
- int floodFill( UCHAR* node, int st[3], int len, int height, int threshold ) ;
+ void floodFill();
+ void clearProcessBits(Node* node, int height);
+ int floodFill(LeafNode* leaf, int st[3], int len, int height, int threshold);
+ int floodFill(Node* node, int st[3], int len, int height, int threshold);
/**
* Write out polygon file
*/
void writeOut();
- void writeOFF ( char* fname ) ;
- void writePLY ( char* fname ) ;
- void writeOpenEdges( FILE* fout ) ;
- void writeAllEdges( FILE* fout, int mode ) ;
- void writeAllEdges( FILE* fout, UCHAR* node, int height, int st[3], int len, int mode ) ;
- void writeOctree( char* fname ) ;
- void writeOctree( FILE* fout, UCHAR* node, int depth ) ;
-#ifdef USE_HERMIT
- void writeOctreeGeom( char* fname ) ;
- void writeOctreeGeom( FILE* fout, UCHAR* node, int st[3], int len, int depth ) ;
-#endif
-#ifdef USE_HERMIT
- void writeDCF ( char* fname ) ;
- void writeDCF ( FILE* fout, UCHAR* node, int height, int st[3], int len ) ;
- void countEdges ( UCHAR* node, int height, int& nedge, int mode ) ;
- void countIntersection( UCHAR* node, int height, int& nedge, int& ncell, int& nface ) ;
- void generateMinimizer( UCHAR* node, int st[3], int len, int height, int& offset ) ;
- void computeMinimizer( UCHAR* leaf, int st[3], int len, float rvalue[3] ) ;
+ void countIntersection(Node* node, int height, int& nedge, int& ncell, int& nface);
+ void generateMinimizer(Node* node, int st[3], int len, int height, int& offset);
+ void computeMinimizer(LeafNode* leaf, int st[3], int len, float rvalue[3]);
/**
* Traversal functions to generate polygon model
* op: 0 for counting, 1 for writing OBJ, 2 for writing OFF, 3 for writing PLY
*/
- void cellProcContour ( UCHAR* node, int leaf, int depth ) ;
- void faceProcContour ( UCHAR* node[2], int leaf[2], int depth[2], int maxdep, int dir ) ;
- void edgeProcContour ( UCHAR* node[4], int leaf[4], int depth[4], int maxdep, int dir ) ;
- void processEdgeWrite ( UCHAR* node[4], int depths[4], int maxdep, int dir ) ;
-#else
- void countIntersection( UCHAR* node, int height, int& nquad, int& nvert ) ;
- void writeVertex( UCHAR* node, int st[3], int len, int height, int& offset, FILE* fout ) ;
- void writeQuad( UCHAR* node, int st[3], int len, int height, FILE* fout ) ;
-#endif
-
- /**
- * Write out original model
- */
- void writeModel( char* fname ) ;
-
- /************************************************************************/
- /* Write out original vertex tags */
- /************************************************************************/
-#ifdef CINDY
- void writeTags( char* fname ) ;
- void readVertices( ) ;
- void readVertex( UCHAR* node, int st[3], int len, int height, float v[3], int index ) ;
- void outputTags( UCHAR* node, int height, FILE* fout ) ;
- void clearCindyBits( UCHAR* node, int height ) ;
-#endif
+ void cellProcContour(Node* node, int leaf, int depth);
+ void faceProcContour(Node* node[2], int leaf[2], int depth[2], int maxdep, int dir);
+ void edgeProcContour(Node* node[4], int leaf[4], int depth[4], int maxdep, int dir);
+ void processEdgeWrite(Node* node[4], int depths[4], int maxdep, int dir);
/* output callbacks/data */
DualConAllocOutput alloc_output;
@@ -394,858 +358,753 @@ private:
private:
/************ Operators for all nodes ************/
- /**
- * Bits order
- *
- * Leaf node:
- * Byte 0,1 (0-11): edge parity
- * Byte 1 (4,5,6): mask of primary edges intersections stored
- * Byte 1 (7): in flood fill mode, whether the cell is in process
- * Byte 2 (0-8): signs
- * Byte 3 (or 5) -- : edge intersections ( 4 bytes per inter, or 12 bytes if USE_HERMIT )
- * Byte 3,4: in coloring mode, the mask for edges
- *
- * Internal node:
- * Byte 0: child mask
- * Byte 1: leaf child mask
- */
-
/// Lookup table
- int numChildrenTable[ 256 ] ;
- int childrenCountTable[ 256 ][ 8 ] ;
- int childrenIndexTable[ 256 ][ 8 ] ;
- int numEdgeTable[ 8 ] ;
- int edgeCountTable[ 8 ][ 3 ] ;
+ int numChildrenTable[256];
+ int childrenCountTable[256][8];
+ int childrenIndexTable[256][8];
+ int numEdgeTable[8];
+ int edgeCountTable[8][3];
/// Build up lookup table
- void buildTable ( )
+ void buildTable()
{
- for ( int i = 0 ; i < 256 ; i ++ )
+ for(int i = 0; i < 256; i ++)
{
- numChildrenTable[ i ] = 0 ;
- int count = 0 ;
- for ( int j = 0 ; j < 8 ; j ++ )
+ numChildrenTable[i] = 0;
+ int count = 0;
+ for(int j = 0; j < 8; j ++)
{
- numChildrenTable[ i ] += ( ( i >> j ) & 1 ) ;
- childrenCountTable[ i ][ j ] = count ;
- childrenIndexTable[ i ][ count ] = j ;
- count += ( ( i >> j ) & 1 ) ;
+ numChildrenTable[i] +=((i >> j) & 1);
+ childrenCountTable[i][j] = count;
+ childrenIndexTable[i][count] = j;
+ count +=((i >> j) & 1);
}
}
- for ( int i = 0 ; i < 8 ; i ++ )
+ for(int i = 0; i < 8; i ++)
{
- numEdgeTable[ i ] = 0 ;
- int count = 0 ;
- for ( int j = 0 ; j < 3 ; j ++ )
+ numEdgeTable[i] = 0;
+ int count = 0;
+ for(int j = 0; j < 3; j ++)
{
- numEdgeTable[ i ] += ( ( i >> j ) & 1 ) ;
- edgeCountTable[ i ][ j ] = count ;
- count += ( ( i >> j ) & 1 ) ;
+ numEdgeTable[i] +=((i >> j) & 1);
+ edgeCountTable[i][j] = count;
+ count +=((i >> j) & 1);
}
}
- };
+ }
- int getSign( UCHAR* node, int height, int index )
+ int getSign(Node* node, int height, int index)
{
- if ( height == 0 )
+ if(height == 0)
{
- return getSign( node, index ) ;
+ return getSign(&node->leaf, index);
}
else
{
- if ( hasChild( node, index ) )
+ if(hasChild(&node->internal, index))
{
- return getSign( getChild( node, getChildCount( node, index ) ), height - 1, index ) ;
+ return getSign(getChild(&node->internal, getChildCount(&node->internal, index)),
+ height - 1,
+ index);
}
else
{
- return getSign( getChild( node, 0 ), height - 1, 7 - getChildIndex( node, 0 ) ) ;
+ return getSign(getChild(&node->internal, 0),
+ height - 1,
+ 7 - getChildIndex(&node->internal, 0));
}
}
}
/************ Operators for leaf nodes ************/
- void printInfo( int st[3] )
+ void printInfo(int st[3])
{
- printf("INFO AT: %d %d %d\n", st[0] >> minshift, st[1] >>minshift, st[2] >> minshift ) ;
- UCHAR* leaf = locateLeafCheck( st ) ;
- if ( leaf == NULL )
- {
- printf("Leaf not exists!\n") ;
- }
+ printf("INFO AT: %d %d %d\n", st[0] >> minshift, st[1] >>minshift, st[2] >> minshift);
+ LeafNode* leaf = (LeafNode*)locateLeafCheck(st);
+ if(leaf)
+ printInfo(leaf);
else
- {
- printInfo( leaf ) ;
- }
+ printf("Leaf not exists!\n");
}
- void printInfo( UCHAR* leaf )
+ void printInfo(const LeafNode* leaf)
{
/*
- printf("Edge mask: ") ;
- for ( int i = 0 ; i < 12 ; i ++ )
+ printf("Edge mask: ");
+ for(int i = 0; i < 12; i ++)
{
- printf("%d ", getEdgeParity( leaf, i ) ) ;
+ printf("%d ", getEdgeParity(leaf, i));
}
- printf("\n") ;
- printf("Stored edge mask: ") ;
- for ( i = 0 ; i < 3 ; i ++ )
+ printf("\n");
+ printf("Stored edge mask: ");
+ for(i = 0; i < 3; i ++)
{
- printf("%d ", getStoredEdgesParity( leaf, i ) ) ;
+ printf("%d ", getStoredEdgesParity(leaf, i));
}
- printf("\n") ;
+ printf("\n");
*/
- printf("Sign mask: ") ;
- for ( int i = 0 ; i < 8 ; i ++ )
+ printf("Sign mask: ");
+ for(int i = 0; i < 8; i ++)
{
- printf("%d ", getSign( leaf, i ) ) ;
+ printf("%d ", getSign(leaf, i));
}
- printf("\n") ;
+ printf("\n");
}
/// Retrieve signs
- int getSign ( UCHAR* leaf, int index )
+ int getSign(const LeafNode* leaf, int index)
{
- return (( leaf[2] >> index ) & 1 );
- };
+ return ((leaf->signs >> index) & 1);
+ }
/// Set sign
- void setSign ( UCHAR* leaf, int index )
+ void setSign(LeafNode* leaf, int index)
{
- leaf[2] |= ( 1 << index ) ;
- };
+ leaf->signs |= (1 << index);
+ }
- void setSign ( UCHAR* leaf, int index, int sign )
+ void setSign(LeafNode* leaf, int index, int sign)
{
- leaf[2] &= ( ~ ( 1 << index ) ) ;
- leaf[2] |= ( ( sign & 1 ) << index ) ;
- };
+ leaf->signs &= (~(1 << index));
+ leaf->signs |= ((sign & 1) << index);
+ }
- int getSignMask( UCHAR* leaf )
+ int getSignMask(const LeafNode* leaf)
{
- return leaf[2] ;
+ return leaf->signs;
}
- void setInProcessAll( int st[3], int dir )
+ void setInProcessAll(int st[3], int dir)
{
- int nst[3], eind ;
- for ( int i = 0 ; i < 4 ; i ++ )
+ int nst[3], eind;
+ for(int i = 0; i < 4; i ++)
{
- nst[0] = st[0] + dirCell[dir][i][0] * mindimen ;
- nst[1] = st[1] + dirCell[dir][i][1] * mindimen ;
- nst[2] = st[2] + dirCell[dir][i][2] * mindimen ;
- eind = dirEdge[dir][i] ;
+ nst[0] = st[0] + dirCell[dir][i][0] * mindimen;
+ nst[1] = st[1] + dirCell[dir][i][1] * mindimen;
+ nst[2] = st[2] + dirCell[dir][i][2] * mindimen;
+ eind = dirEdge[dir][i];
- UCHAR* cell = locateLeafCheck( nst ) ;
- if ( cell == NULL )
- {
- printf("Wrong!\n") ;
- }
- setInProcess( cell, eind ) ;
+ LeafNode* cell = locateLeafCheck(nst);
+ assert(cell);
+
+ setInProcess(cell, eind);
}
}
- void flipParityAll( int st[3], int dir )
+ void flipParityAll(int st[3], int dir)
{
- int nst[3], eind ;
- for ( int i = 0 ; i < 4 ; i ++ )
+ int nst[3], eind;
+ for(int i = 0; i < 4; i ++)
{
- nst[0] = st[0] + dirCell[dir][i][0] * mindimen ;
- nst[1] = st[1] + dirCell[dir][i][1] * mindimen ;
- nst[2] = st[2] + dirCell[dir][i][2] * mindimen ;
- eind = dirEdge[dir][i] ;
+ nst[0] = st[0] + dirCell[dir][i][0] * mindimen;
+ nst[1] = st[1] + dirCell[dir][i][1] * mindimen;
+ nst[2] = st[2] + dirCell[dir][i][2] * mindimen;
+ eind = dirEdge[dir][i];
- UCHAR* cell = locateLeaf( nst ) ;
- flipEdge( cell, eind ) ;
+ LeafNode* cell = locateLeaf(nst);
+ flipEdge(cell, eind);
}
}
- void setInProcess( UCHAR* leaf, int eind )
- {
- // leaf[1] |= ( 1 << 7 ) ;
- ( (USHORT*) (leaf + leaf_node_bytes - (flood_bytes + CINDY_BYTES)))[0] |= ( 1 << eind ) ;
- }
- void setOutProcess( UCHAR* leaf, int eind )
- {
- // leaf[1] &= ( ~ ( 1 << 7 ) ) ;
- ( (USHORT*) (leaf + leaf_node_bytes - (flood_bytes + CINDY_BYTES)))[0] &= ( ~ ( 1 << eind ) ) ;
- }
-
- int isInProcess( UCHAR* leaf, int eind )
+ void setInProcess(LeafNode* leaf, int eind)
{
- //int a = ( ( leaf[1] >> 7 ) & 1 ) ;
- int a = ( ( ( (USHORT*) (leaf + leaf_node_bytes - (flood_bytes + CINDY_BYTES)))[0] >> eind ) & 1 ) ;
- return a ;
- }
+ assert(eind >= 0 && eind <= 11);
-#ifndef USE_HERMIT
- /// Set minimizer index
- void setEdgeIntersectionIndex( UCHAR* leaf, int count, int index )
- {
- ((int *)( leaf + leaf_node_bytes ))[ count ] = index ;
+ leaf->flood_fill |= (1 << eind);
}
-
- /// Get minimizer index
- int getEdgeIntersectionIndex( UCHAR* leaf, int count )
+
+ void setOutProcess(LeafNode* leaf, int eind)
{
- return ((int *)( leaf + leaf_node_bytes ))[ count ] ;
+ assert(eind >= 0 && eind <= 11);
+
+ leaf->flood_fill &= ~(1 << eind);
}
- /// Get all intersection indices associated with a cell
- void fillEdgeIntersectionIndices( UCHAR* leaf, int st[3], int len, int inds[12] )
+ int isInProcess(LeafNode* leaf, int eind)
{
- int i ;
-
- // The three primal edges are easy
- int pmask[3] = { 0, 4, 8 } ;
- for ( i = 0 ; i < 3 ; i ++ )
- {
- if ( getEdgeParity( leaf, pmask[i] ) )
- {
- inds[pmask[i]] = getEdgeIntersectionIndex( leaf, getEdgeCount( leaf, i ) ) ;
- }
- }
+ assert(eind >= 0 && eind <= 11);
- // 3 face adjacent cubes
- int fmask[3][2] = {{6,10},{2,9},{1,5}} ;
- int femask[3][2] = {{1,2},{0,2},{0,1}} ;
- for ( i = 0 ; i < 3 ; i ++ )
- {
- int e1 = getEdgeParity( leaf, fmask[i][0] ) ;
- int e2 = getEdgeParity( leaf, fmask[i][1] ) ;
- if ( e1 || e2 )
- {
- int nst[3] = {st[0], st[1], st[2]} ;
- nst[ i ] += len ;
- // int nstt[3] = {0, 0, 0} ;
- // nstt[ i ] += 1 ;
- UCHAR* node = locateLeaf( nst ) ;
-
- if ( e1 )
- {
- inds[ fmask[i][0] ] = getEdgeIntersectionIndex( node, getEdgeCount( node, femask[i][0] ) ) ;
- }
- if ( e2 )
- {
- inds[ fmask[i][1] ] = getEdgeIntersectionIndex( node, getEdgeCount( node, femask[i][1] ) ) ;
- }
- }
- }
-
- // 3 edge adjacent cubes
- int emask[3] = {3, 7, 11} ;
- int eemask[3] = {0, 1, 2} ;
- for ( i = 0 ; i < 3 ; i ++ )
- {
- if ( getEdgeParity( leaf, emask[i] ) )
- {
- int nst[3] = {st[0] + len, st[1] + len, st[2] + len} ;
- nst[ i ] -= len ;
- // int nstt[3] = {1, 1, 1} ;
- // nstt[ i ] -= 1 ;
- UCHAR* node = locateLeaf( nst ) ;
-
- inds[ emask[i] ] = getEdgeIntersectionIndex( node, getEdgeCount( node, eemask[i] ) ) ;
- }
- }
+ return (leaf->flood_fill >> eind) & 1;
}
-
-#endif
-
/// Generate signs at the corners from the edge parity
- void generateSigns ( UCHAR* leaf, UCHAR table[], int start )
+ void generateSigns(LeafNode* leaf, unsigned char table[], int start)
{
- leaf[2] = table[ ( ((USHORT *) leaf)[ 0 ] ) & ( ( 1 << 12 ) - 1 ) ] ;
+ leaf->signs = table[leaf->edge_parity];
- if ( ( start ^ leaf[2] ) & 1 )
+ if((start ^ leaf->signs) & 1)
{
- leaf[2] = ~ ( leaf[2] ) ;
+ leaf->signs = ~(leaf->signs);
}
}
/// Get edge parity
- int getEdgeParity( UCHAR* leaf, int index )
+ int getEdgeParity(LeafNode* leaf, int index)
{
- int a = ( ( ((USHORT *) leaf)[ 0 ] >> index ) & 1 ) ;
- return a ;
- };
+ assert(index >= 0 && index <= 11);
+
+ return (leaf->edge_parity >> index) & 1;
+ }
/// Get edge parity on a face
- int getFaceParity ( UCHAR* leaf, int index )
+ int getFaceParity(LeafNode* leaf, int index)
{
- int a = getEdgeParity( leaf, faceMap[ index ][ 0 ] ) +
- getEdgeParity( leaf, faceMap[ index ][ 1 ] ) +
- getEdgeParity( leaf, faceMap[ index ][ 2 ] ) +
- getEdgeParity( leaf, faceMap[ index ][ 3 ] ) ;
- return ( a & 1 ) ;
+ int a = getEdgeParity(leaf, faceMap[index][0]) +
+ getEdgeParity(leaf, faceMap[index][1]) +
+ getEdgeParity(leaf, faceMap[index][2]) +
+ getEdgeParity(leaf, faceMap[index][3]);
+ return (a & 1);
}
- int getFaceEdgeNum ( UCHAR* leaf, int index )
+ int getFaceEdgeNum(LeafNode* leaf, int index)
{
- int a = getEdgeParity( leaf, faceMap[ index ][ 0 ] ) +
- getEdgeParity( leaf, faceMap[ index ][ 1 ] ) +
- getEdgeParity( leaf, faceMap[ index ][ 2 ] ) +
- getEdgeParity( leaf, faceMap[ index ][ 3 ] ) ;
- return a ;
+ int a = getEdgeParity(leaf, faceMap[index][0]) +
+ getEdgeParity(leaf, faceMap[index][1]) +
+ getEdgeParity(leaf, faceMap[index][2]) +
+ getEdgeParity(leaf, faceMap[index][3]);
+ return a;
}
/// Set edge parity
- void flipEdge( UCHAR* leaf, int index )
+ void flipEdge(LeafNode* leaf, int index)
{
- ((USHORT *) leaf)[ 0 ] ^= ( 1 << index ) ;
- };
+ assert(index >= 0 && index <= 11);
+
+ leaf->edge_parity ^= (1 << index);
+ }
+
/// Set 1
- void setEdge( UCHAR* leaf, int index )
+ void setEdge(LeafNode* leaf, int index)
{
- ((USHORT *) leaf)[ 0 ] |= ( 1 << index ) ;
- };
+ assert(index >= 0 && index <= 11);
+
+ leaf->edge_parity |= (1 << index);
+ }
+
/// Set 0
- void resetEdge( UCHAR* leaf, int index )
+ void resetEdge(LeafNode* leaf, int index)
{
- ((USHORT *) leaf)[ 0 ] &= ( ~ ( 1 << index ) ) ;
- };
+ assert(index >= 0 && index <= 11);
+
+ leaf->edge_parity &= ~(1 << index);
+ }
/// Flipping with a new intersection offset
- void createPrimalEdgesMask( UCHAR* leaf )
+ void createPrimalEdgesMask(LeafNode* leaf)
{
- int mask = (( leaf[0] & 1 ) | ( (leaf[0] >> 3) & 2 ) | ( (leaf[1] & 1) << 2 ) ) ;
- leaf[1] |= ( mask << 4 ) ;
-
+ leaf->primary_edge_intersections = getPrimalEdgesMask2(leaf);
}
- void setStoredEdgesParity( UCHAR* leaf, int pindex )
+ void setStoredEdgesParity(LeafNode* leaf, int pindex)
{
- leaf[1] |= ( 1 << ( 4 + pindex ) ) ;
+ assert(pindex <= 2 && pindex >= 0);
+
+ leaf->primary_edge_intersections |= (1 << pindex);
}
- int getStoredEdgesParity( UCHAR* leaf, int pindex )
+ int getStoredEdgesParity(LeafNode* leaf, int pindex)
{
- return ( ( leaf[1] >> ( 4 + pindex ) ) & 1 ) ;
+ assert(pindex <= 2 && pindex >= 0);
+
+ return (leaf->primary_edge_intersections >> pindex) & 1;
}
- UCHAR* flipEdge( UCHAR* leaf, int index, float alpha )
+ LeafNode* flipEdge(LeafNode* leaf, int index, float alpha)
{
- flipEdge( leaf, index ) ;
+ flipEdge(leaf, index);
- if ( ( index & 3 ) == 0 )
+ if((index & 3) == 0)
{
- int ind = index / 4 ;
- if ( getEdgeParity( leaf, index ) && ! getStoredEdgesParity( leaf, ind ) )
+ int ind = index / 4;
+ if(getEdgeParity(leaf, index) && ! getStoredEdgesParity(leaf, ind))
{
// Create a new node
- int num = getNumEdges( leaf ) + 1 ;
- setStoredEdgesParity( leaf, ind ) ;
- int count = getEdgeCount( leaf, ind ) ;
- UCHAR* nleaf = createLeaf( num ) ;
- for ( int i = 0 ; i < leaf_node_bytes ; i ++ )
- {
- nleaf[i] = leaf[i] ;
- }
+ int num = getNumEdges(leaf) + 1;
+ setStoredEdgesParity(leaf, ind);
+ int count = getEdgeCount(leaf, ind);
+ LeafNode* nleaf = createLeaf(num);
+ *nleaf = *leaf;
- setEdgeOffset( nleaf, alpha, count ) ;
+ setEdgeOffset(nleaf, alpha, count);
- if ( num > 1 )
+ if(num > 1)
{
- float * pts = ( float * ) ( leaf + leaf_node_bytes ) ;
- float * npts = ( float * ) ( nleaf + leaf_node_bytes ) ;
- for ( int i = 0 ; i < count ; i ++ )
+ float *pts = leaf->edge_intersections;
+ float *npts = nleaf->edge_intersections;
+ for(int i = 0; i < count; i ++)
{
- for ( int j = 0 ; j < EDGE_FLOATS ; j ++ )
+ for(int j = 0; j < EDGE_FLOATS; j ++)
{
- npts[i * EDGE_FLOATS + j] = pts[i * EDGE_FLOATS + j] ;
+ npts[i * EDGE_FLOATS + j] = pts[i * EDGE_FLOATS + j];
}
}
- for ( int i = count + 1 ; i < num ; i ++ )
+ for(int i = count + 1; i < num; i ++)
{
- for ( int j = 0 ; j < EDGE_FLOATS ; j ++ )
+ for(int j = 0; j < EDGE_FLOATS; j ++)
{
- npts[i * EDGE_FLOATS + j] = pts[ (i - 1) * EDGE_FLOATS + j] ;
+ npts[i * EDGE_FLOATS + j] = pts[(i - 1) * EDGE_FLOATS + j];
}
}
}
- removeLeaf( num-1, leaf ) ;
- leaf = nleaf ;
+ removeLeaf(num-1, (LeafNode*)leaf);
+ leaf = nleaf;
}
}
- return leaf ;
- };
+ return leaf;
+ }
/// Update parent link
- void updateParent( UCHAR* node, int len, int st[3], UCHAR* leaf )
+ void updateParent(InternalNode* node, int len, int st[3], LeafNode* leaf)
{
// First, locate the parent
- int count ;
- UCHAR* parent = locateParent( node, len, st, count ) ;
+ int count;
+ InternalNode* parent = locateParent(node, len, st, count);
- // UPdate
- setChild( parent, count, leaf ) ;
+ // Update
+ setChild(parent, count, (Node*)leaf);
}
- void updateParent( UCHAR* node, int len, int st[3] )
+ void updateParent(InternalNode* node, int len, int st[3])
{
- if ( len == dimen )
+ if(len == dimen)
{
- root = node ;
- return ;
+ root = (Node*)node;
+ return;
}
// First, locate the parent
- int count ;
- UCHAR* parent = locateParent( len, st, count ) ;
+ int count;
+ InternalNode* parent = locateParent(len, st, count);
// UPdate
- setChild( parent, count, node ) ;
+ setChild(parent, count, (Node*)node);
}
/// Find edge intersection on a given edge
- int getEdgeIntersectionByIndex( int st[3], int index, float pt[3], int check )
+ int getEdgeIntersectionByIndex(int st[3], int index, float pt[3], int check)
{
// First, locat the leaf
- UCHAR* leaf ;
- if ( check )
+ LeafNode* leaf;
+ if(check)
{
- leaf = locateLeafCheck( st ) ;
+ leaf = locateLeafCheck(st);
}
else
{
- leaf = locateLeaf( st ) ;
+ leaf = locateLeaf(st);
}
- if ( leaf && getStoredEdgesParity( leaf, index ) )
+ if(leaf && getStoredEdgesParity(leaf, index))
{
- float off = getEdgeOffset( leaf, getEdgeCount( leaf, index ) ) ;
- pt[0] = (float) st[0] ;
- pt[1] = (float) st[1] ;
- pt[2] = (float) st[2] ;
- pt[index] += off * mindimen ;
+ float off = getEdgeOffset(leaf, getEdgeCount(leaf, index));
+ pt[0] =(float) st[0];
+ pt[1] =(float) st[1];
+ pt[2] =(float) st[2];
+ pt[index] += off * mindimen;
- return 1 ;
+ return 1;
}
else
{
- return 0 ;
+ return 0;
}
}
/// Retrieve number of edges intersected
- int getPrimalEdgesMask( UCHAR* leaf )
+ int getPrimalEdgesMask(LeafNode* leaf)
{
- // return (( leaf[0] & 1 ) | ( (leaf[0] >> 3) & 2 ) | ( (leaf[1] & 1) << 2 ) ) ;
- return ( ( leaf[1] >> 4 ) & 7 ) ;
+ return leaf->primary_edge_intersections;
}
- int getPrimalEdgesMask2( UCHAR* leaf )
+ int getPrimalEdgesMask2(LeafNode* leaf)
{
- return (( leaf[0] & 1 ) | ( (leaf[0] >> 3) & 2 ) | ( (leaf[1] & 1) << 2 ) ) ;
+ return (((leaf->edge_parity & 0x1) >> 0) |
+ ((leaf->edge_parity & 0x10) >> 3) |
+ ((leaf->edge_parity & 0x100) >> 6));
}
/// Get the count for a primary edge
- int getEdgeCount( UCHAR* leaf, int index )
+ int getEdgeCount(LeafNode* leaf, int index)
{
- return edgeCountTable[ getPrimalEdgesMask( leaf ) ][ index ] ;
+ return edgeCountTable[getPrimalEdgesMask(leaf)][index];
}
- int getNumEdges( UCHAR* leaf )
+ int getNumEdges(LeafNode* leaf)
{
- return numEdgeTable[ getPrimalEdgesMask( leaf ) ] ;
+ return numEdgeTable[getPrimalEdgesMask(leaf)];
}
- int getNumEdges2( UCHAR* leaf )
+ int getNumEdges2(LeafNode* leaf)
{
- return numEdgeTable[ getPrimalEdgesMask2( leaf ) ] ;
+ return numEdgeTable[getPrimalEdgesMask2(leaf)];
}
/// Set edge intersection
- void setEdgeOffset( UCHAR* leaf, float pt, int count )
- {
- float * pts = ( float * ) ( leaf + leaf_node_bytes ) ;
-#ifdef USE_HERMIT
- pts[ EDGE_FLOATS * count ] = pt ;
- pts[ EDGE_FLOATS * count + 1 ] = 0 ;
- pts[ EDGE_FLOATS * count + 2 ] = 0 ;
- pts[ EDGE_FLOATS * count + 3 ] = 0 ;
-#else
- pts[ count ] = pt ;
-#endif
+ void setEdgeOffset(LeafNode* leaf, float pt, int count)
+ {
+ float *pts = leaf->edge_intersections;
+ pts[EDGE_FLOATS * count] = pt;
+ pts[EDGE_FLOATS * count + 1] = 0;
+ pts[EDGE_FLOATS * count + 2] = 0;
+ pts[EDGE_FLOATS * count + 3] = 0;
}
/// Set multiple edge intersections
- void setEdgeOffsets( UCHAR* leaf, float pt[3], int len )
+ void setEdgeOffsets(LeafNode* leaf, float pt[3], int len)
{
- float * pts = ( float * ) ( leaf + leaf_node_bytes ) ;
- for ( int i = 0 ; i < len ; i ++ )
+ float * pts = leaf->edge_intersections;
+ for(int i = 0; i < len; i ++)
{
- pts[i] = pt[i] ;
+ pts[i] = pt[i];
}
}
/// Retrieve edge intersection
- float getEdgeOffset( UCHAR* leaf, int count )
+ float getEdgeOffset(LeafNode* leaf, int count)
{
-#ifdef USE_HERMIT
- return (( float * ) ( leaf + leaf_node_bytes ))[ 4 * count ] ;
-#else
- return (( float * ) ( leaf + leaf_node_bytes ))[ count ] ;
-#endif
+ return leaf->edge_intersections[4 * count];
}
/// Update method
- UCHAR* updateEdgeOffsets( UCHAR* leaf, int oldlen, int newlen, float offs[3] )
+ LeafNode* updateEdgeOffsets(LeafNode* leaf, int oldlen, int newlen, float offs[3])
{
// First, create a new leaf node
- UCHAR* nleaf = createLeaf( newlen ) ;
- for ( int i = 0 ; i < leaf_node_bytes ; i ++ )
- {
- nleaf[i] = leaf[i] ;
- }
+ LeafNode* nleaf = createLeaf(newlen);
+ *nleaf = *leaf;
// Next, fill in the offsets
- setEdgeOffsets( nleaf, offs, newlen ) ;
+ setEdgeOffsets(nleaf, offs, newlen);
// Finally, delete the old leaf
- removeLeaf( oldlen, leaf ) ;
+ removeLeaf(oldlen, leaf);
- return nleaf ;
+ return nleaf;
}
- /// Set original vertex index
- void setOriginalIndex( UCHAR* leaf, int index )
- {
- ((int *)( leaf + leaf_node_bytes ))[ 0 ] = index ;
- }
- int getOriginalIndex( UCHAR* leaf )
- {
- return ((int *)( leaf + leaf_node_bytes ))[ 0 ] ;
- }
-#ifdef USE_HERMIT
/// Set minimizer index
- void setMinimizerIndex( UCHAR* leaf, int index )
+ void setMinimizerIndex(LeafNode* leaf, int index)
{
- ((int *)( leaf + leaf_node_bytes - leaf_extra_bytes - 4 ))[ 0 ] = index ;
+ leaf->minimizer_index = index;
}
/// Get minimizer index
- int getMinimizerIndex( UCHAR* leaf )
+ int getMinimizerIndex(LeafNode* leaf)
{
- return ((int *)( leaf + leaf_node_bytes - leaf_extra_bytes - 4 ))[ 0 ] ;
+ return leaf->minimizer_index;
}
- int getMinimizerIndex( UCHAR* leaf, int eind )
+ int getMinimizerIndex(LeafNode* leaf, int eind)
{
- int add = manifold_table[ getSignMask( leaf ) ].pairs[ eind ][ 0 ] - 1 ;
- if ( add < 0 )
- {
- printf("Manifold components wrong!\n") ;
- }
- return ((int *)( leaf + leaf_node_bytes - leaf_extra_bytes - 4 ))[ 0 ] + add ;
+ int add = manifold_table[getSignMask(leaf)].pairs[eind][0] - 1;
+ assert(add >= 0);
+ return leaf->minimizer_index + add;
}
- void getMinimizerIndices( UCHAR* leaf, int eind, int inds[2] )
+ void getMinimizerIndices(LeafNode* leaf, int eind, int inds[2])
{
- const int* add = manifold_table[ getSignMask( leaf ) ].pairs[ eind ] ;
- inds[0] = ((int *)( leaf + leaf_node_bytes - leaf_extra_bytes - 4 ))[ 0 ] + add[0] - 1 ;
- if ( add[0] == add[1] )
+ const int* add = manifold_table[getSignMask(leaf)].pairs[eind];
+ inds[0] = leaf->minimizer_index + add[0] - 1;
+ if(add[0] == add[1])
{
- inds[1] = -1 ;
+ inds[1] = -1;
}
else
{
- inds[1] = ((int *)( leaf + leaf_node_bytes - leaf_extra_bytes - 4 ))[ 0 ] + add[1] - 1 ;
+ inds[1] = leaf->minimizer_index + add[1] - 1;
}
}
/// Set edge intersection
- void setEdgeOffsetNormal( UCHAR* leaf, float pt, float a, float b, float c, int count )
+ void setEdgeOffsetNormal(LeafNode* leaf, float pt, float a, float b, float c, int count)
{
- float * pts = ( float * ) ( leaf + leaf_node_bytes ) ;
- pts[ 4 * count ] = pt ;
- pts[ 4 * count + 1 ] = a ;
- pts[ 4 * count + 2 ] = b ;
- pts[ 4 * count + 3 ] = c ;
+ float * pts = leaf->edge_intersections;
+ pts[4 * count] = pt;
+ pts[4 * count + 1] = a;
+ pts[4 * count + 2] = b;
+ pts[4 * count + 3] = c;
}
- float getEdgeOffsetNormal( UCHAR* leaf, int count, float& a, float& b, float& c )
+ float getEdgeOffsetNormal(LeafNode* leaf, int count, float& a, float& b, float& c)
{
- float * pts = ( float * ) ( leaf + leaf_node_bytes ) ;
- a = pts[ 4 * count + 1 ] ;
- b = pts[ 4 * count + 2 ] ;
- c = pts[ 4 * count + 3 ] ;
- return pts[ 4 * count ] ;
+ float * pts = leaf->edge_intersections;
+ a = pts[4 * count + 1];
+ b = pts[4 * count + 2];
+ c = pts[4 * count + 3];
+ return pts[4 * count];
}
/// Set multiple edge intersections
- void setEdgeOffsetsNormals( UCHAR* leaf, float pt[], float a[], float b[], float c[], int len )
+ void setEdgeOffsetsNormals(LeafNode* leaf, float pt[], float a[], float b[], float c[], int len)
{
- float * pts = ( float * ) ( leaf + leaf_node_bytes ) ;
- for ( int i = 0 ; i < len ; i ++ )
+ float *pts = leaf->edge_intersections;
+ for(int i = 0; i < len; i ++)
{
- if ( pt[i] > 1 || pt[i] < 0 )
+ if(pt[i] > 1 || pt[i] < 0)
{
- printf("\noffset: %f\n", pt[i]) ;
+ printf("\noffset: %f\n", pt[i]);
}
- pts[ i * 4 ] = pt[i] ;
- pts[ i * 4 + 1 ] = a[i] ;
- pts[ i * 4 + 2 ] = b[i] ;
- pts[ i * 4 + 3 ] = c[i] ;
+ pts[i * 4] = pt[i];
+ pts[i * 4 + 1] = a[i];
+ pts[i * 4 + 2] = b[i];
+ pts[i * 4 + 3] = c[i];
}
}
/// Retrieve complete edge intersection
- void getEdgeIntersectionByIndex( UCHAR* leaf, int index, int st[3], int len, float pt[3], float nm[3] )
+ void getEdgeIntersectionByIndex(LeafNode* leaf, int index, int st[3], int len, float pt[3], float nm[3])
{
- int count = getEdgeCount( leaf, index ) ;
- float * pts = ( float * ) ( leaf + leaf_node_bytes ) ;
+ int count = getEdgeCount(leaf, index);
+ float *pts = leaf->edge_intersections;
- float off = pts[ 4 * count ] ;
+ float off = pts[4 * count];
- pt[0] = (float) st[0] ;
- pt[1] = (float) st[1] ;
- pt[2] = (float) st[2] ;
- pt[ index ] += ( off * len ) ;
-
- nm[0] = pts[ 4 * count + 1 ] ;
- nm[1] = pts[ 4 * count + 2 ] ;
- nm[2] = pts[ 4 * count + 3 ] ;
+ pt[0] = (float) st[0];
+ pt[1] = (float) st[1];
+ pt[2] = (float) st[2];
+ pt[index] +=(off * len);
+
+ nm[0] = pts[4 * count + 1];
+ nm[1] = pts[4 * count + 2];
+ nm[2] = pts[4 * count + 3];
}
- float getEdgeOffsetNormalByIndex( UCHAR* leaf, int index, float nm[3] )
+ float getEdgeOffsetNormalByIndex(LeafNode* leaf, int index, float nm[3])
{
- int count = getEdgeCount( leaf, index ) ;
- float * pts = ( float * ) ( leaf + leaf_node_bytes ) ;
+ int count = getEdgeCount(leaf, index);
+ float *pts = leaf->edge_intersections;
- float off = pts[ 4 * count ] ;
+ float off = pts[4 * count];
- nm[0] = pts[ 4 * count + 1 ] ;
- nm[1] = pts[ 4 * count + 2 ] ;
- nm[2] = pts[ 4 * count + 3 ] ;
+ nm[0] = pts[4 * count + 1];
+ nm[1] = pts[4 * count + 2];
+ nm[2] = pts[4 * count + 3];
- return off ;
+ return off;
}
- void fillEdgeIntersections( UCHAR* leaf, int st[3], int len, float pts[12][3], float norms[12][3] )
+ void fillEdgeIntersections(LeafNode* leaf, int st[3], int len, float pts[12][3], float norms[12][3])
{
- int i ;
- // int stt[3] = { 0, 0, 0 } ;
+ int i;
+ // int stt[3] = {0, 0, 0};
// The three primal edges are easy
- int pmask[3] = { 0, 4, 8 } ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int pmask[3] = {0, 4, 8};
+ for(i = 0; i < 3; i ++)
{
- if ( getEdgeParity( leaf, pmask[i] ) )
+ if(getEdgeParity(leaf, pmask[i]))
{
- // getEdgeIntersectionByIndex( leaf, i, stt, 1, pts[ pmask[i] ], norms[ pmask[i] ] ) ;
- getEdgeIntersectionByIndex( leaf, i, st, len, pts[ pmask[i] ], norms[ pmask[i] ] ) ;
+ // getEdgeIntersectionByIndex(leaf, i, stt, 1, pts[pmask[i]], norms[pmask[i]]);
+ getEdgeIntersectionByIndex(leaf, i, st, len, pts[pmask[i]], norms[pmask[i]]);
}
}
// 3 face adjacent cubes
- int fmask[3][2] = {{6,10},{2,9},{1,5}} ;
- int femask[3][2] = {{1,2},{0,2},{0,1}} ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int fmask[3][2] = {{6,10},{2,9},{1,5}};
+ int femask[3][2] = {{1,2},{0,2},{0,1}};
+ for(i = 0; i < 3; i ++)
{
- int e1 = getEdgeParity( leaf, fmask[i][0] ) ;
- int e2 = getEdgeParity( leaf, fmask[i][1] ) ;
- if ( e1 || e2 )
+ int e1 = getEdgeParity(leaf, fmask[i][0]);
+ int e2 = getEdgeParity(leaf, fmask[i][1]);
+ if(e1 || e2)
{
- int nst[3] = {st[0], st[1], st[2]} ;
- nst[ i ] += len ;
- // int nstt[3] = {0, 0, 0} ;
- // nstt[ i ] += 1 ;
- UCHAR* node = locateLeaf( nst ) ;
+ int nst[3] = {st[0], st[1], st[2]};
+ nst[i] += len;
+ // int nstt[3] = {0, 0, 0};
+ // nstt[i] += 1;
+ LeafNode* node = locateLeaf(nst);
- if ( e1 )
+ if(e1)
{
- // getEdgeIntersectionByIndex( node, femask[i][0], nstt, 1, pts[ fmask[i][0] ], norms[ fmask[i][0] ] ) ;
- getEdgeIntersectionByIndex( node, femask[i][0], nst, len, pts[ fmask[i][0] ], norms[ fmask[i][0] ] ) ;
+ // getEdgeIntersectionByIndex(node, femask[i][0], nstt, 1, pts[fmask[i][0]], norms[fmask[i][0]]);
+ getEdgeIntersectionByIndex(node, femask[i][0], nst, len, pts[fmask[i][0]], norms[fmask[i][0]]);
}
- if ( e2 )
+ if(e2)
{
- // getEdgeIntersectionByIndex( node, femask[i][1], nstt, 1, pts[ fmask[i][1] ], norms[ fmask[i][1] ] ) ;
- getEdgeIntersectionByIndex( node, femask[i][1], nst, len, pts[ fmask[i][1] ], norms[ fmask[i][1] ] ) ;
+ // getEdgeIntersectionByIndex(node, femask[i][1], nstt, 1, pts[fmask[i][1]], norms[fmask[i][1]]);
+ getEdgeIntersectionByIndex(node, femask[i][1], nst, len, pts[fmask[i][1]], norms[fmask[i][1]]);
}
}
}
// 3 edge adjacent cubes
- int emask[3] = {3, 7, 11} ;
- int eemask[3] = {0, 1, 2} ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int emask[3] = {3, 7, 11};
+ int eemask[3] = {0, 1, 2};
+ for(i = 0; i < 3; i ++)
{
- if ( getEdgeParity( leaf, emask[i] ) )
+ if(getEdgeParity(leaf, emask[i]))
{
- int nst[3] = {st[0] + len, st[1] + len, st[2] + len} ;
- nst[ i ] -= len ;
- // int nstt[3] = {1, 1, 1} ;
- // nstt[ i ] -= 1 ;
- UCHAR* node = locateLeaf( nst ) ;
+ int nst[3] = {st[0] + len, st[1] + len, st[2] + len};
+ nst[i] -= len;
+ // int nstt[3] = {1, 1, 1};
+ // nstt[i] -= 1;
+ LeafNode* node = locateLeaf(nst);
- // getEdgeIntersectionByIndex( node, eemask[i], nstt, 1, pts[ emask[i] ], norms[ emask[i] ] ) ;
- getEdgeIntersectionByIndex( node, eemask[i], nst, len, pts[ emask[i] ], norms[ emask[i] ] ) ;
+ // getEdgeIntersectionByIndex(node, eemask[i], nstt, 1, pts[emask[i]], norms[emask[i]]);
+ getEdgeIntersectionByIndex(node, eemask[i], nst, len, pts[emask[i]], norms[emask[i]]);
}
}
}
- void fillEdgeIntersections( UCHAR* leaf, int st[3], int len, float pts[12][3], float norms[12][3], int parity[12] )
+ void fillEdgeIntersections(LeafNode* leaf, int st[3], int len, float pts[12][3], float norms[12][3], int parity[12])
{
- int i ;
- for ( i = 0 ; i < 12 ; i ++ )
+ int i;
+ for(i = 0; i < 12; i ++)
{
- parity[ i ] = 0 ;
+ parity[i] = 0;
}
- // int stt[3] = { 0, 0, 0 } ;
+ // int stt[3] = {0, 0, 0};
// The three primal edges are easy
- int pmask[3] = { 0, 4, 8 } ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int pmask[3] = {0, 4, 8};
+ for(i = 0; i < 3; i ++)
{
- if ( getStoredEdgesParity( leaf, i ) )
+ if(getStoredEdgesParity(leaf, i))
{
- // getEdgeIntersectionByIndex( leaf, i, stt, 1, pts[ pmask[i] ], norms[ pmask[i] ] ) ;
- getEdgeIntersectionByIndex( leaf, i, st, len, pts[ pmask[i] ], norms[ pmask[i] ] ) ;
- parity[ pmask[i] ] = 1 ;
+ // getEdgeIntersectionByIndex(leaf, i, stt, 1, pts[pmask[i]], norms[pmask[i]]);
+ getEdgeIntersectionByIndex(leaf, i, st, len, pts[pmask[i]], norms[pmask[i]]);
+ parity[pmask[i]] = 1;
}
}
// 3 face adjacent cubes
- int fmask[3][2] = {{6,10},{2,9},{1,5}} ;
- int femask[3][2] = {{1,2},{0,2},{0,1}} ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int fmask[3][2] = {{6,10},{2,9},{1,5}};
+ int femask[3][2] = {{1,2},{0,2},{0,1}};
+ for(i = 0; i < 3; i ++)
{
{
- int nst[3] = {st[0], st[1], st[2]} ;
- nst[ i ] += len ;
- // int nstt[3] = {0, 0, 0} ;
- // nstt[ i ] += 1 ;
- UCHAR* node = locateLeafCheck( nst ) ;
- if ( node == NULL )
+ int nst[3] = {st[0], st[1], st[2]};
+ nst[i] += len;
+ // int nstt[3] = {0, 0, 0};
+ // nstt[i] += 1;
+ LeafNode* node = locateLeafCheck(nst);
+ if(node == NULL)
{
- continue ;
+ continue;
}
- int e1 = getStoredEdgesParity( node, femask[i][0] ) ;
- int e2 = getStoredEdgesParity( node, femask[i][1] ) ;
+ int e1 = getStoredEdgesParity(node, femask[i][0]);
+ int e2 = getStoredEdgesParity(node, femask[i][1]);
- if ( e1 )
+ if(e1)
{
- // getEdgeIntersectionByIndex( node, femask[i][0], nstt, 1, pts[ fmask[i][0] ], norms[ fmask[i][0] ] ) ;
- getEdgeIntersectionByIndex( node, femask[i][0], nst, len, pts[ fmask[i][0] ], norms[ fmask[i][0] ] ) ;
- parity[ fmask[i][0] ] = 1 ;
+ // getEdgeIntersectionByIndex(node, femask[i][0], nstt, 1, pts[fmask[i][0]], norms[fmask[i][0]]);
+ getEdgeIntersectionByIndex(node, femask[i][0], nst, len, pts[fmask[i][0]], norms[fmask[i][0]]);
+ parity[fmask[i][0]] = 1;
}
- if ( e2 )
+ if(e2)
{
- // getEdgeIntersectionByIndex( node, femask[i][1], nstt, 1, pts[ fmask[i][1] ], norms[ fmask[i][1] ] ) ;
- getEdgeIntersectionByIndex( node, femask[i][1], nst, len, pts[ fmask[i][1] ], norms[ fmask[i][1] ] ) ;
- parity[ fmask[i][1] ] = 1 ;
+ // getEdgeIntersectionByIndex(node, femask[i][1], nstt, 1, pts[fmask[i][1]], norms[fmask[i][1]]);
+ getEdgeIntersectionByIndex(node, femask[i][1], nst, len, pts[fmask[i][1]], norms[fmask[i][1]]);
+ parity[fmask[i][1]] = 1;
}
}
}
// 3 edge adjacent cubes
- int emask[3] = {3, 7, 11} ;
- int eemask[3] = {0, 1, 2} ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int emask[3] = {3, 7, 11};
+ int eemask[3] = {0, 1, 2};
+ for(i = 0; i < 3; i ++)
{
-// if ( getEdgeParity( leaf, emask[i] ) )
+// if(getEdgeParity(leaf, emask[i]))
{
- int nst[3] = {st[0] + len, st[1] + len, st[2] + len} ;
- nst[ i ] -= len ;
- // int nstt[3] = {1, 1, 1} ;
- // nstt[ i ] -= 1 ;
- UCHAR* node = locateLeafCheck( nst ) ;
- if ( node == NULL )
+ int nst[3] = {st[0] + len, st[1] + len, st[2] + len};
+ nst[i] -= len;
+ // int nstt[3] = {1, 1, 1};
+ // nstt[i] -= 1;
+ LeafNode* node = locateLeafCheck(nst);
+ if(node == NULL)
{
- continue ;
+ continue;
}
- if ( getStoredEdgesParity( node, eemask[i] ) )
+ if(getStoredEdgesParity(node, eemask[i]))
{
- // getEdgeIntersectionByIndex( node, eemask[i], nstt, 1, pts[ emask[i] ], norms[ emask[i] ] ) ;
- getEdgeIntersectionByIndex( node, eemask[i], nst, len, pts[ emask[i] ], norms[ emask[i] ] ) ;
- parity[ emask[ i ] ] = 1 ;
+ // getEdgeIntersectionByIndex(node, eemask[i], nstt, 1, pts[emask[i]], norms[emask[i]]);
+ getEdgeIntersectionByIndex(node, eemask[i], nst, len, pts[emask[i]], norms[emask[i]]);
+ parity[emask[i]] = 1;
}
}
}
}
- void fillEdgeOffsetsNormals( UCHAR* leaf, int st[3], int len, float pts[12], float norms[12][3], int parity[12] )
+ void fillEdgeOffsetsNormals(LeafNode* leaf, int st[3], int len, float pts[12], float norms[12][3], int parity[12])
{
- int i ;
- for ( i = 0 ; i < 12 ; i ++ )
+ int i;
+ for(i = 0; i < 12; i ++)
{
- parity[ i ] = 0 ;
+ parity[i] = 0;
}
- // int stt[3] = { 0, 0, 0 } ;
+ // int stt[3] = {0, 0, 0};
// The three primal edges are easy
- int pmask[3] = { 0, 4, 8 } ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int pmask[3] = {0, 4, 8};
+ for(i = 0; i < 3; i ++)
{
- if ( getStoredEdgesParity( leaf, i ) )
+ if(getStoredEdgesParity(leaf, i))
{
- pts[ pmask[i] ] = getEdgeOffsetNormalByIndex( leaf, i, norms[ pmask[i] ] ) ;
- parity[ pmask[i] ] = 1 ;
+ pts[pmask[i]] = getEdgeOffsetNormalByIndex(leaf, i, norms[pmask[i]]);
+ parity[pmask[i]] = 1;
}
}
// 3 face adjacent cubes
- int fmask[3][2] = {{6,10},{2,9},{1,5}} ;
- int femask[3][2] = {{1,2},{0,2},{0,1}} ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int fmask[3][2] = {{6,10},{2,9},{1,5}};
+ int femask[3][2] = {{1,2},{0,2},{0,1}};
+ for(i = 0; i < 3; i ++)
{
{
- int nst[3] = {st[0], st[1], st[2]} ;
- nst[ i ] += len ;
- // int nstt[3] = {0, 0, 0} ;
- // nstt[ i ] += 1 ;
- UCHAR* node = locateLeafCheck( nst ) ;
- if ( node == NULL )
+ int nst[3] = {st[0], st[1], st[2]};
+ nst[i] += len;
+ // int nstt[3] = {0, 0, 0};
+ // nstt[i] += 1;
+ LeafNode* node = locateLeafCheck(nst);
+ if(node == NULL)
{
- continue ;
+ continue;
}
- int e1 = getStoredEdgesParity( node, femask[i][0] ) ;
- int e2 = getStoredEdgesParity( node, femask[i][1] ) ;
+ int e1 = getStoredEdgesParity(node, femask[i][0]);
+ int e2 = getStoredEdgesParity(node, femask[i][1]);
- if ( e1 )
+ if(e1)
{
- pts[ fmask[i][0] ] = getEdgeOffsetNormalByIndex( node, femask[i][0], norms[ fmask[i][0] ] ) ;
- parity[ fmask[i][0] ] = 1 ;
+ pts[fmask[i][0]] = getEdgeOffsetNormalByIndex(node, femask[i][0], norms[fmask[i][0]]);
+ parity[fmask[i][0]] = 1;
}
- if ( e2 )
+ if(e2)
{
- pts[ fmask[i][1] ] = getEdgeOffsetNormalByIndex( node, femask[i][1], norms[ fmask[i][1] ] ) ;
- parity[ fmask[i][1] ] = 1 ;
+ pts[fmask[i][1]] = getEdgeOffsetNormalByIndex(node, femask[i][1], norms[fmask[i][1]]);
+ parity[fmask[i][1]] = 1;
}
}
}
// 3 edge adjacent cubes
- int emask[3] = {3, 7, 11} ;
- int eemask[3] = {0, 1, 2} ;
- for ( i = 0 ; i < 3 ; i ++ )
+ int emask[3] = {3, 7, 11};
+ int eemask[3] = {0, 1, 2};
+ for(i = 0; i < 3; i ++)
{
-// if ( getEdgeParity( leaf, emask[i] ) )
+// if(getEdgeParity(leaf, emask[i]))
{
- int nst[3] = {st[0] + len, st[1] + len, st[2] + len} ;
- nst[ i ] -= len ;
- // int nstt[3] = {1, 1, 1} ;
- // nstt[ i ] -= 1 ;
- UCHAR* node = locateLeafCheck( nst ) ;
- if ( node == NULL )
+ int nst[3] = {st[0] + len, st[1] + len, st[2] + len};
+ nst[i] -= len;
+ // int nstt[3] = {1, 1, 1};
+ // nstt[i] -= 1;
+ LeafNode* node = locateLeafCheck(nst);
+ if(node == NULL)
{
- continue ;
+ continue;
}
- if ( getStoredEdgesParity( node, eemask[i] ) )
+ if(getStoredEdgesParity(node, eemask[i]))
{
- pts[ emask[i] ] = getEdgeOffsetNormalByIndex( node, eemask[i], norms[ emask[i] ] ) ;
- parity[ emask[ i ] ] = 1 ;
+ pts[emask[i]] = getEdgeOffsetNormalByIndex(node, eemask[i], norms[emask[i]]);
+ parity[emask[i]] = 1;
}
}
}
@@ -1253,344 +1112,320 @@ private:
/// Update method
- UCHAR* updateEdgeOffsetsNormals( UCHAR* leaf, int oldlen, int newlen, float offs[3], float a[3], float b[3], float c[3] )
+ LeafNode* updateEdgeOffsetsNormals(LeafNode* leaf, int oldlen, int newlen, float offs[3], float a[3], float b[3], float c[3])
{
// First, create a new leaf node
- UCHAR* nleaf = createLeaf( newlen ) ;
- for ( int i = 0 ; i < leaf_node_bytes ; i ++ )
- {
- nleaf[i] = leaf[i] ;
- }
+ LeafNode* nleaf = createLeaf(newlen);
+ *nleaf = *leaf;
// Next, fill in the offsets
- setEdgeOffsetsNormals( nleaf, offs, a, b, c, newlen ) ;
+ setEdgeOffsetsNormals(nleaf, offs, a, b, c, newlen);
// Finally, delete the old leaf
- removeLeaf( oldlen, leaf ) ;
+ removeLeaf(oldlen, leaf);
- return nleaf ;
+ return nleaf;
}
-#endif
/// Locate a leaf
/// WARNING: assuming this leaf already exists!
- UCHAR* locateLeaf( int st[3] )
+ LeafNode* locateLeaf(int st[3])
{
- UCHAR* node = root ;
- for ( int i = GRID_DIMENSION - 1 ; i > GRID_DIMENSION - maxDepth - 1 ; i -- )
+ Node* node = (Node*)root;
+ for(int i = GRID_DIMENSION - 1; i > GRID_DIMENSION - maxDepth - 1; i --)
{
- int index = ( ( ( st[0] >> i ) & 1 ) << 2 ) |
- ( ( ( st[1] >> i ) & 1 ) << 1 ) |
- ( ( ( st[2] >> i ) & 1 ) ) ;
- node = getChild( node, getChildCount( node, index ) ) ;
+ int index =(((st[0] >> i) & 1) << 2) |
+ (((st[1] >> i) & 1) << 1) |
+ (((st[2] >> i) & 1));
+ node = getChild(&node->internal, getChildCount(&node->internal, index));
}
- return node ;
+ return &node->leaf;
}
- UCHAR* locateLeaf( UCHAR* node, int len, int st[3] )
+ LeafNode* locateLeaf(InternalNode* parent, int len, int st[3])
{
- int index ;
- for ( int i = len / 2 ; i >= mindimen ; i >>= 1 )
+ Node *node = (Node*)parent;
+ int index;
+ for(int i = len / 2; i >= mindimen; i >>= 1)
{
- index = ( ( ( st[0] & i ) ? 4 : 0 ) |
- ( ( st[1] & i ) ? 2 : 0 ) |
- ( ( st[2] & i ) ? 1 : 0 ) ) ;
- node = getChild( node, getChildCount( node, index ) ) ;
+ index =(((st[0] & i) ? 4 : 0) |
+ ((st[1] & i) ? 2 : 0) |
+ ((st[2] & i) ? 1 : 0));
+ node = getChild(&node->internal,
+ getChildCount(&node->internal, index));
}
- return node ;
+ return &node->leaf;
}
- UCHAR* locateLeafCheck( int st[3] )
+
+ LeafNode* locateLeafCheck(int st[3])
{
- UCHAR* node = root ;
- for ( int i = GRID_DIMENSION - 1 ; i > GRID_DIMENSION - maxDepth - 1 ; i -- )
+ Node* node = (Node*)root;
+ for(int i = GRID_DIMENSION - 1; i > GRID_DIMENSION - maxDepth - 1; i --)
{
- int index = ( ( ( st[0] >> i ) & 1 ) << 2 ) |
- ( ( ( st[1] >> i ) & 1 ) << 1 ) |
- ( ( ( st[2] >> i ) & 1 ) ) ;
- if ( ! hasChild( node, index ) )
+ int index =(((st[0] >> i) & 1) << 2) |
+ (((st[1] >> i) & 1) << 1) |
+ (((st[2] >> i) & 1));
+ if(!hasChild(&node->internal, index))
{
- return NULL ;
+ return NULL;
}
- node = getChild( node, getChildCount( node, index ) ) ;
+ node = getChild(&node->internal, getChildCount(&node->internal, index));
}
- return node ;
+ return &node->leaf;
}
- UCHAR* locateParent( int len, int st[3], int& count )
+
+ InternalNode* locateParent(int len, int st[3], int& count)
{
- UCHAR* node = root ;
- UCHAR* pre = NULL ;
- int index = 0 ;
- for ( int i = dimen / 2 ; i >= len ; i >>= 1 )
+ InternalNode* node = (InternalNode*)root;
+ InternalNode* pre = NULL;
+ int index = 0;
+ for(int i = dimen / 2; i >= len; i >>= 1)
{
- index = ( ( ( st[0] & i ) ? 4 : 0 ) |
- ( ( st[1] & i ) ? 2 : 0 ) |
- ( ( st[2] & i ) ? 1 : 0 ) ) ;
- pre = node ;
- node = getChild( node, getChildCount( node, index ) ) ;
+ index =(((st[0] & i) ? 4 : 0) |
+ ((st[1] & i) ? 2 : 0) |
+ ((st[2] & i) ? 1 : 0));
+ pre = node;
+ node = &getChild(node, getChildCount(node, index))->internal;
}
- count = getChildCount( pre, index ) ;
- return pre ;
+ count = getChildCount(pre, index);
+ return pre;
}
- UCHAR* locateParent( UCHAR* papa, int len, int st[3], int& count )
+
+ InternalNode* locateParent(InternalNode* parent, int len, int st[3], int& count)
{
- UCHAR* node = papa ;
- UCHAR* pre = NULL ;
+ InternalNode* node = parent;
+ InternalNode* pre = NULL;
int index = 0;
- for ( int i = len / 2 ; i >= mindimen ; i >>= 1 )
+ for(int i = len / 2; i >= mindimen; i >>= 1)
{
- index = ( ( ( st[0] & i ) ? 4 : 0 ) |
- ( ( st[1] & i ) ? 2 : 0 ) |
- ( ( st[2] & i ) ? 1 : 0 ) ) ;
- pre = node ;
- node = getChild( node, getChildCount( node, index ) ) ;
+ index =(((st[0] & i) ? 4 : 0) |
+ ((st[1] & i) ? 2 : 0) |
+ ((st[2] & i) ? 1 : 0));
+ pre = node;
+ node = (InternalNode*)getChild(node, getChildCount(node, index));
}
- count = getChildCount( pre, index ) ;
- return pre ;
+ count = getChildCount(pre, index);
+ return pre;
}
+
/************ Operators for internal nodes ************/
- /// Print the node information
- void printNode( UCHAR* node )
- {
- printf("Address: %p ", node ) ;
- printf("Leaf Mask: ") ;
- for ( int i = 0 ; i < 8 ; i ++ )
- {
- printf( "%d ", isLeaf( node, i ) ) ;
- }
- printf("Child Mask: ") ;
- for ( int i = 0 ; i < 8 ; i ++ )
- {
- printf( "%d ", hasChild( node, i ) ) ;
- }
- printf("\n") ;
- }
-
- /// Get size of an internal node
- int getSize ( int length )
- {
- return INTERNAL_NODE_BYTES + length * 4 ;
- };
-
/// If child index exists
- int hasChild( UCHAR* node, int index )
+ int hasChild(InternalNode* node, int index)
{
- return ( node[0] >> index ) & 1 ;
- };
+ return (node->has_child >> index) & 1;
+ }
/// Test if child is leaf
- int isLeaf ( UCHAR* node, int index )
+ int isLeaf(InternalNode* node, int index)
{
- return ( node[1] >> index ) & 1 ;
- };
+ return (node->child_is_leaf >> index) & 1;
+ }
/// Get the pointer to child index
- UCHAR* getChild ( UCHAR* node, int count )
+ Node* getChild(InternalNode* node, int count)
{
- return (( UCHAR ** ) ( node + INTERNAL_NODE_BYTES )) [ count ] ;
+ return node->children[count];
};
/// Get total number of children
- int getNumChildren( UCHAR* node )
+ int getNumChildren(InternalNode* node)
{
- return numChildrenTable[ node[0] ] ;
- };
+ return numChildrenTable[node->has_child];
+ }
/// Get the count of children
- int getChildCount( UCHAR* node, int index )
+ int getChildCount(InternalNode* node, int index)
{
- return childrenCountTable[ node[0] ][ index ] ;
+ return childrenCountTable[node->has_child][index];
}
- int getChildIndex( UCHAR* node, int count )
+ int getChildIndex(InternalNode* node, int count)
{
- return childrenIndexTable[ node[0] ][ count ] ;
+ return childrenIndexTable[node->has_child][count];
}
- int* getChildCounts( UCHAR* node )
+ int* getChildCounts(InternalNode* node)
{
- return childrenCountTable[ node[0] ] ;
+ return childrenCountTable[node->has_child];
}
/// Get all children
- void fillChildren( UCHAR* node, UCHAR* chd[ 8 ], int leaf[ 8 ] )
+ void fillChildren(InternalNode* node, Node* children[8], int leaf[8])
{
- int count = 0 ;
- for ( int i = 0 ; i < 8 ; i ++ )
+ int count = 0;
+ for(int i = 0; i < 8; i ++)
{
- leaf[ i ] = isLeaf( node, i ) ;
- if ( hasChild( node, i ) )
+ leaf[i] = isLeaf(node, i);
+ if(hasChild(node, i))
{
- chd[ i ] = getChild( node, count ) ;
- count ++ ;
+ children[i] = getChild(node, count);
+ count ++;
}
else
{
- chd[ i ] = NULL ;
- leaf[ i ] = 0 ;
+ children[i] = NULL;
+ leaf[i] = 0;
}
}
}
/// Sets the child pointer
- void setChild ( UCHAR* node, int count, UCHAR* chd )
+ void setChild(InternalNode* node, int count, Node* chd)
{
- (( UCHAR ** ) ( node + INTERNAL_NODE_BYTES )) [ count ] = chd ;
+ node->children[count] = chd;
}
- void setInternalChild ( UCHAR* node, int index, int count, UCHAR* chd )
+ void setInternalChild(InternalNode* node, int index, int count, InternalNode* chd)
{
- setChild( node, count, chd ) ;
- node[0] |= ( 1 << index ) ;
- };
- void setLeafChild ( UCHAR* node, int index, int count, UCHAR* chd )
+ setChild(node, count, (Node*)chd);
+ node->has_child |= (1 << index);
+ }
+ void setLeafChild(InternalNode* node, int index, int count, LeafNode* chd)
{
- setChild( node, count, chd ) ;
- node[0] |= ( 1 << index ) ;
- node[1] |= ( 1 << index ) ;
- };
+ setChild(node, count, (Node*)chd);
+ node->has_child |=(1 << index);
+ node->child_is_leaf |= (1 << index);
+ }
/// Add a kid to an existing internal node
/// Fix me: can we do this without wasting memory ?
/// Fixed: using variable memory
- UCHAR* addChild( UCHAR* node, int index, UCHAR* chd, int aLeaf )
+ InternalNode* addChild(InternalNode* node, int index, Node* child, int aLeaf)
{
// Create new internal node
- int num = getNumChildren( node ) ;
- UCHAR* rnode = createInternal( num + 1 ) ;
+ int num = getNumChildren(node);
+ InternalNode* rnode = createInternal(num + 1);
// Establish children
- int i ;
- int count1 = 0, count2 = 0 ;
- for ( i = 0 ; i < 8 ; i ++ )
+ int i;
+ int count1 = 0, count2 = 0;
+ for(i = 0; i < 8; i ++)
{
- if ( i == index )
+ if(i == index)
{
- if ( aLeaf )
+ if(aLeaf)
{
- setLeafChild( rnode, i, count2, chd ) ;
+ setLeafChild(rnode, i, count2, &child->leaf);
}
else
{
- setInternalChild( rnode, i, count2, chd ) ;
+ setInternalChild(rnode, i, count2, &child->internal);
}
- count2 ++ ;
+ count2 ++;
}
- else if ( hasChild( node, i ) )
+ else if(hasChild(node, i))
{
- if ( isLeaf( node, i ) )
+ if(isLeaf(node, i))
{
- setLeafChild( rnode, i, count2, getChild( node, count1 ) ) ;
+ setLeafChild(rnode, i, count2, &getChild(node, count1)->leaf);
}
else
{
- setInternalChild( rnode, i, count2, getChild( node, count1 ) ) ;
+ setInternalChild(rnode, i, count2, &getChild(node, count1)->internal);
}
- count1 ++ ;
- count2 ++ ;
+ count1 ++;
+ count2 ++;
}
}
- removeInternal( num, node ) ;
- return rnode ;
+ removeInternal(num, node);
+ return rnode;
}
/// Allocate a node
- UCHAR* createInternal( int length )
+ InternalNode* createInternal(int length)
{
- UCHAR* inode = alloc[ length ]->allocate( ) ;
- inode[0] = inode[1] = 0 ;
- return inode ;
- };
- UCHAR* createLeaf( int length )
+ InternalNode* inode = (InternalNode*)alloc[length]->allocate();
+ inode->has_child = 0;
+ inode->child_is_leaf = 0;
+ return inode;
+ }
+
+ LeafNode* createLeaf(int length)
{
- if ( length > 3 )
- {
- printf("wierd");
- }
- UCHAR* lnode = leafalloc[ length ]->allocate( ) ;
- lnode[0] = lnode[1] = lnode[2] = 0 ;
+ assert(length <= 3);
- return lnode ;
- };
+ LeafNode* lnode = (LeafNode*)leafalloc[length]->allocate();
+ lnode->edge_parity = 0;
+ lnode->primary_edge_intersections = 0;
+ lnode->signs = 0;
- void removeInternal ( int num, UCHAR* node )
+ return lnode;
+ }
+
+ void removeInternal(int num, InternalNode* node)
{
- alloc[ num ]->deallocate( node ) ;
+ alloc[num]->deallocate(node);
}
- void removeLeaf ( int num, UCHAR* leaf )
+ void removeLeaf(int num, LeafNode* leaf)
{
- if ( num > 3 || num < 0 )
- {
- printf("wierd");
- }
- leafalloc[ num ]->deallocate( leaf ) ;
+ assert(num >= 0 && num <= 3);
+ leafalloc[num]->deallocate(leaf);
}
/// Add a leaf (by creating a new par node with the leaf added)
- UCHAR* addLeafChild ( UCHAR* par, int index, int count, UCHAR* leaf )
+ InternalNode* addLeafChild(InternalNode* par, int index, int count,
+ LeafNode* leaf)
{
- int num = getNumChildren( par ) + 1 ;
- UCHAR* npar = createInternal( num ) ;
- npar[0] = par[0] ;
- npar[1] = par[1] ;
+ int num = getNumChildren(par) + 1;
+ InternalNode* npar = createInternal(num);
+ *npar = *par;
- if ( num == 1 )
+ if(num == 1)
{
- setLeafChild( npar, index, 0, leaf ) ;
+ setLeafChild(npar, index, 0, leaf);
}
else
{
- int i ;
- for ( i = 0 ; i < count ; i ++ )
+ int i;
+ for(i = 0; i < count; i ++)
{
- setChild( npar, i, getChild( par, i ) ) ;
+ setChild(npar, i, getChild(par, i));
}
- setLeafChild( npar, index, count, leaf ) ;
- for ( i = count + 1 ; i < num ; i ++ )
+ setLeafChild(npar, index, count, leaf);
+ for(i = count + 1; i < num; i ++)
{
- setChild( npar, i, getChild( par, i - 1 ) ) ;
+ setChild(npar, i, getChild(par, i - 1));
}
}
- removeInternal( num-1, par ) ;
- return npar ;
- };
+ removeInternal(num-1, par);
+ return npar;
+ }
- UCHAR* addInternalChild ( UCHAR* par, int index, int count, UCHAR* node )
+ InternalNode* addInternalChild(InternalNode* par, int index, int count,
+ InternalNode* node)
{
- int num = getNumChildren( par ) + 1 ;
- UCHAR* npar = createInternal( num ) ;
- npar[0] = par[0] ;
- npar[1] = par[1] ;
+ int num = getNumChildren(par) + 1;
+ InternalNode* npar = createInternal(num);
+ *npar = *par;
- if ( num == 1 )
+ if(num == 1)
{
- setInternalChild( npar, index, 0, node ) ;
+ setInternalChild(npar, index, 0, node);
}
else
{
- int i ;
- for ( i = 0 ; i < count ; i ++ )
+ int i;
+ for(i = 0; i < count; i ++)
{
- setChild( npar, i, getChild( par, i ) ) ;
+ setChild(npar, i, getChild(par, i));
}
- setInternalChild( npar, index, count, node ) ;
- for ( i = count + 1 ; i < num ; i ++ )
+ setInternalChild(npar, index, count, node);
+ for(i = count + 1; i < num; i ++)
{
- setChild( npar, i, getChild( par, i - 1 ) ) ;
+ setChild(npar, i, getChild(par, i - 1));
}
}
- removeInternal( num-1, par ) ;
- return npar ;
- };
+ removeInternal(num-1, par);
+ return npar;
+ }
};
-
-
#endif