Optimizing meshes for the iPhone

The PowerVR guide says if you order triangle indices as if they were triangle strips you will get a speed boost, because the PowerVR chip implementation uses  triangle strips internally. The PowerVR SDK has an example to shows this, using a model of a sphere. I assumed that the example was an extreme case and you wouldn’t see such a big improvement for real models. However, I was pleasantly surprised to see that it actually did give a big improvement in a real world example – cutting down render time from 38ms to 35.5ms in a scene with 18 skinned meshes.

I used tootle to re-order the indices:

int result = TootleOptimizeVCache(pIndices,
      numTriIndices/3, m_listVertexArray[0]->GetNumVertices(),
      TOOTLE_DEFAULT_VCACHE_SIZE, pIndices, NULL, TOOTLE_VCACHE_LSTRIPS);
if (result != TOOTLE_OK)
    cout << "could not optimise!" << endl;

It’s important to use TOOTLE_VCACHE_LSTRIPS, because the default ordering is designed for PC GPUs and won’t work well on the iPhone.
Also, you have to reorder the vertex data to match the order in the triangle index array. Tootle can be found here.
Unfortunately, Tootle crashes for certain meshes. If there was source code, I probably could have fixed that – but there isn’t :(.

Advertisements

Vertex data interleaving on iPhone

In the PowerVR manual it says that you should interleave vertex data:

I tried this out on my engine and actually found no measurable improvement for static meshs. For skinned meshes it actually goes slower! Why? Because if you are doing software skinning, you have to reset the vertex buffer ever frame. If the vertex data isn’t interleaved then you can do this using memset for the postion and normal data, however if it’s interleaved you can’t because you would overwrite the texture co-ordinates, so you have to use a loop instead.

Accelerating Software skinning with VFP assembler

I was trying to get my engine perform better on older iDevices. I need to be able to render 18 characters on screen simultaneously, however on the 1st gen iPod touch it takes 63ms to render the scene. I thought I’d try to use vfp assembly to speed it up, using code from this site: http://code.google.com/p/vfpmathlibrary/

Initially, it didn’t make any difference at all. This was because it was GPU bound. So, I reduced the scene to 8 skinned meshes – which would show up optimisation improvements better.

The assembler code still didn’t speed things that much. I ran the code analyzer tool and found the piece of code that was most of the time was the code that transforms the vertices with the current matrix of the joint:

for (n = 0; n < (int)m_listVertex.size(); n++)
{
weight = m_listWeight[n];
index = m_listVertex[n]*3;
matrix.TransformPoint(&pOrigData[index],weight, &pCurrData[index]);
}

void Matrix::TransformPoint(const float* pInVertex, float weight, float* pOutVertex) const
{
pOutVertex[0] += weight*(pInVertex[0]*m[0] + pInVertex[1]*m[4] + pInVertex[2]*m[8] + m[12]);
pOutVertex[1] += weight*(pInVertex[0]*m[1] + pInVertex[1]*m[5] + pInVertex[2]*m[9] + m[13]);
pOutVertex[2] += weight*(pInVertex[0]*m[2] + pInVertex[1]*m[6] + pInVertex[2]*m[10] + m[14]);
}

There was a function similiar to this in the vfpmathlibrary. So I modified it and this is the result:

// Sets length and stride to 0.
#define VFP_VECTOR_LENGTH_ZERO “fmrx    r0, fpscr            \n\t” \
“bic     r0, r0, #0x00370000  \n\t” \
“fmxr    fpscr, r0            \n\t”

// Set vector length. VEC_LENGTH has to be bitween 0 for length 1 and 3 for length 4.
#define VFP_VECTOR_LENGTH(VEC_LENGTH) “fmrx    r0, fpscr                         \n\t” \
“bic     r0, r0, #0x00370000               \n\t” \
“orr     r0, r0, #0x000” #VEC_LENGTH “0000 \n\t” \
“fmxr    fpscr, r0                         \n\t”

void Matrix::TransformPoint(const float* pInVertex, float weight, float* pOutVertex) const
{
asm volatile (
// Load the whole matrix.
“fldmias  %[matrix], {s8-s23}     \n\t”
// Load vector to scalar bank.
“fldmias  %[pInVertex], {s0-s2}      \n\t”
// Load weight to scalar bank.
“fldmias  %[weight], {s3}      \n\t”
“fldmias  %[pOutVertex], {s28-s30}      \n\t”

VFP_VECTOR_LENGTH(2)

“fmuls s24, s8, s0        \n\t”
“fmacs s24, s12, s1       \n\t”
“fmacs s24, s16, s2       \n\t”
“fadds s24, s24, s20        \n\t”
“fmuls s24, s24, s3        \n\t”
“fadds s24, s24, s28        \n\t”

// Save vector.
“fstmias  %[out], {s24-s26}  \n\t”

VFP_VECTOR_LENGTH_ZERO
:
: [matrix] “r” (m),

[pInVertex] “r” (pInVertex),

[weight] “r” (&weight),

[out] “r” (pOutVertex)
: “r0”, “cc”,
“s0”,  “s1”,  “s2”,  “s3”,
“s8”,  “s9”,  “s10”, “s11”, “s12”, “s13”, “s14”, “s15”,
“s16”, “s17”, “s18”, “s19”, “s20”, “s21”, “s22”, “s23”,
“s24”, “s25”, “s26”, “s28”, “s29”, “s30”
);
}

It took me quite a while to figure out the assembler, because you need to reference several very technical books to figure it out. I’d like to make this job easier for any interested programmers out there. So, just let me explain it line by line.

On the first line you have: asm volatile(…); .This instructs gcc that the stuff in the ( ) brackets is assembler code. volatile means, tells gcc not to try to “optimize” the code.

Then you have a number of strings each string is an arm vfp instruction.

The vfp has 4 banks of 8 single precision floating point registers:

The idea is that you can do up to 8 similar floating point operations at the same time.  If you look at the formula that we’re trying to implement again:

pOutVertex[0] += weight*(pInVertex[0]*m[0] + pInVertex[1]*m[4] + pInVertex[2]*m[8] + m[12]);
pOutVertex[1] += weight*(pInVertex[0]*m[1] + pInVertex[1]*m[5] + pInVertex[2]*m[9] + m[13]);
pOutVertex[2] += weight*(pInVertex[0]*m[2] + pInVertex[1]*m[6] + pInVertex[2]*m[10] + m[14]);

You see that we could do pInVertex[0]*m[0], pInVertex[0]*m[1] and pInVertex[0]*m[2] all in one instruction. And the rest of the formula is done the same way – three operations all in the one go.

So, let’s go through the code line by line.

First you have: “fldmias  %[matrix], {s8-s23}     \n\t”

fldmais loads memory contents into several registers. Here, it’s loading the entire matrix (16 floats) into s8-s23. (It doesn’t actually use all the data in the matrix, but it’s easier to do it all in one instruction).

The “matrix” is an assember variable defined in the section at the bottom, but we’ll cover that later.

Notice, there is \n\t at the end of the line. Thats just to format the assember code. It’s just something that you have to add to each assembler line.

Next, we have: “fldmias  %[pInVertex], {s0-s2}      \n\t”

This loads the 3 vertex co-ords into s0-s2 – i.e. bank 0. Bank zero is different than the other banks, but I’ll go into that later.

Then, we load the weight and the output vertex co-ords into other registers:

“fldmias  %[weight], {s3}      \n\t”
“fldmias  %[
pOutVertex], {s28-s30}      \n\t”

So, now we have everything loaded.

Next we have to tell the vpf how many ops we do at the same time. We have a macro:

VFP_VECTOR_LENGTH(2)

This sets the vector length setting to 3 (it’s actually one more than the specified parameter).

So, now it’s time to do the fun part: the math ops!

The first op is: “fmuls s24, s8, s0        \n\t”

This is equivalent to three single vector ops:

fmuls 24, s8, s0
fmuls 25, s9, s0
fmuls 26, s10, s0

s0 is in bank 0 and this bank has special function: the address never increments for a vector operation ( a so-called scalar vector). Now, if you remember we had the matrix data in s8-s23 and the vertex data in s0-s3. So this function does the following calculation:

s24 = pInValues[0]*m[0]
s25 = pInValues[0]*m[1] 
s26 = pInValues[0]*m[2] 

We are always dumping the results into s24-s26, which we use as temp registers.

The next instruction is:

“fmacs s24, s12, s1       \n\t”

fmacs multiplies, then adds. So this instruction is the equivilant to:

s24 += pInValues[1]*m[4]
s25 += pInValues[1]*m[5]
s26 += pInValues[1]*m[6] 

Then

“fmacs s24, s16, s2       \n\t”

As you probably guess, this is the equivilant to:

s24 += pInValues[2]*m[8]
s25 += pInValues[2]*m[9]
s26 += pInValues[2]*m[10]

Then:

“fadds s24, s24, s20        \n\t”

As you might guess this is addition:

s24 += m[12]
s25 += m[13]
s26 += m[14]

Then multiply by the weight which is stored in s3:

“fmuls s24, s24, s3        \n\t”

s24 *= weight
s25 *= weight 
s26 *= weight

Finally, add to the current vertex data (which we stored in s28-s30):

“fadds s24, s24, s28        \n\t”

s24 += pOutValues[0]
s25 += pOutValues[1] 
s26 += pOutValues[2]

Then, we load the result back into the current vertex data:

“fstmias  %[out], {s24-s26}  \n\t”

And the VFP_VECTOR_LENGTH_ZERO macro restores the vector size back to the default value of 1 (otherwise all hell would break loose).

The stuff at the end tells gcc the inputs and output of the function. There always has to be three sections seperated by colons :

 : // output parameters
 : [matrix] "r" (m),
   [pInVertex] "r" (pInVertex),
   [weight] "r" (&weight),
   [pOutVertex] "r" (pOutVertex)            // input parameters
 : "r0", "cc",  "s0",  "s1",  "s2",  "s3",
 "s8",  "s9",  "s10", "s11", "s12", "s13", "s14", "s15",
 "s16", "s17", "s18", "s19", "s20", "s21", "s22", "s23",
 "s24", "s25", "s26", "s28", "s29", "s30"  // clobber list

The first section is the output parameters, which is blank. This doesn’t make any sense, because really it should have pOutVertex, but apparently it just works that way – don’t ask me why.

The next section is the input parameters. First you have the variable name used in the assembler code surrounded by square brackets [], then you have a “r” then the variable name as used in the c++ part of the code in round brackets (). Note: this has to be an address, *not* a value, that’s why the weight has a & in front of it.

The next section is what is affectionately known as “the clobber list“. This tells gcc what registers we have used in the program. If you accidentally forget to include a register in the clobber list, it’ll crash, so this is important.

I found that the program could be speeded up even more by moving the VFP_VECTOR_LENGTH macros from TransformPoint to outside of the main loop:

SetVectorLen2();
for (n = 0; n < (int)m_listVertex.size(); n++)
{
weight = m_listWeight[n];
index = m_listVertex[n]*3;
matrix.TransformPoint(&pOrigData[index], weight, &pCurrData[index]);
}
SetVectorLen0();

All in all, the assembler code reduces the total render time from 34ms to 30.5ms (when rendering 8 skinned meshes), which is not bad.

If you try to run this code on a newer device, like a iPhone 3GS, you’re in store for a surprise as the 3GS has no VFP unit and it actually reduces the performance by a large amount :-D.

But don’t worry about this because the 3GS goes so fast it doesn’t really need assembler.

Protected: DS 2050

This content is password protected. To view it please enter your password below:

Slowville: std::map

Many people don’t realise how slow the  map that comes with the standard template library is.

Reciently, did some performance comparisons of std::map versus boost::unordered_map.

These are the benchmarks that I tested:

fmap<int, int> mapTest;
fmap<int, int>::iterator iter;
int time1 = GetMilliSeconds();
int n;
int randNum, rand2;
rand2 = 0;
for (n = 0; n < 100000; n++)
{
 randNum = rand()%1000;
 iter = mapTest.find(randNum);
 if (iter != mapTest.end())
 {
 rand2 = iter->second;
 }
 else
 {
 mapTest[randNum] = rand2;
 rand2 = n;
 }
}
int time2 = GetMilliSeconds();
int timeElapsed = abs(time2-time1);
cout << "map test1 time:" << timeElapsed << "ms" << endl;
time1 = time2;

fmap<int, int> mapTest2;
fmap<int, int>::iterator iterLowest;
int f;
for (n = 0; n < 10000; n++)
{
 for (f = 0; f < 10; f++)
 {
 randNum = rand()%1000;
 iter = mapTest2.find(randNum);
 if (iter != mapTest2.end())
 {
 rand2 = iter->second+1;
 }
 else
 {
 mapTest2[randNum] = rand2;
 rand2 = n;
 }
 }
 // find lowest
 iterLowest = mapTest2.begin();
 for (iter = mapTest2.begin(); iter != mapTest2.end(); iter++)
 {
 if (iter->second > iterLowest->second)
 iterLowest = iter;
 }
 mapTest2.erase(iterLowest);
}
time2 = GetMilliSeconds();
timeElapsed = abs(time2-time1);
cout << "map test2 time:" << timeElapsed << "ms" << endl;

(Unfortunately, this looks awful because stupid word press strips out my code indentation 😦 )

And these are the results running on 1st gen iPod touch:

boost::unordered_map
map test1 time:115ms
map test2 time:2251ms

std::map
map test1 time:200ms
map test2 time:3940ms

As you can see it’s nearly twice as slow.

std::map is an ordered map. In other words, when iterating the values are ordered according to the key. Normally, you don’t need this functionality, so using a hash map like boost::unordered_map is a no-brainer.

How the App Store featured lists work

I published my game Armageddon Wars a few weeks ago and was very lucky to get on the “New and Noteworthy” list under the games category. Apps only stay on that list for one week, but then to my surprise I saw it on the “What’s hot” list. Again Apps only last a week on the “What’s hot” list. So, I assumed that was that, but again to my surprise I saw yesterday that it was on the “What we’re playing” list.

Anyway, I was looking at the screenshots just now and I noticed that the exact same apps get on all the lists:

I thought that these lists were hand picked by Apple, but that seems only to be the case with the “New and Noteworthy” list. Once you are on that list you automatically get moved onto the other lists after a week.

Edit:

Just now I noticed my game stayed on the “What we’re playing” list for much longer than a week, but it seems that after a week it moved down the list, so the user has to press “see all” to see the game. Also, in some countries it stayed on the “what’s hot” list. In Australia for instance it’s still on the first page of that list. I assume that’s because the game got a higher star rating there than in other countries

more improvements

I did some more work on my engine.

Implemented redundant node removal and made the class hierarchy more logical and added compressed textures.

The result was that I reduced the frame time to 53ms from 63ms (presume that’s mainly because of reduced nodes)

Also discovered, that just by building on Mac that my character’s face renders correctly (I could have sworn that it wasn’t like that on Windows)