Let’s see now, where do I start? I only have about 10 hours to complete this article before leaving for Belgium with my classmates, let’s hope I have time to say everything I want to before taking off. =)
Using the engine
You have (so far) two important tags to work with. They are <Drawline> and <Drawshape>. To define a polygon, you give <Drawline> a path-argument. In that argument you define the points you want the lines to be drawn between like this: path=”X1.Y1: X2.Y2: X3.Y3: …..“. The polygon will automatically be closed with a straight line from the last co-ordinate to the first unless you set autoclose=“no”. To zoom in on your polygon, use the zoom-attribute. Its default value is 2, at which the polygon is drawn at scale 1:1.
Filling the polygon is very easy. To fill with a single colour, use the fillcolor-attribute like you do with the color-attribute for a <font> tag. If you want to fill the polygon with an image, use bg-image=”the url to the image”. You can even move the image around using bg-position=”X,Y”. And if the fill-algorithm fails to fill the correct area(s) of your polygon, there’s the Fill=”X1.Y1: X2.Y2: X3.Y3: …..“-attribute which tells the algorithm where to start filling.
You can’t draw smooth shapes using only lines, so it’s possible to tell the engine to draw a curve instead of a line between two points. We have two types of curves to choose from: the Bézier curve and a cosine-smoothed curve. To use a Bézier curve, append “.b” to one of the coordinates in the path-attribute so it looks like this: “Xn.Yn.b:”. Then the algorithm will draw a curve using that and the next three coordinates as control points.
The other type of curve can be drawn in two ways, either by smoothing the position of the x coordinates or the y coordinates. You decide which method to use by appending “.cy” or “.cx” to one or more of the coordinates in the path-attribute, just like with Bézier curves. This type of curve only needs a start- and an end- co-ordinate though. This type of curve is usually very good for smoothing the lines between values in a graph.
There are further options when drawing polygons with <Drawline>. You can set the width of the lines using the linewidth-attribute. You even can make the lines dotted using the dotted-attribute. For example: dotted=”3,5” will give you a three pixel long space between each five pixels long dot.
What about <Drawshape> then? It does almost the same thing as the <Drawline> tag and it has almost the same attributes. The difference is that the path-attribute is replaced by a shape-attribute. You can set the shape-attribute to most common shapes like octagons, squares, circles, triangles etc. And you can set their height and width using the areaheight- and areawidth- attributes.
Drawing lines and curves - pixel by pixel
The line-drawing part of the engine uses two or three algorithms, depending how we are counting. The first algorithm is used for straight lines. It is based on the Bresenham algorithm which steps along the longest axis of the line. This means that no matter what the line looks like, we will always find only one pixel per x or y value.
The other line-drawing part is used for drawing curves. Currently, the vector engine can draw two types of curves. One is a Bézier curve, and the other is a cosine smoothed line. A Bézier curve has four control points. The curve only passes through the first and last points, the two other points define how the curve bends. Bézier curves are very useful since they can define many types of curves, from S-shaped curves to loops. A Bézier curve can be drawn using a parametric cubic polynomial where t goes from 0 to 1:
a1-3 and b1-3 are calculated using the control points but including too much math here would just confuse things.
The cosine smoothed curve is calculated in a similar way using either
xt = x0+(x1-x0)(1-cos(p*t)) and yt=y0+t(y0-y1)
yt = y0+(y1-y0)(1-cos(p*t)) and xt=x0+t(x0-x1)
depending on along which axis you want to smooth the curve.
The curves produced by these formulas are often not continuous because the distance between each pixel on the curve is determined by the value you increase t with in each iteration.
The formulas will also give you too many points if you use a too small value on t, which creates a very thick curve. Therefore, the algorithms are designed to calculate two pixels ahead of what it is drawing, while adjusting t and removing bad pixels to draw a nice curve.
Since the engine uses <div> tags to represent pixels, we want to produce as few tags as possible, or the browser will choke when trying to render the polygons. This can be done by stretching some of the tags so they cover more than one pixel. A good example is a horizontal or vertical line. We could use 100 tags to draw a 100 pixel wide or high line, or we could use just one. And since sloped lines, and also curves, are composed of many small horizontal and vertical lines, there are many tags to save. To accomplish this, the algorithms “remember” the position of the last calculated pixel. If the next calculated pixel is located directly above/below or to the left/right of the last pixel, then increase a variable that tells how wide or high the last pixel is. When the next pixel is not located on the same line as the last one, print out the last pixel and start over with the new one.
We also want to minimize the amount of text each <div> tag contains for even higher rendering speeds (and readability of the generated HTML code). This is done by putting all the common style-attributes of each tag into a stylesheet. The <div> tags are linked to the stylesheet using a unique random id.
Since we want to fill these polygons later on, we create a two-dimensional Array representing the polygon. In this array we mark each pixel we’ve drawn so we’ll have a huge grid or matrix containing each pixel in the polygon. The grid will become quite big, but accessing it for information on pixel locations is much faster than looking through all the <div> tags we generated to see if any of them are located at the coordinates we want to check. The grid is also useful when filling polygons that have dotted contours. Since even the pixels that are not drawn are represented in the grid, there’s no problem to fill the polygon. To mark a pixel in the grid, we simply place the line’s id at Grid[Y][X]. If there already is a different line id at that location, we place an “X” there instead to mark those coordinates as an intersection. I’ll explain why we do this later. Now it’s time to move on to the filling algorithm.
Filling the polygons
This algorithm I have designed myself. I have not seen an algorithm like it before and the end result is very similar to what a Flood Fill algorithm would produce, but it’s much faster. The idea behind Flood Filling is that you place a seed at a point in an area of the polygon you want filled. Then the seed expands and fills the pixels above/below and to the left/right of it. Those pixel also become seed points and will start to grow in all directions where there has not been placed a pixel before. This continues until the seeds encounter a pixel of a different colour, normally the colour of the lines the polygon was drawn with (the contour). Then those seeds “die” and they no longer produce more seeds. When the polygon is completely filled, the algorithm will have visited all of the pixels inside the polygon at least two times to check if they are already filled. My algorithm only visits the pixels inside the polygon once, and that’s when filling them.
My idea was to let the first seed figure out at which x coordinates the closest contours of the polygon are located, at the current row (y co-ordinate). Once that is done, fill the space between them and “split” the seed in two parts. One is placed one row of pixels up and will continue to follow the contours upward to fill that part of the polygon. The other part of the original seed will follow the contours downward to fill the other section of the polygon. This way we make sure no area is filled twice.
To fill a convex polygon, one initial seed is enough, no matter where it is placed. For concave and complex polygons, we have to consider a special case when following the contours. This special case reveals itself when one (or both) of the contours “turn” and can no longer be followed in the direction (along the y-axis) the “follower” was going. Then the algorithm starts looping across the row in search of the x co-ordinate at which the line turns back and continues in the direction the follower was going. When the x co-ordinate has been found, which is likely to happen since polygons are mostly closed, a new seed is planted in the gap between the x coordinates before the area is filled and the followers continue in the same direction. This new seed already knows the location of the contours and it can therefore follow them in the opposite direction of its “parent” seed to fill that area of the polygon.
Something similar happens when the algorithm detects a new contour between two contours it’s following. When this happens, a new seed is planted wherever the distance between the contours is above one pixel. The new seeds start to follow the contours they were placed between in the same direction as the parent seed did.
One important thing to notice about this algorithm is that it always tries to stay with the same lines when it’s following a contour. This means that it doesn’t just jump to the next closest pixel of the contour if it isn’t part of the line it’s following. The algorithm only switches to another line when it’s currently “standing” on an X. For an example, look at pixel B2 in the image to the right. A Flood-Fill algorithm would have stopped at C3 unless it was also growing diagonally. But that would mean it would have also “leaked” to A3, B5, C7, E7, F6, G5, G3, C1, E2 and their neighbours.
Here I must make an abrupt end to this article. My time is running short but I think I have covered all areas needed to clarify what the vector engine is capable of. It sure is a powerful tool, and I doubt its potential has been fully discovered yet. I’m still tinkering with a few things before this version is released. The previous version isn’t as sophisticated but it’s available at http://www.naltabyte.com.
If you have any further questions about the vector engine, feel free to contact me on H dot Danielsson at gmail dot com.