Futurecraft Forums

A forum dedicated to communication and innovation!
 
HomeCalendarFAQSearchMemberlistUsergroupsRegisterLog in
Welcome, one and all, to the Futurecraft Forums!

Share | 
 

 Additional heightmap compression.

View previous topic View next topic Go down 
Go to page : Previous  1, 2, 3, 4, 5, 6, 7  Next
AuthorMessage
Laibach
General
General
avatar

Posts : 2024
Join date : 2012-01-23
Age : 66
Location : Frozen Fields

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 12:37 pm

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.
Back to top Go down
View user profile
Ivan2006
General
General
avatar

Posts : 2096
Join date : 2012-05-08
Age : 19
Location : The Dungeon.

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 12:59 pm

I know, but it will still exist when he moves it to the real stuff if he doesn´t notice...
Back to top Go down
View user profile
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 1:56 pm

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.


Last edited by fr0stbyte124 on Wed Sep 18, 2013 5:48 pm; edited 1 time in total
Back to top Go down
View user profile
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 5:00 pm

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);
}


Last edited by fr0stbyte124 on Wed Sep 18, 2013 5:46 pm; edited 1 time in total
Back to top Go down
View user profile
ACH0225
General
General
avatar

Posts : 2346
Join date : 2012-01-01
Location : I might be somewhere, I might not.

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 5:25 pm

Math is happening here! Be warned!
Back to top Go down
View user profile
Laibach
General
General
avatar

Posts : 2024
Join date : 2012-01-23
Age : 66
Location : Frozen Fields

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 5:27 pm

Again, accept my deepest gratitude for doing this, whatever this is.
Back to top Go down
View user profile
Delta
Sergeant
Sergeant
avatar

Posts : 903
Join date : 2012-03-26
Age : 19
Location : Virginia

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 5:27 pm

Can someone explain what fr0st is saying in layman's terms?
Back to top Go down
View user profile http://arsln100.forumotion.com
Laibach
General
General
avatar

Posts : 2024
Join date : 2012-01-23
Age : 66
Location : Frozen Fields

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 5:40 pm

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
?
Back to top Go down
View user profile
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 5:47 pm

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.


Last edited by fr0stbyte124 on Wed Sep 18, 2013 6:13 pm; edited 4 times in total
Back to top Go down
View user profile
Laibach
General
General
avatar

Posts : 2024
Join date : 2012-01-23
Age : 66
Location : Frozen Fields

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 5:57 pm

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.
Back to top Go down
View user profile
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 6:09 pm

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
Back to top Go down
View user profile
Laibach
General
General
avatar

Posts : 2024
Join date : 2012-01-23
Age : 66
Location : Frozen Fields

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 6:30 pm

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!
Back to top Go down
View user profile
Delta
Sergeant
Sergeant
avatar

Posts : 903
Join date : 2012-03-26
Age : 19
Location : Virginia

PostSubject: Re: Additional heightmap compression.   Wed Sep 18, 2013 7:09 pm

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.
Back to top Go down
View user profile http://arsln100.forumotion.com
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Thu Sep 19, 2013 2:02 am

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.
Back to top Go down
View user profile
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Thu Sep 19, 2013 3:37 am

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.
Back to top Go down
View user profile
Keon
Lord/Lady Rear Admiral 1st
Lord/Lady Rear Admiral 1st
avatar

Posts : 3075
Join date : 2012-01-17
Location : Hahahaha.

PostSubject: Re: Additional heightmap compression.   Thu Sep 19, 2013 10:15 am

Is there a fix possible?

_________________
fr0stbyte124 wrote:
You know, I was thinking we should have a 3D crafting grid for complex recipes, but Kielaran is right: why have three dimensions when you can have six? Truly I don't know how we ever got by with a measly two.


Mackeroth? wrote:
Now, if Fr0stbyte wrote that, someone would make a sig, guaranteed. So what are you going to do now?
Back to top Go down
View user profile
craftqq
Newbie
Newbie
avatar

Posts : 18
Join date : 2013-07-30

PostSubject: Re: Additional heightmap compression.   Thu Sep 19, 2013 12:33 pm

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.
Back to top Go down
View user profile
Laibach
General
General
avatar

Posts : 2024
Join date : 2012-01-23
Age : 66
Location : Frozen Fields

PostSubject: Re: Additional heightmap compression.   Thu Sep 19, 2013 1:15 pm

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.
Back to top Go down
View user profile
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Thu Sep 19, 2013 1:31 pm

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.
Back to top Go down
View user profile
craftqq
Newbie
Newbie
avatar

Posts : 18
Join date : 2013-07-30

PostSubject: Re: Additional heightmap compression.   Thu Sep 19, 2013 2:29 pm

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.
Back to top Go down
View user profile
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Thu Sep 19, 2013 3:10 pm

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.
Back to top Go down
View user profile
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Fri Sep 20, 2013 7:38 pm

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.


Back to top Go down
View user profile
ACH0225
General
General
avatar

Posts : 2346
Join date : 2012-01-01
Location : I might be somewhere, I might not.

PostSubject: Re: Additional heightmap compression.   Fri Sep 20, 2013 11:40 pm

I have no idea what the fuck I'm looking at here.
Back to top Go down
View user profile
fr0stbyte124
Super Developrator
Super Developrator
avatar

Posts : 1835
Join date : 2011-10-13

PostSubject: Re: Additional heightmap compression.   Sat Sep 21, 2013 12:55 am

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.
Back to top Go down
View user profile
Groot
Marine
Marine
avatar

Posts : 1456
Join date : 2012-03-18
Age : 21
Location : Yggdrasil

PostSubject: Re: Additional heightmap compression.   Sat Sep 21, 2013 1:53 am

You cannot grasp the true form of Fr0stbyte's picture
Back to top Go down
View user profile
Sponsored content




PostSubject: Re: Additional heightmap compression.   

Back to top Go down
 
Additional heightmap compression.
View previous topic View next topic Back to top 
Page 6 of 7Go to page : Previous  1, 2, 3, 4, 5, 6, 7  Next
 Similar topics
-
» Details about ISO compression
» EX-70 1.4.2.0 compression modes question
» [ANSWERED] Inefficient ISO compression?
» How to do at home migraine device

Permissions in this forum:You cannot reply to topics in this forum
Futurecraft Forums :: Development :: Idea Center-
Jump to: