The main motivation for undertaking this project is to develop a monotone partitioning algorithm to be used in creating a process planner to numerically control the Shape Deposition Manufacturing (SDM) process. SDM combines material addition with material removal processes for fabricating metal objects with arbitrarily complex geometries. First, the material for each layer is deposited using a unique, weld-based deposition process called microcasting. In microcasting, molten metal droplets are created in a plasma and fall due to gravity onto the substrate. A robot moves the microcasting apparatus to deposit rows of droplets, forming layers. The long term goal of this project is to find the most efficient method of numerically decomposing a 3-D CAD model into 2-D layers which can be used by the planner to develop a plan for the microcasting process.
Before explaining monotone partitioning, a definition of monotonicity needs to be introduced first. Monotonicity is a property of a polygon that is defined with respect to a line. A polygonal chain C, is considered to be monotonic with respect to a line L, if every line, L`, which is orthogonal to L, meets C in at most one point. A chain is monotonic if the intersection of L` with C is either empty, a single point, or a single line segment. Note however that a strictly monotonic chain excludes a line segment from the intersection of L` with C. The monotone partitioning algorithm works with a monotone polygon, so strict monotonicity is not required.
A polygon P is considered monotone with respect to a line L if it can be split into two polygonal chains A and B, both of which are monotone with respect to L. The two chains share the highest and lowest vertices. The following polygon (which also serves as our test case) is considered to be monotonic with respect to the vertical (i.e. y-axis) but not strictly monotonic because both the right and left chains of vertices contain a horizontal line segment.
Figure 1: A polygon monotone with respect to the vertical.
Some polygons, especially convex ones, are monotone with respect to several lines, while other polygons, like the one you see above, is monotone with respect to the vertical only. An attempt was made to triangulate the following polygon (Figure 2), this time with respect to the horizontal, can you guess why the triangulation wasn't successful?
Figure 2: A non-monotonic polygon in the shape of a donkey
The reason is that this polygon is not monotonic! The polygon is not monotonic with respect to the horizontal and neither is it monotonic with respect to the vertical. After a slight modification to the polygon (it doesn't look like a donkey anymore), the polygon now looks like this (Figure 3) and can be triangulated using this concept.
Figure 3: A slight modification has been made to Figure 2.
The main idea behind the algorithm is quite simple. First the vertices are sorted with respect to the line of monotonicity, which in the first case is the y-axis (which involves sorting the vertices by their y-coordinate), and in the second case it is the x-axis. Sorting becomes more complex when the line of monotonicity is neither the x nor the y-axis, yet it is not impossible. However, finding the line of monotonicity can be quite difficult to implement. This issue requires more effort and it lies beyond the scope of this report. After sorting the vertices from top to bottom, the triangles are cut off from the top.
The algorithm is summarized in pseudocode (taken from Computational Geometry in C by Joseph O'Rourke, 57):
Algorithm: Monotone Triangulation
Sort vertices by y-coordinate. (or x-coordinate, whichever the case may be)
Initialize reflex chain to be two top vertices.
Let v be the third highest vertex.
while v != lowest vertex, do:
Case 1: v is on chain opposite reflex chain,
Draw diagonal from v to second vertex from top of chain.
and remove top of chain.
if chain has one element, then add v and advance v.
Case 2: v is adjacent to bottom of reflex chain.
Case 2a: v+ is strictly convex.
Draw diagonal from v to second vertex from bottom of chain,
and remove bottom of chain.
if chain has one element, then add v and advance v.
Case 2b: v+ is reflex or flat.
Add v to bottom of reflex chain,
Advance v.
This algorithm takes advantage of the fact that at every new iteration of the monotone triangulation algorithm, the vertices above v are (1) all in one chain and (2) the chain is reflex (which means that all the internal angles are greater than or equal to pi). If the vertices weren't all in one chain, then the diagonal would have been found in an earlier iteration (Case 1), and if the chain were not reflex, the diagonal would also have been found earlier (Case 2a).
Here are the files that were used to compile monotone.exe (all the code is written in the C programming language):
Figure 4: A complete triangulation of the polygon of Figure 1.
As can be seen from Figure 2, the polygon was successfully decomposed into triangles. The polygon in Figure 5 however has not been triangulated successfully due to the non-monotonicity of the geometry of the polygon. Compare Figure 6 with Figure 5.
Figure 5: Monotonic triangulation that failed because the polygon is not monotonic
Figure 6: A successful monotonic triangulation of the modified polygon
The reader might be wondering why monotonicity is required in this algorithm. The reason is because of the first assumption that was stated earlier, which is that the vertices above v are all in one chain. If the polygon were not monotonic, this would fail to hold true. The algorithm would check for diagonals across holes and gaps and various extensions within the polygon, which would make it almost impossible to triangulate it.
A future course of action would be, given an arbitrarily oriented polygon, to find the line of monotonicity. In case more than one line of monotonicity exists, the goal would be to find the line of monotonicity which yields the most efficient building direction for SDM.
Surprisingly however, the algorithm does not work for all cases of monotonic polygons. For example, if you would have run the pseudocode exactly as it is stated, the result that you would get from that can be seen in Figure 7. If you look really closely at it, the polygon is not completely triangulated and there is room for two more diagonals. This problem was corrected by adding a double if statement that is not part of the original algorithm.
Figure 7: An unsuccessful triangulation using the un-modified algorithm
The first if statement checks to see whether or not the vertex at the top of the chain and the vertex that is second from the top are adjacent in the polygon (i.e., they share a polygon edge between them). The second if statement checks to see whether or not the vertex v, and the top of the chain are adjacent. If they are not for both cases, then the program adds a diagonal between v and the top of the chain.
However, by adding the two if statements, the running code produces the following triangulation of a simple polygon (Figure 8) instead of the correct triangulation (Figure 9).
Figure 8: Incorrect triangulation caused by the two if statements
Figure 9: Correct triangulation (achieved by removing the two if statements)
As can be seen from the previous figures, the algorithm has to be re-thought and re-written before it can be used in any sort of manufacturing application. There are many triangulation methods in existence. Even though this algorithm runs faster than the general triangulation algorithm discussed in class, O(n2) vs O(n3), it can be exchanged for something else that actually works.
If you have comments or suggestions, email me at alessa+@cmu.edu.