Re: [glob2-devel] gradient improvement

[Kai Antweiler]

>> 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.

Are you sure?  I don't see this.  
If I draw a horizontal line, no matter how distorted the order is,
if I have enough steps of undisturbed propagation the line will be
in a beneficial 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.

At least for the forbidden gradient this should make a difference,
since there most fields are resources.


>> 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.

I guess the way I proposed will be nice and easy to implement.
Of course vertical wave fronts are not regarded at all.
Would your implementation have been ugly, if you would have omitted
vertical wave fronts?


>> 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.

I once changed the:

if (g <= 2)
   continue;

to:

if (g <= 2)
   return;

and got different gradients.
Maybe I had changed some other thing too.
(but I don't think so.)

-- 
Kai Antweiler