[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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
address@hidden wrote:
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 @@
void Map::updateGlobalGradientSmall(Uint8 *gradient)
{
- Uint16 *listedAddr = new Uint16[size];
+ Uint16 listedAddr[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;
- size_t deltaAddrC[8];
+ size_t deltaAddrC[4];
Uint8 *addr;
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};
addr = &gradient[deltaAddrC[ci]];
side = *addr;
if (side > 0 && side < g)
@@ -2171,21 +2174,42 @@
if (g > 2)
listedAddr[listCountWrite++] =
deltaAddrC[ci];
}
+ 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++)
+ {
+ addr = &gradient[deltaAddrC[ci]];
+ side = *addr;
+ if (side > 0 && side < g)
+ {
+ *addr = g;
+ if ((g > 2) && (horizFlag & 1))
+ listedAddr[listCountWrite++] =
deltaAddrC[ci];
+ }
+ horizFlag >>= 1;
}
}
assert(listCountWrite<=size);
- delete[] listedAddr;
}
void Map::updateGlobalGradientBig(Uint8 *gradient)
{
- size_t *listedAddr = new size_t[size];
+ size_t listedAddr[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;
- size_t deltaAddrC[8];
+ size_t deltaAddrC[4];
Uint8 *addr;
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};
addr = &gradient[deltaAddrC[ci]];
side = *addr;
if (side > 0 && side < g)
@@ -2224,10 +2247,27 @@
if (g > 2)
listedAddr[listCountWrite++] =
deltaAddrC[ci];
}
+ 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++)
+ {
+ addr = &gradient[deltaAddrC[ci]];
+ side = *addr;
+ if (side > 0 && side < g)
+ {
+ *addr = g;
+ if ((g > 2) && (horizFlag & 1))
+ listedAddr[listCountWrite++] =
deltaAddrC[ci];
+ }
+ horizFlag >>= 1;
}
}
assert(listCountWrite<=size);
- delete[] listedAddr;
}
void Map::updateGlobalGradient(Uint8 *gradient)
- Re: [glob2-devel] forums! nuag eplease read thx, (continued)
- Re: [glob2-devel] forums! nuag eplease read thx, Nuage, 2005/12/28
- Re: [glob2-devel] forums! nuag eplease read thx, Munteanu Alexandru, 2005/12/28
- Re: [glob2-devel] forums! nuag eplease read thx, Kyle Lutze, 2005/12/29
- Re: [glob2-devel] forums! nuag eplease read thx, Munteanu Alexandru, 2005/12/29
- Re: [glob2-devel] forums! nuag eplease read thx, cyrille . dunant, 2005/12/28
- Re: [glob2-devel] forums! nuag eplease read thx, simon schuler, 2005/12/28
- Re: [glob2-devel] forums! nuag eplease read thx, nct, 2005/12/28
- Re: [glob2-devel] forums! nuag eplease read thx,
simon schuler <=
- Nuage plz read (was Re: [glob2-devel] forums! nuag eplease read thx), nct, 2005/12/29
- Re: Nuage plz read (was Re: [glob2-devel] forums! nuag eplease read thx), Nuage, 2005/12/29
- Re: Nuage plz read (was Re: [glob2-devel] forums! nuag eplease read thx), nct, 2005/12/29
- Re: Nuage plz read (was Re: [glob2-devel] forums! nuag eplease read thx), Nuage, 2005/12/29
- Re: [glob2-devel] forums! nuag eplease read thx, Nuage, 2005/12/29
- [glob2-devel] Simon's idea on gradiens, Nuage, 2005/12/29
- Re: [glob2-devel] Simon's idea on gradiens, simon schuler, 2005/12/30