ADFs - the heart of the Saffron Font engine
I was reading up on the Saffron font engine technology today, and as I was skimming this paper I noticed that the technology seems to use quadtrees and octtrees, which are popular concepts in collision detection space partitioning. Basically, it works on the principle of scanning an object, and analysing the amount of detail in it, and only storing higher resolution data of it if needed. For example, if we have a 200×200 square, and there’s only a 25×25 box in the top right hand corner, we can ignore 3/4 of the scene by dividing the square by four and discarding the empty sections. We can then go further, by dividing the one occupied square by four again, and again, ad infinitum. This lets us draw and query the scene much more quickly, and means that less data is needed to represent it. It also means that the coordinates themselves will be limited to a smaller range, because they only need to be stored in terms of the coordinate space of the cell they are in. This can potentially cut the size of the data in half again. ADF seems to use the corners to represent edges, so it can avoid too many levels of recursion into a shape, while still maintaining the same level of quality.