Alrighty.

I managed to work through a bunch of the code and twiddle this and that until I
got it to "work" and pretty much fill the screen with selected points.

The first issue that I ran into was that I was doing some kind of "screen size
math" which was just messing everything up, so I'm just using the whole image
resolution.

Then I managed to get a bunch of cycles to function, but the algorithm would
exit early - sometimes after only 7 cycles.

I added some logic to break out of the nested loops, and then I expanded the
neighbor search to a 5x5 grid, as suggested/explained/illustrated by Sebastian
Lague.

It still runs forever without a bailout value set, instead of exhausting the
Active array and properly exiting the macro.

Finally, the points are clustered much too closely - I ought to be able to draw
circles with radius R that don't overlap, and the attached image is using
circles that are only R/4.

Clearly POV-Ray is very different than Javascript or C#, or I'm really in a long
stretch of brain-fry or code blindness and am missing something very simple but
utterly crucial.

- BW

Post a reply to this message

Attachments:
Download 'poisson-disc sampling.pov.txt' (7 KB)

On 23/09/2023 01:30, Bald Eagle wrote:

> 
> One thing that I did notice is that I'm splicing out array entries until I have
> an empty array.
> 
> That was triggering an invalid array size error, which I fixed / worked around
> by doing:
> 
> #if (newSize <= 0)
>   #local tmpArray = array;
>  #else
>   #local tmpArray = array[newSize]
>  #end
> 
> and
> 
> #if (newSize <= 0)
>   #declare thisArray = array;
>  #else
>   #declare thisArray = array[newSize]
>  #end
> 
> 
> Maybe do some further testing and see what you think, then update that last
> macro.
> 


AAs always, that's a very good remark on your part.

I've never thought about the cases where the arrays are empty.

I'm going to apply your suggestions, correct my macros and
run more in-depth tests.







-- 
Kurtz le pirate
Compagnie de la Banquise

Post a reply to this message

"Bald Eagle" <cre### [at] netscapenet> wrote:
So, I played around with starting to implement the Fortune algorithm for the
Voronoi diagram, but I also need a DCEL and a red-black tree data structure, a
balanced binary tree, or similar.

I got a bunch of points and a scan line, and managed to plot all of the
parabolas and kind of draw some of the Voronoi edges by looping all the way down
the screen and plotting all of the intersection points.
It took a long time to spot a pair of missing parentheses that I should have
had.
Repeat after me: -b +/- sqrt (b*b -4*a*c)    ***ALL*** over 2*a
which makes it (-b +/- sqrt (b*b -4*a*c)) / 2*a

Someone said it was easier to code the Bowyer-Watson algorithm, so I might try
to code both in parallel and see which one (if any) I get to work first.

For that, I need to test if a point lay inside of a triangle's circumcircle, and
luckily someone had a nice little simple compact method for doing so.

I always find it fascinating how many geometric questions can be answered just
by simple arithmetic of point coordinates, be it sum, difference,
multiplication, vdot, vcross, or a matrix determinant.

We would be served well by compiling a list of such useful tricks and
maintaining that on a wiki page, or in the documentation, or as a periodically
updated (with version number and date) include file.

I also find these simple inside/outside test renders to be unusually visually
appealing for some reason.  Attached is the testing of 5000 points against a
triangle's circumcircle.

If there was a band named POV-Ray (a college friend had a band named Man Ray)
this would make a good album cover.   :D

- BE

Post a reply to this message

Attachments:
Download 'circumcircle.png' (348 KB)

Preview of image 'circumcircle.png'

Re: Voronoi Furtune algorithm

"Bald Eagle" <cre### [at] netscapenet> wrote:
> "Bald Eagle" <cre### [at] netscapenet> wrote:
> So, I played around with starting to implement the Fortune algorithm for the
> Voronoi diagram, but I also need a DCEL and a red-black tree data structure, a
> balanced binary tree, or similar.

Update here - jr has been leading me by the nose-hairs to get the binary tree /
Red-Black tree coded up, and hopefully we (mostly he) will have some code we can
start to play with soon.

> Someone said it was easier to code the Bowyer-Watson algorithm, so I might try
> to code both in parallel and see which one (if any) I get to work first.

Admittedly, I have not started on that one yet.

The RB-tree and the DCEL are used for storing the data for/from the Fortune
algorithm, and that seems to be mostly the results of "site events" and "circle
events".

The site event seems trivial (scanline is the same height as a voronoi seed),
and so I worked out the detection of a circle event (the intersection of 3
parabolas)  to the best of my meager ability.

Shown is the point where the scanline generates a circle event, where the seeds
are all equidistant from each other and the scanline, and so all lie on a
circumcircle, with the Voronoi vertex at the center.

- BW

Post a reply to this message

Attachments:
Download 'circleeventdetection.png' (42 KB)

Preview of image 'circleeventdetection.png'

hi,

"Bald Eagle" <cre### [at] netscapenet> wrote:
> Re: Voronoi Furtune algorithm
> ...
> Update here - jr has been leading me by the nose-hairs ...

_that's_ what they were, eh ?!  </grin>


> to get the binary tree / Red-Black tree coded up, and hopefully we (mostly he) will
have some code we can
> start to play with soon.

to tease..


regards, jr.

Post a reply to this message

Attachments:
Download '231022-be.png' (62 KB)

Preview of image '231022-be.png'

Made some progress sorting out the whole "sparse convolution noise".

Probably don't need to pursue this part any further until i see how it works in
the whole texture-generating chain of algorithms.

Post a reply to this message

Attachments:
Download 'sparseconvolutionnoise.png' (33 KB)

Preview of image 'sparseconvolutionnoise.png'

Working through the spiral part of:

http://flycooler.com/download/Wood_SIGAsia2016.pdf

And struggling to understand

1) how the texture actually gets mapped/tiled onto the spiral

and

2) what points then, am I interpolating?

I'm guessing that either the 2D texture get mapped once onto each successive
turn of the spiral,
or it gets mapped linearly onto the nonlinear arc-length of the spiral arms, and
so there are then spaces between the x-dimension points?

Maybe someone could look at this and offer some ideas?
Even if you're just shooting in the dark, whatever you suggest might trigger an
idea for a solution.

Thanks!

- BW

Post a reply to this message

Slowing working through things.

To help me work through understanding how to use the end result of all of the
daisy-chained algorithms in an actual texture, I needed to understand how to
remap <x, y> into <r, theta>

So here's a nice pigment {function {}} to make an infinite spiral in the xy
plane.

(Thanks again, ShaderToy coders!)

I think this would be a nice basic stock pattern for POV-Ray.
I set the spiral turn spacing to twice the line thickness to get a "maximally
dense" spiral.

- BW

Post a reply to this message

Attachments:
Download 'spiralpattern.png' (588 KB)

Preview of image 'spiralpattern.png'

It also seems to me that in addition to knowing if I'm on of off/in-between the
spiral, I'll need to somehow be able to know how far along the arc length of the
spiral I am at any given point.

Varying the r, g, and b values by different multiples of the arc length formula,
and changing the thickness of the lines as a function of arc length gives me the
attached.

- BW

Post a reply to this message

Attachments:
Download 'spiralpattern.png' (439 KB)

Preview of image 'spiralpattern.png'

On 11/2/23 18:19, Bald Eagle wrote:
> I think this would be a nice basic stock pattern for POV-Ray.
> I set the spiral turn spacing to twice the line thickness to get a "maximally
> dense" spiral.

I'm interested - FWIW. :-)

Maybe 5-6 weeks back I started to dig more into our warp{} code. I'd 
like to rework it all, including a bunch of hacks I have in that code. 
Then stuff, and more stuff, and it's on the back burner of the stove 
again...

One thing I'd like to do in yuqk is dump the two inbuilt spiral patterns 
for more general, tapered spiral warping as one or more additional 
options of the warp{} mechanism.

We have too f_spiral() - which has issues - as you well know. The 
solutions to which, I believe, sit more with some sort of general 
tapered warping capability.

Aside: We can today implement a limited form of the sort of spiral - I 
think you're implementing - with a series of half arc functions (there 
is too the new-ish list_object pattern in yuqk which could use the torus 
or functions via coded isosurfaces(a) (inside tests)). This approach, 
however, slows down significantly on the addition of each half arc.

(a) The inside test of 'isosurface shapes' is relatively fast when used 
for object based patterns. It's just whether the function returns a 
negative value or not at a given location. In fact, 'isosurface shapes 
for inside test purposes' do not need to be good isosurfaces with 
respect to being render-able as actual shapes!

Anyhow, I'm interested in seeing what code you work up.

Bill P.

Post a reply to this message