Non-photorealistic rendering projects

MartinBraendli2

gtoal wrote:
This has however interested me in dithering algorithms such as Floyd-Steinberg which I think I will give a try to soon.

Sorry, looks like I “stole” your project. I have seen your post just after i finished it.

gtoal wrote:
did try that in one iteration, but it looked even worse :-(

Press 6 in my project. RGB and W are enough to get a decent picture. At least with error diffusion.

Edit: Spelling

Last edited by MartinBraendli2 (June 3, 2016 04:52:55)

gtoal

MartinBraendli2 wrote:
Sorry, looks like I “stole” your project. I have seen your post just after i finished it.

Not at all! That's great!

gtoal

New challenge/collab suggestion!

I dusted off my point recorder and fixed a few problems ( https://scratch.mit.edu/projects/76587082/ ) so that now it is usable to record the positioning of 300 points over an image. (It could do with a better user interface, but it's at least usable now, if a bit slow.)

If you take those recorded points (up to 300) and apply a Delauney graph to them, you have a set of triangles that ought to make a pretty good poly art image.

Zro716 has a Delauney algorithm ( https://scratch.mit.edu/projects/47435046/ ) but even with 100 points it's too slow. I think it may be possible to speed it up by using a spatial data structure for finding nearest neighbours. That's a good old computer science problem that I think is fairly well solved.

(Zro also has a reasonably fast Voronoi art generator https://scratch.mit.edu/projects/76291226/ but to get the edges of poly art right you need Delauney, not Voronoi. I don't think it would be easy to find the dual of a Voronoi that was generated graphically - that trick creates no data structure)

I'm inviting anyone who specialises in speeding up Scratch code to take Zro's Delauney (or write a new one) and make it fast enough to handle 300 points. Then merge that with my point recorder, so that you can see the Delauney in place after recording the points.

Once we have that, we can use the code from one of many NPR programs that finds the average colour for any triangle in the image, in order to colour in the Delauney, creating a complete Poly Art image editor that can be tweaked in close to real time. (As you know, our Poly Art version of NPR Guy was constructed semi-manually using an external image edting program)

In fact if we have a spatial data structure and an easy way of finding nearest points, I can use that to rewrite the point recorder without clones which should speed it up considerably, which I'll do as a second iteration if we can get a working poly art generator going first.

Graham

ilikelegos

gtoal wrote:
New challenge/collab suggestion!

I dusted off my point recorder and fixed a few problems ( https://scratch.mit.edu/projects/76587082/ ) so that now it is usable to record the positioning of 300 points over an image. (It could do with a better user interface, but it's at least usable now, if a bit slow.)

If you take those recorded points (up to 300) and apply a Delauney graph to them, you have a set of triangles that ought to make a pretty good poly art image.

Zro716 has a Delauney algorithm ( https://scratch.mit.edu/projects/47435046/ ) but even with 100 points it's too slow. I think it may be possible to speed it up by using a spatial data structure for finding nearest neighbours. That's a good old computer science problem that I think is fairly well solved.

(Zro also has a reasonably fast Voronoi art generator https://scratch.mit.edu/projects/76291226/ but to get the edges of poly art right you need Delauney, not Voronoi. I don't think it would be easy to find the dual of a Voronoi that was generated graphically - that trick creates no data structure)

I'm inviting anyone who specialises in speeding up Scratch code to take Zro's Delauney (or write a new one) and make it fast enough to handle 300 points. Then merge that with my point recorder, so that you can see the Delauney in place after recording the points.

Once we have that, we can use the code from one of many NPR programs that finds the average colour for any triangle in the image, in order to colour in the Delauney, creating a complete Poly Art image editor that can be tweaked in close to real time. (As you know, our Poly Art version of NPR Guy was constructed semi-manually using an external image edting program)

In fact if we have a spatial data structure and an easy way of finding nearest points, I can use that to rewrite the point recorder without clones which should speed it up considerably, which I'll do as a second iteration if we can get a working poly art generator going first.

Graham

Sounds cool, but I won't be of much help there. Though I can't wait to see the results!

Hi! I'm a computer science student who learned coding on Scratch!

Zro716

I had this brilliant idea for a new approach to the Delauney problem:

For every pair of points that make a unique line…
1. Check every other line in stack for intersections.
2. If at least one intersecting line is shorter, do not add line
3. Otherwise, delete all other intersecting lines and add line to stack

It kind of works, but once or twice it will leave or create a “quadrilateral” open space. I'm not sure if the problem is inherent to the design or if it's avoidable. It's definitely a new approach but it could use some fine-tuning.

Anyways, you can play around my demo w/ 20 points here: http://phosphorus.github.io/#110336333

As a long time Scratcher, I have found new meaning to the name “Scratch”: for me, it means to “scratch that itch”, to come back again and again to realize new ideas in this toy language, even when I'm capable of creating my projects in real programming languages years later. It's a friend that helped me to pursue programming and get me to enjoy its fruit. I'm certain many others who have walked this path as well have grown fond of its importance in their life.

NickyNouse

Zro716 wrote:
I had this brilliant idea for a new approach to the Delauney problem:

For every pair of points that make a unique line…
1. Check every other line in stack for intersections.
2. If at least one intersecting line is shorter, do not add line
3. Otherwise, delete all other intersecting lines and add line to stack

It kind of works, but once or twice it will leave or create a “quadrilateral” open space. I'm not sure if the problem is inherent to the design or if it's avoidable. It's definitely a new approach but it could use some fine-tuning.

Anyways, you can play around my demo w/ 20 points here: http://phosphorus.github.io/#110336333

is it any faster?

are you deleting the lines as you go? step 2 might need the lines that have already failed other tests?

gtoal

One thing to be aware of… for a poly art generator, fast is better than accurate - as long as it looks about right, it doesn't have to be a canonical delauney.

gtoal

Zro716 wrote:
It kind of works, but once or twice it will leave or create a “quadrilateral” open space. I'm not sure if the problem is inherent to the design or if it's avoidable.

Isn't it a problem with all delauney algorithms if you have four equidistant points?

A simple way of visualising the problem is if you have four points making a square, which diagonal do you pick to triangulate that square? Since either one will do, there's no fixed solution.

In practice it's easy to always choose consistently, eg top left to botton right.

gtoal

Zro716 wrote:
I had this brilliant idea for a new approach to the Delauney problem:

For every pair of points that make a unique line…
1. Check every other line in stack for intersections.
2. If at least one intersecting line is shorter, do not add line
3. Otherwise, delete all other intersecting lines and add line to stack

It kind of works, but once or twice it will leave or create a “quadrilateral” open space. I'm not sure if the problem is inherent to the design or if it's avoidable. It's definitely a new approach but it could use some fine-tuning.

Anyways, you can play around my demo w/ 20 points here: http://phosphorus.github.io/#110336333

I finally got this to run by switching to the Edge browser (seems broken on Chrome on my machine, probably adblock or privacy badger related), and it looks good - good enough for the polyart editor *if* it scales up to 300 points. Could you try that, see what happens?

thanks

G

gtoal

Zro716 wrote:
I had this brilliant idea for a new approach to the Delauney problem:

For every pair of points that make a unique line…
1. Check every other line in stack for intersections.
2. If at least one intersecting line is shorter, do not add line
3. Otherwise, delete all other intersecting lines and add line to stack

It kind of works, but once or twice it will leave or create a “quadrilateral” open space. I'm not sure if the problem is inherent to the design or if it's avoidable. It's definitely a new approach but it could use some fine-tuning.

Anyways, you can play around my demo w/ 20 points here: http://phosphorus.github.io/#110336333

If there are N points…

for any one point, there are N-1 lines possible.

So there are N^2-N (let's just call it N^2) lines altogether.

Each line has to be compared to every other line, so doesn't that mean N^4 comparisons?

If N=300 then N^4 = 81 00 00 00 00 comparisons, roughly? Call it 10^10 for an order of magnitude.

Which would imply it doesn't scale well? Or did I make a wrong assumption somewhere?

Zro716

gtoal wrote:
Each line has to be compared to every other line, so doesn't that mean N^4 comparisons?

If N=300 then N^4 = 81 00 00 00 00 comparisons, roughly? Call it 10^10 for an order of magnitude.

Which would imply it doesn't scale well? Or did I make a wrong assumption somewhere?

On the first big loop it creates N-1 lines, then it can add or delete lines depending on what intersections it finds, so it maintains a relatively stable heap of lines to compare (N log N I believe). So you're close, it's N^3 log N.

I honestly don't know how it compares to my other Delauney implementation, so I'll have to do some benchmarking… 100 points didn't take too long, but for 300 it might have been too much.

*testing*

Yes, it seems my calculations are about right. I graphed the N^3 log N curve over the benchmark times for 1-80 points and it fits when a = 0.000015. Using the regression I estimated, at N = 300 it would take around 1000 seconds (16 mins 40 secs) to finish. So probably not the fastest at that scale, but this is Scratch, everything is slower.

Last edited by Zro716 (June 4, 2016 19:39:20)

As a long time Scratcher, I have found new meaning to the name “Scratch”: for me, it means to “scratch that itch”, to come back again and again to realize new ideas in this toy language, even when I'm capable of creating my projects in real programming languages years later. It's a friend that helped me to pursue programming and get me to enjoy its fruit. I'm certain many others who have walked this path as well have grown fond of its importance in their life.

Zro716

Edit: Darn double post bug. I hit a 404 and a 403.

Last edited by Zro716 (June 4, 2016 19:37:38)

As a long time Scratcher, I have found new meaning to the name “Scratch”: for me, it means to “scratch that itch”, to come back again and again to realize new ideas in this toy language, even when I'm capable of creating my projects in real programming languages years later. It's a friend that helped me to pursue programming and get me to enjoy its fruit. I'm certain many others who have walked this path as well have grown fond of its importance in their life.

gtoal

Zro716 wrote:
gtoal wrote:
Each line has to be compared to every other line, so doesn't that mean N^4 comparisons?

If N=300 then N^4 = 81 00 00 00 00 comparisons, roughly? Call it 10^10 for an order of magnitude.

Which would imply it doesn't scale well? Or did I make a wrong assumption somewhere?
On the first big loop it creates N-1 lines, then it can add or delete lines depending on what intersections it finds, so it maintains a relatively stable heap of lines to compare (N log N I believe). So you're close, it's N^3 log N.

I honestly don't know how it compares to my other Delauney implementation, so I'll have to do some benchmarking… 100 points didn't take too long, but for 300 it might have been too much.

*testing*

Yes, it seems my calculations are about right. I graphed the N^3 log N curve over the benchmark times for 1-80 points and it fits when a = 0.000015. Using the regression I estimated, at N = 300 it would take around 1000 seconds (16 mins 40 secs) to finish. So probably not the fastest at that scale, but this is Scratch, everything is slower.

16 minutes using an O(N^3logN) alg is actually promising - since the N^3 part can also be reduced considerably by using a divide and conquer strategy, ie a spatial data structure such as a quad tree. That should get at a minimum an N^2 component down to NlogN. That could be enough.

Even if not, it's great to see a new algorithm for an old problem. Worth drilling down on for sure.

I'm wondering if there's any ‘meet in the middle’ ground to be found with a hybrid of your bottom-up algorithm and something top-down such as http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c8901/Delaunay-Triangles.htm ?

gtoal

For “The Polyart Problem” (as opposed to classic Delaunay), there's a couple of other considerations besides the ones I mentioned already (ie fast better than accurate, arbitrary but consistent resolution when > 3 points on a circle).

We want to interactively add points

We want to interactively remove points

We want to interactively move points

*and* I think, when we make modifications to a triangulation, we can accept only local changes, we don't need to insist on mesh-wide changes if the algorithm turns out to be easier that way.

The interface I envisage for a poly art editor is to have a live triangulation superimposed on top of a photograph in semi-transparent mode (degree of transparency on a slider) so that you see changes to the polyart the instant you modify a point.

Colouring is done by averaging the contents of a triangle, but if there are adjacent triangles of the same colour, then one should be tweaked a tiny bit lighter and the neighbor a tiny bit darker. If this causes a knock-on effect, a 4-colour map theorem solution (actually, 3 colours for a tirangulation) could be used to distribute the deltas across the entire image. This is so that the poly art retains a triangulated look and doesn't create large flat surfaces of the same colour, which orevious experiments have shown to be unaesthetic.

Classic Delauney is NlogN worst case, with the logN coming from optimising the spacial searching. With an incremental assembly, we may not have that luxury and may be forced to accept N^2 worst case, *but* since I envision this as an interactive editor, I think we can arrange it so that the first N is spread out over time (ie as you add each point interactively) with the result that the interactive delay is only a single N or if lucky, just logN, for the incremental work needed to add a single new point. This should guarantee a pretty zippy interactive experience.

Then the mesh info can be saved with the final design so that it is precomputed if that design is lioaded again, to ensure that you're never hit with the N^2 in a single operation.

Is this plausible? (edit: it is! I found an android app that's almost exactly this. Also, https://github.com/whyi/Delaunay is a good incremental mesh builder…)

G
PS Once we have a good polyart editor, we can play with automatically determining the control points. My gut tells me that intersecting a grid with the lines of an ETF will be a fairly good approximation, especially if enhanced by detecting endpoints or points of inflection of lines in the ETF. If we can get 95% of the way there and have to manually tweak 5% of the control points to make good aesthetic choices, I'll be more than satisfied.

Last edited by gtoal (June 4, 2016 21:47:32)

gtoal

I just noticed that 0 : (480*360)^3 can be exactly represented by Scratch's variables as integers. I believe this means that we can represent 3 points in a scratch display within a single scratch variable.

This is rather nice as it may give us a compact way to represent the triangles in polyart…

(and I'm thinking ahead to animated polyart in the style of Martin Braendli's compact videos…)

I'm not sure how much room is left in the 52 bit mantissa - how many colours can we represent in there too without getting into extremely expensive packing/unpacking of the IEEE float representation? Or do we just multiply by 2^X where X is the colour represented within the 12 bit exponent?

Last edited by gtoal (June 6, 2016 01:25:10)

Layzej

Layzej wrote:
@MartinBraendli2 suggested stacking the lego bricks Here it is:

gtoal

Features for a polyart editor?

Let's assume we've mastered the mesh design and have a good set of triangles. We need to colour our image…

1) automatically assign colour using image below triangle
1.5) optionally using something like error diffusion into neighbouring triangles if the colour space is restricted
2) Assign WPAP-style contrasting colours rather than true colour - but this requires that we preserve luminosity and only alter hue
3) manually tweak
3.1) assign colour from a colour picker
3.2) lighten existing colour
3.3) darken existing colour
4) handle areas with multiple triangles of the same colour
4.1) possibly use 4-colour map theorem to locally lighten and darken neighnouring triangles, leaving overall image at same intensity?
4.2) merge triangles into polygons
4.2.1) … but only convex polygons (because IMHO from earlier trials, concave polygons look weird)

Anything else?

G

Last edited by gtoal (June 6, 2016 19:29:15)

ilikelegos

gtoal wrote:
Features for a polyart editor?

Let's assume we've mastered the mesh design and have a good set of triangles. We need to colour our image…

1) automatically assign colour using image below triangle
1.5) optionally using something like error diffusion into neighbouring triangles if the colour space is restricted
2) Assign WPAP-style contrasting colours rather than true colour - but this requires that we preserve luminosity and only alter hue
3) manually tweak
3.1) assign colour from a colour picker
3.2) lighten existing colour
3.3) darken existing colour
4) handle areas with multiple triangles of the same colour
4.1) possibly use 4-colour map theorem to locally lighten and darken neighnouring triangles, leaving overall image at same intensity?
4.2) merge triangles into polygons
4.2.1) … but only convex polygons (because IMHO from earlier trials, concave polygons look weird)

Anything else?

G

Would it just average together all the colors under the triangle? Or would it somehow pick the most prominent or important color for the image?

Hi! I'm a computer science student who learned coding on Scratch!

gtoal

ilikelegos wrote:
Would it just average together all the colors under the triangle? Or would it somehow pick the most prominent or important color for the image?

'most prominent colour' isn't an obvious concept if the colour range in the image is continuous as in a photograph. The most common colour may only occur 1% of the time, for example, if there are a lot of gradations of colour - say 500 pixels, most of which are unique colours but one colour occurs in 5 separate pixels. So you have to bin the colours into ranges, and say ‘most common is a variation of purple’ but then you have to pick which purple to represent it with…

average is looking pretty good at this point. Probably some sort of weighted average.

Then if the drawing technique limits you to a fixed palette, the problems becomes choosing an actual colour closest to the ideal colour.

There have been quite a few NPR projects already that have had to pick colours when painting an area. What have you guys done?

Layzej

I've always used the average. I think some select the colour at the center of the polygon.

Discuss Scratch