/*********************************************************************************************** * * Copyright © DreamWorks Interactive. 1997 * * Implementation of texture packing. * * This will pack square and rectangular textures in to a texture page 256x256. Each texture * surface is 2 texture pages which are interleaved on a pixel byte interval and therefore the * stride of each texture surface is 512 pixels. The stride of 512 is VERY important because * it is what gives us the capability of tiling textures, these textures are created by having * an empty bit at bit 8 which is ignored by the texture walking but is used when the texel * address is calculated. This results in 256 texels and then a gap of 256 texels, this leads * to a width of 256, a stride of 512 and a second texture page that starts 256 bytes after * the first. * * The structures used by this packer, mainly the quad tree, are aligned to a bytes boundary. * This is so memory overhead in minimal and performance is not essential here although it * still has to be very fast. From an individual model there will only be about 10 textures * that are loaded so the unaligned access will not cause any noticable decrease in speed. * * NOTE: The data in the packed surface is not affected by any operation within CPackedRaster * *********************************************************************************************** * * $Log:: /JP2_PC/Source/Lib/Loader/TexturePackSurface.cpp $ * * 18 8/26/98 5:20p Asouth * Fixed loop-scoping error * * 17 4/25/98 8:07p Agrant * Do not print out for every texture * * 16 4/24/98 4:08p Rwyatt * Fixed assert if a 8x256 map was packed first in a page. * * 15 4/21/98 3:12p Rwyatt * New pack surface type for smallest mip maps. * New logic to set the smallest mip maps * * 14 3/30/98 11:13p Rwyatt * Modified to allow a parent surface that is not 256x256. This is still themaximum size but now * any power of 2 and sqaure raster can be used, * There is also a minimum now a minimum size that all smaller allocations are rounded upto. * * 13 3/17/98 7:59p Rwyatt * Added a few asserts * * 12 3/17/98 7:53p Rwyatt * Added new functions that allow textures to be packed at a specified location. * * 11 3/11/98 3:50p Rwyatt * Fixed a serious bug in the delete function. * * 10 3/06/98 8:41p Rwyatt * The check for less than 256 is now an always assert because larger maps cause all sorts of * problems. * * 9 2/24/98 6:55p Rwyatt * CTexturePackSurface has been split into two seperate classes. The new class CPackedRaster * does the packing on a single raster and the old class has been modifed to suit. * * 8 1/29/98 7:41p Rwyatt * New mip settings for special cases such as curved bump map parents * * 7 1/14/98 6:25p Rwyatt * Modified very incorrect comment * * 6 1/09/98 7:04p Rwyatt * Each pack surface has a base mip level which is used to determine what can be packed in it. * The default is don't care * * 5 12/04/97 4:14p Rwyatt * Packed rasters are now allocated from virtual memory * Removed some memory counters * * 4 9/01/97 7:57p Rwyatt * Delete member can now handle any surfcaes of any bit depth * * 3 8/19/97 7:03p Rwyatt * Sub allocated mem rasters (such as textures) now have an rpt back to the parent Texture Pack * surface. This is so the packer can be infomred when the texture is deleted, it is an rptr to * avoid static destructor dependencies. * * 2 7/29/97 2:01a Rwyatt * Latest packer, this version has no knowledege about the thing that represents the sub region. * No texture pointer is stored in the quad node - just a 0/1 used flag which is now a byte to * keep the node size minimum. * Packing is set 1 * * 1 7/29/97 1:00a Rwyatt * Initial implementation * **********************************************************************************************/ #include "Common.hpp" #include "Lib/View/Raster.hpp" #include "TexturePackSurface.hpp" #include "Lib/sys/MemoryLog.hpp" #include "Lib/sys/DebugConsole.hpp" //********************************************************************************************* // #if (VER_DEBUG == TRUE) static bool AssertEmptyTree(STextureQuadTree* ptqt) { // is the root texture used?? if (ptqt->tqnRoot.u1Texture) return false; // are any of the children nodes used?? if (ptqt->tqnRoot.ptqnSubNode[0]) return false; if (ptqt->tqnRoot.ptqnSubNode[1]) return false; if (ptqt->tqnRoot.ptqnSubNode[2]) return false; if (ptqt->tqnRoot.ptqnSubNode[3]) return false; // tree is free, so return true return true; } #else _inline static bool AssertEmptyTree(STextureQuadTree* ptqt) { return true; } #endif //********************************************************************************************* // CPackedRaster::CPackedRaster ( rptr pras_parent, uint32 u4_smallest ) //************************************* { // The raster passed in must be valid and must have a valid width and height (256x256). // NOTE: The parent raster does require a valid surface pointer. The surface is never // accessed because it may be in virtual memory. All packed rasters have a surface // pointer relative to the base address of the parent. Assert( pras_parent ); Assert( u4_smallest>0); Assert( pras_parent->iWidth >= u4_smallest); Assert( pras_parent->iHeight >= u4_smallest); Assert( pras_parent->iWidth <= 256); Assert( pras_parent->iHeight <= 256); Assert( pras_parent->iHeight == pras_parent->iWidth); u4SmallestAllocation = u4_smallest; // all allocations are rounded upto this size prasPackedParent = pras_parent; InitQuadTree(pras_parent->iWidth, u4_smallest); // we do not know what the mip level or texture type of this surface is. eptMipLevel = eptDONT_CARE; // // A little memory logging.... // #ifdef LOG_MEM switch (pras_parent->iPixelBits) { case 8: MEMLOG_ADD_COUNTER(emlTexturePages8,1); break; case 16: MEMLOG_ADD_COUNTER(emlTexturePages16,1); break; case 32: MEMLOG_ADD_COUNTER(emlTexturePages32,1); break; } #endif } //********************************************************************************************* // CPackedRaster::~CPackedRaster ( ) //************************************* { if (!AssertEmptyTree(&tqtPackQuadTree)) { dprintf("Textures remain in surface\n"); } // // A little memory logging.... // #ifdef LOG_MEM switch (prasPackedParent->iPixelBits) { case 8: MEMLOG_SUB_COUNTER(emlTexturePages8,1); break; case 16: MEMLOG_SUB_COUNTER(emlTexturePages16,1); break; case 32: MEMLOG_SUB_COUNTER(emlTexturePages32,1); break; } #endif // // Delete the free lists, note the first 3 lists are statically allocated so do not // try to delete them. // for (int i = tqtPackQuadTree.u4ParentSize-3; i>=0; i--) { delete tqtPackQuadTree.anltFree[ i ].aptqn; } } //********************************************************************************************* // Init a quad tree withe an empty root node. This must be called before the tree is used. // void CPackedRaster::InitQuadTree ( uint32 u4_parent, uint32 u4_smallest ) //************************************* { int i_parent_size = iGetSize(u4_parent); int i_small_size = iGetSize(u4_smallest); // setup the root node tqtPackQuadTree.u4ParentSize = (uint32)i_parent_size; tqtPackQuadTree.tqnRoot.u1Size = (uint8)u4_parent-1; tqtPackQuadTree.tqnRoot.u1XOrg = 0; tqtPackQuadTree.tqnRoot.u1YOrg = 0; tqtPackQuadTree.tqnRoot.u1Texture = 0; tqtPackQuadTree.tqnRoot.ptqnLink = NULL; // no children, the children of a node are not allocated until the node needs to be split // and at that point all 4 children are created. tqtPackQuadTree.tqnRoot.ptqnSubNode[0] = NULL; tqtPackQuadTree.tqnRoot.ptqnSubNode[1] = NULL; tqtPackQuadTree.tqnRoot.ptqnSubNode[2] = NULL; tqtPackQuadTree.tqnRoot.ptqnSubNode[3] = NULL; // Empty every free list and null the pointers, all lists are now invalid and no size // can be allocated for (int k = 0 ; k<=8 ; k++) { tqtPackQuadTree.anltFree[ k ].u1Count = 0; tqtPackQuadTree.u4LostNodeCount[ k ] = 0; tqtPackQuadTree.anltFree[ k ].aptqn = NULL; } // allocate and initialize all free lists that are within the valid size range for (int i = i_parent_size, j=0 ; i>=i_small_size ; i--,j++) { uint8 u1_max = 0; tqtPackQuadTree.anltFree[ i ].u1Count = 0; tqtPackQuadTree.u4LostNodeCount[ i ] = 0; switch (j) { case 0: u1_max = u4FREE_LIST_ENTRIES_PARENT; tqtPackQuadTree.anltFree[ i ].aptqn = atqnSizeParent; break; case 1: u1_max = u4FREE_LIST_ENTRIES_DIVIDE1; tqtPackQuadTree.anltFree[ i ].aptqn = atqnSizeDivide1; break; case 2: u1_max = u4FREE_LIST_ENTRIES_DIVIDE2; tqtPackQuadTree.anltFree[ i ].aptqn = atqnSizeDivide2; break; case 3: u1_max = u4FREE_LIST_ENTRIES_DIVIDE3; tqtPackQuadTree.anltFree[ i ].aptqn = (STextureQuadNode**) new char[sizeof(STextureQuadNode*)*u1_max]; break; case 4: u1_max = u4FREE_LIST_ENTRIES_DIVIDE4; tqtPackQuadTree.anltFree[ i ].aptqn = (STextureQuadNode**) new char[sizeof(STextureQuadNode*)*u1_max]; break; case 5: u1_max = u4FREE_LIST_ENTRIES_DIVIDE5; tqtPackQuadTree.anltFree[ i ].aptqn = (STextureQuadNode**) new char[sizeof(STextureQuadNode*)*u1_max]; break; case 6: u1_max = u4FREE_LIST_ENTRIES_DIVIDE6; tqtPackQuadTree.anltFree[ i ].aptqn = (STextureQuadNode**) new char[sizeof(STextureQuadNode*)*u1_max]; break; case 7: u1_max = u4FREE_LIST_ENTRIES_DIVIDE7; tqtPackQuadTree.anltFree[ i ].aptqn = (STextureQuadNode**) new char[sizeof(STextureQuadNode*)*u1_max]; break; case 8: u1_max = u4FREE_LIST_ENTRIES_DIVIDE8; tqtPackQuadTree.anltFree[ i ].aptqn = (STextureQuadNode**) new char[sizeof(STextureQuadNode*)*u1_max]; break; } tqtPackQuadTree.anltFree[ i ].u1MaxCount = u1_max; // zero the new free list for (uint32 k=0; k CPackedRaster::prasAllocateRaster ( uint32 u4_xsize, uint32 u4_ysize, CPixelFormat* pxf ) //************************************* { uint32 u4_powx = NextPowerOfTwo(u4_xsize); uint32 u4_powy = NextPowerOfTwo(u4_ysize); // // So lets try to add the map to this surface. // (find a block of the correct size in the quad tree // Sizes are rounded up to the next power of two) // STextureQuadNode* ptqn = ptqnAddRaster(u4_powx,u4_powy); // failed to allocate, return a NULL rptr if (ptqn == NULL) { return rptr0; } // log the rounding waste MEMLOG_ADD_COUNTER(emlRoundingWaste,((u4_powx*u4_powy)- (u4_xsize*u4_ysize)) * prasGetParentRaster()->iPixelBytes() ); // make a rectangle from the info returned in the quad tree and use this rectange // to allocate a section of the parent. // NOTE: The texture quad node returned above is the square in the top left hand // corner of the rectangle that was requested. For example, if a 256x128 rectangle // is requested the reselting node is 128x128. This is not a bug, the packer knows // that the neighbouring 128x128 is also used. SRect rc(ptqn->u1XOrg, ptqn->u1YOrg, u4_xsize, u4_ysize); return rptr_cast(CRasterMem, rptr_new CRasterMem( prasGetParentRaster(), rc, rptr_this(this), pxf )); } //********************************************************************************************* // bool CPackedRaster::bFindNextHorizontal ( STextureQuadNode* aptqn[], uint32 au4[], uint32 u4_count, uint32* pu4_adjcount, uint32* pu4_amin, uint32* pu4_amax, uint32 i_pixels ) //************************************* { if (*pu4_adjcount == 0) { // // Find the first good node and insert it into the index array // // while there is entries in the list, find the first good node thatwe can use. while (u4_count) { u4_count--; // if this node set?? if (aptqn[u4_count]) { au4[0] = u4_count; // index of the first good one *pu4_adjcount = 1; // number in list *pu4_amin = u4_count; // index in index array of the minimum point *pu4_amax = u4_count; // index in index array of the maximum point return true; } } return false; } else { // starting block, this will get decremented // this will get decremented so we actaully start 1 before it. u4_count = au4[0]; // while there are entries in the list, find the first good node that we can use. while (u4_count) { u4_count--; // if this node set?? if (aptqn[u4_count]) { if ( (aptqn[u4_count]->u1YOrg) == (aptqn[ au4[0] ]->u1YOrg) ) { if ( (uint32)aptqn[u4_count]->u1XOrg == ((uint32)aptqn[ *pu4_amax ]->u1XOrg + i_pixels) ) { // this is our neighbour, 1 to the right au4[ *pu4_adjcount ] = u4_count; (*pu4_amax) = u4_count; (*pu4_adjcount)++; return true; } if ( (uint32)aptqn[u4_count]->u1XOrg == ((uint32)aptqn[ *pu4_amin ]->u1XOrg - i_pixels) ) { // this is our neighbour, 1 to the right au4[ *pu4_adjcount ] = u4_count; (*pu4_amin) = u4_count; (*pu4_adjcount)++; return true; } } } } } return false; } //********************************************************************************************* // bool CPackedRaster::bFindNextVertical ( STextureQuadNode* aptqn[], uint32 au4[], uint32 u4_count, uint32* pu4_adjcount, uint32* pu4_amin, uint32* pu4_amax, uint32 i_pixels ) //************************************* { if (*pu4_adjcount == 0) { // // Find the first good node and insert it into the index array // // while there is entries in the list, find the first good node thatwe can use. while (u4_count) { u4_count--; // if this node set?? if (aptqn[u4_count]) { au4[0] = u4_count; // index of the first good one *pu4_adjcount = 1; // number in list *pu4_amin = u4_count; // index in index array of the minimum point *pu4_amax = u4_count; // index in index array of the maximum point return true; } } return false; } else { // starting block, this will get decremented // this will get decremented so we actaully start 1 before it. u4_count = au4[0]; // while there are entries in the list, find the first good node that we can use. while (u4_count) { u4_count--; // if this node set?? if (aptqn[u4_count]) { if ( (aptqn[u4_count]->u1XOrg) == (aptqn[ au4[0] ]->u1XOrg) ) { if ( (uint32)aptqn[u4_count]->u1YOrg == ((uint32)aptqn[ *pu4_amax ]->u1YOrg + i_pixels) ) { // this is our neighbour, 1 below au4[ *pu4_adjcount ] = u4_count; (*pu4_amax) = u4_count; (*pu4_adjcount)++; return true; } if ( (uint32)aptqn[u4_count]->u1YOrg == ((uint32)aptqn[ *pu4_amin ]->u1YOrg - i_pixels) ) { // this is our neighbour, 1 above au4[ *pu4_adjcount ] = u4_count; (*pu4_amin) = u4_count; (*pu4_adjcount)++; return true; } } } } } return false; } //********************************************************************************************* // Add the specified texture to this texture page // NOTE: The node that this returns is smallest square that fits into the top left hand corner // of the area requested. This is not a bug is is down to the way rectangles are broken into // squares with sides equal to the minor side of the rectangle. // STextureQuadNode* CPackedRaster::ptqnAddRaster ( int i_width, int i_height ) //************************************* { int i_size; int i_big; int i_small; int i_blocks; int i_pixels; bool b_vertical; Assert(bPowerOfTwo(i_width)); Assert(bPowerOfTwo(i_height)); // dprintf("WIDTH = %d\nHEIGHT = %d\n\n", i_width, i_height); if (i_width<(int)u4SmallestAllocation) { i_width = (int)u4SmallestAllocation; } if (i_height<(int)u4SmallestAllocation) { i_height = (int)u4SmallestAllocation; } // which free list are we to use first (the list of the biggest size) i_size = iGetSize(i_width>i_height?i_width:i_height); // if the width and height are equal then allocate directly... if (i_width == i_height) { STextureQuadNode* ptqn = ptqnFindQuadNode( iGetSize(i_width) ); if (ptqn == NULL) return NULL; // fill in the info within the quad node ptqn->u1Texture = 1; ptqn->ptqnLink = NULL; return ptqn; } // get the dimensions and number of sub blocks that we need to allocate.... if (i_width1) { uint32 u4_count = tqtPackQuadTree.anltFree[i_size].u1Count; // number of blocks if (u4_count >= (uint32)i_blocks) { uint32 u4_adjcount = 0; uint32 u4_amin = 0; uint32 u4_amax = 0; bool b_res; // make sure we do not overrun the local free lists obove.. Assert(u4_count<=u4LOCAL_FREE_LIST_SIZE); // make a local copy of the free list for (uint32 u4 = 0; u4< u4_count; u4++) { aptqn_adjcopy[u4] = tqtPackQuadTree.anltFree[i_size].aptqn[u4]; } while (1) { if (b_vertical) { b_res = bFindNextVertical(aptqn_adjcopy,u4_list,u4_count,&u4_adjcount,&u4_amin,&u4_amax,i_pixels); } else { b_res = bFindNextHorizontal(aptqn_adjcopy,u4_list,u4_count,&u4_adjcount,&u4_amin,&u4_amax,i_pixels); } if (!b_res) { // we have not returned any blocks this time so the ones currently // in the list are not valid. If we never inserted a start block // then we are at the end and have not found what we are looking for. // if (u4_adjcount == 0) break; // go through the list and remove any that cannot be used for (uint32 i = 0; i= i_blocks) { int i; if (i_size == i_small) { // // we have a suitable set of blocks that are the same size in one // dimension as the source block, therefore no subdivision is required. // delete the N nodes from the free list and set the texture pointer // // THIS IS THE ONLY PLACE WHERE THE LINK IS SET TO NON-NULL // // copy the first element to the last just so we can point to it! u4_list[i_blocks] = u4_list[0]; for (i=0; iu1Texture = 1; aptqn_adjcopy[ u4_list[i] ]->ptqnLink = aptqn_adjcopy[ u4_list[i+1] ]; } } else { // we have a set of blocks that make up an area of the correct dimensions // but it needs to be subdivided, so lets do that.... for (i=0; i>= 1; // half the number of blocks } // if we get to here things are still hopeful.. // we are down to one block so allocate it with the normal allocator and divide it down // we need to allocate a block at the master (bigger) size STextureQuadNode* ptqn = ptqnFindQuadNode(i_big ); if (ptqn == NULL) return NULL; SplitQuadNodeForRectangle(ptqn, b_vertical, i_small, i_size-1); return ptqnAddRaster(i_width, i_height); } //********************************************************************************************* // The node passed in is not in the free list for that node size // // This will keep dividing until it is the size of the smaller of the two dimensions, at this // point our rectangle can be added // void CPackedRaster::SplitQuadNodeForRectangle ( STextureQuadNode* ptqn, bool b_vertical, // set to true to split vertically (widthptqnSubNode[3], i_size ,false); KillNode(ptqn->ptqnSubNode[1], i_size ,false); SplitQuadNodeForRectangle(ptqn->ptqnSubNode[3], b_vertical, i_small, i_size-1); SplitQuadNodeForRectangle(ptqn->ptqnSubNode[1], b_vertical, i_small, i_size-1); } else { KillNode( ptqn->ptqnSubNode[3], i_size ,false); KillNode(ptqn->ptqnSubNode[2], i_size ,false); SplitQuadNodeForRectangle(ptqn->ptqnSubNode[3], b_vertical, i_small, i_size-1); SplitQuadNodeForRectangle(ptqn->ptqnSubNode[2], b_vertical, i_small, i_size-1); } } } //********************************************************************************************* // Divides the specified node and adds the children to the free list // This function has to handle running out of space in the free lists // void CPackedRaster::DivideNode ( STextureQuadNode* ptqn, int i_size ) //************************************* { // set the parent sub pointers ptqn->ptqnSubNode[0] = new STextureQuadNode; ptqn->ptqnSubNode[1] = new STextureQuadNode; ptqn->ptqnSubNode[2] = new STextureQuadNode; ptqn->ptqnSubNode[3] = new STextureQuadNode; MEMLOG_ADD_ADRSIZE(emlTextureManQuad,ptqn->ptqnSubNode[0]); MEMLOG_ADD_ADRSIZE(emlTextureManQuad,ptqn->ptqnSubNode[1]); MEMLOG_ADD_ADRSIZE(emlTextureManQuad,ptqn->ptqnSubNode[2]); MEMLOG_ADD_ADRSIZE(emlTextureManQuad,ptqn->ptqnSubNode[3]); // set the free list pointers for (int i = 0; i<4 ; i++) { if (tqtPackQuadTree.anltFree[i_size].u1Count < tqtPackQuadTree.anltFree[i_size].u1MaxCount ) { tqtPackQuadTree.anltFree[i_size].aptqn[ tqtPackQuadTree.anltFree[i_size].u1Count ] = ptqn->ptqnSubNode[i]; tqtPackQuadTree.anltFree[i_size].u1Count++; } else { break; } } // zero all the texture pointers ptqn->ptqnSubNode[0]->u1Texture = 0; ptqn->ptqnSubNode[1]->u1Texture = 0; ptqn->ptqnSubNode[2]->u1Texture = 0; ptqn->ptqnSubNode[3]->u1Texture = 0; // zero all the texture links ptqn->ptqnSubNode[0]->ptqnLink = 0; ptqn->ptqnSubNode[1]->ptqnLink = 0; ptqn->ptqnSubNode[2]->ptqnLink = 0; ptqn->ptqnSubNode[3]->ptqnLink = 0; // set the width of all the new nodes ptqn->ptqnSubNode[0]->u1Size = ((ptqn->u1Size+1)>>1)-1; ptqn->ptqnSubNode[1]->u1Size = ((ptqn->u1Size+1)>>1)-1; ptqn->ptqnSubNode[2]->u1Size = ((ptqn->u1Size+1)>>1)-1; ptqn->ptqnSubNode[3]->u1Size = ((ptqn->u1Size+1)>>1)-1; // node 0 is top left ptqn->ptqnSubNode[3]->u1XOrg = ptqn->u1XOrg; ptqn->ptqnSubNode[3]->u1YOrg = ptqn->u1YOrg; // node 1 is top right ptqn->ptqnSubNode[2]->u1XOrg = ptqn->u1XOrg + ((ptqn->u1Size+1)>>1); ptqn->ptqnSubNode[2]->u1YOrg = ptqn->u1YOrg; // node 2 is bottom left ptqn->ptqnSubNode[1]->u1XOrg = ptqn->u1XOrg; ptqn->ptqnSubNode[1]->u1YOrg = ptqn->u1YOrg + ((ptqn->u1Size+1)>>1); // node 3 is bottom right ptqn->ptqnSubNode[0]->u1XOrg = ptqn->u1XOrg + ((ptqn->u1Size+1)>>1); ptqn->ptqnSubNode[0]->u1YOrg = ptqn->u1YOrg + ((ptqn->u1Size+1)>>1); } //********************************************************************************************* // Add the specified texture to the specified tree // STextureQuadNode* CPackedRaster::ptqnFindQuadNode ( int i_size ) //************************************* { STextureQuadNode* ptqn = NULL; // Make sure we have a free list for this size, if there is no free list then this size // should have not been used as it is less than the smallest allocation size. Assert(tqtPackQuadTree.anltFree[i_size].aptqn); // first move is to allocate from the cahce of free nodes... if (tqtPackQuadTree.anltFree[i_size].u1Count>0) { // we have a slot of this size that we can use. tqtPackQuadTree.anltFree[i_size].u1Count--; // return the address that we have found, remember to null the element ptqn = tqtPackQuadTree.anltFree[i_size].aptqn[ tqtPackQuadTree.anltFree[i_size].u1Count ]; tqtPackQuadTree.anltFree[i_size].aptqn[ tqtPackQuadTree.anltFree[i_size].u1Count ] = NULL; } // second move is to see if there are any lost nodes of the requested size... else if (tqtPackQuadTree.u4LostNodeCount[i_size]>0) { ptqn = ptqnSearchFreeNode(&tqtPackQuadTree.tqnRoot, tqtPackQuadTree.u4ParentSize,i_size); if (ptqn) { KillNode(ptqn,i_size,false); } } // the final move is to search for a bigger node and sub divide it. else { // are we looking for the biggest size?? if (i_size<(int)tqtPackQuadTree.u4ParentSize) { // it is time to up one a size and sub divide // zero is the texture handle so that we mark the parent as unused ptqn = ptqnFindQuadNode(i_size+1); // ptqn is the pointer to our parent node, or NULL if our request cannot be made if (ptqn != NULL) { DivideNode(ptqn, i_size); // allocate one of the quads allocated above ptqn = ptqnFindQuadNode(i_size); } } } return ptqn; } //********************************************************************************************* // this will walk the tree looking for a free node, if it finds other free nodes that are not // in the list it will add them - even for different sizes. // STextureQuadNode* CPackedRaster::ptqnSearchFreeNode ( STextureQuadNode* ptqn, int i_size, int i_searchsize ) //************************************* { STextureQuadNode* ptqn_local = NULL; STextureQuadNode* ptqn_temp = NULL; if ((ptqn->ptqnSubNode[0] == NULL) && (ptqn->ptqnSubNode[1] == NULL) && (ptqn->ptqnSubNode[2] == NULL) && (ptqn->ptqnSubNode[3] == NULL) && (ptqn->u1Texture == 0)) { bool b_res = false; // this node is free, check if it is in the free list for (uint32 u4=0; u4<(uint32)tqtPackQuadTree.anltFree[i_size].u1Count; u4++) { if (tqtPackQuadTree.anltFree[i_size].aptqn[u4] == ptqn) { Assert(b_res); // if we are in the list twice we are screwed... b_res = true; } } // did we find it?? if (!b_res) { // the node is not in the free list. Assert(tqtPackQuadTree.u4LostNodeCount[i_size]>0); // now check if there is room in the free list... if (tqtPackQuadTree.anltFree[i_size].u1Counti_searchsize) { ptqn_temp = ptqnSearchFreeNode(ptqn->ptqnSubNode[0],i_size-1,i_searchsize); if (ptqn_local == NULL) { ptqn_local = ptqn_temp; } ptqn_temp = ptqnSearchFreeNode(ptqn->ptqnSubNode[1],i_size-1,i_searchsize); if (ptqn_local == NULL) { ptqn_local = ptqn_temp; } ptqn_temp = ptqnSearchFreeNode(ptqn->ptqnSubNode[2],i_size-1,i_searchsize); if (ptqn_local == NULL) { ptqn_local = ptqn_temp; } ptqn_temp = ptqnSearchFreeNode(ptqn->ptqnSubNode[3],i_size-1,i_searchsize); if (ptqn_local == NULL) { ptqn_local = ptqn_temp; } } } return ptqn_local; } //********************************************************************************************* // Delete Texture from current page // All this requires is the address of the map within the page // void CPackedRaster::Delete ( void* p_tex ) //************************************* { STextureQuadNode* ptqn_last; Assert(p_tex); // get the byte offset from the start of the texture.. uint32 p_texture = ((uint8*)p_tex) - ((uint8*)(prasPackedParent->pSurface)); uint32 u4_ypos; uint32 u4_xpos; p_texture /= (prasPackedParent->iPixelBits / 8); u4_ypos = p_texture / prasPackedParent->iLinePixels; // pixel Y pos of texture in page u4_xpos = p_texture % prasPackedParent->iLinePixels; // pixel X pos Assert (u4_xpos<256); Assert (u4_ypos<256); ptqnDel = ptqn_last = NULL; ptqnStart = NULL; bRemoveQuadNodeAndCompact(&tqtPackQuadTree.tqnRoot,u4_xpos,u4_ypos,tqtPackQuadTree.u4ParentSize); while ((ptqnDel!=ptqnStart) && (ptqnDel!=NULL)) { bRemoveQuadNodeAndCompact(&tqtPackQuadTree.tqnRoot,u1DelXPos,u1DelYPos,tqtPackQuadTree.u4ParentSize); } } //********************************************************************************************* // This will return true if the specifed node is in the size list // bool CPackedRaster::bFindInNodeList ( STextureQuadNode* ptqn, int i_size ) //************************************* { // A node with no chldren and no texture is free. a node gets to this state when it cannot // be entered into a free list. When its siblings are deleted it can still be freed dur to // this check. if ((ptqn->ptqnSubNode[0] == NULL) && (ptqn->ptqnSubNode[1] == NULL) && (ptqn->ptqnSubNode[2] == NULL) && (ptqn->ptqnSubNode[3] == NULL) && (ptqn->u1Texture == 0)) return true; for (uint32 u4=0; u4<(uint32)tqtPackQuadTree.anltFree[i_size].u1Count; u4++) { if (tqtPackQuadTree.anltFree[i_size].aptqn[u4] == ptqn) return true; } return false; } //********************************************************************************************* // Kill the specified node and keep the free list consecutive. // void CPackedRaster::KillNode ( STextureQuadNode* ptqn, int i_size, bool b_delete ) //************************************* { uint32 u4_count = (uint32)tqtPackQuadTree.anltFree[i_size].u1Count; bool b_found = false; for (uint32 u4=0; u40 ); tqtPackQuadTree.u4LostNodeCount[i_size]--; if (b_delete) { MEMLOG_SUB_ADRSIZE(emlTextureManQuad,ptqn); delete ptqn; } } } //********************************************************************************************* // Do the actual delete and delete your parent all the way to the root if all your siblings // have also been removed. This is essential if you are going to prevent global framgmentation // bool CPackedRaster::bRemoveQuadNodeAndCompact ( STextureQuadNode* ptqn, uint32 u4_xp, uint32 u4_yp, int i_size ) { Assert(u4_xp<256); Assert(u4_yp<256); Assert(ptqn); if ( ((ptqn->u1XOrg<=u4_xp) && (((ptqn->u1XOrg)+ptqn->u1Size)>=(uint8)u4_xp) ) && //Is X within the node ((ptqn->u1YOrg<=u4_yp) && (((ptqn->u1YOrg)+ptqn->u1Size)>=(uint8)u4_yp)) ) //Is Y within the node { if (ptqn->u1Texture == 0) { // if there is no texture then we much check the children bool b_ret = false; for (int i=0; i<4; i++) { if (ptqn->ptqnSubNode[i]) { if (bRemoveQuadNodeAndCompact(ptqn->ptqnSubNode[i], u4_xp, u4_yp, i_size-1)) { b_ret = true; } } } // if we deleted a child, it could mean that we can delete ourselves, Check the free list at the // relevent size to see if all children are present. if (b_ret) { // TO PREVENT GLOBAL FRAGMENTATION // if all child nodes are free, delete them and return true so our parent will delete us if (bFindInNodeList(ptqn->ptqnSubNode[0],i_size-1) && bFindInNodeList(ptqn->ptqnSubNode[1],i_size-1) && bFindInNodeList(ptqn->ptqnSubNode[2],i_size-1) && bFindInNodeList(ptqn->ptqnSubNode[3],i_size-1)) { // all of the children are in the size list // Kill the node, this will free its memory and remove it from the free list of the associted size KillNode(ptqn->ptqnSubNode[0],i_size-1, true); KillNode(ptqn->ptqnSubNode[1],i_size-1, true); KillNode(ptqn->ptqnSubNode[2],i_size-1, true); KillNode(ptqn->ptqnSubNode[3],i_size-1, true); ptqn->ptqnSubNode[0] = NULL; ptqn->ptqnSubNode[1] = NULL; ptqn->ptqnSubNode[2] = NULL; ptqn->ptqnSubNode[3] = NULL; // make this node free ptqn->u1Texture = 0; ptqn->ptqnLink = NULL; // just to be safe! // add us to the free list if there is room in the current free list if (tqtPackQuadTree.anltFree[i_size].u1Count < tqtPackQuadTree.anltFree[i_size].u1MaxCount) { tqtPackQuadTree.anltFree[i_size].aptqn[ tqtPackQuadTree.anltFree[i_size].u1Count ] = ptqn; tqtPackQuadTree.anltFree[i_size].u1Count++; } else { // we do not have room to add the node, so keep a counter of it as a // lost node. tqtPackQuadTree.u4LostNodeCount[i_size]++; } return true; } else { return false; } } return false; } else { // yep, there is a texture pointer and there should not be any children // // THIS IS THE ONLY PLACE THAT A TEXTURED NODE CAN GET REMOVED. SO IT IS // OK TO REMEMBER THE LINK POINTER OF THE DELETED ITEM SO WE DO NOT HAVE // TO PASS IT AROUND THE RECURSION. // Assert(ptqn->ptqnSubNode[0] == NULL); Assert(ptqn->ptqnSubNode[1] == NULL); Assert(ptqn->ptqnSubNode[2] == NULL); Assert(ptqn->ptqnSubNode[3] == NULL); // make this node free ptqn->u1Texture = 0; ptqnDel = ptqn->ptqnLink; if (ptqnStart == NULL) { ptqnStart = ptqn; } // if there is a link no only do we have to remember the link address but we // must remember the position. we cannot get the position from the link because // the last node may point to the first node if it is a rectangle and the block // for the first node may have been deleted and paged out when the last node // references it. if (deletedNodes.find(ptqnDel) != deletedNodes.end()) { //Pointer is known to have been deleted, do not use dout << "applied dead texture node link correction" << std::endl; ptqnDel = nullptr; } else if (ptqnDel) { u1DelXPos = ptqnDel->u1XOrg; u1DelYPos = ptqnDel->u1YOrg; } ptqn->ptqnLink = NULL; // add us to the free list if there is room if (tqtPackQuadTree.anltFree[i_size].u1Count < tqtPackQuadTree.anltFree[i_size].u1MaxCount) { tqtPackQuadTree.anltFree[i_size].aptqn[ tqtPackQuadTree.anltFree[i_size].u1Count ] = ptqn; tqtPackQuadTree.anltFree[i_size].u1Count++; } else { // we do not have room to add the node, so keep a counter of it as a // lost node. tqtPackQuadTree.u4LostNodeCount[i_size]++; } return true; } } return false; } //********************************************************************************************* // Try to allocate a texture of the given size at the position requested. // Return a texture quad node like the other allocators if successful otherwise return NULL. // STextureQuadNode* CPackedRaster::ptqnAddTextureAtPosition ( int i_width, int i_height, int i_xp, int i_yp ) //************************************* { Assert(bPowerOfTwo(i_width)); Assert(bPowerOfTwo(i_height)); if (i_width<(int)u4SmallestAllocation) { i_width = (int)u4SmallestAllocation; } if (i_height<(int)u4SmallestAllocation) { i_height = (int)u4SmallestAllocation; } // we must be aligned to a multiple of the size Assert( (i_xp%i_width) == 0); Assert( (i_yp%i_height) == 0); STextureQuadNode* ptqn = &tqtPackQuadTree.tqnRoot; int i_node_size = (int)(tqtPackQuadTree.u4ParentSize); // if it is sqyare then it is trivial to add. if (i_width == i_height) { // which free list are we to use first (the list of the biggest size) int i_size = iGetSize(i_width>i_height?i_width:i_height); return ptqnInsertNodeAtPosition(ptqn, i_node_size, i_size, i_xp, i_yp); } // // We are allocating a rectangular block, split it up into many squares whose size // are that of the minor edge of the rectangle. // int i_blocks; int i_small; int i_big; int i_xstep; int i_ystep; if (i_widthu1XOrg,ptqn_sub[i]->u1YOrg,tqtPackQuadTree.u4ParentSize); } return NULL; } // co-ords of the next square i_xp+=i_xstep; i_yp+=i_ystep; i_blocks--; i_count++; } // // Link the seperate individual sqaures into a list // int i; for (i = 0; iptqnLink = ptqn_sub[i+1]; } ptqn_sub[i]->ptqnLink = ptqn_sub[0]; return ptqn; } //********************************************************************************************* // Divides tree and allocates a sqaure region. // Function will return NULL is the request sqaure cannot be allocated. STextureQuadNode* CPackedRaster::ptqnInsertNodeAtPosition ( STextureQuadNode* ptqn, int i_current_size, int i_target_size, int i_xp, int i_yp ) //************************************* { while (i_current_size!=i_target_size) { // if this node is allocated then we must fail, as we cannot allocate it and we cannot // sub divide it. if (ptqn->u1Texture) { return NULL; } i_current_size--; // If this node has no children then remove it from the free list and divide it, // which will add 4 elements to the next smallest free list. If this node has // already been divided, ie, has children then do nothing. if ((ptqn->ptqnSubNode[0]==NULL) && (ptqn->ptqnSubNode[1]==NULL) && (ptqn->ptqnSubNode[2]==NULL) && (ptqn->ptqnSubNode[3]==NULL) ) { RemoveFromFreeList(ptqn,i_current_size+1); DivideNode(ptqn, i_current_size); } // // Logically figure out which of the 4 nodes we need to work on next based on the // requested co-ordinates passed in. // int i_node = 0; if (i_xp < ptqn->ptqnSubNode[0]->u1XOrg) { i_node |= 1; } if (i_yp < ptqn->ptqnSubNode[0]->u1YOrg) { i_node |= 2; } ptqn = ptqn->ptqnSubNode[i_node]; } // We have divided down to the requested size if (ptqn->u1Texture || ptqn->ptqnSubNode[0] || ptqn->ptqnSubNode[1] || ptqn->ptqnSubNode[2] || ptqn->ptqnSubNode[3]) { // The specified co-ordinate in the pack surface is already being used by a texture // or is a parent of smaller textures. Either way it cannot be used. return NULL; } // we have found the node we are looking for, so remove it from the free list of the // packer and mark it as used. RemoveFromFreeList(ptqn,i_current_size); ptqn->u1Texture = (uint8)true;; ptqn->ptqnLink = NULL; return ptqn; } //********************************************************************************************* // CRenderTexturePackSurface::CRenderTexturePackSurface ( uint32 u4_bits, ETexturePackTypes ept ) { //***************************************************************************************** // First create two interleaved rasters of the required bit depth //***************************************************************************************** // Create a virtual memory raster that is 256x256 pixels with a stride of 512 pixels. // Packed surfaces have no pixel format.. // NOTE: If the texture pack type is 'smallest mip' then the memory comes fom the sub // block allocator. rptr pras_a = rptr_cast(CRaster, rptr_new CRasterMem( 256, 256, u4_bits, 512*(u4_bits/8), NULL, (ept == eptSMALLEST)?emtTexManSubVirtual:emtTexManVirtual) ); // the second surface is created as a sub rectangle of the first, initially using the // same address space but the pAddress element is shifted on by 256 texels. SRect rc(0,0,256,256); rptr pras_b = rptr_cast(CRaster, rptr_new CRasterMem(pras_a, rc) ); // surface B will use the memory that is unused within the interleave on surface A. // This is essential to the tiling primitives..... pras_b->pSurface = ((char*)pras_b->pSurface) + ((pras_b->iWidth) * (pras_b->iPixelBits/8)); // Create the pack classes for the two surfaces ppckPackA = rptr_cast(CPackedRaster, rptr_new CPackedRaster(pras_a) ); ppckPackB = rptr_cast(CPackedRaster, rptr_new CPackedRaster(pras_b) ); SetType(ept); } //********************************************************************************************* // CRenderTexturePackSurface::~CRenderTexturePackSurface() { // // Remove our reference to the packed surfaces // ppckPackA = rptr0; ppckPackB = rptr0; } //********************************************************************************************* // Try to allocate a raster of the specified size in one of the two rasters that this // class contains. rptr CRenderTexturePackSurface::prasAllocateRaster ( uint32 u4_xsize, uint32 u4_ysize, CPixelFormat* pxf ) //************************************* { rptr pras = ppckPackA->prasAllocateRaster(u4_xsize,u4_ysize,pxf); if (!pras) { // try surface B pras = ppckPackB->prasAllocateRaster(u4_xsize,u4_ysize,pxf); if (!pras) return rptr0; } return pras; } //********************************************************************************************* // Try to allocate a raster of the same size as the raster passed in. The raster passed in is // just used as a reference for the parameters. No data is copied into the new raster and the // raster passed in is not midified in anyway. rptr CRenderTexturePackSurface::prasAllocateRaster ( rptr pras_src ) //************************************* { return prasAllocateRaster(pras_src->iWidth, pras_src->iHeight, &pras_src->pxf); }