# 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" />