I've been playing with 'facets' and 'crackle' of late. I've turned up a 
bug (or two) (*).

Documenting now - partly so I can think through what I'm seeing as I write.

The crackle pattern and facets perturbation maintain thread local 
storage so information can be cached in a thread safe way.

The issue, I think, is that that storage is set up to work with one 
crackle and/or facets use per thread and no more.

Once we run >1 of either in the same thread they share the thread local 
storage. This >1 usage per thread happens, for example, when we layer 
textures both based upon crackle.

See the two attached scene files which result in images like those 
attached when things go wrong. (Using v3.7 beta 2 and the not yet 
released yuqk R15 for the renders)

1) Things don't always go wrong. The problem is flaky. Scene renders 
with artifacts often later run cleanly and visa versa. The two scene 
files attached are good at having problems.

2) The v38 scene uses 'repeat <>' and the yuqk one 'ip_strength <>' - 
which twiddles with the strength of the noise used to push the point per 
cube around inside the cube for the pseudo random-ish point set. My 
guess at the moment is these features turn over the thread crackle cache 
more often.

3) I've only seen the buggy results when the text output reports less 
than 100% cache hits. For example:

   Crackle Cache Queries:          960000
   Crackle Cache Hits:             888124 ( 93 percent)

4) The problem seems slightly worse - with more of a render block 
signature - when multiple threads are used. This doesn't really line up
with my best guess as to the issue! At the moment I think this probably 
a secondary bug where maybe the cache is supposed to be cleared at 
render block end, but it isn't, or similar. Might be a secondary thread 
safety issue too.

5) I've not looked at the v3.7 code as yet for these issue(s).

---
I know. The yuqk fork's tearing result looks kinda cool - wish it 
reflected intent... :-)

Bill P.

(*) - There are a couple other minor bugs too in crackle with offset and 
<=0 metric settings patched / fixed in the yuqk fork.

Post a reply to this message

Attachments:
Download 'crackle2_v38.pov.txt' (2 KB) Download 'crackle2_v38_00.jpg' (224 KB) Download 'crackle2_yuqk.pov.txt' (2 KB) Download 'crackle2_yuqk2.jpg' (315 KB)

Preview of image 'crackle2_v38_00.jpg'

Preview of image 'crackle2_yuqk2.jpg'

On 6/8/24 15:12, William F Pokorny wrote:
> The issue, I think, is that that storage is set up to work with one 
> crackle and/or facets use per thread and no more.

OK. I ran an experiment where I forced 100% cache misses in yuqk. I then 
re-ran a collections of scenes running multiple crackle patterns per 
thread. Everything looks OK.

This method of disabling the cache is not optimal as the cache set up 
mechanism is forced to run all the time, but the cached data is never 
used. Still, I ran some timing using the crackle2_v38.pov scene with no 
AA and forced (+a0.0) heavy AA.

p380b2 -> yuqk (R15). Cache active. No AA. Shows yuqk 62% faster(a).
p380b2 -> yuqk (R15). Cache active. With AA. Shows yuqk 34% faster(a).

yuqk (with cache) -> yuqk (all misses). No AA. yuqk is 240% slower.
yuqk (with cache) -> yuqk (all misses). With AA. yuqk is 335% slower.

So... Forcing cache misses and getting no cache benefit is very costly. 
Of course, the results are correct, which matters more.

Suppose, I need to attempt thread local storage which completely 
replaces the current cache mechanism to see where that performance comes 
in. :-(

Unsure if I'll do that work for R15 though. I might just force the cache 
misses for now. It would leave me a release where crackle is working and 
I've not further twiddled with how the the code works.

Ah, and what about facets.

Bill P.

(a) - Is the current yuqk speed up over p380b2 is mostly:

https://news.povray.org/povray.beta-test/thread/%3C663eff9d%241%40news.povray.org%3E/

I'm unsure what else it might be if not.

Post a reply to this message

On 6/9/24 00:21, William F Pokorny wrote:
> Ah, and what about facets.

FWIW. The caching mechanism is simpler (older) for facets. As with 
crackle I experimented some with forcing 100% misses. The slow down in 
the heavy AA case is +195% as opposed to the +335% seen with crackle. 
The difference likely comes down to the overhead for the simpler facets 
cache being smaller. The facets cache comes close to what I wanted to 
try with the crackle cache.

Going to let ideas to rattle around in my head for a while as to what to 
do. ( 1. Limit use to one crackle and one facets use in any given scene. 
2. A cache per crackle/facets use / per thread. 3. ...)

Bill P.

Post a reply to this message

On 10.06.2024 13:51, William F Pokorny wrote:
> On 6/9/24 00:21, William F Pokorny wrote:
>> Ah, and what about facets.
> 
> FWIW. The caching mechanism is simpler (older) for facets. As with 
> crackle I experimented some with forcing 100% misses. The slow down in 
> the heavy AA case is +195% as opposed to the +335% seen with crackle. 
> The difference likely comes down to the overhead for the simpler facets 
> cache being smaller. The facets cache comes close to what I wanted to 
> try with the crackle cache.
> 
> Going to let ideas to rattle around in my head for a while as to what to 
> do. ( 1. Limit use to one crackle and one facets use in any given scene. 
> 2. A cache per crackle/facets use / per thread. 3. ...)

Hi Bill,

the other issue to consider is that while there is no user interface for 
it, in theory multiple renders of the same scene can run in parallel. 
The actual solution to the whole problem is to keep the data needed not 
only thread-local but look carefully at what is actually cached and then 
ideally have it block local (also meaning, as with thread-local storage, 
that the pattern changes with render block size) or even better pixel 
local (no change with block size). To avoid the access to thread-local 
storage, the whole rendering actually could be overhauled (which would 
be good anyway) to move from a recursive to a stack based approach. That 
way the needed local data could be (more easily) passed as argument down 
to patterns ... but expect half a year full time to implement something 
like this.

Thorsten

Post a reply to this message

On 6/11/24 03:43, Thorsten wrote:
> Hi Bill,
> 
> the other issue to consider is that while there is no user interface for 
> it, in theory multiple renders of the same scene can run in parallel. 
> The actual solution to the whole problem is to keep the data needed not 
> only thread-local but look carefully at what is actually cached and then 
> ideally have it block local (also meaning, as with thread-local storage, 
> that the pattern changes with render block size) or even better pixel 
> local (no change with block size). To avoid the access to thread-local 
> storage, the whole rendering actually could be overhauled (which would 
> be good anyway) to move from a recursive to a stack based approach. That 
> way the needed local data could be (more easily) passed as argument down 
> to patterns ... but expect half a year full time to implement something 
> like this.
> 
> Thorsten

Hi Thorsten,

Thank you for your thoughts about the situation.

One thing I've not done is think about all patterns / perturbations / 
shape, thread caching with respect to overlapping in-thread storage use. 
In other words, what other problems like this might be sitting in the 
code today...

On the blocking, you got me thinking one nearer term option with crackle 
and facets might be to track the pattern / perturbation pointers 
themselves alongside the usual cube centers. In cases where we get a 
hit, but the pointers themselves don't match, we'd act like we missed 
and create a new cache entry. Rather than stick that 'overlapping hit' 
entry in the cache, we'd do the distance measures locally and discard 
the entry. Not optimal, more storage for the cache, but it would be 
better than just turning the cache off.

On storage block or pixel local/thread storage. Better I'd say, but so 
long as the patterns might share the storage, I think it still leaves us 
exposed given how the crackle / facets patterns work today.

Overhauling the rendering approach. Yeah, likely due and good, but not 
at all trivial as you say. I'm not myself sure how such a restructuring 
should look in total.

With the solver work I did now 5-6 years ago, I came to the conclusion a 
fused shape/solver approach would be far better given we are 
ray-tracing. See:

https://news.povray.org/povray.programming/thread/%3C5d0f64ff%241%40news.povray.org%3E/

When I think about really implementing that approach, I also start to 
think about how a different approach to parallelism than our block based 
approach could be good. One where we spin up the combined 
shape/solver(s) as processes to which we'd send batches of rays at a 
time and get back batches of intersections... Yeah, I'm practically 
dreaming, but pretty sure that sort of set up would be best for the 
merged uni-variate, polynomial solver/shape approach. How it well that 
structure would work overall - I'm not at all sure. :-)

As a practical near term solution, one thing I want to try is similar to 
what I did with the four ripple/wave value-pattern/normal-perturbation 
re-writes. I dumped already calculated locations for ones always 
calculated on the fly. At the default source location count of 10, the 
hit for not storing the locations was 20% give or take - IIRC.

If I can figure out a way to re-write the crackle and facets at that 
sort of performance hit, I'll probably just dump all the caching / 
thread local storage in total for local stack based storage.

Whether I can accomplish such a re-write - at a performance hit not too 
bad -is an open question at the moment. Not the least for the reason 
it's a chunk of work which well might not work out as a solution in the 
end - so I'm procrastinating.

Bill P.

Post a reply to this message

On 11.06.2024 17:39, William F Pokorny wrote:
> When I think about really implementing that approach, I also start to 
> think about how a different approach to parallelism than our block based 
> approach could be good. One where we spin up the combined 
> shape/solver(s) as processes to which we'd send batches of rays at a 
> time and get back batches of intersections... Yeah, I'm practically 
> dreaming, but pretty sure that sort of set up would be best for the 
> merged uni-variate, polynomial solver/shape approach. How it well that 
> structure would work overall - I'm not at all sure. 😄

Well, yes, an intersection based approach would probably offer the most 
potential performance on a shared memory system. You would also end up 
with a stack-based approach automatically that way. However, you hit 
sort of a wall once you get to the really big multi-die systems like 
Epyc and newer Xeons because they only share the last level cache with 
all cores. So in the end the best performance probably hides somewhere 
in a hybrid of the two with blocks still offering some benefit for large 
multi-core systems. That is, of course, assuming the ray order doesn't 
disrupt first and second level caches too much. It is impossible to 
predict the complexity with modern CPU, I think.

The benefit would be that the "texturing" would become a completely 
separate task, and could actually be done (sans reflection and 
refraction) after tracing, which, if nothing else, would lead to a cool 
looking render preview. The other effect would be that at least bounding 
optimisations and mesh intersection testing could be done on a GPU.

Yet another benefit you get from separating the tracing and the 
texturing is that you end up with a sort of frame buffer that contains 
object data. An idea I never pursued to the end 20 or so years ago was 
that this gives rise to the ability to edit a ray-traced scene on the 
fly because you have access to the objects making up an individual pixel 
and can separate objects in and out of the scene as long as the camera 
doesn't move.

Thorsten

Post a reply to this message

On 6/11/24 14:17, Thorsten wrote:
> It is impossible to predict the complexity with modern CPU, I think.

I agree. Today's hardware optimizations make performance tuning a tough 
trick - and make questionable a number of "rules of thumb" about which 
algorithms perform best.

> 
> The benefit would be that the "texturing" would become a completely 
> separate task, and could actually be done (sans reflection and 
> refraction) after tracing, which, if nothing else, would lead to a cool 
> looking render preview. The other effect would be that at least bounding 
> optimisations and mesh intersection testing could be done on a GPU.
> 
> Yet another benefit you get from separating the tracing and the 
> texturing is that you end up with a sort of frame buffer that contains 
> object data. An idea I never pursued to the end 20 or so years ago was 
> that this gives rise to the ability to edit a ray-traced scene on the 
> fly because you have access to the objects making up an individual pixel 
> and can separate objects in and out of the scene as long as the camera 
> doesn't move.

Cool ideas. :-) I can see how some parts might work, but far from all of 
it.

Our ray tracing and texturing is today tangled in places (adc bailout, 
filtering/transparency, media, object modifiers). There is too how to 
handle anti-aliasing (AA) / camera focal blur.

Though our 'AA' approach today is expensive(a), it's a strength with 
respect to 'true result' that each sample ray considers the scene - 
including texturing - alongside all the ray tracing / branching in total.

Bill P.

(a) - With respect to performance, on my 'try it someday' list are 
cheaper AA / focal blur modes where the rays beyond some 'sampling 
depth/count' would terminate at a much shallower max_trace_level/sample 
count(*). Or maybe we gradually reduce the trace depth in opposition to 
the AA/blur sampling 'depth'. Results would be less true, but I 
'suspect' they'd often look good as a rule. (There is a tradeoff buried 
in the idea as the less accurate results due shallower ray trace depth 
would sometimes itself trigger additional sampling - and sometimes not 
where we would otherwise have shot more rays.)

(*) - Yes! I made trying the idea harder by implementing the forced min 
sampling AA in yuqk.

Post a reply to this message

On 6/8/24 15:12, William F Pokorny wrote:
> The crackle pattern and facets perturbation maintain thread local 
> storage so information can be cached in a thread safe way.

Note too:

https://stackoverflow.com/questions/35985960/c-why-is-boosthash-combine-the-best-way-to-combine-hash-values

---
In working to clean up and commit my last updates, I ran across a TODO 
comment I'd added to friend std::size_t hash_value() in cracklecache.h 
about the initial seed value of 0 - which bothers me. I did a quick 
search this morning to look for rumblings about boost:combine().

Other issues aside. It might be our crackle caching mechanism is less 
effective than it could be.

Bill P.

Post a reply to this message

Minimally hijacking this thread to just post an FYI which may be helpful in some
of your source-code optimizing work.

https://iquilezles.org/articles/noacos/

I haven't looked under the hood in a while to see how we're handling stuff like
this, but it seems like it could provide some performance increases, and for the
basis for some macros / include files.

- BW

Post a reply to this message

On 6/14/24 09:49, Bald Eagle wrote:
> Minimally hijacking this thread to just post an FYI which may be helpful in some
> of your source-code optimizing work.
> 
> https://iquilezles.org/articles/noacos/

Thanks. Been some years, but I read that article at some point in the 
past! Good to be reminded of it.

Bill P.

Post a reply to this message

On 6/8/24 15:12, William F Pokorny wrote:
> I've been playing with 'facets' and 'crackle' of late. I've turned up a 
> bug (or two) (*).
> 
> Documenting now - partly so I can think through what I'm seeing as I write.
> 
> The crackle pattern and facets perturbation maintain thread local 
> storage so information can be cached in a thread safe way.
> 
> The issue, I think, is that that storage is set up to work with one 
> crackle and/or facets use per thread and no more.
> 
> Once we run >1 of either in the same thread they share the thread local 
> storage. This >1 usage per thread happens, for example, when we layer 
> textures both based upon crackle

An update for those who might follow at some later time...

I think I've finished the re-write of the crackle pattern with a simpler 
fixed size, per thread cache (for other than ip_solid on) which tracks 
the pattern along with the center cube location. To be released in 
yuqk(R16).

In testing the new code I discovered the 'repeat' feature of v3.8 beta 2 
has a self cache collision issue at the origin in addition to the cache 
collision issues of multiple crackle patterns within a thread.

For the attached images the scene set up is a large disc with a hole. 
Within the hold there is a second smaller disc which doesn't quite fill 
the hole. The rose color is the background seen through a gap. The outer 
disc crackle pattern is scaled very small, but is otherwise the default 
crackle.

The repeat, self, cache collision bug of v3.8 beta 2 is shown in the 
upper left. I didn't chase a fix.

The image in the upper right is the version of yuqk I released in July 
(R15) where, by hack, I disabled the crackle caching. The crackle 
implementation is still what is in V3.8 beta 2. The repeat works as I 
thin clipka intended!

In the lower left showing my development yuqk re-write, crackle repeat 
feature result. Yes, its different than v3.8. I didn't like the 
complexity and cost of the v3.8 implementation and went with something 
simpler (I avoided the self cache repeat bug by chance...). With yuqk 
(R16) the pattern flipping would be done with warp { repeat }(s).

The lower right is there just to fill out the 4x4! It shows the use of 
a, new to yuqk, crackle ip_seed feature to change the inner disc's 
ip_solid result. I added ip_seed to make it easier to get different 
crackle looks on different shapes otherwise using the same crackle 
pattern specification.

Bill P.


Aside 1: What is the repeated pattern on the outer disc seen in the v3.8 
top row? It's a side effect of the more limited accuracy of the hashing 
mechanism used to create the per cube point offsets in the v3.8 code. I 
believe I changed things so this type of artifact is much less likely 
with yuqk.

Aside 2 (*): Why is yuqk's lower left image a little brighter than 
v3.8s? One of the aspects of the traditional POV-Ray crackle cube point 
offsets is that they work from a starting corner. This produces a result 
which, to my eye, creates too many pinched regions in the pattern's 
result. With the yuqk re-write the offsets are done from the cube center 
in a +-(0.0 to 0.49) way. Less pinching, more white area, brighter image...

(*) - This yuqk change unexpectedly created a sampling issue where, when 
scaling the crackle pattern very small, the crackle's inner cube nature 
becomes more quickly apparent when anti-aliasing is off. It's a kind of 
harmonic of rays with the underlying, less pinched crackle pattern. It's 
not an issue when AA is used.

Post a reply to this message

Attachments:
Download 'v38b2_repeat_at_origin_bug.pov.txt' (1 KB) Download 'v38_repeat_at_origin_bug.png' (358 KB)

Preview of image 'v38_repeat_at_origin_bug.png'

On 10/30/24 02:19, William F Pokorny wrote:
> In the lower left showing my development yuqk re-write, crackle repeat 
> feature result. Yes, its different than v3.8. I didn't like the 
> complexity and cost of the v3.8 implementation and went with something 
> simpler (I avoided the self cache repeat bug by chance...). With yuqk 
> (R16) the pattern flipping would be done with warp { repeat }(s).

In the end, after I played a bit, I didn't much like my alternate repeat 
implementation in yuqk...

Took me a while, but I think I've gotten to what clipka was aiming for 
in his v3.8 crackle repeat feature. A <3,3,0> repeat is shown in the 
center of the attached image.

Bill P.

Post a reply to this message

Attachments:
Download 'yuqk_crackle_repeat.jpg' (122 KB)

Preview of image 'yuqk_crackle_repeat.jpg'

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

> Took me a while, but I think I've gotten to what clipka was aiming for
> in his v3.8 crackle repeat feature. A <3,3,0> repeat is shown in the
> center of the attached image.

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!

- BW

Post a reply to this message

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

On 11/12/24 03:17, William F Pokorny wrote:
> 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 didn't spend much time on it, but the top of the attached image shows 
outlines as a pigment just slightly red (negative) by allowing raw value 
returns after changing ip_form to: 'ip_form <-0.1,0.08,0> - the default 
is <-1,1,0>.

The bottom of the image is an isosurface where a cylindrical shell is 
intersected with a similar crackle pattern in space. No attempt wrap the 
cylinder - just punching out a thin part of the crackle cell outlines.

The isosurface functions are:

// yuqk required
#declare Fn00 = function (x,y,z) {
     f_planar(f_cylinder(x,y,z,0.9),0.01,1)
}
#declare FnCrk = function {
     pattern {
         crackle
         ip_form <-0.1,0.097,0>
         ip_strength <0.25,0.25,0.25>
         ip_raw_return
         raw_wave
         translate <0,0,0.25>
         scale 1/5
     }
}
#declare Fn01 = function (x,y,z) { max(Fn00(x,y,z),FnCrk(x,y,z)) }

Yes, The outline / cell-walls vary some due differences in gradients - 
but more due how the slices catch the cell wall. For practical purposes, 
expect an approach like this often OK for cell outlines.

Bill P.

Post a reply to this message

Attachments:
Download 'be_crk.jpg' (124 KB)

Preview of image 'be_crk.jpg'

On 11/17/24 06:51, William F Pokorny wrote:
> No attempt wrap the cylinder - just punching out a thin part of the 
> crackle cell outlines.

Got some coffee in me and gave the cylindrical warp a go. The crackle 
function becomes:

#declare FnCrk = function {
     pattern {
         crackle
         ip_form <-0.1,0.080,0>
         ip_strength <0.25,0.25,0.25>
         ip_repeat <5,0,0>
         ip_raw_return
         raw_wave
         scale 1/5
         scale <1/5,1,1>
         warp { cylindrical }
     }
}

(And I fattened up the cell walls for a better gradient)

Aside: I think there is a slight stretch in the wrap because the warp{} 
mapping warps often seems to want radian measures - 'scale <1/tau,1,1>' 
for best geometric mapping.

Anyhow. Image attached.

Bill P.

Post a reply to this message

Attachments:
Download 'tmpiso_wrp.png' (178 KB)

Preview of image 'tmpiso_wrp.png'

On 11/17/24 07:53, William F Pokorny wrote:
> Got some coffee in me and gave the cylindrical warp a go.

While playing, created attached images. The right one by accident...

Last part of the function { pattern {crackle ...} } used was:

         warp {
             it_amount <1/3,1/3,1/3>
             it_omega 0.87 it_lambda 4.7 it_scale 1/5
         }
         scale <1/6,1,1>
         warp { cylindrical }
         warp { spherical }    // Oops

Aiming again for shapes that are not really shapes in a usual way. 
Suppose yesbird's recent gravity toy post in the same vein.

The isosurface gradient set low (1.3), accuracy really rough at 0.05, 
but with isosurface jitter (jittering within accuracy range) on - and 
aggressive AA (antialias_min_depth=2 +r4) sampling. yuqk only features 
are involved.

Bill P.

Post a reply to this message

Attachments:
Download 'morecracks.jpg' (251 KB)

Preview of image 'morecracks.jpg'

William F Pokorny <ano### [at] anonymousorg> wrote:
> On 11/17/24 06:51, William F Pokorny wrote:
> > No attempt wrap the cylinder - just punching out a thin part of the
> > crackle cell outlines.

Huh.  And what happens if you do the same sort of thing with something like the
Stanford bunny?

- BW

Post a reply to this message

On 11/17/24 21:52, Bald Eagle wrote:
> William F Pokorny <ano### [at] anonymousorg> wrote:
>> On 11/17/24 06:51, William F Pokorny wrote:
>>> No attempt wrap the cylinder - just punching out a thin part of the
>>> crackle cell outlines.
> 
> Huh.  And what happens if you do the same sort of thing with something like the
> Stanford bunny?
> 

If the aim is seeing the outlines rather than creating an isosurface 
shape from them, the quick thing would be to create a pigment from the 
crackle pattern set up to show outlines - the parts of the pattern not 
outlines would be set transparent. Ignoring that we can define an inside 
vector for a well formed / closed mesh, a mesh surface is already 
infinitely thin for the purposes of sampling.

If you want to play with isosurfaces based upon a mesh, one of the 
techniques to turn them into value fields would be the up front 
approach. There are a couple SDL only ones. A method I posted in the mid 
to late 2000s and one Sam B posted in the early 2010s. The yuqk fork has 
hard_object{} and soft_object{} inbuilt features for turning shapes into 
value fields / patterns.

The recent filling a shape with random noise approach might work for a 
noisier result. There is too a way to pre-sample a shapes interior 
saving the result as a df3 file which can then be used as a value 
pattern suitable for an isosurface.

A straight intersection with a mesh having a clean inside region or any 
object with an defined inside is an option too. The gradients will be 
bad and the result, visually, less interesting as the outer layer of 
cell outlines will hide everything to the interior.

Bill P.

Aside: I've wondered some what an intersection of two crackle value 
pattern intersected might look like - where one crackle changes ip_seed, 
is rotated or scaled differently such that the cells walls intersect 
sparsely.

With the ip_strength option set up asymmetrically we might also be able 
to define certain patterns or shapes. One crackle ip_repeat, repeating 
differently than the other where both have identical ip_seed, seeds...

Post a reply to this message