Telegram Charts Contest

This is how it should look like

So one day I got a message from Telegram about contest that they going to hold. Above I attached gif of example that they provided. Yup that’s it, no more information about how it should work, just the gif. App can be for iOS, Android or web. I decided to make it for iOS — why not. This is the story about app that I made, techniques that I used, and architecture. One note is that the version that I describe here uses Metal as charts renderer. For contest I used CoreGraphics — because of two kids and ton of work I had no chance to finish it in time. This is going to be long (duhh), so let’s go.

Table Of Contents

Preparation

Architecture

  1. Data Source
  2. Render stage
  3. Presenter

Implementation

  1. X Coordinates
  2. Y Coordinates
  3. Highlights Rendering
  4. Info board
  5. Charts Rendering

Next contest

Conclusion

Preparation

First of all let me describe the architecture that I used. There were few iterations of changes, but final result looks like this:

It is split into 3 parts.

  1. Render Stage. This part contains all the code that provides environment for rendering.
  2. Presenter. It configures all parts that are required for rendering
  3. Data provider. It is responsible for providing data that should be displayed.

It can remind you of MVC (MVP, MVVM, MVCCPVMMP?), and it kinda is.

Main controller creates presenter and data provider and then just places the view of charts (provided by presenter) where it wants it to be displayed. So for this telegram charts we will have two presenters, one for big charts view and one for small one, and one data provider, as data that they display is the same.

Before going into details, I want to introduce concept of viewport. This concept is nothing new and all games use it. Basically it is the camera inside some coordinate space. In our case it is the camera in charts coordinate space, that we will move, contract, expand, and move. Then we will just display the part of the coordinate space that it sees. It will greatly simplify things for rendering. It will let us do really simple rendering loop: view controller updates view port of presenter (let’s say user moved slider), presenter fetches data slice for this view port from data source. Adjusts view port, for example provided view port can not fit data vertically, then it updates viewport height. And then just passes this view port to render stage, and updates renderers with new slice of data. Thats it, now renderers have new portion of data to render for viewport and also have new viewport to render data in.

There are few subtleties that I will describe later, but the overall flow looks exactly like this.

For your convenience I attached diagram bellow that shows how components interact. Do not get scared, I will describe all parts and why we need them.

Main components

Now let’s go through each part of this architecture and how it is used.

Architecture

Data Source

This component is the most straight forward one and its main purpose is to provide data for presenter. It is created by external users of presenter and provided to it. Presenter can ask for slice of charts in some range (visible area of view port), and data source should give this slice.

What is intricate about it is that I wanted to take into consideration that there can be a lot of points on chart, maybe thousands. So I decided to have some logic to sparse data. The logic is like that. First of all I want to have no more then, let’s say, N points visible for chart at once. To achieve this we can have few versions of chart data for each scale. For example when view port is at its min width (and at this level of scale no more, then N points are visible), we can have version with all points. When user starts to scale the width of view port, at some point more, then N points would be visible. In this case we eliminate points from chart data until we get less then N points for view port. And so on. It means we will have few scale levels and for each we would have some version of chart data with different level of sparsity. The more area user can see, the more sparse version of charts data we show.

Ok, so how to do sparsing now. The most popular is Ramer–Douglas–Peucker algorithm. It is pretty simple in nature. You take first and last points and add them to the result. This two points make a line. Next we iterate over all points between these ones and select the one that is furthest away from the line they make. This distance is considered as importance and if it higher, then some value that was specified as input to algorithm then it is added to result. Then we recursively repeat these steps in case point was added.

This algorithm does not fit my needs, as I want to pass max number of points (N), and algorithm should give me data that has N max important points. Also recursive nature of algorithm can overflow stack.

The adopted version of this algorithm looks like this. We have two data structures to hold computation results. First one is just array that holds range in data that we want to consider but did not find most important point yet. Another one is a heap, that holds ranges of data for which we already calculated most important point (heap max would have range with point, that have point is most importance among all ranges). Until we have any data in any structure we iterate. First if we have data in ranges array, we calculate important point for each range and put it into the heap. When there are no more ranges in array, we pop one range from heap and add its point to result (It means it is the most important point among all ranges that we calculated by far). We create new range by splitting considered one with this point and add it to ranges array. Then everything repeats. Let me give you and example.

At start we have one range, that is the range that first and last point make. We put into ranges array. Algorithm takes this range out of ranges array and calculates important point (let’s call it P) and puts this range into the heap. Now we have no more ranges in array, so we start popping the heap. We pop the range we’ve just put there, put the point we’ve just calculated into result and make two new ranges (first, P), (P, last) and put them into ranges array. Because ranges array is not empty, we start processing it. Again, for first range (start; P) we calculate most import ant point (let’s call it A) and same for the second range (let’s call its point B) and put them into the heap. Without loss of generality we can say A is more important, then B (it is further to the line made of (start, P), then B to the line made of (P, last)). Ranges array is empty, and we start popping heap. Because A is more important, then B, we get its range, we add A to result, make two new ranges to array and start processing array again. This all repeats until all data points are processed or we found N most important points.

Why does this work? Well this is actually pretty simple, we always add most important point out of all available first. To be more strict, heap top always points to the range with most important point.

Original algorithm has O(N²) complexity in the worst case and O(Nlog(N)) in average. It is doing very similar thing to quick sort so no surprise here. I am not 100% sure about mine but it should be like this. There will be no more then N/2 ranges and each would get pushed and popped once (heap has log(N) for both) which would give O((N/2) * log(N/2) + N²) in the worst case which is same as original one, and O((N/2) * log(N/2) + Nlog(N)) on average which also same same as original one.

This is mostly it. We have sparsing algorithm, now to have different levels of sparsity we create L (number of scale levels) variants of data. Then each important point, that we found, we add to every data variant. If some variant is full we stop adding points to it.

Render stage

Render Stage is the part that tries to hide all platform dependent parts of rendering by providing convenient api for it. What it means is that if I would want to make charts app for android, basically only this part would change, and also specific rendering calls (like metal or CoreGraphics), and other parts I would just copy paste and convert to Kotlin or smth like that.

First of all it provides main view that presenter would pass to external users, animator that can be used for non Core Animation parts and also dimensions converter, that would convert coordinates from viewport space to main view coordinate space.

At start I did not know where all logic of rendering would take place and which component would control it. Also I was not sure what kind of interface that components would require to perform theirs tasks. Thats why I decided to delegate as much of such logic to external components and only provide some interface that they would use and I would add extra capabilities to this interface when needed. Thats where Render Controllers come in. Render Controller is an external component that users of Render Stage would add to Render Stage and Render Stage on its part would provide some interface — Render Environment — that Render Controllers would use. This level of indirection makes evolution of Render Stage and Render Controller to be more or less independent.

I also wanted to try several rendering techniques. Like try to render charts with Core Graphics and Metal. Also to have several rendering options at a time, like use simple UILabels and also render with Core Graphics. It was challenging, because different rendering techniques require different tools to render, and sometimes even different render methods. Like drawing with Core Graphics and just laying out UILabels. Both are some kind of rendering but have different tools to do so. This is where I introduce Render Surface and Renderer. Render Surface is some abstract container that we can inflate with Renderers and then Renders can display something on that Render Surface. Internally Render Surfaces can have nothing in common, the only thing that is required from them is to provide a UIView instance for Render Stage, which Render Stage can add to main view. To emphasize how different Render Surfaces can be here is an example with two that I use: ViewRenderSurface and CGRenderSurface. First one lets you add renderers, that would manage some UIView by adding subviews to it and laying them out (constraints also supported). I use such renderers to manage y/x coordinate labels. Another one lets you add renderers that would use CGContext to draw lines or what ever you want. Event though they are different in nature, there is same api in Render Environment to create Render Surfaces and attach Renderers to them. Each Render Surface can be different, have different params etc. I introduce RenderSurfaceManager, thats can be registered in Render Stage, and which’s main purpose is to create Render Surfaces, based on RenderSurfaceParams provided to it.

The last piece of the rendering puzzle is not really important, but can be beneficial in terms of performance - Render Target. All Render Surfaces are grouped into Render Targets, to which Render Controller is attached. It is really just a collection of Render Surfaces request by Render Controller. The benefit is that when controller requests rerendering (some data changed or other stuff), we would invalidate only its specific Render Surfaces.

This is basically it for architecture of Render Stage. To recap here is how its (Render Stage) usage can look like. Each user of Render Stage can add Render Controllers to it. Render Controller will be attached to Render Target and also will get Render Environment component that it can use. To draw something render controller, using render environment, request render surface of required type (UIView, CoreGraphics, Metal currently supported), creates renderers that would perform rendering, and attach renderer to Render Surface. Thats it, renderer can render using render surface.

Few words about viewport and its update. Render Stage holds viewport and provides ground truth about its state. External users can request its update and this update can be animated. Each update is reported to Render Controllers. This is all they need to do proper rendering… almost. Actually funny part is animated update.

Two things here that should be handled delicately. The first one is that each side of view should be updated independently. Thats it, user can request to update view port x to say X1 without animation, and also update y end of view port with animation. This is actually what this chart animation requires. You can see that user can slide back and forth and x should get updated immediately, but y coordinate does not depend on it, it should get updated based on max y point of a chart. So you see that updating viewport x coordinate should not stop y animation. To solve this requirement external users can update different sides of view port independently. Like ask for x immediate update and also ask for y to be updated with animation (or just skip this value in update).

Another one is that it is not enough for controllers to be just notified on actual view port update (and we will see why when discuss y labels animation). They also should be notified of target values of view port that animation drives to. Say we update view port y with animation, then controller would first get notified that view port will be updated from old value to new value. And then each actual update would also notify it.

Presenter

Presenter is the component that sets up everything up. It creates Render Stage, creates all required Render Controllers, registers them in Render Stage, adds gesture recognizers for interactions. After this its role is mostly done.

Specifically for this contest presenter would create 4 controllers — Y coordinates controller, x coordinates controller, charts controller, no data controller. Register few gesture recognizers in Render Stage, to handle highlight of chart. Then for every view port update, it updates Render Stage view port x and x end (y coordinates are driven by charts data) based on provided view port. Fetches data for view port. When data arrives it resolves view port max Y and updates Render Stage viewport y if needed (data maxY is lower or hight, then previous).

Implementation

Now I will describe implementation that uses framework above to achieve the same result as on first gif. I split this into 5 parts: X Coordinates, Y Coordinates, Highlights Rendering, Info board rendering, Charts Rendering.

X Coordinates

This logic is implemented in XCoordinatesController and uses one render surface of type View. Requirements — based on the gif that was provided I can say that every Nth coordinate should be labeled and number of such coordinates that fit into viewport should be in range 3–6. If we can fit more, then 6 coordinates, then every 2nd labeled coordinate should be removed, and if we can fit less then 3 coordinates, then we should add extra labeled coordinate between each pair of currently displayed labeled coordinate. 3–6 range is just my choice, another one can be 4–8. It is obvious that max should be double size of the min, as every time we decide that there are too many labeled coordinates that viewport can fit, we remove half of them, and vice versa if we want to add labeled coordinates.

So when we settled requirements, implementation is straight forward and there are few ways to do it. You can take width of your data and split it in two until required amount of coordinates are fit into the view port. Then use this distance to label coordinates — basically each labeled coordinate will have N * distance x coordinates, where N is an integer number.

I actually took different approach that does not depend on data. I basically calculate viewports width power of 2, like if it is 64 then I would get 6, let’s call it P. And then distance to place labels is 2^(P - 2). It means I should get roughly 4 labels for view port. I actually want a bit more, so I actually calculate this power of 2 for narrowed viewport width: width * 0.7. This ways our actual view port would get extra labels. This one is just empirical value I found that fits well.

The last one thing to take into account, is that actions of adding extra coordinates and removing redundant ones, should get triggered for different viewport width. What I mean is that if there is viewport width value that triggered action of adding coordinates, let’s call it W. Then action of removing coordinates should take place at say W - x, where x is some small value (i take it W * 0.05). This will help to overcome some issues with back and forth jumps between number of labeled coordinates.

Y Coordinates

Well, this one is really weird at took some time to configure right. Let me try to settle requirements first. We should label 6 Y coordinates, one of them is always at y = 0. Another 5 are based on viewport height and should always have fixed position in screen coordinate space. We also should draw line for each such coordinate. When view port height changes to some value H, then we should label five new coordinates, based on new height. Show new labels with fade in animation, remove old ones with fade out animation.

Ok, I can not argue that animation on the gif looks pretty good, but it shows us perfect world scenario. User slides, new max Y in chart data appears. We make transition to new y labels. Unfortunately in real life user can change viewport really quickly, and then we can have a lot of y coordinates transitions, which will look like crap.

So here is the implementation that tries to do as much as possible. Here controller uses two Render Surfaces — one for labels, which is ViewRenderSurface, and another one for lines, which is CGRenderSurface. It means y labels will be just UILabels and lines will be drawn with CoreGraphics.

Calculation of y coordinates is straightforward, we just calculate coordinates between 0 and max Y of viewport. The difficult part is transition. As we see height of view port always changes with animation. This means if we will calculate coordinates based on current viewport height, then each animated update would trigger cascade of labels transitions. This is where we use the part, that Render Stage notifies controllers about target values of viewport when animation starts. Like if we animate height from 100 to 150 then Render Stage would notify about this transition and then start animation. When Controller gets this notification, it calculate new y labels for target viewport height and starts animation. This solves part of the problems, but there is one more - the one where viewports height changes rapidly. For example if user changes viewport position back and forth, then it is a big chance that max Y of charts data would go back and forth between some values. I solve it by ignoring updates until some portion of transition finished, and then start new transition. I postpone till 50% of transition finished and then start new one if needed. From my point of view this works pretty good.

Highlights Rendering

Highlights, charts and info board are handled in ChartController. I wanted to split them to different controllers, but when you think about it, there is no way to do so, as highlights and info board should be rendered at the same place where charts are rendered. This is because highlight points should be places exactly on chart lines, and thus only the logic that calculates how chart is rendered can tell us coordinates for highlight points. Same with info board, as it depends on positions of highlight points.

Highlights are rendered using two surfaces CGRenderSurface, which means they both will be rendered with CoreGraphics. Again, there is nothing fancy about this process — get tap coordinate, find closest point on charts, draw vertical line at this coordinate and for each chart draw a circle there. Is this enough? Not really. I want to remind that we sparse data that is rendered, and this is why we can select a coordinate on chart that is actually cut out by sparser. To overcome this problem we use linearity of rendered data. Let’s say we tapped somewhere and we calculated, that point P is the closest point to that tap. If this point was not cut out, we just draw circle at coordinates of this point. If this point got cut out by sparsing algorithm, then we find neighbours of this point in sparse version of data and using linear equation find y coordinate of x value on line made by rendered neighbours. For example we have points (1;1) (2;3) (3;2) (4;10) (5;5). Sparse data has these points (1;1) (4;10) (5;5) and we selected point (3;2) which is missing in sparse variant of data. Then (1;1) and (4;10) are the neighbours in sparse version of data. Now we find y value for x = 3 on line made of (1;1) and (4;10):

k = (10–1) / (4 —1) = 3
b = 1 - k * 1 = 1 - 3 * 1 = -2
y = k * x + b = 3 * 3 - 2 = 7

So this is the coordinate for highlight at point (3;2): (3; 7).

Basically thats it. Now we can render circles and vertical line.

Info board

Info board is this small board that you see when you select some point on chart. ChartController handles it, and it is rendered using ViewRenderSurface, so it is going to be just a view.

Again, there are no obvious requirements for this board, but I decided that it would be cool if this board would have feature, that it never overlaps highlight circles. This one was a bit challenging. Main code for this is in layout method of HighlightViewManager. First of all I use target view port to layout this board (viewport that animation is driving current viewport to, or current viewport if there is no animation). This way we adjust board position based on the state of the screen, that viewport strives to. Next logic avoids overlapping of highlight circles. Basically there are 2 cases to consider:

  1. We do not overlap highlights if we place views center where highlights are. In this case we are done, we do not overlap anything, we are good to go.
  2. Here we overlap circles and have to move board to the right or left. We move board to the left if by doing so we do not overlap screen x. Otherwise we move it to the right.

The last step is to adjust board x position, to prevent screen overlap. We can do this as a last step, because if we got into case 1, then we can freely move board, and it won’t overlap highlights. If we in case 2, then we already calculated side that does not overlap screen.

Charts Rendering

Charts rendering is handled in ChartController and was the easiest part that I made using CoreGraphics, using CGRenerSurface. This is the implementation I sent to Telegram. But then I decided that I should try out metal.

This is the first time I used Metal, and I have to give credit to apple guys, this time, they did a great job. It is so easy to use. Every time I implemented something using OpenGL, there are so many curses in my had. This black screen that you have no idea how to fix and weird errors from OpenGL… jeez. Metal if absolutely different, straightforward setup, passing params to shader is peace a cake. Though several features that I could have used are missing, like geometry shaders, but they are not mandatory.

One thing that you should take into consideration if you decide to check how it works, is that I create limited data buffers in renderer. It means if there are more points, then it can comprise, you will have problems :) . The solution is pretty straightforward — using some kind of buffers pool, that renderers should take buffers from. But this is what I left unfinished. Also I used apples tutorial example as starting point, so you can stumble on parts of it in the code. Ok, so let’s see how metal rendering works.

Rendering with Metal uses MetalSurface, rendering happens in MetalChartRenderer, shader file is ChartShaders.metal. The rendering cycle looks like that: ChartController gives new data to render to renderer. Render Surface calls renderer to rerender data. Renderer generates geometry for line filling in vertex buffer and index buffer. Passes viewport and screen size as extra params, shader does all the rest.

The hard part about rendering line is its width. I used this algorithm described by paul.houx. Few words about terminology: I will use perp to denote perpendicular vector to some other vector, and norm will denote normalized perp. Ok so, basically algorithm requires 2 perps for each point (Let’s call it Current). First perp is vector that is perpendicular to vector made by Current point and its left neighbour point. Another perp is perpendicular to vector made by Current point and its right neighbour point. Calculations are straightforward:

perp1 = (- (Current.y — left.y), Current.x — left.x)
perp2 = (- (right.y — Current.y), right.x — Current.x)

This comes from the fact that perp to vector V has coordinates (-V.y, Vx), which is easy to check using dot product:

V · perp = V.x * perp.x + V.y * perp.y = V.x * (-V.y)+ V.y * V.x = 0

And vector from point A to point B is just (B.x - A.x; B.y - A.y).

For first and last point we just take pseudo points with coordinates shifted in x: FirstPseudo(First.x - 1; First.y), LastPseudo(Last.x + 1; Last.y).

For each point we pass its coordinates and 2 vectors we just calculated. Remaining calculations are done in vertex shader.

One thing that this algorithm does not take into consideration is that we can scale up or down. Our viewport can change and we still should have same line width.

Every point in vertex shader goes through several transformations and the output should convert vertex x and y coordinate to [-1; 1] range. For example if we have viewport with x start coordinate 100 and x end coordinate 500, and point has x coordinate 100, then vertex shader should return -1 as a result for point x coordinate. For point with x coordinate 300, vertex shader should return 0, and so on. What it means is that points will get scaled coordinates as an output, and if viewports width is not the same as height, then we can not really use algorithm directly, as perps won’t be the same in scaled versions of points.

To circumvent this problem we will use linearity property of perps under linear transformations of points. To see how it works, let’s say we have two points, say P1 and P2. The perp for this points can be calculated the same way as we did before.

(-(P2.y — P1.y), P2.x — P1.x)

Ok so lets scale each coord separately and translate them (which is done by shader) and then calculate perp again. We have:

P1' = (P1.x * cx + ox, P1.y * cy + oy)
P2' = (P2.x * cx + ox, P2.y * cy + oy)

where cx, cy are scale values and ox, oy are offset values. Then we have

(-(P2'.y — P1'.y), P2'.x — P1'.x) =
(-(P1.y * cy + oy - (P1.y * cy + oy)), P2.x * cx + ox - (P1.x * cx + ox)) =
(-P1.y * cy - oy + P1.y * cy + oy), P2.x * cx + ox - P1.x * cx + ox) =
(-(P1.y + P1.y) * cy), (P2.x * cx - P1.x) * cx)

Which tells us that to calculate perps for this transformed points we should take original perp, and multiply its x by y scale (cy) and multiply y by x scale (cx).

In vertex shader each chart point get scaled like this: position = (position/viewport) * 2 - 1.0. It means, that we should scale passed perps by viewport.yx * 2. As we see from calculations x and y scale are swapped. We can skip multiplication by 2 as perps normalization would discard it. Then we apply algorithm above. That’s it… at least thats what I thought. Actually there is one more thing that I missed first time. After vertex shader gives back converted point, it actually would get transformed again for screen size. Basically this transformation would take -1 coordinate to 0 screen coordinate and 1 to screen.(width|height) coordinate. It means we should take this into consideration. To make it work I just convert final points coordinates and perps to screen coordinates, apply algorithm, and then convert points back to [-1: 1] range. Probably there is a way to simplify this, but I am not sure.

Ok, we are done, we have our Metal renderer!

As a result I get pretty impressive performance, which works great even on iPod.

Next contest

Right now Telegram started next contest, which I will not be part of as I do not have a lot of spare time now. But seems like all new charts can be rendered same way with Metal using same algorithm with ease. Only difficult part that I see there is performing transitions.

Conclusion

Even though I did not win the prize, because of one subtle bug that I missed in my implementation, the performance (without Metal) was qualified as 9/10. I am very glad that I decided to participate in competition as it was quite fun and reminded me of times when I was a student :)

Here is the link for source code: https://github.com/AndreLami/TelegramCharts