Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1402007 Posts in 68021 Topics- by 61604 Members - Latest Member: pnaser74

August 09, 2022, 03:02:51 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperTechnical (Moderator: ThemsAllTook)Filling an image with (tiling) circles
Pages: [1]
Print
Author Topic: Filling an image with (tiling) circles  (Read 1486 times)
Thaumaturge
Level 10
*****



View Profile WWW
« on: August 25, 2020, 09:42:10 AM »

I want to generate an image that tiles in both the vertical and the horizontal, and which is filled with circles. Specifically, my requirements for my circles are as follows.

I want the circles to be:
  • Of generally similar sizes, but not all of a single size
  • Seemingly randomly placed
    • If a grid is involved, I don't want it to be apparent
  • Touching their neighbours
    • Small gaps are okay, but should be minimal and few

I've been trying to come up with a method of doing this (other than "sit down and draw it by hand in GIMP"), and thus far haven't found anything that seems likely to work well.

Does anyone have any suggestions as to how this might be done? (Whether by code, or Blender physics, or GIMP-script, or some other method besides.)
Logged


A Fantasy Top-Down "Space" Metroidvania
Itch page ~ Twitter
qMopey
Level 6
*


View Profile WWW
« Reply #1 on: August 25, 2020, 11:11:58 AM »

I have an idea!

You can use blue noise to generate points. Then you can fill in the circles with semi-random radii. Just make sure the noise distance from each point is large enough to not cause overlaps of the circles (unless you want them to overlap).

Then you can write code to detect if the image is tileable. Just loop over the borders and see if the pixels match! If it's not tiling, then reject it and continue. This would be like an offline baking process, an infinite loop.

I don't know enough (or hardly anything) about blue noise, but if there's a way to seed it, which I'm sure there is, you can use one-dimensional blue noise to generate tileable borders. This is the initialization, or seeded step. Then you can fill in the middle of the tile with randomized blue noise.
Logged
Thaumaturge
Level 10
*****



View Profile WWW
« Reply #2 on: August 26, 2020, 09:46:05 AM »

Thank you for the idea! ^_^

Hmm... I had a similar idea, I believe. My thought was to simply scatter points within the image, duplicating across borders for tiling purposes, and to then generate circles based on distances to neighbours; or something to that effect, I believe.

However, it seems to me that this might produce quit a few cases in which there are large gaps, as a result of arrangements that produce spaces between points that are rather longer in one dimension than another. A few such gaps wouldn't be a problem--but I fear that this might produce too many.

That said, I'm not familiar with blue noise--does it have some property that might help?
Logged


A Fantasy Top-Down "Space" Metroidvania
Itch page ~ Twitter
ThemsAllTook
Administrator
Level 10
******



View Profile WWW
« Reply #3 on: August 26, 2020, 10:57:40 AM »

This sounds like a fun little challenge.

My thought was to simply scatter points within the image, duplicating across borders for tiling purposes, and to then generate circles based on distances to neighbours; or something to that effect, I believe.

That'd be my starting point - a random point distribution with random radii assigned to each, with adjustments you can tweak for point count and radius min/mix so you could tweak for the density and variance you want. I'd then do some kind of pairwise iteration of every point with every other point, pushing them apart if they overlap. This would have to be an iterative process, since pushing two circles apart might put them inside others they didn't previously overlap, and might need some edge case handling for cases that don't resolve after some number of iterations (like, say, reducing the radius of circles that aren't in a position where pushing them around can stop them from intersecting). To get it to stabilize, I'd weight each iteration so that it moves things around less than the last, and do the radius adjustment step just once to clean up any remaining intersections.

For tiling, it'd just be a matter of making the distance calculations wrap on the x and y axes, and sampling the image in the same way. Note that this doesn't involve duplication - a single point could generate pixels and outward force in all four corners if it was close to one. My suspicion is that the weakness of this approach would be that it would leave empty spaces without a great way to fill them, but it'd hard to know without seeing it in action.

If I find a moment, I might just have to write a little test program to try this out. I'll share it here if I get any good results.
Logged

qMopey
Level 6
*


View Profile WWW
« Reply #4 on: August 26, 2020, 09:21:46 PM »

That said, I'm not familiar with blue noise--does it have some property that might help?

It produces visually nice results, perfect for a bunch of circles.

Logged
Thaumaturge
Level 10
*****



View Profile WWW
« Reply #5 on: August 27, 2020, 09:04:01 AM »

That'd be my starting point - a random point distribution with random radii assigned to each, with adjustments you can tweak for point count and radius min/mix so you could tweak for the density and variance you want. I'd then do some kind of pairwise iteration of every point with every other point, pushing them apart if they overlap.

...

Ooh, an iterative approach--that might just work, indeed!

Perhaps holes, if not too many, could be detected by testing points between neighbouring circles and then filling them in with little circles...

It produces visually nice results, perfect for a bunch of circles.

...

That... actually does look pretty good. I might well look this up, if the iterative approach doesn't work out. Thank you! ^_^

Also, that image is one of those that feels somewhat strange to look at for more than a moment, as the arrangement leads the eye flowing around the frame... o_o
Logged


A Fantasy Top-Down "Space" Metroidvania
Itch page ~ Twitter
JobLeonard
Level 10
*****



View Profile
« Reply #6 on: August 27, 2020, 03:25:01 PM »

Well, qMopey already brought up blue noise. I'd say go one step further and check out recursive Wang tiles:





http://johanneskopf.de/publications/blue_noise/

As for generating blue noise in 2D, this improved Bridson's Algorithm is a good start:

http://extremelearning.com.au/an-improved-version-of-bridsons-algorithm-n-for-poisson-disc-sampling/#more-2300

https://observablehq.com/@techsparx/an-improvement-on-bridsons-algorithm-for-poisson-disc-samp/2
Logged
qMopey
Level 6
*


View Profile WWW
« Reply #7 on: August 27, 2020, 11:32:52 PM »

Welp this seems like an entirely solved problem. Nice  Well, hello there!
Logged
JobLeonard
Level 10
*****



View Profile
« Reply #8 on: August 28, 2020, 02:02:54 AM »

Well, not entirely, but surprisingly much of it is, yeah Cheesy

It's worth going to Google Scholar and check which papers cite that paper, to see if any interesting follow-ups have happened since 2006:

https://scholar.google.de/scholar?hl=en&as_sdt=0%2C5&q=Recursive+Wang+Tiles+for+Real-Time+Blue+Noise&btnG=


This is a pretty extensive overview from two years after:

https://lirias.kuleuven.be/1652438?limo=0

And more recent paper with an interesting technique:

https://kops.uni-konstanz.de/bitstream/handle/123456789/40291/Ahmed_2-1ik12f8cd8mqq2.pdf?sequence=1

Here's a cool one using pinwheel tiles:

https://diglib.eg.org/handle/10.2312/cgvc20191271
Logged
Thaumaturge
Level 10
*****



View Profile WWW
« Reply #9 on: August 28, 2020, 08:11:15 AM »

Ah, thank you for those resources! ^_^

I suspect that some of them go further than I require for this application--I only intend a single repeatable tile, and I generation needn't be real-time--but they may nevertheless prove useful should I go the blue-noise route. ^_^
Logged


A Fantasy Top-Down "Space" Metroidvania
Itch page ~ Twitter
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic