shn@allgfx.agi.oz (Si-Hanh NGUYEN) (02/26/90)
Does anybody know the detailed algorithm used in pr_vector() of Sun Pixrect ? The manual says that "pr_vector draws balanced vectors. (The technique used is to balance the Breshenham error term)". I have to fill some shapes which have straight edge(s) by pr_traprop(), and I would like these edges align perfectly with lines drawn by pr_vector() (or bold lines by pr_polygon_2()). I need to know how pr_vector() works in order to derive the bit vector of chain of those straight edges. I have tried the Bresenham algorithm from Foley an Van Dam. It works except when the line segment is in the 4th and 8th octant (Y-axis is from top to bottom and slope of the line segment is in ]0,-1[). Any help would be greatly appreciated. Si-Hanh Nguyen shn@allgfx.agi.oz
klassen@gvax.cs.cornell.edu (R. Victor Klassen) (03/07/90)
In article <1990Feb25.222157.26389@allgfx.agi.oz> shn@allgfx.agi.oz (Si-Hanh NGUYEN) writes: > >Does anybody know the detailed algorithm used in pr_vector() of Sun Pixrect ? >The manual says that "pr_vector draws balanced vectors. (The technique used >is to balance the Breshenham error term)". > There are two papers of which I am aware which address what I beleive to be the balancing to which the Sun manual refers. %A J. Boothroyd %A P.A. Hamilton %T Exactly reversible plotter paths %J Australian Computer Journal %V 2 %N 1 %P 20-21 %D 1970 %K reversible incremental interpolation %A D.E. Field %T Incremental linear interpolation %J ACM Transactions on Graphics %V 4 %N 1 %P 1-11 %D January 1985 %K DDA Bresenham scan conversion The issue is one of rounding down or toward zero. I don't have anything more at my fingertips, but I think you want to round down when you do the division in the initialization, which isn't what most processors do if you're in the wrong octant.
mpogue@dg.dg.com (Mike Pogue) (03/13/90)
In article <38280@cornell.UUCP> klassen@gvax.cs.cornell.edu (R. Victor Klassen) writes: >In article <1990Feb25.222157.26389@allgfx.agi.oz> shn@allgfx.agi.oz (Si-Hanh NGUYEN) writes: >> >>Does anybody know the detailed algorithm used in pr_vector() of Sun Pixrect ? >>The manual says that "pr_vector draws balanced vectors. (The technique used >>is to balance the Breshenham error term)". >> > Note that a very simple way to "balance" the error term involves reversing the end points before feeding them to Bresenham's algorithm, when the vector is in one of 4 octants (it doesn't matter which 4). This will guarantee that (A,B) = (B,A), and avoids writing code for 8 octants (and the associated balancing required). The disadvantage is that the line is drawn "backwards" in those 4 octants. Is this a problem? In my experience, since only one line is drawn at a time, no. Mike Pogue Data General Speaking for myself, not my company....