home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / sys / next / programm / 8097 < prev    next >
Encoding:
Internet Message Format  |  1993-01-12  |  4.3 KB
  1. Xref: sparky comp.sys.next.programmer:8097 comp.lang.postscript:6253
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!ames!olivea!mintaka.lcs.mit.edu!ai-lab!wheat-chex!bkph
  3. From: bkph@wheat-chex.ai.mit.edu (Berthold K.P. Horn)
  4. Newsgroups: comp.sys.next.programmer,comp.lang.postscript
  5. Subject: Re: Arcs and circles from curveto
  6. Message-ID: <1ivuifINNsji@life.ai.mit.edu>
  7. Date: 13 Jan 93 02:25:19 GMT
  8. References: <1993Jan11.014246.4735@drefla.mese.com> <1993Jan12.175132.27149@trilithon.mpk.ca.us>
  9. Organization: MIT Artificial Intelligence Lab
  10. Lines: 92
  11. NNTP-Posting-Host: wheat-chex.ai.mit.edu
  12. In-reply-to: henry@trilithon.mpk.ca.us's message of 12 Jan 93 17:51:32 GMT
  13.  
  14.  
  15. In article <1993Jan12.175132.27149@trilithon.mpk.ca.us> henry@trilithon.mpk.ca.us (Henry McGilton) writes:
  16.  
  17.    In article <1993Jan11.014246.4735@drefla.mese.com> matt@drefla.mese.com (Matt  
  18.    Brandt) writes:
  19.        *  I've been able to come up with a pretty good approximation
  20.        *  of a circle using curveto . . .
  21.    <<<<<   stuff deteleted  >>>>>>
  22.        *  of course, you can repeat for the bottom of the circle.
  23.        *  Like I said though, this is only an approximation. Does
  24.        *  anybody out there have a better approximation of circle
  25.        *  drawing using curveto? I need to do it this way for bizarre
  26.        *  reasons and I would like to improve the accuracy a little bit.
  27.  
  28.    You can't get an accurate enough circle with only two curves.  You
  29.    need one curve per quadrant, and you draw four of them.  The ``magic
  30.    number'' for the circle is  0.555.  Here's an example which you
  31.    can hack to your needs.
  32.  
  33.            %!PS
  34.            /R 288 def
  35.            /M R 0.555 mul def
  36.            306 396 translate
  37.            R 0 moveto
  38.            R M dup R dup 0 exch curveto
  39.            M neg R dup neg M R neg 0 curveto
  40.            R neg M neg dup R neg dup 0 exch curveto
  41.            M R neg R M neg R 0 curveto
  42.            closepath
  43.            stroke
  44.  
  45.    I cross posted this to comp.lang.postscript, because, as Eric Scott
  46.    pointed out, this topic is pure PostScript and only tangentially
  47.    NeXT related.
  48.  
  49.  
  50.        ........  Henry
  51.  
  52. Addendum: Approximating circular arcs with Bezier curves:
  53.  
  54. The smaller the angle of the circular arc the better an
  55. approximation you can get out of a Bezier curve, obviously.
  56. For a unit radius circle, a good approximation
  57. of an arc turning through angle theta uses
  58.  
  59.     eta = (4/3) (1 - cos(theta/2)) / sin(theta/2)
  60.  
  61. where eta is the distance of the control points from the knots,
  62. measured along a line tangent at the knots (sorry you'll
  63. have to draw the figure yourself, my ASCII curve drawing skills
  64. are unequal to the task).
  65.  
  66. For  theta=pi/2  you get  eta = (4/3)(sqrt(2) - 1) = .55228...
  67. which yields a very good approximation to a quadrant of a circle
  68.  
  69. For  theta=pi  you get  eta = (4/3) = 1.33333....
  70. which is a not so good approximation of a semicircle.
  71.  
  72. In the limit as theta tends to zero, by the way, the control
  73. points end up 2/3 of the way from the knots to the
  74. intersection of the tangents.  This is a quick and dirty way 
  75. to generate a good approximation, if breaking up an arc into 
  76. many pieces is not a concern.
  77.  
  78. By the way, the above approximations all have the Bezier curve
  79. departing from the true arc in one direction (error always has 
  80. the same sign).  One can do twice as well by balancing the
  81. positive and the negative errors, but then no closed form 
  82. solution to the problem appears to be at hand.  
  83. For  theta=pi/2  the optimum is 
  84.  
  85.     eta = .5541...
  86.  
  87. The same technique can obviously be used for ellipses, since
  88. ellipses are circles on an anisotropically scaled coordinate system.
  89. Super-ellipses can also be very well aproximated by Bezier curves
  90. (super-ellipses have equations of the form (x/a)^beta + (y/b)^beta = 1).
  91.  
  92. Cubic `splines' are quite `flexible' since they have 8 parameters (2 knots
  93. and 2 control points).  On average, it takes twice as many quadratic splines
  94. to describe a shape adequately as it does cubic splines.
  95.  
  96. Exercise for the reader:
  97.  
  98. Suppose you draw a pen-stroke with a pen that has a circular nib, where the
  99. center of stroke follows a given Bezier curve.  Can the `outer' and `inner'
  100. edges of the resulting shape be described exactly using a Bexier curve?
  101. If not, how do you compute an adequate approximation - one that does not
  102. require splicing together too many separate cubic splines?
  103.  
  104. Berthold K.P. Horn
  105. Cambridge, Massachusetts, USA
  106.