Geogebra Tool Support in Kig

Hello !!  In this post I will be describing my latest progress in the Geogebra Filter that we are creating for Kig.

After a lot of hiccups, it finally seems that we have found a proper implementation which smartly handles both Geogebra worksheets and Geogebra tools.

Although the planning had been done a long time ago and a draft implementation which successfully read geogebra’s tools into Kig had been done, David (David Narvaez , my mentor ) was not happy with it ( and neither was I .. ) since the code looked dirty ( with a lots  if-else’s scattered everywhere. Reading Geogebra worksheets and tool-files both require very similar XSLT manipulation and parsing and the challenge was to smartly create an implementation which could handle both  ( Geogebra worksheets and Tools  )  with the least code duplication and with a flexible and sensible design.

A lot of attempts were made by both David and me in reaching the implementation that we have today. In my first attempt I was able to create an implementation which read tools correctly but the tool file ( .ggt file ) had to be opened from the open-file Dialog ( and not from the Types Dialog in Kig ) .  Again in my second attempt I was able to enable the opening of tool files from the Types Dialog instead of the file dialog. This was more accurate in behaviour since in Kig ( and also in Geogebra ) tools are maintained from a separate dialog and not from the file dialog.

Previously we had just one class to handle Geogebra files- KigFilterGeogebra class which inherited from both KigFilter and QAbstractXMLReceiver class. The problem that created was that if we extended the class to read tools,  a lot of complicacy was introduced in the functions. Then we separated the QAbstractXMLReceiver part of the KigFlterGeogebra class and moved it to a new class – GeogebraTransformer class which reads the transformed XML file and generates the object-tree of the document. Both The GogebraFilter and the GeogebraToolFilter classes use an instance of this Transformer class to get the object-tree. This way the code duplicacy issue was solved and also simplified the Filter classes.

After just a little polishing, our filter will enable Kig to read Geogebra tools !!

Geogebra file support in Kig ( GSoC Report )

KIG currently has filters for various formats ( Cabri, Dr-Geo, KGeo, KSeg ). I have been working on implementing the Geogebra-filter for KIG. Here’s some introduction about the Geogebra-filter that we are trying to implement :

The Geogebra filter that we are developing is based on XSLT ( eXtensible Stylesheet Language Transformation ). With XSLT one can transform one representation of some XML data to another ( i.e. the contents between some tag or value of some attribute can be extracted and put between some different tag or as value of some different attribute, as per the requirements of the user ). In our filter we first read and transform the XML data of the Geogebra worksheet/tool file and then use the callback interface provided by the QAbstractXmlReceiver class to carry out appropriate action on encountering specific elements or attributes.There are various objects that Geogebra ( and KIG ) allow the user to construct ( i.e. line, parallel-line, conics, circles ) with different types ( i.e different inputs. For example one can construct a circle if the center and the radius are known, or three points lying on it are known … ). In our filter we have to handle different object-types separately which requires some smart XSLT handling. Currently we have one major XSLT template ( called argsTemplate ) with which most objects which are of the same ‘type’ ( i.e require the same arguments for construction ) in both KIG and Geogebra, can be easily be  KIG. We need to classify from the XML representation of the Geogebra worksheet that which object is of which type and suitably put that object in the KigDocument maintaining proper parent-child relationship ( or dependencies ). However there are many objects which are represented in slightly different way in Geogebra than they are in KIG. That requires handling with either a different XSLT template or at the callback level.

Support for points, various lines, circles, conics, some trasnformations, angles, vectors has been added. Document properties (like whether to show axis/grid or not, Euclidean or polar coordinate system, precision) and Graphic properties of objects ( like line-style, point-style, line-thickness, point-thickness, color) of Geogebra files can be read by KIG now ( will be pushed soon ). Currently I am trying to add a new object – perpendicular bisector ( which will take two points and construct the perpendicular bisector of the segment obtained by those points ) in KIG. Similar functionality exists but it is done through a built-in macro and can only construct the perpendicular bisector of segments. We are also trying to enable the Geogebra-filter to also read the .ggt files ( i.e. Geogebra tool files ). In KIG, loading ( or deleting ) a macro is done through the Types Dialog. With my current approach however, to load Geogebra tools, the user will just have to open them like a normal worksheet file ( from the open-file Dialog and not from the types dialog). The approach to read the tool files is simple – The KigDocument is created just like in case of normal Geogebra worksheet and then we create a object-hierarchy ( which contains the input and output objects of the macro ) and finally we construct a macro with this object-hierarchy and add it to the appropriate menu/subMenu.

One difficult thing to do is to support Geogebra Loci in KIG since the way they are represented in Geogebra is very different from that of KIG. I haven’t been able to figure out a plan for the Loci yet. Constrained Points, Tangents to the curves, Intersection and some arc and sector types are threatening to disturbing the uniformity of the filter. Support for Text-labels is yet to be added. The challenge is to sort out a way of supporting all the Geogebra objects in a way which stays as uniform and simple as possible throughout. If you find this interesting or have any question/suggestion feel free to contact  me 🙂 .

Into a Physics Simulator

Hi, this is my first post in PlanetKDE 🙂 . In this post I will be talking about the new features that I am trying to implement
in the KDE Physics Simualator STEP.
First one is the ‘FRAME-CHANGE’ feature. With this feature STEP will be able to give the users a better feel
of relative motion between the bodies. After enabling frame-change the user can select a body and STEP will observe the motion
of all the bodies on the scene relative to the currently selected body. STEP will be able to show that the path of one projectile
as seen from another projectile is a straight-line ( given the value of acceleration-due-to-gravity is same for both ).

I implemented it using the void QGraphicsView::centerOn(qreal x, qreal y)  method. Since the view is to be fixed to the body
which is currently selected, I take the currentIndex() from the ItemSelectionModel and then pass the co-ordinates of thus obtained
QGraphicsItem  to the QGraphicsView::centerOn(qreal x, qreal y) method.

Next one is the ‘REWIND’ feature. Watching the simulation go forward in time was becoming a littel boring 🙂 . Bring in something new
…. STEP will now have a REWIND button just beside the Simulate button. If the rewind button is pressed while the simulation is
 going on, world->time  begins to decrease and the worldscene travels back in time.

Implementation is quite simple. Integration with a +(ve) timescale gives forward simulation. Change the timescale to -(ve)  and you get
the REWIND feature (Or alternatively we can reverse the velocities of all the bodies ). Adjustments are needed to accomodate collisions
while rewinding. It works fine for simple scenes, but there are issues when using different values of restitution-coefficients and  in
cases where friction is there.

Another feature I am trying to do is the Pulley Joint. STEP already has Anchor, Pin, and Stick Joints. It will be a simple disc with
two handler items ( which can snap to a rigid-body or a particle ). The ration of the Pulley will be fixed and equal to one. Yes,
a very simple pulley. The constraint-eqations of the pulley-joint are causing some serious head-ache at the moment.
The same little problem is there in getting the equations and values correct in case of friction.
I hope to fix it soon….

Adding Straight-Plane and friction

A simple Box or a Polygon can already be created but sometimes their size falls short …i.e. the  disk or particle (or some other polygon) may go beyond it. For that I am adding a ‘Straight-Plane’ object in the palette. Many intersecting Straight-Planes can be created on the scene at the same time. It will be like an infinite fixed surface which will provide a surface with which other objects may collide or slide/roll upon. Straight-PLane

The StraightPlane class will inherit from RigidBody and will have just two specific properties :
point1 (Vector2d)
point2 (Vector2d)
(…. just like we need two points to define a straight line in 2-D plane). The two points will decide its inclination and position.

But here lies the problem , How to keep the straight plane fom moving ?
We could take care of GravitationForce and Weightforce by setting its mass to zero.
to make sure that it doesnt move during collisions we could fix the values of ConstraintsInfo::DynSparseRowMatrix ::jacobian value  , to 1 (at the
correct offset of course..).

We will have to neutralise any force from being applied to it by any SPRING also.

All of this can be taken care of if in the StraightPlaneCreator class we create an ‘Anchor’ just
after the second point of the Plane is set by the user and call
Anchor::setBody() to set the Straight-Plane as the Object of that anchor . The plane will get added to the BodyList and the Anchor will
get added to the JointList of the StepCore::World class.
This way all the problem of keeping the straight-plane fixed will be solved without spreading any dirt around in the previous code.

The functions to check state of collision (Contacted, Separating, Separated, Colliding etc.) have been written.
Although I went through many papers and googled the phrase “Gilbert-johnson-keerthy Distance algorithm” over a hundred times, I still
could not “hundred-percent” understand how to check the state of collision for two polgons (and the code is a mile long..). Thankfully I dont have any use of it
at the moment.

The algorithm to find the state of collision with a Straight-Plane is quite simple. I am using the formula to find the
distance of a point in 2-D space from a straight-line.

if the equation of the line is (Ax + By + C = 0) and the given point is (x1, y1), then the distance of the point
from the straight-line is

abs(Ax1 + By1 + C)/sqrt(pow(A,2) + pow(B, 2))

The value of tolerance is to be checked with a little testing.

But I am having some trouble handling the mouseEvents on the scene ..(due to which StraightPlaneCreator and StraightPlaneGraphicsItem
classes are not yet functional. )
Also I dont know how to paint something that will extend itself with the view (the plane is supposed to be infinite and should
extend if the user scrolls…)

About Friction:

The documentation says :

>>>QHash provides very similar functionality to QMap. The differences are:

>>>QHash provides faster lookups than QMap. (See Algorithmic Complexity for details.)
When iterating over a QMap, the items are always sorted by key. With QHash, the items are arbitrarily ordered.

Therefore to store the friction-Coefficient and the restitution-Coefficient I am going to use a QHash as I need faster lookups
and at the same time no need to store keys in sorted-order.

Since there will be a ‘FrictionForce’ icon just like ‘Weightforce’ and ‘GravitationForce’ icons on the palette, I will need to
__REGISTER(FrictionForce) and __ADD_TO_PALETTE(FrictionForce) in the constructor of the WorldFactory Class.
There will be a QHash<QPair<RigidBody*, RigidBody*>, QPair<double, double>>
First double of the second QPair to store friction-coefficient and the second double to store the restitution-coefficient
for the pair of rigidbodies.

Or ther can be two QHash-es One for QHash<QPair<RigidBody*, RigidBody*>, double> (for friction-coefficient)
and another QHash<QPair<RigidBody*, RigidBody*>, double> (restitution-coefficient)

(but this will require searching for the same pair of RigidBody- pointers from two different QHashes , so I will go with the
first idea i.e. a single QHash).

I noticed one anomaly, the solveCollisions() function exists but is never called anywhere. I looked everywhere the
StepCore::World:: doEvolve() function led but didn’t find it being used anywhere. The collisions are being solved
by gathering the contacts information int a ‘ConstraintsInfo’ structure and then passing the structure to ConstraintSolver::solve()
function… I still have to do some study on the internals of that ConstraintSolver::solve() function (particularly the ei_constrained_cg() method from
Eigen::Unsupported module..)

But the place to add friction and coefficient of restitution (bounceness) would be in the CollisionSolver::getContactsInfo()
(which I am working on right now..)


I did some backtracking on Simulation Start/Stop button.

Step carries out simulation frame by frame. WorldModel contains a _simulationFps (int ) and a _simulationTimer (QTimer) whose interval is (currently) set to
(1000/_simulationFps) i.e. 40 milliseconds…( as the _simulationFps is set to 25 in the constructor of the WorldModel.)

simulationFrameBegin() calls _simulationThread->doWorldEvolve(1.0/_simulationFps) i.e. the ‘delta’ time value for world->doEvolve()
is 4o milliseconds ( same as the frame-width…).
On finishing world->doEvolve(), simulationThread emits the WorldEvelveDone signal which calls WorldModel::simulationFrameEnd(reault)
(result is the value returned by doEvolve()). and the GUI updated…

So Each frame is displayed after a gap of 40 milliseconds. (for _simulationFps = 25).

There is one more interesting thing in StepCore::World class . It is _timeScale. The runSpeedAction group exploits this
variable to make the simulation appear faster.

in World::doEvolve(delta) function targetTime = currentTime + delta * timescale .
So if the timescale is 2 or 4… targetTime becomes greater and while the _simulationTimer and frame-rate remain unaffected.
The outcome is:
If at 1x speed , after one frame you were seeing the state of the world after 40 milliseconds. (in reality also 40 milliseconds are allowed \
for the frame).

Then at 2x after one frame you would see the state of the world after 80 milliseconds. (but in reality only 40 milliseconds are allowed
for the frame).

Thus the simulation appears to go faster.

I am planning to test the simulation with increased values of _simulationFps (may be 40 or 50 ..or at-least 30)
or may be add this option in the configure-step menu item.
and may be convert the radio buttons for runspeed Action-Group to a slider (after all they are just changing the _timescale of the
StepCore::World class).










New ‘Step’

Well, it doesn’t need you to be a scientist or a developer to see that STEP is much behind from where it should be. It doesn’t yet support objects in contact.  If you create two objects touching each  other and try to begin the simulation – a stupid dialogue will appear  telling you – “there are collisions which cannot be resolved automatically, please remove that contact first”. If you cannot create contact , you are only left with few options – projectile motion under the effect of weight, simple collisions (which are assumed elastic, no option to control the coefficient of restitution), spring related stuff, and a little fun with charged particles. What I miss the most in STEP are the pulleys. They can really bring you options, just close your eyes and fit  as many of them any place you want. Would be real fun to watch where which  one goes.  Friction and pulleys alone will provide a lot of options to the user.

Another missing thing is the ability to change the frame of observation during simulation. Imagine you have a lot of projectiles flying around. Where is the fun in watching them standing on the ground. I want STEP to allow users to experience relative-motion. What will the projectiles look like if you yourself were one of those flying things. How great would that be!!….

Step – The Physics Simulator (Code Study)

colliding discs

Discs colliding with Box:

Studying the Code:

The root of inheritance tree is the ‘Object’ class in the StepCore/object.h file which takes help from the MetaObject and MetaProperty classes to assign the properties to the objects created .To construct an Object –  ‘a’  , STEPCORE_OBJECT(a) is called which in turn calls the ‘EIGEN_MAKE_ALIGNED_OPERATOR_NEW’ macro (which is to generate aligned-pointers for fixed-size vectorisable eigen objects, it is pre-defined in the Eigen library) and then  the STEPCORE_OBJECT_NA(a) macro.

An important class for controlling the Objects and Forces is the ‘World’ class. All the objects as well as the forces that are created in the workspace by the user, reside in the world which contains a _timeScale and Itemlist (typedef std::vector<Item*>  ItemList), BodyList (typedef std::vector<Body*>  BodyList;), ForceList (typedef std::vector<Force*> ForceList;) which act as parameters to the solver functions to generate simulation. addItem() and removItem() functions of this class add and remove Items respectively from the world.
collisionSolver() resolves the collisions occuring between bodies depending on the flag value.
doCalcFn() is an important function here.

Then there is the collisionSolver class inheriting from the Object class. It uses information from the ‘Contact’ structure which contains information about the contact that has occurred – like pointers to the bodies which have come in contact, and type of the objects (disk-polygon, disk-disk etc.). The checkContact() virtual function of the CollisionSolver class takes a bodyList& as argument and counts the number of contacts. Objects are treated as in-contact and colliding if the minimum( all points in first body, all points in second body) < a limiting value. The functions are based on Gilbert-Johnson-Keerthi Algorithm(GJK Algorithm). GSL library is being used to find the approxiamte solutions of  the  differential-equations.

RigidBody class is the base class for all bodies that we see on the left-palette of the window (disc, box, polygon). This class defines  the basic properties of rigidbodies i.e.  mass, inertia, posotion, velocity, acceleration, angular-velocity, etc. (along with the corresponding getter-setter functions). It also contains an Eigen::Vector2d type member  ‘_force ‘  which keeps track of total force acting on the centre-of-mass of the rigidbody. Similarly a double type member ‘_torque’ keeps track of the total torque acting on the rigidbody.  Functions  pointWorldToLocal()  and pointLocalToWorld()  are there to convert a point on the global scene  to the specific  body’s co-ordinates and a point on the body to the scene’s co-ordinates respectively.

The basic interfacing is controlled by the WorldModel, WorldView  WorldGraphicsItem and WorldScene classes.  worldgraphics.h file contains the arrow classes and the corresponding handler events to display the velocities, angular-velocities etc. of the bodies on scene (when they are hovered or selected). It also contains definitions of the itemCreator classes. The WorldModel class inherits from  QAbstractItemModel  and is mainly responsible for controlling the selection behaviour and simulation related behavours. The WorlGraphicsView (inheriting from QGraphicsView) provides a view to the WorldScene. It caontains the zoomIn, zoomOut functions (actually slots)  for the scene and  the scroll Events. WorldScene is the scene where all the objects created and the simulation is displayed.

to be continued later…..