In the never ending quest to find something slightly better than a height map for terrain modelling, there is one obvious improvement: soften some of the jagged edges by splitting pixels along diagonals to cut off the 90-degree corners.
A well-behaved height map has no need of such things because it is all smooth elevation changes that turn into beautiful meshes, but the moment your game design becomes more ambitious you start running into problems. For example, suppose you want a road on your landscape and so you give certain pixels a color to indicate they should be rendered with a road texture. That creates a sharp line between the road and the ground, and whenever the road curves you will get jagged pixelated edges. One alternative is to make the edges fuzzy so the two textures blur together, but that may not be a look you want. Sharp edges can also occur when there are breaks in the terrain, such as vertical cliffs. The edges of those cliffs are bound to pixelate even with a very fine resolution height map, but allowing the pixels to be split diagonally can remove the 90-degree corners that makes the pixelation so obvious.
Unfortunately it is much easier to manipulate conventional raster images than it is to edit images with diagonally split pixels, since no existing image editing application supports that format. We need a special tool to draw the lines that will become the edges of cliffs in the height map, and a tool for marking the regions that will become things like roads.
Drawing the lines is relatively simple, since we can just start from a mouse click and follow the mouse as it is dragged, marking each edge as we go. We have 8 directions to choose from and we can simply choose whichever direction is closest to the angle from the current point to the mouse cursor.
Painting regions is far more complex, because it requires specialized rasterization algorithms that need to be custom designed and cannot be found directly on the internet. Even so, we can get inspiration from freely available rasterization algorithms such as: Midpoint Circle Algorithm on Wikipedia. That algorithm shows how to draw a circle without diagonal pixels, but we can simply create a diagonal pixel each time we take an x step. Unfortunately, drawing a circle isn't really our goal. What we need at minimum is to allow the mouse to drag a circle across the image and rasterize the resulting smear. Each movement of the mouse becomes a line segment and we need to fill the Minkowski sum of each line segment with the brush circle. It is difficult to find any references for solving this problem in normal rasterization, and still that would leave the problem of converting it into a diagonal pixel algorithm.
My current line of thinking is that we should combine the circle-drawing algorithm with the line drawing algorithm and draw the smear to a pair of one-dimensional arrays, one representing the left side and containing the minimum x values, and one representing the right side and containing the maximum x values, with the arrays being indexed by y values. The concept is similar to what is being done in this algorithm from Stack Overflow: how to rasterize rotated rectangle (in 2d by setpixel)
Assuming the line segment goes from A to B, we find the angle between A and B and imagine a line cut through the circle perpendicular to AB. One side of the circle will be drawn centered around A, and the other side of the circle will be drawn centered around B; we run the circle algorithm as normal and choose to center for each pixel just before the pixel is drawn based on its angle. Then we draw lines from ends of A's semicircle to the ends of B's semicircle.
Once we have finished drawing to the left and right arrays, we can fill in the space between the two arrays by drawing horizontal lines from the left side to the right side.
Is this over-complicating the problem? Has anyone seen anything like this before? Is there a better way to do any of these things?
