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

## 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 on other sites
- 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 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 on other sites
Quote:
 Original post by SneftelMy 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

That is cool.

##### 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 on other sites
Quote:
 Original post by SneftelMy 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
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 on other sites
Quote:
 Original post by szecsI 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 on other sites
Quote:
Original post by Antheus
Quote:
 Original post by szecsI 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 on other sites
Quote:
 Original post by szecsThanks 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 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.

• 11
• 20
• 12
• 10
• 38
• ### Forum Statistics

• Total Topics
631401
• Total Posts
2999865
×