Re: [glob2-devel] gradient improvement

[Simon Schuler]

Hi,

So, now i've finally had some time to take a look at your patch.

Am Thu, 09 Mar 2006 22:54:39 +0100
schrieb Kai Antweiler
> While thinking about the first part of this mail I recognized an easy
> way to improve Simons implementation.
> 
> http://lists.gnu.org/archive/html/glob2-devel/2005-12/msg00178.html
> 
> Simon wrote:
> > This leads me to an interesting idea about the gradient
> > computations. In updateGradientSmall you don't always have to add
> > every neighbour of a square into the listedAddr list. If you process
> > a square and for example the squares on the upper left and the lower
> > left aren't obstacles you can just update the square on the left,
> > without having to add it into the list. Every square which could be
> > reached from there can also be reached from one of the other two
> > squares.
> 
> 
> 
> Map.cpp line 2267:  if (side > 0 && side < g)
> 
> This tests for obstacles and already processed areas.
> But these two cases should be considered separately.
> Because most of the time we can see the gradient propagation
> locally as a horizontal or vertical line.

OK, after a long thought I finally see what you're doing. I think
you're correct. In the File Map.cpp it's not exactly as I intended it.
In my original patch I made it similar.
http://lists.gnu.org/archive/html/glob2-devel/2005-12/msg00192.html
it was:
else if (side == 0)
        horizFlag |= diagFlags[ci];
which actually does exactly the same thing as your patch.
The person who integrated my patch as a comment (nuage I think) changed
some things... I'm sorry that I haven't looked at the version which is
now in Map.cpp that exactly. Thank you for pointing this out and having
such a close look at my algorithm! It really doesn't seem very useful
the way it is now.

Btw, I had a nice system to prevent bad situations at the beginning. My
original patch replaced the creation of the first list:
I changed
for (int y = 0; y < h; y++)
        for (int x = 0; x < w; x++)
                if (gradient[(y << wDec) | x] >= 3)
                        listedAddr[listCountWrite++] = (y << wDec) | x;

to
for (int y = 0; y < h; y++)
        for (int x = y % 2; x < w; x += 2)
                if (gradient[(y << wDec) | x] >= 3)
                        listedAddr[listCountWrite++] = (y << wDec) | x;
for (int y = 0; y < h; y++)
        for (int x = (y + 1) % 2; x < w; x += 2)
                if (gradient[(y << wDec) | x] >= 3)
                        listedAddr[listCountWrite++] = (y << wDec) | x;

I never tested if it's really that useful. (your gprof stats seem
pretty good, without it...) But it allows Horizontal lines to be
optimised right at the beginning. This could even be extended to have 2
seperate lists for fields with (x+y)%2 == 0 and (x+y)%2 == 1 and then
always process one of them first. But I don't know if that would really
be an optimisation. I'd do some more testing about it, but i can't
compile glob2 atm (don't have boost)... perhaps i'll have some time
this week to install boost and make more tests.

 
> The jointed gprof results:
> 
>   %   cumulative   self              self     total           
>  time   seconds   seconds    calls  ms/call  ms/call  name
> 
>  ------------------------------------- old
> ------------------------------------ 62.98      3.42     3.42
> 1011     3.38     3.38  void Map::updateGlobalGradient 61.38
> 3.29     3.29     1011     3.25     3.25  void
> Map::updateGlobalGradient 60.71      3.23     3.23     1011
> 3.19     3.19  void Map::updateGlobalGradient 66.73      3.59
> 3.59     1011     3.55     3.55  void Map::updateGlobalGradient
> 64.01      3.45     3.45     1011     3.41     3.41  void
> Map::updateGlobalGradient 69.57      3.75     3.75     1011
> 3.71     3.71  void Map::updateGlobalGradient 65.92      3.54
> 3.54     1011     3.50     3.50  void Map::updateGlobalGradient
> 63.69      3.42     3.42     1011     3.38     3.38  void
> Map::updateGlobalGradient 65.41      3.46     3.46     1011
> 3.42     3.42  void Map::updateGlobalGradient
> 
> ------------------------------------ simon
> ------------------------------------ 65.45      3.60     3.60
> 1011     3.56     3.56  void Map::updateGlobalGradient 67.40
> 3.70     3.70     1011     3.66     3.66  void
> Map::updateGlobalGradient 68.12      3.76     3.76     1011
> 3.72     3.72  void Map::updateGlobalGradient 66.07      3.70
> 3.70     1011     3.66     3.66  void Map::updateGlobalGradient
> 64.01      3.61     3.61     1011     3.57     3.57  void
> Map::updateGlobalGradient 61.34      3.38     3.38     1011
> 3.34     3.34  void Map::updateGlobalGradient 63.07      3.57
> 3.57     1011     3.53     3.53  void Map::updateGlobalGradient
> 65.03      3.70     3.70     1011     3.66     3.66  void
> Map::updateGlobalGradient 65.21      3.58     3.58     1011
> 3.54     3.54  void Map::updateGlobalGradient
> 
> ---------------------------------------- new
> ---------------------------------- 52.09      1.99     1.99
> 1011     1.97     1.97  void Map::updateGlobalGradient 51.57
> 1.97     1.97     1011     1.95     1.95  void
> Map::updateGlobalGradient 54.57      2.03     2.03     1011
> 2.01     2.01  void Map::updateGlobalGradient 52.32      2.03
> 2.03     1011     2.01     2.01  void Map::updateGlobalGradient
> 52.71      2.04     2.04     1011     2.02     2.02  void
> Map::updateGlobalGradient 52.08      2.00     2.00     1011
> 1.98     1.98  void Map::updateGlobalGradient 53.42      2.03
> 2.03     1011     2.01     2.01  void Map::updateGlobalGradient
> 52.24      1.98     1.98     1011     1.96     1.96  void
> Map::updateGlobalGradient 52.31      2.04     2.04     1011
> 2.02     2.02  void Map::updateGlobalGradient
> 
Nice to see that you have such impressive results, too ;-)

> I checked if my changes could result in wrong gradients:
> If for example the upper left and upper right field already have
> gradient values but are not marked to become active:  the change
> would cause the upper field to not get active and so the upper field
> of the upper field might not get its legitimate value.
> 
> But this is not so, because for the upper right (call it A) to have a
> gradient value and not getting actived would mean that it is not a
> resource and that there has to be a nondiagonal neighbour with two
> diagonal neighbours next to A. 
I think it is correct. At least the way I first submitted it it
produced correct gradients in all my tests.

> ps: I like Simons algorithm
Thanks, pleased to hear this. I just don't seem to find a clean
implementation for it... (e.g without this cryptic and ugly flag ;-))

Simon