Sign in to follow this  
judge dreadz

spot the mistake in this algorithm please! [SOLVED]

Recommended Posts

judge dreadz    193
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 this post


Link to post
Share on other sites
TheGangster    134
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.

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.

Share this post


Link to post
Share on other sites
dave    2187
Quote:
Original post by TheGangster
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.

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 this post


Link to post
Share on other sites
judge dreadz    193
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 this post


Link to post
Share on other sites
haegarr    7372
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 this post


Link to post
Share on other sites
Greig Hamilton    181
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 this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
Xai    1848
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 this post


Link to post
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 fabsf

namespace
{
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 next
comparePos[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 this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
ok, replacing the line is not enough... this ?

int count = 0;
int j;

read2CPU();
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 this post


Link to post
Share on other sites
judge dreadz    193
Quote:
Original post by haegarr
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?



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 this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
judge dreadz    193
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 this post


Link to post
Share on other sites
judge dreadz    193
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 this post


Link to post
Share on other sites
Greig Hamilton    181
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 this post


Link to post
Share on other sites
Alfith_    122
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 this post


Link to post
Share on other sites
judge dreadz    193
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!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this