# Using connectivity information in the algorithm
The first versions of the fill tessellator were using the connectivity of the edges to determine the type of vertex that the sweep-line was processing at each step. For example, when looking at a vertex V, we'd ask the Path data structure it's previous and next vertices in order to determine the type of event (left, right, start, end, merge, split). working this way is very simple, but it falls down with certain edge cases, such as when two start events are interleaved (TODO, illustration).
The tessellator inherited this strategy from the computational geometry book in which the monotone polygon tessellation algortithm assumes an polygons with no self-intersection and therefore does not have to handle these types of problematic cases.
In order to fix this, the tessellator accumulates all edges that start at the current point and handle them all at once. This is adds a fair amount of complexity, but makes it possible to consider all possible cases including several pairs of edges intersecting at the same position.
# Floating point precision versus integer overflows
The tessellator was initially imlemented with 32 bits floating point numbers. This caused a lot of bugs in the intersection detection code, and with the way the sweep line accumulates edges at the current position by comparing positions. I would have saved a lot of time and effort if I had followed cairo and skia's footsteps and went with integer or fixed point coordinates from the start.
TODO: a lot of war stories to tell here. Variable precision is terribly bug-prone for this type of algorithm.
Another benefit of working this way is that the tessellator is now independent from the path data structure. The input is a sorted list of edges that does not need to retain extra information connectivity information, and can be constructed from an iterator or built directly with the PathBuilder interface. As a result, if a progam uses the tessellator with a custom path data structure (such as a half-edge mesh), tessellating does not require re-building a particular type of path object, as long as the custom path provides an iterator of path events or SVG events.
Integer and fixed point number arithmetic can also have recision issues when performing divisions and multiplications.
Multiplication can be computed without precision loss by multiplying the internal integer representation of the fixed point numbers.
consider fixed point numbers a and b with N bits of fractional part, a is equal to ```a.raw / 2^N```. Therefore ```a * b * 2^N == a.raw * b.raw```. we must remember that the result of the multiplication of the integer representations will have to be divided by 2^N at some point, but until then we postpone the precision loss.
It is best to avoid divisions whenever possible. For example when computing the comparison ```a / b > c```, expressing it as ```a > b * c``` avoids the precision loss, although it increases the risk of running into integer overflows.
If the result of a division must be saved for later, it is possible to store it as a fraction type which contains both the dividende and the divisor.
Now that the tessellator internally works with fixed point numbers, it is very easy to run into overflows because fixed point numbers can describe a much smaller range than floating point number. There's a tradeoff to make between how much precision we want in the fractional part and the size of the range. Currently the tessellator works with 32 bit fixed point precision numbers with 8 bits for fractional part (which is not a lot, but simple test cases were running into overflows with 16.16 fixed point numbers). Some computations are already implemented with 64 bit integers and the results is translated back to 32 bit fixed point numbers before being stored.
It's probable that the tessellator will move to 64 bit number or be made generic over the scalar type to let the user decide the range and precision.
The challenge, when trying to not lose any precision, is that every time the internal representations of two fixed point numbers are multiplied, we need to potentially double the amout of bits required to hold the result, which grows quickly over the 64 bits we are comfortable working with. So postponing all divisions to the end of a long series of computation is not always a viable option.
One way to mitigate the overflow issue could be to enforce tiled tessellation, with small enough tiles that the limited fixed point range is not an issue anymore. The tessellated geometry can be a lot bigger than the range can describe by adding tiles.
# Working with iterators
Path flattening used to be done in by PathBuilder, which meant that we would build and store a path object containing a lot of small line segments instead of the bezier curves. If all we need to do is iterate over flattened paths, storing the flattened path is not necessary. We can store the compact and resolution-independent bezier path and flatten it on the fly while iterating, which saves memory and does not require throwing away and re-building the path when the zoom level changes.