On 11/1/24 09:36, Bald Eagle wrote:
> I would greatly appreciate some advice on how to properly accomplish this, as my
> experiments in the past were fraught with unwanted artefacts:
> https://news.povray.org/ 
> web.6394be0a7dc652cc1f9dae3025979125%40news.povray.org
> 
> I'm sure that one of your long "ramblings on" would be an insightful read, and
> probably spur on other tangential projects - as they always do.
> 
> Hopefully we'll both have a few round-tuits at some point to compare notes.
> 
> Good work, and much appreciated!

Hi Bill.

Thanks.

Unsure how much my particular methods might help! How one might approach 
repeatability depends on the environment, underlying metrics, forms, etc.

In my re-write of the crackle code I took advantage of newer hardware 
and features of C++. For example, I push all the working coordinates 
into a +x, +y +z space. Already the working grid internally (for the 
cubes) was integer based as the origin for each offset point relative to 
the evaluation point.

Much of the trouble I had with repeat (I suspect it's related to what's 
wrong with the v3.8 repeat feature and caching too) was realizing I had 
to do the cube calculations for offsets apart from the cached cube 
coordinates. This something which might not even be doable with the 
cache structure of the V3.8 beta 2 code - not thought about it too much 
though. The yuqk caching is set up differently.

When I finally got my head on straight about that, the repeat code 
became something which creates x,y,z unsigned integer coordinates 
differently for the negative cube coordinates and positive cube 
coordinates about the center evaluation cube - depending upon where in 
the repeat range the evaluation point is on each axis.

In the POV-Ray implementation, a virtual environment of cubes containing 
offset points is created around each cube in space where we find 
ourselves evaluating 3D locations. For the repeat aspect, suppose I 
created what amounts to another virtual working space on top of that one 
in which to repeat.

Backing up, the POV-Ray set up of a virtual box of cubelets containing 
the center cube with the evaluation point is driven by the 'form' 
feature. It requires up to three closest point measures for downstream 
metric calculations.

If for your crackle implementation, you only care about the closest 
points - as is true for solid(*) results - the implementation can be 
simpler.

(*) - In the yuqk re-write I treat the solid feature as something almost 
completely apart from the crackle proper features.

Anyhow. The updated source code will be in the next yuqk release (R16). 
Having it to review might help make sense of what I've written.

Bill P.

Aside: I'm reminded that years ago I experimented some with different 
shape functions set at point locations as a way to to create crackle 
pattern shapes - all in SDL - which was limiting. The traditional 
crackle solid look you can create with cones. Can't find the post... Too 
many ideas and not enough time. :-)

Post a reply to this message

William F Pokorny <ano### [at] anonymousorg> wrote:

> Unsure how much my particular methods might help! How one might approach
> repeatability depends on the environment, underlying metrics, forms, etc.

I guess I was mostly interested in if/how you were doing the modular arithmetic
to get seamless tiling, and assign pattern results to drive color_map values.

> In my re-write of the crackle code I took advantage of newer hardware
> and features of C++. For example, I push all the working coordinates
> into a +x, +y +z space. Already the working grid internally (for the
> cubes) was integer based as the origin for each offset point relative to
> the evaluation point.

So - you've got a central cubelet surrounded by 26 other neighbor cubelets.
Is the central cubelet (off)set at <2, 2, 2>?

I suppose I will have to read through your code to better understand, and ask
better questions (or any at all).


Recalling some of your other posts - the pattern looks very "cubic" - rather
than a typical Voronoi pattern.

Also, have you thought about allowing user-defined distance metrics (Euclidean,
Manhattan, Minkowski, etc.) for generating the underlying pattern?

- BW

Post a reply to this message

On 11/6/24 10:51, Bald Eagle wrote:

Hi.

> So - you've got a central cubelet surrounded by 26 other neighbor cubelets.
> Is the central cubelet (off)set at <2, 2, 2>?
> 

The evaluation point is in the center cubelet of a larger 5x5x5 cube(*) 
of cubelets. The center point of all cubelets is offset by a random-ish 
still within each cubelet as the 'Voronoi' points.

(*) Official POV-Ray does an optimization to calculate only 81 cubelet 
offset vectors & yuqk might later adopt something similar (**). The 
current yuqk crackle is set up for up to 7x7x7 as I wanted to experiment 
with other crackle options at some point.

(**) - I think OK to a high probability & for our crackle pattern, but 
not quite completely "right".

> 
> Recalling some of your other posts - the pattern looks very "cubic" - rather
> than a typical Voronoi pattern.
> 

Allowing for some tuning differences, both the official POV-Ray and yuqk 
methods are cubelets forming a cube based (not pure Voronoi, points 
anywhere implementations), so yes this underlying structure is noticeable.

I suspect you are more noticing yuqk's new ip_strength vector multiplier 
for the offsets, which can be <1.0 for any of the components. At a 
strength of 0.0 the cube of cublets structure is completely on display.

> Also, have you thought about allowing user-defined distance metrics (Euclidean,
> Manhattan, Minkowski, etc.) for generating the underlying pattern?

Sure, the first two are already implemented as metrics 2 and 1 (***). 
I'm not completely sure what you mean by minkowski. I'm familiar with 
minkowski sum and difference with respect to shapes. Some options today 
give a similar look, but the devil is in the details.

(***) The official POV-Ray code both implements a power metric and 
defined the exponent for it by using metrics values other than 1 or 2. I 
thought this ugly, especially given I wanted to add more metrics.

So in yuqk there is an ip_metric 0, which means use a power metric with 
which a new ip_exponent keyword for the exponent to use. This allows 
ip_metric to be extended. I've only added one in (3) for four total in 
0,1,2,3 - but there are plans to try others.

User defined. The ip_form vector offers some control. Each component is 
a +- distance multiplier for the three distance measures taken (The 
three closest points to the evaluation point).

Bill P.

Post a reply to this message

William F Pokorny <ano### [at] anonymousorg> wrote:

> The evaluation point is in the center cubelet of a larger 5x5x5 cube(*)
> of cubelets. The center point of all cubelets is offset by a random-ish
> still within each cubelet as the 'Voronoi' points.
>
> (*) Official POV-Ray does an optimization to calculate only 81 cubelet
> offset vectors & yuqk might later adopt something similar (**). The
> current yuqk crackle is set up for up to 7x7x7 as I wanted to experiment
> with other crackle options at some point.

Right - I forgot about the larger cube dimensions to "catch" the corners.

So, some better thought-out questions are:

How many Voronoi "seeds" are there in the unit cube before you reach the "edge"
and there is a repeat?  Is that / can that be a variable?

What are you doing at the edges/corners to make a space-filling tesselation by
that "unit cube" of Voronoi pattern?  Essentially just a mod (<x, y, z>, N)?



> > Also, have you thought about allowing user-defined distance metrics (Euclidean,
> > Manhattan, Minkowski, etc.) for generating the underlying pattern?
>
> Sure, the first two are already implemented as metrics 2 and 1 (***).
> I'm not completely sure what you mean by minkowski. I'm familiar with
> minkowski sum and difference with respect to shapes. Some options today
> give a similar look, but the devil is in the details.

I guess Minkowski is a generalized form of the first two.
see:
https://www.kdnuggets.com/2023/03/distance-metrics-euclidean-manhattan-minkowski-oh.html

Apparently there's also
Chebyshev
power diagrams - https://en.wikipedia.org/wiki/Power_diagram
weighted Voronoi diagrams -
https://en.wikipedia.org/wiki/Weighted_Voronoi_diagram
https://cs.stackexchange.com/questions/43817/voronoi-diagrams-with-l%E2%88%9E-metric
https://www.researchgate.net/publication/228910426_Visualization_of_Generalized_Voronoi_Diagrams
https://www.researchgate.net/publication/331203691_Computation_of_Compact_Distributions_of_Discrete_Elements

etc

Post a reply to this message

On 11/6/24 13:26, Bald Eagle wrote:
> How many Voronoi "seeds" are there in the unit cube before you reach the "edge"
> and there is a repeat?  Is that / can that be a variable?

The is one seed point per unit cubelet. To do the repeat the overall 
5x5x5 cube gets re-created as the evaluation point moves to another 
centered global cubelet location (tracked with unsigned integers in yuqk).

A trick of the repeat is to wrap in both in the forward direction as 
each x,y,z change - but also behind so the local 'center' see an 
environment valid for the range of supported distances(*).

(*) In yuqk the ip_strength vector lets you use >1.0 vector components 
and exceed the technically supported distances. Same can happen if the 
ip_exponent of the '0' / power ip_metric is <1.0. You still get a result 
usable for effect, but it doesn't look like a standard crackle / Voronoi 
result.

The repeat values are user variables.

The size of the supported cache for cubes of cubelets environments is 
done with build options / environment variables.

To date the max size of the cuble for experimentation is manually hacked 
into the code - I'm not sure what all I might be doing there in the end.

> 
> What are you doing at the edges/corners to make a space-filling tesselation by
> that "unit cube" of Voronoi pattern?  Essentially just a mod (<x, y, z>, N)?

Yes, fmod() (SDL's mod()) gets used to set up both the cubelet locations 
and the repeated cubelets.

With this I think the code is the best answer. In my re-write, I 
flattened the code so there is little (no?) jumping around in the 
overall code base required to see what is going on. Last time I counted, 
yuqk's crackle was roughly 400 lines of code or so. See:

CracklePattern::EvaluateRaw() in source/core/material/pattern.cpp

Bill P.

Post a reply to this message

William F Pokorny <ano### [at] anonymousorg> wrote:

> With this I think the code is the best answer. In my re-write, I
> flattened the code so there is little (no?) jumping around in the
> overall code base required to see what is going on. Last time I counted,
> yuqk's crackle was roughly 400 lines of code or so. See:
>
> CracklePattern::EvaluateRaw() in source/core/material/pattern.cpp

Excellent.
Thanks - I hope I get the opportunity to download that and spend some
uninterrupted time reading and understanding it.

So much to do!

Post a reply to this message

William F Pokorny <ano### [at] anonymousorg> wrote:

> With this I think the code is the best answer. In my re-write, I
> flattened the code so there is little (no?) jumping around in the
> overall code base required to see what is going on. Last time I counted,
> yuqk's crackle was roughly 400 lines of code or so. See:
>
> CracklePattern::EvaluateRaw() in source/core/material/pattern.cpp


It's probably going to take me a bit of time to translate from c++ to something
I can more easily follow.

However, let me offer the following for your consideration:
(inspired by recent scenes, and some long-standing & recurring challenges, plus
you comment: "// TODO. Idea here is maybe return largest fitting spheres, etc...
")

The Appolonian Gasket code returns the largest fitting circles, and in 3D - the
largest fitting spheres.
Perhaps if "crackle" were to be approached from the standpoint of Voronoi and
Appolonian sharing common ground, then the triangles or tetrahedra containing
the inscribed circles or spheres would be more easily generated, and we could
get both for (a little more than) the price of one?

This would be the/a solution to the long-desired ability to pack a region with
non-overlapping circles/spheres.

A similar and directly related pattern would be the Malfatti circles.

Do we presently have the capability to simply "draw the outline" of the Voronoi
cells?

Do we have any idea what would be required to be able to generate the Dual
pattern - the Delaunay triangulation?

- BW

Post a reply to this message

Relevant search results and further reading:

Stephane Laurent (stla)
https://github.com/stla/Apollonius

Inigo Quilez
https://www.shadertoy.com/view/4sd3D7

Voronoi Diagram Research Center
http://voronoi.hanyang.ac.kr/c3_voronoiDiagrams.htm

Need to further look into:
Johnson-Mehl tessellation

Post a reply to this message

On 11/11/24 15:30, Bald Eagle wrote:
> Relevant search results and further reading:
> 
> Stephane Laurent (stla)
> https://github.com/stla/Apollonius
> 
> Inigo Quilez
> https://www.shadertoy.com/view/4sd3D7
> 
> Voronoi Diagram Research Center
> http://voronoi.hanyang.ac.kr/c3_voronoiDiagrams.htm
> 
> Need to further look into:
> Johnson-Mehl tessellation
> 

Thanks for the references. IIRC shadertoy has a distance method to draw 
the outline of cells, but I don't recalled the particulars at the 
moment. I have ideas for how to do it in C++, but I also wonder if in 
yuqk it cannot already 'mostly' be done. Stuff like this why I added the 
ip_raw_return as a yuqk crackle option. Maybe I'll take a 'crack' at it 
in a bit.

I see a path to something like a the Delaunay dual for which performance 
might be acceptable, but due the current limits to the three closest 
measures it would be limited / degenerate in a strict sense.

As for other extensions, some might be worth a try.

With a lot of this voronoi like stuff, 2d is a lot easier than three. 
General, solid 3D solutions likely requires stand alone dedicated code. 
We are working under the constraint that we want a reasonably performant 
pattern in the end - as you know :-).

Bill P.

Post a reply to this message

William F Pokorny <ano### [at] anonymousorg> wrote:

> IIRC shadertoy has a distance method to draw
> the outline of cells, but I don't recalled the particulars at the
> moment. I have ideas for how to do it in C++, but I also wonder if in
> yuqk it cannot already 'mostly' be done. Stuff like this why I added the
> ip_raw_return as a yuqk crackle option. Maybe I'll take a 'crack' at it
> in a bit.

Perhaps you are thinking of this article:
https://iquilezles.org/articles/voronoilines/

> I see a path to something like a the Delaunay dual for which performance
> might be acceptable, but due the current limits to the three closest
> measures it would be limited / degenerate in a strict sense.

I'm not sure where we are with libraries, but I'm pretty sure CGAL has all of
this stuff, plus a bewildering pile more.


> With a lot of this voronoi like stuff, 2d is a lot easier than three.
> General, solid 3D solutions likely requires stand alone dedicated code.
> We are working under the constraint that we want a reasonably performant
> pattern in the end - as you know :-).

Maybe?
I don't really know that that's true, if we exclude the fancy stuff.
A dirt-simple min (distance-of-pixel-from-all-seeds) ought to work just as well
in 3D as it does in 2.
I'll bet that visualizing that with a black-to-clear gradient or media would be
a quick and easy test.

- BW

Post a reply to this message