--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/egl/sfopenvg/riRasterizer.cpp Wed May 12 11:20:41 2010 +0100
@@ -0,0 +1,499 @@
+/*------------------------------------------------------------------------
+ *
+ * OpenVG 1.1 Reference Implementation
+ * -----------------------------------
+ *
+ * Copyright (c) 2007 The Khronos Group Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and /or associated documentation files
+ * (the "Materials "), to deal in the Materials without restriction,
+ * including without limitation the rights to use, copy, modify, merge,
+ * publish, distribute, sublicense, and/or sell copies of the Materials,
+ * and to permit persons to whom the Materials are furnished to do so,
+ * subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Materials.
+ *
+ * THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+ * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+ * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE MATERIALS OR
+ * THE USE OR OTHER DEALINGS IN THE MATERIALS.
+ *
+ *//**
+ * \file
+ * \brief Implementation of polygon rasterizer.
+ * \note
+ *//*-------------------------------------------------------------------*/
+
+#include "riRasterizer.h"
+
+//==============================================================================================
+
+namespace OpenVGRI
+{
+
+/*-------------------------------------------------------------------*//*!
+* \brief Rasterizer constructor.
+* \param
+* \return
+* \note
+*//*-------------------------------------------------------------------*/
+
+Rasterizer::Rasterizer() :
+ m_edges(),
+ m_scissorEdges(),
+ m_scissor(false),
+ m_samples(),
+ m_numSamples(0),
+ m_numFSAASamples(0),
+ m_sumWeights(0.0f),
+ m_sampleRadius(0.0f),
+ m_vpx(0),
+ m_vpy(0),
+ m_vpwidth(0),
+ m_vpheight(0),
+ m_fillRule(VG_EVEN_ODD),
+ m_pixelPipe(NULL),
+ m_covBuffer(NULL)
+{}
+
+/*-------------------------------------------------------------------*//*!
+* \brief Rasterizer destructor.
+* \param
+* \return
+* \note
+*//*-------------------------------------------------------------------*/
+
+Rasterizer::~Rasterizer()
+{
+}
+
+/*-------------------------------------------------------------------*//*!
+* \brief Removes all appended edges.
+* \param
+* \return
+* \note
+*//*-------------------------------------------------------------------*/
+
+void Rasterizer::clear()
+{
+ m_edges.clear();
+ m_edgeMin.set(RI_FLOAT_MAX, RI_FLOAT_MAX);
+ m_edgeMax.set(-RI_FLOAT_MAX, -RI_FLOAT_MAX);
+}
+
+/*-------------------------------------------------------------------*//*!
+* \brief Appends an edge to the rasterizer.
+* \param
+* \return
+* \note
+*//*-------------------------------------------------------------------*/
+
+void Rasterizer::addBBox(const Vector2& v)
+{
+ if(v.x < m_edgeMin.x) m_edgeMin.x = v.x;
+ if(v.y < m_edgeMin.y) m_edgeMin.y = v.y;
+ if(v.x > m_edgeMax.x) m_edgeMax.x = v.x;
+ if(v.y > m_edgeMax.y) m_edgeMax.y = v.y;
+}
+
+void Rasterizer::addEdge(const Vector2& v0, const Vector2& v1)
+{
+ if( m_edges.size() >= RI_MAX_EDGES )
+ throw std::bad_alloc(); //throw an out of memory error if there are too many edges
+
+ if(v0.y == v1.y)
+ return; //skip horizontal edges (they don't affect rasterization since we scan horizontally)
+
+ Edge e;
+ if(v0.y < v1.y)
+ { //edge is going upward
+ e.v0 = v0;
+ e.v1 = v1;
+ e.direction = 1;
+ }
+ else
+ { //edge is going downward
+ e.v0 = v1;
+ e.v1 = v0;
+ e.direction = -1;
+ }
+
+ addBBox(v0);
+ addBBox(v1);
+
+ m_edges.push_back(e); //throws bad_alloc
+}
+
+/*-------------------------------------------------------------------*//*!
+* \brief Set up rasterizer
+* \param
+* \return
+* \note
+*//*-------------------------------------------------------------------*/
+
+void Rasterizer::setup(int vpx, int vpy, int vpwidth, int vpheight, VGFillRule fillRule, const PixelPipe* pixelPipe, unsigned int* covBuffer)
+{
+ RI_ASSERT(vpwidth >= 0 && vpheight >= 0);
+ RI_ASSERT(vpx + vpwidth >= vpx && vpy + vpheight >= vpy);
+ RI_ASSERT(fillRule == VG_EVEN_ODD || fillRule == VG_NON_ZERO);
+ RI_ASSERT(pixelPipe || covBuffer);
+ m_vpx = vpx;
+ m_vpy = vpy;
+ m_vpwidth = vpwidth;
+ m_vpheight = vpheight;
+ m_fillRule = fillRule;
+ m_pixelPipe = pixelPipe;
+ m_covBuffer = covBuffer;
+ m_covMinx = vpx+vpwidth;
+ m_covMiny = vpy+vpheight;
+ m_covMaxx = vpx;
+ m_covMaxy = vpy;
+}
+
+/*-------------------------------------------------------------------*//*!
+* \brief Sets scissor rectangles.
+* \param
+* \return
+* \note
+*//*-------------------------------------------------------------------*/
+
+void Rasterizer::setScissor(const Array<Rectangle>& scissors)
+{
+ m_scissor = true;
+ try
+ {
+ m_scissorEdges.clear();
+ for(int i=0;i<scissors.size();i++)
+ {
+ if(scissors[i].width > 0 && scissors[i].height > 0)
+ {
+ ScissorEdge e;
+ e.miny = scissors[i].y;
+ e.maxy = RI_INT_ADDSATURATE(scissors[i].y, scissors[i].height);
+
+ e.x = scissors[i].x;
+ e.direction = 1;
+ m_scissorEdges.push_back(e); //throws bad_alloc
+ e.x = RI_INT_ADDSATURATE(scissors[i].x, scissors[i].width);
+ e.direction = -1;
+ m_scissorEdges.push_back(e); //throws bad_alloc
+ }
+ }
+ }
+ catch(std::bad_alloc)
+ {
+ m_scissorEdges.clear();
+ throw;
+ }
+}
+
+/*-------------------------------------------------------------------*//*!
+* \brief Returns a radical inverse of a given integer for Hammersley
+* point set.
+* \param
+* \return
+* \note
+*//*-------------------------------------------------------------------*/
+
+static double radicalInverseBase2(unsigned int i)
+{
+ if( i == 0 )
+ return 0.0;
+ double p = 0.0;
+ double f = 0.5;
+ double ff = f;
+ for(unsigned int j=0;j<32;j++)
+ {
+ if( i & (1<<j) )
+ p += f;
+ f *= ff;
+ }
+ return p;
+}
+
+/*-------------------------------------------------------------------*//*!
+* \brief Calls PixelPipe::pixelPipe for each pixel with coverage greater
+* than zero.
+* \param
+* \return
+* \note
+*//*-------------------------------------------------------------------*/
+
+int Rasterizer::setupSamplingPattern(VGRenderingQuality renderingQuality, int numFSAASamples)
+{
+ RI_ASSERT(renderingQuality == VG_RENDERING_QUALITY_NONANTIALIASED ||
+ renderingQuality == VG_RENDERING_QUALITY_FASTER ||
+ renderingQuality == VG_RENDERING_QUALITY_BETTER);
+ RI_ASSERT(numFSAASamples > 0 && numFSAASamples <= RI_MAX_SAMPLES);
+
+ //make a sampling pattern
+ m_sumWeights = 0.0f;
+ m_sampleRadius = 0.0f; //max offset of the sampling points from a pixel center
+ m_numFSAASamples = numFSAASamples;
+ if(numFSAASamples == 1)
+ {
+ if(renderingQuality == VG_RENDERING_QUALITY_NONANTIALIASED)
+ {
+ m_numSamples = 1;
+ m_samples[0].x = 0.0f;
+ m_samples[0].y = 0.0f;
+ m_samples[0].weight = 1.0f;
+ m_sampleRadius = 0.0f;
+ m_sumWeights = 1.0f;
+ }
+ else if(renderingQuality == VG_RENDERING_QUALITY_FASTER)
+ { //box filter of diameter 1.0f, 8-queen sampling pattern
+ m_numSamples = 8;
+ m_samples[0].x = 3;
+ m_samples[1].x = 7;
+ m_samples[2].x = 0;
+ m_samples[3].x = 2;
+ m_samples[4].x = 5;
+ m_samples[5].x = 1;
+ m_samples[6].x = 6;
+ m_samples[7].x = 4;
+ for(int i=0;i<m_numSamples;i++)
+ {
+ m_samples[i].x = (m_samples[i].x + 0.5f) / (RScalar)m_numSamples - 0.5f;
+ m_samples[i].y = ((RScalar)i + 0.5f) / (RScalar)m_numSamples - 0.5f;
+ m_samples[i].weight = 1.0f / (RScalar)m_numSamples;
+ m_sumWeights += m_samples[i].weight;
+ }
+ m_sampleRadius = 0.5f;
+ }
+ else
+ {
+ RI_ASSERT(renderingQuality == VG_RENDERING_QUALITY_BETTER);
+ m_numSamples = RI_MAX_SAMPLES;
+ m_sampleRadius = 0.75f;
+ for(int i=0;i<m_numSamples;i++)
+ { //Gaussian filter, implemented using Hammersley point set for sample point locations
+ RScalar x = (RScalar)radicalInverseBase2(i);
+ RScalar y = ((RScalar)i + 0.5f) / (RScalar)m_numSamples;
+ RI_ASSERT(x >= 0.0f && x < 1.0f);
+ RI_ASSERT(y >= 0.0f && y < 1.0f);
+
+ //map unit square to unit circle
+ RScalar r = (RScalar)sqrt(x) * m_sampleRadius;
+ x = r * (RScalar)sin(y*2.0f*PI);
+ y = r * (RScalar)cos(y*2.0f*PI);
+ m_samples[i].weight = (RScalar)exp(-0.5f * RI_SQR(r/m_sampleRadius));
+
+ 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
+
+ m_samples[i].x = x;
+ m_samples[i].y = y;
+ m_sumWeights += m_samples[i].weight;
+ }
+ }
+ }
+ else
+ { //box filter
+ m_numSamples = numFSAASamples;
+ RI_ASSERT(numFSAASamples >= 1 && numFSAASamples <= 32); //sample mask is a 32-bit uint => can't support more than 32 samples
+ //use Hammersley point set as a sampling pattern
+ for(int i=0;i<m_numSamples;i++)
+ {
+ m_samples[i].x = (RScalar)radicalInverseBase2(i) + 1.0f / (RScalar)(m_numSamples<<1) - 0.5f;
+ m_samples[i].y = ((RScalar)i + 0.5f) / (RScalar)m_numSamples - 0.5f;
+ m_samples[i].weight = 1.0f;
+ RI_ASSERT(m_samples[i].x > -0.5f && m_samples[i].x < 0.5f);
+ RI_ASSERT(m_samples[i].y > -0.5f && m_samples[i].y < 0.5f);
+ }
+ m_sumWeights = (RScalar)m_numSamples;
+ m_sampleRadius = 0.5f;
+ }
+ return m_numSamples;
+}
+
+/*-------------------------------------------------------------------*//*!
+* \brief Calls PixelPipe::pixelPipe for each pixel with coverage greater
+* than zero.
+* \param
+* \return
+* \note
+*//*-------------------------------------------------------------------*/
+
+void Rasterizer::fill()
+{
+ if(m_scissor && !m_scissorEdges.size())
+ return; //scissoring is on, but there are no scissor rectangles => nothing is visible
+
+ //proceed scanline by scanline
+ //keep track of edges that can intersect the pixel filters of the current scanline (Active Edge Table)
+ //until all pixels of the scanline have been processed
+ // for all sampling points of the current pixel
+ // determine the winding number using edge functions
+ // add filter weight to coverage
+ // divide coverage by the number of samples
+ // determine a run of pixels with constant coverage
+ // call fill callback for each pixel of the run
+
+ int fillRuleMask = 1;
+ if(m_fillRule == VG_NON_ZERO)
+ fillRuleMask = -1;
+
+ int bbminx = (int)floor(m_edgeMin.x);
+ int bbminy = (int)floor(m_edgeMin.y);
+ int bbmaxx = (int)floor(m_edgeMax.x)+1;
+ int bbmaxy = (int)floor(m_edgeMax.y)+1;
+ int sx = RI_INT_MAX(m_vpx, bbminx);
+ int ex = RI_INT_MIN(m_vpx+m_vpwidth, bbmaxx);
+ int sy = RI_INT_MAX(m_vpy, bbminy);
+ int ey = RI_INT_MIN(m_vpy+m_vpheight, bbmaxy);
+ if(sx < m_covMinx) m_covMinx = sx;
+ if(sy < m_covMiny) m_covMiny = sy;
+ if(ex > m_covMaxx) m_covMaxx = ex;
+ if(ey > m_covMaxy) m_covMaxy = ey;
+
+ //fill the screen
+ Array<ActiveEdge> aet;
+ Array<ScissorEdge> scissorAet;
+ for(int j=sy;j<ey;j++)
+ {
+ //gather scissor edges intersecting this scanline
+ scissorAet.clear();
+ if( m_scissor )
+ {
+ for(int e=0;e<m_scissorEdges.size();e++)
+ {
+ const ScissorEdge& se = m_scissorEdges[e];
+ if(j >= se.miny && j < se.maxy)
+ scissorAet.push_back(m_scissorEdges[e]); //throws bad_alloc
+ }
+ if(!scissorAet.size())
+ continue; //scissoring is on, but there are no scissor rectangles on this scanline
+ }
+
+ //simple AET: scan through all the edges and pick the ones intersecting this scanline
+ aet.clear();
+ for(int e=0;e<m_edges.size();e++)
+ {
+ RScalar cminy = (RScalar)j - m_sampleRadius + 0.5f;
+ RScalar cmaxy = (RScalar)j + m_sampleRadius + 0.5f;
+ const Edge& ed = m_edges[e];
+ RI_ASSERT(ed.v0.y <= ed.v1.y); //horizontal edges should have been dropped already
+
+ ActiveEdge ae;
+ ae.v0 = ed.v0;
+ ae.v1 = ed.v1;
+ ae.direction = ed.direction;
+
+ if(cmaxy >= ae.v0.y && cminy < ae.v1.y)
+ {
+ ae.n.set(ae.v0.y - ae.v1.y, ae.v1.x - ae.v0.x); //edge normal
+ ae.cnst = ae.v0.x * ae.n.x + ae.v0.y * ae.n.y; //distance of v0 from the origin along the edge normal
+
+ //compute edge min and max x-coordinates for this scanline
+ Vector2 vd(ae.v1.x - ae.v0.x, ae.v1.y - ae.v0.y);
+ RScalar wl = 1.0f / vd.y;
+ RScalar sx = ae.v0.x + vd.x * (cminy - ae.v0.y) * wl;
+ RScalar ex = ae.v0.x + vd.x * (cmaxy - ae.v0.y) * wl;
+ RScalar bminx = RI_MIN(ae.v0.x, ae.v1.x);
+ RScalar bmaxx = RI_MAX(ae.v0.x, ae.v1.x);
+ sx = RI_CLAMP(sx, bminx, bmaxx);
+ ex = RI_CLAMP(ex, bminx, bmaxx);
+ ae.minx = RI_MIN(sx,ex);
+ ae.maxx = RI_MAX(sx,ex);
+ aet.push_back(ae); //throws bad_alloc
+ }
+ }
+ if(!aet.size())
+ continue; //no edges on the whole scanline, skip it
+
+ //sort AET by edge minx
+ aet.sort();
+
+ //sort scissor AET by edge x
+ scissorAet.sort();
+
+ //fill the scanline
+ int scissorWinding = m_scissor ? 0 : 1; //if scissoring is off, winding is always 1
+ int scissorIndex = 0;
+ int aes = 0;
+ int aen = 0;
+ for(int i=sx;i<ex;)
+ {
+ Vector2 pc(i + 0.5f, j + 0.5f); //pixel center
+
+ //find edges that intersect or are to the left of the pixel antialiasing filter
+ while(aes < aet.size() && pc.x + m_sampleRadius >= aet[aes].minx)
+ aes++;
+ //edges [0,aes[ may have an effect on winding, and need to be evaluated while sampling
+
+ //compute coverage
+ RScalar coverage = 0.0f;
+ unsigned int sampleMask = 0;
+ for(int s=0;s<m_numSamples;s++)
+ {
+ Vector2 sp = pc; //sampling point
+ sp.x += m_samples[s].x;
+ sp.y += m_samples[s].y;
+
+ //compute winding number by evaluating the edge functions of edges to the left of the sampling point
+ int winding = 0;
+ for(int e=0;e<aes;e++)
+ {
+ if(sp.y >= aet[e].v0.y && sp.y < aet[e].v1.y)
+ { //evaluate edge function to determine on which side of the edge the sampling point lies
+ RScalar side = sp.x * aet[e].n.x + sp.y * aet[e].n.y - aet[e].cnst;
+ if(side <= 0.0f) //implicit tie breaking: a sampling point on an opening edge is in, on a closing edge it's out
+ {
+ winding += aet[e].direction;
+ }
+ }
+ }
+ if(winding & fillRuleMask)
+ {
+ coverage += m_samples[s].weight;
+ sampleMask |= (unsigned int)(1<<s);
+ }
+ }
+
+ //constant coverage optimization:
+ //scan AET from left to right and skip all the edges that are completely to the left of the pixel filter.
+ //since AET is sorted by minx, the edge we stop at is the leftmost of the edges we haven't passed yet.
+ //if that edge is to the right of this pixel, coverage is constant between this pixel and the start of the edge.
+ 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
+ aen++;
+
+ int endSpan = m_vpx + m_vpwidth; //endSpan is the first pixel NOT part of the span
+ if(aen < aet.size())
+ endSpan = RI_INT_MAX(i+1, RI_INT_MIN(endSpan, (int)ceil(aet[aen].minx - m_sampleRadius - 0.5f)));
+
+ coverage /= m_sumWeights;
+ RI_ASSERT(coverage >= 0.0f && coverage <= 1.0f);
+
+ //fill a run of pixels with constant coverage
+ if(sampleMask)
+ {
+ for(;i<endSpan;i++)
+ {
+ //update scissor winding number
+ while(scissorIndex < scissorAet.size() && scissorAet[scissorIndex].x <= i)
+ scissorWinding += scissorAet[scissorIndex++].direction;
+ RI_ASSERT(scissorWinding >= 0);
+
+ if(scissorWinding)
+ {
+ if(m_covBuffer)
+ m_covBuffer[j*m_vpwidth+i] |= (RIuint32)sampleMask;
+ else
+ m_pixelPipe->pixelPipe(i, j, coverage, sampleMask);
+ }
+ }
+ }
+ i = endSpan;
+ }
+ }
+}
+
+//=======================================================================
+
+} //namespace OpenVGRI