robinson@cs.wvu.wvnet.edu (John Robinson) (11/13/90)
I would like to know more about the implementation of regions on the Macintosh. I remember someone mentioning the use of "inversion points" in the Macintosh implementation. What exactly is the theory behind "inversion points"? Any references are welcome. But specifically I would like details on how to access the region description given a region handle so that I can manipulate the region eg: rotation, inversion, etc.
smoke@well.sf.ca.us (Nicholas Jackiw) (11/15/90)
In article <996@h.cs.wvu.wvnet.edu> robinson@cs.wvu.wvnet.edu (John Robinson) writes: >I would like to know more about the implementation of regions on the >Macintosh. I remember someone mentioning the use of "inversion points" >in the Macintosh implementation. What exactly is the theory behind >"inversion points"? Inversion points are points in a plane which toggle the contents of the plane below them and to their right as either being included or excluded from the region description. (Whether they are included or excluded depends upon the inversion points before them, hence a region must be an *ordered* list of these points.) For instance, the region X*****X ******* ******* ******X********* **************** X***********X can be entirely described by the five X's, ordered from left to right, top to bottom. (Not a precise example, actually--the asterisks should be pixels, and the X's interpixel points.) The region data structure simple contains a list of inversion lines (Y coordinates on which one or more inversion points are located), which in turn are lists of X coordinates on that Y value. Tags are used to indicate end of inversion line. (Y1 X1 X2 X3 tag Y2 X1 X2 tag Y3 ... tag tag, e.g.) I think the value of tag is 32767. As you can see, regions are very efficient for intersected and excluded rectangular areas, but are dreadful for things which include edges running neither parallel nor perpendicular to the axis. (45 degree edges are the worst case, requiring a new inversion point on each scan-line.) There have been a number of MacTutor articles dealing with regions over the years. I recommend looking in the index of Volumes #3 or #4 in your local technical bookstore. -Nick -- --- * --- Nicholas Jackiw Smoke@well.sf.ca.us | Jackiw@cs.swarthmore.edu Key Curriculum Press, Inc. Applelink: D3970 | (415) 548-2304 --- * ---