Computational complexity (and possible optimisation for ImGui code)

[jamesthomasgriffin]

Some general thoughts and possible change

A stack of transformations is contructed per-frame and when a value or (second) derivative is required at a particular point the whole stack is traversed. So the complexity is O(n^2). When the positions at which values/derivatives are required are not known in advance, this is the best we can do. If all transformations are matrix transformations then there is the possibility of computing the transformation and derivatives for all possible parameters as the stack is being built, however the number of second derivatives could also grow as n^2 so unless the number of parameters is known to be << n the complexity of this approach is n^3.

On the other hand if we do know the positions to be computed and the variables that need to be differentiated against in advance then these can be computed as the stack is built and the complexity is linear in n.

Application to ImGui code

The second derivatives are only used for moving an activate point which is not activated, this means the point is unique and the parameters are changed from the second frame that it is active for. The reason for this is to allow for z-ordering when control points are overlapping. As a result we know in advance the position of the control point (lagging by one frame if it moves) and the variables associated to it (from the previous frame). These variables can be differentiated against as the stack is constructed.

The first derivatives are only used for the unique active control point and when plotting derivatives, these could be requested for the next frame rather than supplied at the call. However the values of the current transformation are required for each control point whether active or not. Storing every control point position for the next frame is feasable but increases the complexity to O(n^2) again.

If we now restrict to transformations which can be represented by 4x4 matrices then it is no longer necessary to store every point as the current matrix representations and the required derivatives can be stored in the stack. This restriction does not affect any of the ImGui style calls currently implemented. There is an implicit x ---> x / x.w at the end of the stack, but this can be handled separately.