Jump to content
  • Advertisement
Sign in to follow this  
judge dreadz

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.

If you intended to correct an error in the post then please contact us.

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


Link to post
Share on other sites
Advertisement
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
At first glance that looks fine to me. What exactly is wrong, is it counting too few or too many?

Dave

Share this post


Link to post
Share on other sites
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
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
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
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
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!