Original Post
🔒 Locked
Code Optimization
Advertisement
Yeah, I''m sure it''s that function. I''ve used a profiler on it and that function is pretty much eating 100% of my cpu time.
What I''m doing is generating alpha textures for terrain texture splatting (ala. Charles Bloom) (www.cbloom.com).
How do you post code in here so that it shows up as formatted code?
is it
What I''m doing is generating alpha textures for terrain texture splatting (ala. Charles Bloom) (www.cbloom.com).
How do you post code in here so that it shows up as formatted code?
is it
i++ ?
Sorry..... didn''t think about the faq.... my bad.
Basically this method is to generate an alpha map to use in terrain splatting.
m_mapSplat is a 256x256x8bit array that tells me what images go where.
my terrain is divided into quad-trees so pLeaf->m_pParent->m_iMinX and m_iMinZ are the start of my quad-tree and thus serve as a lookup into the m_mapSplat to find out what section I''m generating it for.
I generate a 64x64x16 (4444) format texture (I''ve removed writing to a d3d texture with the lock/unlock and use an array instead for speed testing). I only have to write to the uppermost 4 bits since I use the alpha of it.
for each texel of my alpha map that I''m generating, I sample the 9 surrounding types (from m_mapSplat) to see if they are equal to the splat I''m laying down. This is so that I can generate correct fade outs between layers.
FloatToInt is a method to turn a float to an int (duh) without all the c++ overhead. It''s a pretty fast function that I got from Game Programming Gems 2.
if anyone can give me some pointers here or there as to maybe what I could do to speed it up but still keep all it''s functionality, It''d be greatly appreciated.
Thanks fellas (and ladies, if there are any in here - send a pic, heheheheh).
// our testing matrix of values
int GiMatrix[18] = { -1, -1, -1, 0, -1, 1,
0, -1, 0, 0, 0, 1,
1, -1, 1, 0, 1, 1 };
float GfMatrix[18] = { -1.0f, -1.0f, -1.0f, 0.0f, -1.0f, 1.0f,
0.0f, -1.0f, 0.0f, 0.0f, 0.0f, 1.0f,
1.0f, -1.0f, 1.0f, 0.0f, 1.0f, 1.0f };
// constructs an alpha map for the quad leaf and splat
int Terrain::CreateSplatAlpha(QuadLeaf* pLeaf,
int iSplatIndex,
LPDIRECT3DTEXTURE8 pTexture)
{
assert(pLeaf != NULL);
assert(pTexture != NULL);
assert(m_mapSplat.IsValid());
// lock the texture for writing the alpha
D3DLOCKED_RECT lr;
int x, y;
int iLookX, iLookY;
int iSplatPos, iRealPos;
int i, a, b;
float weight, tweight;
float d = 1.0f / (1.75f * 1.75f); // maximum falloff distance
float px = -0.25f, py = -0.25f;
float dx, dy, q;
WORD* pPixels;
WORD pwTemp[64*64];
lr.pBits = (void*)pwTemp;
lr.Pitch = 128;
// generate the 64x64 alpha splat
for(y = 0; y < m_iCySplat; y++) {
// change our lookup value
iLookY = pLeaf->m_pParent->m_iMinZ + (y >> 1);
pPixels = (WORD*)((BYTE*)lr.pBits + (y * lr.Pitch));
iSplatPos = iLookY * m_mapSplat.m_iCx;
for(x = 0; x < m_iCxSplat; x++) {
// change our lookup value
weight = 0.0f;
tweight = 0.0f;
iLookX = pLeaf->m_pParent->m_iMinX + (x >> 1);
// check surrounding 9 places
for(i = 0; i < 9; i++) {
a = GiMatrix[i<<1];
b = GiMatrix[(i<<1)+1];
// make sure values in range
if((iLookX+b < 0) || (iLookY+a < 0) ||
(iLookX+b >= m_mapSplat.m_iCx) || (iLookY+a >= m_mapSplat.m_iCy))
continue;
dy = GfMatrix[(i<<1)] - py;
dx = GfMatrix[(i<<1)+1] - px;
// q = ClampFloatToZero(1.0f - (dx * dx + dy * dy) * d);
q = 1.0f - (dx * dx + dy * dy) * d;
if(q < 0.0f) q = 0.0f;
tweight += q;
iRealPos = iSplatPos + (a * m_mapSplat.m_iCx) + iLookX + b;
if(m_mapSplat.m_pData[iRealPos] == iSplatIndex)
weight += q;
}
// normalize the weight
weight = weight * tweight;//15.0f * weight / tweight;
// convert to an integer value
*pPixels++ = FloatToInt(weight) << 12;
// adjust the pixel location
px *= -1.0f;
}
// adjust pixel location
py *= -1.0f;
}
return(0);
}
Basically this method is to generate an alpha map to use in terrain splatting.
m_mapSplat is a 256x256x8bit array that tells me what images go where.
my terrain is divided into quad-trees so pLeaf->m_pParent->m_iMinX and m_iMinZ are the start of my quad-tree and thus serve as a lookup into the m_mapSplat to find out what section I''m generating it for.
I generate a 64x64x16 (4444) format texture (I''ve removed writing to a d3d texture with the lock/unlock and use an array instead for speed testing). I only have to write to the uppermost 4 bits since I use the alpha of it.
for each texel of my alpha map that I''m generating, I sample the 9 surrounding types (from m_mapSplat) to see if they are equal to the splat I''m laying down. This is so that I can generate correct fade outs between layers.
FloatToInt is a method to turn a float to an int (duh) without all the c++ overhead. It''s a pretty fast function that I got from Game Programming Gems 2.
if anyone can give me some pointers here or there as to maybe what I could do to speed it up but still keep all it''s functionality, It''d be greatly appreciated.
Thanks fellas (and ladies, if there are any in here - send a pic, heheheheh).
sorry, mistake in the code... this is the REAL code... but still read the comments from before from me...
// our testing matrix of values
int GiMatrix[18] = { -1, -1, -1, 0, -1, 1,
0, -1, 0, 0, 0, 1,
1, -1, 1, 0, 1, 1 };
float GfMatrix[18] = { -1.0f, -1.0f, -1.0f, 0.0f, -1.0f, 1.0f,
0.0f, -1.0f, 0.0f, 0.0f, 0.0f, 1.0f,
1.0f, -1.0f, 1.0f, 0.0f, 1.0f, 1.0f };
// constructs an alpha map for the quad leaf and splat
int Terrain::CreateSplatAlpha(QuadLeaf* pLeaf,
int iSplatIndex,
LPDIRECT3DTEXTURE8 pTexture)
{
assert(pLeaf != NULL);
assert(pTexture != NULL);
assert(m_mapSplat.IsValid());
// lock the texture for writing the alpha
D3DLOCKED_RECT lr;
// if(pTexture->LockRect(0, &lr, NULL, 0) != D3D_OK)
// return(1);
int x, y;
int iLookX, iLookY;
int iSplatPos, iRealPos;
int i, a, b;
float weight, tweight;
float d = 1.0f / (1.75f * 1.75f); // maximum falloff distance
float px = -0.25f, py = -0.25f;
float dx, dy, q;
WORD* pPixels;
WORD pwTemp[64*64];
lr.pBits = (void*)pwTemp;
lr.Pitch = 128;
// generate the 64x64 alpha splat
for(y = 0; y < m_iCySplat; y++) {
// change our lookup value
iLookY = pLeaf->m_pParent->m_iMinZ + (y >> 1);
pPixels = (WORD*)((BYTE*)lr.pBits + (y * lr.Pitch));
iSplatPos = iLookY * m_mapSplat.m_iCx;
for(x = 0; x < m_iCxSplat; x++) {
// change our lookup value
weight = 0.0f;
tweight = 0.0f;
iLookX = pLeaf->m_pParent->m_iMinX + (x >> 1);
// check surrounding 9 places
for(i = 0; i < 9; i++) {
a = GiMatrix[i<<1];
b = GiMatrix[(i<<1)+1];
// make sure values in range
if((iLookX+b < 0) || (iLookY+a < 0) ||
(iLookX+b >= m_mapSplat.m_iCx) || (iLookY+a >= m_mapSplat.m_iCy))
continue;
dy = GfMatrix[(i<<1)] - py;
dx = GfMatrix[(i<<1)+1] - px;
// q = ClampFloatToZero(1.0f - (dx * dx + dy * dy) * d);
q = 1.0f - (dx * dx + dy * dy) * d;
if(q < 0.0f) q = 0.0f;
tweight += q;
iRealPos = iSplatPos + (a * m_mapSplat.m_iCx) + iLookX + b;
if(m_mapSplat.m_pData[iRealPos] == iSplatIndex)
weight += q;
}
// normalize the weight
weight = 15.0f * weight / tweight;
// convert to an integer value
*pPixels++ = FloatToInt(weight) << 12;
// adjust the pixel location
px *= -1.0f;
}
// adjust pixel location
py *= -1.0f;
}
// unlock it now that we''re done
// pTexture->UnlockRect(0);
return(0);
}
a) Break down your function into several functions and profile the parts separately (it''ll be slower than the with a single function, but it''ll give you a better image of the situation).
b) When trying to hand-optimize, examine the assembly output to see if you''re not being redundant with compiler optimizations (KNOW YOUR COMPILER!). Compilers have become decently good at optimizing code. Obfuscating it doesn''t necessarily make it go faster (bitshift vs. multiplication by two, comparisons to zero, strength reduction ...)
c) transform conditional statements into arithmetic operations.
could become (though I don''t know if the logical & has issues with floats, so this specific example might be wrong... a reinterpret_cast() is probably appropriate here.)
const unsigned long mask[2] = { 0L, ~(0L) };
const int test = m_mapSplat.m_pData[iRealPos] == iSplatIndex;
weight += q & mask[test]
d) Use preincrement
e) Strength reduction : turn multiplications into additions :
could become
f) Remember that 2D arrays still are 1D arrays in fact : the ''next'' element is always current+1, regardless of rows & columns (computations for pPixel ?)
g) table lookups (see c), but you already know that (Gi, Gf)
h) make local constant copies of variables that don''t change (e.g. *(pLeaf->m_pParent))
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
b) When trying to hand-optimize, examine the assembly output to see if you''re not being redundant with compiler optimizations (KNOW YOUR COMPILER!). Compilers have become decently good at optimizing code. Obfuscating it doesn''t necessarily make it go faster (bitshift vs. multiplication by two, comparisons to zero, strength reduction ...)
c) transform conditional statements into arithmetic operations.
if(m_mapSplat.m_pData[iRealPos] == iSplatIndex)
weight += q;
could become (though I don''t know if the logical & has issues with floats, so this specific example might be wrong... a reinterpret_cast
const unsigned long mask[2] = { 0L, ~(0L) };
const int test = m_mapSplat.m_pData[iRealPos] == iSplatIndex;
weight += q & mask[test]
d) Use preincrement
e) Strength reduction : turn multiplications into additions :
for(y = 0; y < m_iCySplat; y++)
pPixels = (WORD*)((BYTE*)lr.pBits + (y * lr.Pitch));
could become
for(y = 0, z = 0; y < m_iCySplat; ++y, z+= lr.Pitch)
pPixels = (WORD*)((BYTE*)lr.pBits + z);
f) Remember that 2D arrays still are 1D arrays in fact : the ''next'' element is always current+1, regardless of rows & columns (computations for pPixel ?)
g) table lookups (see c), but you already know that (Gi, Gf)
h) make local constant copies of variables that don''t change (e.g. *(pLeaf->m_pParent))
Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
Thanks for the reply. I was actually optimizing it before I read your post. Here is what I done before I read it. I''m gonna go back over it now and see what else I can eliminate or make faster.
The first version produced around 1.8million texels per second. This new version produces 3.35million texels per second. Those were timings on an original Celeron 850 (actually, a 550 overclocked but that''s besides the point).
So this new version is better but still not what I want. I''m actually hoping to get a lot more than that yet. If my calculation is right, that works out to around 250 cycles/pixel which is pretty high still. It''d be nice to get that down around 50-100cycles/pixel if possible. So if anyone wants to help a little, I''d still really appreciate it.
// constructs an alpha map for the quad leaf and splat
int Terrain::CreateSplatAlpha(QuadLeaf* pLeaf,
int iSplatIndex,
LPDIRECT3DTEXTURE8 pTexture)
{
assert(pLeaf != NULL);
assert(pTexture != NULL);
assert(m_mapSplat.IsValid());
// lock the texture for writing the alpha
D3DLOCKED_RECT lr;
if(pTexture->LockRect(0, &lr, NULL, 0) != D3D_OK)
return(1);
int x, y;
int iLookX, iLookY;
int iSplatPos, iSplatOffset;
int a, b, iAddWeights;
float weight[4], tweight[4];
float dx[2], dy[2], q[4];
float fa, fb;
DWORD* pPixels, *pSurface;
// this is our falloff normalizer
const float d = 1.0f / (1.75f * 1.75f); // maximum falloff distance is 1.75 texels
// our initial surface pointer
pSurface = (DWORD*)((BYTE*)lr.pBits);
// initial Y lookup value
iLookY = pLeaf->m_pParent->m_iMinZ;
// and overall initial lookup value
iSplatPos = iLookY * m_mapSplat.m_iCx;
// generate the 64x64 alpha splat
for(y = 0; y < m_iCySplat>>1; ++y, ++iLookY) {
// change our current pixel pointer
pPixels = pSurface;
// set our x lookup value
iLookX = pLeaf->m_pParent->m_iMinX;
// process this row, unrolled to do 2x2 pixels each iteration
for(x = 0; x < m_iCxSplat>>1; ++x, ++iLookX) {
// change our lookup value
weight[0] = weight[1] = weight[2] = weight[3] = 0;
tweight[0] = tweight[1] = tweight[2] = tweight[3] = 0;
// check surrounding 9 places
for(a = -1, fa = -1.0f; a < 2; ++a, fa+=1.0f) {
// make sure we don''t sample outside the dimensions
// of the m_mapSplat[0] surface
if( (iLookY+a < 0) || (iLookY+a >= m_mapSplat.m_iCy) )
continue;
// get the offset
iSplatOffset = iSplatPos + (a * m_mapSplat.m_iCx) + iLookX;
for(b = -1, fb = -1.0f; b < 2; ++b,fb+=1.0f) {
// again, don''t sample outside
if( (iLookX+b < 0) || (iLookX+b >= m_mapSplat.m_iCx) )
continue;
// do we need to add weights to these pixels for this spot?
iAddWeights = (m_mapSplat.m_pData[iSplatOffset+b] == iSplatIndex);
// 4 distances
dy[0] = fa + 0.25;
dy[1] = fa - 0.25;
dx[0] = fb + 0.25;
dx[1] = fb - 0.25;
// and square them
dx[0] *= dx[0];
dx[1] *= dx[1];
dy[0] *= dy[0];
dy[1] *= dy[1];
// now find the distances between and clamp to 0
q[0] = 1.0f - (dx[0] + dy[0]) * d;
if(q[0] < 0.0f)
q[0] = 0.0f;
tweight[0] += q[0];
q[1] = 1.0f - (dx[1] + dy[0]) * d;
if(q[1] < 0.0f)
q[1] = 0.0f;
tweight[1] += q[1];
q[2] = 1.0f - (dx[0] + dy[1]) * d;
if(q[2] < 0.0f)
q[2] = 0.0f;
tweight[2] += q[2];
q[3] = 1.0f - (dx[1] + dy[1]) * d;
if(q[3] < 0.0f)
q[3] = 0.0f;
tweight[3] += q[3];
// and if we need to add the weights, add them
if(iAddWeights) {
weight[0] += q[0];
weight[1] += q[1];
weight[2] += q[2];
weight[3] += q[3];
}
}
}
// invert
/* 15 << 12 = 61440 */
// since we need alpha values in the range of 0 to 15 (4-bit alpha)
// and we need to shift this to the left by 12 bits, we may as well
// expand it here i guess. hence 61440.0
tweight[0] = 61440.0 / tweight[0];
tweight[1] = 61440.0 / tweight[1];
tweight[2] = 61440.0 / tweight[2];
tweight[3] = 61440.0 / tweight[3];
// normalize the weights
weight[0] *= tweight[0];
weight[1] *= tweight[1];
weight[2] *= tweight[2];
weight[3] *= tweight[3];
// convert to an integer value (writing 2 pixels at once)
*pPixels = (FloatToInt(weight[0])<<16) | FloatToInt(weight[1]);
// move to next row in image
pPixels += (lr.Pitch>>2);
// write the next two pixels
*pPixels++ = (FloatToInt(weight[2])<<16) | FloatToInt(weight[3]);
// move the row backwards
pPixels -= (lr.Pitch>>2);
}
// change surface pointer to skip a row and start on the next
pSurface += (lr.Pitch>>1);
// and move our mapSplat index
iSplatPos += m_mapSplat.m_iCx;
}
// unlock it now that we''re done
pTexture->UnlockRect(0);
return(0);
}
The first version produced around 1.8million texels per second. This new version produces 3.35million texels per second. Those were timings on an original Celeron 850 (actually, a 550 overclocked but that''s besides the point).
So this new version is better but still not what I want. I''m actually hoping to get a lot more than that yet. If my calculation is right, that works out to around 250 cycles/pixel which is pretty high still. It''d be nice to get that down around 50-100cycles/pixel if possible. So if anyone wants to help a little, I''d still really appreciate it.
Some quick suggestions:
1) replace your bounds checking code with:
if((unsigned)(iLook?+?) >= m_mapSplat.m_iC?)
continue;
2) replace your clamp-to-zero with
MUCH faster, but it requires a PPro or above.
3) this is just screaming for SIMD
1) replace your bounds checking code with:
if((unsigned)(iLook?+?) >= m_mapSplat.m_iC?)
continue;
2) replace your clamp-to-zero with
> eax - q
> edx - 0
test eax, 0x80000000 ; test sign bit - IEEE32 specific
cmovnz eax, edx
MUCH faster, but it requires a PPro or above.
3) this is just screaming for SIMD
tweight[0] = 61440.0 / tweight[0];
tweight[1] = 61440.0 / tweight[1];
tweight[2] = 61440.0 / tweight[2];
tweight[3] = 61440.0 / tweight[3];
// normalize the weights
weight[0] *= tweight[0];
weight[1] *= tweight[1];
weight[2] *= tweight[2];
weight[3] *= tweight[3];
=>
// normalize the weights
weight[0] *= 61440.0f / tweight[0];
weight[1] *= 61440.0f / tweight[1];
weight[2] *= 61440.0f / tweight[2];
weight[3] *= 61440.0f / tweight[3];
(note the f's, otherwise compiler might have to convert tweight[] to double during calculation)
Also
// do we need to add weights to these pixels for this spot?
iAddWeights = (m_mapSplat.m_pData[iSplatOffset+b] == iSplatIndex);
//...
if(iAddWeights) {
weight[0] += q[0];
weight[1] += q[1];
weight[2] += q[2];
weight[3] += q[3];
}
=>
if(m_mapSplat.m_pData[iSplatOffset+b] == iSplatIndex) {
weight[0] += q[0];
weight[1] += q[1];
weight[2] += q[2];
weight[3] += q[3];
}
[edited by - civguy on October 7, 2002 8:33:40 AM]
One more:
=>
Compiler might convert them first to doubles, then back to floats.
But here
you could have (and should, IMO, to add clarity)
Because 0 is a constant and will be converted to the ''more complex type'' (i.e. float) during compilation.
// 4 distances
dy[0] = fa + 0.25;
dy[1] = fa - 0.25;
dx[0] = fb + 0.25;
dx[1] = fb - 0.25;
=>
// 4 distances
dy[0] = fa + 0.25f;
dy[1] = fa - 0.25f;
dx[0] = fb + 0.25f;
dx[1] = fb - 0.25f;
Compiler might convert them first to doubles, then back to floats.
But here
if(q[0] < 0.0f)
q[0] = 0.0f;
you could have (and should, IMO, to add clarity)
if(q[0] < 0)
q[0] = 0;
Because 0 is a constant and will be converted to the ''more complex type'' (i.e. float) during compilation.
Ha, I''m not stopping yet.
Evil useless mul. Look at fruny''s point e)
Also:
=>
=>
iSplatOffset = iSplatPos + (a * m_mapSplat.m_iCx) + iLookX;
Evil useless mul. Look at fruny''s point e)
Also:
for(b = -1, fb = -1.0f; b < 2; ++b,fb+=1.0f) {
dx[0] = fb + 0.25f;
dx[1] = fb - 0.25f;
dx[0] *= dx[0];
dx[1] *= dx[1];
}
=>
for(b = -1; b < 2; ++b) {
dx[0] = fb1squared[b+1];
dx[1] = fb2squared[b+1];
}
=>
for(b = -1, float* fb1it = fb1squared, float* fb2it = fb2squared; b < 2; ++b, ++fb1it, ++fb2it) {
dx[0] = *fb1it;
dx[1] = *fb2it;
}
Wow, thanks for replies. I''m gonna start to change it now and see. I''ll let you know of the speed.
By the way, I''ve already changed my clamp to 0 using a method I got from Game Programming Gems 2. Here''s the method:
It''s a neat little trick I must say. Mine is a bit more unreadable than theirs (they use a union that contains a float and an int for easy conversion between the two). It seemed to help quite a bit.
I already have it up to 3.9million texels/sec, up from my original 1.8million.
By the way, I''ve already changed my clamp to 0 using a method I got from Game Programming Gems 2. Here''s the method:
inline float ClampFloatToZero(float f)
{
int s = (*(int*)&f) & (~((*(int*)&f) >> 31));
return(*(float*)&s);
}
It''s a neat little trick I must say. Mine is a bit more unreadable than theirs (they use a union that contains a float and an int for easy conversion between the two). It seemed to help quite a bit.
I already have it up to 3.9million texels/sec, up from my original 1.8million.
Okay, I took all your advice and got it working much faster. He''s the latest version:
This version now runs at 6.4Mtexels/sec, compared to the original at 1.8Mtexels/sec. That''s quite an improvement.
I''d like to send out props to CivGuy, Jan Wassenberg, and Fruny for the great tips. I certainly probably wouldn''t have thought about half of them. I think that this is a fairly optimized C++ loop to do the work that I''m doing. I''d say that I''m approaching the upper bounds of the speed in C++ for this method.
I think for my final version for in game, I will probably just pre-generate them at run-time and store them in memory (or HD). Overall, I think it''s still a bit slow for real-time. But thanks all.
// a special lookup table to remove mults
float G_TexelLut[6] = {
/* (-1.0 + 0.25)^2 / (1.75^2) -> 0.5625 / 3.0625 */0.18367346938775510204081632653061f,
/* ( 0.0 + 0.25)^2 / (1.75^2) -> 0.0625 / 3.0625 */0.020408163265306122448979591836735f,
/* ( 1.0 + 0.25)^2 / (1.75^2) -> 1.5625 / 3.0625 */0.51020408163265306122448979591837f,
/* (-1.0 - 0.25)^2 / (1.75^2) -> 1.5625 / 3.0625 */0.51020408163265306122448979591837f,
/* ( 0.0 - 0.25)^2 / (1.75^2) -> 0.0625 / 3.0625 */0.020408163265306122448979591836735f,
/* ( 1.0 - 0.25)^2 / (1.75^2) -> 0.5625 / 3.0625 */0.18367346938775510204081632653061f
};
// constructs an alpha map for the quad leaf and splat
// texels/sec measured on a P2-Celeron 850Mhz
// version 1: 1.80 million texels/sec
// version 2: 3.20 million texels/sec
// version 3: 3.35 million texels/sec
// version 4: 3.90 million texels/sec
int Terrain::CreateSplatAlpha(QuadLeaf* pLeaf,
int iSplatIndex,
LPDIRECT3DTEXTURE8 pTexture)
{
assert(pLeaf != NULL);
assert(pTexture != NULL);
assert(m_mapSplat.IsValid());
int x, y;
int iLookX, iLookY;
int iSplatPos, iSplatOffset;
int a, b;
float fWeight[4], fTotal[4], q[4];
DWORD *pPixels, *pSurface;
// float pointer for the lookup table
float *pDx0, *pDx1, *pDy0, *pDy1;
// unchangings
int iMinX = pLeaf->m_pParent->m_iMinX;
int iMinZ = pLeaf->m_pParent->m_iMinZ;
int iPitch = m_mapSplat.m_iCx;
// lock the texture for writing the alpha
D3DLOCKED_RECT lr;
if(pTexture->LockRect(0, &lr, NULL, 0) != D3D_OK)
return(1);
// our initial surface pointer
pSurface = (DWORD*)((BYTE*)lr.pBits);
// initial Y lookup value
iLookY = iMinZ;
// and overall initial lookup value
iSplatPos = iLookY * iPitch;
// generate the 64x64 alpha splat
for(y = 0; y < m_iCySplat>>1; ++y, ++iLookY) {
// change our current pixel pointer
pPixels = pSurface;
// set our x lookup value
iLookX = iMinX;
// process this row, unrolled to do 2x2 pixels each iteration
for(x = 0; x < m_iCxSplat>>1; ++x, ++iLookX, ++iSplatOffset) {
// change our lookup value
fWeight[0] = fWeight[1] = fWeight[2] = fWeight[3] = 0;
fTotal[0] = fTotal[1] = fTotal[2] = fTotal[3] = 0;
// set the offset
iSplatOffset = iSplatPos - iPitch + iLookX;
// set pDy? pointers
pDy0 = &G_TexelLut[0];
pDy1 = &G_TexelLut[3];
// check surrounding 9 places
for(a = -1; a < 2; ++a, ++pDy0, ++pDy1, iSplatOffset += iPitch) {
// make sure we don''t sample outside the dimensions
// of the m_mapSplat[] surface
if((unsigned)(iLookY+a) >= iPitch)
continue;
// set pDx? pointers
pDx0 = &G_TexelLut[0];
pDx1 = &G_TexelLut[3];
// loop through this row of 3
for(b = -1; b < 2; ++b, ++pDx0, ++pDx1) {
// again, don''t sample outside
if((unsigned)(iLookX+b) >= iPitch)
continue;
// lut to find the 4 distances
q[0] = ClampFloatToZero(1.0f - (*pDx0 + *pDy0));
q[1] = ClampFloatToZero(1.0f - (*pDx1 + *pDy0));
q[2] = ClampFloatToZero(1.0f - (*pDx0 + *pDy1));
q[3] = ClampFloatToZero(1.0f - (*pDx1 + *pDy1));
// add up the total fWeights
fTotal[0] += q[0];
fTotal[1] += q[1];
fTotal[2] += q[2];
fTotal[3] += q[3];
// don''t add the fWeights if this isn''t the right splat
if(!(m_mapSplat.m_pData[iSplatOffset+b] == iSplatIndex))
continue;
// and add the splat fWeights
fWeight[0] += q[0];
fWeight[1] += q[1];
fWeight[2] += q[2];
fWeight[3] += q[3];
}
}
// invert
/* 15 << 12 = 61440 */
// since we need alpha values in the range of 0 to 15 (4-bit alpha)
// and we need to shift this to the left by 12 bits, we may as well
// expand it here i guess. hence 61440.0. Now normalize...
fWeight[0] *= 61440.0f / fTotal[0];
fWeight[1] *= 61440.0f / fTotal[1];
fWeight[2] *= 61440.0f / fTotal[2];
fWeight[3] *= 61440.0f / fTotal[3];
// convert to an integer value (writing 2 pixels at once)
*pPixels = (FloatToInt(fWeight[0])<<16) | FloatToInt(fWeight[1]);
// move to next row in image
pPixels += (lr.Pitch>>2);
// write the next two pixels
*pPixels = (FloatToInt(fWeight[2])<<16) | FloatToInt(fWeight[3]);
// move the row backwards
pPixels -= (lr.Pitch>>2)-1;
}
// change surface pointer to skip a row and start on the next
pSurface += (lr.Pitch>>1);
// and move our mapSplat index
iSplatPos += iPitch;
}
// unlock it now that we''re done
pTexture->UnlockRect(0);
return(0);
}
This version now runs at 6.4Mtexels/sec, compared to the original at 1.8Mtexels/sec. That''s quite an improvement.
I''d like to send out props to CivGuy, Jan Wassenberg, and Fruny for the great tips. I certainly probably wouldn''t have thought about half of them. I think that this is a fairly optimized C++ loop to do the work that I''m doing. I''d say that I''m approaching the upper bounds of the speed in C++ for this method.
I think for my final version for in game, I will probably just pre-generate them at run-time and store them in memory (or HD). Overall, I think it''s still a bit slow for real-time. But thanks all.
Now that I saw the current version, I saw some new room for quite a big speed improvement (I''ve ripped away all the ''useless'' lines to show what you must do).
=>
Gone are the slow ClampFloatToZeros, many of the adds etc, all put to the LUTs. The innermost loop looks pretty simple now :D (surely there has to be the if-clauses and fWeight-additions, but still)..
// set pDy? pointers
pDy0 = &G_TexelLut[0];
pDy1 = &G_TexelLut[3];
// check surrounding 9 places
for(a = -1; a < 2; ++a, ++pDy0, ++pDy1, iSplatOffset += iPitch) {
pDx0 = &G_TexelLut[0];
pDx1 = &G_TexelLut[3];
for(b = -1; b < 2; ++b, ++pDx0, ++pDx1) {
q[0] = ClampFloatToZero(1.0f - (*pDx0 + *pDy0));
q[1] = ClampFloatToZero(1.0f - (*pDx1 + *pDy0));
q[2] = ClampFloatToZero(1.0f - (*pDx0 + *pDy1));
q[3] = ClampFloatToZero(1.0f - (*pDx1 + *pDy1));
fTotal[0] += q[0];
fTotal[1] += q[1];
fTotal[2] += q[2];
fTotal[3] += q[3];
}
}
=>
//G_TexelLut?[]-arrays contain 9 elements each, one for every place you''re iterating
pD0 = &G_TexelLut1[0];
pD1 = &G_TexelLut2[0];
pD2 = &G_TexelLut3[0];
pD3 = &G_TexelLut4[0];
// check surrounding 9 places
for(a = -1; a < 2; ++a, iSplatOffset += iPitch) {
for(b = -1; b < 2; ++b, ++pD0, ++pD1, ++pD2, ++pD3) {
fTotal[0] += *pD0;
fTotal[1] += *pD1;
fTotal[2] += *pD2;
fTotal[3] += *pD3;
}
}
Gone are the slow ClampFloatToZeros, many of the adds etc, all put to the LUTs. The innermost loop looks pretty simple now :D (surely there has to be the if-clauses and fWeight-additions, but still)..
yeah, that''s a good optimization. Another one I got from someone on FlipCode was to make a LUT for the whole loop inside x. It just compares the same 9 spots for a given texel... that could be made into a 512 LUT that would contain all the divides etc... the only problem is getting it to work with the edges... once I figure that out, I may be able to make a LUT for the while for(x) loop. That would be sweetness indeed.
Hey, hey! Got it pretty damn optimized now. Moved all that inner stuff into a look-up table. I''m now 1434% faster than my original method! So needless to say I''m pretty happy. On a GeForce4 Ti with a P4-2.4, I can get terrain texture splatting running real-time generating every splat for every leaf visible every frame. That''s not my final intention, but it''s cool nonetheless.
So here''s my new code...
I got one weird thing tho... I tried to remove the if() statements in my inner loop and used an AND statement to mask between 0 and 1. It actually ran slower both on a P2 and P4. This I found very weird since I thought that conditionals were bad in an inner loop. I timed it over and over but it still is faster to use the conditionals. Can anyone shed any light on this? I remmed out the code that removes the conditional but it''s still there in comments.
Anyway, thanks to everyone who helped.
So here''s my new code...
// a special lookup table to remove mults
float G_TexelLut[6] = {
/* (-1.0 + 0.25)^2 / (1.75^2) -> 0.5625 / 3.0625 */0.18367346938775510204081632653061f,
/* ( 0.0 + 0.25)^2 / (1.75^2) -> 0.0625 / 3.0625 */0.020408163265306122448979591836735f,
/* ( 1.0 + 0.25)^2 / (1.75^2) -> 1.5625 / 3.0625 */0.51020408163265306122448979591837f,
/* (-1.0 - 0.25)^2 / (1.75^2) -> 1.5625 / 3.0625 */0.51020408163265306122448979591837f,
/* ( 0.0 - 0.25)^2 / (1.75^2) -> 0.0625 / 3.0625 */0.020408163265306122448979591836735f,
/* ( 1.0 - 0.25)^2 / (1.75^2) -> 0.5625 / 3.0625 */0.18367346938775510204081632653061f
};
// a special weight lookup table
DWORD G_WeightLut[512];
// Builds the weighted LUT for the CreateSplatAlpha() method
int Terrain::BuildWeightLut()
{
// float pointer for the lookup table
float *pDx0, *pDx1, *pDy0, *pDy1;
// weights, totals and temps
float fWeight[4], fTotal[4], fQ[4];
// 512 possible values to choose from
for(int i = 0; i < 512; ++i) {
// set pDy? pointers
pDy0 = &G_TexelLut[0];
pDy1 = &G_TexelLut[3];
// reset weights
for(int z = 0; z < 4; ++z) {
fWeight[z] = 0;
fTotal[z] = 0;
}
// each one samples 9 regions
for(int y = 0; y < 3; ++y, ++pDy0, ++pDy1) {
// set pDx? pointers
pDx0 = &G_TexelLut[0];
pDx1 = &G_TexelLut[3];
// loop row....
for(int x = 0; x < 3; ++x, ++pDx0, ++pDx1) {
// is this position a splat?
int iIsRegion = (i >> (8-(y*3+x))) & 1;
// lut to find the 4 distances
fQ[0] = ClampFloatToZero(1.0f - (*pDx0 + *pDy0));
fQ[1] = ClampFloatToZero(1.0f - (*pDx1 + *pDy0));
fQ[2] = ClampFloatToZero(1.0f - (*pDx0 + *pDy1));
fQ[3] = ClampFloatToZero(1.0f - (*pDx1 + *pDy1));
// add up the total fWeights
fTotal[0] += fQ[0];
fTotal[1] += fQ[1];
fTotal[2] += fQ[2];
fTotal[3] += fQ[3];
// don''t add the fWeights if this isn''t the right splat
if(!iIsRegion)
continue;
// and add the splat fWeights
fWeight[0] += fQ[0];
fWeight[1] += fQ[1];
fWeight[2] += fQ[2];
fWeight[3] += fQ[3];
}
}
// 15 << 12 = 61440
// since we need alpha values in the range of 0 to 15 (4-bit alpha)
// and we need to shift this to the left by 12 bits, we may as well
// expand it here i guess. hence 61440.0. Now normalize...
fWeight[0] *= 15.0f / fTotal[0];
fWeight[1] *= 15.0f / fTotal[1];
fWeight[2] *= 15.0f / fTotal[2];
fWeight[3] *= 15.0f / fTotal[3];
// convert to an integer value (writing 2 pixels at once)
G_WeightLut[i] = ((DWORD)FloatToInt(fWeight[3]) << 24) |
((DWORD)FloatToInt(fWeight[2]) << 16) |
((DWORD)FloatToInt(fWeight[1]) << 8) |
((DWORD)FloatToInt(fWeight[0]));
}
return(0);
}
// constructs an alpha map for the quad leaf and splat
// texels/sec measured on a P2-Celeron 850Mhz
// version 1: 1.80 million texels/sec
// version 2: 3.20 million texels/sec
// version 3: 3.35 million texels/sec
// version 4: 3.90 million texels/sec
// version 5: 4.20 million texels/sec
// version 6: 6.40 million texels/sec
// version 7: 27.7 million texels/sec
int Terrain::CreateSplatAlpha(QuadLeaf* pLeaf,
int iSplatIndex,
LPDIRECT3DTEXTURE8 pTexture)
{
assert(pLeaf != NULL);
assert(pTexture != NULL);
assert(m_mapSplat.IsValid());
int x, y;
int iLookX, iLookY;
int iSplatPos, iSplatOffset;
int a, b;
DWORD *pPixels, *pSurface;
// table lookup value
DWORD dwLutIndex;
// unchangings
int iMinX = pLeaf->m_pParent->m_iMinX;
int iMinZ = pLeaf->m_pParent->m_iMinZ;
int iPitch = m_mapSplat.m_iCx;
// lock the texture for writing the alpha
D3DLOCKED_RECT lr;
if(pTexture->LockRect(0, &lr, NULL, 0) != D3D_OK)
return(1);
// our initial surface pointer
pSurface = (DWORD*)((BYTE*)lr.pBits);
// initial Y lookup value
iLookY = iMinZ;
// and overall initial lookup value
iSplatPos = iLookY * iPitch;
// generate the 64x64 alpha splat
for(y = 0; y < m_iCySplat>>1; ++y, ++iLookY) {
// change our current pixel pointer
pPixels = pSurface;
// set our x lookup value
iLookX = iMinX;
// process this row, unrolled to do 2x2 pixels each iteration
for(x = 0; x < m_iCxSplat>>1; ++x, ++iLookX, ++iSplatOffset) {
// reset our lut index
dwLutIndex = 0;
// set the offset
iSplatOffset = iSplatPos - iPitch + iLookX;
// check surrounding 9 places
for(a = -1; a < 2; ++a, iSplatOffset += iPitch) {
// int iTestA = ((unsigned)(iLookY+a) < iPitch);
// make sure we don''t sample outside the dimensions
// of the m_mapSplat[] surface
if((unsigned)(iLookY+a) >= iPitch)
continue;
// loop through this row of 3
for(b = -1; b < 2; ++b, dwLutIndex <<= 1) {
// again, don''t sample outside
if((unsigned)(iLookX+b) >= iPitch)
continue;
// don''t add the fWeights if this isn''t the right splat
dwLutIndex |= (m_mapSplat.m_pData[iSplatOffset+b] == iSplatIndex);
// int iTestB = ((unsigned)(iLookX+b) < iPitch);
// dwLutIndex |= (m_mapSplat.m_pData[iSplatOffset+b] == iSplatIndex) & iTestA & iTestB;
}
}
// shift back a position (1 too many)
dwLutIndex >>= 1;
// get the lut value
DWORD dwLutValue = G_WeightLut[dwLutIndex];
// decompose into pixel components
*pPixels = (((dwLutValue >> 8) & 0xff) << 28) | ((dwLutValue & 0xff) << 12);
pPixels += (lr.Pitch >> 2);
*pPixels = (((dwLutValue >> 24) & 0xff) << 28) | (((dwLutValue >> 16) & 0xff) << 12);
pPixels -= (lr.Pitch >> 2) - 1;
}
// change surface pointer to skip a row and start on the next
pSurface += (lr.Pitch>>1);
// and move our mapSplat index
iSplatPos += iPitch;
}
// unlock it now that we''re done
pTexture->UnlockRect(0);
return(0);
}
I got one weird thing tho... I tried to remove the if() statements in my inner loop and used an AND statement to mask between 0 and 1. It actually ran slower both on a P2 and P4. This I found very weird since I thought that conditionals were bad in an inner loop. I timed it over and over but it still is faster to use the conditionals. Can anyone shed any light on this? I remmed out the code that removes the conditional but it''s still there in comments.
Anyway, thanks to everyone who helped.
The "is outside" test is predicted perfectly most of the time, so it''s basically free.
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement