1 /*------------------------------------------------------------------------ |
|
2 * |
|
3 * OpenVG 1.1 Reference Implementation |
|
4 * ----------------------------------- |
|
5 * |
|
6 * Copyright (c) 2007 The Khronos Group Inc. |
|
7 * |
|
8 * Permission is hereby granted, free of charge, to any person obtaining a |
|
9 * copy of this software and /or associated documentation files |
|
10 * (the "Materials "), to deal in the Materials without restriction, |
|
11 * including without limitation the rights to use, copy, modify, merge, |
|
12 * publish, distribute, sublicense, and/or sell copies of the Materials, |
|
13 * and to permit persons to whom the Materials are furnished to do so, |
|
14 * subject to the following conditions: |
|
15 * |
|
16 * The above copyright notice and this permission notice shall be included |
|
17 * in all copies or substantial portions of the Materials. |
|
18 * |
|
19 * THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
|
20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
|
21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
|
22 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, |
|
23 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR |
|
24 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE MATERIALS OR |
|
25 * THE USE OR OTHER DEALINGS IN THE MATERIALS. |
|
26 * |
|
27 *//** |
|
28 * \file |
|
29 * \brief Implementation of polygon rasterizer. |
|
30 * \note |
|
31 *//*-------------------------------------------------------------------*/ |
|
32 |
|
33 #include "riRasterizer.h" |
|
34 |
|
35 //============================================================================================== |
|
36 |
|
37 namespace OpenVGRI |
|
38 { |
|
39 |
|
40 /*-------------------------------------------------------------------*//*! |
|
41 * \brief Rasterizer constructor. |
|
42 * \param |
|
43 * \return |
|
44 * \note |
|
45 *//*-------------------------------------------------------------------*/ |
|
46 |
|
47 Rasterizer::Rasterizer() : |
|
48 m_edges(), |
|
49 m_scissorEdges(), |
|
50 m_scissor(false), |
|
51 m_samples(), |
|
52 m_numSamples(0), |
|
53 m_numFSAASamples(0), |
|
54 m_sumWeights(0.0f), |
|
55 m_sampleRadius(0.0f), |
|
56 m_vpx(0), |
|
57 m_vpy(0), |
|
58 m_vpwidth(0), |
|
59 m_vpheight(0), |
|
60 m_fillRule(VG_EVEN_ODD), |
|
61 m_pixelPipe(NULL), |
|
62 m_covBuffer(NULL) |
|
63 {} |
|
64 |
|
65 /*-------------------------------------------------------------------*//*! |
|
66 * \brief Rasterizer destructor. |
|
67 * \param |
|
68 * \return |
|
69 * \note |
|
70 *//*-------------------------------------------------------------------*/ |
|
71 |
|
72 Rasterizer::~Rasterizer() |
|
73 { |
|
74 } |
|
75 |
|
76 /*-------------------------------------------------------------------*//*! |
|
77 * \brief Removes all appended edges. |
|
78 * \param |
|
79 * \return |
|
80 * \note |
|
81 *//*-------------------------------------------------------------------*/ |
|
82 |
|
83 void Rasterizer::clear() |
|
84 { |
|
85 m_edges.clear(); |
|
86 m_edgeMin.set(RI_FLOAT_MAX, RI_FLOAT_MAX); |
|
87 m_edgeMax.set(-RI_FLOAT_MAX, -RI_FLOAT_MAX); |
|
88 } |
|
89 |
|
90 /*-------------------------------------------------------------------*//*! |
|
91 * \brief Appends an edge to the rasterizer. |
|
92 * \param |
|
93 * \return |
|
94 * \note |
|
95 *//*-------------------------------------------------------------------*/ |
|
96 |
|
97 void Rasterizer::addBBox(const Vector2& v) |
|
98 { |
|
99 if(v.x < m_edgeMin.x) m_edgeMin.x = v.x; |
|
100 if(v.y < m_edgeMin.y) m_edgeMin.y = v.y; |
|
101 if(v.x > m_edgeMax.x) m_edgeMax.x = v.x; |
|
102 if(v.y > m_edgeMax.y) m_edgeMax.y = v.y; |
|
103 } |
|
104 |
|
105 void Rasterizer::addEdge(const Vector2& v0, const Vector2& v1) |
|
106 { |
|
107 if( m_edges.size() >= RI_MAX_EDGES ) |
|
108 throw std::bad_alloc(); //throw an out of memory error if there are too many edges |
|
109 |
|
110 if(v0.y == v1.y) |
|
111 return; //skip horizontal edges (they don't affect rasterization since we scan horizontally) |
|
112 |
|
113 Edge e; |
|
114 if(v0.y < v1.y) |
|
115 { //edge is going upward |
|
116 e.v0 = v0; |
|
117 e.v1 = v1; |
|
118 e.direction = 1; |
|
119 } |
|
120 else |
|
121 { //edge is going downward |
|
122 e.v0 = v1; |
|
123 e.v1 = v0; |
|
124 e.direction = -1; |
|
125 } |
|
126 |
|
127 addBBox(v0); |
|
128 addBBox(v1); |
|
129 |
|
130 m_edges.push_back(e); //throws bad_alloc |
|
131 } |
|
132 |
|
133 /*-------------------------------------------------------------------*//*! |
|
134 * \brief Set up rasterizer |
|
135 * \param |
|
136 * \return |
|
137 * \note |
|
138 *//*-------------------------------------------------------------------*/ |
|
139 |
|
140 void Rasterizer::setup(int vpx, int vpy, int vpwidth, int vpheight, VGFillRule fillRule, const PixelPipe* pixelPipe, unsigned int* covBuffer) |
|
141 { |
|
142 RI_ASSERT(vpwidth >= 0 && vpheight >= 0); |
|
143 RI_ASSERT(vpx + vpwidth >= vpx && vpy + vpheight >= vpy); |
|
144 RI_ASSERT(fillRule == VG_EVEN_ODD || fillRule == VG_NON_ZERO); |
|
145 RI_ASSERT(pixelPipe || covBuffer); |
|
146 m_vpx = vpx; |
|
147 m_vpy = vpy; |
|
148 m_vpwidth = vpwidth; |
|
149 m_vpheight = vpheight; |
|
150 m_fillRule = fillRule; |
|
151 m_pixelPipe = pixelPipe; |
|
152 m_covBuffer = covBuffer; |
|
153 m_covMinx = vpx+vpwidth; |
|
154 m_covMiny = vpy+vpheight; |
|
155 m_covMaxx = vpx; |
|
156 m_covMaxy = vpy; |
|
157 } |
|
158 |
|
159 /*-------------------------------------------------------------------*//*! |
|
160 * \brief Sets scissor rectangles. |
|
161 * \param |
|
162 * \return |
|
163 * \note |
|
164 *//*-------------------------------------------------------------------*/ |
|
165 |
|
166 void Rasterizer::setScissor(const Array<Rectangle>& scissors) |
|
167 { |
|
168 m_scissor = true; |
|
169 try |
|
170 { |
|
171 m_scissorEdges.clear(); |
|
172 for(int i=0;i<scissors.size();i++) |
|
173 { |
|
174 if(scissors[i].width > 0 && scissors[i].height > 0) |
|
175 { |
|
176 ScissorEdge e; |
|
177 e.miny = scissors[i].y; |
|
178 e.maxy = RI_INT_ADDSATURATE(scissors[i].y, scissors[i].height); |
|
179 |
|
180 e.x = scissors[i].x; |
|
181 e.direction = 1; |
|
182 m_scissorEdges.push_back(e); //throws bad_alloc |
|
183 e.x = RI_INT_ADDSATURATE(scissors[i].x, scissors[i].width); |
|
184 e.direction = -1; |
|
185 m_scissorEdges.push_back(e); //throws bad_alloc |
|
186 } |
|
187 } |
|
188 } |
|
189 catch(std::bad_alloc) |
|
190 { |
|
191 m_scissorEdges.clear(); |
|
192 throw; |
|
193 } |
|
194 } |
|
195 |
|
196 /*-------------------------------------------------------------------*//*! |
|
197 * \brief Returns a radical inverse of a given integer for Hammersley |
|
198 * point set. |
|
199 * \param |
|
200 * \return |
|
201 * \note |
|
202 *//*-------------------------------------------------------------------*/ |
|
203 |
|
204 static double radicalInverseBase2(unsigned int i) |
|
205 { |
|
206 if( i == 0 ) |
|
207 return 0.0; |
|
208 double p = 0.0; |
|
209 double f = 0.5; |
|
210 double ff = f; |
|
211 for(unsigned int j=0;j<32;j++) |
|
212 { |
|
213 if( i & (1<<j) ) |
|
214 p += f; |
|
215 f *= ff; |
|
216 } |
|
217 return p; |
|
218 } |
|
219 |
|
220 /*-------------------------------------------------------------------*//*! |
|
221 * \brief Calls PixelPipe::pixelPipe for each pixel with coverage greater |
|
222 * than zero. |
|
223 * \param |
|
224 * \return |
|
225 * \note |
|
226 *//*-------------------------------------------------------------------*/ |
|
227 |
|
228 int Rasterizer::setupSamplingPattern(VGRenderingQuality renderingQuality, int numFSAASamples) |
|
229 { |
|
230 RI_ASSERT(renderingQuality == VG_RENDERING_QUALITY_NONANTIALIASED || |
|
231 renderingQuality == VG_RENDERING_QUALITY_FASTER || |
|
232 renderingQuality == VG_RENDERING_QUALITY_BETTER); |
|
233 RI_ASSERT(numFSAASamples > 0 && numFSAASamples <= RI_MAX_SAMPLES); |
|
234 |
|
235 //make a sampling pattern |
|
236 m_sumWeights = 0.0f; |
|
237 m_sampleRadius = 0.0f; //max offset of the sampling points from a pixel center |
|
238 m_numFSAASamples = numFSAASamples; |
|
239 if(numFSAASamples == 1) |
|
240 { |
|
241 if(renderingQuality == VG_RENDERING_QUALITY_NONANTIALIASED) |
|
242 { |
|
243 m_numSamples = 1; |
|
244 m_samples[0].x = 0.0f; |
|
245 m_samples[0].y = 0.0f; |
|
246 m_samples[0].weight = 1.0f; |
|
247 m_sampleRadius = 0.0f; |
|
248 m_sumWeights = 1.0f; |
|
249 } |
|
250 else if(renderingQuality == VG_RENDERING_QUALITY_FASTER) |
|
251 { //box filter of diameter 1.0f, 8-queen sampling pattern |
|
252 m_numSamples = 8; |
|
253 m_samples[0].x = 3; |
|
254 m_samples[1].x = 7; |
|
255 m_samples[2].x = 0; |
|
256 m_samples[3].x = 2; |
|
257 m_samples[4].x = 5; |
|
258 m_samples[5].x = 1; |
|
259 m_samples[6].x = 6; |
|
260 m_samples[7].x = 4; |
|
261 for(int i=0;i<m_numSamples;i++) |
|
262 { |
|
263 m_samples[i].x = (m_samples[i].x + 0.5f) / (RScalar)m_numSamples - 0.5f; |
|
264 m_samples[i].y = ((RScalar)i + 0.5f) / (RScalar)m_numSamples - 0.5f; |
|
265 m_samples[i].weight = 1.0f / (RScalar)m_numSamples; |
|
266 m_sumWeights += m_samples[i].weight; |
|
267 } |
|
268 m_sampleRadius = 0.5f; |
|
269 } |
|
270 else |
|
271 { |
|
272 RI_ASSERT(renderingQuality == VG_RENDERING_QUALITY_BETTER); |
|
273 m_numSamples = RI_MAX_SAMPLES; |
|
274 m_sampleRadius = 0.75f; |
|
275 for(int i=0;i<m_numSamples;i++) |
|
276 { //Gaussian filter, implemented using Hammersley point set for sample point locations |
|
277 RScalar x = (RScalar)radicalInverseBase2(i); |
|
278 RScalar y = ((RScalar)i + 0.5f) / (RScalar)m_numSamples; |
|
279 RI_ASSERT(x >= 0.0f && x < 1.0f); |
|
280 RI_ASSERT(y >= 0.0f && y < 1.0f); |
|
281 |
|
282 //map unit square to unit circle |
|
283 RScalar r = (RScalar)sqrt(x) * m_sampleRadius; |
|
284 x = r * (RScalar)sin(y*2.0f*PI); |
|
285 y = r * (RScalar)cos(y*2.0f*PI); |
|
286 m_samples[i].weight = (RScalar)exp(-0.5f * RI_SQR(r/m_sampleRadius)); |
|
287 |
|
288 RI_ASSERT(x >= -1.5f && x <= 1.5f && y >= -1.5f && y <= 1.5f); //the specification restricts the filter radius to be less than or equal to 1.5 |
|
289 |
|
290 m_samples[i].x = x; |
|
291 m_samples[i].y = y; |
|
292 m_sumWeights += m_samples[i].weight; |
|
293 } |
|
294 } |
|
295 } |
|
296 else |
|
297 { //box filter |
|
298 m_numSamples = numFSAASamples; |
|
299 RI_ASSERT(numFSAASamples >= 1 && numFSAASamples <= 32); //sample mask is a 32-bit uint => can't support more than 32 samples |
|
300 //use Hammersley point set as a sampling pattern |
|
301 for(int i=0;i<m_numSamples;i++) |
|
302 { |
|
303 m_samples[i].x = (RScalar)radicalInverseBase2(i) + 1.0f / (RScalar)(m_numSamples<<1) - 0.5f; |
|
304 m_samples[i].y = ((RScalar)i + 0.5f) / (RScalar)m_numSamples - 0.5f; |
|
305 m_samples[i].weight = 1.0f; |
|
306 RI_ASSERT(m_samples[i].x > -0.5f && m_samples[i].x < 0.5f); |
|
307 RI_ASSERT(m_samples[i].y > -0.5f && m_samples[i].y < 0.5f); |
|
308 } |
|
309 m_sumWeights = (RScalar)m_numSamples; |
|
310 m_sampleRadius = 0.5f; |
|
311 } |
|
312 return m_numSamples; |
|
313 } |
|
314 |
|
315 /*-------------------------------------------------------------------*//*! |
|
316 * \brief Calls PixelPipe::pixelPipe for each pixel with coverage greater |
|
317 * than zero. |
|
318 * \param |
|
319 * \return |
|
320 * \note |
|
321 *//*-------------------------------------------------------------------*/ |
|
322 |
|
323 void Rasterizer::fill() |
|
324 { |
|
325 if(m_scissor && !m_scissorEdges.size()) |
|
326 return; //scissoring is on, but there are no scissor rectangles => nothing is visible |
|
327 |
|
328 //proceed scanline by scanline |
|
329 //keep track of edges that can intersect the pixel filters of the current scanline (Active Edge Table) |
|
330 //until all pixels of the scanline have been processed |
|
331 // for all sampling points of the current pixel |
|
332 // determine the winding number using edge functions |
|
333 // add filter weight to coverage |
|
334 // divide coverage by the number of samples |
|
335 // determine a run of pixels with constant coverage |
|
336 // call fill callback for each pixel of the run |
|
337 |
|
338 int fillRuleMask = 1; |
|
339 if(m_fillRule == VG_NON_ZERO) |
|
340 fillRuleMask = -1; |
|
341 |
|
342 int bbminx = (int)floor(m_edgeMin.x); |
|
343 int bbminy = (int)floor(m_edgeMin.y); |
|
344 int bbmaxx = (int)floor(m_edgeMax.x)+1; |
|
345 int bbmaxy = (int)floor(m_edgeMax.y)+1; |
|
346 int sx = RI_INT_MAX(m_vpx, bbminx); |
|
347 int ex = RI_INT_MIN(m_vpx+m_vpwidth, bbmaxx); |
|
348 int sy = RI_INT_MAX(m_vpy, bbminy); |
|
349 int ey = RI_INT_MIN(m_vpy+m_vpheight, bbmaxy); |
|
350 if(sx < m_covMinx) m_covMinx = sx; |
|
351 if(sy < m_covMiny) m_covMiny = sy; |
|
352 if(ex > m_covMaxx) m_covMaxx = ex; |
|
353 if(ey > m_covMaxy) m_covMaxy = ey; |
|
354 |
|
355 //fill the screen |
|
356 Array<ActiveEdge> aet; |
|
357 Array<ScissorEdge> scissorAet; |
|
358 for(int j=sy;j<ey;j++) |
|
359 { |
|
360 //gather scissor edges intersecting this scanline |
|
361 scissorAet.clear(); |
|
362 if( m_scissor ) |
|
363 { |
|
364 for(int e=0;e<m_scissorEdges.size();e++) |
|
365 { |
|
366 const ScissorEdge& se = m_scissorEdges[e]; |
|
367 if(j >= se.miny && j < se.maxy) |
|
368 scissorAet.push_back(m_scissorEdges[e]); //throws bad_alloc |
|
369 } |
|
370 if(!scissorAet.size()) |
|
371 continue; //scissoring is on, but there are no scissor rectangles on this scanline |
|
372 } |
|
373 |
|
374 //simple AET: scan through all the edges and pick the ones intersecting this scanline |
|
375 aet.clear(); |
|
376 for(int e=0;e<m_edges.size();e++) |
|
377 { |
|
378 RScalar cminy = (RScalar)j - m_sampleRadius + 0.5f; |
|
379 RScalar cmaxy = (RScalar)j + m_sampleRadius + 0.5f; |
|
380 const Edge& ed = m_edges[e]; |
|
381 RI_ASSERT(ed.v0.y <= ed.v1.y); //horizontal edges should have been dropped already |
|
382 |
|
383 ActiveEdge ae; |
|
384 ae.v0 = ed.v0; |
|
385 ae.v1 = ed.v1; |
|
386 ae.direction = ed.direction; |
|
387 |
|
388 if(cmaxy >= ae.v0.y && cminy < ae.v1.y) |
|
389 { |
|
390 ae.n.set(ae.v0.y - ae.v1.y, ae.v1.x - ae.v0.x); //edge normal |
|
391 ae.cnst = ae.v0.x * ae.n.x + ae.v0.y * ae.n.y; //distance of v0 from the origin along the edge normal |
|
392 |
|
393 //compute edge min and max x-coordinates for this scanline |
|
394 Vector2 vd(ae.v1.x - ae.v0.x, ae.v1.y - ae.v0.y); |
|
395 RScalar wl = 1.0f / vd.y; |
|
396 RScalar sx = ae.v0.x + vd.x * (cminy - ae.v0.y) * wl; |
|
397 RScalar ex = ae.v0.x + vd.x * (cmaxy - ae.v0.y) * wl; |
|
398 RScalar bminx = RI_MIN(ae.v0.x, ae.v1.x); |
|
399 RScalar bmaxx = RI_MAX(ae.v0.x, ae.v1.x); |
|
400 sx = RI_CLAMP(sx, bminx, bmaxx); |
|
401 ex = RI_CLAMP(ex, bminx, bmaxx); |
|
402 ae.minx = RI_MIN(sx,ex); |
|
403 ae.maxx = RI_MAX(sx,ex); |
|
404 aet.push_back(ae); //throws bad_alloc |
|
405 } |
|
406 } |
|
407 if(!aet.size()) |
|
408 continue; //no edges on the whole scanline, skip it |
|
409 |
|
410 //sort AET by edge minx |
|
411 aet.sort(); |
|
412 |
|
413 //sort scissor AET by edge x |
|
414 scissorAet.sort(); |
|
415 |
|
416 //fill the scanline |
|
417 int scissorWinding = m_scissor ? 0 : 1; //if scissoring is off, winding is always 1 |
|
418 int scissorIndex = 0; |
|
419 int aes = 0; |
|
420 int aen = 0; |
|
421 for(int i=sx;i<ex;) |
|
422 { |
|
423 Vector2 pc(i + 0.5f, j + 0.5f); //pixel center |
|
424 |
|
425 //find edges that intersect or are to the left of the pixel antialiasing filter |
|
426 while(aes < aet.size() && pc.x + m_sampleRadius >= aet[aes].minx) |
|
427 aes++; |
|
428 //edges [0,aes[ may have an effect on winding, and need to be evaluated while sampling |
|
429 |
|
430 //compute coverage |
|
431 RScalar coverage = 0.0f; |
|
432 unsigned int sampleMask = 0; |
|
433 for(int s=0;s<m_numSamples;s++) |
|
434 { |
|
435 Vector2 sp = pc; //sampling point |
|
436 sp.x += m_samples[s].x; |
|
437 sp.y += m_samples[s].y; |
|
438 |
|
439 //compute winding number by evaluating the edge functions of edges to the left of the sampling point |
|
440 int winding = 0; |
|
441 for(int e=0;e<aes;e++) |
|
442 { |
|
443 if(sp.y >= aet[e].v0.y && sp.y < aet[e].v1.y) |
|
444 { //evaluate edge function to determine on which side of the edge the sampling point lies |
|
445 RScalar side = sp.x * aet[e].n.x + sp.y * aet[e].n.y - aet[e].cnst; |
|
446 if(side <= 0.0f) //implicit tie breaking: a sampling point on an opening edge is in, on a closing edge it's out |
|
447 { |
|
448 winding += aet[e].direction; |
|
449 } |
|
450 } |
|
451 } |
|
452 if(winding & fillRuleMask) |
|
453 { |
|
454 coverage += m_samples[s].weight; |
|
455 sampleMask |= (unsigned int)(1<<s); |
|
456 } |
|
457 } |
|
458 |
|
459 //constant coverage optimization: |
|
460 //scan AET from left to right and skip all the edges that are completely to the left of the pixel filter. |
|
461 //since AET is sorted by minx, the edge we stop at is the leftmost of the edges we haven't passed yet. |
|
462 //if that edge is to the right of this pixel, coverage is constant between this pixel and the start of the edge. |
|
463 while(aen < aet.size() && aet[aen].maxx < pc.x - m_sampleRadius - 0.01f) //0.01 is a safety region to prevent too aggressive optimization due to numerical inaccuracy |
|
464 aen++; |
|
465 |
|
466 int endSpan = m_vpx + m_vpwidth; //endSpan is the first pixel NOT part of the span |
|
467 if(aen < aet.size()) |
|
468 endSpan = RI_INT_MAX(i+1, RI_INT_MIN(endSpan, (int)ceil(aet[aen].minx - m_sampleRadius - 0.5f))); |
|
469 |
|
470 coverage /= m_sumWeights; |
|
471 RI_ASSERT(coverage >= 0.0f && coverage <= 1.0f); |
|
472 |
|
473 //fill a run of pixels with constant coverage |
|
474 if(sampleMask) |
|
475 { |
|
476 for(;i<endSpan;i++) |
|
477 { |
|
478 //update scissor winding number |
|
479 while(scissorIndex < scissorAet.size() && scissorAet[scissorIndex].x <= i) |
|
480 scissorWinding += scissorAet[scissorIndex++].direction; |
|
481 RI_ASSERT(scissorWinding >= 0); |
|
482 |
|
483 if(scissorWinding) |
|
484 { |
|
485 if(m_covBuffer) |
|
486 m_covBuffer[j*m_vpwidth+i] |= (RIuint32)sampleMask; |
|
487 else |
|
488 m_pixelPipe->pixelPipe(i, j, coverage, sampleMask); |
|
489 } |
|
490 } |
|
491 } |
|
492 i = endSpan; |
|
493 } |
|
494 } |
|
495 } |
|
496 |
|
497 //======================================================================= |
|
498 |
|
499 } //namespace OpenVGRI |
|