4 ms·

Random-order dithering can be done in WebGL, but they are of poor quality. I am talking about error-diffusion dithering, where you are reading and writing pixel

Random-order dithering can be done in WebGL, but they are of poor quality. I am talking about error-diffusion dithering, where you are reading and writing pixels, and then re-reading those modified pixels that change the rest of the pixels. In WebGL, you can read the pixels of the image, but you cannot modify and read. You are returning the actual pixel you have modified, which is what glReadPixels() returns. You could use webgl, but you'd have to use glReadPixels() for every pixel modified so that the next pixel knows the new data.

dahart 10y ago
Yes, ordered dither is easier in a shader than error diffusion, that's true, but error diffusion is definitely possible on a GPU. If you need it. Do you really need it? Why not still use the GPU to accelerate whatever parts you can? Even if you dither on the CPU, doing your color filters on the GPU instead of in JS could make the difference between interactive and not. I don't know what you're doing exactly, but when you do need dithering, it's usually the last thing you need to do before output, and it's usually less important that the dither is fast than most other operations you need in an image editor. BTW, random order is lower quality, and error diffusion is better, only for for very low res color palettes. If your result is more than 256 colors, it's irrelevant, and for high quality dithering, e.g., 16 bits per channel colors to 8 bits per channel for print, random ordered dithering is superior. https://community.arm.com/graphics/b/blog/posts/when-parallelism-gets-tricky-accelerating-floyd-steinberg-on-the-mali-gpu https://community.arm.com/graphics/b/blog/posts/when-paralle... http://www.cs.cmu.edu/~imisra/projects/dithering/HybridDithering.pdf http://www.cs.cmu.edu/~imisra/projects/dithering/HybridDithe... https://www.shadertoy.com/view/4dt3W7 https://www.shadertoy.com/view/4dt3W7 That last one is ugly, but it's a great proof of concept here. You could get error diffusion in a shader using 2 passes. The first pass you render to texture, and the second pass, you can sample the texture however you want. Note how in this example, the error diffusion propagates backwards from what you would normally do in JS or C++, because it's a shader looping over destination pixels, not code that loops over source pixels. > In WebGL, you can read the pixels of the image, but you cannot modify and read. I don't know exactly what you mean here. You can modify & read pixels using render to texture, or using multiple passes. Render to texture will be faster, if you can do it. Multiple round-trips from CPU to GPU and back will be slower, so you want to limit the number of trips, but it's easy to do.
- devwastaken 10y ago
  >Even if you dither on the CPU, doing your color filters on the GPU instead of in JS could make the difference between interactive and not. Dithering requires quantization. If you mean things like brightness and contrast, yes, webgl is better for that. But quantization with error diffusion dithering is still based upon previous modified pixels, so you cannot just send a bunch of pixel info to webgl, you have to do each pixel seperately. Meaning, pushing through 2.5Million seperate inputs sequentially, and having to use glReadPixels() 2.5Million times. >BTW, random order is lower quality, and error diffusion is better, only for for very low res color palettes. Not in any of the images I have used. Ordered dithering looks fake, because it appears like a texture to the image. Dithering with error diffusion kernels, like Floyd-Steinberg create a less obvious texturization that still preserves the underlying image. >https://www.shadertoy.com/view/4dt3W7 https://www.shadertoy.com/view/4dt3W7 From what I'm reading, for every pixel, it is processing a 250 iteration loop that gets the pixels in the row and builds errors based upon those. However, it is not modifying any pixels as it goes, this is a parallel operation independent of each other. Good error diffusion with a kernel requires previous pixels to be modified, and errors to be built upon them, which is why it is a sequential operation. I don't see any destination-dependant pixel manipulation. >Multiple round-trips from CPU to GPU and back will be slower, so you want to limit the number of trips, but it's easy to do. If its possible to get data back from Uniform Buffer Objects in WebGL2, it may be possible to send up to 1000 or so uniform pixel values, but that is the general cap. Some GPU's have less. Unless I am missing some magic buffer you can use to write out many pixels too, and in that case I would be very interested in testing that, but shaders are designed to output a single pixel per instance. >https://community.arm.com/graphics/b/blog/posts/when-parallelism-gets-tricky-accelerating-floyd-steinberg-on-the-mali-gpu https://community.arm.com/graphics/b/blog/posts/when-paralle... From what I'm reading, this is using OpenCL, and parrallelizing in rows, but these rows have height. A single thread processes one row and sequentially goes through the pixels like normal error diffusion. Just that this breaks different parts of the image up. I may have to try this out in JS and see if perhaps it can thread better that way. ty.
  - dahart 10y ago
    > so you cannot just send a bunch of pixel info to webgl, you have to do each pixel seperately. Why do you think that? You certainly can get previously modified pixels, you can send millions of pixels to WebGL with a single call (as a texture). Nobody calls glReadPixels millions of times, that's a bad idea. :) You might want to investigate multipass rendering techniques. Small kernel convolutions, for example, are standard and simple operations in WebGL. People use blur & edge filters all the time, and those depend on neighborhood computation. Regarding the 1-d error diffusion shader on shadertoy, it is using a gather instead of a scatter. It's a pull instead of a push, he flipped the operation inside-out. It is still computing error diffusion correctly (but for only a single pixel row). And it's running at 60fps. This is the whole point I tried to make above multiple times wrt performance: this code looks unrecognizable compared to the straightforward CPU serial way to implement error diffusion. The reason this example is correct (in 1D) is because it recomputes the error propagation for every destination pixel; it's wasting almost all of the computation it's doing because in this case it's not sharing the error computation. But that doesn't mean it can't -- this is just a proof of concept on ShaderToy, not the limit of what you can do. You can't do multipass with ShaderToy, and multipass is how you share pixel results from one iteration to the next. > Unless I am missing some magic buffer you can use to write out many pixels to It sounds like you're missing render to texture and multipass techniques, the ways to use textures as compute I/O. To do multipass in WebGL and share the results of computation from one pass to the next, you create an offscreen framebuffer for your results, and you render directly to that framebuffer. You can then use the result as an input texture for the next pass (via glCopyTexImage2D) or you can read back the buffer (via glReadPixels) and then you repeat. Using glCopyTexImage2D is much faster because you never leave the GPU. I think you could do error diffusion by rendering the error to a texture, and using a multipass technique that only needs as many iterations as the maximum distance any error could travel. In the worst case it'd probably be the greater of your image width or image height, e.g. 512 passes for a 512x512 image, but in practice I think you'd be done much sooner. That's assuming there isn't something hierarchical and more clever that could do it in log(width) passes, which I suspect there is.

dahart 10y ago

Yes, ordered dither is easier in a shader than error diffusion, that's true, but error diffusion is definitely possible on a GPU. If you need it. Do you really need it? Why not still use the GPU to accelerate whatever parts you can? Even if you dither on the CPU, doing your color filters on the GPU instead of in JS could make the difference between interactive and not. I don't know what you're doing exactly, but when you do need dithering, it's usually the last thing you need to do before output, and it's usually less important that the dither is fast than most other operations you need in an image editor. BTW, random order is lower quality, and error diffusion is better, only for for very low res color palettes. If your result is more than 256 colors, it's irrelevant, and for high quality dithering, e.g., 16 bits per channel colors to 8 bits per channel for print, random ordered dithering is superior. https://community.arm.com/graphics/b/blog/posts/when-parallelism-gets-tricky-accelerating-floyd-steinberg-on-the-mali-gpu https://community.arm.com/graphics/b/blog/posts/when-paralle... http://www.cs.cmu.edu/~imisra/projects/dithering/HybridDithering.pdf http://www.cs.cmu.edu/~imisra/projects/dithering/HybridDithe... https://www.shadertoy.com/view/4dt3W7 https://www.shadertoy.com/view/4dt3W7 That last one is ugly, but it's a great proof of concept here. You could get error diffusion in a shader using 2 passes. The first pass you render to texture, and the second pass, you can sample the texture however you want. Note how in this example, the error diffusion propagates backwards from what you would normally do in JS or C++, because it's a shader looping over destination pixels, not code that loops over source pixels. > In WebGL, you can read the pixels of the image, but you cannot modify and read. I don't know exactly what you mean here. You can modify & read pixels using render to texture, or using multiple passes. Render to texture will be faster, if you can do it. Multiple round-trips from CPU to GPU and back will be slower, so you want to limit the number of trips, but it's easy to do.

devwastaken 10y ago
>Even if you dither on the CPU, doing your color filters on the GPU instead of in JS could make the difference between interactive and not. Dithering requires quantization. If you mean things like brightness and contrast, yes, webgl is better for that. But quantization with error diffusion dithering is still based upon previous modified pixels, so you cannot just send a bunch of pixel info to webgl, you have to do each pixel seperately. Meaning, pushing through 2.5Million seperate inputs sequentially, and having to use glReadPixels() 2.5Million times. >BTW, random order is lower quality, and error diffusion is better, only for for very low res color palettes. Not in any of the images I have used. Ordered dithering looks fake, because it appears like a texture to the image. Dithering with error diffusion kernels, like Floyd-Steinberg create a less obvious texturization that still preserves the underlying image. >https://www.shadertoy.com/view/4dt3W7 https://www.shadertoy.com/view/4dt3W7 From what I'm reading, for every pixel, it is processing a 250 iteration loop that gets the pixels in the row and builds errors based upon those. However, it is not modifying any pixels as it goes, this is a parallel operation independent of each other. Good error diffusion with a kernel requires previous pixels to be modified, and errors to be built upon them, which is why it is a sequential operation. I don't see any destination-dependant pixel manipulation. >Multiple round-trips from CPU to GPU and back will be slower, so you want to limit the number of trips, but it's easy to do. If its possible to get data back from Uniform Buffer Objects in WebGL2, it may be possible to send up to 1000 or so uniform pixel values, but that is the general cap. Some GPU's have less. Unless I am missing some magic buffer you can use to write out many pixels too, and in that case I would be very interested in testing that, but shaders are designed to output a single pixel per instance. >https://community.arm.com/graphics/b/blog/posts/when-parallelism-gets-tricky-accelerating-floyd-steinberg-on-the-mali-gpu https://community.arm.com/graphics/b/blog/posts/when-paralle... From what I'm reading, this is using OpenCL, and parrallelizing in rows, but these rows have height. A single thread processes one row and sequentially goes through the pixels like normal error diffusion. Just that this breaks different parts of the image up. I may have to try this out in JS and see if perhaps it can thread better that way. ty.
- dahart 10y ago
  > so you cannot just send a bunch of pixel info to webgl, you have to do each pixel seperately. Why do you think that? You certainly can get previously modified pixels, you can send millions of pixels to WebGL with a single call (as a texture). Nobody calls glReadPixels millions of times, that's a bad idea. :) You might want to investigate multipass rendering techniques. Small kernel convolutions, for example, are standard and simple operations in WebGL. People use blur & edge filters all the time, and those depend on neighborhood computation. Regarding the 1-d error diffusion shader on shadertoy, it is using a gather instead of a scatter. It's a pull instead of a push, he flipped the operation inside-out. It is still computing error diffusion correctly (but for only a single pixel row). And it's running at 60fps. This is the whole point I tried to make above multiple times wrt performance: this code looks unrecognizable compared to the straightforward CPU serial way to implement error diffusion. The reason this example is correct (in 1D) is because it recomputes the error propagation for every destination pixel; it's wasting almost all of the computation it's doing because in this case it's not sharing the error computation. But that doesn't mean it can't -- this is just a proof of concept on ShaderToy, not the limit of what you can do. You can't do multipass with ShaderToy, and multipass is how you share pixel results from one iteration to the next. > Unless I am missing some magic buffer you can use to write out many pixels to It sounds like you're missing render to texture and multipass techniques, the ways to use textures as compute I/O. To do multipass in WebGL and share the results of computation from one pass to the next, you create an offscreen framebuffer for your results, and you render directly to that framebuffer. You can then use the result as an input texture for the next pass (via glCopyTexImage2D) or you can read back the buffer (via glReadPixels) and then you repeat. Using glCopyTexImage2D is much faster because you never leave the GPU. I think you could do error diffusion by rendering the error to a texture, and using a multipass technique that only needs as many iterations as the maximum distance any error could travel. In the worst case it'd probably be the greater of your image width or image height, e.g. 512 passes for a 512x512 image, but in practice I think you'd be done much sooner. That's assuming there isn't something hierarchical and more clever that could do it in log(width) passes, which I suspect there is.