Contents
Introduction
For various reasons, I need to draw some lines on terrain in Unity. I’m not sure if these are the algorithms I’ll end up using, but given that I couldn’t find anything but pseudo-code for them (okay, I didn’t look that long), here they are in C# using Unity terrain splat maps.
Splat maps
There are a couple (literally, two) good old-ish articles on Splatmaps – try this one if you’re new to them. To actually apply colour to the splat map, in my (very) specific case, I use the following function. You’ll want to take this function, change it to apply to your texture indices, make it waaay better then send it to me. You know. Just because.
In my case, I wanted the texture in slot 3 (index 2) to be applied wherever I splat’d. I also clamped the boundaries, just to avoid any awkward crashes that left the terrain undressed.
To use the later anti-aliasing methods, this function takes a float, c, indicating the transparency. This is calculated very simply (too simply?) as a linear combination of old textures and new textures. When c is 1.0, we only splat, when c is 0 we do not splat at all (or at least we have no effect).
|
1 2 3 4 5 6 7 8 9 10 |
static void splat (int z, int x, float c, float[, ,] splatmapData) { x = Mathf.Clamp (x, 0, splatmapData.GetLength (0) - 1); z = Mathf.Clamp (z, 0, splatmapData.GetLength (1) - 1); splatmapData [x, z, 0] = Mathf.Lerp (0.0f, splatmapData [x, z, 0], 1.0f-c); splatmapData [x, z, 1] = Mathf.Lerp (0.0f, splatmapData [x, z, 1], 1.0f-c); splatmapData [x, z, 2] = Mathf.Lerp (splatmapData [x, z, 0], 1.0f, c); splatmapData [x, z, 3] = Mathf.Lerp (0.0f, splatmapData [x, z, 3], 1.0f-c); } |
In addition, all x and y are in terrain alpha map coordinates already – see the other articles if you don’t know how to get into those coordinates.
That’s all we need to get into the algorithms.
Bresenham’s Algorithm
Bresenham’s algorithm is an extremely efficient line drawing algorithm, with two drawbacks –
- It does not handle anti-aliasing (which has a wide range of implications).
- It can’t turn left. Gah, it can’t draw vertical lines. Not even lines that are very close to vertical.
If you can live with these restrictions, this algorithm will do well for you. This one is adapted from the basic algorithm found at its Wikipedia page, except that I splat on either side of the line as well in order to make it more visible.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
static void bresenham (int x0, int y0, int x1, int y1, float[,,] splatmapData) { float deltax = x1 - x0; float deltay = y1 - y0; float error = -1.0f; float deltaerr = Mathf.Abs (deltay / deltax); // Assume deltax != 0 (line is not vertical), int y = y0; for (int x = x0; x < x1; x++) { splat (x, y, 1.0f, splatmapData); splat (x, y - 1, 1.0f, splatmapData); splat (x, y + 1, 1.0f, splatmapData); error += deltaerr; if (error >= 0.0) { y++; error = error - 1.0f; } } } |
This produces something like
Although this looks fairly good (thanks Unity!), we get nothing if the line runs in the other direction.
Xiaolin Wu’s Algorithm
This algorithm is considerably more complicated (and not as fast), but given that it handles both anti-aliasing and vertical lines, I think we can forgive it that. This version is also based on the Wikipedia article.
This algorithm also uses a range of helper functions, which are listed first. As per the Wiki article, plot is replaced by splat which was given above.
Helper functions
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
int ipart (float x) { return (int)x; } int round (float x) { return ipart (x + 0.5f); } // fractional part of x float fpart (float x) { if (x < 0.0f) return 1 - (x - Mathf.Floor (x)); return x - Mathf.Floor (x); } float rfpart (float x) { return 1 - fpart (x); } |
The main algorithm is
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
void xiaolinWu (float x0, float y0, float x1, float y1, float[,,] splatmapData) { bool steep = Mathf.Abs (y1 - y0) > Mathf.Abs (x1 - x0); if (steep) { float temp = x0; x0 = y0; y0 = temp; temp = y1; y1 = x1; x1 = temp; } if (x0 > x1) { float temp = x0; x0 = x1; x1 = temp; temp = y0; y0 = y1; y1 = temp; } float dx = x1 - x0; float dy = y1 - y0; float gradient = dy / dx; // handle first endpoint int xend = round (x0); float yend = y0 + gradient * (xend - x0); float xgap = rfpart (x0 + 0.5f); int xpxl1 = xend; // this will be used in the main loop int ypxl1 = ipart (yend); if (steep) { splat (ypxl1, xpxl1, rfpart (yend) * xgap, splatmapData); splat (ypxl1 + 1, xpxl1, fpart (yend) * xgap, splatmapData); splat (ypxl1, xpxl1+1, rfpart (yend) * xgap, splatmapData); splat (ypxl1 + 1, xpxl1+1, fpart (yend) * xgap, splatmapData); splat (ypxl1, xpxl1-1, rfpart (yend) * xgap, splatmapData); splat (ypxl1 + 1, xpxl1-1, fpart (yend) * xgap, splatmapData); } else { splat (xpxl1, ypxl1, rfpart (yend) * xgap, splatmapData); splat (xpxl1, ypxl1 + 1, fpart (yend) * xgap, splatmapData); splat (xpxl1+1, ypxl1, rfpart (yend) * xgap, splatmapData); splat (xpxl1+1, ypxl1 + 1, fpart (yend) * xgap, splatmapData); splat (xpxl1-1, ypxl1, rfpart (yend) * xgap, splatmapData); splat (xpxl1-1, ypxl1 + 1, fpart (yend) * xgap, splatmapData); } float intery = yend + gradient; // first y-intersection for the main loop // handle second endpoint xend = round (x1); yend = y1 + gradient * (xend - x1); xgap = fpart (x1 + 0.5f); int xpxl2 = xend; //this will be used in the main loop int ypxl2 = ipart (yend); if (steep) { splat (ypxl2, xpxl2, rfpart (yend) * xgap, splatmapData); splat (ypxl2 + 1, xpxl2, fpart (yend) * xgap, splatmapData); splat (ypxl2, xpxl2+1, rfpart (yend) * xgap, splatmapData); splat (ypxl2 + 1, xpxl2+1, fpart (yend) * xgap, splatmapData); splat (ypxl2, xpxl2-1, rfpart (yend) * xgap, splatmapData); splat (ypxl2 + 1, xpxl2-1, fpart (yend) * xgap, splatmapData); } else { splat (xpxl2, ypxl2, rfpart (yend) * xgap, splatmapData); splat (xpxl2, ypxl2 + 1, fpart (yend) * xgap, splatmapData); splat (xpxl2+1, ypxl2, rfpart (yend) * xgap, splatmapData); splat (xpxl2+1, ypxl2 + 1, fpart (yend) * xgap, splatmapData); splat (xpxl2-1, ypxl2, rfpart (yend) * xgap, splatmapData); splat (xpxl2-1, ypxl2 + 1, fpart (yend) * xgap, splatmapData); } // main loop if (steep) { for (int x = xpxl1 + 1; x < xpxl2; x++) { splat (ipart (intery), x, rfpart (intery), splatmapData); splat (ipart (intery) + 1, x, fpart (intery), splatmapData); splat (ipart (intery), x+1, rfpart (intery), splatmapData); splat (ipart (intery) + 1, x+1, fpart (intery), splatmapData); splat (ipart (intery), x-1, rfpart (intery), splatmapData); splat (ipart (intery) + 1, x-1, fpart (intery), splatmapData); intery = intery + gradient; } } else { for (int x = xpxl1 + 1; x < xpxl2; x++) { splat (x, ipart (intery), rfpart (intery), splatmapData); splat (x, ipart (intery) + 1, fpart (intery), splatmapData); splat (x+1, ipart (intery), rfpart (intery), splatmapData); splat (x+1, ipart (intery) + 1, fpart (intery), splatmapData); splat (x-1, ipart (intery), rfpart (intery), splatmapData); splat (x-1, ipart (intery) + 1, fpart (intery), splatmapData); intery = intery + gradient; } } } |
This produces something that looks a lot like:
Although this looks quite faded, this looks more effective at a lower zoom and could (hopefully will be) improved as discussed below.
Improvements
In my case, I’m drawing a line with a width and a height – to be precise, a rectangle. My code is drawing from one corner to the opposite corner, so actually drawing out the rectangles would no doubt produce a better result. Hopefully to come.
End!
Any questions / improvements / spam, feel free to get hold of me in the comments. Except the spam. I’m always watching.
Leave a Reply