GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2010-10-08 14:38:14

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Dithering for Game Design

NOTE: This tutorial is a work in progress. The script provided, while functional, is unoptimized for clarity.

What is dithering?

Dithering, or digital halftoning, is a process for reducing a high dynamic range signal into a quantized, low dynamic range signal. Through the use of alternating patterns, signals that otherwise can't be reproduced can be simulated or approximated. The figure below shows a continuous tone grayscale image and three different ways it can be dithered for a bilevel display. Although dithering is most often seen in image reproduction, it has applications in audio and other areas.
4mdBK8y.gif

The Floyd-Steinberg algorithm is an example of an "error diffusion" image filter and is one of the fastest and simplest to implement. Error diffusion means measuring the total amount of error that is produced when recoloring a pixel, selecting the available color that minimizes the error, and then transfering the error to neighboring pixels for future consideration. In this way all error produced through dithering can be gradually dealt with as it is spread to and accumulates in other pixels, minimizing the total level of error for any particular group of pixels.

On the right side of the image below you can see the Floyd-Steinberg algorithm at work on Lenna, reducing the grayscale image to only black or white pixels. On the left you can see how it was actually used.
6xSjSLM.jpg


How can dithering be used in games?

The problem I was faced with was finding an optimal way to distribute jigsaw puzzle pieces onto the available play area. There were several considerations: the pieces should not obscure the solving area in the center; the pieces should be arranged at random but in a pleasing naturalistic way; the pieces should overlap as little as possible; and the entire operation must be fast.

I tried several approaches. I started with a simple random number modulated by this gain function, forcing the piece placement to be biased towards the edges of the play area. This worked very well but the pieces largely overlapped. I tried a few simple collision based methods for fixing overlapping pieces, and they worked decently on some puzzles, but all were far too slow for puzzles that exceeded only a hundred pieces.

Once again inspiration hit while I was in bed about to fall asleeep. I was imagining how I wanted the random piece arrangements to look when it occured to me that it looked a bit like a dithered image, specifically one using error diffusion. I reasoned that all that needed to be done is create an image that had the right shades in the right places and the dithering process would take care of the rest. I knew I had already implemented a version of the Floyd-Steinberg algorithm in GFA Basic more than 15 years ago, I just had to find it. Incredibly, I did and a few minutes later the problem was solved.

The algorithm is extremely fast for puzzles of any practical size. The dispersed pieces rarely overlap and where they do it is minor or intentional. By varying the shades used, one can easily force pieces to cluster near certain areas or avoid them. A characteristic of the Floyd-Steinberg algorithm is that at the input intensities used, pixels often align along diagonals. This ensures that the visually important piece edges remain relatively unobscurred.

Similar techniques should be applicable to many games that require naturalistic object distribution with a high degree of control. The ds_grid_fsdither function (below) extends the Floyd-Steinberg algorithm to follow a "serpentine" path and output any number of shades. Multiple shades might be useful for scenes constructed of transitioning tiles (eg. sandy beach to grass to hills to forest). The algorithm has been further extended to inject noise into the error calculation. This can help break up the regular patterns that can manifest at certain critical input intensities. There are several other attractive error diffusion filters that should be experimented with. They all work similarly and have their own unique characteristics. The simplicity and fine granularity of the Floyd-Steinberg algorithm fit my needs well.

//  ds_grid_fsdither(id,source [,levels [,noise]])
//      Outputs a Floyd-Steinberg dither of the given data.
//      Source grid data expected to conform to [0..1] interval.
//      Destination grid populated with integers in [0..levels-1] interval. 
//          id          destination ds_grid 
//          source      source ds_grid
//          levels      levels in the output, integer (minimum 2, default 2)
//          noise       amount of error noise, real ([0..1], default 0)
//      Returns 0.
{
    var w,h,halfnoise;
    w = ds_grid_width(argument0);
    h = ds_grid_height(argument0);
    if (argument2 == 0) argument2 = 1;
    else argument2 -= 1;
    halfnoise = argument3/2;
    
    //  Initialize
    var ac0,ac1,i,j,s,tmp,intens,e1,e2,error;
    ac0 = ds_grid_create(w,1);
    ac1 = ds_grid_create(w,1);
    i = 0;
    j = 0;
    s = 1;
    
    repeat (h)
    {
        //  Swap the accumulation buffers
        tmp = ac0;
        ac0 = ac1;
        ac1 = tmp;
        //  Clear the lower buffer
        ds_grid_clear(ac1,0);
        repeat (w)
        {
            intens = ds_grid_get(argument1,i,j)*argument2;
            //  Compute the dither error
            e2 = frac(intens)+ds_grid_get(ac0,i,0)+random(argument3)-halfnoise;
            e1 = e2-1;
            //  Minimize the error and apply the dither
            if (abs(e1) < abs(e2))
            {
                error = e1/16;
                ds_grid_set(argument0,i,j,floor(intens)+1);
            }
            else
            {
                error = e2/16;
                ds_grid_set(argument0,i,j,floor(intens));
            }	
            //  Diffuse the error with          // current  +------+------+
            //  F-S Error Diffusion Kernel      //  pixel --> XXXX | 7/16 | ac0[]
            ds_grid_add(ac0,i+s,0,7*error);     //   +------+------+------+ 
            ds_grid_add(ac1,i-s,0,3*error);     //   | 3/16 | 5/16 | 1/16 | ac1[]
            ds_grid_add(ac1,i  ,0,5*error);     //   +------+------+------+
            ds_grid_add(ac1,i+s,0,  error);     //     i-1     i     i+1
            
            //  Advance to next column
            i += s;
        }
        //  Reverse direction and advance to the next row
        s *= -1;
        i += s;
        j += 1;
    }
    //  Clean up
    ds_grid_destroy(ac0);
    ds_grid_destroy(ac1);
    return 0;
}

Jigsaw Puzzle Piece Dispersion Details

xDsdYBZ.gifAt the top of the image to the right is a magnified view of the puzzle template image. Each pixel of the image represents a space that a piece could fit into. The entire play area is exactly twice as wide and tall as the assembled puzzle. If the puzzle is 10 x 8 pieces in size, the image of the entire play area is 20 x 16 pixels in size.

An assembled puzzle takes up exactly 1/4 of the entire play area. When the puzzle is disassembled the pieces must only occupy the other 3/4 of the play area. An area of 1/4 size is being divided into an area of 3/4 size; the outer play area requires a 1/3 piece density to hold all of the pieces. Dither a grayscale image of 1/3 intensity to get an image where 2/3 of the pixels are black and 1/3 are white. Where the grayscale input image (top) is colored black, white pixels will be completely absent from the dithered output image (bottom).

Everywhere a white pixel is drawn, that position is placed in a priority queue with random priority. Once the dithering is complete, each piece is displaced to a new position removed from the priority queue. Very small images require the intensity to be increased slightly to ensure that enough candidate spaces are produced for the number of pieces in the puzzle.


Various Error Diffusion Kernels

Floyd-Steinberg
[tex]\begin{array}{|c|c|c|} \hline & X \to & 7/16  \\ \hline 3/16 & 5/16 & 1/16  \\ \hline \end{array}[/tex]
This is the original digital error diffusion filter, presented at SIGGRAPH 75. It is by far the most commonly used diffusion filter in existence. Although originally created in an ad hoc manner, it is highly successful in terms of quality and simplicity. One of its interesting features, proven by later researchers, is its built-in edge enhancement properties. A distinctive feature of this dither is that it produces a perfect checkerboard pattern at 50% intensity. This was a conscious design choice, although other researchers have worked hard to eliminate such patterns from their filters.

Jarvis-Judice-Ninke
[tex]\begin{array}{|c|c|c|c|c|} \hline & & X \to & 7/48 & 5/48  \\ \hline 3/48 & 5/48 & 7/48 & 5/48 & 3/48 \\ \hline 1/48 & 3/48 & 5/48 & 3/48 & 1/48 \\ \hline \end{array}[/tex]
Developed independently at around the same time as the Floyd-Steinberg dither. Lower resolution due to the larger kernel. Features strong ringing related to edge enhancement.

Stucki
[tex]\begin{array}{|c|c|c|c|c|} \hline & & X \to & 8/42 & 4/42  \\ \hline 2/42 & 4/42 & 8/42 & 4/42 & 2/42  \\ \hline 1/42 & 2/42 & 4/42 & 2/42 & 1/42 \\ \hline \end{array}[/tex]
Published in 1981 by an IBM Research Lab in Switzerland. Finer grained modification of Jarvis-Judice-Ninke with error distribution more locally concentrated.

Burkes
[tex]\begin{array}{|c|c|c|c|c|} \hline & & X \to & 8/32 & 4/32  \\ \hline 2/32 & 4/32 & 8/32 & 4/32 & 2/32  \\ \hline \end{array}[/tex]
A simplified version of Stucki created in 1988 for speed but featuring strongly orthogonal artifacts. Like other variants of existing filters, speed-ups mainly hinge on converting the division operations to bit-shift operations (ie. division by a power of two).

Sierra
[tex]\begin{array}{|c|c|c|c|c|} \hline & & X \to & 5/32 & 3/32  \\ \hline 2/32 & 4/32 & 5/32 & 4/32 & 2/32  \\ \hline & 2/32 & 3/32 & 2/32 & \\ \hline \end{array}[/tex]
A slightly simplified version of Jarvis-Judice-Ninke created in 1989 and yielding very similar results.

Sierra Two-Row
[tex]\begin{array}{|c|c|c|c|c|} \hline & & X \to & 4/16 & 3/16  \\ \hline 1/16 & 2/16 & 3/16 & 2/16 & 1/16  \\ \hline \end{array}[/tex]
A variant of the original created a year later.

Sierra Filter Lite
[tex]\begin{array}{|c|c|c|} \hline & X \to & 2/4  \\ \hline 1/4 & 1/4 & \\ \hline \end{array}[/tex]
Extremely simple filter created by Frankie Sierra and comparable to Floyd-Steinberg in quality.

Stevenson-Arce
[tex]\begin{array}{|c|c|c|c|c|c|c|} \hline & & & X \to & & 32/200 & \\ \hline 12/200 & & 26/200 & & 30/200 & & 16/200 \\ \hline & 12/200 & & 26/200 & & 12/200 & \\ \hline 5/200 & & 12/200 & & 12/200 & & 5/200 \\ \hline \end{array}[/tex]
Published in 1985 and originally created for hexagonal lattices. It can produce pleasing results for rectangular lattices as well.

Shiau-Fan (US patent 5,353,127)
[tex]\begin{array}{|c|c|c|c|c|} \hline & & & X \to & 8/16 \\ \hline 1/16 & 1/16 & 2/16 & 4/16 & \\ \hline \end{array}[/tex]
One of the few patented digital halftoning algorithms. The patent is due to expire October, 2011.

Atkinson
[tex]\begin{array}{|c|c|c|c|} \hline & X \to & 1/8 & \\ \hline 1/8 & 1/8 & 1/8 & 1/8  \\ \hline & 1/8 & & \\ \hline \end{array}[/tex]
Former Apple developer Bill Atkinson designed this dither for the bi-level display of the original Macintosh computer. It is responsible for the distinctive dithering featured in the Mac software and support materials of the time. This high-contrast filter is unusual in that it only distributes 3/4 of the total error and has very strong edge enhancement properties.

Ostromoukhov
[tex]\begin{array}{|c|c|c|} \hline & X \to & d_{10} \\ \hline d_{-11} & d_{01} & \\ \hline \end{array}[/tex]
Victor Ostromoukhov developed this very interesting variable error diffusion dither. It uses varying coefficients dependent on the input level. They were originally selected through an exhaustive heuristic search for "blue noise" fitness, in an effort to reduce unwanted patterns in the dither while providing ideal sampling. The tiny size of the kernel makes it extremely fast and memory efficient. The 384 entry table of coefficients is unfortunately too large to include with this tutorial, but the paper they are presented in can be found here [PDF].


Sources:
Bit-Mapped Graphics, by Steve Rimmer, copyright © 1990, Windcrest Books / TAB Books
    Ulichney, R. "Digital Halftoning", MIT Press, 1987
    Burkes, D.F. "Presentation of the Burkes Error Filter", P.D.
    Floyd, R.W. and Steinberg, L. "An Adaptive Algorithm for Spatial Gray Scale", SID International Symposium Digest of Technical Papers, vol. 1975m
    Stucki, P. "MECCA - A Multiple-Error Correcting Computation Algorithm for Bilevel Image Hard Copy Reproductions", Research Report RZ1060, IBM Research Laboratory, Zurich, Switzerland
Ostromoukhov, V. "A Simple and Efficient Error-Diffusion Algorithm", ACM SIGGRAPH 2001
    Shiau, J. and Fan, Z. "Method for quantization gray level pixel data with extended distribution set", 1994. US patent 5,353,127.
    Shiau, J. and Fan, Z. "A set of easily implementable coefficients in error diffusion with reduced worm artifacts", SPIE, 2658:222–225, 1996.
Crocker, L. et al "Digital Halftoning", 1991
Kock, V. "Dither" (Photoshop plugin), 2007
Stevenson, R. and Arce, G. "Binary display of hexagonally sampled continuous-tone images", Optical Society of America, 1985


Abusing forum power since 1986.

Offline

#2 2010-10-08 17:11:01

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Dithering for Game Design

I plan to follow this up with some demonstrations and some very highly optimized dithering code. It runs much faster, especially for larger kernels.

In my research I discovered that this common implementation of the error diffusion algorithm is flawed. Here we see random noise being injected into the error measurement. That just gives us a bad measurement. Noise should be injected into the signal instead so that the error is always measured correctly. Solves a few problems and allows the algorithm to be reimplemented with very fast parallelized ds_grid based math.

Stay tuned.


Abusing forum power since 1986.

Offline

#3 2010-10-08 18:45:29

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: Dithering for Game Design

Could this also be used to place objects in the room where none touch? I've seen this asked many times, usually solved (half assely) using code loke this
create object
while (object touches any) position =  random room size

Offline

#4 2010-10-08 19:44:54

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Dithering for Game Design

Yes, that's exactly the sort of thing this is perfect for. As long as you aren't trying to stuff too many things in one area, it should work really well.

If you know how many objects you want to place, and the dimensions of the area they are to go in, it is easy to calculate the object density. With the density known, a template image can be constructed using a shade that corresponds to the required density. A pass through a dither function will distribute the objects evenly. Depending on the situation, I might apply some jitter to the placement so it's not obviously grid-like. If the jitter isn't too extreme, collisions shouldn't be an issue. If they are, they will be rare and can be quickly dealt with.

The dither functions don't tend to operate well at the extremes (intensities below 5%?). If you only wanted a few objects in a large area, it may pay to use a lower resolution template to raise the relative object density to levels the filters do work well with. The obvious limit to that is that you must have at least as many available pixels as objects you wish to place.

Where this technique really begins to shine is the ability to control the density at the local level. If you were creating a forest, you might want it to conform to a specific shape. It's simply a matter of painting that shape in a paint program. If you want the forest to taper in density at the edges, alter the shading there, or apply a blur filter. If you want a densely populated area, simply paint that area with lighter shades. The dither function takes care of the distribution automatically.


Abusing forum power since 1986.

Offline

#5 2010-10-08 20:14:22

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: Dithering for Game Design

Oh man, I'm getting goosebumps... Thanks for another out of the box idea xot.

Offline

#6 2010-10-10 00:27:47

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: Dithering for Game Design

So here is my updated forest!!!

Download dither_forest.zip

Without using noise, the result is contant, and that is a good thing because, for use for map generation, you dont want to have ramdomness if you want the map to be static like for a level map...

In my example, the only thing that changes are the type of trees... the position remains constant.

It was tough to set up right because I really had to blacken everything.

I think the method can also be used for unsmoothing a 3d terrain...

Last edited by icuurd12b42 (2010-10-10 00:28:39)

Offline

#7 2010-10-10 16:49:16

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Dithering for Game Design

Hey, that's pretty neat! I'm glad you liked this idea enough try it out.

If you wanted noise, you could always use randomization seeds to ensure that the map is generated the same way every time. That's what I did when testing my optimized versions of these dithers to ensure they produced the same output as the reference versions.

You can make painting the images easier by scaling the the data in the grid after you load it. That only takes one function call. Manually tweak the scaling to produce the number of trees you want, or use the grid min, max, sum, and multiply functions to automatically and analytically normalize, weight, and adjust the grid data to create the desired number of trees/objects.

For instance:

//  ds_grid_normalize(id)
//      Remaps numerical grid data to [0..1] interval
//      Returns -1 on error (zero dynamic range), 0 otherwise.
{
    var i,j,m,n,d;
    i = ds_grid_width(argument0) - 1;
    j = ds_grid_height(argument0) - 1;
    m = ds_grid_get_min(argument0, 0, 0, i, j);
    n = ds_grid_get_max(argument0, 0, 0, i, j);
    d = n - m;
    if (d == 0)
    {
        return -1;
    }
    else
    {
        ds_grid_add_region(argument0, 0, 0, i, j, -m);
        ds_grid_multiply_region(argument0, 0, 0, i, j, 1/d);
        return 0;
    }
}

Not sure what you mean by unsmoothing a 3D terrain, but if you mean split it into discrete levels that are dithered together, the yes, that's exactly what the levels argument could provide.

Multi-Level FS Dither
LpH0vu4.png

You might get nicer results with a more advanced kernel. Floyd-Steinberg produces some pretty strong banding, although they all do to some extent.


Abusing forum power since 1986.

Offline

#8 2010-10-10 22:56:03

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: Dithering for Game Design

In the case of my trees, since they are soo big, changing the room size to accomodate the distribution helps... Or decrease the color intesity like I did. The result is less pixels, less trees.

Alternatively, you can pass .1 and comment out the
else argument2-=1 in your script....

This allows a wider range for dithering (more range in the less pixel department) so to be able to use full black to full white images. like the one you show above while reducing the number of pixels/objects on the screen. Not sure what the factor would be... but it would be the size of the tree compared to the size of the room to the size of the image... ranging from >0<=1 (less trees for small room) to >1 (more trees for large room) where the shape of the map would be held, visually, at any size.


As for unsmoothing.... Again your image above shows what I meant, the one on the right. Think minecraft for example. It's easy the draw a terrain height (on the left) that has obvious elevation. But not that obvious to generate a blocky terrain, even if you use the spray brush in paint.


Also, in the image on the right, (not sure how you did it 'cause i'm getting just black and white pixels) black could be grass, lighter, shrubs, all the way to full grown trees in white

Last edited by icuurd12b42 (2010-10-10 23:01:37)

Offline

#9 2010-10-11 05:08:33

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Dithering for Game Design

Also, in the image on the right, (not sure how you did it 'cause i'm getting just black and white pixels) black could be grass, lighter, shrubs, all the way to full grown trees in white

Yeah, that's exactly what I had in mind. I'm not sure what problem you might be having. Perhaps it is a misunderstanding about the output? For the above example, given an input grid with values between 0 and 1, the output should be a grid populated with the values {0,1,2,3} when given a value of 4 for the levels argument. I can see how that difference in ranges might be counter-intuitive.

That image was produced with an error diffusion "explorer" that I'll be releasing here very soon. I haven't worked on this stuff for six months, but it appears it is using the same script that is in the initial post.

VeJHxSE.png


Abusing forum power since 1986.

Offline

#10 2010-10-11 20:21:18

Marchal_Mig12
Member
Registered: 2009-05-21
Posts: 72

Re: Dithering for Game Design

Could it be used as a tool to create randomly generated levels?

Offline

#11 2010-10-11 21:12:55

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Dithering for Game Design

It could certainly supplement such a tool, as a way to populate areas with objects in an efficient, highly directed, naturalistic way.

Under the right conditions, error diffusion can produce maze like structures.

It can also be used to create interesting geometric patterns and circuit board like imagery.

There is a lot of space yet to explore with it. As far as I can tell, these kinds of algorithms have only been used for digital halftoning. I've not seen them applied like this or in any other way. Nor have I seen them employed to produce large scale or highly structured output. All of the research seems to be directed at the opposite, with fine grained blue noise being the goal.

Mlfb6WA.png
zwIXLM8.png
owGBtrc.png


Abusing forum power since 1986.

Offline

#12 2010-10-12 00:26:36

icuurd12b42
Member
Registered: 2008-12-11
Posts: 303

Re: Dithering for Game Design

OK, got it!
ds filled: in a loop

        b=file_bin_read_byte(file);
        g=file_bin_read_byte(file);
        r=file_bin_read_byte(file);
        if(bitsPerPixel == 32)
            forth = file_bin_read_byte(file);
         
        //ds_grid_set(argument0,xx,yy,make_color_rgb(r,g,b))
        ds_grid_set(argument0,xx,yy,(r+g+b)/3/255)

____________
ds_grid_fsdither(dds,ds,4)

xx =0;
yy = 0;
repeat(ds_grid_height(dds))
{
repeat(ds_grid_width(dds))
{
    v = ds_grid_get(dds,xx,yy) * 255/4;
    draw_point_color(xx+128+256,yy,make_color_rgb(v,v,v))
    xx+=1;
}
yy+=1;
xx = 0;
}

and yes, normalizing seems to improve the end result, in the final image that is though it may not be what people need. it may change shrubs into trees.

As for as applying dither in this way, I'm glad I've come to know you, this is a VERY interesting thought process. I'd be glad to toy with it and supplement your ideas.

I added a topic in expanding game maker/scripts->readBMPFile which is a great help for people who want to make levels in paint.
http://gmc.yoyogames.com/index.php?showtopic=488086

Last edited by icuurd12b42 (2010-10-12 00:28:13)

Offline

#13 2011-09-07 05:09:47

LigH
Member
Registered: 2011-09-07
Posts: 4

Re: Dithering for Game Design

Quite an interesting article, xot & all. Thank you for collecting so many matrices to compare.

I did not yet use GML, but was able to implement matrix based Image dithering with palette matching in PHP using GD2 functions, specifically to match true-color textures to e.g. the DOOM PLAYPAL (via imagecolorat, imagecolorclosest, imagecolorsforindex etc.), with reducable error distribution factor to avoid high-contrast stray pixels.

I believe that a YUV or HSL/HSV (instead of euklidean RGB space distance) based calculation of the closest available palette index color might improve the results further.


Video? doom9 | Gleitz – what else?

Offline

#14 2011-09-07 15:54:10

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Dithering for Game Design

I'm pleased you found the article helpful. If you learn anything from color matching within different color spaces, I've very much like to read about your findings.

I noticed two kernels in your menu I'm not familiar with: Floyd-Steinberg-Fan and a second Shiau-Fan. What can you tell me about those?


Abusing forum power since 1986.

Offline

#15 2011-09-26 01:02:47

LigH
Member
Registered: 2011-09-07
Posts: 4

Re: Dithering for Game Design

Sorry for the delay - looks like I waited for a never sent reply notification... (and I can't upload an avatar either; maybe due to the post count?)

I included some variants from the documentation of libcaca; and also I successfully adapted some matrices on my own with interesting results (playing in another script - subject to changing unexpectedly).


Video? doom9 | Gleitz – what else?

Offline

#16 2011-09-26 07:18:49

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Dithering for Game Design

Thanks for the reply and link to your work. Very interesting read. Your sub-block dither method seems to work well and can produce some very visually pleasing results. I'll certainly study it some more in the future. Although your script worked for me a few times, I did run into some problems using it (500 Internal Server Error).

I like your selection of license. smile

I'll look into the problem with avatar uploads and subscriptions. I actually didn't realize either of the options were enabled and they may be disabled in the future. The forum does have an RSS feed which can be monitored for topic changes.

EDIT:

Avatar uploads should be fixed now. Subscriptions have been disabled for bandwidth limitation reasons. Thank you for reporting the problems.

Last edited by xot (2011-09-26 07:47:21)


Abusing forum power since 1986.

Offline

#17 2011-09-27 12:39:44

LigH
Member
Registered: 2011-09-07
Posts: 4

Re: Dithering for Game Design

Yes, the error 500 is related to limitations of the server I'm using, and some strange behaviour of PHP -- taking incredible amounts of RAM, more than really necessary, way beyond 3x the size of the true-color image it shall process. I have no idea if I made a mistake in my PHP algorithm, if I could avoid it by including specific "tidy up!" commands...

License? Uhm ... it is a study, a "proof of concept", not an application for daily use. As the patent for Shiau-Fan is expected to run out quite soon, I wonder if I may even make the source public, but as mentioned, something is weird regarding memory consumption. Well ... after Ostromoukhov was implemented, maybe. Or it may disappear. Who knows.
__

P.S.: I tried to discuss it in DoomWorld's image thread, after offering a few "sky cylinders" created from higher resolution panorama images using some "noise dither" to apply the DOOM PLAYPAL; but no replies so far.

Last edited by LigH (2011-09-27 12:48:44)


Video? doom9 | Gleitz – what else?

Offline

#18 2011-10-07 04:16:18

LigH
Member
Registered: 2011-09-07
Posts: 4

Re: Dithering for Game Design

A general question to a detail I'm missing in all the descriptions of dithering algorithms:

Shall the error values be able to accumulate to values even less than 0 or greater than 255?

If yes, then the error buffer can't be an image itself which is limited to 1-byte values per component... that is probably my mistake and explains the different appearance with stripes.


Video? doom9 | Gleitz – what else?

Offline

#19 2013-01-18 07:31:08

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Dithering for Game Design

Shoot. This is a really old question I only just noticed it due to a spammer replying here.

You probably won't see this but it deserves an answer. I don't believe it should be possible for the error to accumulate beyond the limits of the source's natural range. I'm unable to imagine a situation where that would ever be possible. It seems like it could only happen if the error was "minimized" incorrectly.

Truthfully, it's not something I've ever given any thought to, nor have I tried treating the accumulation buffer as an image. It's late and I may not be thinking clearly or creatively enough.


Abusing forum power since 1986.

Offline

#20 2013-04-11 16:36:17

xot
Administrator
Registered: 2007-08-18
Posts: 1,201

Re: Dithering for Game Design

I know I promised to upload this a couple years ago. Well, here it is.

http://host-a.net/u/xot/ds_grid_error_diffusion-gm8.gmk

The reason I didn't upload it originally is because I had some difficulty getting my reference filters to perfectly match my optimized, generalized dithering solution. I got tired of trying to figure it out and forgot about posting the project.

The heart of the project is the ds_grid_error_diffusion() script. It works similarly to the Floyd-Steinberg script posted earlier, but it takes as an argument any kernel you choose to feed it. Any of the kernels mentioned above can be used, with the exception of Ostromoukhov which works different than the rest.

The project features a kernel editor for experimenting (upper-right corner). It's not the most user friendly thing I've made, but it works. Press F1 for full instructions. The generalized solution I've provided is able to execute even very large kernels fairly quickly. The project also includes several test images to play with. This is a GM8 project. I think it will take some minor editing to get it working with GM:S.


Abusing forum power since 1986.

Offline

Board footer

Powered by FluxBB