# spot the mistake in this algorithm please! [SOLVED]

## Recommended Posts

i've been staring at this for half an hour and i still cant see why its not working! i have a texture, and i want to look throught the texture to count how many pixels are duplicated (only looking at the rgb value). it runs ok but it doesnt give the right number. heres what i have:

int count = 0;
read2CPU();  // this reads the texture values into an array of floats called endPos
for (int i = 0; i<size*4; i+=4)  // loop throught the array
{
float pos[3] = {endPos[i], endPos[i+1], endPos[i+2]}; // get the rgb value for the element
for (int j = i+4; j<size*4; j+=4) // loop through the rest of the array
{
float comparePos[3] = {endPos[j], endPos[j+1], endPos[j+2]};
if((pos[0] == comparePos[0])
&& (pos[1] == comparePos[1])
&& (pos[2] == comparePos[2])
&&  pos[1] != -1.0f)
{
count++;
comparePos[1] = -1.0f; // set a dummy value so we dont count the duplication again at the next iteration.
}
}
}
printf("\n%i", count);


[Edited by - judge dreadz on March 13, 2006 9:52:24 AM]

##### Share on other sites
Not sure if I am right but you're doing i+=4 and only using 3 positions (0, 1, 2) so you're always missing one pixel.

float pos[2] ...float comparePos[2] ..

Do not forget that position 0 is also a position.

##### Share on other sites
At first glance that looks fine to me. What exactly is wrong, is it counting too few or too many?

Dave

##### Share on other sites
Quote:
 Original post by TheGangsterNot sure if I am right but you're doing i+=4 and only using 3 positions (0, 1, 2) so you're always missing one pixel.Hope this can help you, also note that your arrays should be float pos[2] ...float comparePos[2] ..Do not forget that position 0 is also a position.

No, it does need to be 3 in the square brackets, to specify the size of the array, it is still zero indexed though.

##### Share on other sites
dave: counting sometimes too many and sometimes too few. the thing that really gives it away though is that the count doesnt change very often, it seems to repeatedly return the same number, even though i know the duplication in the texture is increasing (and this is what i need to monitor).

gangster: i'm only concerned about the rgb values, which is why i only look at the first 3 values of each 4 valued pixel element. my arrays should be pos[2]? you've lost me there!

##### Share on other sites
How is the texture generated? The snippet says that the RGB values are floats and compares them using ==. Perhaps its a question of resolution? What happens if you use a "close to" instead of "is identical" or even better if you quantize the RGB values more coarsly?

##### Share on other sites
There is a risk when comparing floats that they are not exactly the same as stated above. Perhaps use ints or allow for a small error.

Also are you sure that pos[1] is never -1.0f naturally? If it is then you will be missing these duplicates.

Greig

##### Share on other sites
maybe this line:
comparePos[1] = -1.0f; // set a dummy value so we dont count the duplication again at the next iteration

must be:
pos[1] = -1.0f; // set a dummy value so we dont count the duplication again at the next iteration

##### Share on other sites
To verify that your code is not incorrect because of floating point rounding problems ... write a CompareFloat function and inside of it put something like the following:

float epsilon = ???; // don't know the C++ version of epsilon, in C# it is a contant in Math

float fudgeFactor = epsilon * 16; // just an artitrary number that is less than 25% of the difference between the numbers you expect to use. For instance if your numbers are ranges from 0.0 - 1.0 with 100 steps, then use something like 0.0025 (1/4th of your approximate step size).

In fact if you know your step size, this test will be much more valid.

return (lhs > (rhs - fudgeFactor) && lhs < (rhs + fudgeFactor));

If that works, then you knows its a float compare problem, else you know it isn't.

##### Share on other sites
It is a rather bad idea to compare float using the ==() operator. Not all float values can be represented in the IEEE floating point format. You should test the difference between the two float - if the difference is below a given treshold then you can assume they are identical.

For example:

#include <cmath>      // for fabsfnamespace{  bool areFloatEqual(float a, float b)  {    // test if the difference between a and b is lower than 0.000001:    if (std::fabsf(a - b) < 1e-6f) {      return true;    }    return false;  }}

Moreover, this is unneeded:
// set a dummy value so we dont count the duplication again at the nextcomparePos[1] = -1.0f;

As well as your != -1 test, of course. You initialize comparePos each time you enter in the comparison loop. It means that you'll do it right after this unneeded line of code.

Now, from an algoritmic point of view, you code don't work. If we simplify the problem to an array of integers instead of an array of {float,float,float}, consider this example:
array[] = { 1, 2, 1, 2, 1, 2, 1 };

Your first iteration will count the number of 1 from pos 0; your second iteration will count the number of 2 from pos 1; Your third iteration will count the number of 1 from pos 1, and so on.
[1     2     1     2     1     2     1][0     0    +1     0    +1     0    +1] (1st iteration)[0     0     0    +1     0    +1     0] (2nd iteration)[0     0     0     0    +1     0    +1] (3rd iteration)[0     0     0     0     0    +1     0] (4th iteration)[0     0     0     0     0     0    +1] (5th iteration)[0     0     0     0     0     0     0] (6th and 7th iteration)

At the end, count = 9 = more than the number of values in the array! (and we didn't count the first two duplicated values).

Do you see what's wrong?

I said before that setting comparePos[1] to -1 is useless - comparePos[] is a local array. In fact, you must modify the value of the corresponding pixel in endPos. Of course, you'll change your texture, so you have to copy it before doing anything else.

HTH,

##### Share on other sites
ok, replacing the line is not enough... this ?

int count = 0;
int j;

for (int i = 0; i i)
{
count++;
}
j = size * 4;
}
}
j+=4;
}
}
printf("\n%i", count);
(sorry to post in anonymous for the second time but my account is not yet activated...

Alfith.

##### Share on other sites
Quote:
 Original post by haegarrHow is the texture generated? The snippet says that the RGB values are floats and compares them using ==. Perhaps its a question of resolution? What happens if you use a "close to" instead of "is identical" or even better if you quantize the RGB values more coarsly?

hmmm... i'm not sure about this. if it was a rounding problem, surely it would consistanly overestimate the number of duplicates? at the moment is seems to constantly come out with either 496 or 406 (with a 32x32 texture)

anyway, i'm pretty certain there is something else going on - i changed the following line:

if (..... && pos[1] != -1.0f)

to:

if (..... && pos[1] > 0.0f)

and now it says 0 all the time!

##### Share on other sites
emmanuel, yes you are right, the line

comparePos[1] = -1.0f;

should in fact be

endPos[j+1] = -1.0f;

##### Share on other sites
grrr !
my reply is completly messed up...
sorry for this... my account is not yet activated...
I hope this will of be of some help:

for each "i" element
{
.initialize "pos"
.j = 0;
.while j i
....{
.....count++;
....}
....j = size * 4;
...}
..}
..j+=4;
.}
}

Alfith.

##### Share on other sites
ok, i wrote a function to compare floats to 4 decimal places, and it still doesnt work!

##### Share on other sites
infact, just to test, i set the floatEqual function to:

if (fabsf(a - b) < 100000.0f) return true;

and running on a 32*32 texture it says 3!

somedays i hate computers!

##### Share on other sites
whoops lol! please shoot me now. sorry everyone :(

##### Share on other sites
Care to expand on how you solved the issue finally?

Greig

##### Share on other sites
err.. not really cos it still doesnt work lol!

where i'm passing in "size", its a size*size texture but i was only looping over size (so only actually reading half the texture).

thats why when i set the floatEquals function to <1000.0f it didnt give the expected answer of 1023 (32*32 texture). i spotted that and thought that was the only mistake.

turns out i was a bit rash though, setting the floatEquals to <0.1f (which is pretty generous, its a 32 bit floating point texture!) still repeatedly gives out the same number. this number is far lower than it should be and it should gradually increase, its remains constant at the moment.

##### Share on other sites
Maybe it's time for some debugging.

Can you perform a test on a very small part of the texture? Print out the values for each pixel and then print out when a match is found.

Then go through each pixel (the values you have printed) and search to see if it has been repeated and your algorithm has missed it.

Basically work out which ones aren't being matched up and then work out why. Hopefully once you havev two pixels that should match but don't it will be easier to find the bug.

Greig

##### Share on other sites
ok, I have an account...
sorry for the mess...
int count = 0;int i, j;read2CPU();for (i = 0; i<size*size*4; i+=4){  float pos[3] = {endPos[i], endPos[i+1], endPos[i+2]};  j = 0;  while (j < size*size*4)  {    if (j != i)    {      float comparePos[3] = {endPos[j], endPos[j+1], endPos[j+2]};      if((pos[0] == comparePos[0])      && (pos[1] == comparePos[1])      && (pos[2] == comparePos[2]))      {        if (j > i)        {          count = count+1;        }        j = size*size*4;      }    }    j=j+4;  }}printf("\n%i", count);

I hope it is finally ok...

Alfith.

##### Share on other sites
ok hold on guys, a thought is forming in my head... think i might no what the problem is... will report back in 10

##### Share on other sites
ok, i've found it. there was nothing wrong with the algorithm. the problem was where i was calling it from.

its a little complex but i will explain as best i can for the curiosity of others.

i originally wrote the read2CPU function to monitor the texture update in the gpu. the gpu texture update requires mapping the texture by setting the viewport to a 1:1 mapping. the viewport then has to be re-set in the display method at each frame to display the system on screen. so when i called checkDuplication from the display method, the read2CPU function was using an incorrect mapping and not returning the correct data.

ps. i'm not sure if the above method is correct, if anyone knows a more efficient method then resetting the viewport twice every frame, please let me know!

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628282
• Total Posts
2981812

• 9
• 10
• 11
• 17
• 15