Jump to content

Pointers and speed (re. edge-shader for objects)


Red ochre

Recommended Posts

Intestines: http://i.imgur.com/J4OxE4p.png
Terrain/height map?: http://i.imgur.com/rfR5PtK.png
This Edge Shader: http://i.imgur.com/gW2BiP8.png
TR's 'Contour': http://i.imgur.com/LXRY4hd.png

This is for shading objects dependant on the distance to the nearest edge.
Similar to TR's 'Contour' but different (compare last two images).
I did try shading from colour/tone 'edges' as well but in this form it is just too slow.

I'm not 100% sure I'm using unsafe pointers correctly here.
If anyone has any corrections or ideas to improve the speed it would be useful and appreciated.
The first part, testing for edges and loading the ArrayLists is very quick, typically less than a second (800 by 600 canvas).
However, looping through the arrays takes a while, depending on the size of the array due to complexity of the object edge (just about acceptable).
It also seems to take a very long time once 'OK' has been clicked? - is there a way for it to simply copy over what it has already done. It seems as if it is calculating everything again?

I'm using VSExpress 2010 (3.5.NET) and Pdn3.5.11 for this as VSexpress2013 and W10 are being awkward at the moment.
(I had VSE2013 running ok in W8.1, now having problems with build events using 4.5NET).
It uses another surface. That part is in the full code in the project at dropbox here:
https://www.dropbox.com/s/gedz11hd8vhfw06/EdgeShader1%20(2).zip?dl=0

Below is just the 'user entered code'.
And here is the .dllEdgeShader1.zip

All ideas useful! Thanks in advance.

 #region User Entered Code
        /* =================================================== */
        /* EdgeShader    */
        /* Name    */
        /* (c) 2015 Red ochre (John Robbins)     */
        /* comment   */
        /* Description: uses distance to nearest edge to colour an image*/
        /*     */
        /* ========================================== ======== */

        // Name: EdgeShader
        // Author: Red ochre (John Robbins)
        // Submenu: Advanced
        // URL: http://www.getpaint.net/redirect/plugins.html
        // Title:EdgeShader                       Red ochre Feb 2015

        #region UICode
        int threshA = 255; // [0,255] Opacity threshold
        int maxdistance = 50; // [0,100] Maximum distance
        double effectmix = 50; // [0,100] Effect mix %
        bool swapcols = false;
        #endregion
        //BASIC IDEA: 
        //load up arraylists with edges
        //then do normal y/x loops for every opaque pixel and loop through arrays to find nearest edge pixel distance
        //change pixel colour according to distance and mix with src
        //- will be slow but slightly quicker than checking every surrounding pixel - quicker for less edge and more distance
        //slower for complex edges and short distances - comparing with a blurred surface is better for that.
        //did have a version of this working finding colour/tone edges too but far too slow using this method.
        //I have ideas for another (more efficient) way to do this.

        //PROBLEM - am I using pointers correctly in y/x loops at end?
        //*srcpix works but *destpix crashes Pdn although fine in VS? - hence removed and using dest[x,y]
        //NOTE: I am using another surface 'dest' as multithread detection doesn't know when it's found an edge - I assume.
       

        Boolean AlphaEdges(Surface dest, Surface src, Rectangle rect, int x, int y)
        {
            bool Aedge = false;

            ColorBgra TL = src[x - 1, y - 1];//Top Left
            ColorBgra TM = src[x, y - 1];//Top Middle
            ColorBgra TR = src[x + 1, y - 1];//Top Right
            ColorBgra ML = src[x - 1, y];//Middle Left
            //ColorBgra MM = src[x, y];//Middle or 'current pixel'- not required here
            ColorBgra MR = src[x + 1, y];//Middle Right
            ColorBgra BL = src[x - 1, y + 1];//Bottom Left
            ColorBgra BM = src[x, y + 1];// Bottom Middle
            ColorBgra BR = src[x + 1, y + 1];//Bottom Right
            if (TL.A < threshA || TM.A < threshA || TR.A < threshA || ML.A < threshA || MR.A < threshA || BL.A < threshA || BM.A < threshA || BR.A < threshA) { Aedge = true; }
            return Aedge;
        }
    
        unsafe void Render(Surface dest, Surface src, Rectangle rect)//unsafe for pointers!
        {
            dest.CopySurface(src, rect.Location, rect);// copy surface quicker than looping through
            ColorBgra PC = (ColorBgra)EnvironmentParameters.PrimaryColor;
            ColorBgra SC = (ColorBgra)EnvironmentParameters.SecondaryColor;
            if (swapcols) { SC = (ColorBgra)EnvironmentParameters.PrimaryColor; PC = (ColorBgra)EnvironmentParameters.SecondaryColor; }
            int H = rect.Bottom - rect.Top;
            int W = rect.Right - rect.Left;
            ColorBgra cp;
            ArrayList Xedgepixels = new ArrayList();
            ArrayList Yedgepixels = new ArrayList();
            int B, G, R, A, nx, ny;
            int xdiff = 0; int ydiff = 0;
            int neari = 0;
            double shadrat = 0, ishadrat;
            double emix = effectmix / 100; double iemix = 1 - emix;
            int MDsq = maxdistance * maxdistance;
            int mindistSQ = MDsq;
            int distSQ = 0;
            //loop thru each pixel, if an 'edge' add coords to arrays
            //NOT processing edge of selection to avoid out of bounds errors - could adjust methods later
            for (int y = rect.Top + 1; y < rect.Bottom - 1; y++) 
            {
                if (IsCancelRequested) return;
 
                for (int x = rect.Left + 1; x < rect.Right - 1; x++)
                {
                    cp = src[x, y];
                    A = cp.A;

                    if (A > threshA)
                    {
                        //Load ArrayLists
                        if (AlphaEdges(dest, src, rect, x, y)) { Xedgepixels.Add(x); Yedgepixels.Add(y); }
                    }
                }
            }

                for (int y = rect.Top; y < rect.Bottom; y++)
                {
                    if (IsCancelRequested) return;
                    ColorBgra* srcpix = src.GetPointAddressUnchecked(rect.Left, y);
                   // ColorBgra* destpix = src.GetPointAddressUnchecked(rect.Left, y);//that way compiles but attempts to read protected mem?
                    //don't understand why as the position should be exactly as srcpix?
                    for (int x = rect.Left; x < rect.Right; x++)
                    {
                      
                        cp = *srcpix;

                        A = cp.A;
                        if (A > threshA)
                        {
                            mindistSQ = MDsq;
                            for (int i = 0; i < Xedgepixels.Count; i++)
                            {
                                nx = (int)Xedgepixels[i];
                                ny = (int)Yedgepixels[i];
                                xdiff = x - nx; ydiff = y - ny;
                                distSQ = (xdiff * xdiff) + (ydiff * ydiff);
                                if (distSQ < mindistSQ) { mindistSQ = distSQ; neari = i; if (mindistSQ < 2) { break; } }
                             }//end i loop
                         
                            shadrat = Math.Sqrt(mindistSQ) / maxdistance;
                            ishadrat = 1 - shadrat;


                            double Bnew = (shadrat * SC. + (ishadrat * PC.;
                            double Gnew = (shadrat * SC.G) + (ishadrat * PC.G);
                            double Rnew = (shadrat * SC.R) + (ishadrat * PC.R);

                            B = (int)((iemix * cp. + (emix * Bnew));
                            G = (int)((iemix * cp.G) + (emix * Gnew));
                            R = (int)((iemix * cp.R) + (emix * Rnew));

                            cp = ColorBgra.FromBgra(Int32Util.ClampToByte(, Int32Util.ClampToByte(G), Int32Util.ClampToByte(R), Int32Util.ClampToByte(A));

                           dest[x, y] = cp;
                            //*destpix = cp;//doesn't work
                        }//end of if A

                        srcpix++;
                       // destpix++;
                    }// end of x loop
                }//end of y loop
             }//end render
        #endregion
  • Upvote 2

 

Red ochre Plugin pack.............. Diabolical Drawings ................Real Paintings

 

PdnForumSig2.jpg

Link to comment
Share on other sites

// ColorBgra* destpix = src.GetPointAddressUnchecked(rect.Left, y);//that way compiles but attempts to read protected mem?

 

Shouldn't that be, destpix = dst.GetPointAddressUnchecked(rect.Left, y) ?

  • Upvote 1
Link to comment
Share on other sites

I must say, using pointers instead of array indexing to move the pixels in order to speed up the plugin seems like tossing out a toothpick in the hope of making more room in a crowded house. A plugin that uses indexing to just copy the source to the destination runs in a thrice. That's not the part that makes the plugin run slowly; it's searching the edge lists for every pixel that takes the time. Maybe (maybe) using pointers in the edge search loop would help somewhat.

Edited by MJW
Link to comment
Share on other sites

I wouldn't bother with unsafe pointer usage here. You have a million other things that need to be optimized first before I'd start worrying about that.

 

For instance, please do not use System.Collections.ArrayList. It will be excruciatingly slow for what you're doing with it. Use System.Collections.Generic.List<T> instead.

 

Edit: What MJW said :)

I must say, using pointers instead of array indexing to move the pixels in order to speed up the plugin seems like tossing out a toothpick in the hope of making more room in a crowded house.

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html

forumSig_bmwE60.jpg

Link to comment
Share on other sites

Slow or not, I've got a use for this plugin.

 

The reason it's so slow is that it's basically an n-squared algorithm, so the time it takes increases rapidly with the number of pixels. The basic idea is equivalent to a well-known problem called "nearest neighbor."  There are algorithms that can solve the problem in about n*log(n) time. One basic idea is to build a tree structure in which most branches don't need to be traversed because no point in the branch can be closer than the nearest point already found. The trick is to build a well-balanced tree in n*long(n) time. I'll try to add some more details soon.

Edited by MJW
Link to comment
Share on other sites

Thank you all for the responses.

MJW - well spotted. I tried "ColorBgra* destpix = dest.GetPointAddressUnchecked(rect.Left, y);" and that cures that particular problem.
(Render is using 'dest' an extra surface). It doesn't seem to improve the speed sadly - as you (and Rick) could foresee.
Regarding speed, I realise that for every opaque pixel it needs to loop through the whole array, so the time needed increases exponentially with the complexity of the object outline.
However, for smallish outline arrays it is doing less checks per pixel than if I were checking all surrounding pixels. That's a terrible explanation from me!
I fully agree that it is not efficient for complex selections. I do have some other ideas on how to do this (without ArrayLists) but look forward to seeing any other ideas.

BoltBait - I thought looping from "rect.Top + 1 too rect.Bottom - 1" (same idea for x), would be sufficient but you are right. I should be using something like
"int H = Selection.Bottom - Selection.Top;
for (int ya = 0; ya < H-2; ya++){
int y = rect.Top + 1 + ya;"
And protecting within the method too.

Rick - Thanks. I wanted an array that could be dynamically re-sized, but if ArrayLists are slow I will avoid them. I will investigate other possibilites, I see more information further down the msdn page
https://msdn.microsoft.com/en-us/library/system.collections.arraylist(v=vs.110).aspx

Thanks again for all your input.

 

Red ochre Plugin pack.............. Diabolical Drawings ................Real Paintings

 

PdnForumSig2.jpg

Link to comment
Share on other sites

Thanks Rick - The List<T> class does look better than ArrayLists. I will try that route.

I may find a way without first storing the edge pixels in an array at all.
Then it's a matter of working out which is most efficeint/quickest.

 

Red ochre Plugin pack.............. Diabolical Drawings ................Real Paintings

 

PdnForumSig2.jpg

Link to comment
Share on other sites

Regarding speed, I realise that for every opaque pixel it needs to loop through the whole array, so the time needed increases exponentially with the complexity of the object outline.

 

Not exponentially, actually, just n2. Still, n2 can be pretty slow when there are lots of pixels.

 

I'm probably missing the obvious, but why do you need an extra surface? It seems like you could write the results into the regular dst surface inside the normal render loops. If you could, you'd be able to take advantage of multiple cores for the part that takes most of the time.

 

Instead of storing the x and y results in two List<T>s, you ought to make a struct (not class) consisting of an x and y value. You could make the values shorts (16 bits)  instead of ints. Then you can make a List of these xy structs.

 

To really speed it up, though, you'll need to use a faster algorithm.

Edited by MJW
Link to comment
Share on other sites

I started out trying to use codelab but couldn't find any way to avoid 'striping', or other strange results.
I do not understand threading but if two threads are looking for the shortest distance to the edge of an object how does each thread compare it's distance and know when to stop?
If I've missed something (quite likely   ;) ) and you can find a multithreaded way to do what the current code is doing, that would be extremely useful.

 

 

To really speed it up, though, you'll need to use a faster algorithm.

I completely agree.

 

Many thanks for the tips MJW!

 

Red ochre Plugin pack.............. Diabolical Drawings ................Real Paintings

 

PdnForumSig2.jpg

Link to comment
Share on other sites

Instead of storing the x and y results in two List<T>s, you ought to make a struct (not class) consisting of an x and y value. You could make the values shorts (16 bits)  instead of ints. Then you can make a List of these xy structs.

 

Nah, just use PaintDotNet.Rendering.PointInt32. It is a struct with an X and Y, both 32-bit integers, and should cover pretty much anything you need. It even implements stuff like IEquatable<PointInt32> which means it'll be efficient to use as a key in a Dictionary<PointInt32, *>. It supports string formatting and parsing, as well as XAML serialization and deserialization.

 

Best of all, you don't have to write it yourself.

 

Other friends of this struct include PointFloat, PointDouble, RectInt32, RectFloat, RectDouble, SizeInt32, SizeFloat, SizeDouble, VectorInt32, VectorFloat, VectorDouble, Matrix3x2Float, Matrix3x2Double. I cranked these out during 4.0's development and was careful to ensure consistency to high levels on the OCD scale. They are better than the primitives from System.Drawing or System.Windows.

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html

forumSig_bmwE60.jpg

Link to comment
Share on other sites

BTW, this happens because you're calling src.GetPointAddressUnchecked(). And yes, the source Surface is write protected when an Effect is running, precisely to catch mistakes like this :)

 

// ColorBgra* destpix = src.GetPointAddressUnchecked(rect.Left, y);//that way compiles but attempts to read protected mem?

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html

forumSig_bmwE60.jpg

Link to comment
Share on other sites

I started out trying to use codelab but couldn't find any way to avoid 'striping', or other strange results.

I do not understand threading but if two threads are looking for the shortest distance to the edge of an object how does each thread compare it's distance and know when to stop?

 

 

I don't think this plugin should be done in CodeLab, though it might be doable by using some type of semaphore-like synchronization for the edge-list-making phase. In any case, building the the edge list has to be done completely before the second, shading, phase begins, which is easier in VS then in CodeLab.

 

If I correctly understand what the second phase of the code is doing, it just takes each pixel, looks through the edge list for the nearest edge pixel, and shades the pixel based on the distance. There doesn't seem to be any order dependency in this step, nor any reason it couldn't be done in parallel for several pixels.

 

EDIT: Parallel computations can be done in different threads provided that the threads don't try to modify the same values and none of the threads modify something another thread might be using (keeping in mind that all the local variables, like x and y, are allocated separately for each thread, so they don't count). In the second phase, only the pixel is modified, and each thread has its own unique set of pixels.

Edited by MJW
Link to comment
Share on other sites

Brief update before sleep.

List<short> Xedgepixels and List<short> Ypixels work well - seems fasters.
Still working on creating the struct - getting there - loads more MSDN reading to do!

As mentioned I think there is a more efficient way for this but learning how to speed this version up will be very useful generally.

Thanks again.

 

Red ochre Plugin pack.............. Diabolical Drawings ................Real Paintings

 

PdnForumSig2.jpg

Link to comment
Share on other sites

It's definitively better to use a struct, but I don't think things like that are going to make a difference noticeable for the user.

 

I have never really used CodeLab, but doesnt the current code already run in parallel? The code in the Render method just Loops over the Pixel in one Rect but in general a selection consist of many rectangles and many calls to Render with different rectangles are made parallel by paint.net, no? If so, if the nearest edge of a Pixel is in a rectangle other than the currently processed, this code will not deliver the expected result.

 

Again, I have not much knowledge about CodeLab, but I think you should do this in Visual Studio, it would be quite easy I think. I did something very similar in my Reverse Blend Plugin, where I also needed to calculate Information from the whole selection (in my case the average Color) before rendering the result. I called the PropertyBaseEffect constructor with the EffectFlags.SingleRenderCall flag and parallelized the process myself. If the algorithm allows it, this is an easy Task in C# (using e.g. Parallel.For). And you're algorithm could be processed in parallel withouth Problems I think.

 

One last Thing about List<T> and the like: These classes manage internal Arrays and resize/reallocate them if needed. If an item is added, but the internal Array is already "full", a new, larger, Array is allocated, the elements from the old Array copied and then the new item is added. If you use These classes in a way in which they Need to resize often, this can be time consuming since every time all the old elements Need to be copied. So if you know how much items you are going to have in the list or if you at least can make an educated guess (better too many than too few, Memory is seldom an issue), it's better to initialize it with the new List<T>(int capacity) constructor.

 

edit: I just took a look at the whole solution, Forget the second paragraph

 

edit2: I wrote a quick template to Show what I meant, I hope you don't mind. This won't work out of the box, you Need to Change the commented sections in the OnRender Method.

EdgeShaderParallel.zip

Edited by ArgusMagnus
  • Upvote 1

My batch Image Processor: https://imagenator.codeplex.com

Link to comment
Share on other sites

Thanks for your input and ideas ArgusMagnus!

As you've probably gathered I'm not a pro coder!
I believe by using the extra surface in VS this forces the processing from src to 'dest' single threaded? (dest then gets copied to dst normally).
The idea was suggested to me by user 'Null54' a while back when I was having R.O.I problems using codelab.

Will take a look at your template - thanks! (may take some time as many ideas to explore and much still to learn!)

 

 

Nah, just use PaintDotNet.Rendering.PointInt32

Missed that last night - thanks Rick - will try those too!

 

Red ochre Plugin pack.............. Diabolical Drawings ................Real Paintings

 

PdnForumSig2.jpg

Link to comment
Share on other sites

Yes, your code is processed single threaded, but this is because you do the calculations and Rendering to the temporary dest Surface in the OnSetRenderInfo method (or more precisely, you call your Render method from the OnSetRenderInfo method) which is called single threaded as far as I know. I guess the only reason to use the temporary Surface and then copy it to the dst in the OnRender method and not directly write to the dst Surface is to not break the rules which state that you may not write to dst outside the scope of the OnRender method.

 

I think this is a rather ugly solution and I wouldn't recommend it, but then again, I'm new to paint.net plugin development and I don't know what the old foxes here or the developers of paint.net recommend, so don't give too much weight to my opinion :-)

 

If you pass the EffectFlags.SingleRenderCall to the constructor you could move your whole calculations as they are now to the OnRender method and eliminate the Need for a temporary Surface.

Edited by ArgusMagnus

My batch Image Processor: https://imagenator.codeplex.com

Link to comment
Share on other sites

Surface and then copy it to the dst in the OnRender method and not directly write to the dst Surface is to not break the rules which state that you may not write to dst outside the scope of the OnRender method.

 

 

In this routine, there's no reason I can see to write outside the selection. "rect" should be set to the selection region, not the surface. The code that builds the edge records need to read all the pixels in the surface, so instead of rect, it could use src for the index limits.

 

If you pass the EffectFlags.SingleRenderCall to the constructor you could move your whole calculations as they are now to the OnRender method and eliminate the Need for a temporary Surface.

 

That would probably work, but I wouldn't recommend doing it, since I think the edge-building part should be done at the OnRender stage, and the slow part should be done in the regular render code, where it can be assigned to multiple cores. (As a side comment, I've never understood why the PDN divides the surface into more ROIs then the number of cores in the system. What gain is there from "parallelizing" code that runs on the same core? Doesn't it actually just get run sequentially? I'm far from an expert on multi-threading, so I'm probably missing the obvious.)

Link to comment
Share on other sites

I never said anything about writing outside the selection :-)

 

Of what I have seen and confirmed through testing so far (not 100% sure) the OnRender method is called by the PDN system in parallel, the body of the OnRender method is usually just a loop which calls the Render method for every rectangle in the selection, regular for-loop, nothing parallel.

 

As a reply to your side comment: The PDN system has no way of knowing how long a plugin effect will take to compute, it cannot know if the calculation will take the same time for to different rois even if they contain the same amount of pixels, and in general the calculation times for two rois will be different. So if it just runs the calculation of 4 rois in parallel on 4 threads (on a 4 core system) odds are that 1, 2 or 3 threads finish before the 4th and have to wait idle for the last one. That's one of the reasons workload is split into more parts than available cores.

My batch Image Processor: https://imagenator.codeplex.com

Link to comment
Share on other sites

That's a good point about different regions taking different amounts of time. I'm still not convinced that the extra overhead from dividing the surface into so many ROIs is worth the gain. For plugins written in VS, which can do the setup once in OnSetRenderInfo, that's probably much less a consideration. My bias against the small ROIs is largely based on some CodeLab plugins I've written in which the complex pre-render setup probably takes nearly as much time as rendering the pixels for the ROI.

 

I never said anything about writing outside the selection :-)

 

I should have read your comment more carefully. In any event, my basic point is unchanged: there's no reason I can see why the dst surface can't be written directly in the normal Render routines, with no auxiliary surface. (No doubt, because I've repeated that point so many times, it will turn out to be untrue.) When I said OnRender, I meant OnSetRenderInfo. I haven't looked at that stuff for a while, and had forgotten what does what.

Edited by MJW
Link to comment
Share on other sites

  • 2 weeks later...

Here's my attempt to implement the EdgeShader with a different algorithm:

 

Hidden Content:
        #region User Entered Code
        // Name: EdgeShaderMJW
        // Author: Red ochre (John Robbins) and MJW
        // Submenu: Advanced
        // URL: http://www.getpaint.net/redirect/plugins.html
        // Title:EdgeShader                       Red ochre Feb 2015
        
        #region UICode
        int Amount1 = 255; // [0,255] Opacity threshold
        int Amount2 = 50; // [0,100] Maximum distance
        double Amount3 = 50; // [0,100] Effect mix %
        bool Amount4 = false; // [0,1] Swap Colors
        #endregion
        
           
        Boolean AlphaEdges(int x, int y)
        {
            int left = (x == 0) ? x : x - 1;
            int right = (x == maxX) ? x : x + 1;
            int top = (y == 0) ? y : y - 1;
            int bottom = (y == maxY) ? y : y + 1;
            bool Aedge = false;
            ColorBgra TL = Src[left, top];//Top Left
            ColorBgra TM = Src[x, top];//Top Middle
            ColorBgra TR = Src[right, top];//Top Right
            ColorBgra ML = Src[left, y];//Middle Left
            //ColorBgra MM = src[x, y];//Middle or 'current pixel'- not required here
            ColorBgra MR = Src[right, y];//Middle Right
            ColorBgra BL = Src[left, bottom];//Bottom Left
            ColorBgra BM = Src[x, bottom];// Bottom Middle
            ColorBgra BR = Src[right, bottom];//Bottom Right
            if (TL.A < threshA || TM.A < threshA || TR.A < threshA ||
                ML.A < threshA || MR.A < threshA || BL.A < threshA ||
                BM.A < threshA || BR.A < threshA) { Aedge = true; }
            return Aedge;
        }
        
        Surface Src;
        int maxX, maxY;
        FloodFill floodFill;
        int [,] distanceArray = null;
        
        int threshA;
        int maxdistance;
        double effectmix;
        bool swapcols;
        
        
        // Call from OnSetRenderInfo
        void InitializeRendering(Surface dst, Surface src)
        {
            Src = src;
            maxX = src.Width - 1; maxY = src.Height - 1;
            
            threshA = Amount1; // Opacity threshold
            maxdistance = Amount2; // Maximum distance
            effectmix = Amount3; // Effect mix %
            swapcols = Amount4;
        
            if (distanceArray == null)
                distanceArray = new int[src.Width, src.Height];
            if (floodFill == null)
                floodFill = new FloodFill(0, 0, maxX, maxY);
            
            int maxdist2 = Sq(maxdistance);
            // Fill in the starting distance values: -1 for transparent, 0 for edge, maxdist2 otherwise.
            for (int y = 0; y < src.Height; y++)
            {
                for (int x = 0; x < src.Width; x++)
                {
                    distanceArray[x, y] = (src[x, y].A < threshA) ? -1 : maxdist2;
                    //if (src[x, y].A < threshA)
                    //    distanceArray[x, y] = -1;
                    //else if (AlphaEdges(x, y))
                    //    distanceArray[x, y] = 0;
                    //else
                    //    distanceArray[x, y] = maxdist2;
                }
            }
            
             // Fill in the nearest distances.
            for (int y = 0; y < src.Height; y++)
            {   
                for (int x = 0; x < src.Width; x++)
                {
                    if ((distanceArray[x, y] > 0) && AlphaEdges(x, y))
                    {
                        currX = x; currY = y;    // Global variables -- kind of kludgy.
                        floodFill.Fill4(x, y, FillDistance);
                    }
                }
            }
        }
        
        void Render(Surface dst, Surface src, Rectangle rect)
        {
            // For CodeLab processing.
            if (distanceArray == null)
            {
                dst.CopySurface(src, rect.Location, rect);// copy surface quicker than looping through
                return;
            }
            
            ColorBgra PC = (ColorBgra)EnvironmentParameters.PrimaryColor;
            ColorBgra SC = (ColorBgra)EnvironmentParameters.SecondaryColor;
            if (swapcols) { SC = (ColorBgra)EnvironmentParameters.PrimaryColor; PC = (ColorBgra)EnvironmentParameters.SecondaryColor; }
            int H = rect.Bottom - rect.Top;
            int W = rect.Right - rect.Left;
            ColorBgra cp;
            int B, G, R, A;
            double shadrat = 0, ishadrat;
            double emix = effectmix / 100; double iemix = 1 - emix;
            double distScale = 1.0 / (double)maxdistance;
        
            for (int y = rect.Top; y < rect.Bottom; y++)
            {
                if (IsCancelRequested) return;
                for (int x = rect.Left; x < rect.Right; x++)
                {        
                    cp = src[x, y];
                    if (cp.A < threshA)
                    {
                        dst[x, y] = cp;
                    }
                    else
                    {   
                        shadrat = distScale * Math.Sqrt((double)distanceArray[x, y]);
                        ishadrat = 1 - shadrat;
        
                        double Bnew = (shadrat * SC. + (ishadrat * PC.;
                        double Gnew = (shadrat * SC.G) + (ishadrat * PC.G);
                        double Rnew = (shadrat * SC.R) + (ishadrat * PC.R);
        
                        B = (int)((iemix * cp. + (emix * Bnew));
                        G = (int)((iemix * cp.G) + (emix * Gnew));
                        R = (int)((iemix * cp.R) + (emix * Rnew));
                        A = cp.A;
        
                        cp = ColorBgra.FromBgra(Int32Util.ClampToByte(,
                                                Int32Util.ClampToByte(G),
                                                Int32Util.ClampToByte(R), Int32Util.ClampToByte(A));
                        dst[x, y] = cp;
                    }
                }// end of x loop
            }//end of y loop
        }//end render
        
        
        // Flood fill delegate.
        int currX, currY;
        bool FillDistance(int x, int y)
        {       
            int dist2 = Sq(x - currX) + Sq(y - currY);
            if (dist2 < distanceArray[x, y])
            {
                distanceArray[x, y] = dist2;
                return true;
            }
            return false;
        }
        
        int Sq(int x)
        {
            return x * x;
        }
        // Flood fill routine based on "A Seed Fill Algorithm" by Paul Heckbert
        // from "Graphics Gems", Academic Press, 1990
        // Some details improved by MJW, including better handling of the initial span, and
        // elimination of the unnecessary retesting of the pixels to the left and right of the
        // parent span.
        class FloodFill
        {
            private SpanStack stack;
        
            public FloodFill()
            {
                stack = new SpanStack();
            }
            
            public FloodFill(int xMin, int yMin, int xMax, int yMax)
            {
                stack = new SpanStack();
                SetRange(xMin, yMin, xMax, yMax);
        
            }
            
            // Set the allowable ranges for X and Y.
            // Must be called before the first fill.
            protected int xMin, yMin, xMax, yMax;
            public void SetRange(int xMin, int yMin, int xMax, int yMax)
            {
                this.xMin = xMin; this.yMin = yMin;
                this.xMax = xMax; this.yMax = yMax;
                stack.SetYRange(yMin, yMax);
            }
        
            public void DeallocateMemory()
            {
                stack.DeallocateShadows();
            }
        
            public int GetAllocationCount()
            {
                return stack.ShadowCount;
            }
        
            private class SpanStack
            {
                private int yMin, yMax;
                private int shadowCount = 0;
        
                public SpanStack()
                {
                    InitShadows();
                }
        
                public void SetYRange(int yMin, int yMax)
                {
                    this.yMin = yMin; this.yMax = yMax;
                }
        
                private class Shadow
                {
                    public int y, yParent, xLeft, xRight;
                    public Shadow previous, next;
                }
                private Shadow shadowsHead;
                private Shadow shadows;
        
                public void DeallocateShadows()
                {
                    InitShadows();
                }
        
                public int ShadowCount
                {
                    get { return shadowCount; }
                }
        
                private void InitShadows()
                {
                    shadowsHead = new Shadow();
                    shadows = shadowsHead;
                    shadowCount = 0;
                }
        
                public void Push(int y, int yParent, int xLeft, int xRight)
                {
                    if ((y >= yMin) && (y <= yMax))
                    {
                        if ((shadows = shadows.previous) == null)
                        {
                            shadows = new Shadow();
                            shadowsHead.previous = shadows;
                            shadows.next = shadowsHead;
                            shadowsHead = shadows;
                            shadowCount++;
                        }
        
                        shadows.y = y;
                        shadows.yParent = yParent;
                        shadows.xLeft = xLeft;
                        shadows.xRight = xRight;
                    }
                }
        
                public void Pop(out int y, out int yParent,
                                out int xLeft, out int xRight)
                {
                    y = shadows.y;
                    yParent = shadows.yParent;
                    xLeft = shadows.xLeft;
                    xRight = shadows.xRight;
                    shadows = shadows.next;
                }
        
                public bool Empty
                {
                    get { return (shadows.next == null); }
                }
            }
        
            // The delegate must test the pixel and modify it if it fits the match criteria.
            // Return true if the pixel matched (and was therefore modified) and false otherwise.
            public delegate bool TestAndModifyPixel(int x, int y);
        
            // Fill4: If the pixel at (x, y) fits the match criteria, modify it. Then check all its 4-connected
            // neighbors. Modify any than match, and check their 4-connected neighbors, etc. Continue until all the
            // matching connected pixels have been modified.
            // A 4-connected neighbor is a pixel above, below, left, or right of a pixel.
            public void Fill4(int x, int y, TestAndModifyPixel testAndModifyPixel)
            {
                int left, parentLeft, parentRight, parentY;
        
                // Exit if the position is out of range.
                if ((x < xMin) || (y < yMin) ||
                    (x > xMax) || (y > yMax))
                    return;
        
                // Scan the first span as a special case.  The first span is unique,
                // since it has no parent span.
        
                // Scan left starting at the initial pixel.
                left = x;
                while ((left >= xMin) && testAndModifyPixel(left, y))
                    left--;
        
                // If no pixels were modified, just return.
                if (left == x)
                    return;
        
                // Scan right starting at the pixel just right of the initial pixel
                do
                {
                    x++;
                }
                while ((x <= xMax) && testAndModifyPixel(x, y));
        
                // Push the span for the lines above and below.
                stack.Push(y - 1, y, left + 1, x - 1);
                stack.Push(y + 1, y, left + 1, x - 1);
        
                // Scan the remaining spans, adding new 'shadow' spans of pixels to test to
                // adjacent lines as we go. Above and below each span is a 'parent' line that
                // generated the span, and an 'other' line that lies on the opposite side.
                // For each group of set pixels in the current line, we must add a corresponding
                // span in the 'other' line.  Spans for the parent line only need to be added
                // for the regions that extend to the left and right of the parent span, since
                // the parent span has already been tested.  The pixels immediately left and
                // right of the parent span were tested while processing the parent span, so
                // they don't need to be retested.
                //
                // Parent:        aa ppppppppppppppppp aaaa
                // Current:       cccc cccccc  cccc ccccccc
                // Other:         aaaa aaaaaa  aaaa aaaaaaa
                while (!stack.Empty)
                {
                    stack.Pop(out y, out parentY, out parentLeft, out parentRight);
                    int otherY = y + (y - parentY);
        
                    // Scan left, starting at the leftmost pixel of the parent span, for
                    // pixels that need replacing.
                    x = parentLeft;
                    while ((x >= xMin) && testAndModifyPixel(x, y))
                        x--;
        
                    if (x == parentLeft)
                    {
                        // The pixel with the same x as the parent's leftmost pixel
                        // wasn't replaced, so we don't need to check for additional
                        // leftward pixels on the parent line.
                        // Scan rightward for the beginning of the first span,
                        // finishing if we reach the end of the parent span.
                        do
                        {
                            if (++x > parentRight)
                                goto PopNext;
                        }
                        while (!testAndModifyPixel(x, y));
                        left = x++;
                    }
                    else
                    {
                        left = x + 1;    // Save x of leftmost modified pixel.
                        // The pixel with the same x as the parent's leftmost pixel
                        // was replaced.  We know the parent's leftmost pixel was modified
                        // and that the pixel to its left was tested but not modified,
                        // so there's no there's no need to retest them.  Only add a new
                        // parent span if we need to test the pixels at least two pixels
                        // to the left of the parent's leftmost pixel.
                        if (left < parentLeft - 1)
                            stack.Push(parentY, y, left, parentLeft - 2);
                        x = parentLeft + 1;
                    }
        
                    // At this point we've processed the first pixel from a new span.
                    // Process this span and any subsequent spans until we're no longer
                    // inside the parent span.
                    do
                    {
                        // Scan rightward for the end of the current span.  When
                        // the end of the span is reached, push the span for the
                        // non-parent neighboring line.
                        while ((x <= xMax) && testAndModifyPixel(x, y))
                            x++;
                        stack.Push(otherY, y, left, x - 1);
                        // If the span ends after the end of the parent's span,
                        // we may need to test additional pixels on the parent line.
                        // We know the parent's rightmost pixel was modified and that
                        // the pixel to its right was tested but not modified, so there's
                        // no there's no need to retest them.  Only add a new parent span
                        // if we need to test the pixels at least two pixels to the right
                        // of the parent's rightmost pixel.
                        if (x > parentRight + 2)
                            stack.Push(parentY, y, parentRight + 2, x - 1);
        
                        // Scan rightward for the beginning of the next span, finishing
                        // if we reach the end of the parent span before finding a span.
                        // (I could eliminate the goto by testing (x > parentRight)
                        // twice -- once for each while loop)
                        do
                        {
                            if (++x > parentRight)
                                goto PopNext;
                        }
                        while (!testAndModifyPixel(x, y));
                        left = x++;
                    }
                    while (true);
        
                PopNext: ;
                }
            }
        
            public void Fill8(int x, int y, TestAndModifyPixel testAndModifyPixel)
            {
                int left, parentLeft, parentRight, parentY;
        
                // Exit if the position is out of range.
                if ((x < xMin) || (y < yMin) ||
                    (x > xMax) || (y > yMax))
                    return;
        
                stack.Push(y + 1, y, x, x); // needed in some cases
                stack.Push(y, y + 1, x, x); // seed segment (popped 1st)
        
                while (!stack.Empty)
                {
                    stack.Pop(out y, out parentY, out parentLeft, out parentRight);
                    int otherY = y + (y - parentY);
                    // Get the range of pixels that were 8-connected to the
                    // parent span.
                    int spanRight = Math.Min(parentRight + 1, xMax);
        
                    // Scan leftward, starting at the pixel to the left of the
                    // leftmost pixel of the parent span, for pixels that need
                    // replacing.
                    x = parentLeft - 1;
                    while ((x >= xMin) && testAndModifyPixel(x, y))
                        x--;
                    if (x == parentLeft - 1)
                    {
                        // The pixel with the same x as the pixel to the left of the
                        // parent's leftmost pixel wasn't replaced, so we don't need
                        // to check for additional leftward pixels on the parent line.
                        // Scan rightward for the beginning of the next span,
                        // finishing if we reach the end of the parent span.
                        do
                        {
                            if (++x > spanRight)
                                goto PopNext;
                        }
                        while (!testAndModifyPixel(x, y));
                        left = x++;
                    }
                    else
                    {
                        left = x + 1;    // Save x of leftmost modified pixel.
                        // The pixel with the same x as the pixel left of the parent's
                        // leftmost pixel was replaced.  We must check the pixels
                        // they touch on the parent's line.
                        stack.Push(parentY, y, left, parentLeft - 1);
                        x = parentLeft;
                    }
        
                    while (true)
                    {
                        // Scan rightward for the end of the current span.  When
                        // the end of the span is reached, push the span for the
                        // non-parent neighboring line.
                        while ((x <= xMax) && testAndModifyPixel(x, y))
                            x++;
                        stack.Push(otherY, y, left, x - 1);
                        // If the span ends after the end of the parent's span,
                        // push a span from the position after the end of the
                        // parent's span up to the end of this span.
                        if (x > spanRight)
                            stack.Push(parentY, y, spanRight, x - 1);
        
                        // Scan rightward for the beginning of the next span,
                        // finishing if we reach the end of the parent span.
                        do
                        {
                            if (++x > spanRight)
                                goto PopNext;
                        }
                        while (!testAndModifyPixel(x, y));
                        left = x++;
                    }
                PopNext: ;
                }
            }
        }
        
        #endregion

 

Here's the plugin: EdgeShaderMJW.zip

 

It seems to work, and I believe it works, but I'm note absolutely positive.

 

It isn't a true code lab plugin. To build the plugin, open it in CodeLab; do a build, showing the source code; save the source code; add the InitializeRendering call to OnSetRenderInfo; then build as a VS project.

 

The algorithm is:

Inside OnSetRenderInfo --

1) Allocate an integer depth array the size of the canvas.

2) Initialize the array so the depth of exterior points is -1; the depth of interior poits is maxdistance squared..

3) For each edge pixel, stating at the pixel, flood fill all the pixels whose distances are currently greater than their distance from the current edge pixel. Replace the current distance with the (squared) squared to current edge pixel.

 

After this process is complete, for each pixel, the distance buffer contains the distance squared to nearest edge pixel. The colors are computed by the normal render routines.

 

 

 

 

  • Upvote 1
Link to comment
Share on other sites

I tried to make some changes to the previous comment, but the editor doesn't work.  It doesn't show me the current version. Maybe the comment is too long?

 

The edits don't affect it much. Mostly I wanted to remove some commented out code in the source.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...