Kessells_SR@cc.curtin.edu.au (10/22/90)
Does anybody know a simple test for a polygon's orientation ? (.i.e. clockwise or anti-clockwise) Please mail to below, thanks ! Michael ------------------------------------------------------------------------------- Aussie Post: Michael Evans Internet: TKESSELLS01@cc.curtin.edu.au ACSnet: TKESSELLS01@cc.cut.oz.au Bitnet: TKESSELLS01%cc.curtin.edu.au@cunyvm.bitnet UUCP: uunet!munnari.oz!cc.curtin.edu.au!TKESSELLS01 -------------------------------------------------------------------------------
) (10/23/90)
> >Does anybody know a simple test for a polygon's orientation ? >------------------------------------------------------------------------------- I'm kind of new to graphics (well, anything beyond playing on the apple II), but the same question came to me recently, so I started thinking about it. I thought of one way, but I think it would be rather slow (ie. don't try to run this algorythm in a real-time sim). Oh...I"m assuming from your question you mean a 3-d polygon, where you are trying to determine the direction of the normal for hidden surfaces...if this is wrong, then completely ignore my alg. :) Also, it wont work for polyhedrons with serious concavities. 1) Determine the center of your solid (simply averaging all of the points of the poly's is good enough for the purposes of this test). 2) Determine the center of the plane of your polygon. 3) make this into a vector. 4) Determine the normal to your polygon (using it's current order) 5) If the Normal of the poly is in the same direction (read: within 90 degrees) as the vector from step 3, then the poly is clockwise. If the Normal is in the opposite (greater than 90 degrees), then your poly is anti-clockwise. If it's 90 degrees, then I'm not sure what you ought to do. If your return value is anti-clockwise or clockwise, then this is all you need. If you're return value is hidden or non-hidden, then substitute this for step 5 5) if the Normal of the poly is in the same direction, then determine whether or not the surface is hidden with this Normal vector. if they are in opposite directions, then use the Normal's negative (multiply the coefficients of I, J, and K by -1) for determining if the surface is hidden or not. Again, I don't know what to do if the normals turn out perpendicular (sp?). Hope this helps (btw: if anyone knows of a formalised version of this algorythm, let me know..) John Rudd -- Emporers Thought for the Day: | John E. Rudd jr. Only the insane have the strength to prosper; | ccastjr@prism.gatech.edu Only those who prosper judge what is sane. | (ex- kzin@ucscb.ucsc.edu) #include<std.disclaim> Send all comments, flames, and complaints to /dev/null.
jcs@crash.cts.com (John Schultz) (10/23/90)
Yes, there are at least two easy ways:
1. Use the cross product of two of the points, the sign determines
the orientation (Subtract point 0 from points 1 and 2, compute
the cross product between the new points 1 and 2).
2. Use the Newell method (in many graphics texts).
Here's a snippet of code to get you started:
if (count > 3) { /* Newell method */
orient = 0;
for (i=0; i < count; i++) {
if (i == (count-1)) {
j = 0;
} else {
j = i+1;
}
orient += (point[i].x - point[j].x)*(point[i].y + point[j].y);
}
} else { /* Move to origin, and do cross product */
d1.x = point[1].x - point[0].x;
d1.y = point[1].y - point[0].y;
d2.x = point[2].x - point[1].x;
d2.y = point[2].y - point[1].y;
orient = d1.x*d2.y - d1.y*d2.x;
} /* if count > 3 */
/* Right handed coordinate system with +z into screen */
sgnorient = sgn(orient);
if (sgnorient < 0) { /* do counter-clockwise case */
} else if (sgnorient > 0) { /* do clockwise case */
} else { /* Polygon is a line segment or point (coplaner points) */
} /* if */
Hope this helps,
Johnfalk@peregrine.Sun.COM (fred) (10/23/90)
In article <5201@crash.cts.com> jcs@crash.cts.com (John Schultz) writes: > Yes, there are at least two easy ways: > > 1. Use the cross product of two of the points, the sign determines > the orientation (Subtract point 0 from points 1 and 2, compute > the cross product between the new points 1 and 2). Careful! If the polygon isn't convex, you can easily get the wrong answer. > 2. Use the Newell method (in many graphics texts). This works. Essentially, you use the standard algorithm for finding the area of a polygon: A = .5 * ( (y1+y0)(x1-x0) + (y2+y1)(x2-x1) + ... + (y0+yn)(x0-xn) ) and look at the sign of the result. That's all. -ed falk, sun microsystems sun!falk, falk@sun.com card-carrying ACLU member.
smiller@wet.UUCP (Gregory Shane Miller) (10/27/90)
The best way to see if a 2D poly is CCW or CW is too look in the PREPARATA/SHAMOS Comp. Geometry book in chapter 2. As I recall in sect 2.3 or 2.2 (I don't have the book with me) there is a foot note saying, given any three points from a polygon, eval this 3x3 matrix (eg. find det of the 3x3 matrix). If returns the twice the signed area of the three points (eg a triangle). The sign of the result tells whether it's oriented CW or CCW. Check it out. regards- -- -- G. Shane Miller [ smiller@wet.UUCP ] Von Neumann eat your heart out!
pfbertnd@watcgl.waterloo.edu (Philippe F. Bertrand) (10/29/90)
In article <1728@wet.UUCP> smiller@wet.UUCP (Gregory Shane Miller) writes: > >Note saying, given any three points from a polygon, eval this 3x3 >matrix (eg. find det of the 3x3 matrix). If returns the twice the >signed area of the three points (eg a triangle). The sign of the >result tells whether it's oriented CW or CCW. This algorithm only works on concave polygons! ie it will not work for (0,0), (1,1), (0,2), (2,2), (2,0) = square with a chunk removed your algorithm using the first 3 points will return CCW when in fact it is CW This is important for hidden surface algorithms in 3D where a face of an object has all the perspective and view operations performed on it resulting in a 2D polygon. If all faces originally appear CW when they are facing you, hidden surfaces will be CCW after the view transformations. Previously posted solutions appeared correct. > >G. Shane Miller [ smiller@wet.UUCP ] Von Neumann eat your heart out! - Philip F. Bertrand pfbertrand@violet.waterloo.edu Computer Graphics Lab, or pfbertnd@watcgl.waterloo.edu Department of Computer Science, University of Waterloo Waterloo, Canada N2L 3G1
kellehe@silver.ucs.indiana.edu (Mike Kelleher) (11/04/90)
This message was first posted on the Comp.simulation Newsnet, but in order to receive more coverage and feedback, it will be poster here as well. Several other Graphics personnel and I here at Indiana University are trying to compile a database of information on Virtual Environments and other related data. In accordance with Univeristy Computing Services here at Indiana, we will take any information that is sent to us over the net, organize and catalog the information and send out a completed packet to anyone who is interested. Information on VR certainly can be found, but in order to get a clearer idea of where VR is now and where it is going, data will have to be gathered and recorded. Official sources such as the Smithsonian in Washington, DC and the Autodesk Corporation have pledged their support of this project and will send (or have already sent) us their available information. However, this database will not be complete until it is certain that we have received as much information as possible on this subject. This database is public, and therefore should be treated as such. Without all available information, this database will not live up to it's full potential: to bring all relevant information to all interested parties. It should also be noted that this project, though University supported, is not University organized, like many other college research projects. This Database is relying solely on the participants who will contribute and the dedication of the graphics personnel here at University Computing Services. Without outside public help, it is too much for a financially unsupported, self-organized task. We would like to thank the people and sources that have helped us so far in the effort, but we still need more support. Data and information can be sent to us at these addresses at any time. Thank you. Mike Kelleher Univeristy Computing Services VR Project =============================================================================== | ii | |_| | [] Michael Kelleher | Virtual Environment | | ==== | Database Project, 1990 | | || University Computing Services | VR, Past Present & Future | | || Neat-Oh Enterprises | Design and Research | | || Kellehe@bronze.ucs.indiana.edu | -=-=-=-=-=-=-=-=-=-=-=-=- | | || Kellehe@silver.ucs.indiana.edu | Public Database in cooperation | | || Kellehe@ucs.indiana.edu | with University Computing Services| | \/ | | ===============================================================================