// For each polygon face
for (int i = 0; i < faces; i++)
{
if (i > 0)
{
edge = vertices<span style="font-weight:bold;"> - vertices;
<span class="cpp-keyword">if</span> (CCW)
{
Vector2 normal_RH = <span class="cpp-keyword">new</span> Vector2();
normal_RH.X = -edge.Y;
normal_RH.Y = edge.X;
normal = Vector2.Normalize(normal_RH);
}
<span class="cpp-keyword">else</span>
{
Vector2 normal_LH = <span class="cpp-keyword">new</span> Vector2();
normal_LH.X = edge.Y;
normal_LH.Y = -edge.X;
normal = Vector2.Normalize(normal_LH);
}
}
<span class="cpp-comment">// Set vertices/indices for drawing the polygon</span>
Vector3 position = <span class="cpp-keyword">new</span> Vector3();
position.X = vertices<span style="font-weight:bold;">.X;
position.Y = vertices<span style="font-weight:bold;">.Y;
position.Z = 0f;
vertices_Drawable<span style="font-weight:bold;"> = <span class="cpp-keyword">new</span> VertexPositionColor(position, Color.Red);
indices<span style="font-weight:bold;"> = (<span class="cpp-keyword">short</span>)i;
<span class="cpp-comment">// Calculate polygon centroid</span>
centre += vertices<span style="font-weight:bold;">;
}
</pre></div><!–ENDSCRIPT–>
The problem is that the last side can't be currently calulated in the loop and has to be placed outside the loop:
<!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre>
<span class="cpp-comment">// Add the first vertex to the end of the indices to close the line strip</span>
indices[faces] = <span class="cpp-number">0</span>;
<span class="cpp-comment">// Compute final edge and face normal</span>
edge[faces - <span class="cpp-number">1</span>] = vertices[<span class="cpp-number">0</span>] - vertices[faces - <span class="cpp-number">1</span>];
<span class="cpp-keyword">if</span> (CCW)
{
Vector2 normal_RH = <span class="cpp-keyword">new</span> Vector2();
normal_RH.X = -edge[faces - <span class="cpp-number">1</span>].Y;
normal_RH.Y = edge[faces - <span class="cpp-number">1</span>].X;
normal[faces - <span class="cpp-number">1</span>] = Vector2.Normalize(normal_RH);
}
<span class="cpp-keyword">else</span>
{
Vector2 normal_LH = <span class="cpp-keyword">new</span> Vector2();
normal_LH.X = edge[faces - <span class="cpp-number">1</span>].Y;
normal_LH.Y = -edge[faces - <span class="cpp-number">1</span>].X;
normal[faces - <span class="cpp-number">1</span>] = Vector2.Normalize(normal_LH);
}
</pre></div><!–ENDSCRIPT–>
Is there any way to combine both calculations into one loop?
Thanks.Is there any way to combine the following into one loop?
Author
Hi there,
I've got a loop that creates a polygon as follows:
- 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.
- 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.
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:
Beautiful, no?
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?
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.
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.
Quote:Original post by SneftelI 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.
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?
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).
Quote:Original post by AntheusThanks for that, I didn't know modulus is slow. I use it heavily, I should rethink it.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).
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; }.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
