 |
|
|
Really came in handy for a little project I'm working on.
I ported it to java and thought I'd post the code here in case anyone else searching for flood fill algorithms finds it useful.
P.S: Fixed the bug mentioned by hankhuf too, in LinearFill method change
if (lFillLoc <= 0 || ...
to
if (lFillLoc < 0 || ...
//Original algorithm by J. Dunlap http://www.codeproject.com/KB/GDI-plus/queuelinearfloodfill.aspx
//Java port by Owen Kaluza
import java.awt.*;
import java.awt.image.*;
import java.util.Queue;
import java.util.LinkedList;
public class QueueLinearFloodFiller
{
//Image to fill, colour to fill, colour tolerance R,G,B
protected BufferedImage image = null;
protected int[] tolerance = new int[] {0,0,0};
//cached image properties
protected int width = 0;
protected int height = 0;
protected int[] pixels = null;
//internal, initialized per fill
protected boolean[] pixelsChecked;
protected int fillColour = 0;
protected int[] startColour = new int[] {0,0,0};
//Queue of floodfill ranges
protected Queue ranges;
//Construct using an image and a copy will be made to fill into,
//Construct with BufferedImage and flood fill will write directly to provided BufferedImage
public QueueLinearFloodFiller(Image img) {copyImage(img);}
public QueueLinearFloodFiller(BufferedImage img) {useImage(img);}
public int getFillColor() {return fillColour;}
public void setFillColour(Color value) {fillColour = value.getRGB();}
public void setFillColour(int value) {fillColour = value;}
public int[] getTolerance() {return tolerance;}
public void setTolerance(int[] value) {tolerance = value;}
public void setTolerance(int value) {tolerance = new int[] {value, value, value};}
public BufferedImage getImage() {return image;}
public void copyImage(Image img)
{
//Copy data from provided Image to a BufferedImage to write flood fill to, use getImage to retrieve
//cache data in member variables to decrease overhead of property calls
width = img.getWidth(null);
height = img.getHeight(null);
image = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB); //TYPE_INT_ARGB
Graphics gfx = image.getGraphics();
gfx.drawImage(img, 0, 0, null);
pixels = ((DataBufferInt)image.getRaster().getDataBuffer()).getData();
}
public void useImage(BufferedImage img)
{
//Use a pre-existing provided BufferedImage and write directly to it
//cache data in member variables to decrease overhead of property calls
width = img.getWidth(null);
height = img.getHeight(null);
image = img;
pixels = ((DataBufferInt)image.getRaster().getDataBuffer()).getData();
}
protected void Prepare()
{
//Called before starting flood-fill
pixelsChecked = new boolean[pixels.length];
ranges = new LinkedList();
}
// Fills the specified point on the bitmap with the currently selected fill color.
// int x, int y: The starting coords for the fill
public void FloodFill(int x, int y)
{
//Setup
Prepare();
//***Get starting color.
int startPixel = pixels[(width * y) + x];
startColour[0] = (startPixel >> 16) & 0xff;
startColour[1] = (startPixel >> 8) & 0xff;
startColour[2] = startPixel & 0xff;
//***Do first call to floodfill.
LinearFill(x, y);
//***Call floodfill routine while floodfill ranges still exist on the queue
FloodFillRange range;
while (ranges.size() > 0)
{
//**Get Next Range Off the Queue
range = ranges.remove();
//**Check Above and Below Each Pixel in the Floodfill Range
int downPxIdx = (width * (range.Y + 1)) + range.startX;
int upPxIdx = (width * (range.Y - 1)) + range.startX;
int upY = range.Y - 1;//so we can pass the y coord by ref
int downY = range.Y + 1;
for (int i = range.startX; i <= range.endX; i++)
{
//*Start Fill Upwards
//if we if (range.Y > 0 && (!pixelsChecked[upPxIdx]) && CheckPixel(upPxIdx))
LinearFill( i, upY);
//*Start Fill Downwards
//if we if (range.Y < (height - 1) && (!pixelsChecked[downPxIdx]) && CheckPixel(downPxIdx))
LinearFill( i, downY);
downPxIdx++;
upPxIdx++;
}
}
}
// Finds the furthermost left and right boundaries of the fill area
// on a given y coordinate, starting from a given x coordinate, filling as it goes.
// Adds the resulting horizontal range to the queue of floodfill ranges,
// to be processed in the main loop.
//
// int x, int y: The starting coords
protected void LinearFill(int x, int y)
{
//***Find Left Edge of Color Area
int lFillLoc = x; //the location to check/fill on the left
int pxIdx = (width * y) + x;
while (true)
{
//**fill with the color
pixels[pxIdx] = fillColour;
//**indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
//**de-increment
lFillLoc--; //de-increment counter
pxIdx--; //de-increment pixel index
//**exit loop if we if (lFillLoc < 0 || (pixelsChecked[pxIdx]) || !CheckPixel(pxIdx))
break;
}
lFillLoc++;
//***Find Right Edge of Color Area
int rFillLoc = x; //the location to check/fill on the left
pxIdx = (width * y) + x;
while (true)
{
//**fill with the color
pixels[pxIdx] = fillColour;
//**indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
//**increment
rFillLoc++; //increment counter
pxIdx++; //increment pixel index
//**exit loop if we if (rFillLoc >= width || pixelsChecked[pxIdx] || !CheckPixel(pxIdx))
break;
}
rFillLoc--;
//add range to queue
FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);
ranges.offer(r);
}
//Sees if a pixel is within the color tolerance range.
protected boolean CheckPixel(int px)
{
int red = (pixels[px] >>> 16) & 0xff;
int green = (pixels[px] >>> 8) & 0xff;
int blue = pixels[px] & 0xff;
return (red >= (startColour[0] - tolerance[0]) && red <= (startColour[0] + tolerance[0]) &&
green >= (startColour[1] - tolerance[1]) && green <= (startColour[1] + tolerance[1]) &&
blue >= (startColour[2] - tolerance[2]) && blue <= (startColour[2] + tolerance[2]));
}
// Represents a linear range to be filled and branched from.
protected class FloodFillRange
{
public int startX;
public int endX;
public int Y;
public FloodFillRange(int startX, int endX, int y)
{
this.startX = startX;
this.endX = endX;
this.Y = y;
}
}
}
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
|
|
|
Hi,
Very nice work, can i use this code in my applications. actually i m converting it to AS3. Again very nice and clear job done.
Thank you.
Bulent Ozturk
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
|
|
|
I like many things about your algorithm, and it has inspired me to write my own. I did notice a small bug during my testing. If you load a pure red PNG and flood fill with green or black or some other contrasty color, you will see that pixels along the left edge do not fill.
Hank
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
I'm not sure exactly how it works without getting deep in the code; however, how could this code be used to fill a bitmap?
For instance, I was hoping that I could flood fill by...
//Create the new bitmap and the graphics canvas
oBitmap = new Bitmap(nWidth, nHeight, PixelFormat.Format32bppArgb);
oGraphic = Graphics.FromImage(oBitmap);
FloodFill(oGraphic, Color.Black, x,y, ToleranceRed, ToleranceBlue, ToleranceGreen);
(or something that effect)
Any suggestions? Any sample is greatly appreciated!
Mike
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
I've adapted the code a bit to wrap in a single unit (hope the author doesn't mind!), I think it will do what you want.
To use:
Bitmap bitmap = new Bitmap("MyBitmap.bmp");
FloodFiller ff = new FloodFiller();
bitmap = ff.FloodFillBitmap(bitmap, new Point(58, 51), Color.Red);
Bruce
----------------------------
using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using System.Diagnostics;
using System.Runtime.InteropServices;
using System.Drawing.Imaging;
using System.Collections.ObjectModel;
namespace FloodFillClasses
{
public class FloodFiller
{
protected AbstractFloodFiller ff;
public Bitmap FloodFillBitmap(Bitmap bm, Point p, Color c)
{
if ((bm == null) || (p == null)) return null;
ff = new QueueLinearFloodFiller(ff);
ff.FillColor = c;
ff.Tolerance[0] = (byte)5;
ff.Tolerance[1] = (byte)5;
ff.Tolerance[2] = (byte)5;
ff.Bitmap = new EditableBitmap(bm, PixelFormat.Format32bppArgb);
ff.FloodFill(p);
return ff.Bitmap.Bitmap;
}
}
///
///
///
///
///
public delegate void UpdateScreenDelegate(ref int x, ref int y);
///
/// The base class that the flood fill algorithms inherit from. Implements the
/// basic flood filler functionality that is the same across all algorithms.
///
public abstract class AbstractFloodFiller
{
protected EditableBitmap bitmap;
protected byte[] tolerance = new byte[] { 25, 25, 25 };
protected Color fillColor = Color.Magenta;
protected bool fillDiagonally = false;
protected bool slow = false;
//cached bitmap properties
protected int bitmapWidth = 0;
protected int bitmapHeight = 0;
protected int bitmapStride = 0;
protected int bitmapPixelFormatSize = 0;
protected byte[] bitmapBits = null;
//internal int timeBenchmark = 0;
internal Stopwatch watch = new Stopwatch();
internal UpdateScreenDelegate UpdateScreen;
//internal, initialized per fill
//protected BitArray pixelsChecked;
protected bool[] pixelsChecked;
protected byte[] byteFillColor;
protected byte[] startColor;
//protected int stride;
public AbstractFloodFiller()
{
}
public AbstractFloodFiller(AbstractFloodFiller configSource)
{
if (configSource != null)
{
this.Bitmap = configSource.Bitmap;
this.FillColor = configSource.FillColor;
this.FillDiagonally = configSource.FillDiagonally;
this.Slow = configSource.Slow;
this.Tolerance = configSource.Tolerance;
}
}
public bool Slow
{
get { return slow; }
set { slow = value; }
}
public Color FillColor
{
get { return fillColor; }
set { fillColor = value; }
}
public bool FillDiagonally
{
get { return fillDiagonally; }
set { fillDiagonally = value; }
}
public byte[] Tolerance
{
get { return tolerance; }
set { tolerance = value; }
}
public EditableBitmap Bitmap
{
get { return bitmap; }
set
{
bitmap = value;
}
}
public abstract void FloodFill(Point pt);
protected void PrepareForFloodFill(Point pt)
{
//cache data in member variables to decrease overhead of property calls
//this is especially important with Width and Height, as they call
//GdipGetImageWidth() and GdipGetImageHeight() respectively in gdiplus.dll -
//which means major overhead.
byteFillColor = new byte[] { fillColor.B, fillColor.G, fillColor.R };
bitmapStride = bitmap.Stride;
bitmapPixelFormatSize = bitmap.PixelFormatSize;
bitmapBits = bitmap.Bits;
bitmapWidth = bitmap.Bitmap.Width;
bitmapHeight = bitmap.Bitmap.Height;
pixelsChecked = new bool[bitmapBits.Length / bitmapPixelFormatSize];
}
}
/// A queue of FloodFillRanges.
public class FloodFillRangeQueue
{
FloodFillRange[] array;
int size;
int head;
///
/// Returns the number of items currently in the queue.
///
public int Count
{
get { return size; }
}
public FloodFillRangeQueue()
: this(10000)
{
}
public FloodFillRangeQueue(int initialSize)
{
array = new FloodFillRange[initialSize];
head = 0;
size = 0;
}
/// Gets the at the beginning of the queue.
public FloodFillRange First
{
get { return array[head]; }
}
/// Adds a to the end of the queue.
public void Enqueue(ref FloodFillRange r)
{
if (size + head == array.Length)
{
FloodFillRange[] newArray = new FloodFillRange[2 * array.Length];
Array.Copy(array, head, newArray, 0, size);
array = newArray;
head = 0;
}
array[head + (size++)] = r;
}
/// Removes and returns the at the beginning of the queue.
public FloodFillRange Dequeue()
{
FloodFillRange range = new FloodFillRange();
if (size > 0)
{
range = array[head];
array[head] = new FloodFillRange();
head++;//advance head position
size--;//update size to exclude dequeued item
}
return range;
}
/// Remove all FloodFillRanges from the queue.
/*public void Clear()
{
if (size > 0)
Array.Clear(array, 0, size);
size = 0;
}*/
}
///
/// Implements the QueueLinear flood fill algorithm using array-based pixel manipulation.
///
public class QueueLinearFloodFiller : AbstractFloodFiller
{
//Queue of floodfill ranges. We use our own class to increase performance.
//To use .NET Queue class, change this to:
// ranges = new Queue();
FloodFillRangeQueue ranges = new FloodFillRangeQueue();
public QueueLinearFloodFiller(AbstractFloodFiller configSource) : base(configSource) { }
///
/// Fills the specified point on the bitmap with the currently selected fill color.
///
/// The starting point for the fill.
public override void FloodFill(System.Drawing.Point pt)
{
watch.Reset();
watch.Start();
//***Prepare for fill.
PrepareForFloodFill(pt);
ranges = new FloodFillRangeQueue(((bitmapWidth + bitmapHeight) / 2) * 5);//new Queue();
//***Get starting color.
int x = pt.X; int y = pt.Y;
int idx = CoordsToByteIndex(ref x, ref y);
startColor = new byte[] { bitmap.Bits[idx], bitmap.Bits[idx + 1], bitmap.Bits[idx + 2] };
bool[] pixelsChecked = this.pixelsChecked;
//***Do first call to floodfill.
LinearFill(ref x, ref y);
//***Call floodfill routine while floodfill ranges still exist on the queue
while (ranges.Count > 0)
{
//**Get Next Range Off the Queue
FloodFillRange range = ranges.Dequeue();
//**Check Above and Below Each Pixel in the Floodfill Range
int downPxIdx = (bitmapWidth * (range.Y + 1)) + range.StartX;//CoordsToPixelIndex(lFillLoc,y+1);
int upPxIdx = (bitmapWidth * (range.Y - 1)) + range.StartX;//CoordsToPixelIndex(lFillLoc, y - 1);
int upY = range.Y - 1;//so we can pass the y coord by ref
int downY = range.Y + 1;
int tempIdx;
for (int i = range.StartX; i <= range.EndX; i++)
{
//*Start Fill Upwards
//if we're not above the top of the bitmap and the pixel above this one is within the color tolerance
tempIdx = CoordsToByteIndex(ref i, ref upY);
if (range.Y > 0 && (!pixelsChecked[upPxIdx]) && CheckPixel(ref tempIdx))
LinearFill(ref i, ref upY);
//*Start Fill Downwards
//if we're not below the bottom of the bitmap and the pixel below this one is within the color tolerance
tempIdx = CoordsToByteIndex(ref i, ref downY);
if (range.Y < (bitmapHeight - 1) && (!pixelsChecked[downPxIdx]) && CheckPixel(ref tempIdx))
LinearFill(ref i, ref downY);
downPxIdx++;
upPxIdx++;
}
}
watch.Stop();
}
///
/// Finds the furthermost left and right boundaries of the fill area
/// on a given y coordinate, starting from a given x coordinate, filling as it goes.
/// Adds the resulting horizontal range to the queue of floodfill ranges,
/// to be processed in the main loop.
///
/// The x coordinate to start from.
/// The y coordinate to check at.
void LinearFill(ref int x, ref int y)
{
//cache some bitmap and fill info in local variables for a little extra speed
byte[] bitmapBits = this.bitmapBits;
bool[] pixelsChecked = this.pixelsChecked;
byte[] byteFillColor = this.byteFillColor;
int bitmapPixelFormatSize = this.bitmapPixelFormatSize;
int bitmapWidth = this.bitmapWidth;
//***Find Left Edge of Color Area
int lFillLoc = x; //the location to check/fill on the left
int idx = CoordsToByteIndex(ref x, ref y); //the byte index of the current location
int pxIdx = (bitmapWidth * y) + x;//CoordsToPixelIndex(x,y);
while (true)
{
//**fill with the color
bitmapBits[idx] = byteFillColor[0];
bitmapBits[idx + 1] = byteFillColor[1];
bitmapBits[idx + 2] = byteFillColor[2];
//**indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
//**screen update for 'slow' fill
if (slow) UpdateScreen(ref lFillLoc, ref y);
//**de-increment
lFillLoc--; //de-increment counter
pxIdx--; //de-increment pixel index
idx -= bitmapPixelFormatSize;//de-increment byte index
//**exit loop if we're at edge of bitmap or color area
if (lFillLoc <= 0 || (pixelsChecked[pxIdx]) || !CheckPixel(ref idx))
break;
}
lFillLoc++;
//***Find Right Edge of Color Area
int rFillLoc = x; //the location to check/fill on the left
idx = CoordsToByteIndex(ref x, ref y);
pxIdx = (bitmapWidth * y) + x;
while (true)
{
//**fill with the color
bitmapBits[idx] = byteFillColor[0];
bitmapBits[idx + 1] = byteFillColor[1];
bitmapBits[idx + 2] = byteFillColor[2];
//**indicate that this pixel has already been checked and filled
pixelsChecked[pxIdx] = true;
//**screen update for 'slow' fill
if (slow) UpdateScreen(ref rFillLoc, ref y);
//**increment
rFillLoc++; //increment counter
pxIdx++; //increment pixel index
idx += bitmapPixelFormatSize;//increment byte index
//**exit loop if we're at edge of bitmap or color area
if (rFillLoc >= bitmapWidth || pixelsChecked[pxIdx] || !CheckPixel(ref idx))
break;
}
rFillLoc--;
//add range to queue
FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);
ranges.Enqueue(ref r);
}
///Sees if a pixel is within the color tolerance range.
///The byte index of the pixel to check, passed by reference to increase performance.
protected bool CheckPixel(ref int px)
{
//tried a 'for' loop but it adds an 8% overhead to the floodfill process
/*bool ret = true;
for (byte i = 0; i < 3; i++)
{
ret &= (bitmap.Bits[px] >= (startColor[i] - tolerance[i])) && bitmap.Bits[px] <= (startColor[i] + tolerance[i]);
px++;
}
return ret;*/
return (bitmapBits[px] >= (startColor[0] - tolerance[0])) && bitmapBits[px] <= (startColor[0] + tolerance[0]) &&
(bitmapBits[px + 1] >= (startColor[1] - tolerance[1])) && bitmapBits[px + 1] <= (startColor[1] + tolerance[1]) &&
(bitmapBits[px + 2] >= (startColor[2] - tolerance[2])) && bitmapBits[px + 2] <= (startColor[2] + tolerance[2]);
}
///Calculates and returns the byte index for the pixel (x,y).
///The x coordinate of the pixel whose byte index should be returned.
///The y coordinate of the pixel whose byte index should be returned.
protected int CoordsToByteIndex(ref int x, ref int y)
{
return (bitmapStride * y) + (x * bitmapPixelFormatSize);
}
///
/// Returns the linear index for a pixel, given its x and y coordinates.
///
/// The x coordinate of the pixel.
/// The y coordinate of the pixel.
///
protected int CoordsToPixelIndex(int x, int y)
{
return (bitmapWidth * y) + x;
}
}
///
/// Represents a linear range to be filled and branched from.
///
public struct FloodFillRange
{
public int StartX;
public int EndX;
public int Y;
public FloodFillRange(int startX, int endX, int y)
{
StartX = startX;
EndX = endX;
Y = y;
}
}
public class EditableBitmap : IDisposable
{
Bitmap bitmap;
int stride;
int pixelFormatSize;
SharedPinnedByteArray byteArray;
///
/// Gets the pixel format size in bytes (not bits, as with Image.GetPixelFormatSize()).
///
public int PixelFormatSize
{
get { return pixelFormatSize; }
}
///
/// Gets the stride of the bitmap.
///
public int Stride
{
get { return stride; }
}
///
/// Gets the underlying
/// that this EditableBitmap wraps.
///
public Bitmap Bitmap
{
get { return bitmap; }
set { bitmap = value; }
}
///
/// Gets an array that contains the bitmap bit buffer.
///
public byte[] Bits
{
get { return byteArray.bits; }
}
private EditableBitmap owner;
///
/// The that this is a view on.
/// This property's value will be null if this EditableBitmap is not a view on another
/// .
///
public EditableBitmap Owner
{
get { return owner; }
}
///
/// Gets a safe pointer to the buffer containing the bitmap bits.
///
public IntPtr BitPtr
{
get
{
return byteArray.bitPtr;
}
}
///
/// Creates a new EditableBitmap with the specified pixel format,
/// and copies the bitmap passed in onto the buffer.
///
/// The bitmap to copy from.
/// The PixelFormat for the new bitmap.
public EditableBitmap(Bitmap source, PixelFormat format)
: this(source.Width, source.Height, format)
{
//NOTE: This ONLY preserves the first frame of the image.
//It does NOT copy EXIF properties, multiple frames, etc.
//In places where preserving them is necessary, it must
//be done manually.
Graphics g = Graphics.FromImage(bitmap);
g.DrawImageUnscaledAndClipped(source, new Rectangle(0, 0, source.Width, source.Height));
g.Dispose();
}
///
/// Creates a new EditableBitmap with the specified pixel format and size,
/// and copies the bitmap passed in onto the buffer. The source bitmap is stretched to
/// fit the new size.
///
///
///
///
///
public EditableBitmap(Bitmap source, PixelFormat format, int newWidth, int newHeight)
: this(newWidth, newHeight, format)
{
//NOTE: This ONLY preserves the first frame of the image.
//It does NOT copy EXIF properties, multiple frames, etc.
//In places where preserving them is necessary, it must
//be done manually.
Graphics g = Graphics.FromImage(bitmap);
g.DrawImage(source, 0, 0, newWidth, newHeight);
g.Dispose();
}
///
/// Creates a new EditableBitmap containing a copy of the specified source bitmap.
///
///
public EditableBitmap(Bitmap source)
: this(source, source.PixelFormat)
{
}
///
/// Creates a new, blank EditableBitmap with the specified width, height, and pixel format.
///
///
///
///
public EditableBitmap(int width, int height, PixelFormat format)
{
pixelFormatSize = Image.GetPixelFormatSize(format) / 8;
stride = width * pixelFormatSize;
int padding = (stride % 4);
stride += padding == 0 ? 0 : 4 - padding;//pad out to multiple of 4
byteArray = new SharedPinnedByteArray(stride * height);
bitmap = new Bitmap(width, height, stride, format, byteArray.bitPtr);
}
#region View Support
///
/// Creates an as a view on a section of an existing .
///
///
///
protected EditableBitmap(EditableBitmap source, Rectangle viewArea)
{
owner = source;
pixelFormatSize = source.pixelFormatSize;
byteArray = source.byteArray;
byteArray.AddReference();
stride = source.stride;
try
{
startOffset = source.startOffset + (stride * viewArea.Y) + (viewArea.X * pixelFormatSize);
bitmap = new Bitmap(viewArea.Width, viewArea.Height, stride, source.Bitmap.PixelFormat,
(IntPtr)(((int)byteArray.bitPtr) + startOffset));
}
finally
{
if (bitmap == null)
byteArray.ReleaseReference();
}
}
///
/// Creates an as a view on a section of an existing .
///
/// The area that should form the bounds of the view.
public EditableBitmap CreateView(Rectangle viewArea)
{
if (disposed)
throw new ObjectDisposedException("this");
return new EditableBitmap(this, viewArea);
}
private int startOffset;
///
/// If this is a view on another instance,
/// this property gets the index where the pixels that are within the view's pixel area start.
///
public int StartOffset
{
get { return startOffset; }
}
#endregion
private bool disposed;
public bool Disposed
{
get { return disposed; }
}
#region IDisposable Members
public void Dispose()
{
Dispose(true);
}
#endregion
protected void Dispose(bool disposing)
{
if (disposed)
return;
bitmap.Dispose();
byteArray.ReleaseReference();
disposed = true;
//Set managed object refs to null if explicitly disposing, so that they can be cleaned up by the GC.
if (disposing)
{
owner = null;
bitmap = null;
}
}
~EditableBitmap()
{
Dispose(false);
}
}
internal class SharedPinnedByteArray
{
internal byte[] bits;
internal GCHandle handle;
internal IntPtr bitPtr;
int refCount;
public SharedPinnedByteArray(int length)
{
bits = new byte[length];
// if not pinned the GC can move around the array
handle = GCHandle.Alloc(bits, GCHandleType.Pinned);
bitPtr = Marshal.UnsafeAddrOfPinnedArrayElement(bits, 0);
refCount++;
}
internal void AddReference()
{
refCount++;
}
internal void ReleaseReference()
{
refCount--;
if (refCount <= 0)
Destroy();
}
bool destroyed;
private void Destroy()
{
if (!destroyed)
{
handle.Free();
bits = null;
destroyed = true;
}
}
~SharedPinnedByteArray()
{
Destroy();
}
}
}
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
The algorithm is powerful, but i want to ask about is there any way to control the threashold from the code insted of control it manually??
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
 | License 
Jonas Beckeman | 23:31 23 Jan '07 |
|
|
Hi, great article and code!
I couldn't find any licence or copyright notices in the code. Do you consider it public domain? I would like to include it in my project here http://www.codeproject.com/csharp/Endogine.asp - would that be possible? If so, how do you want them commented (so credit goes where credit's due)?
A side note: the source doesn't compile unless the namespaces of PicturePanel and EditableBitmap are changed to FloodFill2.
Thanks!
|
| Sign In·View Thread·PermaLink | 1.00/5 |
|
|
|
|
|
|
I used your earlier flood fill post's code and now I'll have a deeeeep look at this one - just looked at it breifly, couldn't wait 
Thanks a lot buddy, you're great! 
|
| Sign In·View Thread·PermaLink | 5.00/5 |
|
|
|
|
|
|
This is just absolutely amazing, along with the pointerless image processing article. It really really shows what a good programmer can do with C#.
I mean, this is all managed code! I can hardly believe it!
One thing I'm totally baffled about: how the hell is it that bounds checking isn't incurring any notable performance penalty? It certainly isn't eligible for omission in any of the methods. Is it just because it's negligible relative to the rest of the operation? Or is the JITter doing something funky?
Wow.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
reinux wrote: This is just absolutely amazing, along with the pointerless image processing article. It really really shows what a good programmer can do with C#.
Thanks! 
reinux wrote: One thing I'm totally baffled about: how the hell is it that bounds checking isn't incurring any notable performance penalty? It certainly isn't eligible for omission in any of the methods. Is it just because it's negligible relative to the rest of the operation? Or is the JITter doing something funky?
Rico Mariani a wrote a blog post[^] a while back regarding the costs of range checking. He actually modified the JIT engine to not emit range checking, and compared the performance when using the modified JIT engine to the normal performance. He concluded that the performance hit of range-checking was negligable. I'm not convinced that what he checked against was necessarily the optimal test case, but I do tend to think that his results would hold in most cases.
What really surprised me is the fact that, even in just a simple iteration test, array access seemed to outperform pointers by a noticeable margin. We could chock it up to optimizations, but what sort of optimizations could there be? Or maybe there is something that the compiler adds to try to make unsafe code a little 'safer', that adds a perf hit? Sometime when I get a chance I'll probably use sos and similar tools to have a look at the generated machine code, as I did for delegates and dynamic methods once.
I would also be interested to find out how this C# code compares against equivalent C++ code. I tried with C++/CLI before with 2 tests - simple array access and pointers - and it ended up being actually noticeably slower. Nish and I both independently verified that the IL that was output was inferior to what the C# compiler generated, at least for the compiler version I was using (the release version that comes with the Software Architect version of VS). But unmanaged C++ would be a different situation, and I'm interested to find out what the results would be.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Hmm cool.
I've always been happy with array performance in big applications, but I never thought it'd start becoming negligible even in such a tight loop.
Here's a really blunt benchmark I did with linked lists a couple years ago:
http://img292.imageshack.us/img292/2209/performancels6.gif[^]
The only thing I could really say for sure from this test was that in allocating lots of small objects (10,000,000 8 byte nodes with 8 bytes overhead each), C# 2.0 outperforms unmanaged C++. Also that the .NET 2.0 (Beta 2) JITter has some improvements over .NET 1.1.
I'm willing to bet though that even with your flood algorithm, C# would still be just as fast if not faster than unmanaged C++. I thought bounds checking would inevitably make things slower with image processing, but hey!
Now if only Microsoft would stop beating around the bush and fix inlining methods with struct parameters
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
reinux wrote: I thought bounds checking would inevitably make things slower with image processing, but hey!
Well, it does, but not enough to worry about.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Maybe good code in .NET enviroment, but i wont believe it is compareable to plain c or c++.
If i didnt misunderstood, then ngen'ed applications are real binaries.
I compared this solution with a hack in plain c, i created for this year icfp.
results:
this solution array:89 ms
this solution lock bits:76 ms
my solution :13 ms
hardware:2*xeon 3.8GHz (woodcrest), 3.5GB ram
image size 1560x1030
image outline basic B (rectangle 764-778,498-514), P (pattern 761-0,502-0), w(hite)
the basic image was mirrored two times giving
Pw|wP
wB|Bw
wB|Bw
Pw|wP
the pattern was like (snake)
... ----------------
... |
---------------- ...
| ...
---------------- ...
a closer look at pixel level shows like
XXXOXO
XOXXXX
OOOOX
XXXOXX
XOXXXO
the maximum expected depth ist 3*MAX(width, height)/MIN(width, height)
friendly kodieropa
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Hmm yeah that's quite a difference. I don't think I've ever seen such a big difference between C and C# performance. Usually the trend seems to be that C# often generates slightly faster code than full fledged C++, and straight C generates faster code than C# -- but not by this much.
Have you tested it on a different CPU? Maybe ngen doesn't optimize very well on Xeons.
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
reinux wrote: Have you tested it on a different CPU? Maybe ngen doesn't optimize very well on Xeons.
Perhaps a different cpu will show a smaller advantage, but i think it is a risk to bet on it!
It would a waste of time, looking for optimal hardware for ngen or .net.
My hint is caused by the fact, that my teammate (.net dev.) showed me this article after the contest in a debate about recursive implementations.
I still believe that .net is usefull for business logic, as long as you do not have too much work close to bits and bytes.
friendly Kodieropa
-- modified at 16:34 Thursday 30th August, 2007
PS: not only the calculation is wrong - width*height/3
-- modified at 16:39 Thursday 30th August, 2007
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Well, I mean, test it on a Pentium 4 or Core Duo maybe? Then again maybe Xeon isn't that much different.
Hmm...
|
| Sign In·View Thread·PermaLink | 2.00/5 |
|
|
|
|
|
|
Bounds checking is removed for certain types of loops -- where the compiler can tell at compile time, that the index will never be out of bounds.
check out VG.net: www.vgdotnet.comAn animated vector graphics system integrated in VS.net
|
| Sign In·View Thread·PermaLink | |
|
|
|
|
|
|
Correct; however, as reinux pointed out, "It certainly isn't eligible for omission in any of the methods." The size of the bitmap's byte array is unknown from the compiler's perspective.
|
| Sign In·View Thread·PermaLink | 5.00/5 |
|
|
|
|
|
