Back to pufferfish.pl

Voxel to SVG

Introduction

When I was playing Minecraft with my friends we wanted to see the map of the world that we explored. So I made a flat 2D map, but after some time I realized that it was boring. Then I started working on a map with dimetric perspective.


The Algorithm

It uses the fact that grid of triangles can be used to draw voxels. Unlike the other Minecraft mappers it uses SVG files to output images. This algorithm is designed to process large maps in a very short amount of time. Creating SVG images for 4096x4096 voxel world took about 45 seconds on my i7-7700.

Let's assume that the top right triangle is a master triangle of the voxel. Focusing on only one triangle will make translations easier to understand.


First step is translation voxel coordinates (voxelX, voxelZ) to triangle grid coordinates (gridX, gridY).

By looking at voxels on the left image and master triangles on the right image it is easy to see the relationships between coordinate systems.
The formula is very simple:

gridX = voxelX - voxelZ
gridY = voxelX + voxelZ

There is also an Y coordinate so voxel coordinates are now (voxelX, voxelY, voxelZ), grid coordinates are the same.

The image shows that the voxel Y axis is pointing an opposite direction of the grid Y axis. It also must be multiplied by 2. The image shows why.
So the formula now looks:

gridX = voxelX - voxelZ
gridY = voxelX + voxelZ - voxelY * 2

There are situations where one triangle is used by two voxels, that causes images to break (left image below). To fix that one needs to know which voxel is closer to the camera so we need to calculate the depth.

In the voxel coordinate system the resultant (wypadkowa) of X, Y and Z axes is pointing to the camera, then the sum of negative X, negative Y and negative Z is the depth.
Then the formula is

depth = -(voxelX + voxelY + voxelZ)

All 6 triangles of the voxel have the same depth. Then when two triangles are at the same coordinate we choose that one which has lower depth.


When the coordinates and depth of the master triangle are known, other triangles of voxel can also be calculated.


Skipping obscured voxels

Many voxels are behind the other voxels, so they are not visible. Updating triangles of that voxels is a waste of time. Checking that the voxel is behind the other voxels is done while updating the master triangle of that voxel. When at a given position already there is a master triangle of the other voxel and its depth is lower than the current master triangle then the current voxel is obscured by it.
The code looks:

updateTriangle(x, y, depth, color, isMaster){
	Triangle triangle = // get triangle at (x, y)
	if(triangle.depth > depth){
		triangle.depth = depth
		triangle.color = color
		if(isMaster){
			triangle.masterDepth = depth
		}
	}else if(isMaster){
		if(triangle.masterDepth > depth){
			triangle.masterDepth = depth
		}else{
			return true // voxel is behind
		}
	}
	return false
}

After updating the master triangle of the voxel it is known that the voxel is obscured or not. If it is obscured it does not update other triangles of that voxel.


Splitting into pieces

Splitting is done at processing time. When new voxel is read from world file, then all its triangles are put into given pieces, triangles from one voxel may be on different pieces. If the piece does not exist, the a new piece is created. Then the triangle is put into this piece at given position. Splitting into rectangular pieces causes some triangles to be inside different pieces (red triangles on the image below).

The code looks:

pieceX = flooredDivision(gridX, pieceWidth)
pieceY = flooredDivision(gridY, pieceHeight)
innerX = positiveModulo(gridX, pieceWidth)
innerY = positiveModulo(gridY, pieceHeight)
if(innerY == 0){ // when the triangle is inside two pieces
	getOrCreatePiece(pieceX, pieceY - 1).updateTriangle(innerX, pieceHeight, depth, color, false)
}
return getOrCreatePiece(pieceX, pieceY).updateTriangle(innerX, innerY, depth, color, isMaster)

SVG optimization

To optimize SVG files, instead of creating path element for each triangle, triangles with the same color were mergerd into one path element. In the worst case, where all triangles have different colors, the file size would not be bigger than without this optimization.

Not optimized SVG paths:

<path d="M0,-1v2l2,-1z" fill="#ff0000" />
<path d="M0,1l2,-1v2z" fill="#cc0000" />
<path d="M0,1v2l2,-1z" fill="#cc0000" />
<path d="M2,0l2,-1v2z" fill="#ff0000" />
<path d="M2,0v2l2,-1z" fill="#b20000" />
<path d="M2,2l2,-1v2z" fill="#b20000" />

Optimized SVG paths:

<path d="M0,-1v2l2,-1zM2,0l2,-1v2z" fill="#ff0000" />
<path d="M0,1l2,-1v2zM0,1v2l2,-1z" fill="#cc0000" />
<path d="M2,0v2l2,-1zM2,2l2,-1v2z" fill="#b20000" />

Shading

Everything is done now. Let's remove the grid and add shading.

Shading makes the voxel look more 3D, not just a hexagon.


The problems

You may noticed ugly white gaps between triangles even if there is no grid. It may not look identical on different browsers.

The second problem is that when the browser is rendering the images, it takes a very long time when there are many SVG images.

One piece of map in SVG format that contains 128x128 visible voxels (about 32768 triangles) is the size of about 500KB. To create a 4096x4096 voxel world, it requires about 1200 such pieces that together are the size of about 0.5GB. That is the third problem.

The above problems forced me to render SVG files to PNG images. To avoid gaps between triangles I added shape-rendering="crispEdges" to path elements. That solved the problem but now the rendered images were pixelated. Since all images are SVG files I could render them bigger, and then downscale them. That resulted in non-pixelated well-looking images. After rendering every image to PNG (256x256 pixels) the total size of all images was only 20MB, which is 25 times less than storing the images in SVG format.

Back to pufferfish.pl