roger@everexn.uucp (Roger House) (05/30/90)
In <807@fsu.scri.fsu.edu> prem@geomag.fsu.edu (Prem Subrahmanyam) writes: > I am presently writing a converter program between Aegis Modeller/ > VideoScape 3d format files to DBW_Render files. The one problem > I've encountered is that DBW has only triangles and parallelograms > as primitives, and I need to convert between possibly concave polygons > from Modeller to triangles. So far, this is what I've come up with > as a general algorithm: > 1. find a set of 3 points in a convex section of the polygon, and > slice these off as a triangle by drawing a line between the first > and third points. > 2. trianglulate the remaining part, according the the above until > you've boiled it down to a triangle--which is obviously pre-triangulated. > Question: how can I find 1. simply--I'd rather not try to map all the > points to a 2-dimensional coordinate system and test for insideness/ > outsideness by testing the intersection between a ray (of the Euclidean > type-not a CG ray) and the sides of the polygons by extending the ray in > any direction from the test point and determining how many lines it > hits--odd means inside, even means outside...I need a faster, dirtier > version that this. Any help will be much appreciated. > ---Prem Subrahmanyam It seems to me that projecting the original polygon to a 2-d situation is the way to go. However, after the projection, there is no need to check how many sides of the polygon are cut by a ray. It is not clear to me how the use of such a ray would help in decomposing into triangles. Following is a somewhat verbose description of a way to solve your problem, begin- ning with the 2-d case and then extending it to your 3-d problem. Concave or Convex? The cruz of your problem is determining whether an angle is convex (< 180 degrees) or not. Given three distinct points P0, P1, and P2 in the plane, how do we tell it the angle formed by line segments P0P1 and P1P2 is con- vex or not? Before we answer this, we must be clear about our point of view: We assume that we are ABOVE the xy-plane (i.e., at some point with a positive z-coordinate), looking down. In addition, we define the angle between P0P1 and P1P2 by measuring the arc swept out by rotating P1P2 about P1 in a COUNTERCLOCKWISE direction until we meet segment P0P1. We don't actually need to determine the exact angle. We simply want to know if it is < 180 degrees or not. Thus, we can conceptualize the pro- blem in a bit different way: Consider the infinite line oriented FROM P0 TO P1. Where is P2 in relation to this line? P2 is on the left: The angle is < 180 degrees P2 is on the line: The angle is = 180 degrees P2 is on the right: The angle is > 180 degrees So now the problem boils down to figuring out which side of a line that a point is on. This is easily determined. If L(x, y) = 0 is the ORIEN- TED equation of a line, where L(x, y) = ax + by + c, then for any point P, L(P) > 0: Point P is on the left of the line L(P) = 0: Point P is on the line L(P) < 0: Point P is on the right of the line Thus, to tell whether angle P0P1P2 is convex, do this: Determine the oriented equation of the line FROM P0 TO P1, and plug P2 into the equa- tion. If the result is > 0, then the angle is convex. WARNING: As always when working with floating point arithmetic, all comparisons should involve an epsilon. Furthermore, to be safe, the equation of the line should be normalized by dividing all coefficients by sqrt(a*a + b*b). Then when the equation is evalutated at a point, the result is actually the signed distance of the point from the line, which can be compared against an epsilon to see where the point is in relation to the line. A shortcut to the above method of determining a line equation is to use this determinant, where Ph = (xh, yh), Pi = (xi, yi), and Pj = (xj, yj): | xh yh 1 | D = | xi yi 1 | | xj yj 1 | If D > 0 then Pj lies on the left of the line FROM Ph TO Pi. If D = 0, the three points are collinear. If D < 0 then Pj lies on the right of the line FROM Ph TO Pi. (Lying on the left means angle PhPiPj is convex, and lying on the right means the angle is nonconvex.) DISCLAIMER: The above determinant should be checked. I am recalling it from memory, and it may not be quite right. Using this determinant is not really different from the method already de- scribed. Calculating the determinant is exactly the same as determining the equation of the line from point Ph to point Pi and then plugging Pj into the equation. Also, a warning is in order, because no normalization is done. So now we have a way to tell if an angle is convex or not. This operation is the basic primitive for all the following algorithms. Clockwise or Counterclockwise? Say we are given an array of n >= 3 distinct points labeled P0, P1, ..., Pn-1, which are the vertices of a well-formed simple polygon P. Say that the n vertices are in order, but we don't know if the order is clockwise or counterclockwise. How do we tell? Here is a simple algorithm: Scan the set of vertices and find the one with least x-coordinate. If there is more than one vertex with least x-coordinate, then pick the one of them which has least y-coordinate. The resulting vertex is unique. (If not, the polygon is ill-formed because its vertices are not distinct points.) Call this vertex Pi. Let Ph be the vertex preceding Pi, and let Pj be the vertex following Pi. Then test if angle PhPiPj is convex. If it is, then the vertices of poly- gon P are oriented counterclockwise in our input array. Otherwise, the vertices are ordered clockwise. In the latter case, reverse the elements of P to put the vertices in counterclockwise order. Decomposing a 2-d polygon in the xy-plane into triangles Given a well-formed simple polygon P with n >= 3 vertices labeled P0, P1, ..., Pn-1, we want to decompose P into triangles. We assume that the vertices are oriented in a counterclockwise direction as seen from above. Before presenting a general algorithm which handles all cases, it is worthwhile to consider the case when it is known that the polygon is convex (i.e., all angles < 180 degrees). Then the polygon is easily decomposed into n-2 triangles by drawing diagonals from vertex 0 to the n-3 vertices P2, P3, ..., Pn-2, resulting in these triangles: P0,P1,P2 P0,P2,P3 P0,P3,P4 . . . P0,Pn-2,Pn-1 If it is known that many of the polygons to be processed are likely to be convex, then it is a good idea to test each polygon to see if it is convex, and if so, apply the above simple algorithm. Only when a non- convex polygon is encountered is it necessary to apply the general al- gorithm. Here is the general algorithm: Let Pi be any vertex of the polygon. Let Ph be the vertex preceding Pi, and let Pj be the vertex following Pi. Test if angle PhPiPj is convex. If not, increment i, determine h and j from i, and test again. If a convex angle is not found by this process, there is an error in the polygon. It is either not well-formed, or it is oriented clockwise. Once a convex angle PhPiPj is found, the triangle formed by the three points is a candidate. However, it is ONLY a candidate. It must be tested like this: For every vertex V of the polygon other than the three forming the triangle, test if V is OUTSIDE the triangle (note that V must not be ON the boundary of the triangle). If some vertex is found which is either on the boundary of or inside of the triangle, then the triangle must be rejected. In this case, increment i and continue searching for a convex angle. If all V are outside of the triangle, then slice the triangle off the polygon by removing vertex Pi. If the number of points in the resulting polygon is 3, then the decomposition is finished. Otherwise, search again from a convex angle. Here is a more detailed version of the algorithm: i = n-1; while (n > 3) { h = i; i = (i == n-1 ? 0 : i+1); j = (i == n-1 ? 0 : i+1); if (angle PhPiPj nonconvex) continue; k = (j == n-1 ? 0 : j+1); /* k is vertex after j */ m = n-3; while (m--) if (Pk outside triangle PhPiPj) k = (k == n-1 ? 0 : k+1); else break; if (k != h) /* Vertex k not outside */ continue; /* triangle PhPiPj */ Store triangle PhPiPj; Remove vertex Pi from polygon P; n--; i = (i == 0 ? n-1 : i-1); } Store triangle P0P1P2 as the final triangle of the decomposition; The above algorithm always produces exactly n-2 triangles. Also, every vertex of every triangle produced by the algorithm is a vertex of the original polygon. In other words, no new points are created by this al- gorithm. Now Back to 3-Space Since your original problem has to do with a polygon in 3-space, we need to consider how to get from there to the xy-plane. Say that the input is an array Q of n >= 3 3-points, Q0, Q1, ..., Qn-1 which are the vertices of a well-formed simple planar polygon. If the plane of the polygon is not vertical (consider the xy-plane to be horizontal), then simply set up a 2-d polygon P with the points Q, ignor- ing the z-coordinate. In effect, this projects polygon Q onto the xy- plane. Now check if P is counterclockwise, and, if not, reverse its ele- ments so it is counterclockwise. Then decompose P into triangles. Note that if the z-coordinates are carried in polygon P (they will never be used because all algorithms above use only x- and y-coordinates), then the triangles produced by the decomposition will in fact be polygons in 3-space with correct z-coordinates. Thus, the input polygon is decom- posed as desired. If the input polygon is in a vertical plane (which can be determined by checking to see if the projection onto the xy-plane is a straight line), then simply swap the x- and z-coordinates of the input vertices, apply the algorithm in the preceding paragraph, and then swap the x- and z- coordinates of the resulting triangles. Note that this method of going from 3-space to 2-space works because a parallel projection of a polygon does not change any convex angles to nonconvex ones, or vice versa. Hope this helps.
lambert@spectrum.eecs.unsw.oz (Tim Lambert) (06/01/90)
>>>>> On 29 May 90 21:28:26 GMT, roger@everexn.uucp (Roger House) said:
% Let Pi be any vertex of the polygon. Let Ph be the vertex preceding Pi,
% and let Pj be the vertex following Pi. Test if angle PhPiPj is convex.
% If not, increment i, determine h and j from i, and test again. If a
% convex angle is not found by this process, there is an error in the
% polygon. It is either not well-formed, or it is oriented clockwise.
% Once a convex angle PhPiPj is found, the triangle formed by the three
% points is a candidate. However, it is ONLY a candidate. It must be
% tested like this: For every vertex V of the polygon other than the three
% forming the triangle, test if V is OUTSIDE the triangle (note that V
% must not be ON the boundary of the triangle). If some vertex is found
% which is either on the boundary of or inside of the triangle, then the
% triangle must be rejected. In this case, increment i and continue
% searching for a convex angle.
% If all V are outside of the triangle, then slice the triangle off the
% polygon by removing vertex Pi. If the number of points in the resulting
% polygon is 3, then the decomposition is finished. Otherwise, search
% again from a convex angle.
It is possible to construct triangles for which this algorithm takes
O(n^3) time. If you get triangles like this with a lot of points,
this algorithm will probably be unacceptably slow.
Timwrf@mab.ecse.rpi.edu (Wm Randolph Franklin) (06/07/90)
This problem is harder to do fast than you'd think. It's related to the planar graph location problem. (Given a net of polygons, process them so that we can tell which polygon contains a new point). The triangulation can actually be implemented to run in (n lg n) time, I think. Chazelle may have an (n lg* n) method. People think a linear method exists. All these times are from a vague recollection. Actually the easiest way is probably to divide and conquer. Pick 2 nonadjacent vertices and see if they are visible from each other. If so join them and recursively solve the 2 subproblems. If not, keep looking, perhaps by moving to an endpoint of the edge that prevents the 2 original points from seeing each other. Put a counter here to stop the program from infinitely looping. There will always be some pair of visible vertices, but optimization attempts may prevent you from hitting them. -- Wm. Randolph Franklin Internet: wrf@ecse.rpi.edu (or @cs.rpi.edu) Bitnet: Wrfrankl@Rpitsmts Telephone: (518) 276-6077; Telex: 6716050 RPI TROU; Fax: (518) 276-6261 Paper: ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180