Jump to content
  • Advertisement
Sign in to follow this  
Spa8nky

Is there any way to combine the following into one loop?

This topic is 3051 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

Hi there, I've got a loop that creates a polygon as follows:
            // For each polygon face
            for (int i = 0; i < faces; i++)
            {
                if (i > 0)
                {
                    edge[i - 1] = vertices - vertices[i - 1];

                    if (CCW)
                    {
                        Vector2 normal_RH = new Vector2();
                        normal_RH.X = -edge[i - 1].Y;
                        normal_RH.Y = edge[i - 1].X;

                        normal[i - 1] = Vector2.Normalize(normal_RH);
                    }
                    else
                    {
                        Vector2 normal_LH = new Vector2();
                        normal_LH.X = edge[i - 1].Y;
                        normal_LH.Y = -edge[i - 1].X;

                        normal[i - 1] = Vector2.Normalize(normal_LH);
                    }
                }

                // Set vertices/indices for drawing the polygon
                Vector3 position = new Vector3();
                position.X = vertices.X;
                position.Y = vertices.Y;
                position.Z = 0f;

                vertices_Drawable = new VertexPositionColor(position, Color.Red);
                indices = (short)i;

                // Calculate polygon centroid
                centre += vertices;
            }


The problem is that the last side can't be currently calulated in the loop and has to be placed outside the loop:
            // Add the first vertex to the end of the indices to close the line strip
            indices[faces] = 0;

            // Compute final edge and face normal
            edge[faces - 1] = vertices[0] - vertices[faces - 1];

            if (CCW)
            {
                Vector2 normal_RH = new Vector2();
                normal_RH.X = -edge[faces - 1].Y;
                normal_RH.Y = edge[faces - 1].X;

                normal[faces - 1] = Vector2.Normalize(normal_RH);
            }
            else
            {
                Vector2 normal_LH = new Vector2();
                normal_LH.X = edge[faces - 1].Y;
                normal_LH.Y = -edge[faces - 1].X;

                normal[faces - 1] = Vector2.Normalize(normal_LH);
            }


Is there any way to combine both calculations into one loop? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
- Expand the array by one, copy 0-th element last place, ignore it elsewhere
- use (i%faces) instead of just i as index
- refactor the function to take (Face a, Face b) parameters (cuts down the amount of duplicated code

Pick any of the above.

Generalized description of the problem: How to process consecutive pairs of array elements with wrapping.

Share this post


Link to post
Share on other sites
My apologies to whoever wrote the awesome blog post that explained how to do this because I forgot who he was, but he cribbed it from someone else so I don't feel too bad. I assume Knuth did it originally, because, well, he's Knuth. This is a thing that every graphics programmer should know how to do.

Suppose you need to iterate over the following pairs: (0,1), (1,2), (2, 3) ... (n-2, n-1), (n-1, 0). The key is to put the last pair first. Here's the loop:

for(int a=n-1, b=0; b<n; a=b, b++)
{
printf("(%d, %d)\n", a, b);
}

Beautiful, no?

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
My apologies to whoever wrote the awesome blog post that explained how to do this because I forgot who he was, but he cribbed it from someone else so I don't feel too bad. I assume Knuth did it originally, because, well, he's Knuth. This is a thing that every graphics programmer should know how to do.

Suppose you need to iterate over the following pairs: (0,1), (1,2), (2, 3) ... (n-2, n-1), (n-1, 0). The key is to put the last pair first. Here's the loop:

for(int a=n-1, b=0; b<n; a=b, b++)
{
printf("(%d, %d)\n", a, b);
}

Beautiful, no?


That is cool.

Share this post


Link to post
Share on other sites

for(int a=n-1, b=0; b<n; a=b, b++)
{
printf("(%d, %d)\n", a, b);
}


That's a pretty cool trick. You'll get two cache misses right off the bat as you aren't accessing in sequence, but the usual approach will probably cache miss when accessing the final edge anyway, as the very first edge would have been kicked out by that time.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
My apologies to whoever wrote the awesome blog post that explained how to do this because I forgot who he was, but he cribbed it from someone else so I don't feel too bad. I assume Knuth did it originally, because, well, he's Knuth. This is a thing that every graphics programmer should know how to do.

Suppose you need to iterate over the following pairs: (0,1), (1,2), (2, 3) ... (n-2, n-1), (n-1, 0). The key is to put the last pair first. Here's the loop:

for(int a=n-1, b=0; b<n; a=b, b++)
{
printf("(%d, %d)\n", a, b);
}

Beautiful, no?
I prefer (and always do) the (i+1)%n stuff, as Antheus suggested, that trick is hard to read, and has 2 variables. But if it was just irony, that sorry, I'm tired to see that.

Share this post


Link to post
Share on other sites
Quote:
Original post by szecs
I prefer (and always do) the (i+1)%n stuff, as Antheus suggested, that trick is hard to read, and has 2 variables.


modulus tends to be slow. The only advantage it has is that it works universally for m elements (think wrapped convolution kernel computation).

For pairs, for loop is quite clean, although if I encountered it in code without knowing context, I'd be scratching my head for a while.

Either way, I find that this type of problem, while algorithmically elegant, might be clearest to express explicitly:
for (i:0..n-1) handle(i, i+1);
handle(i+1, 0);


IMHO: if performance is paramount, then it is likely that some other method will work much faster anyway, and special case handling will likely work best, or use something like loop unrolling anyway. For everything else, clarity should probably be a priority. For this reason, I'd suggest moving the body out of the loop in either case, since it makes the intent much more explicit (we're doing something with a and b).

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Original post by szecs
I prefer (and always do) the (i+1)%n stuff, as Antheus suggested, that trick is hard to read, and has 2 variables.


modulus tends to be slow. The only advantage it has is that it works universally for m elements (think wrapped convolution kernel computation).

For pairs, for loop is quite clean, although if I encountered it in code without knowing context, I'd be scratching my head for a while.

Either way, I find that this type of problem, while algorithmically elegant, might be clearest to express explicitly:
for (i:0..n-1) handle(i, i+1);
handle(i+1, 0);


IMHO: if performance is paramount, then it is likely that some other method will work much faster anyway, and special case handling will likely work best, or use something like loop unrolling anyway. For everything else, clarity should probably be a priority. For this reason, I'd suggest moving the body out of the loop in either case, since it makes the intent much more explicit (we're doing something with a and b).
Thanks for that, I didn't know modulus is slow. I use it heavily, I should rethink it.

Share this post


Link to post
Share on other sites
Quote:
Original post by szecs
Thanks for that, I didn't know modulus is slow. I use it heavily, I should rethink it.


OTOH, the usual advice about premature optimization applies. And on the other other hand, you could also try something like if (++x == n) { x = 0; }.

Share this post


Link to post
Share on other sites
Quote:
I prefer (and always do) the (i+1)%n stuff, as Antheus suggested, that trick is hard to read, and has 2 variables.
Not only is modulus slow, it's only applicable to random-access containers. I'm surprised you find it hard to read -- prev=cur; increment cur is a pretty common idiom -- but I guess I've seen this idiom enough that I couldn't really give a useful opinion on how easy it is to understand the first time. The 2 variables thing is a complete red herring, though. If you're using (i+1)%n all over your loop body, (i+1)%n is a variable, whether you call it that or not.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!