Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!rutgers!lll-crg!styx!ames!ucbcad!ucbvax!ADS.ARPA!Info-Graphics-Request From: Info-Graphics-Request@ADS.ARPA.UUCP Newsgroups: mod.graphics Subject: Info-Graphics Digest Message-ID: <8611231112.AA24282@ucbvax.Berkeley.EDU> Date: Sun, 23-Nov-86 06:00:19 EST Article-I.D.: ucbvax.8611231112.AA24282 Posted: Sun Nov 23 06:00:19 1986 Date-Received: Mon, 24-Nov-86 01:08:00 EST Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Info-Graphics@ADS.ARPA Organization: The ARPA Internet Lines: 140 Approved: info-graphics@ads.arpa Info-Graphics Digest Sun Nov 23 03:00:19 PST 1986 - Send submissions to Info-Graphics@ADS.ARPA - Send requests for list membership to Info-Graphics-Request@ADS.ARPA Today's Topics: Re: Line-Polygon Intersection Rendering Workshop, Call for Participation ---------------------------------------------------------------------- Date: Wed, 19 Nov 86 22:54:48 EST From: garry@tcgould.tn.cornell.edu (Garry Wiegand) Subject: Re: Line-Polygon Intersection Organization: Cornell Engineering && Flying Moose Graphics In a recent article scm@onion.cs.reading.Ac.Uk (Stephen Marsh) wrote: >... What I need is NOT the line-plane intersection point, >but an algorithm which tests to see if the intersection point >is contained within the 3D polygon. { Warning: yet another description of point-in-polygon coming! } The simple minded approach is to project it down into a convenient 2-D plane and apply the usual point-in-polygon algorithms. For example, given the 3-D intersection point and polygon, and given (for this example) that the polygon is not perpendicular to the XY plane, project it down into that plane. Do this by ignoring the Z-values! Once there, start anywhere on the polygon and walk around. At each step, test to see if the edge passes above-to-below or below-to-above with respect to the test point. (Note: For purposes of "passing", the start vertex of the edge does NOT count, and the end vertex DOES count.) If it *does* pass, figure whether it passes to the left or right of the test point: If the test edge is horizontal and includes the test point, declare it "in" and exit. If the edge is horizontal and doesn't include the test point, forget it. If it's not horizontal, see if the edge is completely left or right of the test point. If it's not completely left or right, then compute the intersection with the horizontal and see whether *that* is left or right. If the intersection is right on top, declare the point "in" and exit. Remember how many times you pass to the left, say. If this ends up odd, the point's in. Otherwise it's out. In the normal "in" case you'll need to compute maybe *one* edge/axis intersection. Whew. (We need a picture.) You can improve the computation with bounding boxes and other such tricks. If you know the polygon's convex, you of course won't need a counter, and you'll only need to look at at most (n+1)/2 edges (often far fewer) (exercise left for the reader.) (If you're working in floating-point, be careful about tests-for- equality!) (If the original polygon WAS perpendicular to the XY plane, project into the YZ plane, say, and apply a tweaked version of the above algorithm.) I trust I've been complete. Wonder if it's right - I've never gotten around to reading about this subject (who said computer graphics wasn't ffun ? :-) garry wiegand (garry%cadif-oak@cu-arpa.cs.cornell.edu) ------------------------------ Date: Wed, 19 Nov 86 21:18:40 cst From: ihnp4!sask!peachey@ucbvax.Berkeley.EDU (Darwyn Peachey) Subject: Rendering Workshop, Call for Participation Workshop on Rendering Algorithms and Systems Call for Participation A limited attendance workshop on rendering algorithms and systems will be held on Sunday, April 5 and Monday, April 6, 1987 in conjunction with the CHI + GI '87 Conference in Toronto. The workshop will begin with the presentation of ``position papers'' by each participant. Subsequent group discussion will focus on current practice and promising new techniques in rendering, with the goal of producing a taxonomic breakdown of the rendering process, placing current techniques in context. Discussion will be directed to determining the relationships (ideal and actual) among the various sub-problems which must be solved by any rendering system, for example: o+ modeling and representation o+ hidden-surface algorithms, including scan conversion o+ illumination models and shading o+ system considerations Individuals wishing to participate in the workshop may request an invitation by submitting a two to four page position paper discussing the taxonomy of rendering techniques, or the relationship of the author's own work to other rendering techniques. The workshop report, listing the participants and summarizing the discussion, will be presented at the Conference and submitted for publication in the SIGGRAPH newsletter, _C_o_m_p_u_t_e_r _G_r_a_p_h_i_c_s. Position papers are due no later than DDDDeeeecccceeeemmmmbbbbeeeerrrr 11115555,,,, 1111999988886666.... Three copies of each paper should be sent to the workshop organizer: Darwyn Peachey Dept. of Computational Science 86 Commerce Building University of Saskatchewan Saskatoon, Saskatchewan CANADA S7N 0W0 Invited participants will be notified by February 1, 1987 and will be sent copies of the selected position papers and a final agenda for the workshop. Questions may be directed to the following addresses: PHONE: (306) 966-4909 UUCP: {ihnp4,alberta,utcsri}!sask!peachey BITNET: peacheyd@sask ------------------------------ End of INFO-GRAPHICS ********************