out of core rendering

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

1. Convert original "big-endian" format to "little-endian" with supplied software, merge total 1100 model files into one big file. Also during this pass calculate the bounding of whole data for octree construction.
2. Using two-pass to sort data model into octree by loading segments by segments of whole data into memory. (I think it is impossible to do it in one pass because the sequence of vertex is changed and the triangle's index array can only be modified until vertex is sorted.) So, the first pass to sort vertex and second pass to sort triangle.
3. Precalculate all neighbours of each octree node and store this infomation in octree nodes. I think this is the best solution for "neighbour-finding" in octree.
4. All data structure will be saved as memory image in file so that at run time just simple loading and update of starting address of array is needed. To do that, all "pointers" are just index numbers which can used when reloading.
5. The triangles at boundary which run across multiple octree nodes will be calculated multiple times in each node. Therefore the number of triangle will inflate after sorting about 30%.
6. The preprocess of 11million vertex and 12million triangles take a little more than one hour. (After preprocessing, the number of triangle becomes 16million.) There are total 44414 octree nodes and total memory usage will be nearly 9M and will be saved as memory image in file. The maximum depth of octree is 12 and total pre-calculated neighbour nodes for all octree nodes are 265k.
7. I use 1000 vertex as threshold for octree leaf node. Maybe it is a little bit too big? What do you think? The model is "power plant" of which the length of bounding box is more than 80000. Should I decide this "leaf node" size according to each model?

¡¡

C.The idea of program
¡¡

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

    ¡¡

    ¡¡

    ¡¡

    ¡¡