Additional heightmap compression.

Ivan2006 wrote:

Meh. K.
just saying it might look ugly if you are (somehow, maybe creative) flying over the ocean and when it turns into your stuff in the distance it might look a bit...strange at the border

He's just testing this, it's not even in java/Minecraft yet.

I know, but it will still exist when he moves it to the real stuff if he doesn´t notice...

I'll notice.  Water's a different shader entirely.

Anyway, I gave up trying to solve the quadratic equation by hand, and I left Wolfram Alpha do it.  Here were the two results.

Given:
a = height(0,0)
b = height(1,0)
c = height(1,1)
d = height(0,1)
i = rayStart.x
j = rayStart.y
m = rayStart.z
k = rayStep.x
l = rayStep.y
n = rayStep.z
solving for t = 1 unit of time along the vector rayStep


That looks about right.

Apparently there are special cases when the ray is perfectly aligned with either horizontal axis, and another if (a-b+c-d) = 0.  Pretty sure that means it is planar.  The aligned axis can be avoided by introducing a small amount of noise to offset the vector, and the planar version can simply be left in, since it is going to the case over the entire triangle, so we don't need to worry about branching behavior.

Also, the only difference between the first two is the +sqrt and the -sqrt

A simple factorization puts the first solution at

Code:

A = kl(a-b+c-d)
B = a(il+jk-k-l) - b(il+jk-k) + c(il+jk) - d(il+jk-l) - n
C = a(ij-i-j+1) - b(ij-i) + c(ij) - d(ij-j) - m

t= -B +- sqrt( B^2 - 4AC)
   ----------------------
            2A

Notice that the a-b+c-d is the same for each.  We can turn that into a 4D vector and do dot products to combine them.  This is turning into something really nice.

*edit*

I think this is right.  I'll need to double-check the signs of the vectors, but otherwise, this is the whole thing.  I think it's pretty cool.

Code:

vec4 abcd = vec4(a, -b, c, -d);

float A = dot(abcd, vec4(kl,kl,kl,kl));
float B = dot(abcd, vec4(iljk-k-l, iljk-k, iljk, iljk-l)) - n;
float C = dot(abcd, vec4(ij-i-j+1, ij-i, ij, ij-j)) - m;

//want smaller value, square root can't be negative
float t = (-B - sqrt(pow(B, 2.0) - 4.0*A*C))/(2.0 * A);

vec3 rayFinal = rayStart + t*rayStep;

It's possible for t to be negative, as well, meaning the surface of the heightfield is behind the starting point of the ray, and the blocks will be projected above the surface of the mesh.  This might cause some clipping issues when viewed from oblique angles, but from what I've seen I don't think it will be a problem.

Refactored and combined the cases.  Now we have this.  I am pretty sure it is right.

float s1 = iljk-k-l;
float s2 = ij-i-j+1;
float B0 = dot(abcd, vec4(s1,s1,s1,s1));
float C0 = dot(abcd, vec4(s2,s2,s2,s2));
float B1 = dot(abcd, vec4(i-1, i, i, i-1)) * l;
float B2 = dot(abcd, vec4(j-1, j-1, j, j)) * k;
float B = B1+B2 - n;
float C = dot(abcd, vec4(ij-i-j+1, ij-i, ij, ij-j)) - m;  //abcd * {(i-1)(j-1), (i)(j-1), (i)(j), (i-1)(j)} - m
float A = dot(abcd, vec4(kl,kl,kl,kl));

if(lk==0)
{
float t = -C / (B);
}
else if(A==0)
{
float t = (C0 - C ) / (B0 - B);
}
else
{
float t = (-B - sqrt(pow(B, 2.0) - 4.0*A*C))/(2.0 * A);
}

Math is happening here! Be warned!

Again, accept my deepest gratitude for doing this, whatever this is.

Can someone explain what fr0st is saying in layman's terms?

Solar112 wrote:

Can someone explain what fr0st is saying in layman's terms?

He's adding together a lot of vectors, for some reason or another.
Edit: Can you follow the math? It isn't too advanced(as far as I can tell) just complicated.
Moar edit: Fr0st, is there any reason why you multiply

Code:

ij*l*k

instead of

Code:

ij*kl

?

Yeah, let me fix the notation there...

I had started writing it like glsl, where ij would be seen as a new variable unrelated to i or j.  But that is pointless here, so ij is now an implied i*j.

Solar112 wrote:

Can someone explain what fr0st is saying in layman's terms?

In the far view system, the heightmap is stored to a texture which becomes increasingly lower resolution the further you get from the player.  What the raytracer is sampling, then, is the weighted average of the 4 nearest textels.  Because the 4 input textels are the same for every block inside a grid unit (I posted an image of it on the previous page), we are cutting out the middle-man and solving the intersection directly for where the elevation of the ray at (x,z) matches the interpolated height sample at the same (x,z).  The function for this resolves to to a quadratic, which can then be solved with the quadratic formula.  The other two special cases happen for ways in which you end up dividing by zero, but can still be solved through refactoring.

Err, hooray?

This is sort of unrelated, but do you know of any books on 4 dimensional geometry? Not qauternions or whatever they're called, just like a basic plane geometry textbook, but for 4 dimensions, if that makes sense.

Laibach wrote:

Err, hooray?

This is sort of unrelated, but do you know of any books on 4 dimensional geometry? Not qauternions or whatever they're called, just like a basic plane geometry textbook, but for 4 dimensions, if that makes sense.

Wikipedia is a better textbook than any textbook I've ever owned.  And if you get lucky, http://simple.wikipedia.org/ will have an even more straightforward explaination.  Other than that, I don't really have any suggestions.  4D geometry is not something I deal with too often and when I do, the equations I need are mostly already derived.

If you are interested is 4D shapes, this is a handy reference. http://simple.wikipedia.org/wiki/Convex_regular_4-polytope

fr0stbyte124 wrote:

Laibach wrote:

Err, hooray?

This is sort of unrelated, but do you know of any books on 4 dimensional geometry? Not qauternions or whatever they're called, just like a basic plane geometry textbook, but for 4 dimensions, if that makes sense.

Wikipedia is a better textbook than any textbook I've ever owned.  And if you get lucky, http://simple.wikipedia.org/ will have an even more straightforward explaination.  Other than that, I don't really have any suggestions.  4D geometry is not something I deal with too often and when I do, the equations I need are mostly already derived.

If you are interested is 4D shapes, this is a handy reference. http://simple.wikipedia.org/wiki/Convex_regular_4-polytope

Thanks!

fr0stbyte124 wrote:

Solar112 wrote:

Can someone explain what fr0st is saying in layman's terms?

In the far view system, the heightmap is stored to a texture which becomes increasingly lower resolution the further you get from the player.  What the raytracer is sampling, then, is the weighted average of the 4 nearest textels.  Because the 4 input textels are the same for every block inside a grid unit (I posted an image of it on the previous page), we are cutting out the middle-man and solving the intersection directly for where the elevation of the ray at (x,z) matches the interpolated height sample at the same (x,z).  The function for this resolves to to a quadratic, which can then be solved with the quadratic formula.  The other two special cases happen for ways in which you end up dividing by zero, but can still be solved through refactoring.

Thanks.

Ah crap, it's not working.  There is a ridiculous number of places for there to be a mistake.  The output is all over the place and changes sign depending on which quadrant the ray is pointing in, and that shouldn't have happened.  Worst part is how difficult it is to debug, since you can't see what the actual values being used are.  There's a tool I'm looking into which might help though.

*Edit*
Aaaaand it doesn't work. FML.

On a side note, I've started taking a liking to this weird looking artifact.



I wonder if we can use it somewhere, like a warp-in effect or something.

Is there a fix possible?

Would something like this fix it? (Came to my mind because part of your code reminded me of the formula for solving quadratic eqations)

Code:

float s1 = iljk-k-l;
float s2 = ij-i-j+1;
float B0 = dot(abcd, vec4(s1,s1,s1,s1));
float C0 = dot(abcd, vec4(s2,s2,s2,s2));
float B1 = dot(abcd, vec4(i-1, i, i, i-1)) * l;
float B2 = dot(abcd, vec4(j-1, j-1, j, j)) * k;
float B = B1+B2 - n;
float C = dot(abcd, vec4(ij-i-j+1, ij-i, ij, ij-j)) - m;  //abcd * {(i-1)(j-1), (i)(j-1), (i)(j), (i-1)(j)} - m
float A = dot(abcd, vec4(kl,kl,kl,kl));

if(lk==0)
{
float t = -C / (B);
}
else if(A==0)
{
float t = (C0 - C ) / (B0 - B);
}
else if((pow(B, 2.0) - 4.0*A*C) >= 0)
{
float t = (-B - sqrt(pow(B, 2.0) - 4.0*A*C))/(2.0 * A);
}
else
{
float t = (-B - sqrt(pow(B, 2.0) - 4.0*-A*C))/(2.0 * -A);
}

Disregard if it doesn't.

craftqq wrote:

Would something like this fix it? (Came to my mind because part of your code reminded me of the formula for solving quadratic eqations)

Code:

float s1 = iljk-k-l;
float s2 = ij-i-j+1;
float B0 = dot(abcd, vec4(s1,s1,s1,s1));
float C0 = dot(abcd, vec4(s2,s2,s2,s2));
float B1 = dot(abcd, vec4(i-1, i, i, i-1)) * l;
float B2 = dot(abcd, vec4(j-1, j-1, j, j)) * k;
float B = B1+B2 - n;
float C = dot(abcd, vec4(ij-i-j+1, ij-i, ij, ij-j)) - m;  //abcd * {(i-1)(j-1), (i)(j-1), (i)(j), (i-1)(j)} - m
float A = dot(abcd, vec4(kl,kl,kl,kl));

if(lk==0)
{
float t = -C / (B);
}
else if(A==0)
{
float t = (C0 - C ) / (B0 - B);
}
else if((pow(B, 2.0) - 4.0*A*C) >= 0)
{
float t = (-B - sqrt(pow(B, 2.0) - 4.0*A*C))/(2.0 * A);
}
else
{
float t = (-B - sqrt(pow(B, 2.0) - 4.0*-A*C))/(2.0 * -A);
}

Disregard if it doesn't.

His code was solving a quadratic equation.

fr0stbyte124 wrote:

Ah crap, it's not working.  There is a ridiculous number of places for there to be a mistake.  The output is all over the place and changes sign depending on which quadrant the ray is pointing in, and that shouldn't have happened.  Worst part is how difficult it is to debug, since you can't see what the actual values being used are.  There's a tool I'm looking into which might help though.

*Edit*
Aaaaand it doesn't work.  FML.

So is it a total loss? Or just really hard to debug.

It's not a total loss. I'm confident I just made an error or a bad assumption while refactoring it. But it is really hard to debug because you can't step through it or see what sort of numbers it is generating. The best you can do is set outputs to colors and hope that you can interpret it. This other program I was trying is a glsl debugger which is supposed to let me step through the shader code, but it crashes before the program even finishes compiling the shaders and I don't know why.

Laibach wrote:

craftqq wrote:

Would something like this fix it? (Came to my mind because part of your code reminded me of the formula for solving quadratic eqations)
-snip-

His code was solving a quadratic equation.
-snip-

That's actually what I meant, I just phrased that bad. My addition would check if sqrt(pow(B, 2.0) - 4.0*A*C)) would be solvable, and turns if it isn't, it "mirrors the graph" (if you'd draw the quadratic equation in a diagram) so there'd be a solution to it.

If it goes negative, that means there are no intercepts because the ray passes above the curve. I have glsl checking whether the value becomes undefined afterwards, to avoid branching.

New pic.



This shows the difference between projecting the heightmap directly onto the mesh vs raytracing the heightmap.  Both are identical from the top looking down, but the discrepancy becomes quite apparent when viewed horizontally.  I'm still trying to solve the intersection directly, but now at least we have something that works to compare it against.

I have no idea what the fuck I'm looking at here.

Look at it like a topographical map.  Both images are the side of a hill.  Each black band is 1m apart vertically, and if the block renderer was enabled, these lines are the contours they would follow.

You cannot grasp the true form of Fr0stbyte's picture