Out-Of-Core Rendering (Preprocessing)

A. First Edition

This is the first part of my term project "out of core rendering" of comp7661 and it pre-processes data file

into an octree.

B.The problem

There is one subtle problem which is worth mentioning. Originally the octree is designed to be an "self-incremental" array.

And I am also very careful about the invalid addressing after reallocating array. i.e.

void Octree::createNewSonNode() {

Octee*ptr;

ptr=root+getNewNodeIndex(); //====>this kind of thing I am very careful! you see the "root" might be changed in

                            //getNewNodeIndex which "re-allocate" the array. So, the "ptr" will be invalid.

ptr->level=level+1; //====>>Big Problem!! Because "member data" "level" becomes invalid after "octree array" is moved!

However, this is NOT enough! Even those "member data" is also becoming invalid. This is really subtle and tricky!

D.The major functions

E.Further improvement

F.File listing

1. plyModel.h 

2. Octree.h

3. Octree.cpp

4. main.cpp

file name: plyModel.h

#ifndef PLYMODEL_H
#define PLYMODEL_H



typedef float FVector[3];
typedef unsigned char UCVector[3];
typedef unsigned int UIVector[3];


struct PlyVertex
{
	FVector coord;
	UCVector color;
	FVector normal;
};

struct PlyFace
{
	unsigned char number;
	int* indexList;
	UCVector color;
};

struct PlyModel
{
	int vNumber;//internal usage only
	int fNumber;//internal usage only
	PlyVertex* vertex;
	UIVector* triangle;
	int vertexCount;
	int faceCount;
	FVector maxCoord;
	FVector minCoord;

	//PlyFace* faceList;
	bool analysis(char* buf);
	int readFile(const char* fileName);
	int convertFile(const char* fileName);
	void readDirectory(char* dir);

};

#endif

file name: octree.h

/**********************************************************************
E:\working>octree
finished vertex processing and now start face processing...
finished face processing, now start octree calculation...
total vertex is 11070509 face is 16364639
total process time 4623141
octree info: nodeCount=44414, nodeSize=204
totalNeighbourCount=265602
max depth of octree is 12

E:\working>

*********************************************************************/
#include "plyModel.h"
#include <windows.h>
#include <cstdio>
#include <cstdlib>
#include <stack>

using namespace std;

const int PageSize=64*1024;
const int MaxNodeArrayLength=1024*256;
const int MemoryThreshold=1000;
const int TempFileStartOffset=sizeof(int);
//const int NodeArrayLengthIncrement=10;
const int MaxNeighbourCount=26;

struct InfoStruct
{
	int nodeCount;
	int nodeSize;
	//int nodeArrayLength;
	int totalNeighbourCount;
	int maxDepth;
};

struct Octree
{
	enum OctreeNodeEnum
	{ 
		TOP_LEFT_FRONT =2, TOP_LEFT_BACK =3, 
		TOP_RIGHT_BACK =7, TOP_RIGHT_FRONT =6,	
		BOTTOM_LEFT_FRONT =0, BOTTOM_LEFT_BACK =1, 
		BOTTOM_RIGHT_BACK =5, BOTTOM_RIGHT_FRONT =4 
	};
	static int nodeCount;
	static int maxDepth;
	static Octree root[MaxNodeArrayLength];
	static int nodeArrayLength;
	static int totalNeighbourCount;


	////////////////////////////////////////////////////
	//here goes the preprocessing methods and they will be used only once
	static void createOctreeFromFile(char* vertexFileName, char* faceFileName, 
		char* infoFileName, char* outVertexFileName, char* outFaceFileName, 
		char* octreeFileName);

	static void calculatePageIndex();
	static void calculateNeighbour();
	void doCalculateNeighbour(Octree* theNode);

	void doCreateOctree(HANDLE outVertexHandle);

	int doTraverseOctree(HANDLE outFaceHandle);

	/////////////////////////////////////////////
	//utility methods
	int relativePosition(FVector vPoint, FVector vCtr);
	int relativePosition(UIVector triangle);
	void setSonNodeCentre(int nodeID, FVector vNodeCenter);
	void setupNewSonNode(int nodeID, int sonNodePos);
	
	/////////////////////////////////////////////
	//constructor
	int createNewOctreeNode(int nodeID);


	////////////////////////////////////////////////////
	//the following is all data and try to make sure they are smaller than 64bytes
	FVector center;
	float width;//from center to edge, the half width of edge
	int vNumber;
	int fNumber;
	int vStartIndex;
	int fStartIndex;
	int myNodeIndex;
	int parentIndex;
	int sons[8];
	int vStartPageIndex;//vertex
	int vPageCount;	
	int fStartPageIndex;//face
	int fPageCount;
	void* reserved1;
	void* reserved2;
	unsigned char sonCount;
	unsigned char level;
	unsigned char neighbourCount;
	int neighbours[MaxNeighbourCount];//maximumly 26 neighbours

};

file name: octree.cpp

///////////////////////////////////////////////////////////////
//The molton code scheme is as simple as following:
//1. using an unsigned int (32) for code.
//2. The first 4 bits represents level, , root node starting from 0x0 (this limits our deepest level from 16
//3. each level using 3 bits representing son index.
// I forget this after only two weeks
//
////////////////////////////////////////////////////////////////
////we use the largest radius for radius of octree node
//
//////////////////////////////////////////////////////////////

#include <stdio.h>
#include <math.h>
#include "Octree.h"
#include <windows.h>
#include <winbase.h>

#include "PlyModel.h"

//////////////////////////////////////////////


#define CHECK_NEW(x) if (x==NULL){printf("memory alloc failed\n"); exit(1);}

const double Epsilon=0.001;

int Octree::maxDepth=0;
int Octree::nodeCount=0;
Octree Octree::root[MaxNodeArrayLength];
int Octree::nodeArrayLength=0;
int* hashTable;
int vertexIndexCounter=0;
int Octree::totalNeighbourCount=0;

HANDLE dumpHandle;


void dumpEveryThing()
{
	unsigned long length;
	WriteFile(dumpHandle, &Octree::nodeCount, sizeof(int), &length, NULL);
	WriteFile(dumpHandle, &vertexIndexCounter, sizeof(int), &length, NULL);
	CloseHandle(dumpHandle);
}

void sortTriangle(UIVector triangle)
{
	unsigned int swap;
	if (triangle[0]>triangle[1])
	{
		swap=triangle[0];
		triangle[0]=triangle[1];
		triangle[1]=swap;
	}
	if (triangle[0]>triangle[2])
	{
		swap=triangle[0];
		triangle[0]=triangle[2];
		triangle[2]=swap;
	}
	if (triangle[1]>triangle[2])
	{
		swap=triangle[1];
		triangle[1]=triangle[2];
		triangle[2]=swap;
	}
}


//return the new node index
int Octree::createNewOctreeNode(int nodeID)
{
	int result=nodeCount;
	Octree *ptr;
	//lazy
	if (nodeCount==MaxNodeArrayLength)
	{
		printf("max node array length reached!\n");
		exit(78);

		/*
		newRoot=new Octree[nodeArrayLength+NodeArrayLengthIncrement];
		if (newRoot==NULL)
		{
			printf("allocate new octree node array failed\n");
			exit(1);
		}
		memcpy(newRoot, root, sizeof(Octree)*nodeCount);
		delete[] root;
		root=newRoot;
		nodeArrayLength+=NodeArrayLengthIncrement;
		*/
	}
	nodeCount++;
	
	ptr=root+result;

	setSonNodeCentre(nodeID, ptr->center);
	ptr->width=width/2.0;
	sons[nodeID]=result;
	ptr->myNodeIndex=result;//this will not change

	ptr->neighbourCount=0;
	//these are initialization to make things neat
	ptr->fNumber=ptr->vNumber=ptr->fStartIndex=ptr->vStartIndex=-1;
	ptr->vPageCount=ptr->fPageCount=ptr->vStartPageIndex=ptr->fStartPageIndex=-1;
	ptr->parentIndex=myNodeIndex;
	ptr->level=level+1;
	if (ptr->level>maxDepth)
	{
		maxDepth=ptr->level;
	}
	for (int i=0; i<8; i++)
	{
		ptr->sons[i]=-1;
	}
	ptr->sonCount=0;
	sonCount++;

	return result;
}
		

/////////////////////////////////////////

void Octree::setSonNodeCentre(int nodeID, FVector vNodeCenter)
{
	switch(nodeID)
    {
	case TOP_LEFT_FRONT:
		//vNodeCenter = TPoint(vCtr[0] - width/4, vCtr[1] + width/4, vCtr[2] + width/4);
		vNodeCenter[0] = center[0] - width/4;
		vNodeCenter[1] = center[1] + width/4;
		vNodeCenter[2] = center[2] + width/4;
		break;

	case TOP_LEFT_BACK:
		vNodeCenter[0] = center[0] - width/4;
		vNodeCenter[1] = center[1] + width/4;
		vNodeCenter[2] = center[2] - width/4;
		break;

	case TOP_RIGHT_BACK:
		//vNodeCenter = TPoint(vCtr[0] + width/4, vCtr[1] + width/4, vCtr[2] - width/4);
		vNodeCenter[0] = center[0] + width/4;
		vNodeCenter[1] = center[1] + width/4;
		vNodeCenter[2] = center[2] - width/4;
		break;

	case TOP_RIGHT_FRONT:
		//vNodeCenter = TPoint(vCtr[0] + width/4, vCtr[1] + width/4, vCtr[2] + width/4);
		vNodeCenter[0] = center[0] + width/4;
		vNodeCenter[1] = center[1] + width/4;
		vNodeCenter[2] = center[2] + width/4;
		break;

	case BOTTOM_LEFT_FRONT:
		//vNodeCenter = TPoint(vCtr[0] - width/4, vCtr[1] - width/4, vCtr[2] + width/4);
		vNodeCenter[0] = center[0] - width/4;
		vNodeCenter[1] = center[1] - width/4;
		vNodeCenter[2] = center[2] + width/4;
		break;

	case BOTTOM_LEFT_BACK:
		//vNodeCenter = TPoint(vCtr[0] - width/4, vCtr[1] - width/4, vCtr[2] - width/4);
		vNodeCenter[0] = center[0] - width/4;
		vNodeCenter[1] = center[1] - width/4;
		vNodeCenter[2] = center[2] - width/4;
		break;

	case BOTTOM_RIGHT_BACK:
		//vNodeCenter = TPoint(vCtr[0] + width/4, vCtr[1] - width/4, vCtr[2] - width/4);
		vNodeCenter[0] = center[0] + width/4;
		vNodeCenter[1] = center[1] - width/4;
		vNodeCenter[2] = center[2] - width/4;
		break;

	case BOTTOM_RIGHT_FRONT:
		//vNodeCenter = TPoint(vCtr[0] + width/4, vCtr[1] - width/4, vCtr[2] + width/4);
		vNodeCenter[0] = center[0] + width/4;
		vNodeCenter[1] = center[1] - width/4;
		vNodeCenter[2] = center[2] + width/4;
		break;
    }	
}

int Octree::relativePosition(FVector vPoint, FVector vCtr)
{

	if( (vPoint[0] <= vCtr[0]) && (vPoint[1] >= vCtr[1]) && (vPoint[2] >= vCtr[2]) )
	{
		return TOP_LEFT_FRONT;
	}

	if( (vPoint[0] <= vCtr[0]) && (vPoint[1] >= vCtr[1]) && (vPoint[2] <= vCtr[2]) )
	{
		return TOP_LEFT_BACK;
	}
	if( (vPoint[0] >= vCtr[0]) && (vPoint[1] >= vCtr[1]) && (vPoint[2] <= vCtr[2]) )
	{
		return TOP_RIGHT_BACK;
	}

	if( (vPoint[0] >= vCtr[0]) && (vPoint[1] >= vCtr[1]) && (vPoint[2] >= vCtr[2]) )
	{
		return TOP_RIGHT_FRONT;
	}
	if( (vPoint[0] <= vCtr[0]) && (vPoint[1] <= vCtr[1]) && (vPoint[2] >= vCtr[2]) )
	{
		return BOTTOM_LEFT_FRONT;
	}

	if( (vPoint[0] <= vCtr[0]) && (vPoint[1] <= vCtr[1]) && (vPoint[2] <= vCtr[2]) )
	{
		return BOTTOM_LEFT_BACK;
	}

	if( (vPoint[0] >= vCtr[0]) && (vPoint[1] <= vCtr[1]) && (vPoint[2] <= vCtr[2]) )
	{
		return BOTTOM_RIGHT_BACK;
	}

	if( (vPoint[0] >= vCtr[0]) && (vPoint[1] <= vCtr[1]) && (vPoint[2] >= vCtr[2]) ) 
	{
		return BOTTOM_RIGHT_FRONT;
	} 
	//we should never reach this
	return -1;
}

//hard coding page size=64k
void Octree::calculatePageIndex()
{
	int vertexSize=sizeof(PlyVertex);
	int faceSize=sizeof(UIVector);
	int startOffset, endOffset;
	Octree*ptr;

	for (int i=0; i<nodeCount; i++)
	{
		ptr=root+i;
		startOffset=ptr->vStartIndex*vertexSize;
		endOffset=(ptr->vStartIndex+ptr->vNumber)*vertexSize;
		ptr->vStartPageIndex=startOffset/PageSize;

		ptr->vPageCount=(endOffset-startOffset)/PageSize;
		if ((endOffset-startOffset)%PageSize!=0)
		{
			ptr->vPageCount++;
		}
		//repeat

		startOffset=ptr->fStartIndex*faceSize;
		endOffset=(ptr->fStartIndex+ptr->fNumber)*faceSize;
		ptr->fStartPageIndex=startOffset/PageSize;

		ptr->fPageCount=(endOffset-startOffset)/PageSize;
		if ((endOffset-startOffset)%PageSize!=0)
		{
			ptr->fPageCount++;
		}
	}
}
	
void Octree::doCalculateNeighbour(Octree* theNode)
{
	Octree* ptr;
	int i;
	float distance;
	if (theNode==this)
	{
		return;
	}
	if (level<theNode->level)
	{
		for (i=0; i<8; i++)
		{
			if (sons[i]!=-1)
			{
				ptr=root+sons[i];
				ptr->doCalculateNeighbour(theNode);
			}
		}
	}
	else
	{
		if (level==theNode->level)
		{
			//check all sides to see if they colinear			
			for (i=0; i<3; i++)
			{
				//all coord must be exact one width away or colinear 
				distance=fabs(center[i]-theNode->center[i]);
				if (distance>Epsilon)
				{			
					distance=fabs(distance-width);
					if (distance>Epsilon)
					{
						//no! this is far away
						return;
					}
				}
			}
			//got it
			theNode->neighbours[theNode->neighbourCount]=myNodeIndex;
			theNode->neighbourCount++;	
			totalNeighbourCount++;
			if (theNode->neighbourCount>MaxNeighbourCount)
			{
				printf("corrupted data or neighbour calculation mistake\n");
				exit(77);
			}
		}	
	}
	//in all case we end
}



void Octree::calculateNeighbour()
{
	Octree* ptr;
	for (int i=0; i<nodeCount; i++)
	{
		ptr=root+i;
		root->doCalculateNeighbour(ptr);
	}
}




void Octree::createOctreeFromFile(char* vertexFileName, char* faceFileName, char* infoFileName,
		char* outVertexFileName, char* outFaceFileName, char* octreeFileName)
{
	HANDLE infoHandle, inVertexHandle, outVertexHandle, inFaceHandle, outFaceHandle, octreeHandle;
	Octree* ptr;
	PlyModel ply;
	int i;
	float sideWidth;
	unsigned long length;
		
	infoHandle=CreateFile(infoFileName, GENERIC_READ|GENERIC_WRITE, 0, NULL, OPEN_EXISTING, 
		FILE_ATTRIBUTE_NORMAL , NULL);
	
	if (infoHandle==INVALID_HANDLE_VALUE)
	{
		printf("open file failed\n");
		exit(3);
	}
	dumpHandle=CreateFile("dumpfile.data", GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, 
		FILE_ATTRIBUTE_NORMAL , NULL);

	//MUST OVER WRITE
	octreeHandle=CreateFile(octreeFileName, GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, 
		FILE_ATTRIBUTE_NORMAL , NULL);

	if (ReadFile(infoHandle, &ply, sizeof(PlyModel), &length, NULL)==0)
	{
		printf("read info failed\n");
		exit(4);
	}
	inVertexHandle=CreateFile(vertexFileName, GENERIC_READ, 0, NULL, OPEN_EXISTING, 
		FILE_ATTRIBUTE_NORMAL , NULL);

	outVertexHandle=CreateFile(outVertexFileName, GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, 
		FILE_ATTRIBUTE_NORMAL , NULL);

	inFaceHandle=CreateFile(faceFileName, GENERIC_READ, 0, NULL, OPEN_EXISTING, 
		FILE_ATTRIBUTE_NORMAL , NULL);

	outFaceHandle=CreateFile(outFaceFileName, GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, 
		FILE_ATTRIBUTE_NORMAL , NULL);
	if (outVertexHandle==INVALID_HANDLE_VALUE||inVertexHandle==INVALID_HANDLE_VALUE
		||outFaceHandle==INVALID_HANDLE_VALUE||inFaceHandle==INVALID_HANDLE_VALUE
		||octreeHandle==INVALID_HANDLE_VALUE||dumpHandle==INVALID_HANDLE_VALUE)
	{
		printf("cannot create output vertex file\n");
		exit(9);
	}


	//nodeArrayLength+=NodeArrayLengthIncrement;
	//root=new Octree[nodeArrayLength];
	//CHECK_NEW(root);
	hashTable=new int[ply.vertexCount];
	CHECK_NEW(hashTable);
	//calculate the center and width of root
	ptr=root;
	nodeCount=1;
	ptr->width=0.0;
	for (i=0; i<3; i++)
	{
		ptr->center[i]=(ply.minCoord[i]+ply.maxCoord[i])/2.0;
		sideWidth=ply.maxCoord[i]-ply.minCoord[i];
		if (ptr->width<sideWidth)
		{
			ptr->width=sideWidth;
		}
	}
	ptr->width;
	ptr->level=0;
	ptr->parentIndex=-1;
	ptr->fStartIndex=0;
	ptr->fNumber=ply.faceCount;
	ptr->vStartIndex=0;
	ptr->vNumber=ply.vertexCount;
	ptr->neighbourCount=0;
	for(i=0; i<8; i++)
	{
		ptr->sons[i]=-1;
	}
	ptr->sonCount=0;
	//hard coding this;
	ptr->myNodeIndex=0;
	ptr->vPageCount=ptr->fPageCount=-1;
	ptr->vStartPageIndex=ptr->fStartPageIndex=-1;

	if (ply.vertexCount>MemoryThreshold)
	{		
		ptr->reserved1=inVertexHandle;
		ptr->reserved2=INVALID_HANDLE_VALUE;
		ptr->doCreateOctree(outVertexHandle);
	}

	printf("finished vertex processing and now start face processing...\n");
	if (ptr->sonCount>0)
	{
		ptr->reserved1=inFaceHandle;
		ptr->fNumber=ptr->doTraverseOctree(outFaceHandle);
	}

	ply.faceCount=ptr->fNumber;
	SetFilePointer(infoHandle, 0, NULL, FILE_BEGIN);

	if (WriteFile(infoHandle, &ply, sizeof(PlyModel), &length, NULL)==0)
	{
		printf("write back info file failed\n");
		exit(82);
	}
	if (WriteFile(infoHandle, &Octree::nodeCount, sizeof(int), &length, NULL)==0)
	{
		printf("write back info file failed\n");
		exit(82);
	}

	delete[] hashTable;
	printf("finished face processing, now start octree calculation...\n");
	calculatePageIndex();
	calculateNeighbour();

	InfoStruct infoStruct;
	infoStruct.nodeCount=Octree::nodeCount;
	infoStruct.nodeSize=sizeof(Octree);
	infoStruct.totalNeighbourCount=Octree::totalNeighbourCount;
	infoStruct.maxDepth=Octree::maxDepth;
	if (WriteFile(infoHandle, &infoStruct, sizeof(InfoStruct), &length, NULL)==0)
	{
		printf("write back info file failed\n");
		exit(82);
	}

	printf("total vertex is %d face is %d\n", ply.vertexCount, ply.faceCount);


	if (WriteFile(octreeHandle, Octree::root, sizeof(Octree)*Octree::nodeCount, &length, NULL)==0)
	{
		printf("write octree file failed\n");
		exit(82);
	}
	CloseHandle(inVertexHandle);
	CloseHandle(octreeHandle);
	CloseHandle(outVertexHandle);
	CloseHandle(inFaceHandle);
	CloseHandle(outFaceHandle);
	CloseHandle(infoHandle);
}
		
/*
void Octree::setupNewSonNode(int nodeID, int sonNodePos)
{
	Octree* ptr;
	ptr=root+ sonNodePos;
	sons[nodeID]=sonNodePos;
	ptr->parentIndex=myNodeIndex;
	setSonNodeCentre(nodeID, ptr->center);
	ptr->width=width/2.0;
}
*/

//this will return the actual face after sorting
int Octree::doTraverseOctree(HANDLE outFaceHandle)
{
	HANDLE tempFileHandle[8];
	char tempFileName[8][MAX_PATH];
	int i, j, k;
	unsigned long length;
	int tempFaceCounter[8];
	UIVector triangle;
	int nodeID;
	HANDLE faceHandle;

	faceHandle=(HANDLE)reserved1;
	
	//remember to read from beginning
	SetFilePointer(faceHandle, 0, NULL, FILE_BEGIN);

	if (sonCount==0)
	{
		for (i=0; i<fNumber; i++)
		{
			if (ReadFile(faceHandle, triangle, sizeof(UIVector), &length, NULL)==0)
			{
				printf("read temp vertex file failed\n");
				exit(11);
			}	
			if (WriteFile(outFaceHandle, triangle, sizeof(UIVector), &length, NULL)==0)
			{
				printf("write output vertex file failed\n");
				exit(11);
			}					
		}
		return fNumber;
	}

	//else
	for (i=0; i<8; i++)
	{
		tempFaceCounter[i]=0;
		if (GetTempFileName(".", "face", 0, tempFileName[i])==0)
		{
			printf("get temp file name failed\n");
			exit(44);
		}		
		tempFileHandle[i]=CreateFile(tempFileName[i], GENERIC_READ|GENERIC_WRITE, 0, NULL, 
			OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
	
		if (tempFileHandle[i]==INVALID_HANDLE_VALUE)
		{
			printf("open temp file failed %d\n", GetLastError());
			exit(55);
		}
	}

	for (i=0; i<fNumber; i++)
	{
		if (ReadFile(faceHandle, triangle, sizeof(UIVector), &length, NULL)==0)
		{
			printf("read file fails\n");
			exit(2);
		}
		//update vertex index
		if (level==0)
		{
			for (j=0; j<3; j++)
			{
				triangle[j]=hashTable[triangle[j]];
			}
			//in this case, we don't have to sort triangle because it is still
			//possible in different nodes, but it makes neat
			sortTriangle(triangle);
		}
		for (j=0; j<8; j++)
		{
			Octree* ptr;
			if (sons[j]!=-1)
			{
				ptr=root+sons[j];
				for (k=0; k<3; k++)
				{
					//this will count the face possibly in multiple nodes
					if (triangle[k]>=ptr->vStartIndex&&triangle[k]<ptr->vStartIndex+ptr->vNumber)
					{
						nodeID=j;
						if (WriteFile(tempFileHandle[nodeID], triangle, sizeof(UIVector), 
								&length, NULL)==0)
						{
							printf("write temp file failed with error code %d\n", GetLastError());
							exit(4);
						}
						tempFaceCounter[nodeID]++;
						//don't count twice
						break;
					}
				}
			}
		}
	}
	//so, we have two kinds of face number "inflation". the following is our sibling at same 
	//level. The below is our children nodes. So, here we don't have to update face number
	//because it is still not right
	//first we need to update the "face number" because some face is overlapping across nodes

	//we calculate from parent starting index
	int currentFaceCount=0;

	for (i=0; i<8; i++)
	{
		if (tempFaceCounter[i]>0)
		{			
			Octree* ptr;
			ptr=root+sons[i];	
			ptr->reserved1=tempFileHandle[i];
			ptr->fStartIndex=fStartIndex+currentFaceCount;
			ptr->fNumber=tempFaceCounter[i];
			//the son node will update inflated face number itself
			currentFaceCount+=ptr->doTraverseOctree(outFaceHandle);				
		}
		//this is of course the safe point to delete and close file
		//and in both case, we need to close file.
		if (CloseHandle(tempFileHandle[i])==0)
		{
			printf("close handle failed\n");
			exit(9);
		}
		if (DeleteFile(tempFileName[i])==0)
		{
			printf("delete file failed\n");
			exit(83);
		}	
	}
	//here update the total face number
	fNumber=currentFaceCount;
	//reporting inflated face number to parent for updating
	return fNumber;
}

	
void Octree::doCreateOctree(HANDLE outVertexHandle)
{
	HANDLE tempFileHandle[8], tempIndexFileHandle[8];
	char tempFileName[8][MAX_PATH], tempIndexFileName[8][MAX_PATH];
	int i, j;
	unsigned long length;
	int currentIndex;
	int tempVertexCounter[8];
	PlyVertex plyVertex;
	int nodeID;
	HANDLE vertexHandle, indexHandle;

	vertexHandle=(HANDLE)reserved1;
	indexHandle=(HANDLE)reserved2;
	//remember to read from beginning
	SetFilePointer(vertexHandle, 0, NULL, FILE_BEGIN);
	if (indexHandle!=INVALID_HANDLE_VALUE)
	{
		SetFilePointer(indexHandle, 0, NULL, FILE_BEGIN);
	}

	for (i=0; i<8; i++)
	{
		tempVertexCounter[i]=0;
		if (GetTempFileName(".", "vertex", 0, tempFileName[i])==0)
		{
			printf("get temp file name failed\n");
			exit(44);
		}		
		if (GetTempFileName(".", "index", 0, tempIndexFileName[i])==0)
		{
			printf("get temp file name failed\n");
			exit(44);
		}			
		tempFileHandle[i]=CreateFile(tempFileName[i], GENERIC_READ|GENERIC_WRITE, 0, NULL, 
			OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
		tempIndexFileHandle[i]=CreateFile(tempIndexFileName[i], GENERIC_READ|GENERIC_WRITE, 
			0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
		if (tempFileHandle[i]==INVALID_HANDLE_VALUE
			||tempIndexFileHandle[i]==INVALID_HANDLE_VALUE)
		{
			printf("open temp file failed %d\n", GetLastError());
			exit(55);
		}
	}

	for (i=0; i<vNumber; i++)
	{
		if (ReadFile(vertexHandle, &plyVertex, sizeof(PlyVertex), &length, NULL)==0)
		{
			printf("read file fails\n");
			exit(2);
		}
		if (indexHandle!=INVALID_HANDLE_VALUE)
		{
			if (ReadFile(indexHandle, &currentIndex, sizeof(int), &length, NULL)==0)
			{
				printf("read index file failed\n");
				exit(9);
			}
		}
		else
		{
			currentIndex=i;
		}

		nodeID=relativePosition(plyVertex.coord, center);
		if (WriteFile(tempFileHandle[nodeID], &plyVertex, sizeof(PlyVertex), 
			&length, NULL)==0)
		{
			printf("write temp file failed with error code %d\n", GetLastError());
			exit(4);
		}
		if (WriteFile(tempIndexFileHandle[nodeID], &currentIndex, sizeof(int), &length, 
			NULL)==0)
		{
			printf("write index file failed code %d\n", GetLastError());
			exit(3);
		}
		tempVertexCounter[nodeID]++;
	}
	//we calculate from parent starting index
	int currentVertexIndex=vStartIndex;
	for (i=0; i<8; i++)
	{				
		int sonNodePos;
		if (tempVertexCounter[i]>0)
		{
			sonNodePos=createNewOctreeNode(i);	
			
			root[sonNodePos].vNumber=tempVertexCounter[i];
			root[sonNodePos].vStartIndex=currentVertexIndex;
			currentVertexIndex+=tempVertexCounter[i];
		}
		if (tempVertexCounter[i]>MemoryThreshold)
		{			
			root[sonNodePos].reserved1=tempFileHandle[i];
			root[sonNodePos].reserved2=tempIndexFileHandle[i];
			root[sonNodePos].doCreateOctree(outVertexHandle);	
			//after this recursion, the temp file will not be used any more
		}
		else
		{
			SetFilePointer(tempFileHandle[i], 0, NULL, FILE_BEGIN);			
			SetFilePointer(tempIndexFileHandle[i], 0, NULL, FILE_BEGIN);
			for (j=0; j<tempVertexCounter[i]; j++)
			{
				if (ReadFile(tempFileHandle[i], &plyVertex, sizeof(PlyVertex), &length, NULL)==0)
				{
					printf("read temp vertex file failed\n");
					exit(11);
				}
				if (ReadFile(tempIndexFileHandle[i], &currentIndex, sizeof(int), &length, NULL)==0)
				{
					printf("read temp index file failed\n");
					exit(2);
				}
				hashTable[currentIndex]=vertexIndexCounter;

				if (WriteFile(outVertexHandle, &plyVertex, sizeof(PlyVertex), &length, NULL)==0)
				{
					printf("write output vertex file failed\n");
					exit(11);
				}
				vertexIndexCounter++;
			}
		}

		//this is of course the safe point to delete and close file
		if (CloseHandle(tempFileHandle[i])==0||CloseHandle(tempIndexFileHandle[i])==0)
		{
			printf("close handle failed\n");
			exit(9);
		}
		if (DeleteFile(tempFileName[i])==0||DeleteFile(tempIndexFileName[i])==0)
		{
			printf("delete file failed\n");
			exit(81);
		}
	}
}





		











/*
void MyOctree::createOctree(TPoint* ptArray, int ptNumber, float max3[3], float min3[3], int* theIndexArray, 
		int theFaceNumber, int colorChoice, float* myColor)
{
	float fl_x, fl_y, fl_z;
	int i, j;
	float temp;
	int* hashTable;
	int nodeFaceIndexCounter[RENDER_OCTREE_NODE_NUMBER];


	hierOct=createNewNode(NULL, 0);
	hierOct->parent=NULL;
	hierOct->level=0;
	//codeArray=new uint[ptNumber];
	//father=NULL;
	//level=0;
	fl_x=max3[0]-min3[0];//x
	fl_y=max3[1]-min3[1];//y
	fl_z=max3[2]-min3[2];//z

	temp=fl_x;
	//size will be the max among three dimension
	if (fl_y>temp)
	{
		temp=fl_y;
	}
	if (fl_z>temp)
	{
		temp=fl_z;
	}
	hierOct->center.pt[0]=(max3[0]+min3[0])/2.0;
	hierOct->center.pt[1]=(max3[1]+min3[1])/2.0;
	hierOct->center.pt[2]=(max3[2]+min3[2])/2.0;
	//hierOct->width=temp+Epsilon;
	hierOct->width=temp;
	
	vector<int> indexList[8];//becomes member
	//float* vCtr=hierOct->center;
	
	//init here

	for( i = 0; i < ptNumber; i++)
	{
		int position;

		//float* vPoint=ptArray[i].pt;	
		position=hierOct->relativePosition(ptArray[i].pt, hierOct->center.pt);
		indexList[position].push_back(i);
	}
	//doCreateOctree(ptArray, indexList);
	hierOct->beginCreateOctree(ptArray, indexList);



	pointNumber=gIndexList.size();
	//now let's copy the pointer array in an order of leaf of BFS or DFS 
	pointArray=new TPoint[pointNumber];

	
	ubyte r=0,g=0,b=0;
	
	int sonIndex=0;

	///////////////////////////////////////////////////
	//this is the ending index array
	calculateNodePointCount(nodeVertexCounter);
	hashTable=new int[pointNumber];

	///////////////////////////////////////////////////
	
	for (i=0; i<pointNumber; i++)
	{
		int myTemp=gIndexList[i];
		pointArray[i]=ptArray[myTemp];
		hashTable[myTemp]=i;

		//assign pseudo color for each point by its index.
		
		//pointArray[i].color[3]=255;
		switch (colorChoice)
		{
		case PSEUDO_COLOR:	
			pointArray[i].color[0]=r;
			pointArray[i].color[1]=g;
			pointArray[i].color[2]=b;
			pointArray[i].color[3]=sonIndex;
			//this is how you increment
			if (b==255)
			{
				b=0;
				if (g==255)
				{
					r++;
					g=0;				
				}
				else
				{
					g++;				
				}
			}
			else
			{
				b++;
			}
		
			//this is the last one in segment
			while (hierOct->sons[sonIndex]==NULL)
			{
				sonIndex++;
			}
			
			if (i==hierOct->sons[sonIndex]->endIndex)
			{
				sonIndex++;			
			}
			break;
		case RANDOM_COLOR:
			if (textureSize>0)
			{
				pointArray[i].color[0]= colorTexture[i%textureSize+0];
				pointArray[i].color[1]= colorTexture[i%textureSize+1];
				pointArray[i].color[2]= colorTexture[i%textureSize+2];
				pointArray[i].color[3]= colorTexture[i%textureSize+3];
			}
			else
			{
				pointArray[i].color[0]=rand()%256;
				pointArray[i].color[1]=rand()%256;
				pointArray[i].color[2]=rand()%256;
				pointArray[i].color[3]=rand()%256;
			}
			break;
		case ORIGIN_COLOR:
			break;
		case ASSIGN_COLOR:
			if (myColor==NULL)
			{
				printf("you want to assign some color, but you haven't passed it.\n");				
			}
			else
			{
				memcpy(pointArray[i].color, myColor, sizeof(float)*4);
			}
			break;
		}
	
	}

	for (i=0; i<RENDER_OCTREE_NODE_NUMBER; i++)
	{
		nodeFaceCounter[i]=nodeFaceIndexCounter[i]=0;
	}
	////////////////////////////////////////////////
	//now let's convert the facelist
	indexArray=new int[theFaceNumber*3];//triangle
	//first pass we need to convert the index and count how many faces are there for 
	//each node
	int theIndex;
	int* ptr;
	int tempCounter=0;
	for (i=0; i<theFaceNumber; i++)
	{
		ptr=theIndexArray+3*i;
		
		ptr[0]=hashTable[ptr[0]];
		theIndex=ptr[0];

		ptr[1]=hashTable[ptr[1]];
		//we need to find the smallest index to decide which node it is in
		//NO! we need to find the biggest index to decide which node it is in
		//because in flat shading the last vertex decides the color and
		//we need the color to determine that which node the triangle belongs to 
		if (ptr[0]>ptr[1])
		{
			//do swap			
			ptr[0]=ptr[1];
			ptr[1]=theIndex;						
		}
		else
		{
			theIndex=ptr[1];
		}

		ptr[2]=hashTable[ptr[2]];
		//we need to find the smallest index to decide which node it is in
		//NO! we need to find the biggest index to decide which node it is in
		//because in flat shading the last vertex decides the color and
		//we need the color to determine that which node the triangle belongs to 
		if (ptr[1]>ptr[2])
		{
			ptr[1]=ptr[2];
			ptr[2]=theIndex;			
		}
		else
		{
			theIndex=ptr[2];
		}

		//now let's find the node it belongs to 
		//tempCounter=0;
		for (j=0; j<RENDER_OCTREE_NODE_NUMBER; j++)
		{			
			if (theIndex<=nodeVertexCounter[j])
			{
				nodeFaceCounter[j]++;//the index is j
				break;
			}
		}
	}
	//now let's convert it into ending index
	tempCounter=0;
	for (i=0; i<RENDER_OCTREE_NODE_NUMBER; i++)
	{
		tempCounter+=nodeFaceCounter[i];
		nodeFaceCounter[i]=tempCounter;
	}

	delete[]hashTable;
	//////////////////////////
	//now let's do the second pass since we have already known the 
	//number of faces in each node
	int* dest;
	for (i=0; i<theFaceNumber; i++)
	{
		ptr=theIndexArray+3*i;
		
		for (j=0; j<RENDER_OCTREE_NODE_NUMBER; j++)
		{
			//it must be within the index before increment
			//because in flat shading the last vertex decides the color and
			//we need the color to determine that which node the triangle belongs to 
			if (ptr[2]<=nodeVertexCounter[j])
			{
				//now we know it should be copied here
				if (j==0)
				{
					tempCounter=0;
				}
				else
				{
					tempCounter=nodeFaceCounter[j-1];
				}
				dest=indexArray+(tempCounter+nodeFaceIndexCounter[j])*3;
				memcpy(dest, ptr, sizeof(int)*3);
				nodeFaceIndexCounter[j]++;				
				break;
			}
			//else we continue to search
			tempCounter+=nodeVertexCounter[j];
		}
	}
	faceNumber=theFaceNumber;
	//now we don't need the hashtable anymore




}


MyOctree* MyOctree::createNewNode(MyOctree* father, int index)
{
	//int sonLevel;
	MyOctree* result;
	CodeType mask;
	//uint levelMask=0x0fffffff;
	const CodeType IndexMask=0x0FFFFFFFFFFFFFFF;

	result= new MyOctree;

	if (father==NULL)//this is the root
	{		
		result->nameCode=0;//zero level, zero index		
	}
	else
	{
		mask=father->level+1;
		//sonLevel=father->level+1;
		//level makes 4 bits
		mask<<=LevelShiftOffset;
		result->nameCode= (father->nameCode & IndexMask);
		result->nameCode |= mask;
		mask=index;
		//total shift is 25, and deduct level*3;
		//we need father's level because root is useless here.
		mask<<=(LevelShiftOffset- (father->level+1)*3);//logically clear
		result->nameCode |= mask;
		//level=father->level+1;
		//parent=father;
		//width=father->width/2.0;
	}

	return result;
}


void MyOctree::beginCreateOctree(TPoint* ptArray, vector<int> parentIndexList[8])
{
	bool bFirstSon=true;
	int lastSonIndex=0, firstSonIndex=0;
	//int index;
	float tempMax=0;
	int pointCount;
	for (int i=0; i<8; i++)
	{
		pointCount=parentIndexList[i].size();
		//Here I borrow the idea of RG's comment
		//if(pointCount >= POINTS_PER_OCTREE_CELL) 
		//you do the number checking at "doCreateOctree"!!!!
		if(pointCount >0) 
		{			
			sons[i] = createNewNode(this, i);
		
			sons[i]->level=level+1;
			sons[i]->width=width/2.0;
			sons[i]->parent = this;

			setSonNodeCentre(i, sons[i]->center.pt);			
			// Changed to accomodate a vector version.
			// Viola !! the parent is set here !
			sons[i]->doCreateOctree(ptArray, parentIndexList[i]);	
			/////////////////////////////////////////////////////////
			//after this recursion, son node should already calculate its radius and 
			//we just pick up the maximum amongn all son node.
			if (sons[i]->radius > tempMax)
			{
				tempMax=sons[i]->radius;
			}
			if (sons[i]->radius==0)
			{
				printf("what is going on\n");
			}
			sonCount++;
			if (bFirstSon)
			{
				bFirstSon=false;
				//the parent startIndex starts from first son's startIndex
				startIndex=sons[i]->startIndex;
				firstSonIndex=i;
			}
			sons[i]->index=i;
	
			lastSonIndex=i;
		}
	}

	//before we return, we pick up the max radius among all sons.
	if (tempMax>radius)
	{
		radius=tempMax;
	}
	else
	{
		printf("cound this happen?\n");
	}
	//assert(radius>0);


	//we try to see the last son index here
	endIndex=sons[lastSonIndex]->endIndex;
}


//guaranttee to have at least one point
void MyOctree::doCreateOctree(TPoint* ptArray, vector<int> parentIndexList)
{
	int position;
	int pointCount=parentIndexList.size();
	//bool isLeaf= (level==MAX_LEVEL)||(pointCount==1);

	//this is for collectLeafNode, otherwise
	bool isLeaf= (level==MAX_LEVEL)||(level>=MIN_LEVEL&&pointCount<POINTS_PER_OCTREE_CELL);


	if (isLeaf)
	{
		//try to calculate average coordinate and its normal
		//calculatePointAverage(ptArray, indexList);
		//here we simply chop the unnecessary points
		collectLeafNode(parentIndexList, ptArray);
		//return and no more recursion
	}
	else
	{
		vector<int> myIndexList[8];
		//no need to check if IndexList is empty cause it is checked in parent's "beginCreateOctree"
		for (vector<int>::const_iterator it=parentIndexList.begin(); it!=parentIndexList.end(); ++it)
		{
			position=relativePosition(ptArray[*it].pt, center.pt);
			myIndexList[position].push_back(*it);
		}	
		beginCreateOctree(ptArray, myIndexList);
	}

}

void MyOctree::collectLeafNode(vector<int> parentIndexList, TPoint* ptArray)
{
	int pointCount=parentIndexList.size();
	
	int stride=1;
	float tempMax=0;
	int temp;
	
	bSubDivided=false;

	//the maximum we want is  POINTS_PER_OCTREE_CELL
#ifndef USING_TRIANGLE_BASED_MODEL
	if (pointCount>POINTS_PER_OCTREE_CELL)
	{
		stride=pointCount/POINTS_PER_OCTREE_CELL;
		pointCount=POINTS_PER_OCTREE_CELL;
	}
#endif
	//else we just copy what we get from parent node

	startIndex=gIndexList.size();
	endIndex=startIndex+pointCount-1;
	//here we bookkeep the index
	//this stupid mistake costs me more than three days!!!!!
	for (int i=0; i<pointCount; i++)
	{
		temp=parentIndexList[i*stride];
		gIndexList.push_back(temp);
		ptArray[temp].nameCode=this->nameCode;
		if (ptArray[temp].radius>tempMax)
		{
			tempMax=ptArray[temp].radius;
		}	
	}

	//we use the largest radius for radius of octree node
	radius=tempMax;

}

*/

file name: main.cpp

#include "octree.h"
#include <stdio.h>

char* vertexFileName="vertex.data";
char* faceFileName="face.data";
char* infoFileName="info.data";
char* outVertexFileName="outVertex.data";
char* outFaceFileName="outFace.data";
char* octreeFileName="octree.data";

extern void dumpEveryThing();

int main()
{
	atexit(dumpEveryThing);
	DWORD start=GetTickCount();
	Octree::createOctreeFromFile(vertexFileName, faceFileName, infoFileName,
		outVertexFileName, outFaceFileName, octreeFileName);

	start=GetTickCount()-start;
	printf("total process time %d\n", start);
	printf("octree info: nodeCount=%d, nodeSize=%d\n", Octree::nodeCount, sizeof(Octree));
	printf("totalNeighbourCount=%d\n", Octree::totalNeighbourCount);
	printf("max depth of octree is %d\n", Octree::maxDepth);
	return 0;
}

///////////////////////////////

The input files are output from my previous little tool reader of ply file:

E:\working>octree
finished vertex processing and now start face processing...
finished face processing, now start octree calculation...
total vertex is 11070509 face is 16364639
total process time 4623141
octree info: nodeCount=44414, nodeSize=204
totalNeighbourCount=265602
max depth of octree is 12