Additional heightmap compression.

So after slacking to check up on FC for awhile now; I look on here and the thread at the minecraft forum…
Nearly blew procrastinating my HW to my parents after seeing the pictures and yelling 'HAHA! AMAZING'.

 My parents now think that I REALY enjoy quadratic equations.

Dux Tell31 wrote:

 My parents now think that I REALY enjoy quadratic equations.

You mean... you don't really like quadratic equations?

Everyone knows finding the exact arc of a parabola is key to success in life..

MercurySteam wrote:

Dux Tell31 wrote:

 My parents now think that I REALY enjoy quadratic equations.

You mean... you don't really like quadratic equations?

Quadratic equations are a godsend. You just run the numbers through the thing and blam, answer. No thought involved.

Alright, here's the current situation. I've worked out the mistakes with the UV mapping which were creating the big holes, and now the surface mesh can fit tightly over the geometry. However, now there is a new issue.



Because the geometry is so close, it is clipping when the angle is too steep. The reason is that the raytracer is comparing a single point, but a block has 4 which can potentially clip the mesh. Because we are interpolating the heightfield at all but the 1m resolution, none of the 4 points are going to be equal. To make sure that the blocks aren't going to clip, the heightfield texture must be sampled in 4 places. It's not too bad from a textel fetching standpoint, because it's mostly the same textels over the life of the ray, only with different weights. Still, it is increasing the number of operations. Despite that, I'm not even close to exhausting the optimizations planned for this, so it should still be alright.

The other thing is that at 1m, the vertex needs to sample 4 textels and take the max of them to get the proper shape of the blocks. If you don't do this, you get pyramids. Since it'll only add error to do this at lower resolutions, I am going to pre-map the heightfield texture with the max-filter, and then re-generate all the lower resolution maps from that. Then the vertex transform only needs one sample at all the levels, and the minimum of 4 points needed in the fragment shader will still use the same rules as before, since the 45 degree parts will force the column downward.

Lately, I've had luck with as little as ~20 steps, which even unoptimized puts me in the 350fps range, though I have a pretty good GPU. Since the mesh is defining where to start scanning, the only times shadows appear are where there is no polygon closer to the surface than the one who's steps ran out. In other words, it is only in the low resolution areas when viewed at shallow angles. Because of this, I think it'll be possible to to fake it by assuming it will collide at the next available Y plane, and work out where that intersection will be and sample the terrain values from there. I've seen that trick used with some similar techniques, and even where it didn't work, it made the artifacts less noticeable than black spots. I feel like there should also be something I can do while the mesh geometry and heightfield resolution match up perfectly. For instance, you should be able to tell whether a ray is going to cross outside the plane of the triangle for that section of surface, and if it does, bail out, since it won't create a shadow. Still working out the math on that one.

FC beta v1.12

Also for the first line in the 3rd paragraph, I thought briefly you said you had to fuck with something, but you actually said you had luck with something.

Dux Tell31 wrote:

 My parents now think that I REALY enjoy quadratic equations.

Yeah, quadratics suck, partial fractions is where it's at.

Laibach wrote:

Dux Tell31 wrote:

 My parents now think that I REALY enjoy quadratic equations.

Yeah, quadratics suck, partial fractions is where it's at.

Bitch please, do you even calculus?

I would normally have something relevant to the topic here, but I am completely out of my depth on this one, apart from saying progress is good.

Prototype wrote:

Laibach wrote:

Dux Tell31 wrote:

 My parents now think that I REALY enjoy quadratic equations.

Yeah, quadratics suck, partial fractions is where it's at.

Bitch please, do you even calculus?

Not for another month or so, no.

Edit: Yay! More progress! Are you still in C++?

Yes, still C++.  The opengl interface is identical, thanks to LWJGL, but Java has a reversed byte order, so you have to do extra song and dance to make it work.  Plus it is way easier to work with low level data structures in C++ because you operate directly on memory.  There won't be any challenge porting it to Java, just time.


In other news, damn, I know I said the shader's not even close to optimized, but I had hoped for better at this point.  Just tried it out on my work computer, which supports DX11, but is an economy-mid range model, and it's getting ~30fps at the 20 step level I mentioned earlier.  30fps might be an acceptable minimum if that were all that was going to be displayed, but there is so much other crap that needs to be added.  I think I can still recover once I introduce the imposter shader(that's where it imitates flat block faces without actually raytracing), and I can always sample the distant renderer at a lower screen resolution and apply some sort of blur.  Might do that anyway to combat the Moire patterns, but this really puts a cramp on our budget.  Thank god the latest MC snapshot has improved performance on Mojang's end, at least, though I no idea what they did. My guess is it's a bunch of little things.

Also, it's safe to say now my home PC is almost exactly 10x faster than my work one, at least in the graphics department.  Good to know.

Would it be possible to package it up in a starter and source it out to us? I'm sure we'd all be happy to run it as a test on our computers, since we have ranges of computer powers.

I mean, you do have a small army of interwebs thralls awaiting your command.

Yeah, that will happen, but have more bugs to fix before I can get a proper baseline.

*Update*
I saw something interesting today.


What I did to get this is prevent the raytracer from crossing the boundary lines in the grid.  Each grid square is made up of two right triangles.  In the image above, the triangles are aligned with one of the left and one on the right.  As you can see, it's the grids where the triangles bend inwards that the clipping becomes an issue.  I can fix that by forcing the blocks down below the triangles if I know where the triangles lie.

But here's the cool part.  Note that the portion of the image not drawn due to restricting grid crossing is quite small, and in practice, crossing two grids is effectively nonexistent.  What I think I can do (at this coarse resolution, anyway) is make one render pass with the the 4 sample points passed from the vertex shader with some flat shading tricks, and then work directly off of those, with no further texture sampling.  You would have a well-defined maximum step size (and a fairly small one at that), and you can test the height much more cheaply.

Then you would run a fix-up pass, only filling in holes at the borders.  If done correctly, this should be really inexpensive, and be way more efficient.

*Edit*
The other bonus of this? All fragments sharing a particular execution path reside on the same polygon. If we want to do logic like whether it is the left or the right triangle, or what direction the triangle is facing, there's no branching logic. This opens up the door do some really powerful tricks.

Working on a equation. Given 4 points, you have a smoothly changing surface. Ignoring rasterization for a moment, you should be able to solve the intersection of a ray with that surface. If not, you should be able to do it in maybe 2 or 3 passes of a Riemann Sum. Once you reach that surface, or acceptably close enough, you should be within one square of the rasterized point. If we manage that, we are back in dirt cheap territory.

Yay dirt cheap.

Also, off topic, but frost, any advice for me on OBB by OBB collisions of voxels and how to optimize that. For no reason. Or at least, no reason that will ever get finished before I have another "brilliant idea" and sprint off to do that idea.

Use separating axis theorem. http://gamedev.tutsplus.com/tutorials/implementation/collision-detection-with-the-separating-axis-theorem/

If you only do one of the orientations, it is identical to the aligned bounding box problem, which is plenty for preliminary culling. That's all I can really say without knowing more about your scenario.

Okay, that plus layered collision checking should be good, thanks.

Okay, so here's the plan. You start with a square, but each corner has a different value on its Y axis. That is basically what a quad is like on our map. To get the interpolated Y value at any given point, you just take the weighted average using your position relative to the 4 points. With a square it is pretty straightforward.

Now imagine we have a ray intersecting this shape, but at an angle. First you make a plane passing through the ray origin with the ray as the normal. Then, to get the depth of the 4 corners, you project them onto the plane with a dot product operator. To figure out their position in terms of this plane, you need two more dot products using axes perpendicular to the ray. It doesn't matter particularly how it is aligned. Then you multiply the depth of the object by the weight of the coordinates in that plane(this is the same for all quadrilaterals regardless of how they are distorted) and sum them together. Now you know exactly where the ideal intersection lies, and you can round to the nearest block face, including one extruding from the mesh (though that could potentially lead to bad silhouettes). But that's the whole algorithm. No stepping, no logic, and only a couple really basic vector operations.

...

I felt good when I understood what a dot product was yesterday.

Anyways, looks like some nice progress on the far-rendering.

If you represent a plane as a unit vector pointing perpendicular to the plane, a dot product of that vector and another point will give you the distance of that point above the plane.  Repeating that twice more with two additional axes gives us a new X, Y, and Z.  If you look a a 3x3 rotation matrix some time, you'll see that it is really just 3 unit vectors which are perpendicular to one another, only you are applying them all at once instead of one at a time.

fr0stbyte124 wrote:

If you represent a plane as a unit vector pointing perpendicular to the plane, a dot product of that vector and another point will give you the distance of that point above the plane.  Repeating that twice more with two additional axes gives us a new X, Y, and Z.  If you look a a 3x3 rotation matrix some time, you'll see that it is really just 3 unit vectors which are perpendicular to one another, only you are applying them all at once instead of one at a time.

That actually made sense.
Carry on.

I'm not sure this reprojection method is right anymore. The math is causing me trouble.

Given a 1x1 height field with 4 height inputs, it should be possible to create a function of the height along an arbitrary crossing through it. Once I can derive that, it should be trivial to solve for the intersect with a given height value and slope. It can intersect in 0, 1, or 2 places, depending on the inputs.

Yep, just verified.  It resolves out to the quadratic equation, so if any of you are wondering what application the quadratic formula has in real life, it's this.  Also, this is probably the craziest instances of it I've ever seen.  It has 10 variables and I've gone through a full page just simplifying the factors, and it'll probably be another full page of simplification once it is plugged into the formula.  I really need to stop doing this in pen.

I just noticed that, on the pics you posted so far (I know they are outdated, but still...) it is showing the bottom of the sea instead of the water surface hight-wise.
(maybe a problem with your software not registering liquid blocks?)

I exported the map using world painter.  The colors and light gradients were its choice.  The heightmap, however, is accurate for the actual ground, so what you are seeing is the riverbed, but painted with the colors of the river's surface.  I figure that's good enough for testing purposes.

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