home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / graphics / 9668 < prev    next >
Encoding:
Internet Message Format  |  1992-09-13  |  2.3 KB
  1. Path: sparky!uunet!cs.utexas.edu!torn!news.ccs.queensu.ca!qucdn!jiangy
  2. Organization: Queen's University at Kingston
  3. Date: Saturday, 12 Sep 1992 22:16:54 EDT
  4. From: <JIANGY@QUCDN.QueensU.CA>
  5. Message-ID: <92256.221654JIANGY@QUCDN.QueensU.CA>
  6. Newsgroups: comp.graphics
  7. Subject: Re: 3d line through 3d polygon
  8. References:  <BuGD8w.CxA@iat.holonet.net>
  9. Lines: 44
  10.  
  11. The most intuitive (not necessarily efficient) solution is:
  12.    (1) compute the coefficient (A, B, C, D) of the polygon plane
  13.        using Newell (?) method. See Gems I (or II or III, cann't
  14.        remember exactly) for the code.
  15.    (2) compute the intersection point between the infinite line
  16.        and the plane.
  17.    (3) test if the point is in the polygon. The code for this can be
  18.        found in the latest Raytracing news (ftp: princeton.edu, in
  19.        pub/Graphics/RTNews/RTNv5n3).
  20.    (4) if the answer to (3) is yes, determine if this point lies
  21.        between the two end points of the line segment. If yes, the
  22.        line segment intersect the polygon and the point is what you
  23.        are looking for.
  24.  
  25. Yaohong Jiang
  26. Queen's U
  27.  
  28.  
  29. (Sorry, I missed one step between steps 2 and 3: you have to rotate
  30. the polygon and the intersection point so that all the polygon vertices
  31. and the intersection point have the same z coordinates, since the point-in-
  32. polygon test in RTNews works only for 2D point and polygons.
  33.  
  34. Rotating the polygon is equivalent to rotating the x-y-z coordinate system
  35. as following: Given a point P(x,y,z) in x-y-z coordinate system, Let
  36. (x', y', z') be the coordinates W.R.T the second coordinate system x'-y'-z'
  37. Assume the two systems have the same origin and :
  38.    x' has direction cosine t11, t21, t32      W.R.T  x-y-z system
  39.    y' has ................ t12, t22, t32      ...................
  40.    z' has                  t13, t23, t33      ...................
  41. ( This also means that:
  42.    x has direction cosine t11, t12, t13      W.R.T x'-y'-z' system
  43.    y                      t21, t22, t23
  44.    z                      t31, t32, t33
  45.   t11, t12, etc. can be computed from the polygon plane easily.
  46.  
  47. Then we have : x' = t11*x + t21*y + t31*z
  48.                y' = t12*x + t22*y + t32*z
  49.                z' = t13*x + t23*y + t33*z
  50.  
  51. And lastly, remember to rotate the polygon and the intersection back
  52. after the point-in-polygon test before the last step above.
  53.  
  54. Y. Jiang
  55.