Minor updates.
/*------------------------------------------------------------------------
*
* 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