Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members | Search for 

Octree Class Reference

#include <bfxpixop.h>

Inheritance diagram for Octree:

CCObject SimpleCCObject List of all members.

Public Member Functions

 Octree ()
 Default constructor.
 ~Octree ()
 Default destructor for pixel op.
BOOL Init (INT32 NumColours)
 Resets all parameters associated with the cache.
BOOL Insert (INT32 r, INT32 g, INT32 b)
 Resets all parameters associated with the cache.
BOOL Index (RGBQUAD *Palette, OctreeElement *pEl=NULL)
 Resets all parameters associated with the cache.
INT32 GetIndex (INT32 r, INT32 g, INT32 b)
 Resets all parameters associated with the cache.

Private Member Functions

 CC_DECLARE_DYNCREATE (Octree)
OctreeElement * GetElement (INT32 r, INT32 g, INT32 b)
 Resets all parameters associated with the cache.
void CheckIntegrity ()
 Unlinks elt from lists.
void Unlink (OctreeElement *pEl)
 Unlinks elt from lists.
void Link (OctreeElement *pEl)
 Links elt into lists.

Private Attributes

INT32 MaxLeaves
INT32 CurrentLeaves
OctreeElement * pTopElement
INT32 CurrentIndex
OctreeElement * ListHead [9][9]

Detailed Description

Definition at line 557 of file bfxpixop.h.

Constructor & Destructor Documentation

Octree::Octree (   ) 
 

Default constructor.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
None [INPUTS]
Constructs object [OUTPUTS]
Returns:
Nothing

Errors: None yet

See also:
-

Definition at line 1150 of file bfxpixop.cpp.

01151 {
01152     MaxLeaves=255;
01153     CurrentLeaves=0;
01154     CurrentIndex=0;
01155     pTopElement=NULL;
01156     for (INT32 d=0; d<=9; d++) for (INT32 c=0; c<=8; c++) ListHead[d][c]=NULL;
01157 }

Octree::~Octree (   ) 
 

Default destructor for pixel op.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
None [INPUTS]
Constructs object [OUTPUTS]
Returns:
Nothing

Errors: Error3 if DeInit hasn't been called.

See also:
-

Definition at line 1174 of file bfxpixop.cpp.

01175 {
01176     if (pTopElement)
01177     {
01178         delete pTopElement; // which deletes its children.
01179         pTopElement=NULL;
01180     }
01181 }

Member Function Documentation

Octree::CC_DECLARE_DYNCREATE (  Octree   )  [private]
 

void Octree::CheckIntegrity (   )  [private]
 

Unlinks elt from lists.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
None [INPUTS]
None [OUTPUTS]
Returns:
None

Errors: 2 & 3 Scope:

See also:
-
Checks the octrees integrity

Definition at line 1380 of file bfxpixop.cpp.

01381 {
01382 #ifdef _DEBUG // avoid unused variable warnings
01383     for (INT32 d=0; d<=8; d++) for (INT32 c=0; c<=8; c++)
01384     {
01385         OctreeElement *pCheck = ListHead[d][c];
01386         OctreeElement *pChild = NULL;
01387         while (pCheck)
01388         {
01389             if (pCheck->pListPrev) ERROR3IF(pCheck->pListPrev->pListNext!=pCheck, "Bad prev ptr");
01390             if (pCheck->pListNext) ERROR3IF(pCheck->pListNext->pListPrev!=pCheck, "Bad next ptr");
01391             ERROR3IF((d!=0) && !pCheck->pParent, "Has no parent on non zero depth");
01392             ERROR3IF((d==0) && (pCheck!=pTopElement), "Bad top element");
01393             ERROR3IF(pCheck->Depth!=d,"Bad depth");
01394             ERROR3IF(pCheck->NumChildren!=c, "Bad Num Children");
01395             INT32 count=0;
01396             INT32 halfwidth=(1<<(8 - pCheck->Depth))>>1;
01397             for (INT32 cc=0; cc<8; cc++) if ((pChild=pCheck->pChildren[cc]/*assign*/)!=NULL)
01398             {
01399                 count++;
01400                 ERROR3IF(pChild->pParent != pCheck, "Bad parent link");
01401                 ERROR3IF(pChild->Depth != d+1, "Bad child depth");
01402                 INT32 R=pCheck->R + ((cc&1)?halfwidth:0);
01403                 INT32 G=pCheck->G + ((cc&2)?halfwidth:0);               
01404                 INT32 B=pCheck->B + ((cc&4)?halfwidth:0);
01405                 ERROR3IF(pChild->R != R, "Bad child R");
01406                 ERROR3IF(pChild->G != G, "Bad child G");
01407                 ERROR3IF(pChild->B != B, "Bad child B");
01408                 OctreeElement *pLChild = pChild;
01409                 while (pLChild->pListPrev) pLChild=pLChild->pListPrev;
01410                 ERROR3IF(pLChild!=ListHead[d+1][pLChild->NumChildren],"Child not in a list");
01411             }
01412             ERROR3IF(c!=count, "Bad child count");
01413             pCheck=pCheck->pListNext;
01414         }
01415     }
01416 #endif
01417     return;
01418 }

OctreeElement * Octree::GetElement (  INT32  r,
INT32  g,
INT32  b
)  [private]
 

Resets all parameters associated with the cache.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
r,g,b values to octree search for [INPUTS]
None [OUTPUTS]
Returns:
pointer to relevant octree element

Errors: None yet Scope: Public

See also:
-

Definition at line 1238 of file bfxpixop.cpp.

01239 {
01240     ERROR2IF(!pTopElement, NULL, "Octree not initialised");
01241     OctreeElement * pEl = pTopElement;
01242     
01243     // descend the tree till we reach the minimal cube containing the colour
01244     while(TRUE)
01245     {
01246         INT32 halfwidth=(1<<(8 - pEl->Depth))>>1;
01247         INT32 R=pEl->R+halfwidth;
01248         INT32 G=pEl->G+halfwidth;
01249         INT32 B=pEl->B+halfwidth;
01250         INT32 child=((r>=R)?1:0)+((g>=G)?2:0)+((b>=B)?4:0);
01251         if (!pEl->pChildren[child]) return pEl;
01252         pEl=pEl->pChildren[child];
01253     }
01254     
01255     ERROR3("How did it get here?");
01256     return NULL;
01257 }

INT32 Octree::GetIndex (  INT32  r,
INT32  g,
INT32  b
) 
 

Resets all parameters associated with the cache.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
r,g,b to get [INPUTS]
None [OUTPUTS]
Returns:
Index for this element

Errors: 2 & 3 Scope: Public

See also:
-

Definition at line 1551 of file bfxpixop.cpp.

01552 {
01553     OctreeElement * pEl=GetElement(r, g, b);
01554     if (!pEl)
01555     {
01556         ERROR3("Help! Can't find an enclosing octree element");
01557         return 0;
01558     }
01559     if (pEl->Index<0)
01560     {
01561         ERROR3("You've given us an RGB value you didn't give us on the first pass, quoth the octree");
01562         return 0;
01563     }
01564     return pEl->Index;
01565 }

BOOL Octree::Index (  RGBQUAD *  Palette,
OctreeElement *  pEl = NULL
) 
 

Resets all parameters associated with the cache.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
*pEl = element to index (and its children) or NULL for top element [INPUTS]
*Palette = palette filled in as per octree [OUTPUTS]
Returns:
TRUE on success, FALSE on error

Errors: 2 & 3 Scope: Public

See also:
-

Definition at line 1503 of file bfxpixop.cpp.

01504 {
01505     CheckIntegrity();
01506 
01507     if (!pEl)
01508     {
01509         pEl=pTopElement;
01510         CurrentIndex=0;
01511         if (!pEl) return TRUE; // for we have done
01512     }
01513 
01514     if (pEl->Pixels)
01515     {
01516         if (CurrentIndex>=MaxLeaves)
01517         {
01518             ERROR3("CurrentIndex>=MaxLeaves in Octree::Index");
01519             CurrentIndex=0;
01520         }
01521         pEl->Index=CurrentIndex;
01522         Palette[CurrentIndex].rgbRed=(BYTE)(pEl->R);
01523         Palette[CurrentIndex].rgbGreen=(BYTE)(pEl->G);
01524         Palette[CurrentIndex].rgbBlue=(BYTE)(pEl->B);
01525         CurrentIndex++;
01526     }   
01527     else
01528     {
01529         pEl->Index=-1;
01530     }
01531     for (INT32 c=0; c<8; c++) if (pEl->pChildren[c]) if (!Index(Palette, pEl->pChildren[c])) return FALSE;
01532     return TRUE;
01533 }

BOOL Octree::Init (  INT32  NumColours  ) 
 

Resets all parameters associated with the cache.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
None [INPUTS]
Resets all parameters associated with the cache [OUTPUTS]
Returns:
TRUE if succeeded, FALSE & error set if not

Errors: Error 2 if init hasn't been called or GDraw fails Error 3 if windows and some other Oil layer are stangely mixed... Scope: Public

See also:
-

Definition at line 1200 of file bfxpixop.cpp.

01201 {
01202     if (pTopElement)
01203     {
01204         delete pTopElement; // which deletes its children.
01205         pTopElement=NULL;
01206     }
01207     MaxLeaves=NumColours;
01208     CurrentLeaves=0;
01209     CurrentIndex=0;
01210 
01211     for (INT32 d=0; d<=9; d++) for (INT32 c=0; c<=8; c++) ListHead[d][c]=NULL;
01212 
01213     if ((pTopElement=new OctreeElement) == NULL) return FALSE; // error already set
01214     // and it's already in a fairly well set up state
01215 
01216     ListHead[0][0]=pTopElement;
01217 
01218     return TRUE;
01219 }

BOOL Octree::Insert (  INT32  r,
INT32  g,
INT32  b
) 
 

Resets all parameters associated with the cache.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
r,g,b values to insert [INPUTS]
None [OUTPUTS]
Returns:
TRUE on success, FALSE on error

Errors: 2 & 3 Scope: Public

See also:
-

Definition at line 1275 of file bfxpixop.cpp.

01276 {
01277     //CheckIntegrity();
01278     
01279     OctreeElement * pEl = GetElement(r, g, b);
01280     if (!pEl) return FALSE;
01281 
01282     // Insert any necessary intermediates
01283     while (pEl->Depth !=8)
01284     {
01285         OctreeElement * pNewEl = new OctreeElement;
01286         if (!pNewEl) return FALSE;
01287         pNewEl->Depth=pEl->Depth+1;
01288         INT32 halfwidth=(1<<(8 - pEl->Depth))>>1;
01289         INT32 R=pEl->R+halfwidth;
01290         INT32 G=pEl->G+halfwidth;
01291         INT32 B=pEl->B+halfwidth;
01292 
01293         pNewEl->R=(r>=R)?R:(pEl->R);
01294         pNewEl->G=(g>=G)?G:(pEl->G);
01295         pNewEl->B=(b>=B)?B:(pEl->B);
01296 
01297         INT32 child=((r>=R)?1:0)+((g>=G)?2:0)+((b>=B)?4:0);
01298         ERROR2IF(pEl->pChildren[child], FALSE, "Blurk! Octree element already has a child");
01299         pEl->pChildren[child]=pNewEl;
01300         pNewEl->pParent=pEl;
01301 
01302         Unlink(pEl);
01303         pEl->NumChildren++;
01304         Link(pEl);
01305 
01306         pEl=pNewEl;
01307         Link(pEl);
01308     
01309         //CheckIntegrity();
01310     }
01311 
01312     if (!pEl->Pixels) CurrentLeaves++;
01313     pEl->Pixels++;
01314 
01315     while (CurrentLeaves>MaxLeaves)
01316     {
01317         pEl=NULL;
01318 
01319         // Seatch deepest in the tree first ...
01320         for (INT32 d=8; (d>=0) && !pEl; d--)
01321         {
01322             // ... for an element with no children ...
01323             OctreeElement * plEl=ListHead[d][0];
01324             while (plEl && !pEl)
01325             {
01326                 // ... which has a parent ...
01327                 pEl=plEl->pParent;
01328                 // ... whose children have no children themselves
01329                 for (INT32 c=0; (c<8) && pEl; c++) if (pEl->pChildren[c] && pEl->pChildren[c]->NumChildren) pEl=NULL;
01330                 plEl=plEl->pListNext;
01331             }
01332         }
01333 
01334         if (pEl)
01335         {
01336             Unlink(pEl);
01337             if (!pEl->Pixels) CurrentLeaves++;
01338             for (INT32 c=0; c<8; c++) if (pEl->pChildren[c])
01339             {
01340                 pEl->Pixels+=pEl->pChildren[c]->Pixels;
01341                 
01342                 Unlink (pEl->pChildren[c]);
01343                 pEl->NumChildren--;
01344                 ERROR3IF(pEl->pChildren[c]->NumChildren, "OK, why have I been given an octree element with children?");
01345                 delete pEl->pChildren[c];
01346                 pEl->pChildren[c]=NULL;
01347                 CurrentLeaves--;
01348             }
01349             Link(pEl);
01350             //CheckIntegrity();
01351         } else
01352         {
01353             ERROR3("Can't find a candidate for combining octree");
01354             break;
01355         }
01356     }
01357     
01358     return TRUE;
01359 }

void Octree::Link (  OctreeElement *  pEl  )  [private]
 

Links elt into lists.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
pEl = pointer to element to unlink [INPUTS]
None [OUTPUTS]
Returns:
None

Errors: 2 & 3 Scope:

See also:
-

Definition at line 1474 of file bfxpixop.cpp.

01475 {
01476     // Now insert pEl on the correct child list
01477     if ((pEl->pListNext=/*assign*/ListHead[pEl->Depth][pEl->NumChildren])!=NULL) // if the list is non empty
01478     {
01479         ListHead[pEl->Depth][pEl->NumChildren]->pListPrev=pEl; // adjust the prev pointer
01480     }
01481     pEl->pListPrev=NULL; // our prev ptr set to NULL
01482     ListHead[pEl->Depth][pEl->NumChildren]=pEl; // put us at the front of the list
01483 }

void Octree::Unlink (  OctreeElement *  pEl  )  [private]
 

Unlinks elt from lists.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
19/04/95
Parameters:
pEl = pointer to element to unlink [INPUTS]
None [OUTPUTS]
Returns:
None

Errors: 2 & 3 Scope:

See also:
-

Definition at line 1437 of file bfxpixop.cpp.

01438 {
01439     // Now unlink pEl from its previous chain firt by sorting out NextPtr of Prev elt
01440     if (pEl->pListPrev)
01441     {
01442         pEl->pListPrev->pListNext=pEl->pListNext; // possibly NULL
01443     }
01444     else // it was the head previously
01445     {
01446         ListHead[pEl->Depth][pEl->NumChildren]=pEl->pListNext; // possibly NULL
01447     }
01448     // then by sorting out PrevPtr of next elt
01449     if (pEl->pListNext) // if there is a next ptr
01450     {
01451         pEl->pListNext->pListPrev=pEl->pListPrev; // possibly NULL
01452     }
01453     pEl->pListNext=pEl->pListPrev=NULL;
01454     return;
01455 }

Member Data Documentation

INT32 Octree::CurrentIndex [private]
 

Definition at line 581 of file bfxpixop.h.

INT32 Octree::CurrentLeaves [private]
 

Definition at line 579 of file bfxpixop.h.

OctreeElement* Octree::ListHead[9][9] [private]
 

Definition at line 583 of file bfxpixop.h.

INT32 Octree::MaxLeaves [private]
 

Definition at line 578 of file bfxpixop.h.

OctreeElement* Octree::pTopElement [private]
 

Definition at line 580 of file bfxpixop.h.

The documentation for this class was generated from the following files:
Generated on Sat Nov 10 03:57:17 2007 for Camelot by  doxygen 1.4.4