🚀 go-pugleaf

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
********************