Public Group

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

This topic is 4508 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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, 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,

1. 1
Rutin
24
2. 2
3. 3
JoeJ
18
4. 4
5. 5

• 38
• 23
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631706
• Total Posts
3001833
×