Thread: Quad-tree algorithm problems

  1. #1
    Registered User
    Join Date
    Jan 2006
    Posts
    2

    Quad-tree algorithm problems

    Hi everyone,

    I am trying to make a quadtree compression algorithmn for tga files, but have come across a lot of problems which I am not sure how to solve. If anybody could help me out that would be greatly appreciated. Thanks

    Here is the current code I have:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <conio.h>
    
    #define HEADERSIZE 18
    
    void CreateNode(unsigned int Bounding[4],unsigned int ParentID,unsigned int NodeID); //creates nodes, used to create the quadtree
    unsigned int CalcNodeNum(unsigned int max,unsigned int min); //create
    typedef struct
    {
            unsigned char R;
            unsigned char G;
            unsigned char B;
     } Pixel;
    
    void checkFP (FILE *fp);
    
     typedef struct quadtreeNode
     {     
            unsigned char R;
            unsigned char G;
            unsigned char B;
            quadtreeNode *ptr_NW;
            quadtreeNode *ptr_NE;
            quadtreeNode *ptr_SW;
            quadtreeNode *ptr_SE;
     };
     bool RGBcheck(int x,int y,Pixel Image[],int width,int height);
    
    
    void quad(int initialWidth, int EndWidth,int initialHeight,int EndHeight ,quadtreeNode *newNode,quadtreeNode *ptr_root, quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[],int width,int height);
    void newnode(int initialWidth, int EndWidth, int initialHeight, int EndHeight, quadtreeNode *newNode,quadtreeNode *ptr_root, quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[], int width,int height);
    void checkImage(int initialWidth, int initialHeight, int EndWidth, int EndHeight, quadtreeNode *newNode, quadtreeNode *ptr_root,quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[], int width,int height);
    int main(void)
    {
    
        int c;
        char word[2];
        FILE * fp;
        
        
        printf("\nLoading Header ... ");fflush(stdout);
        //fp = fopen("ghg.tga", "rb");   
            fp = fopen("gf.tga", "rb");   
        
         checkFP(fp);
         unsigned char header[HEADERSIZE];
         for(c=0;c<HEADERSIZE;c++)
         {
    	  fscanf(fp, "%c", &header[c]);
          } 
          
          int width   = (header[13]<<8)+header[12];
          int height   = (header[15]<<8)+header[14];
          printf("Done (%dx%d). Ver. 1.1\n", width, height);
          fflush(stdout); 
          
          Pixel Image[width*height];   
          printf("Loading Data ... \n");fflush(stdout);
          printf("%d\n", width);
          for(c=0;c<width*height;c++)
           {
           fscanf(fp, "%c", &Image[c].B);
           fscanf(fp, "%c", &Image[c].G);  
           fscanf(fp, "%c", &Image[c].R); 
          
           }  
        struct quadtreeNode *ptr_root; //
        struct quadtreeNode *ptr_next;
        struct quadtreeNode *ptr_previous;
    
        struct quadtreeNode *newNode;
        ptr_root = newNode;
        newNode = (quadtreeNode *)malloc(sizeof(quadtreeNode)); 
    
        ptr_root->ptr_NW = NULL;
        ptr_root->ptr_NE= NULL;
        ptr_root->ptr_SW = NULL;
        ptr_root->ptr_SE = NULL;
        ptr_next = newNode;
        ptr_previous = newNode;
        
        int initialWidth = 0;
        int initialHeight = 0;
        int EndWidth = width;
        int EndHeight = height;   
    
        checkImage(initialWidth,initialHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height);
            fclose(fp);
            printf("Done.\n");fflush(stdout);
    
            printf ("\n\n==============================\n%d",width*height);
            printf("Done.\n");fflush(stdout);
            gets(word);
            gets(word);
    return EXIT_SUCCESS;  
    }
    // create new node/leaf node
    void newnode(int initialWidth, int EndWidth, int initialHeight, int EndHeight, quadtreeNode *newNode,quadtreeNode *ptr_root, quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[], int width, int height)
    {
         printf("new node\n");fflush(stdout);
        // newNode = new struct quadtreeNode;
    //     ptr_next->ptr_NW->ptr_NW= NULL;
    //     ptr_next->ptr_NW->ptr_NE = NULL;
    //     ptr_next->ptr_NW->ptr_SW = NULL;
    //     ptr_next->ptr_NW->ptr_SE = NULL;
    //     
    //     newNode = new struct quadtreeNode;
    //     ptr_next->ptr_NE->ptr_NW = NULL;
    //     ptr_next->ptr_NE->ptr_NE = NULL;
    //     ptr_next->ptr_NE->ptr_SW = NULL;
    //     ptr_next->ptr_NE->ptr_SE = NULL;
    //     
    //     newNode = new struct quadtreeNode;
    //     ptr_next->ptr_SW->ptr_NW = NULL;
    //     ptr_next->ptr_SW->ptr_NE = NULL;
    //     ptr_next->ptr_SW->ptr_SW = NULL;
    //     ptr_next->ptr_SW->ptr_SE = NULL;
    //     
    //     newNode = new struct quadtreeNode;
    //     ptr_next->ptr_SE->ptr_NW = NULL;
    //     ptr_next->ptr_SE->ptr_NE = NULL;
    //     ptr_next->ptr_SE->ptr_SW = NULL;
    //     ptr_next->ptr_SE->ptr_SE = NULL;
    
    //quad each pointer
    quad(initialWidth,EndWidth,initialHeight,EndHeight,newNode,ptr_root,ptr_next->ptr_NW,ptr_next,Image,width,height);
    quad(initialWidth,EndWidth,initialHeight,EndHeight,newNode,ptr_root,ptr_next->ptr_NE,ptr_next,Image,width,height);
    quad(initialWidth,EndWidth,initialHeight,EndHeight,newNode,ptr_root,ptr_next->ptr_SW,ptr_next,Image,width,height);
    quad(initialWidth,EndWidth,initialHeight,EndHeight,newNode,ptr_root,ptr_next->ptr_SE,ptr_next,Image,width,height);
    }
    //checks the image
    void checkImage(int initialWidth, int initialHeight, int EndWidth, int EndHeight, quadtreeNode *newNode, quadtreeNode *ptr_root, quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[], int width,int height)
    {
    //     printf("***********Check image************\n");
    //     printf("Initial width : %d Initial Height : %d\n",initialWidth,initialHeight);
    //     printf("End width : %d End height : %d\n", EndWidth,EndHeight);
    //     printf("For Y = %d ; Y < %d; Y++\n",initialHeight,EndHeight);
    //     printf("For X = %d ; X < %d; X++\n",initialWidth,EndWidth);
    //     printf("Cell width %d\n",EndWidth-initialWidth);
    //     printf("Width %d\n",width);
    //     printf("check image\n");fflush(stdout);
    
         for(int y = initialHeight;y<EndHeight;y++)
         {
              for(int x = initialWidth; x<EndWidth;x++)
              {
                      if ((RGBcheck(x,y,Image,width,height) == false))   //if pixels dont match            
                      {
                          
                         printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);                                                                   
                         newnode(initialWidth,initialHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_next,ptr_previous,Image,width,height);
                         fflush(stdout);
                         }
                        // else //if width and height are both equal to 1 pixel 
                        // {  
                         //     printf("width/height are 1 pixel in width\n"); 
                           //create new node - need to go back  
                        //   newnode(initialWidth,initialHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_previous,Image,width,height);
    //********************************************************************************************************************************************//
                           //problem is here
                           //not sure if i need this
                           //go back to previous pointers (can i do this like this?) or do i need to loop through it
                          // ptr_previous->ptr_NW->R = Image[x+(width * y)].R;
    //                       ptr_previous->ptr_NW->G = Image[x+(width * y)].G;                             
    //                       ptr_previous->ptr_NW->B = Image[x+(width * y)].B;
    //                       ptr_previous->ptr_NE->R = Image[x+(width * y)].R;
    //                       ptr_previous->ptr_NE->G = Image[x+(width * y)].G;
    //                       ptr_previous->ptr_NE->B = Image[x+(width * y)].B;
    //                       ptr_previous->ptr_SW->R = Image[x+(width * y)].R;
    //                       ptr_previous->ptr_SW->G = Image[x+(width * y)].G;
    //                       ptr_previous->ptr_SW->B = Image[x+(width * y)].B; 
    //                       ptr_previous->ptr_SE->R = Image[x+(width * y)].R;
    //                       ptr_previous->ptr_SE->G = Image[x+(width * y)].G;                     
    //                       ptr_previous->ptr_SE->B = Image[x+(width * y)].B;    
    //********************************************************************************************************************************************//                                          
                       //  }
                      //} 
                      else //if pixels match 
                      {  
                      printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);                                                                                             
                       //ptr_next->R = Image[x+(width * y)].R;
                      // ptr_next->G = Image[x+(width * y)].G;
                      // ptr_next->B = Image[x+(width * y)].B;  
                       // not sure how to go to next quadrant of image here  
                      }
                } 
                }  
         
    }
    
    
    // split the image into quadrants
    void quad(int initialWidth, int EndWidth,int initialHeight,int EndHeight ,quadtreeNode *newNode, quadtreeNode *ptr_root,quadtreeNode *ptr_next, quadtreeNode *ptr_previous, Pixel Image[],int width,int height)
    {
         int middlePoint = ((EndWidth - initialWidth)/2);
         int newWidth = initialWidth + middlePoint;
         int newHeight = initialHeight + middlePoint;
         int newEndWidth = EndWidth/2;
         int newEndHeight = EndHeight/2;
              
         int y;
         int x;
    //     printf("\n");
    //     printf("Width : %d Height : %d\n",width,height);
    //     printf("**************Quad*****************\n");
    //     printf("Initial width : %d Initial Height : %d\n",initialWidth,initialHeight);
    //     printf("End width : %d End height : %d\n", EndWidth,EndHeight);
    //     printf("New End width : %d New End height : %d\n", newEndWidth,newEndHeight);
    //     printf("Middlepoint : %d \n", middlePoint);    
    //    printf("***********************************\n");
    
    if((initialWidth == EndWidth/2)||(initialWidth > EndWidth/2)&&(initialHeight == EndHeight/2) && (initialHeight > EndHeight/2))
    {    
                   
    checkImage(initialWidth,initialHeight,newWidth,newHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //topleft
    checkImage(newWidth,initialHeight,EndWidth,newHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //top right
    checkImage(initialWidth,newHeight,newWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom left
    checkImage(newWidth,newHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom right
    }    
    if((initialWidth == EndWidth/2)||(initialWidth > EndWidth/2))
    {
    checkImage(initialWidth,initialHeight,newWidth,newEndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //topleft
    checkImage(newWidth,initialHeight,EndWidth,newEndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //top right
    checkImage(initialWidth,newEndHeight,newWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom left
    checkImage(newWidth,newEndHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom right
    }
    if((initialHeight == EndHeight/2)||(initialHeight > EndHeight/2))
    {
    checkImage(initialWidth,initialHeight,newEndWidth,newHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //topleft
    checkImage(newEndWidth,initialHeight,EndWidth,newHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //top right
    checkImage(initialWidth,newHeight,newEndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom left
    checkImage(newEndWidth,newHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom right
    }
    else
    {
    checkImage(initialWidth,initialHeight,newEndWidth,newEndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //topleft
    checkImage(newEndWidth,initialHeight,EndWidth,newEndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //top right
    checkImage(initialWidth,newEndHeight,newEndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height); //bottom left
    checkImage(newEndWidth,newEndHeight,EndWidth,EndHeight,newNode,ptr_root,ptr_previous,ptr_next,Image,width,height);//bottom right
    }
    //printf("***********************************\n");
    //printf("\n************************Top left************************\n");  
    //for(y=initialHeight;y<newEndHeight;y++)
    //{  
    //    for (x=initialWidth;x<newEndWidth;x++)    
    //     {  
    //             printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);                 
    //     } 
    //} 
    //printf("***********************************\n");
    //printf("\n************************Top right************************\n");  
    //for(y=initialHeight;y<newEndHeight;y++)
    //{  
    //    for (x=newEndWidth;x<EndWidth;x++)  
    //     {  
    //             printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);                 
    //     } 
    //} 
    //printf("***********************************\n");
    //printf("\n************************Bottom left************************\n");  
    //for(y=newEndHeight;y<EndHeight;y++) 
    //{  
    //  for (x=initialWidth;x<newEndWidth;x++)  
    //     {  
    //             printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);                 
    //     } 
    //} 
    //
    //printf("***********************************\n");
    //printf("\n************************Bottom right ************************\n"); 
    //for(y=newEndHeight;y<EndHeight;y++) 
    //{  
    //  for (x=newEndWidth;x<EndWidth;x++)  
    //     {  
    //             printf(" R: %d :  G %d :  B %d Coords X:%d,Y:%d Width %d Height %d\n",Image[x+(y*width)].R, Image[x+(y*width)].G, Image[x+(y*width)].B,x,y,width,height);                 
    //     } 
    //}  
    
    }
    
         
    void checkFP(FILE * fp)
    {
         char word[2];
         if(fp==NULL)
         {
                     printf("File not found : Press any key to exit");
                     gets(word);
                     gets(word);
                     exit(EXIT_FAILURE);
          }
    }
    
    // checks pixels
    bool RGBcheck(int x,int y,Pixel Image[],int width,int height)
    {
    if ((Image[x+(y*width)].R == Image[x+(y*width)+1].R)&&(Image[x+(y*width)].G == Image[x+(y*width)+1].G)&&(Image[x+(y*width)].B == Image[x+(y*width)+1].B))
        {
       // printf("*\n");
        return true;
        }
    else
        {
    
    return false;
        }
    
    }
    Regards Maiden

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So apart from being ugly and non-portable code, what's the problem?

  3. #3
    Registered User
    Join Date
    Jan 2006
    Posts
    2
    Well the problem is the quad function doesn't work at all, it doesn't quad the image. Any help would be appreciated

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Resource manager tree
    By VirtualAce in forum Game Programming
    Replies: 23
    Last Post: 09-07-2007, 10:27 PM
  2. Binary Search Tree Insertion Algorithm Help
    By bcianfrocca in forum C++ Programming
    Replies: 2
    Last Post: 05-09-2005, 07:35 PM
  3. OpenGL, loading BMP Textures?
    By Zeusbwr in forum Game Programming
    Replies: 12
    Last Post: 12-09-2004, 05:16 PM
  4. Tree Problem
    By recluse in forum C Programming
    Replies: 36
    Last Post: 12-04-2004, 03:06 PM
  5. btree balancing
    By ender in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 02:22 PM