neilobremski
Experienced Member
The goal here is to draw lines around the outside of a 3D rendered shape. For my purposes, all 3D to 2D rendering is done via triangles. The reason triangles are so awesome for 3D is that every triangle is always co-planar (flat) and the three points can be rearranged in any order. The method I've created works on projected triangles only, those that have already been converted from 3D to 2D and thus have only two axes: X and Y.
First I need to explain how the shapes are represented in memory. Each point is a single 16-bit value with X in the most significant byte and Y in the least.[SUP][1][/SUP] These points are arranged in a linear array that ends with a zero byte.[SUP][2][/SUP] In order to close the shape, the first point is duplicated at the last. This comes in handy when matching sides because I don't have to check if I'm at the last and loop once to the first. For example, given a triangle (10,10) - (30,10) - (30,20) the point list will be:
To create an outline, I simply add more points to this list. How do I know what points are added and where? The answer is: one at a time by merging each 2D projected triangle in succession. This is based on another assumption I'm making, that the triangles forming the 3D shape are all convex, contiguous and their sides are abutted/overlapped. Given this assumption, a triangle part of a larger shape will share one of its three sides with the existing shape. Then the point that is not part of that shared side is the one to be inserted, simple as that:
In the example picture above, the original shape O shares the side 30,10-10,30 with triangle T. Thus the point inserted will NOT be 30,10 or 10,30 which leaves only 30,30. And a new point is always inserted between the points of the matched side. This results in the following point list (a perfect square):
By now I could have been done with the algorithm if I knew that the triangles would always be added contiguously, but that is not very likely. Since my 3D objects are hollow and convex there will be backface triangles that are culled, e.g. not projected and thus not added to this outline. Depending on which side the rendering starts from, I will end up with two or maybe even three isolated shapes that come together. Leaving this algorithm the way it is, the outline would end up with a seam line where the isolated shapes finally meet:
In the above example, the triangle T would be absorbed into shape O but not N and thus leave a seam line at 70,30-50,40. The next task, then, is to be able to use a triangle to merge two (outline) shapes.
Looking at it with intuitive human eyes, I can see simply that adding the points of N starting at where it overlaps with O is all that is needed. Computers are not intuitive, however, and the complication comes about depending on the ordering of the points. Consider if the points of O are clockwise and N are counter-clockwise [SUP][3][/SUP]:
If I were to add the points in order the result would be disorder and a worse seam than if I had left things alone! The trick is to determine whether the points are oriented the same between the two shapes and figure out where the overlap is so that point is not counted twice. Look at the data I use to determine this in the table: the insertion point I and the new point P for both shapes depending on their orientation.
There is a pattern here that results in the following algorithm:
To explain this better, I need to give a few more terms that relate to the point list. These are "a" for the array index of insert point I, "beg" for the starting index of the shape, and "end" for the final index of the shape that ignores both the duplicated start point and the null terminator. Given these:
The concept of overlap works a bit different depending on whether forward or backward copies are happening. Notice that going forward the points are in the same order as we're writing them whereas for backward they are being read in one direction and written in another.
I've run out of room in this post to give more examples so I'll pick this up again in a while.
Footnotes:
[SUP][1][/SUP]. When viewed in memory this means Y comes first but when looking at an integer (register) X is first due to the little endian byte ordering of the PC.
[SUP][2][/SUP]. No shape may render to a point that is 0,0 or it is seen as this NULL terminator. The algorithm could be modified to store a length value somewhere or use a different terminator but this works for me.
[SUP][3][/SUP]. When two or more isolated shapes are in a point list then another terminator indication is needed to signal the very end of the list. In my case, I use an empty shape which results in two 0000's, a "double null" terminator.
First I need to explain how the shapes are represented in memory. Each point is a single 16-bit value with X in the most significant byte and Y in the least.[SUP][1][/SUP] These points are arranged in a linear array that ends with a zero byte.[SUP][2][/SUP] In order to close the shape, the first point is duplicated at the last. This comes in handy when matching sides because I don't have to check if I'm at the last and loop once to the first. For example, given a triangle (10,10) - (30,10) - (30,20) the point list will be:
Code:
1010
3010
3020
1010
0000To create an outline, I simply add more points to this list. How do I know what points are added and where? The answer is: one at a time by merging each 2D projected triangle in succession. This is based on another assumption I'm making, that the triangles forming the 3D shape are all convex, contiguous and their sides are abutted/overlapped. Given this assumption, a triangle part of a larger shape will share one of its three sides with the existing shape. Then the point that is not part of that shared side is the one to be inserted, simple as that:
In the example picture above, the original shape O shares the side 30,10-10,30 with triangle T. Thus the point inserted will NOT be 30,10 or 10,30 which leaves only 30,30. And a new point is always inserted between the points of the matched side. This results in the following point list (a perfect square):
Code:
1010
3010
3030
1030
1010
0000By now I could have been done with the algorithm if I knew that the triangles would always be added contiguously, but that is not very likely. Since my 3D objects are hollow and convex there will be backface triangles that are culled, e.g. not projected and thus not added to this outline. Depending on which side the rendering starts from, I will end up with two or maybe even three isolated shapes that come together. Leaving this algorithm the way it is, the outline would end up with a seam line where the isolated shapes finally meet:
In the above example, the triangle T would be absorbed into shape O but not N and thus leave a seam line at 70,30-50,40. The next task, then, is to be able to use a triangle to merge two (outline) shapes.
Looking at it with intuitive human eyes, I can see simply that adding the points of N starting at where it overlaps with O is all that is needed. Computers are not intuitive, however, and the complication comes about depending on the ordering of the points. Consider if the points of O are clockwise and N are counter-clockwise [SUP][3][/SUP]:
Code:
1010
3020
5010
5040
3050
1040
1010
0000
9040
9010
7020
5040
7050
9050
0000
0000If I were to add the points in order the result would be disorder and a worse seam than if I had left things alone! The trick is to determine whether the points are oriented the same between the two shapes and figure out where the overlap is so that point is not counted twice. Look at the data I use to determine this in the table: the insertion point I and the new point P for both shapes depending on their orientation.
There is a pattern here that results in the following algorithm:
Code:
IF (Oi == Np) AND (Op == Ni) THEN CopyBackwardsWithoutOverlap
IF (Oi == Np) AND (Op <> Ni) THEN CopyForwardWithoutOverlap
IF (Oi == Ni) AND (Op <> Np) THEN CopyBackwardsWithOverlap
ELSE CopyForwardWithOverlapTo explain this better, I need to give a few more terms that relate to the point list. These are "a" for the array index of insert point I, "beg" for the starting index of the shape, and "end" for the final index of the shape that ignores both the duplicated start point and the null terminator. Given these:
Forward: Na to Nend and Nbeg to Na
Backward: Na to Nbeg and Nend to Na
Backward: Na to Nbeg and Nend to Na
The concept of overlap works a bit different depending on whether forward or backward copies are happening. Notice that going forward the points are in the same order as we're writing them whereas for backward they are being read in one direction and written in another.
I've run out of room in this post to give more examples so I'll pick this up again in a while.
Footnotes:
[SUP][1][/SUP]. When viewed in memory this means Y comes first but when looking at an integer (register) X is first due to the little endian byte ordering of the PC.
[SUP][2][/SUP]. No shape may render to a point that is 0,0 or it is seen as this NULL terminator. The algorithm could be modified to store a length value somewhere or use a different terminator but this works for me.
[SUP][3][/SUP]. When two or more isolated shapes are in a point list then another terminator indication is needed to signal the very end of the list. In my case, I use an empty shape which results in two 0000's, a "double null" terminator.