Futurecraft Forums A forum dedicated to communication and innovation! 
Welcome, one and all, to the Futurecraft Forums! 
  Additional heightmap compression.  
 
Author  Message 

Laibach General
Posts : 2024 Join date : 20120123 Age : 67 Location : Frozen Fields
 Subject: 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. 
   Ivan2006 General
Posts : 2096 Join date : 20120508 Age : 20 Location : The Dungeon.
 Subject: 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... 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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 (ab+cd) = 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(ab+cd) B = a(il+jkkl)  b(il+jkk) + c(il+jk)  d(il+jkl)  n C = a(ijij+1)  b(iji) + c(ij)  d(ijj)  m
t= B + sqrt( B^2  4AC)  2A
Notice that the ab+cd 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 doublecheck 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(iljkkl, iljkk, iljk, iljkl))  n; float C = dot(abcd, vec4(ijij+1, iji, ij, ijj))  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 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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 = iljkkl; float s2 = ijij+1; float B0 = dot(abcd, vec4(s1,s1,s1,s1)); float C0 = dot(abcd, vec4(s2,s2,s2,s2)); float B1 = dot(abcd, vec4(i1, i, i, i1)) * l; float B2 = dot(abcd, vec4(j1, j1, j, j)) * k; float B = B1+B2  n; float C = dot(abcd, vec4(ijij+1, iji, ij, ijj))  m; //abcd * {(i1)(j1), (i)(j1), (i)(j), (i1)(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 
   ACH0225 General
Posts : 2346 Join date : 20120101 Location : I might be somewhere, I might not.
 Subject: Re: Additional heightmap compression. Wed Sep 18, 2013 5:25 pm  
 Math is happening here! Be warned! 
   Laibach General
Posts : 2024 Join date : 20120123 Age : 67 Location : Frozen Fields
 Subject: Re: Additional heightmap compression. Wed Sep 18, 2013 5:27 pm  
 Again, accept my deepest gratitude for doing this, whatever this is. 
   Delta Sergeant
Posts : 903 Join date : 20120326 Age : 20 Location : Virginia
 Subject: Re: Additional heightmap compression. Wed Sep 18, 2013 5:27 pm  
 Can someone explain what fr0st is saying in layman's terms? 
   Laibach General
Posts : 2024 Join date : 20120123 Age : 67 Location : Frozen Fields
 Subject: 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
? 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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 middleman 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 
   Laibach General
Posts : 2024 Join date : 20120123 Age : 67 Location : Frozen Fields
 Subject: 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. 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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_4polytope 
   Laibach General
Posts : 2024 Join date : 20120123 Age : 67 Location : Frozen Fields
 Subject: 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_4polytope
Thanks! 
   Delta Sergeant
Posts : 903 Join date : 20120326 Age : 20 Location : Virginia
 Subject: 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 middleman 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. 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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. 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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 warpin effect or something. 
   Keon Lord/Lady Rear Admiral 1st
Posts : 3075 Join date : 20120117 Location : Hahahaha.
 Subject: 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?

   craftqq Newbie
Posts : 18 Join date : 20130730
 Subject: 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 = iljkkl; float s2 = ijij+1; float B0 = dot(abcd, vec4(s1,s1,s1,s1)); float C0 = dot(abcd, vec4(s2,s2,s2,s2)); float B1 = dot(abcd, vec4(i1, i, i, i1)) * l; float B2 = dot(abcd, vec4(j1, j1, j, j)) * k; float B = B1+B2  n; float C = dot(abcd, vec4(ijij+1, iji, ij, ijj))  m; //abcd * {(i1)(j1), (i)(j1), (i)(j), (i1)(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. 
   Laibach General
Posts : 2024 Join date : 20120123 Age : 67 Location : Frozen Fields
 Subject: 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 = iljkkl; float s2 = ijij+1; float B0 = dot(abcd, vec4(s1,s1,s1,s1)); float C0 = dot(abcd, vec4(s2,s2,s2,s2)); float B1 = dot(abcd, vec4(i1, i, i, i1)) * l; float B2 = dot(abcd, vec4(j1, j1, j, j)) * k; float B = B1+B2  n; float C = dot(abcd, vec4(ijij+1, iji, ij, ijj))  m; //abcd * {(i1)(j1), (i)(j1), (i)(j), (i1)(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. 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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. 
   craftqq Newbie
Posts : 18 Join date : 20130730
 Subject: 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. 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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. 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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. 
   ACH0225 General
Posts : 2346 Join date : 20120101 Location : I might be somewhere, I might not.
 Subject: Re: Additional heightmap compression. Fri Sep 20, 2013 11:40 pm  
 I have no idea what the fuck I'm looking at here. 
   fr0stbyte124 Super Developrator
Posts : 1835 Join date : 20111013
 Subject: 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. 
   Groot Marine
Posts : 1456 Join date : 20120318 Age : 22 Location : Yggdrasil
 Subject: Re: Additional heightmap compression. Sat Sep 21, 2013 1:53 am  
 You cannot grasp the true form of Fr0stbyte's picture 
   Sponsored content
 Subject: Re: Additional heightmap compression.  
 
    Additional heightmap compression.  

Similar topics  

 Permissions in this forum:  You cannot reply to topics in this forum
 
 
 
