Java-Gaming.org
 Featured games (81) games approved by the League of Dukes Games in Showcase (497) Games in Android Showcase (114) games submitted by our members Games in WIP (563) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1] 2
 ignore  |  Print
 traversing all pixels in an area  (Read 6034 times) 0 Members and 1 Guest are viewing this topic.
moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Posted 2003-10-24 10:41:20 »

I need an algorithm to travel through all the cells, in an area which has been defined, in a 2 dimenional map (i.e. image)

Currently i have made and am using a wall following routine with a stack of "Multiple Direction Fork" co-ordinates. My problem is that the stack can get very large.

basically the algorithm is:

0. set current pixel to (0,0)
1. set Direction to none.
2. if pixel above current is empty and pixel left is non-empty, Direction = UP
3. else if pixel left of current is empty and pixel below is non-empty, Direction = LEFT
4. else if pixel below current is empty and pixel right is non-empty, Direction = DOWN
5. else if pixel right of current is empty and pixel above is non-empty, Direction = RIGHT
6. if Direction is UP
6a. if pixels (-1,-1) and (+1,-1) or (+1,+1) are non empty then add current pixel to stack.
7. if Direction is DOWN
7a. if pixels (-1,+1) and (+1,+1) or (-1,-1) are non empty then add current pixel to stack.
8. if Direction is RIGHT
8a. if pixels (+1,-1) and (+1,+1) or (-1,+1) are non empty then add current pixel to stack.
9. if Direction is LEFT
9a. if pixels (-1,-1) and (-1,+1) or (+1,-1) are non empty then add current pixel to stack.
10. if direction is not none process current pixel
10a. else if there are pixels in the stack then pop a pixel and set the current pixel to it.
10b. else exit algorithm
11. move current pixel in direction specified.
12. repeat 1

Does anyone know how to reduce the number of pixels entering the stack or indeed know of a better algorithm to traverse all the pixels in a shape.

The following pictures illusrate my problem:

With out stack pixel indicator(Blue):
www.geocities.com/budgetanime/lena.gif.txt

With stack pixel indicator (Blue)
www.geocities.com/budgetanime/lena1.gif.txt
www.geocities.com/budgetanime/server1.gif.txt

(shaded pixels are the pixels that have been processed, solid blue pixels are pixels that had been in the stack at some point, grey/white pixels define the bounding areas and black pixels are unprocessed pixels)

(you will have to change the file extension after you have downloaded it)

As you can see there are long diagonal lines of (blue) pixels that have been in the stack.

Any suggestions are welcome!

Thanks

JGO Wizard

Medals: 15
Projects: 19

Mojang Specifications

 « Reply #1 - Posted 2003-10-24 11:46:21 »

Do you mean a flood fill?

Play Minecraft!
moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #2 - Posted 2003-10-24 23:14:03 »

Thanks for putting me on to flood fill, it is more than 50% faster than my current fill method.

However it seems cause stack overflows when filling large areas

the flood fill method as it stands:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78 `      public void FloodFill(int x,int y,int width, int height,boolean[][] PixelsChecked,byte[][] frame)      {            count=0;            java.util.Random r=new java.util.Random();            int colourR= r.nextInt(240);            int colourG= r.nextInt(240);            int colourB= r.nextInt(240);            LinearFloodFill4(x,y,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);      }      private void LinearFloodFill4(int x, int y,int width,int height,boolean[][] PixelsChecked,byte[][] frame,int count,int colourR,int colourG,int colourB)      {                            //FIND LEFT EDGE OF COLOR AREA            int LFillLoc=x; //the location to check/fill on the left            while(true)            {                   //fill with the color                  count+=1;                  frame[y*width+LFillLoc][0]=(byte) (colourR+count%15);                  frame[y*width+LFillLoc][1]=(byte) (colourG+count%15);                  frame[y*width+LFillLoc][2]=(byte) (colourB+count%15);                  PixelsChecked[LFillLoc][y]=true;                  LFillLoc--;               //de-increment counter                  if(LFillLoc<=0 ||                         (PixelsChecked[LFillLoc][y]))                              //exit loop if we're at edge of bitmap or color area                              break;                    }            LFillLoc++;                //FIND RIGHT EDGE OF COLOR AREA            int RFillLoc=x; //the location to check/fill on the left            while(true)            {                   //fill with the color                  count+=1;                  frame[y*width+RFillLoc][0]=(byte) (colourR+count%15);                  frame[y*width+RFillLoc][1]=(byte) (colourG+count%15);                  frame[y*width+RFillLoc][2]=(byte) (colourB+count%15);                  PixelsChecked[RFillLoc][y]=true;                  RFillLoc++;          //increment counter                  if(RFillLoc>=width ||                         (PixelsChecked[RFillLoc][y]))                              //exit loop if we're at edge of bitmap or color area                              break;                    }            RFillLoc--;                    //START THE LOOP UPWARDS AND DOWNWARDS                                    for(int i=LFillLoc;i<=RFillLoc;i++)            {              //START LOOP UPWARDS              //if we're not above the top of the bitmap               if(y>0 &&                   (!(PixelsChecked[i][y-1])))                     LinearFloodFill4(i,y-1,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);              //START LOOP DOWNWARDS              if(y<(height-1) &&                       (!(PixelsChecked[i][y+1])))                     LinearFloodFill4(i,y+1,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);            }              }   `

it is modified code from the Flood Fill Algorithms in C# and GDI+ tutorial by jdunlap:

http://www.codeproject.com/cs/media/floodfillincsharp.asp

i will now try using the queued floodfill rather than the linear flood fill as it is not going to cause a stack over flow, however it apparantly is much slower than the linear method...
moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #3 - Posted 2003-10-25 00:09:14 »

I have now implemented the Queued Flood Fill and have recieved quite dissapointing times

Flood Fill - queue - 4 dir:   406 msec
Flood Fill - queue - 8 dir:   3187 msec
Flood Fill - linear  -  4 dir:   47 msec
Follow Wall (my Algrthm):   125 msec

hmm, does anyone know of another filling algorithm which may peform better than my follow wall algorithm?

moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #4 - Posted 2003-10-25 01:21:45 »

A person suggested filling by rows, i.e. go left->right filling pixels until you hit a boundary pixel. then look above you to see if there are row(s) that are to be filled and then fill each of those.

then do the same for rows below you.

I have implemented a row Fill however it does not seem to improving processing time...

here is how i implemented it

Recursive Row Fill:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50 `      public void RecRowFill(int x,int y,int width, int height,boolean[][] PixelsChecked,byte[][] frame)      {            count=0;            java.util.Random r=new java.util.Random();            int colourR= r.nextInt(240);            int colourG= r.nextInt(240);            int colourB= r.nextInt(240);            rowFill(x,y,width,height, PixelsChecked,frame,count,colourR,colourG,colourB);      }            public void rowFill(int x,int y,int width, int height,boolean[][] processedPixel,byte[][] frame,int count,int colourR,int colourG,int colourB)      {            int sx=x;                        while (sx0)            {                  for (int i=x;i0 && !processedPixel[tx][y-1]) tx--;                              rowFill(tx+1,y-1,width,height, processedPixel,frame,count,colourR,colourG,colourB);                        }                  }            }            if (y0 && !processedPixel[tx][y+1]) tx--;                              rowFill(tx+1,y+1,width,height, processedPixel,frame,count,colourR,colourG,colourB);                        }                  }            }                  }`

Queued Row Fill:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67 `      public void QueueRowFill(int x,int y,int width, int height,boolean[][] PixelsChecked,byte[][] frame)      {            LinkedList CheckQueue=new LinkedList();                        Integer Count=new Integer(0);            java.util.Random r=new java.util.Random();            int colourR= r.nextInt(240);            int colourG= r.nextInt(240);            int colourB= r.nextInt(240);                        //start the loop                  rowFillQ(x,y,width,height, PixelsChecked,frame,Count,colourR,colourG,colourB,CheckQueue);                  //call next item on queue                  while(CheckQueue.size()>0)                  {                        x=((Item) CheckQueue.get(0)).freq;                        y=((Item) CheckQueue.get(0)).value;                        CheckQueue.remove(0);                        //System.out.println (CheckQueue.size());                        rowFillQ(x,y,width,height, PixelsChecked,frame,Count,colourR,colourG,colourB,CheckQueue);                  }      }            public void rowFillQ(int x,int y,int width, int height,boolean[][] processedPixel,byte[][] frame,Integer Count,int colourR,int colourG,int colourB,LinkedList queue)      {            int sx=x;                        while (sx0)            {                  for (int i=x;i0 && !processedPixel[tx][y-1]) tx--;                              queue.add(new Item(tx+1,y-1));                        }                  }            }            if (y0 && !processedPixel[tx][y+1]) tx--;                              //rowFill(tx+1,y+1,width,height, processedPixel,frame,count,colourR,colourG,colourB);                              queue.add(new Item(tx+1,y+1));                        }                  }            }                  }`

I have re-calculated the each algorithm times using a large image (1792x1200)

Recusive Row Fill: FAILED (Stack Overflow)
Queued Row Fill: 6496 msec
Linear Row Fill: FAILED (Stack Overflow)
Queued Flood Fill 8 dirs: 33047 msec
Queued Flood Fill 4 dirs: 14140 mesc
Wall Following Fill: 1328 msec

hmm, it is looking like my wall following fill is the best peformer on average. (i.e. linear Flood Fill easily beats it on small areas, however fails on larger areas, while my wall following fill seems to work very well on large areas)

It looks like i will be staying with the wall following fill unless anyone knows of another filling aglorithm.

tom
 « Reply #5 - Posted 2003-10-25 10:40:22 »

I think your queue is hurting your performance. All that new'ing of Items adds up. There is no need to use a queue as a stack will do the same. You can implement you own stack using an int array. It's easy, just double the stack size when it needs to grow.

This way you will hopefully get the same execution time as the recursive versions, but without the stack overflows.

moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #6 - Posted 2003-10-25 21:48:07 »

hmm, i was thinking the same thing (that the new operation was the bottleneck)

you suggest an int array? i would need to use two i am thinking, one for the x co-ordinate and one for the y co-ordinate.

I will impelment the array stack (for all the algorithms) and see what the performance is like.

Cheers
moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #7 - Posted 2003-10-26 03:35:44 »

i have implemented a stack of my own based on int arrays... however it has had a major negative impact on peformance.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48 `      class MyStack      {            int[] x;            int[] y;            int index;            public MyStack()            {                  x= new int[1024];                  y= new int[1024];                  index=0;            }                        public int size()            {                  return index;            }                        public void add(int x1,int y1)            {                  if (index==x.length)                  {                        int[] temp= new int[2*x.length];                        System.arraycopy(x,0,temp,0,x.length);                        x=temp;                        temp= new int[2*y.length];                        System.arraycopy(y,0,temp,0,y.length);                        y=temp;                  }                  x[index]=x1;                  y[index]=y1;                  index++;            }                        public int getX() throws Exception            {                  return x[index-1];            }                        public int getY() throws Exception            {                  return y[index-1];            }                        public void remove() throws Exception            {                  index--;            }      }`

the wall following algorithm using MyStack gives 37547 msecs as compared to the previous 1328.

The Flood Fill using My stack comes to 37672 msec which is worse than using the queue ( 4 direction )

Is there something inheritly wrong with my stack?

tom
 « Reply #8 - Posted 2003-10-26 15:04:13 »

Quote
However it seems cause stack overflows when filling large areas

I think it has some bugs.

 1  2  3  4 `if(LFillLoc<=0 || (PixelsChecked[LFillLoc][y]))if(RFillLoc>=width || (PixelsChecked[RFillLoc][y]))if(y>0 && (!(PixelsChecked[i][y-1])))if(y<(height-1) &&  (!(PixelsChecked[i][y+1])))`

All of the listed lines are missing a check to see if it is still inside the fill area.

Here is my version: (memeber variables not listed)
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 `      private void linearFloodFill4(int x, int y) {            int LFillLoc=x;            while (true) {                  image[y][LFillLoc] = fillcolor;                  pixelsChecked[y][LFillLoc] = true;                  LFillLoc--;                  if (LFillLoc<=0 || (image[y][LFillLoc] != startcolor) || (pixelsChecked[y][LFillLoc]))                        break;            }            LFillLoc++;            int RFillLoc=x;             while (true) {                  image[y][RFillLoc]=fillcolor;                     pixelsChecked[y][RFillLoc] = true;                  RFillLoc++;                  if (RFillLoc>=width || (image[y][RFillLoc] != startcolor) || (pixelsChecked[y][RFillLoc]))                        break;            }            RFillLoc--;            for (int i=LFillLoc;i<=RFillLoc;i++) {                  if ((y>0) && (image[y-1][i]==startcolor) && !pixelsChecked[y-1][i]) {                        linearFloodFill4(i, y-1);                  }                  if (y<(height-1) && (image[y+1][i] == startcolor) && !pixelsChecked[y+1][i]) {                        linearFloodFill4(i, y+1);                  }            }      }`

Quote
A person suggested filling by rows, i.e. go left->right filling pixels until you hit a boundary pixel. then look above you to see if there are row(s) that are to be filled and then fill each of those.

This is exactly what the linear flood fill does.

Quote

I take that back. I implemented a non recursive linear flood fill using an array of int stack and a linked list. The linked list version was much faster.

As a conclusion I will suggest to get the linear flood fill working. It should not be as heavy on the stack as other methods. However, here is a non recursive version, if you still get stack overflows:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64 `      public void linearFloodFill(int startx, int starty, int image[][], boolean pixelsChecked[][], int fillcolor) {            LinkedList stack = new LinkedList();            int height = image.length;            int width = image[0].length;            int startcolor = image[starty][startx];            stack.addLast(getLineSeg(startx, starty, width, image, pixelsChecked, startcolor, fillcolor));            while (stack.size() > 0) {                  LineSeg nextLine = (LineSeg) stack.getLast();                  if (nextLine.x >= nextLine.right) {                        if (nextLine.doneTop == 0) {                              nextLine.x = nextLine.left;                              nextLine.doneTop = 1;                        } else {                              stack.removeLast();                        }                  }                  int x = nextLine.x;                  int y = nextLine.y;                  nextLine.x++;                  if (nextLine.doneTop == 0) {                        if ((y>0) && (image[y-1][x]==startcolor) && !pixelsChecked[y-1][x]) {                              stack.addLast(getLineSeg(x, y-1, width, image, pixelsChecked, startcolor, fillcolor));                        }                  } else {                        if ((y=width || (image[y][right] != startcolor) || (pixelsChecked[y][right])) {                        break;                  }            }            right--;            return new LineSeg(left, right, y);      }      class LineSeg {            int left, right, x, y, doneTop;            LineSeg(int left, int right, int y) {                  this.left = left;                  this.right = right;                  this.x = left;                  this.y = y;            }      }`

Hope this helps. Although I'm not sure if it's faster than your wall following method

tom
 « Reply #9 - Posted 2003-10-26 17:47:42 »

Correction. The linearFloodFill method should look like this:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23 `      public void linearFloodFill(int startx, int starty, int image[][], boolean pixelsChecked[][], int fillcolor) {            LinkedList stack = new LinkedList();            int height = image.length;            int width = image[0].length;            int startcolor = image[starty][startx];            stack.addLast(getLineSeg(startx, starty, width, image, pixelsChecked, startcolor, fillcolor));            while (stack.size() > 0) {                  LineSeg nextLine = (LineSeg) stack.removeLast();                  int y = nextLine.y;                  int right = nextLine.right;                  for (int x=nextLine.left; x<=right; x++) {                        if ((y>0) && (image[y-1][x]==startcolor) && !pixelsChecked[y-1][x]) {                              stack.addLast(getLineSeg(x, y-1, width, image, pixelsChecked, startcolor, fillcolor));                        }                  }                                    for (int x=nextLine.left; x<=right; x++) {                        if ((y

Now it executes almost at the same speed as the recursive version. Only a 5% overhead because of the linked list.

moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #10 - Posted 2003-10-26 20:05:00 »

Thanks! your effort in creating a working implementation was unexpected is very much appreciated!

I will try your method and see if i gain processing speed.

will let you know.
moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #11 - Posted 2003-10-26 20:41:04 »

I have implemented a slighyly modified version of your code

the changes:

image -> frame
checkedPixel[][] now

• checkedPixel contains the boundary points when first sent the the flood fill algorithm

 1  [/li][/list]2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63 `      public void linearFloodFill(int startx,int starty,int width, int height,boolean[][] pixelsChecked,byte[][] frame) {        LinkedList stack = new LinkedList();        int fcount=0;        stack.addLast(getLineSeg(startx, starty, width, frame, pixelsChecked,fcount));        while (stack.size() > 0) {         LineSeg nextLine = (LineSeg) stack.removeLast();         int y = nextLine.y;         int right = nextLine.right;         for (int x=nextLine.left; x<=right; x++) {          if ((y>0)  && !pixelsChecked[x][y-1]) {             stack.addLast(getLineSeg(x, y-1, width, frame, pixelsChecked,fcount));          }         }             for (int x=nextLine.left; x<=right; x++) {          if ((y=width || (pixelsChecked[right][y])) {          break;         }        }        right--;        return new LineSeg(left, right, y);       }        class LineSeg {        int left, right, x, y, doneTop;        LineSeg(int left, int right, int y) {         this.left = left;         this.right = right;         this.x = left;         this.y = y;        }       }  `

however it seems to be not filling each row correcty... and more than likely a problem due to my modifications    I cannot see the error myself, maybe you can?

see www.geocities.com/budgetanime/lena.tif.txt for an example of what i mean.
moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #12 - Posted 2003-10-26 20:50:59 »

damn you copy&paste!

The problem was that when i copied:

 1  2  3 `        frame[y*width+left][0]=(byte) 0;         frame[y*width+left][1]=(byte) (50+fcount%55);         frame[y*width+left][2]=(byte) 0;   `

for the right fill, i forgot to chage the left variable to right

now for some comparisons....
moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #13 - Posted 2003-10-26 21:19:08 »

Looks good!!

for all the tests i run with both my wall following and your linear flood fill, your flood fill consistantly peformed faster than my wall following in some cases 50% or more. This is the same as for the original linear flood fill earlier in this post.

The good news is that your version is superior to the previous version as you implement your own stack and thus have no overflow errors. (worked on images 2360x2100)

thanks heaps!
tom
 « Reply #14 - Posted 2003-10-26 22:03:29 »

Quote
checkedPixel[][] now

I used [y]
• because the algorithm iterates over the x variable. Then it will touch only memory in the same area, and that can give better cach performance. But I haven't tested it so the gain is probably to smal to notice. But the other thing is that you can do this: "boolean line[] = checkedPixels[y]". This will reduce array lookups.

I've also come up with a new optimazation that increased the speed with ~25%. It's where the new LineSeg is added to the stack. X is set to newLineSeg.right, because it's known that all pixels to the left is set. Also the loop is getting so tight that an int[] stack implementation is another 20% faster than the LinkedList. Here is the latest int[] stack version. It's hopefully twice as fast as the last one I posted

The stack:
 1  [/li][/list]2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39 `      private static final int elementSize = 4;      private static final int xOff           = 0-elementSize;      private static final int yOff           = 1-elementSize;      private static final int leftOff       = 2-elementSize;      private static final int rightOff   = 3-elementSize;      class LineSegStack {            int[] data;             int size = 0;            int offset;                         public LineSegStack() {                  data= new int[1024*elementSize];                   offset=0;             }             public void push(int left, int right, int y) {                  if (offset == data.length) {                        int[] temp = new int[2*data.length];                         System.arraycopy(data, 0, temp, 0, data.length);                         data = temp;                   }                  offset+=elementSize;                   data[offset+leftOff] = left;                  data[offset+rightOff] = right;                  data[offset+xOff] = left;                  data[offset+yOff] = y;                  size++;            }             public void pop(LineSeg s) {                  s.x = data[offset+xOff];                  s.y = data[offset+yOff];                  s.left = data[offset+leftOff];                  s.right = data[offset+rightOff];                  offset -= elementSize;                   size--;            }      } `

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61 ` // members are initalized in constructor      private int fillcolor = 0xffff00ff;      private boolean pixelsChecked[][]; //[y][x]      private int image[][]; //[y][x]      private int startcolor = 0xffffffff;      private int startx = 0;      private int starty = 0;      private int width;      private int height;      private LineSegStack stack = new LineSegStack();      public long floodStack() {            LineSeg nextLine = new LineSeg(0, 0, 0);            addLineSegToStack(startx, starty);            while (stack.size > 0) {                  stack.pop(nextLine);                  int y = nextLine.y;                  int right = nextLine.right;                  if (y>0) {                        int topLine[] = image[y-1];                        boolean topChecked[] = pixelsChecked[y-1];                        for (int x=nextLine.left; x<=right; x++) {                              if ((topLine[x]==startcolor) && !topChecked[x]) {                                    x = addLineSegToStack(x, y-1);                              }                        }                  }                                    if (y=0 && (line[left] == startcolor) &&  !checked[left]);            left++;            int right=x;             do {                  line[right]=fillcolor;                     checked[right] = true;                  right++;            } while (right

Enjoy!

moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #15 - Posted 2003-10-27 00:48:43 »

I have implemented your latest vesion.

I have quite interesting results:

 1  2  3  4  5  6 `            image size   Flood_new   Flood_old   Wall_Follow              640x337         172         78           105             512x512         140         78           141             1280x1024       203         609          985             2482x2688       1390        6110         5344 `

where:
Flood_new is your latest Linear Flood Fill Alg
Flood_old is your previous Linear Flood Fill Alg
and Wall_Follow is my wall following algorithm.

Time is measured in millisec and is the avg of 5 runs.

It seems for lower resolution images, your first method seems to out peform your newer version, however it is drastically faster once the image starts getting large.

There must be an inital over head with your second method which becomes less of an impact when more pixels are processed.

moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #16 - Posted 2003-10-27 00:51:50 »

and that the old method seems to get progressivly worse as compared to the wall following as the image gets very large.
tom
 « Reply #17 - Posted 2003-10-27 10:09:31 »

The only extra overhead with the new method is the int stack. You could try reusing it, if thats acceptable. Make it a static member, and reset it at the start of the flood fill. Reducing the inital stack size on smal images might also help.

Not sure why the old method slows downs that much.

There is one more improvement that can be made to the algorithm. It is to not check for "collision" from where it come from. Here's an extract from the code:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 `if (y>0) { // fill the line above this line      int topLine[] = image[y-1];      boolean topChecked[] = pixelsChecked[y-1];  // did we come from there?      if (nextLine.fromtop == 1) {   // check on the left side of where we come from            int min = Math.min(nextLine.prevleft, right);            for (int x=nextLine.left; x<=min; x++) {                  if ((topLine[x]==startcolor) && !topChecked[x]) {                        x = addLineSegToStack(x, y-1, nextLine.left, right, 0);                  }            }   // check on the right side of where we come from            for (int x=Math.max(nextLine.prevright, nextLine.left); x<=right; x++) {                  if ((topLine[x]==startcolor) && !topChecked[x]) {                        x = addLineSegToStack(x, y-1, nextLine.left, right, 0);                  }            }      } else {  // did not come from this side: check the whole line            for (int x=nextLine.left; x<=right; x++) {                  if ((topLine[x]==startcolor) && !topChecked[x]) {                        x = addLineSegToStack(x, y-1, nextLine.left, right, 0);                  }            }      }}`

Gave me a 10-15% improvement.

moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #18 - Posted 2003-10-27 20:28:32 »

Wow!   just by using the same instance of the stack the fill operation has improved effeciency another 50% (the 512x512 image is filled in 68 msec and the 2482x2688 is filled in 609 msec.

From the latest code snippet, related to the do not "collision" detect from the line you have come from, i am unsure how the extra parameters are used in addLineSegToStack.

i.e. addLineSegToStack(x, y-1, nextLine.left, right, 0)

tom
 « Reply #19 - Posted 2003-10-27 21:04:14 »

Well, it has kind of a cascading effect, so everything is changed. I'll post the changes.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86 `class LineSeg:// additianal members.int prevleft, prevright, fromtop;class LineSegStack:private static final int elementSize = 7; // changedprivate static final int prevleftOff  = 4-elementSize; // addedprivate static final int prevrightOff = 5-elementSize; // addedprivate static final int fromtopOff   = 6-elementSize; // added// 3 extra paramterspublic void push(int left, int right, int y, int prevleft, int prevright, int fromtop) { ... data[offset+prevleftOff] = prevleft; data[offset+prevrightOff] = prevright; data[offset+fromtopOff] = fromtop; ...} public void pop(LineSeg s) {...s.prevleft = data[offset+prevleftOff];s.prevright = data[offset+prevrightOff];s.fromtop = data[offset+fromtopOff];}// addLineSegToStack(): only change is that the 3 extra parametrs are pushed on the stackprivate int addLineSegToStack(int x, int y, int prevleft, int prevright, int fromtop) {...stack.push(left, right, y, prevleft, prevright, fromtop);return right;}// the meat of floodStack(), which has grown a bit:            while (stack.size > 0) {                  stack.pop(nextLine);                  int y = nextLine.y;                  int right = nextLine.right;                  if (y>0) {                        int topLine[] = image[y-1];                        boolean topChecked[] = pixelsChecked[y-1];                        if (nextLine.fromtop == 1) {                              int min = Math.min(nextLine.prevleft, right);                              for (int x=nextLine.left; x<=min; x++) {                                    if ((topLine[x]==startcolor) && !topChecked[x]) {                                          x = addLineSegToStack(x, y-1, nextLine.left, right, 0);                                    }                              }                              for (int x=Math.max(nextLine.prevright, nextLine.left); x<=right; x++) {                                    if ((topLine[x]==startcolor) && !topChecked[x]) {                                          x = addLineSegToStack(x, y-1, nextLine.left, right, 0);                                    }                              }                        } else {                              for (int x=nextLine.left; x<=right; x++) {                                    if ((topLine[x]==startcolor) && !topChecked[x]) {                                          x = addLineSegToStack(x, y-1, nextLine.left, right, 0);                                    }                              }                        }                  }                                    if (y

prevleft, prevright and fromtop is used to remember where the function was called from. The you don't need to test that area again.

moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #20 - Posted 2003-10-27 21:10:44 »

lol, i kinda went and made changes where i thought it would be appropriate to implement the check.... I should have waited abit too see if you responded before it did it

Well, here are my changes, however it seems that there is no measureable difference... i may have done something wrong...

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122  123  124  125  126  127  128  129  130  131  132  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153  154  155  156  157  158  159  160  161  162  163  164  165  166  167  168  169  170  171  172  173  174  175 `      class LineSegStack {             private static final int elementSize = 7;             private static final int xOff      = 0-elementSize;             private static final int yOff      = 1-elementSize;             private static final int leftOff  = 2-elementSize;             private static final int rightOff   = 3-elementSize;            private static final int prevLeftOff   = 4-elementSize;            private static final int prevRightOff   = 5-elementSize;            private static final int fromTopOff   = 6-elementSize;         int[] data;         int size = 0;        int offset;            public LineSegStack() {         data= new int[1024*elementSize];          offset=0;         }                 public void push(int left, int right, int y,int fromTop) {         if (offset == data.length) {          int[] temp = new int[2*data.length];           System.arraycopy(data, 0, temp, 0, data.length);           data = temp;          }                 if (offset>0)        {                      offset+=elementSize;                data[offset+leftOff] = left;               data[offset+prevLeftOff] = data[offset+prevLeftOff-elementSize];              data[offset+rightOff] = right;               data[offset+prevRightOff] =data[offset+prevRightOff-elementSize];              data[offset+xOff] = left;               data[offset+yOff] = y;               data[offset+fromTopOff]=fromTop;        }        else        {            offset+=elementSize;              data[offset+leftOff] = left;             data[offset+prevLeftOff] = 0;            data[offset+rightOff] = right;             data[offset+prevRightOff] =0;            data[offset+xOff] = left;             data[offset+yOff] = y;             data[offset+fromTopOff]=fromTop;        }        size++;                }          public void pop(LineSeg s) {         s.x = data[offset+xOff];         s.y = data[offset+yOff];         s.left = data[offset+leftOff];         s.right = data[offset+rightOff];         s.prevLeft= data[offset+prevLeftOff];        s.prevRight= data[offset+prevRightOff];        s.fromTop= data[offset+fromTopOff];        offset -= elementSize;          size--;        }       }                   class LineSeg {        int left, right, x, y, doneTop,prevLeft,prevRight,fromTop;              LineSeg(int left, int right, int y) {         this.left = left;         this.right = right;         this.x = left;         this.y = y;        }       }        public void linearFloodFill1(int startx,int starty,int width, int height,boolean[][] pixelsChecked,byte[][] frame,LineSegStack stack ) {      //LineSegStack stack = new LineSegStack();      LineSeg nextLine = new LineSeg(0, 0, 0);       int fcount=0;      java.util.Random r=new java.util.Random((startx+starty)*(starty-startx));      int RColour = r.nextInt(240);      int GColour = r.nextInt(240);      int BColour = r.nextInt(240);      int fromTop=0;       int y,right;      boolean topChecked[];      boolean botChecked[];      addLineSegToStack(startx, starty,width,height,frame,pixelsChecked,fcount,RColour,GColour,BColour,stack,fromTop);       while (stack.size > 0) {        stack.pop(nextLine);        y = nextLine.y;        right = nextLine.right;        fromTop=0;              if (y>0) {             fromTop=1;        // fill the line above this line        //int topLine[] = image[y-1];        topChecked = pixelsChecked[y-1];          // did we come from there?        if (nextLine.fromTop==1) {             // check on the left side of where we come from         int min = Math.min(nextLine.prevLeft, right);          for (int x=nextLine.left; x<=min; x++) {             if (!topChecked[x]) {              x = addLineSegToStack(x, y-1,width,height,frame,pixelsChecked,fcount,RColour,GColour,BColour,stack,fromTop);             }          }             // check on the right side of where we come from         for (int x=Math.max(nextLine.prevRight, nextLine.left); x<=right; x++) {             if (!topChecked[x]) {              x = addLineSegToStack(x, y-1,width,height,frame,pixelsChecked,fcount,RColour,GColour,BColour,stack,fromTop);            }          }         } else {          // did not come from this side: check the whole line         for (int x=nextLine.left; x<=right; x++) {             if (!topChecked[x]) {              x = addLineSegToStack(x, y-1,width,height,frame,pixelsChecked,fcount,RColour,GColour,BColour,stack,fromTop);            }          }         }        }        /           if (y=0 &&  !checked[left]);       left++;       int right=x;        do {             fcount++;            frame[y*width+right][0]=(byte) (RColour+(fcount%15));            frame[y*width+right][1]=(byte) (GColour+(fcount%15));            frame[y*width+right][2]=(byte) (BColour+(fcount%15));           checked[right] = true;        right++;       } while (right

by comparing our two codes, it looks like we are effectivly doing the same thing.
moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #21 - Posted 2003-10-27 21:12:56 »

thinking that we would do the same if coming from a bottom line, i implemented the same checking, however it made the algorithm slightly slower so i removed it.
tom
 « Reply #22 - Posted 2003-10-27 21:57:50 »

The differance is that I also push prevleft and prevright on the stack. I use dummy values in the first push:

 1  2  3 `addLineSegToStack(startx, starty, -1, -1, 0)while (stack.size > 0) { ...`

which means that the previus left and right of the first call is outside the image. That way it will not effect the algorithm.

moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #23 - Posted 2003-10-27 23:29:55 »

hmm, i thought that is what i was doing...

The previous left and right values are the values of left and right of the last stack push operation, So i set the current previous left and previous right to the left and right of the last push operation.

If the current push operation is the beginning of the stack then i just add dummy prev left and prev right, just like you do.
tom
 « Reply #24 - Posted 2003-10-28 08:38:55 »

Well the variable names is a bit misleading I'm afraid

With "previous" I mean the LineSeg that was prosessed when this LineSeg was added to the stack. It makes more sense in the recursive version. Where the previously prosessed lineSeg is the caller, or previous function.

A better name would be "callerLeft, callerRight and callerY", representing the line segment prosessed by the caller of this "function". Here a function is the code inside the "while (stack.size > 0)" loop. You do a function call by pushing a lineSeg onto the stack. It will be processed by the while loop later.

Thats why you can't use the previous lineSeg on the stack, as it is probably not the caller.

fromTop can also be made more clear. It's a boolean representing from what direction the current function was called. The caller is known to be on a neighbouring side, so it is used to find out if the caller is the top or bottom line. It would be better to just store the callers y, and check against that.

Hope this clears it up. If not, I can post a working version.

moogie

JGO Knight

Medals: 12
Projects: 6
Exp: 10 years

Java games rock!

 « Reply #25 - Posted 2003-10-28 18:35:32 »

ah, i understand now

I am currently on my home computer due to being sick today, so i cannot compare the filling times now with the previous times i have given, however as an indicator, that 2482x2688 image is being fillled in 469 msec on my Athlon XP2100. And the 512x512 is done in 47 msec.

I believe we have achieved a very fast fill!

tom
 « Reply #26 - Posted 2003-10-29 01:11:13 »

Yeah, it's a lean, mean flood-filling machine

Jeff

JGO Coder

Got any cats?

 « Reply #27 - Posted 2003-11-03 21:03:02 »

Okay, here's a key difference between Java and C...

In C, recursion is kinda slow, and random access to an array is very fast (a stack is effectively random access as the next access is not deterministicly determinable at compile time).

In a Modern Java VM, thanks to array bounds checking and great JIT compilers, the reverse is true.

Fastest way to speed up something based on an array stack is to recode it as a true recursive routine.  It'll be simpler code, too.

For this and other great insights see:
http://java.sun.com/docs/books/performance

JK

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
tom
 « Reply #28 - Posted 2003-11-03 22:06:41 »

That's true Jeff, and the recursive and non recursive version is equally fast. But it was made non recursive because of stack overflow problems, not speed.

Jeff

JGO Coder

Got any cats?

 « Reply #29 - Posted 2003-11-03 23:06:48 »

So why not just increase your stack size?

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Pages: [1] 2
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 BurntPizza (22 views) 2014-09-19 03:14:18 Dwinin (35 views) 2014-09-12 09:08:26 Norakomi (62 views) 2014-09-10 13:57:51 TehJavaDev (88 views) 2014-09-10 06:39:09 Tekkerue (43 views) 2014-09-09 02:24:56 mitcheeb (65 views) 2014-09-08 06:06:29 BurntPizza (47 views) 2014-09-07 01:13:42 Longarmx (35 views) 2014-09-07 01:12:14 Longarmx (40 views) 2014-09-07 01:11:22 Longarmx (36 views) 2014-09-07 01:10:19
 BurntPizza 37x Riven 18x Rayvolution 18x princec 17x ags1 16x basil_ 16x KevinWorkman 15x LiquidNitrogen 12x kevglass 12x theagentd 11x nsigma 11x HeroesGraveDev 9x deathpat 9x The Lion King 7x TehJavaDev 6x Gibbo3771 6x
 List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50List of Learning Resources2014-07-31 16:26:06List of Learning Resources2014-07-31 11:54:12HotSpot Optionsby dleskov2014-07-08 01:59:08
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org