glob2-devel
[Top][All Lists]

## Re: [glob2-devel] forums! nuag eplease read thx

 From: simon schuler Subject: Re: [glob2-devel] forums! nuag eplease read thx Date: Thu, 29 Dec 2005 14:42:27 +0100 User-agent: Mail/News 1.4 (X11/20050914)

```Hi

```
```Very interested, but could you also try to first compute using your
algorithm then using the old one? Indeed, there is a high probability the
speed difference is partially due to the gradient already being cached by
updateGlobalGradientSmallOld (thus the slowness) when
updateGlobalGradientSmall is called (thus the fastness).
```
```I tested it both ways and it's almost the same result.
I've made a patch against 0.8.17. It's attached.
```
note: i have only compile-tested it with 0.8.17 because I can't compile the whole release. But on 0.8.15 it worked perfectly.
```I hope it doesn't interfere with nuage's new optimization...

Simon

```
```--- ./src/Map.cpp.orig  2005-12-29 13:27:47.272807750 +0100
+++ ./src/Map.cpp       2005-12-29 14:34:56.980648750 +0100
@@ -2125,12 +2125,16 @@

{
-        Uint16 *listedAddr = new Uint16[size];
size_t listCountWrite = 0;

// make the first list:
for (int y = 0; y < h; y++)
-                for (int x = 0; x < w; x++)
+                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;

@@ -2149,20 +2153,19 @@

Uint8 g = gradient[(y << wDec) | x] - 1;

Uint8 side;

-                deltaAddrC[0] = (yu << wDec) | xl;
-                deltaAddrC[1] = (yu << wDec) | x ;
-                deltaAddrC[2] = (yu << wDec) | xr;
-                deltaAddrC[3] = (y  << wDec) | xr;
-                deltaAddrC[4] = (yd << wDec) | xr;
-                deltaAddrC[5] = (yd << wDec) | x ;
-                deltaAddrC[6] = (yd << wDec) | xl;
-                deltaAddrC[7] = (y  << wDec) | xl;
-                for (int ci=0; ci<8; ci++)
-                {
+               //first the diagonal squares:
+               deltaAddrC[0] = (yu << wDec) | xl;
+               deltaAddrC[1] = (yu << wDec) | xr;
+               deltaAddrC[2] = (yd << wDec) | xr;
+               deltaAddrC[3] = (yd << wDec) | xl;
+               unsigned int horizFlag = 0;
+               for (int ci = 0; ci < 4; ci++)
+               {
+                       const unsigned int diagFlags[4] = {9, 3, 6, 12};
if (side > 0 && side < g)
@@ -2171,21 +2174,42 @@
if (g > 2)
}
+                       else if (side == 0)
+                               horizFlag |= diagFlags[ci];
+               }
+                deltaAddrC[0] = (yu << wDec) | x ;
+                deltaAddrC[1] = (y  << wDec) | xr;
+                deltaAddrC[2] = (yd << wDec) | x ;
+                deltaAddrC[3] = (y  << wDec) | xl;
+                for (int ci=0; ci<4; ci++)
+                {
+                        side = *addr;
+                        if (side > 0 && side < g)
+                        {
+                                *addr = g;
+                                if ((g > 2) && (horizFlag & 1))
+                        }
+                       horizFlag >>= 1;
}
}
assert(listCountWrite<=size);
}
{
-        size_t *listedAddr = new size_t[size];
size_t listCountWrite = 0;

// make the first list:
-        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;
+       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;

size_t listCountRead = 0;
while (listCountRead < listCountWrite)
@@ -2202,20 +2226,19 @@

Uint8 g = gradient[(y << wDec) | x] - 1;

Uint8 side;
-
-                deltaAddrC[0] = (yu << wDec) | xl;
-                deltaAddrC[1] = (yu << wDec) | x ;
-                deltaAddrC[2] = (yu << wDec) | xr;
-                deltaAddrC[3] = (y  << wDec) | xr;
-                deltaAddrC[4] = (yd << wDec) | xr;
-                deltaAddrC[5] = (yd << wDec) | x ;
-                deltaAddrC[6] = (yd << wDec) | xl;
-                deltaAddrC[7] = (y  << wDec) | xl;
-                for (int ci=0; ci<8; ci++)
-                {
+
+               //first the diagonal squares
+               deltaAddrC[0] = (yu << wDec) | xl;
+               deltaAddrC[1] = (yu << wDec) | xr;
+               deltaAddrC[2] = (yd << wDec) | xr;
+               deltaAddrC[3] = (yd << wDec) | xl;
+               unsigned int horizFlag = 0;
+               for (int ci = 0; ci < 4; ci++)
+               {
+                       const unsigned int diagFlags[4] = {9, 3, 6, 12};
if (side > 0 && side < g)
@@ -2224,10 +2247,27 @@
if (g > 2)
}
+                       else if (side == 0)
+                               horizFlag |= diagFlags[ci];
+               }
+                deltaAddrC[0] = (yu << wDec) | x ;
+                deltaAddrC[1] = (y  << wDec) | xr;
+                deltaAddrC[2] = (yd << wDec) | x ;
+                deltaAddrC[3] = (y  << wDec) | xl;
+                for (int ci=0; ci<4; ci++)
+                {
+                        side = *addr;
+                        if (side > 0 && side < g)
+                        {
+                                *addr = g;
+                                if ((g > 2) && (horizFlag & 1))
+                        }
+                       horizFlag >>= 1;
}
}
assert(listCountWrite<=size);