next »

[Ordnas]

Without looking at the benchmark, doing a Reseize and the subscript essentially you are doing two assignments (default constructor and copy assignment then), instead of a push back with a single assigment.

[Deckhead]

Without looking at the benchmark, doing a Reseize and the subscript essentially you are doing two assignments (default constructor and copy assignment then), instead of a push back with a single assigment.

Yes, but what was interesting to find is that even with a vector of int. I would have thought that default initialisation of an int would be negligible.

[Ordnas]

Negligible not really with 1000000 elements, if you consider size of int as 4 bytes, you are allocating 4 bytes x 1000000 elements = 4000000 bytes, which in megabyte is 4 MB, which is a lot. The CPU gets "only" 64 bytes if data is not in cache, so in that case there will be a lot of cache misses, the double initialization does an exponential cost there. Anyway looking at the benchmark, the cost is quite a lot comparing the other way, I do not know how the benchmark simulates a real machine (maybe a CPU with very low cache memory and just L1 and L2).

[Deckhead]

I believe it compiles and executes within their framework n times. So not simulated.

[gimymblert]

Just refreshing some math insecurity:
For all intent and purpose, when you read computer stuff and there is an integral, it's just GENERALLY a sum of all sampled delta of the given function?

[qMopey]

Sum of sampled data is an approximation of the integral. Samples are a discretization.

[gimymblert]

But is it just sum of samples or (sample*deltaBetweenSample)?

[Daid]

From an engineering standpoint, yes. From a science point, no.

The math/science integral makes the deltaBetweenSample infinity small, and the samples with infinite precision.


In the real world/engineering, you cannot sample that fast, and not with that precision, and you lose accuracy due to floating point precision (or integer conversion). Which means it's a approximation of the integral.


Simple example, the math/science integral of sin(x) between x=0 and x=2*pi is zero. But if you try this in practice/engineering, you will end up with some rounding errors, sampling interval issues, etc. And thus you will end up close to zero, but not actual zero. So, really zero, or approximation of zero.

[gimymblert]

You mean that the two (approximate) sampling method I thought up ( (sum of samples) and (sample*deltaBetweenSample)) are equivalent?

[Daid]

You mean that the two (approximate) sampling method I thought up ( (sum of samples) and (sample*deltaBetweenSample)) are equivalent?

Those where two methods? I thought they where a single method, as you generally sum all samples, and if your sampling interval isn't constant then you multiple with the delta time between the previous sample before you sum it.


But I just noticed something, with deltaBetweenSample, I assumed it was a time delta, if not, and it's a sample delta, then... that doesn't make any sense to me, multiplying an absolute value with a relative value of the same base data...


Maybe you have a better example of what you are trying to do? As this becomes very abstract and fuzzy very fast.

[BorisTheBrave]

It's the second one, you must do a sum of sample(x)*deltaBetweenSample to approximate the integral of sample(x).

It should be obvious if you think about it. Suppose you are sampling a constant function. You'd expect you'd get the same answer regardless of the delta you pick. Your first suggestion doesn't have that property.

To be even more precise (as Daid seems a bit confused over your terminology), to approximate the integral of a function f between A and B, using slices of size delta, you'd do

Code:

result = 0
for(x=A; x<B; x+=delta)
  result += f(x) * delta

Using a smaller value of delta gives more accurate answers.

This isn't the only way to approximate an integral, and it is the least accurate, but it is the simplest method. Further reading: https://en.wikipedia.org/wiki/Numerical_integration

[qMopey]

Also note that: a * dt + b * dt is equal to dt * (a + b). However, if you sum too many floating point values before multiplying by dt, you may lose more precision than anticipated.

[gimymblert]

Thanks to all!

[gimymblert]

Does someone know an algorithm that find roots of 2d cubic bezier curve (for shader) without using acos and cos?
The one I found is this one
https://www.particleincell.com/2013/cubic-line-intersection/

Also I'm always in the range of 0-1 in x and 0-infinite in y, what are the implication?

[gimymblert]

Okay I have a good one, I want a pointer if you don't know an answer lol:

You know the problem with car a going a speed b and car b going at speed a? when will a will overtake B?

I kinda have a similar problem.

Imagine you have circle, on this circle you have a point A at an arbitrary angle, and another point B at another angle. Point A move by jump (teleport) of size SA and point B move by jump of size SB, when will A and B on the same position?

I feel this should be simple but brain can't handle it yet

Edit:
shot! I knew it look similar, it's basically line equations intersection, A+t1*SA = B+t2*SB

here is the truth, I actually want to intercept a point in a modulo grid, which mean it's equivalent to a torus. But the problem can be projected on 1d space, so we project A and B on the exit edge using the direction of A, we use the slope of the line from A and find the delta at which the line will progress in the edge, B can be considered to move at edge interval. Then it's a matter to do trigonometry to find the distance in the virtual grid. Pushing a bit more it should be possible to know how many intersection with B for a given "budget" of jump.

does that seem correct?

Edit2
should probably look at line algorithm like bresenham ....

edit3
well not useful for the initial problem I need to compute test it.

[gimymblert]

just for information, I have this problem that should be simple, how much would I pay someone to actually translate it into a formula for me:
https://forum.unity.com/threads/infinite-parallax-hair-volume-using-wrapping-grid-tracing-attempt.593233/

That is the solved intersection with thickness

[BorisTheBrave]

just for information, I have this problem that should be simple, how much would I pay someone to actually translate it into a formula for me:
https://forum.unity.com/threads/infinite-parallax-hair-volume-using-wrapping-grid-tracing-attempt.593233/

That is the solved intersection with thickness

I also find the author a little hard to follow, but if I understood correctly, his key idea is that raycasting against an infinite array of hairs is the same as raycasting a single hair, but wrapping the ray around the cell.

This insight is true, but I don't think it actually helps any computation. You end up writing code like Bresenham's either way. Certainly, the post doesn't seem to clarify how it helps. (I swear I once saw a better solution on stack overflow, but it eludes me now).

Here's a puzzle based on the same concept.

. Like your earlier post, the trick is to turn wrapping space (toroidal) into infinite real space. I've never seen a use in going the other way around.

[gimymblert]

The author is me lol, I'm having more and more difficulty tackling these things. The idea is to get hair impact in a single compute(no recursion), that is given a ray slopes and position get the first depth, due to the math the graphical representation will be equivalent to an infinite volume of hair, and you can discard any hair that is return beyond a threshold (assuming convex). Which should enable a fake shader volume trick like the parallax function I tried on another thread (ie use the UV to bend direction of hairs).

The key realization is that:
1. hair are approximate as parallels, you can then turn that into a 2d problem by taking the cross section.
2. the 2d problem can be turned into a 1d problem, using slopes to compute a delta. So it become an interval overlap problem.
3. The line is wrapping, basically a circle topologically, so it's equivalent to the overlap of the clock needles or planet alignment (that is when big needle move a certain distance (in our case the wrapping unit) the small needle advance at another rate, given the two rate, when will they overlap, here when will have a hit, with in this case discrete movement instead of continuous like clocks and planets).

Bresham is basically recursing over a gris, I'm not. I (try to) compute analytically the hit and derive the distance from the wrapped space to the infinite unwrapped space. Ie I gave the ray as an input, I get the hit depth as an output (if there is a hit, it's the smallest period overlap).

Except I'm incompetent, even though I basically explained everything and translating that seems intuitively it should be trivial ...

And that's before even trying to solve the same but with wrapping helix ... :cry:

In the post on unity forums I basically try to deconstruct teh step by increasing the complexity, next is supposed to add variation of ray slopes (since right now I demonstrate the idea with guaranteed hits, which mean only the slope that lead to a hit on the first vertical, which is a subset of all slopes) and variation of ray positions (which is especially where synchrony problem might arise, until now i'm cheating by using the starting position at zero toward the position 1, but since it wraps it's the same point really, so of course it hits...)

EDIT:
Another way to look at the problem is to consider it like a collision, given two elements moving at different rates in discrete steps (the ray having a given arbitrary steps and the hair having a wrapping unit steps), when will they collide, if they collide.

First I'm trying to solve it with ideal points with no size, then with one element having a size (hair thickness), then trying to see if it works with "round hair" collision, then helicoidal strands. And as a bonus if we can had variety by having the visual grid not being in sync with the calculated grid, so we have effectively the equivalent position of strand changing at given rate too, to produce pseudo random shuffling and have less artficial alignment.

The goal is that I can trace hair even on low end gpu, and given the formula might end up cheap, we can trace multiple infinite volume with various parameters to get variety at a cheap cost (basically sorting per volume instead of per strand).

[Crimsontide]

Maybe I'm misunderstanding you, but I don't think that sort of algorithm would work.

Tracing hair is difficult (like grass) because at most scales many strands contribute to the color of a given pixel.  It isn't which strand is hit, its how many, how much coverage, at what angles, and how does the inter-reflection of light affect the final color.

Ray tracing is only an approximation, decent for large surfaces but it breaks down on micro surfaces (hence the use of BRDF and similar).  Cone tracing is really what you want, but its prohibitively expensive.

Using a texture-space/UV space trace, or straight forward rendering, you're still going to have to model the surface of the hair.  I'd just as soon use a BRDF and not worry about the trace.  I imagine you'll get better results and performance that way.

Even if you managed to create a function that analytically performs cone tracing over a UV/texture space projection, summing/calculating the resulting coverage, angle, etc... for a given hair type/thickness/color/texture it would look very similar in the end (I imagine) to a BRDF.

I guess what you could do is use a cone tracing over hairs given a hair thickness/color/texture/etc... and create a BRDF 'offline' which could then be used render convincing hair.  But I just can't see any sense in doing that in real time.

[gimymblert]

It's an approximation that only care about depth, I don't care about these concern for now. What I need is the volume parallax for certain thing, ie no micro details and BRDF.
It's analytical so there is no recursion (ie no stepping through the volume, it's basically a single primitive intersection that have visual recurrence property due to wrapping).

If I can get to work, you will see what effect I can extract from it (on top of pgc benefit).