home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 12074 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  2.5 KB
  1. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!rpi!psinntp!psinntp!eye!erich
  2. From: erich@eye.com (Eric Haines)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Point inside a triangle
  5. Message-ID: <1992Nov18.095436.27867@eye.com>
  6. Date: Wed, 18 Nov 92 14:54:36 GMT
  7. References: <1992Nov16.115211.23169@sophia.smith.edu> <Bxtz3s.6xA@slipknot.rain.com> <1992Nov17.132302.6345@sophia.smith.edu>
  8. Organization: 3D/EYE, Inc.  Ithaca, NY
  9. Lines: 44
  10.  
  11. In article <1992Nov17.132302.6345@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes:
  12. >In article <Bxtz3s.6xA@slipknot.rain.com> robert@slipknot.rain.com.UUCP (Robert Reed) writes:
  13. >
  14. >>The special cases are trivial to discard, if the ray intersects a vertex, the
  15. >>adjacent vertices must have Y values of opposite sign (assuming a horizontal
  16. >>ray) to represent a crossing.  If the point is collinear with an edge, discard
  17. >>it [the edge, I presume].
  18. >
  19. >It seems from your description that points on the boundary of the triangle
  20. >T are not handled consistently by the ray algorithm.  Below, a is not in T
  21. >but b is in T.
  22. >
  23. >                   /\
  24. >                  b  \
  25. >                 /    \
  26. >                +--a---+       
  27. >
  28. >At least this seems to be what the code that Michael Goza posted does.
  29. >Am I right?
  30.  
  31. Absolutely right - points on the edges are (somewhat) arbitrarily determined
  32. to be in or out by the ray crossings test.  The good news is that there is
  33. consistency:  if a point lies on an edge shared by two polygons, the point
  34. will be found to be inside one and only one polygon when you use the ray
  35. crossings test.  This is an excellent property for rendering and picking, as
  36. you generally want to consider any point on a surface as being inside one and
  37. only one polygon.
  38.  
  39. By the way, to absolutely maintain this consistency property you have to make
  40. sure to project all polygons in the same fashion (i.e. you can't just use the
  41. "cast onto the best plane for this polygon's normal" idea mentioned).  Usually
  42. this consistency does not matter for well-behaved polygons;  only when
  43. (ill-defined) non-planar polygons are being rendered is it important to be
  44. consistent in the way the 3D polygons are projected to 2D.
  45.  
  46.  
  47. Incidentally, all you point-in-triangle posters might want to check out the
  48. FTP site princeton.edu [128.112.128.1], file /pub/Graphics/RTNews/RTNv5n3.Z,
  49. the latest issue of the Ray Tracing News, which is dedicated to the point in
  50. polygon question (though there's still more to be written - next issue...).
  51. There is efficient code for the crossings test (it's a bit faster than the
  52. code Mike Goza posted), the barycentric test, and more.
  53.  
  54. Eric Haines
  55.