Voxelmap mod 1.17/1.16.5 (minimap in minecraft)

Calculating Mesh Normals

You remember this math, right?

Calculating normals is actually quite straightforward. If you remember your multivariable calculus, vectors orthogonal to a level set are always gradients of the function. For a function with a 2D domain, you can imagine a topographical map. The level sets, curves of constant altitude, are always orthogonal to the gradient vector, i.e. the vector pointing in the steepest direction. So for a function with a 3D domain, like our signed distance function, the isosurface is a level set, and its normal vectors are gradients of the signed distance function.

So we will approximate the gradient at a surface point by looking at the same set of 8 cube corners. To get the x coordinate of the gradient, take the sum of the differences between corners along edges in the x direction. Likewise for y and z.

Approximating the normal vector components in 2D. The d values are the signed distances at each corner.

Finding the Mesh Positions

So the first step is to understand what the grid of cubes looks like relative to your input. Our input is a 3D grid of voxels. For Surface Nets, you should imagine that each voxel is actually not a cube but instead a single point in 3D space (the same 3D space where we define the signed distance function). That point is a corner shared by 8 cubes in the grid.

The voxels are the pluses (+) and minuses (-) on the corners of the “cubes”.

So each voxel must store the value of the signed distance function at a corner in the grid. Now we know one of the pieces of data to store in our type. (Don’t worry, we’re not going to store an ).

Now, for each cube in the grid, we need to determine where we would find an isosurface point, if there is one at all. We can look at the 8 corners of a cube, and if there is a mix of positive and negative distances at those corners, we can say that there must be a surface point somewhere in the cube.

The pink dots are surface points. Note that they only appear in “cubes” where the corners don’t all have the same sign.

Similarly, we can look at the 12 edges of the cube, and we know that if an edge connects two points (voxels) with different sign, then by the Intermediate Value Theorem, there must be some point on the edge which has value 0, i.e. it’s a surface point, and that edge intersects the surface there. We take all such edges in the cube and average their surface intersection points to get an approximate surface point that lies inside of the cube. If there are no such edges, then we skip this cube, as it does not contain a surface point.

The pink line segments form the “surface.” (In 3D, they would be quads). Notice that the surface only crosses “cube” edges where the sign changes along the edge.

So how do we calculate the intersection point for one edge? This is where the actual distance values come into play. Technically, we only know the distance from a corner to the closest point on the isosurface (this is the definition of the signed distance function), but that’s not necessarily the point of surface-edge intersection (the point labeled Ps in the diagram below).

We can’t have enough information in our finite grid to calculate the exact intersection. But what if we make the assumption that the surface is approximately flat in the neighborhood of the intersection? This is true in the limiting case for manifolds, which is why you get a better approximation as the grid resolution increases.

Consider the diagram below.

P1 and P2 are corners of a cube. The edge between them intersects the surface at Ps. f is the signed distance function. The perpendicular dotted lines indicate the distances from P1 and P2 to the surface.

We see an edge connecting two corners with 3D coordinates P1 and P2, with the respective signed distance values d1 and d2. The surface intersects the edge at a point with coordinates Ps.

By similarity of the triangles, the ratio

d1 / d2

should be equal to the ratio

|P1 — Ps| / |Ps — P2|

In fact, it is only the ratio that we need to calculate the point of surface-edge intersection. So we use linear interpolation to find the point on the edge where the signed distance must be zero.

Finding the surface-edge intersection point with linear interpolation.

Then, like I said before, we do this calculation of Ps for every intersecting edge, and we find the average of all of those Ps’s. This average is the surface point inside the cube!

Find the average of the surface-edge intersection points.

Building the Mesh Triangles

The final step is to write out an index buffer that defines all of the triangles in your mesh. Get yourself amped because this is probably the most confusing part.

Again, we’ll be looking at edges of cubes, but in a slightly different way. We will iterate over all of the surface points we found before. A pseudocode description goes like this:

mesh_quads = []for P1 in surface_points:    for axis in :        edge = get a cube edge in the direction of "axis"        quad = get a quad, orthogonal to "axis", of surface points               where P1 is the maximal corner        if edge is (-,+) or edge is (+,-):            insert quad into mesh_quads

But which cube edge and which quad are we looking for? The easiest way for me to describe is with pictures, and they’re in 3D this time!

One of the 3 possible quads at P1. An edge intersects the quad. The edge is shared by 4 cubes, and the corners of the quad are the surface points inside of each cube.

There can be up to 3 quads found for surface point P1.

Hopefully that picture gets my point across. And for fun, here’s the 2D analog (an overhead view).

An edge intersecting a surface line segment in 2D. The edge is shared by 2 squares, and the endpoints of the line segment are the surface points inside of each square.

At least in my implementation, I look in the negative directions from p1 to get the other quad corners (p2). Be careful on the boundaries of your grid, since there may not exist surface points in the directions you need to look.

Once you have your quad corners, you need to write the indices of those corners into the index buffer in a winding order that points the normal vector in the correct direction. (You will in fact be using 6 indices to make 2 triangles).

Gimme Some Real Code to Look At!

It’s one thing for me to blather on about the algorithm, and another for you to understand it concretely enough to implement it. So I might as well just give you a cheat sheet. Here’s my implementation of Surface Nets. Sorry I didn’t provide any snippets in this article inline, but it’s kind of hard to make sense of them without seeing all the code at once.

Surface Nets with Chunks

Recall that our voxel map is a set of chunks. Each chunk has a separate mesh. So any time a voxel changes, then the mesh for that chunk needs to change. Rather than trying to figure out how to apply deltas to a mesh, it’s quite simple to just regenerate the entire mesh any time the chunk changes.

But there is an important issue to consider. Do we know that our chunk meshes will be compatible at the chunk boundaries? It turns out that, if you only look at the voxels in a chunk when meshing, you will have discontinuities in your mesh! This happens because Surface Nets only calculates surface points inside of the cubes that you give it. But, looking at the entire set of chunks, there are cubes with corners from multiple chunks.

Each orange square is a chunk, and the V’s inside are the voxels. The pink dots are the surface points, but the pink O’s show where surface points are missing.

Thankfully, the remedy is pretty simple. When meshing a chunk, you look not only at the voxels in that chunk, but all adjacent voxels as well. This will make sure we don’t miss any cubes, and the meshes will calculate identical surface points on the boundary, so they will line up seamlessly.

This solution comes with a cost. Now when you update a voxel on the boundary of a chunk, it will affect the meshes of all adjacent chunks. In fact, any voxels adjacent to boundary voxels will also affect the meshes of adjacent chunks!

All of the voxels between the orange and purple boundaries will induce a mesh dependency with the adjacent chunk they are closest to.

This is something that the Voxel Mapper accounts for . Here’s a picture showing what happens when you fail to account for this.

Meshes incompatible on a chunk boundary

Even once I had implemented all of these fixes, there was yet another problem with the meshes that caused some ugliness. No, it’s not the nasty green color of this mesh (I was working on material blending at the time).

Z fighting of redundant quads

What’s going on here? Do you see the green quad surrounded by darker green quads? That’s actually two overlapping meshes, Z fighting. There are redundant quads being generated on chunk boundaries. Here’s one example of how this can happen:

The chunks generating the same quad (double line) on a boundary

Again, the fix for this is pretty simple once you’ve thought about it for a while. You need to resolve the conflict between the two chunks. You can do this by forcing the chunks to only generate quads on 3 of their 6 boundaries. This only requires a few extra “if” statements (boundary checks) in your code. Here’s what that looks like in 2D:

A chunk only generates quads on the solid lines (planes). It leaves the dotted lines (planes) alone, since they will be picked up by an adjacent chunk.

Texturing a Generated Mesh

So once you have your meshes, how do you make them look nice? You probably want to texture them. This requires generating UV coordinates for every vertex in the mesh.

Procedurally generating UVs, also known as UV unwrapping, is actually a rather difficult problem that’s expensive to implement, especially for a real-time application. I tried it, and it didn’t go well.

My failure at UV unwrapping. Obviously there are well-known techniques for doing this on a sphere, but we need something that works on any manifold.

If you can figure out real-time UV unwrapping that looks good, you are awesome, you should write about it! But I’m not that awesome, so instead I chose to use a simpler technique called Triplanar Mapping.

Triplanar Mapping

The basic idea of Triplanar Mapping is pretty easy to understand. You take three different texture samples for a single vertex and blend them together using weights determined by the normal vector. You are essentially tiling the textures across the entire world and projecting the them onto the surface in the three axis directions. I’m not going to explain this in detail, since there are already some great references on this:

• a somewhat terse article with sample shader code by Martin Palko
• a wonderful article about triplanar normal mapping by Ben Golus
• my own fragment shader for my voxel render pass; I paste the relevant parts of this further down in this article

The main takeaway here is that the mesh vertices only require position and normal attributes to work with Triplanar Mapping, and you don’t have to generate any UVs until you get to the fragment shader stage.

Скачать VoxelMap

Версии: