Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/eXene/graph-util/scan-convert.sml
ViewVC logotype

Annotation of /sml/trunk/src/eXene/graph-util/scan-convert.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2 - (view) (download)

1 : monnier 2 (* scan-convert.sml
2 :     *
3 :     * COPYRIGHT (c) 1994 by AT&T Bell Laboratories
4 :     *
5 :     * Code for scan converting a polygon specified as a list of
6 :     * points and a fill rule into even length list of points
7 :     * corresponding to scan line segments.
8 :     *
9 :     * The resulting list of points is ordered from bottom to top and
10 :     * from left to right.
11 :     *
12 :     * The algorithms are roughly based on those found in the sample X library.
13 :     *)
14 :    
15 :     structure ScanConvert :
16 :     sig
17 :     structure G : GEOMETRY
18 :    
19 :     datatype fill_rule = EvenOdd | Winding
20 :    
21 :     val scanConvert : G.point list * fill_rule -> G.point list
22 :    
23 :     end = struct
24 :    
25 :     structure G = Geometry
26 :    
27 :     open G
28 :    
29 :     datatype fill_rule = EvenOdd | Winding
30 :    
31 :     structure Bres =
32 :     struct
33 :     type bres_info = {
34 :     x : int, (* minor axis *)
35 :     d : int (* decision variable *)
36 :     }
37 :    
38 :     (*
39 :     * In scan converting polygons, we want to choose those pixels
40 :     * which are inside the polygon. Thus, we add .5 to the starting
41 :     * x coordinate for both left and right edges. Now we choose the
42 :     * first pixel which is inside the pgon for the left edge and the
43 :     * first pixel which is outside the pgon for the right edge.
44 :     * Draw the left pixel, but not the right.
45 :     *
46 :     * How to add .5 to the starting x coordinate:
47 :     * If the edge is moving to the right, then subtract dy from the
48 :     * error term from the general form of the algorithm.
49 :     * If the edge is moving to the left, then add dy to the error term.
50 :     *
51 :     * The reason for the difference between edges moving to the left
52 :     * and edges moving to the right is simple: If an edge is moving
53 :     * to the right, then we want the algorithm to flip immediately.
54 :     * If it is moving to the left, then we don't want it to flip until
55 :     * we traverse an entire pixel.
56 :     *)
57 :    
58 :     fun incr (m,m1,incr1,incr2) =
59 :     if m1 > 0
60 :     then fn {x,d} => if d > 0 then {x=x+m1,d=d+incr1} else {x=x+m,d=d+incr2}
61 :     else fn {x,d} => if d >= 0 then {x=x+m1,d=d+incr1} else {x=x+m,d=d+incr2}
62 :    
63 :     fun mkBresInfo (dy, x1, x2) = let (* assume dy > 0 *)
64 :     val dx = x2 - x1
65 :     val m = Int.quot(dx, dy)
66 :     in
67 :     if dx < 0 then
68 :     let val m1 = m - 1
69 :     val ix = ~(dx + dx)
70 :     val iy = dy + dy
71 :     val incr1 = ix + iy * m1
72 :     val incr2 = ix + iy * m
73 :     in
74 :     ({x = x1,d = m1 * iy + ix}, incr (m,m1,incr1,incr2))
75 :     end
76 :     else
77 :     let val m1 = m + 1
78 :     val ix = dx + dx
79 :     val iy = ~(dy + dy)
80 :     val incr1 = ix + iy * m1
81 :     val incr2 = ix + iy * m
82 :     in
83 :     ({x = x1, d = m * iy + ix}, incr (m,m1,incr1,incr2))
84 :     end
85 :     end
86 :     end (* structure Bres *)
87 :    
88 :     val largeCoord = 1000000
89 :     val smallCoord = ~largeCoord
90 :    
91 :     datatype edge = E of {
92 :     adv : Bres.bres_info -> Bres.bres_info, (* function to update Bresenham info *)
93 :     bres : Bres.bres_info ref, (* Bresenham info to run the edge *)
94 :     clockwise : bool, (* flag for winding number rule *)
95 :     ymax : int (* ycoord at which we exit this edge. *)
96 :     }
97 :    
98 :    
99 :     type scanline = int * edge list
100 :    
101 :     datatype edge_table = ET of {
102 :     ymax : int, (* ymax for the polygon *)
103 :     ymin : int, (* ymin for the polygon *)
104 :     scanlines : scanline list (* scanlines *)
105 :     }
106 :    
107 :     fun insertEdge (scanlines,miny : int,edge as E{bres= ref {x=minx,...},...}) = let
108 :     fun ine [] = [edge]
109 :     | ine (el as ((e as E{bres= ref {x,...},...})::rest)) =
110 :     if x < minx then e::(ine rest) else edge::el
111 :     fun ins [] = [(miny,[edge])]
112 :     | ins (sl as ((s as (y,edges))::rest)) =
113 :     if y < miny then s::(ins rest)
114 :     else if y = miny then (y,ine edges)::rest
115 :     else (miny,[edge])::sl
116 :     in ins scanlines end
117 :    
118 :     fun mkEdgeTable pts = let
119 :     (*
120 :     open Format
121 :     val fmt = formatf "make edge: topx %d topy %d botx %d boty %d cw %b\n"
122 :     (outputc std_out)
123 :     val fmt1 = formatf "number of scanlines = %d\n" (outputc std_out)
124 :     *)
125 :     fun mkEdge (ymax,clockwise,dy,topx,botx) = let
126 :     val (info,f) = Bres.mkBresInfo (dy,topx,botx)
127 :     in E {ymax=ymax,clockwise=clockwise,bres = ref info,adv=f} end
128 :     fun loop ([],prevpt,ymax,ymin,slines) =
129 :     ET{ymax=ymax,ymin=ymin,scanlines=slines}
130 :     | loop ((cp as PT{x,y})::rest,PT{x=x',y=y'},ymax,ymin,slines) = let
131 :     (* val _ = fmt1 [INT (length slines)] *)
132 :     val (botx,boty,topx,topy,clockwise) =
133 :     if y' > y then (x',y',x,y,false)
134 :     else (x,y,x',y',true)
135 :     in
136 :     if boty = topy then loop(rest,cp,ymax,ymin,slines)
137 :     else let
138 :     val dy = boty - topy
139 :     val e = mkEdge(boty-1,clockwise,boty-topy,topx,botx)
140 :     (* val _ = fmt [INT topx,INT topy,INT botx,INT boty,BOOL clockwise] *)
141 :     in
142 :     loop (
143 :     rest,
144 :     cp,
145 :     Int.max(y',ymax),
146 :     Int.min(y',ymin),
147 :     insertEdge(slines,topy,e))
148 :     end
149 :     end
150 :     in loop (pts, List.last pts, smallCoord, largeCoord, []) end
151 :    
152 :     fun getWinding edges = let
153 :     fun loop ([],_,_) = []
154 :     | loop ((e as E{clockwise,...})::es,isInside,inside) = let
155 :     val isInside' = if clockwise then isInside+1 else isInside-1
156 :     in
157 :     if inside = (isInside' <> 0) then e::(loop(es,isInside',not inside))
158 :     else loop(es,isInside',inside)
159 :     end
160 :     in loop (edges,0,true) end
161 :    
162 :     fun gtr(E{bres = ref {x,...},...},E{bres = ref {x=x',...},...}) = x > x'
163 :     val sorted = ListMergeSort.sorted gtr
164 :     val sort' = ListMergeSort.sort gtr
165 :     fun sort edges = if sorted edges then (edges,false) else (sort' edges, true)
166 :    
167 :     fun addActive ([],acs) = acs
168 :     | addActive (es,[]) = es
169 :     | addActive (el as (e as E{bres = ref {x,...},...})::es,
170 :     al as (a as E{bres = ref {x=ax,...},...})::acs) =
171 :     if x <= ax then e::(addActive(es,al)) else a::(addActive(el,acs))
172 :    
173 :     fun evenOdd (ET{ymin,ymax,scanlines}) = let
174 :     fun doEdges (y,edges,pts) = let
175 :     fun loop ([],es,pts) = (rev es,pts)
176 :     | loop ((e as E{ymax,adv,bres,...})::rest,es,pts) = let
177 :     val bi as {x,...} = !bres
178 :     in
179 :     if ymax = y then loop(rest,es,PT{x=x,y=y}::pts)
180 :     else (
181 :     bres := adv bi;
182 :     loop(rest,e::es,PT{x=x,y=y}::pts)
183 :     )
184 :     end
185 :     in loop (edges,[],pts) end
186 :     fun chkActive(y,[],active) = ([],active)
187 :     | chkActive(y,sl as ((y',edges)::rest),active) =
188 :     if y = y' then (rest,addActive(edges,active)) else (sl,active)
189 :     fun loop(y,scanlines,active,pts) =
190 :     if y = ymax then pts
191 :     else let
192 :     val (scanlines',active') = chkActive(y,scanlines,active)
193 :     val (active'',pts') = doEdges (y,active',pts)
194 :     in loop(y+1,scanlines',#1(sort active''), pts') end
195 :     in loop(ymin,scanlines,[],[]) end
196 :    
197 :     fun winding (ET{ymin,ymax,scanlines}) = let
198 :     fun doEdges (y,edges,ws,pts) = let
199 :     fun update (e as E{ymax,adv,bres,...},(es,fix)) =
200 :     if ymax = y then (es,true)
201 :     else (bres := adv (!bres); (e::es,fix))
202 :     fun finish (edges,es,pts) = let
203 :     fun f ([],(es,fix)) = (rev es,pts,fix)
204 :     | f (e::rest,es) = f (rest,update(e,es))
205 :     in f (edges,es) end
206 :     fun loop (edges,[],es,pts) = finish (edges,es,pts)
207 :     | loop (e::rest,wl as (E{bres = b',...}::ws),es,pts) = let
208 :     val E{bres = b as ref{x,...},...} = e
209 :     in
210 :     if b = b' then loop(rest,ws,update(e,es),PT{x=x,y=y}::pts)
211 :     else loop(rest,wl,update(e,es),pts)
212 :     end
213 :     | loop _ = raise LibBase.Impossible "ScanConvert.winding"
214 :     in loop (edges,ws,([],false),pts) end
215 :     fun chkActive(y,[],active,ws) = ([],active,ws)
216 :     | chkActive(y,sl as ((y',edges)::rest),active,ws) =
217 :     if y = y' then let
218 :     val acs = addActive(edges,active)
219 :     in (rest,acs,getWinding acs) end
220 :     else (sl,active,ws)
221 :     fun loop(y,scanlines,active,ws,pts) =
222 :     if y = ymax then pts
223 :     else let
224 :     val (scanlines',active',ws') = chkActive(y,scanlines,active,ws)
225 :     val (active'',pts',fix) = doEdges (y,active',ws',pts)
226 :     val (active''',changed) = sort active''
227 :     val ws'' = if fix orelse changed then getWinding active''' else active'''
228 :     in loop(y+1,scanlines',active''', ws'', pts') end
229 :     in loop(ymin,scanlines,[],[],[]) end
230 :    
231 :     fun scanConvert (pts, EvenOdd) = evenOdd(mkEdgeTable pts)
232 :     | scanConvert (pts, Winding) = winding(mkEdgeTable pts)
233 :    
234 :     end

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0