# Infinite parallax hair volume using wrapping grid tracing (attempt)

Discussion in 'Shaders' started by neoshaman, Dec 5, 2018.

1. ### neoshaman

Joined:
Feb 11, 2011
Posts:
4,239
There is this thing I need to get done, it's an extension and end goal of experiment with relief function shader. Basically I want to trace in fragment shader hair that had parallax property. Since I'm having problem with simple math due to a past burn out, my brain blanking out on thing I should know, I figure out that chronicling the attempt publicly and verbalizing it to other people might help me get thing fall into place, and maybe some people might be interested and drop some clue.

Hair rendering is notoriously hard and costly, due to the high number of occluded elements, which may or not contribute to the final image. I propose a technique that use a simplified model of hair, as parallel line in an extruded grid, and a mathematical representation that would allow to find the first visible intersection to a line without having to pay the cost for the occluded many, and potentially infer how many hair has been traversed with the same operation at the exit of the volume.

The main idea is to realize that the simplified hair is "coherent", ie all are in the same position in the grid (idea to shuffle it will be explored later) and therefore all cells are indistinguishable from another, they can be superposed. This mean that a ray entering at one cell boundary will have a predictable trajectory wrapping in the superposed space. The challenge will be to figure out the math of intersection in that wrapping space, which would be the equivalent of determining occlusion in one hit. To simplify further, we will move the hair position to the origin corner of the cell so it's 0,0. We will adapt the DDA algorithm to get to that result.
Further analysis show we can simplified the problem more by simply projecting to 2d position as it's extruded, therefore we can align the grid with one axis, then project to 1d, where it become a problem similar to the " how many timed clock hand overlap in a day" or planetary alignment puzzle
https://www.mathpages.com/home/kmath161/kmath161.htm

The end goal is to have a version of the shader that can also represent curly hair (intersection with helix line).

Given I found all the mathematical foundation it should have been trivial from there ... I'll add image later to illustrate the technique.

AlanMattano likes this.
2. ### neoshaman

Joined:
Feb 11, 2011
Posts:
4,239
Oups, end of years + a loss in the family + a new occupation didn't make me live up to those statement. Slowly coming back to it...

a. the basic
I was trying to model afro textured hair cut, but wasn't satisfied with the result. Afro textured is inherently volumetric and I wanted to reflect that fact.
There is multiple way to implement that idea but my first instinct was to try a parallax shader, to model the superposition of strand, basically representing multiple layer displaced virtually by the view vector.

Going through the math I realized there was opportunity to expand on that. But let's review the math of layer parallax (I hope there is no mistake, I'm not the most competent mathematician here).

Let's consider an UV surface, with layer at regular interval d, and a view normal vector v. Let's simplify the representation of a 2d cross section. Due to thales theorem, we can see than the offset is a ratio k of distance to the plane. If we set d=1 then k<1 because v is a unit vector as such k is equivalent to the depth when v is looking from the top.

Once we see the result we understand that the sample are regularly space in a predictable way, we might be able to derive mathematically an intersection with a fixed position, and skip sampling multiple time an occlusion assuming it happen at the same regular interval.

If we assume hair strands are regularly space line in uv space, we can approximate the hair volume occlusion mathematically. While strands have thickness, we will assume they are mathematical line and try to find the basis of the math from there.

The insight is that multiple plane at the same distance is equivalent to a wrapping plane, also UV wrap around the 0-1 range. SO if we can port the math to wrapping space ... it would be equivalent to tracing through an infinite regular grid. Also since we have wrapping, we can realize it's equivalent to looping, stepping at regular interval is therefore equivalent to the clock needle overlap problem.

The other trick is to realize that the support (the triangle face) can bias the visual such has the straight line become curved while the math stay the same (operating on UV space not in visual space). Of course it has limitation (such has curving beyond the horizon wouldn't work, as the ray would need to intersect twice the same strand.

It's not really a new idea, some people have experimented with modulo space, though I need to find one that give interesting result for hair strands occlusion.

I'll explore that next time.

3. ### neoshaman

Joined:
Feb 11, 2011
Posts:
4,239
Wrapping the space

First let’s assume the hair strands are all situated at position 1 in x in all layers, and the view rays start at position 0 in x on the first. We will trace rays through all layers such as they intercept the strand position at each layer.

If we trace back to the first layer, every intersections with a layer before hitting a strand position, we can observe a pattern. Because the ray slope is constant, and each layer distance is the same, the projected intersection to the first layer are equidistant. We can see there is a correlation between the depth of the layer, where the ray hit the strand is, and the number of projected intersection. Therefore the intersections number give us the depth. We then know we can just divide the distance, between the ray x origin and the strand x position, by the number of intersection to get the depth.

The corollary is that we can guess which depth a strand is hit, by looking at the number of step it takes, which is a function of the slope. Figuring the slope at the first layer give you the delta of the step, you then just to divide the distance. Wrapping horizontally is similar, the difference is that the number of step happen vertically. But really we just need to observe, that the distance to the targeted strand horizontally, is a multiple of the distance to the reference strand on the first later.

Those simplified observation are here to demonstrate how we can infer positions of virtual strands (ie strand beyond the first layer and horizontal wrapping), based on the rays slopes vs the reference strand position, in a kind of wrapping trigonometry. And also how we can basicaly simplify the math to a linear convergence using division or modulo.

However to generalize further, we still need to demonstrate how it works when we start changing the slopes and the offset of the ray, instead of assuming all ray point to a strand from the zero position. And we need to verify when the math allow convergence to a virtual position of a strands and when it does not. Doing so would allow us to guess the first hit in a virtual volume.

Once we have done that, we have effectively found a way to trace an infinite volume of primitive, however hair has thickness, we will need to find a way to intercept more than an infinitely small position. Ideally we would also generalized to different kind of wrapping shape, such has helix, which would allow us to emulate curly hair.

4. ### neoshaman

Joined:
Feb 11, 2011
Posts:
4,239
Up until we cheated by locking the ray slopes and position to the a single place into the receiving surface and only to slopes guaranteed to hit a target point. It was done to demonstrate how it would translate to a 1d problem of interval overlapping. But now we need to introduce two new parameter:
1. arbitrary slopes
2. arbitrary starting position of the ray.

1. variation of slopes
As we have shown earlier, the slope of the ray translate into discrete steps, with same size, on the "surface", and there is collision when they are basically a multiple of the wrapping size, and that multiple give you the depth or distance of the collision within the infinite space. But what happen when we have an arbitrary slope, that give us an arbitrary step, and we want to find the multiple to the wrapping size, does that multiple even exist?

Basically we can reformulate the problem as beat synchronicity, let say you have two beat, one that goes on twos and the other on three, when will the beat pulse together? In this simple set up it's easy, they will be synchrone every 6 beats, that's the "collision depth". But what does that mean in mathematical form, how can we generalize it? seems simple though isn't it?

2. variation of position
Up until we cheated (again), by fixing the position at the start we made it easier, since the space is wrapping the starting and the target are basically the same position, and since we normalized the wrapping distance, it also mean we had neat number to play with. But what happen when we move the ray to anywhere within the wrap space, as it should happen in a real case? Well let's see the beat analogy again, let's say we have two beat on twos, but one start half way after the first beat, they will never be in sync again, ie similar beat with an offset, they will never pulse, can beat we translate that into mathematical form, to check that two beat will never converge to the same time?

I use beat analogy, but we can basically use other one, since the space is wrapping, we can also see the surface "segment" as a circle, since we have stuff moving at different rate on that circle is analogous to a clock needles, which mean we can relate to the clock needle superposition problem (itself analogous to the planet alignement problem), with the added complication that we are moving by "discrete steps" rather than a "continuous rate".

So basically it's this, given two elements moving at discrete step, can they overlap and when? The minimal distance will gave us the depth of the collision, and probably we can define the periodicity of the collision after that.

So here is where my competence end, I need to translate those insight into mathematical form to resolve.

5. ### neoshaman

Joined:
Feb 11, 2011
Posts:
4,239
Up until now I showed that the problem could express as a 1d line with interval overlapping. But since the space is wrapping on itself, that is the first line and teh last line is basically the same, instead of an infinite line with repeated "beat", we can represent it as a circle with interval stop around it: In this example the black tick overshoot the target after one wrap, the red tick is the resulting position of overshooting. We need to calculate how many wrap before it can actually overlap the target.

Using this representation allow us to find equivalence, it looks like a clock, it also look like circular planet orbital. Turns out we can probably get inspire by that to find mathematical equivalence. If you think a bit about it, it turns out that's a similar problem than planets alignment, or the clock needle superposition riddle. The hair target

Let's use planetary alignment.

We find this googling on the net:
https://www.mathpages.com/home/kmath161/kmath161.htm

which gave us this:
If it's correct we have this:
let say we have two point moving at two rate,
- the position of each point = rate * t.
- Therefore position1 = position2 it mean that rate1 * t = rate2 * t,
- that is (rate1-rate2) * t .
What's missing is the bigger period in which rate1 and rate2 are inscribed,
- we can get it by having rate1 * rate2.
- So rate1 and rate2 are sync for t= k(rate1*rate2) / (rate1 -rate2) with k being the number of period.

However we have a specific case where rate2 = the normalized wraping size, rate2 = 1, for k = 1 we have t = rate1 / (rate1-1).

But we only assume no rate as an offset,
- so if we check with offset we have position1+ offset = position2,
- which translate (rate1 *t) +offset = rate2 *t
- which lead to t * (rate1 - rate2) + offset
and we can probably write the final result as t = k(rate1*rate2) / (rate1-rate2+offset)
which finalized as
t = k(rate1) / (rate1+offset-1) which has no solution when rate1+offset = 1

Probably? Any mistake?

Extruding 2d intersections points
More math (help given by someone else in another forum), this would help us define the line in 3d, since hair is axis align with the support geometry UV space (the deformation/orientation of that support geometry being the approximation of the hair direction) once we have the virtual depth, we can compute the virtual position as a function of the origin and the slope.

Jittering the depth alignment
Anyway, we can have some more insight, we have assumed the wrapping itself was fixed, if the wrapping windows itself move, it's equivalent to find 3 planets alignment ... What's the use? well if we stay in the two beat system, we get all hair perfectly aligned in regular interval, if the wrapping move too, we can jitter the depth predictably by multiplying by clever number.

However this isn't that easy, if we go back to the 2d representation, let say we have an angle where the beat is bigger than the wrapping size, we would wrap horizontally first, so the jittering position will not match a ray sampling the nearby cells position, because the order of traversal would matter, so we need to define the wrapping displacement as a 2d problem. Which I haven't figure out yet.

More works is needed
Up until then we have assume mathematical object, ie point that have no size. In order to properly compute hair, we need thickness, we need to find a way to detect when our beat is within a distance of the target to get a hit, not just right on the target. Once we can do that, we can probably extend to a 3d volume cross section (the circle shape of the hair), the problem still being finding a single point, so the extrusion should remain the same.

We also need to find a way to intersect helicoidal shape, they are too repeating, so a wrapping function is fine, the challenge is that there isn't cheap formula to intersect sin wave, which is needed to get the helix. The end game of this exercice, infinite field of infinite helix shape!

NOTE:
If we were to just do infinite straight hair, probably a beat base solution is overkill, on shadertoy, there is already wrapping tracing shader, we could just extend them to get hair approximation.

Last edited: Jul 12, 2019
Invertex likes this.

Joined:
Feb 11, 2011
Posts:
4,239
7. ### neoshaman

Joined:
Feb 11, 2011
Posts:
4,239
Doing recursive interception on wrapping helix is hard, the equation of the helix is x = r cos t, y =r sin t, z=a t ... all those sin and cos create problem, there is no simple equation to intercept them. And it's a curve that is not convex, it's hard to find simplification.

I try simplifying by boxing the shape abusing the inherent symmetry, and then approximate it with a x² curves that we can reliably intercept but I wasn't able to see anything that will put me closer to the goal.

Up until I decided to step back and instead of trying to intercept the coil, intercept the support cylinder, it can be reduce to a 2D problem of line circle intersection, which doesn't have any sin or cos, but then that lead to a realization that the cylinder unroll into a 2D wrapping space where the coile is basically just the diagonal line ...

Now the idea is to try and translate the cylinder intersection equation into an equation of all potential wrapping hit points, given that all points are in the form of (x+n, y+m, z+o), with n,m,o being the wrapping period. Convert that into cylinder space, hope that no sincos appear and trying to intercept the diagonal for hit on the helix...