Generic functions (surface/pixel fill/blend).

Line antialiasing.
Circle antialiasing.

svn-id: r31844

2 files changed, 256 insertions, 85 deletions

diff --git a/graphics/VectorRenderer.cpp b/graphics/VectorRenderer.cpp
index 252fc5722b..0ffaf9811d 100644
--- a/graphics/VectorRenderer.cpp
+++ b/graphics/VectorRenderer.cpp
@@ -31,8 +31,10 @@
 
 namespace Graphics {
 
+inline uint32 fp_sqroot( uint32 x );
+
 VectorRenderer *createRenderer() {
-	return new VectorRendererSpec<uint16,ColorMasks<565>>;
+	return new VectorRendererAA<uint16,ColorMasks<565>>;
 }
 
 
@@ -49,12 +51,20 @@ void vector_renderer_test( OSystem *_system ) {
 	_system->grabOverlay((OverlayColor*)_screen.pixels, _screen.w);
 
 	vr->setSurface( &_screen );
-	vr->setColor( 255, 255, 255 );
+	vr->setColor( 255, 0, 0 );
+	vr->fillSurface();
+	vr->setColor( 255, 255, 0 );
 
 	_system->showOverlay();
 
 	while( true ) { // draw!!
-		vr->drawLine( 25, 100, 25, 150 );
+
+		vr->setColor( 255, 255, 255 );
+		vr->fillSurface();
+		vr->setColor( 255, 0, 0 );
+		vr->drawLine( 25, 25, 125, 300 );
+		vr->drawCircle( 250, 250, 100 );
+
 		_system->copyRectToOverlay((OverlayColor*)_screen.getBasePtr(0, 0), _screen.w, 0, 0, _screen.w, _screen.w);
 		_system->updateScreen();
 		_system->delayMillis(100);
@@ -63,10 +73,9 @@ void vector_renderer_test( OSystem *_system ) {
 	_system->hideOverlay();
 }
 
-
 template<typename PixelType, typename PixelFormat>
 void VectorRendererSpec<PixelType,PixelFormat>::
-drawLineAlg(int x1, int x2, int y1, int y2, int dx, int dy) {
+drawLineAlg(int x1, int y1, int x2, int y2, int dx, int dy) {
 	PixelType *ptr = (PixelType *)_activeSurface->getBasePtr(x1, y1);
 	int pitch = surfacePitch();
 	int xdir = (x2 > x1) ? 1 : -1;
@@ -111,76 +120,77 @@ drawLineAlg(int x1, int x2, int y1, int y2, int dx, int dy) {
 	*ptr = (PixelType)_color;
 }
 
+
 template<typename PixelType, typename PixelFormat>
 void VectorRendererAA<PixelType,PixelFormat>::
-drawLineAlg(int x1, int x2, int y1, int y2, int dx, int dy) {
-	PixelType *ptr = (PixelType *)_activeSurface->getBasePtr(x1, y1);
-	int pitch = surfacePitch();
-	int xdir = (x2 > x1) ? 1 : -1;
+blendPixelPtr( PixelType *ptr, uint8 alpha ) {
+	register int idst = *ptr;
+	register int isrc = _color;
+
+	*ptr = (PixelType)(
+		(PixelFormat::kRedMask & ((idst & PixelFormat::kRedMask) +
+		((int)(((int)(isrc & PixelFormat::kRedMask) -
+		(int)(idst & PixelFormat::kRedMask)) * alpha) >>8))) |
+		(PixelFormat::kGreenMask & ((idst & PixelFormat::kGreenMask) +
+		((int)(((int)(isrc & PixelFormat::kGreenMask) -
+		(int)(idst & PixelFormat::kGreenMask)) * alpha) >>8))) |
+		(PixelFormat::kBlueMask & ((idst & PixelFormat::kBlueMask) +
+		((int)(((int)(isrc & PixelFormat::kBlueMask) -
+		(int)(idst & PixelFormat::kBlueMask)) * alpha) >>8))) );
+}
 
-	int error_line, error_tmp, weight;
-	int error_total = 0;
-	uint8 line_r, line_g, line_b;
-	uint8 bg_r, bg_g, bg_b;
 
-	colorToRGB<PixelFormat>(_color, line_r, line_g, line_b);
+template<typename PixelType, typename PixelFormat>
+void VectorRendererAA<PixelType,PixelFormat>::
+drawLineAlg(int x1, int y1, int x2, int y2, int dx, int dy) {
 
-	uint line_lum = (line_r >> 2) + (line_g >> 1) + (line_b >> 3);
-	uint bg_lum;
+	PixelType *ptr = (PixelType *)_activeSurface->getBasePtr(x1, y1);
+	int pitch = surfacePitch();
+	int xdir = (x2 > x1) ? 1 : -1;
+	uint16 error_tmp, error_acc, gradient;
 
-	// first pixel, should be perfectly accurate so no fading out
-	*ptr = (PixelType)_color; 
+	*ptr = (PixelType)_color;
 
-#define __WULINE_PUTPIXEL( pixel_ptr ) { \
-		colorToRGB<PixelFormat>((PixelType)*(pixel_ptr), bg_r, bg_g, bg_b); \
-		bg_lum = (bg_r >> 2) + (bg_g >> 1) + (bg_b >> 3); \
-		weight = (line_lum < bg_lum) ? error_total >> 8 : (error_total >> 8)^0xFF; \
-		*(pixel_ptr) = RGBToColor<PixelFormat>( \
-			antialiasingBlendWeight(line_r, bg_r, weight), \
-			antialiasingBlendWeight(line_g, bg_g, weight), \
-			antialiasingBlendWeight(line_b, bg_b, weight)); \
-	}
+	if ( dx > dy ) {
+		gradient = (uint32)(dy<<16)/(uint32)dx;
+		error_acc = 0;
 
-	// draw from top to bottom while fading out.
-	// optimized for mostly vertical lines
-	if (dy > dx) {
-		error_line = (dx << 16) / dy;
-		while (--dy) {
-			error_tmp = error_total;
-			error_total += error_line;
+		while( --dx ) {
+			error_tmp = error_acc;
+			error_acc += gradient;
 
-			if (error_total <= error_tmp)
-				ptr += xdir; // move right or left
+			if ( error_acc <= error_tmp )
+				ptr += pitch;
 
-			ptr += pitch; // move down			
+			ptr += xdir;
 
-			__WULINE_PUTPIXEL(ptr);
-			__WULINE_PUTPIXEL(ptr + xdir);
+			blendPixelPtr( ptr, (error_acc >> 8) ^ 0xFF );
+			blendPixelPtr( ptr + pitch, (error_acc >> 8) & 0xFF );
 		}
-	} else { // optimized for mostly horizontal lines
-		error_line = (dy << 16) / dx;
-		while (--dx) {
-			error_tmp = error_total;
-			error_total += error_line;
+	} else {
+		gradient = (uint32)(dx<<16)/(uint32)dy;
+		error_acc = 0;
+
+		while( --dy ) {
+			error_tmp = error_acc;
+			error_acc += gradient;
 
-			if (error_total <= error_tmp)
-				ptr += pitch; // move down
+			if ( error_acc <= error_tmp )
+				ptr += xdir;
 
-			ptr += xdir; // move left or right	
+			ptr += pitch;
 
-			__WULINE_PUTPIXEL(ptr);
-			__WULINE_PUTPIXEL(ptr + pitch);
-		}	
-	} // end of line direction cases
+			blendPixelPtr( ptr, (error_acc >> 8) ^ 0xFF );
+			blendPixelPtr( ptr + xdir, (error_acc >> 8) & 0xFF );
+		}
+	}
 
-	// last pixel, also perfectly accurate.
-	ptr = (PixelType *)_activeSurface->getBasePtr(x2, y2);
-	*ptr = (PixelType)_color;
+	putPixel( x2, y2 );
 }
 
 template<typename PixelType, typename PixelFormat>
 void VectorRendererSpec<PixelType,PixelFormat>::
-drawLine(int x1, int x2, int y1, int y2) {
+drawLine(int x1, int y1, int x2, int y2) {
 	// we draw from top to bottom
 	if (y2 < y1) {
 		SWAP(x1, x2);
@@ -219,7 +229,71 @@ drawLine(int x1, int x2, int y1, int y2) {
 		}
 
 	} else { // generic lines, use the standard algorithm...
-		drawLineAlg(x1, x2, y1, y2, dx, dy);
+		drawLineAlg(x1, y1, x2, y2, dx, dy);
+	}
+}
+
+inline uint32 fp_sqroot( uint32 x ) {
+	register uint32 root, remHI, remLO, testDIV, count;
+
+	root = 0;
+	remHI = 0;
+	remLO = x;
+	count = 23;
+
+	do {
+		remHI = (remHI<<2) | (remLO>>30);
+		remLO <<= 2;
+		root <<= 1;
+		testDIV = (root<<1) + 1;
+
+		if ( remHI >= testDIV ) {
+			remHI -= testDIV;
+			root++;
+		}
+	} while( count-- );
+
+	return root;
+}
+
+template<typename PixelType, typename PixelFormat>
+void VectorRendererAA<PixelType,PixelFormat>::
+drawCircleAlg(int x1, int y1, int r) {
+
+#define __CIRCLE_SIM(x,y,a) { \
+	blendPixel( x1 + (x), y1 + (y), a ); \
+	blendPixel( x1 + (x), y1 - (y), a ); \
+	blendPixel( x1 - (y), y1 + (x), a ); \
+	blendPixel( x1 + (y), y1 + (x), a ); \
+	blendPixel( x1 - (x), y1 + (y), a ); \
+	blendPixel( x1 - (x), y1 - (y), a ); \
+	blendPixel( x1 + (y), y1 - (x), a ); \
+	blendPixel( x1 - (y), y1 - (x), a ); \
+}
+
+	// first quadrant
+/*#define __CIRCLE_SIM(x,y,a) { \
+	blendPixel( x1 + (x), y1 - (y), a ); \
+	blendPixel( x1 + (y), y1 - (x), a ); \
+}*/
+
+	int x = r;
+	int y = 0;
+	uint32 rsq = (r*r)<<16;
+	uint32 T = 0, oldT;
+	
+	__CIRCLE_SIM( x, y, 255 );
+
+	while( x > y++ )
+	{
+		oldT = T;
+		T = fp_sqroot( rsq - ((y*y)<<16) ) ^ 0xFFFF;
+
+		if ( T < oldT )
+			x--;
+
+		__CIRCLE_SIM( x,   y, (T>>8) ^ 0xFF );
+		__CIRCLE_SIM( x-1, y, (T>>8) & 0xFF );
 	}
 }
 
diff --git a/graphics/VectorRenderer.h b/graphics/VectorRenderer.h
index c5a09faf81..b7ee7d1680 100644
--- a/graphics/VectorRenderer.h
+++ b/graphics/VectorRenderer.h
@@ -37,7 +37,7 @@ void vector_renderer_test( OSystem *_system );
 /**
  * VectorRenderer: The core Vector Renderer Class
  *
- * This virtual class which exposes the API with all the vectorial
+ * This virtual class exposes the API with all the vectorial
  * rendering functions that may be used to draw on a given Surface.
  *
  * This class must be instantiated as one of its children, which implement
@@ -60,7 +60,16 @@ public:
 	 * @param y1 Vertical (Y) coordinate for the line start
 	 * @param y2 Vertical (Y) coordinate for the line end
 	 */
-	virtual void drawLine(int x1, int x2, int y1, int y2) = 0;
+	virtual void drawLine(int x1, int y1, int x2, int y2) = 0;
+
+	/**
+	 * Draws a circle centered at (x,y) with radius r.
+	 *
+	 * @param x Horizontal (X) coordinate for the center of the circle
+	 * @param y Vertical (Y) coordinate for the center of the circle
+	 * @param r Radius of the circle.
+	 */
+	virtual void drawCircle( int x, int y, int r ) = 0;
 
 	/**
 	 * Gets the pixel pitch for the current drawing surface.
@@ -96,21 +105,47 @@ public:
 	virtual void setColor(uint8 r, uint8 g, uint8 b) = 0;
 
 	/**
-	 * Set the active painting color for the renderer, including alpha
-	 * intensity. All the drawing from then on will be done with that color, 
-	 * unless specified otherwise.
+	 * Sets the active drawing surface. All drawing from this
+	 * point on will be done on that surface.
 	 *
-	 * @param r	value of the red color byte
-	 * @param g	value of the green color byte
-	 * @param b	value of the blue color byte
-	 * @param a value of the alpha byte
+	 * @param surface Pointer to a Surface object.
 	 */
-	virtual void setColor(uint8 r, uint8 g, uint8 b, uint8 a) = 0;
-
 	virtual void setSurface( Surface *surface ){
 		_activeSurface = surface;
 	}
 
+	/**
+	 * Fills the active surface with the currently active drawing color.
+	 */
+	virtual void fillSurface() = 0;
+
+	/**
+	 * Clears the active surface.
+	 */
+	virtual void clearSurface() {
+		byte *src = (byte *)_activeSurface->pixels;
+		memset( src, 0, _activeSurface->w * _activeSurface->h * _activeSurface->bytesPerPixel );
+	}
+
+	/**
+	 * Draws a single pixel on the surface with the given coordinates and
+	 * the currently active drawing color.
+	 *
+	 * @param x Horizontal coordinate of the pixel.
+	 * @param y Vertical coordinate of the pixel.
+	 */
+	inline virtual void putPixel( int x, int y ) = 0;
+
+	/**
+	 * Blends a single pixel on the surface with the given coordinates, with
+	 * the currently active drawing color and with the given Alpha intensity.
+	 *
+	 * @param x Horizontal coordinate of the pixel.
+	 * @param y Vertical coordinate of the pixel.
+	 * @param alpha Alpha intensity of the pixel (0-255)
+	 */
+	inline virtual void blendPixel( int x, int y, uint8 alpha ) = 0;
+
 protected:
 
 	/**
@@ -125,8 +160,16 @@ protected:
 	 * @param dx Horizontal (X) increasement.
 	 * @param dy Vertical (Y) increasement.
 	 */
-	virtual void drawLineAlg(int x1, int x2, int y1, int y2, int dx, int dy) = 0;
+	virtual void drawLineAlg(int x1, int y1, int x2, int y2, int dx, int dy) = 0;
 
+	/**
+	 * Specific circle drawing algorithm with symmetry. Must be implemented
+	 * on each renderer.
+	 *
+	 * @param x Horizontal (X) coordinate for the center of the circle
+	 * @param y Vertical (Y) coordinate for the center of the circle
+	 * @param r Radius of the circle.
+	 */
 	virtual void drawCircleAlg(int x, int y, int r) = 0;
 
 	Surface *_activeSurface; /** Pointer to the surface currently being drawn */
@@ -156,11 +199,16 @@ protected:
 template<typename PixelType, typename PixelFormat>
 class VectorRendererSpec : public VectorRenderer {
 
+public:
 	/**
 	 * @see VectorRenderer::drawLine()
 	 */
 	void drawLine(int x1, int x2, int y1, int y2);
 
+	void drawCircle( int x, int y, int r ) {
+		drawCircleAlg( x, y, r );
+	}
+
 	/**
 	 * @see VectorRenderer::setColor()
 	 */
@@ -175,6 +223,33 @@ class VectorRendererSpec : public VectorRenderer {
 		_color = RGBToColor<PixelFormat>(r, g, b);
 	}
 
+	/**
+	 * @see VectorRenderer::fillSurface()
+	 */
+	void fillSurface() {
+		PixelType *ptr = (PixelType *)_activeSurface->getBasePtr(0, 0);
+		int s = _activeSurface->w * _activeSurface->h;
+		Common::set_to(ptr, ptr + s, (PixelType)_color);
+	}
+
+	/**
+	 * @see VectorRenderer::putPixel()
+	 */
+	inline void putPixel( int x, int y ) {
+		PixelType *ptr = (PixelType *)_activeSurface->getBasePtr(x, y);
+		*ptr = _color;
+	}
+
+	/**
+	 * On the Specialized Renderer, alpha blending is not supported. 
+	 *
+	 * @see VectorRenderer::blendPixel()
+	 */
+	virtual inline void blendPixel( int x, int y, uint8 alpha ) {
+		if ( alpha > 0 )
+			putPixel( x, y );
+	}
+
 protected:
 
 	/*
@@ -186,8 +261,11 @@ protected:
 	 *
 	 * @see VectorRenderer::drawLineAlg()
 	 */
-	virtual void drawLineAlg(int x1, int x2, int y1, int y2, int dx, int dy);
+	virtual void drawLineAlg(int x1, int y1, int x2, int y2, int dx, int dy);
 
+	/**
+	 * @see VectorRenderer::drawCircleAlg()
+	 */
 	virtual void drawCircleAlg(int x, int y, int r) {}
 
 	PixelType _color; /** Color currently being used to draw on the renderer */
@@ -218,27 +296,46 @@ protected:
 	 *
 	 * @see VectorRenderer::drawLineAlg()
 	 */
-	void drawLineAlg(int x1, int x2, int y1, int y2, int dx, int dy);
+	void drawLineAlg(int x1, int y1, int x2, int y2, int dx, int dy);
 
 	/**
-	 * Calculates the blending weight (relative luminosity) value for
-	 * a given pixel, based on the distance to the ideal line.
-	 * Used for blending pixels in the Wu AA algorithm.
+	 * Perform alpha blending on top of a given pixel, not on a given
+	 * coordinate (just so we don't have to recalculate the surface
+	 * pointer while we are blending consecutive pixels).
+	 *
+	 * Everything from blendPixel() applies here.
 	 *
-	 * @param line_color Byte value of a color component (R/G/B) of the color used to draw the line.
-	 * @param line_color Byte value of a color component (R/G/B) of the color used to draw the BG.
-	 * @param weight Weight of the pixel as calculated by Wu's algorithm.
-	 * @return The new color value for the given component.
+	 * @see VectorRenderer::blendPixel()
+	 * @param ptr Pointer to the pixel where we must draw
+	 * @param alpha Intensity of the pixel (0-255).
 	 */
-	inline uint8 antialiasingBlendWeight(uint8 line_color, uint8 bg_color, uint weight) {
-		uint8 value;
-		if (bg_color > line_color) {
-			value = weight / 255 * (bg_color - line_color) + bg_color;  
-		} else {
-			value = weight / 255 * (line_color - bg_color) + line_color;
-		}
-		return value;
+	inline void blendPixelPtr( PixelType *ptr, uint8 alpha );
+
+	/**
+	 * @see VectorRenderer::blendPixel()
+	 *
+	 * The AA renderer does support alpha blending. Special cases are
+	 * handled separately.
+	 */
+	inline void blendPixel( int x, int y, uint8 alpha ) {
+		if ( alpha == 0 )
+			return;
+		else if ( alpha < 255 )
+			blendPixelPtr( (PixelType*)_activeSurface->getBasePtr(x, y), alpha );
+		else
+			putPixel( x, y );
 	}
+
+	/**
+	 * "Wu's Circle Antialiasing Algorithm" as published by Xiaolin Wu, July 1991
+	 * Based on the theoretical concept of the algorithm.
+	 *
+	 * Implementation of Wu's algorithm for circles using fixed point arithmetics.
+	 * Could be quite fast.
+	 *
+	 * @see VectorRenderer::drawCircleAlg()
+	 */
+	virtual void drawCircleAlg(int x, int y, int r);
 };
 
 } // end of namespace Graphics