Re: [glob2-devel] gradient improvement

[Simon Schuler]

Am Tue, 28 Mar 2006 13:49:08 +0200
schrieb Kai Antweiler:

> > Sorry, I did miss it, can you tell me exactly how to fix it ? Or
> > fix it directly.
> 
> I attach the patch.

Well actually you could just remove my version. With this fix now both
versions are the same.
> 
> >> The algorithm depends on the order in which
> >> fields that need to be processed are listed.  
> 
> I forgot that Simon's algorithm already "repairs" the local order in
> which the fields will be listed by inserting the diagonal neighbours
> before the others.

Yes, that's why I only separated even and odd fields at the beginning.
But once a line is in a bad order it won't be repaired. (only the start
of it) The bad part remains at the end of the line. Perhaps lines never
get in such a bad order...

> But I have two ideas which might use the cache better:
> 
> 1. When initializing the array listedAddr, omit the fields
> which have a right and left neighbour of same or higher gradient
> value, if these will be put in the list.  This uses only information
> which just was processed or will be in the next step.
> Since resources tend to cluster, also checking for upper and lower
> values wouldn't gain much.
> (The idea is that every neighbour of the omited field, is also
> neighbouring one of the other two fields.)
I don't expect this to make a very big difference because it just
removes some fields at the start.
> 
> 2. In updateGlobalGradient:  check if the next field in listedAddr
> is my right neighbour.  If it is, check if the next one is its right
> reighbour. And so on ...
> And then process that whole part of the line.
> You also would have to check, if the right neighbour has the same
> gradient value as you.

This is close to another idea I had. It was based on the observation
that you only have horizontal and vertical wave fronts. So my other
algorithm stores the wave fronts instead of fields. It has the
advantage that you don't have to check the fields around the one you
are currently updating. The next generation wave fronts are derived
from the obstacles in the current wave front: (obstacles more than 2
fields wide cause the wave to split and there is breaking at the ends
of the wavefront)
I've tried to implement this algorithm. It resulted in very ugly code,
but it produced correct gradients. The speedup of this algorithm
compared to the simple one was between 0% and 40%, depending on the
map. (compiled with -O3, measured with gprof)
But it is far too complicated to be useful.
> 
> Why is it possible to have so different gradient values in field which
> are in listedAddr?
> I would expect only two values:
> the present one and the present one minus one
erm, I'd expect that too.