home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / graphics / 13245 < prev    next >
Encoding:
Text File  |  1992-12-29  |  3.7 KB  |  92 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!munnari.oz.au!hp9000.csc.cuhk.hk!hkuxb.hku.hk!h8915726
  3. From: h8915726@hkuxb.hku.hk (Medusa)
  4. Subject: Summary: (WAS: Point inside an enclosed region)
  5. Message-ID: <C00rnH.IGr@hkuxb.hku.hk>
  6. Reply-To: h8915726@hkuxa.hku.hk
  7. Organization: University of Hong Kong
  8. X-Newsreader: Tin 1.1 PL4
  9. Date: Tue, 29 Dec 1992 11:52:28 GMT
  10. Lines: 80
  11.  
  12. Hi, 
  13.  
  14. Here are the replies, up to now, I got. Thanks very much for the suggestion.
  15. If there are anymore, I will post the summary again.
  16.  
  17.  
  18. 1) This is from Mike Brindley.
  19.  
  20. > Well, it seems to me that you should be able to precalculate a bounding
  21. > box (a width at least) for your pattern.  You will probably want to sort
  22.  
  23.     Yes. His guess is right. I know the bounding box, and that's
  24.     what I have done today. it reduces the time by 1/3 to 1/2 if
  25.     the pattern is small enough (i.e., there are MORE complete-within-
  26.     pattern than part-within-pattern). But my program still
  27.     runs slowly as much 30-40 sec as to fill around 300x300 irregular
  28.     closed-type with a semi-circle pattern of around 15x15 pixels.
  29.  
  30. > or otherwise order your pattern.  Then, when you find the span extrema,
  31. > you can do trivial accept/rejects on the points in the pattern. With the
  32. > points in the pattern sorted/ordered, you only need check a part of them
  33. > before you know that you need not check any more.  This is the same idea
  34. > as keeping an active edge list for the polygon.  See your favourite 
  35. > graphics text (Foley, VanDam, Hughes, et al; Newman & Sproull; Harrington;
  36. > etc.)  for details on the scanline/raster filling technique.
  37.  
  38. > Of course, for bitmap (raster) displays, the pattern is normally kept in
  39. > a bitmap.  Then you can easily and cheaply index into it and use the pattern
  40. > pixel as a mask (plot or no plot; complement or leave alone; which color).
  41.  
  42.     Yes. This idea also comes from the following nice people too.
  43.  
  44. 2) This is from Sumant.
  45.  
  46. > 1. Faster Ways to find point inside Polygon:
  47. >    The Infinite Ray test is still the best one for
  48. >    point inside a general polygon test.
  49. >    However, its not as expensive as U think.
  50. >    You can convert the method to simple camparison
  51. >    method.
  52. >    Look at the book "Introductions to Ray Tracing"
  53. >    by Glassner on ray-object intersection !!
  54. >    It gives you the fast algorithm.
  55. >    If U dont have access to it, let me know.
  56. >    I'll send U the alo by mail.
  57. > 2. No one does pattern filling by checking every point for
  58. >    inside-outside. It is done by a simple modification to
  59. >     polygon scan-conversion filling method.
  60. >    If your region to be filled with pattern is not a
  61. >    polygon, then modify the seed-fill algorithm.
  62. >     Look at the Book by Foley, VanDam , Feihner and Hughes.
  63.  
  64.     Yeah. I'm thinking of modifying the seed-fill alg. But my
  65.     another real practical restrain is, I'm controlling a embroidery
  66.     machine, so one stitch must follow another stitch either next-to-next
  67.     or follow the boundary of the area. So seed-fill do requires quite
  68.     some modifications, and I'm working on it. But hope it does not
  69.     incurr to much time on overall performance.
  70.  
  71.  
  72. 3) This is from Steve Cunningham
  73.  
  74. > Your question on "point inside polygon" is prompted, you say, by a desire to
  75. > fill polygons with patterns.  I don't understand why this is a problem; just
  76. > take a standard scanline polygon fill and apply YourFavoritePatternProcess (tm)
  77. > to each point on the scanlines the fill generates.  This is quick, painless,
  78. > and a totally standard technique; see your favorite source for polygon fills.
  79.  
  80.     I wish I could do as if working in a scanline polyfill, but
  81.     this is not, (I think, any enlightenment?), applicable for me.
  82.  
  83.  
  84. Thanks again for the replies. Anyone have more info are REALLY appreicated
  85. to mail me.
  86.  
  87. --
  88. Medusa
  89. University of Hong Kong
  90. H8915726@hkuxa.hku.hk
  91.  
  92.