Dilate algorithm - anyone?

Started by Derron, December 27, 2017, 13:58:29

Previous topic - Next topic

Derron

Hi,

I just want to ask if one of you wrote a "simple" dilate algorithm already? It must not be realtime but should be made in a way so you can easily rewrite it in the language of choice (BlitzMax here).

For what I would use it? I would use it to create "outlines" of images dynamically (which then can get blurred to create "glow" or other effects).


bye
Ron

GW

#1
I once wrote an rts where all the animated soldiers had a black outline. I would set the color to black, draw all the soldiers at +1,-1 x and y, then finally draw them in color, ending up with a 1 pixel black outline.  No real performance hit even for hundreds of sprites in realtime.
If you just want the outline, you could then  iterate the pixels and set every color not outline to alpha 0.


Derron

Quote from: GW on December 27, 2017, 16:56:53
If you just want the outline, you could then  iterate the pixels and set every color not outline to alpha 0.

Aaaand what is the outline? There are "go in all 4 directions"-approaches for outlines but they have some disadvantages - and I doubt that my solution would be the best (thinking about "islands" or holes in the "sprites").


@ +-1 in the directions
Hmm, I use that "simple" approach for "Emboss" and the likes but for "glow" I use a "draw it in _desiredColor_", "blur the texture", "draw normal texture on top"-approach.

I think that might work for what _I_ am planning to do with it. So I would create a "white"-image of the texture (all colors => white, alpha = alpha), then blurring it (have functions for it already). Last step is to subtract every fully opaque image in the original image from the "blurred white" one.
The resulting image is a "soft" outer part of the shape and a "hard" inner part (where the cutout took place) . When rendering that effect-image then it should result in something usable as long as you render the original image on top again (to hide the sharp inner border - if there were alpha'd pixels).

To even avoid that another step seems useful: Copy the effect image, remove "semi transparent" (a < 0.9 or so) pixels. Blur that image slightly and then add that image to the original effect image. This results in an inner border to be "blurred a bit" too and the outer part adding to a already alpha'd/blurred/glowing part (so makes it a bit more opacque - but as it is only a faked glow effect we do not need to make it mathematically correct).


The white effect is useful as I could simply tint it then using "SetColor".


Hmm, yes, this sound like something feasible. Thanks for that little brainstorming moment ;-)


PS: Nonetheless a "Dilate"-function might be helpful and even less cpu hungry. So guys: post it if there is already something in your coding pockets.

bye
Ron

Scaremonger

I have this example code that will draw a border around a PNG image using the alpha (transparency) as a guide. It only checks in 4 directions but you could extend that if you need to.

Un-comment one of the border colours at the top (red, green or blue) before you run it. You'll need a .PNG file with transparency called "example.png" too.

Code: BASIC

SuperStrict
?linux
Import "-ldl"
?

Const FILENAME$ = "example.png"

Const BORDER_COL:Int = $FFFF0000 'Alpha plus #FF0000 (Red)
'Const BORDER_COL:Int = $FF00FF00 'Alpha plus #00FF00 (Green)
'Const BORDER_COL:Int = $FF0000FF 'Alpha plus #0000FF (Blue)

Graphics 800,600
AutoMidHandle( True )

Global bgr%=$ff, bgg%=$ff, bgb%=$ff
Global fgr%=$00, fgg%=$00, fgb%=$00
Global image:TImage[2]
Global mode%=True

image[True] = LoadImage( FILENAME )
image[False] = Border( LoadImage( FILENAME ) )

Repeat
SetClsColor( bgr, bgg, bgb )
Cls

'# Change background
If KeyHit( KEY_1 ) Then
bgr=$ff ; bgg=$ff ; bgb=$ff
fgr=$00 ; fgg=$00 ; fgb=$00
End If
If KeyHit( KEY_2 ) Then
bgr=$00 ; bgg=$00 ; bgb=$00
fgr=$ff ; fgg=$ff ; fgb=$ff
End If

'# Flip draw mode
If KeyHit( KEY_0 ) Then mode=Not mode

'# Draw image
SetColor( $ff, $ff, $ff )
DrawImage( image[mode], GraphicsWidth()/2, GraphicsHeight()/2)

'# Draw overlay text
SetColor( fgr, fgr, fgb )
If mode=True Then
DrawText( "Image", 0,0 )
Else
DrawText( "Border", 0,0 )
End If
DrawText( "0 - Flip border", 0,15 )
DrawText( "1 - White background", 0,30 )
DrawText( "2 - Black background", 0,45 )
DrawText( "ESC - Exit", 0,60 )

Flip

Until KeyHit( KEY_ESCAPE )
End

Function border:TImage( image:TImage )
Local pixmap:TPixmap = LockImage( image, 0 )
'
Local colour:Int, sum:Int
Local argb:Byte Ptr = Varptr colour

Const ALPHA:Int = 3
Const RED:Int = 2
Const GREEN:Int = 1
Const BLUE:Int = 0

For Local x:Int = 0 Until pixmap.width
For Local y:Int = 0 Until pixmap.height
'# Get colour at pixel X,Y
colour = ReadPixel( pixmap, x, y )

'# LOOK FOR TRANSPARANT PIXELS
If argb[ALPHA]=0 Then

'# Get pixels aoundto right and below and sum the ALPHA component
sum=0
If x>0 Then
colour = ReadPixel( pixmap, x-1, y )
'# Only add border if it's not the colour we are adding
If colour<>BORDER_COL Then sum:+ argb[ALPHA]
End If
If x<pixmap.width-1 Then
colour = ReadPixel( pixmap, x+1, y )
sum:+ argb[ALPHA]
End If
If y>0 Then
colour = ReadPixel( pixmap, x, y-1 )
'# Only add border if it's not the colour we are adding
If colour<>BORDER_COL Then sum:+ argb[ALPHA]
End If
If y<pixmap.height-1 Then
colour = ReadPixel( pixmap, x, y+1 )
sum:+ argb[ALPHA]
End If

'# ADD GREEN BORDER
If sum>0 Then WritePixel( pixmap, x, y, BORDER_COL )
End If

Next
Next

UnlockImage(image)
Return image
End Function

Scaremonger


Derron

Thanks for posting - seems you did that 4-in-all-directions approach.

I tried it - and it creates a single pixel wide outline. Nice. Any idea how to increase width of that outline? With "dilate" it should be a matter of the params.
If not, I could use that "single line" to "blur" the outline-only-image with a "line thickness"-value and then multiply the existing alpha values to make them more "visible" (0.2=>0.4, 0.5=>1.0, 1.0=>1.0). This would also solve the issue with "diagonals" not beeing detected (only 4 directions) in all cases. They would get "smoothed out" then.

Think that code snipped would come in handy. Hope you do not mind if I add the "algorithm" (not your code, only the "approach") to my libpng/zlib-licenced code (with a "based on" mention + link).



@ Link
I had that on screen already and did not find it suiting for my brain. Nonetheless thanks for posting that too.


bye
Ron

col

#6
Gaussian blur is generally a good all round blur algorithm.

QuoteAny idea how to increase width of that outline? With "dilate" it should be a matter of the params.
Too much festive drinking Derron? :D

I'm not at my pc at the mo so can not show standard BlitzMax code but you have your outline can use an array of values to iterate through while applying each component of the array to its neighbor pixels depending on its 'distance' to the current pixel. Then like the code posted you sum up the values for the current pixel. The 'magic' of the formula is the values needed for the 'blend'.

For good gaussian blur values I recommend this websites calculator
http://dev.theomader.com/gaussian-kernel-calculator/

I've used the calculator for very good results. It wouldn't be right to share that exact BlitzMax shader code as it is proprietary and paid for by a fellow BlitzMax coder for a realtime effect.

Say you want a pixel to be blurred using a 5x5 'kernel', which means you can easily include the 3 neighbours to the left, up, down, right etc in factors for the final centre pixel value. You can easily optimise to use a 1x3 kernel to create a 5x5 blur using 2 pass blurring. That website gives good values for blurring or you could look up the algo for a gaussian blur factors.
https://github.com/davecamp

"When you observe the world through social media, you lose your faith in it."

Derron

#7
Ah lol ...you are right.

When I only have the outline "doubling" or adding to neighbours is no trouble - as soon as you do a 1,3,5... increase (means on both sides of the "source pixel").

I was under the assumption of the outline + some other stuff being on the same image so that you cannot just rely on the opacque pixels.


Still a dilate-function might be useful somewhen.




@ blur
As said I have blur-functionality already.
https://github.com/GWRon/Dig/blob/master/base.gfx.imagehelper.bmx
"blurpixmap"


bye
Ron

GaborD

You could do it with a simple shader too.

Here is a small demo in AGK. Just renders the main cam into a render texture and draws a border at object edges.
It's just quickly hacked together, but I tried to comment everything.
For now it just draws the result on a quad in the scene, usually you would render it into another rendertex for later usage I guess. But that's basically the same thing, just a different target.



This is pretty fast, if I disable refresh limiting it runs at 4000FPS on my rig with thin outlines, still 1000FPS with 10 pixel thick borders. Above 4 or so it would probably be faster to run passes instead of a wide search in one pass.

The shader is pretty simple (and could be optimized a lot :) ) :
Code: BASIC


#ifdef GL_ES
   #ifdef GL_FRAGMENT_PRECISION_HIGH   
      precision highp float;
   #else
      precision mediump float;
   #endif
#endif

uniform sampler2D texture0;

varying vec2 uv0Varying;
varying vec2 uv1Varying;
varying vec3 normalVarying;

uniform float tsize;
uniform float mode;
uniform float thick;

void main() {
    // calculate the uv offset for a single texture pixel
float sizer = 1.0/tsize;

// fetch middle pixel, to see if we need to search for nearby objects
vec3 col = texture2D(texture0, uv0Varying).rgb;

// initialize some variables we will need
float i = 0.0;
float j = 0.0;
float flg = 0.0;

// check if we are inside objects
if (col == vec3(1,0,1)) {
// if yes, set an inner color (set this to the background color if you just want the outline)
col = vec3(0.43,0.33,0.23);
} else {
// OK, not inside objects, let's check for nearby ones
for (i=-thick; i<thick+1.0; i++) {
for (j=-thick; j<thick+1.0; j++) {
if (texture2D(texture0, uv0Varying+vec2(i*sizer,j*sizer)).rgb == vec3(1,0,1)) {
// found one, set border color
col.rgb = vec3(1.0, 1.0, 1.0);
flg = 1.0;
} else {
// none found, if the pixel is still unset, set a background color
// You could delete this if you just want the original background color from the rendertexture
if(flg==0.0) { col = vec3(0.2, 0.2, 0.2); }
}
}
}
}

// if we are rendering to the rendertexture, set it to inside object
if (mode==1.0) { col= vec3(1.0, 0, 1.0); }

// color output
    gl_FragColor = vec4( col, 1 );
}

col

@GaborD
I recommend to try a 2 pass approach, or at least profile it.
It usually sounds counter intuitive to render twice but I'd definitely give it a go.
Render the horizontal pass out to an image and then do the same to that new image but for vertical. I'd be surprised if you don't get a speed up of some kind.
https://github.com/davecamp

"When you observe the world through social media, you lose your faith in it."

Derron

As default Max2D does not have a crossplatform/renderpath-shader-option I am bound to "cpu only"-algorithms - makes it commandline-friendly too.


Anywise: good to see people jumping in here.


bye
Ron

GaborD

Ah that's too bad, Derron. Ah well, was worth a shot.

In any case, if anyone else is goofing with this, it's usually enough to fan out in the general and diagonal directions to speed things up considerably.
There can be small visual differences with thick borders, but in most cases it's good enough.

This runs at 3000+ FPS even with 10pixel thick borders (so basically a 3x increase over a full search at this border thickness) and still 2000+ with 20 pixel thick borders (which would be really slow with the old version)



Code: BASIC

#ifdef GL_ES
   #ifdef GL_FRAGMENT_PRECISION_HIGH   
      precision highp float;
   #else
      precision mediump float;
   #endif
#endif

uniform sampler2D texture0;

varying vec2 uv0Varying;
varying vec2 uv1Varying;
varying vec3 normalVarying;

uniform float tsize;
uniform float mode;
uniform float thick;
uniform float mode2;

void main() {
    // calculate the uv offset for a single texture pixel
float sizer = 1.0/tsize;

// fetch middle pixel, to see if we need to search for nearby objects
vec3 col = texture2D(texture0, uv0Varying).rgb;

// initialize some variables we will need
float i = 0.0;
float j = 0.0;
float flg = 0.0;

// check if we are inside objects
if (col == vec3(1,0,1)) {
// if yes, set an inner color (set this to the background color if you just want the outline)
col = vec3(0.43,0.33,0.23);
} else {
// OK, not inside objects, let's check for nearby ones
for (i=-thick; i<thick+1.0; i++) {
if (texture2D(texture0, uv0Varying+vec2(i*sizer,0)).rgb == vec3(1,0,1)
|| texture2D(texture0, uv0Varying+vec2(0,i*sizer)).rgb == vec3(1,0,1)
|| texture2D(texture0, uv0Varying+vec2(i*sizer,i*sizer)).rgb == vec3(1,0,1)
|| texture2D(texture0, uv0Varying+vec2(-i*sizer,i*sizer)).rgb == vec3(1,0,1)) {
// found one, set border color
col.rgb = vec3(1.0, 1.0, 1.0);
flg = 1.0;
} else {
// none found, if the pixel is still unset, set a background color
// You could delete this if you just want the original background color from the rendertexture
if(flg==0.0) { col = vec3(0.2, 0.2, 0.2); }
}
}
}

// if we are rendering to the rendertexture, set it to inside object
if (mode==1.0) { col= vec3(1.0, 0, 1.0); }

// color output
    gl_FragColor = vec4( col, 1 );
}


Or multipass, but I am too lazy. :)

Derron

Why does Suzanne (that blender monkey) cast this white little dot at the position of the "right eye socket" (on the outline texture) ?


bye
Ron

Derron

#13
Meanwhile this is my BlitzMax code for "outlines" now (libpng/zlib licenced - will add it to my DIG-framework pretty soon):

Code: blitzmax

'padding variable is there to avoid creating a target image over and over
'if you plan to add a "blur" afterwards (which needs some additional
'pixels on all sides)
Function ConvertToOutLine:TImage(image:TImage, lineThickness:int=1, alphaTreshold:Float = 0.0, outlineColor:int=-1, targetPadding:int=0)
   if outlineColor = -1 then outlineColor = -1 '(Int(255 * $1000000) + Int(255 * $10000) + Int(255 * $100) + Int(255))
   lineThickness = lineThickness / 2

   'convert 0.0-1.0 to 0-255
   alphaTreshold :* 255

   'load source
   Local srcPix:TPixmap = LockImage(image)
   if not srcPix then return Null
   'if it is the wrong format to use, create a temporary copy
   If srcPix.format <> PF_RGBA8888
      srcPix = srcPix.Copy().Convert(PF_RGBA8888)
   EndIf

   'create target
   Local targetPix:TPixmap = CreatePixmap(srcPix.width + targetPadding*2, srcPix.height + targetPadding*2, srcPix.format)
   targetPix.ClearPixels(0)

   'storage for alpha of a pixel's surrounding pixels
   Local sum:int

   For Local x:Int = 0 Until srcPix.width
      For Local y:Int = 0 Until srcPix.height
         'ignore if above treshold
         'except for borders
'         If ARGB_Alpha(col) > alphaTreshold Then continue
         if (x <> 0 and x <> srcPix.width-1) and (y <> 0 and y <> srcPix.height-1)
            If ((ReadPixel(srcPix, x, y) Shr 24) & $ff) > alphaTreshold
               continue
            endif
         EndIf


         'check pixels left/right/top/bottom of current pixel
         'add all of their alphas to "sum" so we could check
         'whether there is something needing a outline
         sum = 0
'         If x > 0               Then sum :+ ARGB_Alpha( ReadPixel(srcPix, x-1, y) )
'         If x < srcPix.width-1  Then sum :+ ARGB_Alpha( ReadPixel(srcPix, x+1, y) )
'         If y > 0               Then sum :+ ARGB_Alpha( ReadPixel(srcPix, x, y-1) )
'         If y < srcPix.height-1 Then sum :+ ARGB_Alpha( ReadPixel(srcPix, x, y+1) )
         If x > 0               Then sum :+ ((ReadPixel(srcPix, x-1, y) Shr 24) & $ff) > alphaTreshold
         If x < srcPix.width-1  Then sum :+ ((ReadPixel(srcPix, x+1, y) Shr 24) & $ff) > alphaTreshold
         If y > 0               Then sum :+ ((ReadPixel(srcPix, x, y-1) Shr 24) & $ff) > alphaTreshold
         If y < srcPix.height-1 Then sum :+ ((ReadPixel(srcPix, x, y+1) Shr 24) & $ff) > alphaTreshold
           
         If sum > 0
            If lineThickness = 0
               WritePixel(targetPix, x + targetPadding, y + targetPadding, outlineColor )
            Else
               For local i:int = 0 to lineThickness
                  If x + targetPadding - i >= 0               Then WritePixel(targetPix, x + targetPadding - i , y + targetPadding, outlineColor )
                  If x + targetPadding + i < targetPix.width  Then WritePixel(targetPix, x + targetPadding + i , y + targetPadding, outlineColor )
                  If y + targetPadding - i >= 0               Then WritePixel(targetPix, x + targetPadding, y + targetPadding - i, outlineColor )
                  If y + targetPadding + i < targetPix.height Then WritePixel(targetPix, x + targetPadding, y + targetPadding + i, outlineColor )
               Next
            EndIf
         EndIf
      Next
   Next

   return LoadImage(targetPix)
End Function


linewidths needs to be odd numbers (1,3,5,...) so I can add them on both sides without trouble, else I think one need to either ignore "bottom and right" or "top and left" - else one needs to use "modulo" to check if a "line growth" is even or not (to ignore or not the "bottom and right"). For me 1,3,5,... as widths is ok so I prefer to save on CPU cycles.

alphaTreshold allows to ignore "semi transparency" pixels - eg a slight existing shadow pre-created on a sprite.

I also added a condition to always handle the borders of a given image - else a sprite is not correctly outlined if it occupies pixels on the borders. In other words: scaremonger's code failed for some sprites here ;-).

Together with my "blur"-function it looks pretty neat.


Image contains a bit of semi-transparency - but is not for what I want to use it. I want to be able to highlight selections (on a map) based on sprites which users could add dynamically to the game - so I cannot "pre-create" the highlights.

This should allow for some cool effects. Thanks guys. Pretty impressive collaboration / brainstorming / copy-pasting-of-scaremongers-stuff :-p

If someone comes up with real "dilate"-stuff (for easy growing of an existing image data/selection), do not hesitate to post it here.


Edit at 01:24 - Glow from auto-outline in action:



bye
Ron

Scaremonger

Pleased you found my code useful and I like the map edge glow, that's pretty impressive.