We mostly avoid coding issues in our book, as our focus is on algorithms, not syntax and compiler vagaries. There’s a coding trick that I want to pass on, as it’s handy. Graphics programmers appear to be divided into two groups with this method: those who think it’s intuitively obvious and learnt it on their pappy’s knee, and those who never saw it before and are glad to find out.
You want to loop through the edges of a polygon. The vertex data is stored in some array vertexData[count], an array of count of some sort of Vertex data structure. The headache is attaching the last and first vertices together to make the connecting edge. There are plenty of weak ways to walk through the edges and connect last and first:
- Double the beginning vertex so it’s added to the end of array; the final edge is then just another pair of adjacent points. This is perhaps even fastest to actually execute but is generally a hideous solution, adding a copy of a vertex to the array.
- Form the last edge explicitly, outside the loop. Poor for maintenance, as you then need to copy whatever other code is inside the loop to be called one more time.
- Use an “if” statement to know if you’re at the end of the loop; if so, then connect the first and last vertices for the last edge. The “if” special case is needed for only one vertex, which is wasteful and we’d like to avoid “ifs”.
- Use modulo arithmetic on the counter for one of the vertices, so that it loops back to the start.
Modulo isn’t terrible, but is overkill and costs processing speed, as the modulo operation is truly needed for only the very last iteration:
for ( int v = 0; v < count; v++ ) {
// access vertexData[v] and vertexData[(v+1)%count] for the edge
}
Here’s the solution I prefer:
for ( int v1 = count-1, int v2 = 0; v2 < count; v1 = v2++ ) {
// access vertexData[v1] and vertexData[v2] for the edge
}
The simple trick is that v1 starts at the end of polygon, so dealing with the tough “bridge” case immediately; v2 counts through the vertices, and v1 follows behind. You can, similarly, make a pointer-based version, updating the pV1 pointer by copying from pV2. If register space is at a premium, then modulo might be a better fit, but otherwise this loop strikes me as the cleanest solution.
This copy approach can be extended to access any number of neighboring vertices per iteration. For example, if you wanted the two vertices vp and vn, previous and next to a given vertex, it’s simply:
int vp, v, vn;
for ( vp = count-2, v = count-1, vn = 0; vn < count; vp = v, v = vn++ ) {
// access vertexData[vp], [v], [vn] for the middle vertex v.
}
I’ve seen this type of trick in code in Geometric Tools, and Barrett formally presents it in jgt. I mention it here because I think it’s a technique every computer graphics person should know.
