path: root/doc/src/examples/elasticnodes.qdoc

/****************************************************************************
**
** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
** All rights reserved.
** Contact: Nokia Corporation (qt-info@nokia.com)
**
** This file is part of the documentation of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:FDL$
** GNU Free Documentation License
** Alternatively, this file may be used under the terms of the GNU Free
** Documentation License version 1.3 as published by the Free Software
** Foundation and appearing in the file included in the packaging of
** this file.
**
** Other Usage
** Alternatively, this file may be used in accordance with the terms
** and conditions contained in a signed written agreement between you
** and Nokia.
**
**
**
**
** $QT_END_LICENSE$
**
****************************************************************************/

/*!
    \example graphicsview/elasticnodes
    \title Elastic Nodes Example

    This GraphicsView example shows how to implement edges between nodes in a
    graph, with basic interaction. You can click to drag a node around, and
    zoom in and out using the mouse wheel or the keyboard. Hitting the space
    bar will randomize the nodes. The example is also resolution independent;
    as you zoom in, the graphics remain crisp.

    \image elasticnodes-example.png

    Graphics View provides the QGraphicsScene class for managing and
    interacting with a large number of custom-made 2D graphical items derived
    from the QGraphicsItem class, and a QGraphicsView widget for visualizing
    the items, with support for zooming and rotation.

    This example consists of a \c Node class, an \c Edge class, a \c
    GraphWidget test, and a \c main function: the \c Node class represents
    draggable yellow nodes in a grid, the \c Edge class represents the lines
    between the nodes, the \c GraphWidget class represents the application
    window, and the \c main() function creates and shows this window, and runs
    the event loop.

    \section1 Node Class Definition

    The \c Node class serves three purposes:

    \list
    \o Painting a yellow gradient "ball" in two states: sunken and raised.
    \o Managing connections to other nodes.
    \o Calculating forces pulling and pushing the nodes in the grid.
    \endlist

    Let's start by looking at the \c Node class declaration.

    \snippet examples/graphicsview/elasticnodes/node.h 0

    The \c Node class inherits QGraphicsItem, and reimplements the two
    mandatory functions \l{QGraphicsItem::boundingRect()}{boundingRect()} and
    \l{QGraphicsItem::paint()}{paint()} to provide its visual appearance. It
    also reimplements \l{QGraphicsItem::shape()}{shape()} to ensure its hit
    area has an elliptic shape (as opposed to the default bounding rectangle).

    For edge management purposes, the node provides a simple API for adding
    edges to a node, and for listing all connected edges.

    The \l{QGraphicsItem::advance()}{advance()} reimplementation is called
    whenever the scene's state advances by one step. The calculateForces()
    function is called to calculate the forces that push and pull on this node
    and its neighbors.

    The \c Node class also reimplements
    \l{QGraphicsItem::itemChange()}{itemChange()} to react to state changes (in
    this case, position changes), and
    \l{QGraphicsItem::mousePressEvent()}{mousePressEvent()} and
    \l{QGraphicsItem::mouseReleaseEvent()}{mouseReleaseEvent()} to update the
    item's visual appearance.

    We will start reviewing the \c Node implementation by looking at its
    constructor:

    \snippet examples/graphicsview/elasticnodes/node.cpp 0

    In the constructor, we set the
    \l{QGraphicsItem::ItemIsMovable}{ItemIsMovable} flag to allow the item to
    move in response to mouse dragging, and
    \l{QGraphicsItem::ItemSendsGeometryChanges}{ItemSendsGeometryChanges} to
    enable \l{QGraphicsItem::itemChange()}{itemChange()} notifications for
    position and transformation changes. We also enable
    \l{QGraphicsItem::DeviceCoordinateCache}{DeviceCoordinateCache} to speed up
    rendering performance. To ensure that the nodes are always stacked on top
    of edges, we finally set the item's Z value to -1.

    \c Node's constructor takes a \c GraphWidget pointer and stores this as a
    member variable. We will revisit this pointer later on.

    \snippet examples/graphicsview/elasticnodes/node.cpp 1

    The addEdge() function adds the input edge to a list of attached edges. The
    edge is then adjusted so that the end points for the edge match the
    positions of the source and destination nodes.

    The edges() function simply returns the list of attached edges.

    \snippet examples/graphicsview/elasticnodes/node.cpp 2

    There are two ways to move a node. The \c calculateForces() function
    implements the elastic effect that pulls and pushes on nodes in the grid.
    In addition, the user can directly move one node around with the mouse.
    Because we do not want the two approaches to operate at the same time on
    the same node, we start \c calculateForces() by checking if this \c Node is
    the current mouse grabber item (i.e., QGraphicsScene::mouseGrabberItem()).
    Because we need to find all neighboring (but not necessarily connected)
    nodes, we also make sure the item is part of a scene in the first place.

    \snippet examples/graphicsview/elasticnodes/node.cpp 3

    The "elastic" effect comes from an algorithm that applies pushing and
    pulling forces. The effect is impressive, and surprisingly simple to
    implement.

    The algorithm has two steps: the first is to calculate the forces that push
    the nodes apart, and the second is to subtract the forces that pull the
    nodes together. First we need to find all the nodes in the graph. We call
    QGraphicsScene::items() to find all items in the scene, and then use
    qgraphicsitem_cast() to look for \c Node instances.

    We make use of \l{QGraphicsItem::mapFromItem()}{mapFromItem()} to create a
    temporary vector pointing from this node to each other node, in \l{The
    Graphics View Coordinate System}{local coordinates}. We use the decomposed
    components of this vector to determine the direction and strength of force
    that should apply to the node. The forces accumulate for each node, and are
    then adjusted so that the closest nodes are given the strongest force, with
    rapid degradation when distance increases. The sum of all forces is stored
    in \c xvel (X-velocity) and \c yvel (Y-velocity).

    \snippet examples/graphicsview/elasticnodes/node.cpp 4

    The edges between the nodes represent forces that pull the nodes together.
    By visiting each edge that is connected to this node, we can use a similar
    approach as above to find the direction and strength of all pulling forces.
    These forces are subtracted from \c xvel and \c yvel.

    \snippet examples/graphicsview/elasticnodes/node.cpp 5

    In theory, the sum of pushing and pulling forces should stabilize to
    precisely 0. In practise, however, they never do. To circumvent errors in
    numerical precision, we simply force the sum of forces to be 0 when they
    are less than 0.1.

    \snippet examples/graphicsview/elasticnodes/node.cpp 6

    The final step of \c calculateForces() determines the node's new position.
    We add the force to the node's current position. We also make sure the new
    position stays inside of our defined boundaries. We don't actually move the
    item in this function; that's done in a separate step, from \c advance().

    \snippet examples/graphicsview/elasticnodes/node.cpp 7

    The \c advance() function updates the item's current position. It is called
    from \c GraphWidget::timerEvent(). If the node's position changed, the
    function returns true; otherwise false is returned.

    \snippet examples/graphicsview/elasticnodes/node.cpp 8

    The \c Node's bounding rectangle is a 20x20 sized rectangle centered around
    its origin (0, 0), adjusted by 2 units in all directions to compensate for
    the node's outline stroke, and by 3 units down and to the right to make
    room for a simple drop shadow.

    \snippet examples/graphicsview/elasticnodes/node.cpp 9

    The shape is a simple ellipse. This ensures that you must click inside the
    node's elliptic shape in order to drag it around. You can test this effect
    by running the example, and zooming far in so that the nodes are very
    large. Without reimplementing \l{QGraphicsItem::shape()}{shape()}, the
    item's hit area would be identical to its bounding rectangle (i.e.,
    rectangular).

    \snippet examples/graphicsview/elasticnodes/node.cpp 10

    This function implements the node's painting. We start by drawing a simple
    dark gray elliptic drop shadow at (-7, -7), that is, (3, 3) units down and
    to the right from the top-left corner (-10, -10) of the ellipse.

    We then draw an ellipse with a radial gradient fill. This fill is either
    Qt::yellow to Qt::darkYellow when raised, or the opposite when sunken. In
    sunken state we also shift the center and focal point by (3, 3) to
    emphasize the impression that something has been pushed down.

    Drawing filled ellipses with gradients can be quite slow, especially when
    using complex gradients such as QRadialGradient. This is why this example
    uses \l{QGraphicsItem::DeviceCoordinateCache}{DeviceCoordinateCache}, a
    simple yet effective measure that prevents unnecessary redrawing.

    \snippet examples/graphicsview/elasticnodes/node.cpp 11

    We reimplement \l{QGraphicsItem::itemChange()}{itemChange()} to adjust the
    position of all connected edges, and to notify the scene that an item has
    moved (i.e., "something has happened"). This will trigger new force
    calculations.

    This notification is the only reason why the nodes need to keep a pointer
    back to the \c GraphWidget. Another approach could be to provide such
    notification using a signal; in such case, \c Node would need to inherit
    from QGraphicsObject.

    \snippet examples/graphicsview/elasticnodes/node.cpp 12

    Because we have set the \l{QGraphicsItem::ItemIsMovable}{ItemIsMovable}
    flag, we don't need to implement the logic that moves the node according to
    mouse input; this is already provided for us. We still need to reimplement
    the mouse press and release handlers, though, to update the nodes' visual
    appearance (i.e., sunken or raised).

    \section1 Edge Class Definition

    The \c Edge class represents the arrow-lines between the nodes in this
    example. The class is very simple: it maintains a source- and destination
    node pointer, and provides an \c adjust() function that makes sure the line
    starts at the position of the source, and ends at the position of the
    destination. The edges are the only items that change continuously as
    forces pull and push on the nodes.

    Let's take a look at the class declaration:

    \snippet examples/graphicsview/elasticnodes/edge.h 0

    \c Edge inherits from QGraphicsItem, as it's a simple class that has no use
    for signals, slots, and properties (compare to QGraphicsObject).

    The constructor takes two node pointers as input. Both pointers are
    mandatory in this example. We also provide get-functions for each node.

    The \c adjust() function repositions the edge, and the item also implements
    \l{QGraphicsItem::boundingRect()}{boundingRect()} and
    \l{QGraphicsItem::paint()}{paint()}.

    We will now review its implementation.

    \snippet examples/graphicsview/elasticnodes/edge.cpp 0

    The \c Edge constructor initializes its \c arrowSize data member to 10 units;
    this determines the size of the arrow which is drawn in
    \l{QGraphicsItem::paint()}{paint()}.

    In the constructor body, we call
    \l{QGraphicsItem::setAcceptedMouseButtons()}{setAcceptedMouseButtons(0)}.
    This ensures that the edge items are not considered for mouse input at all
    (i.e., you cannot click the edges). Then, the source and destination
    pointers are updated, this edge is registered with each node, and we call
    \c adjust() to update this edge's start end end position.

    \snippet examples/graphicsview/elasticnodes/edge.cpp 1

    The source and destination get-functions simply return the respective
    pointers.

    \snippet examples/graphicsview/elasticnodes/edge.cpp 2

    In \c adjust(), we define two points: \c sourcePoint, and \c destPoint,
    pointing at the source and destination nodes' origins respectively. Each
    point is calculated using \l{The Graphics View Coordinate System}{local
    coordinates}.

    We want the tip of the edge's arrows to point to the exact outline of the
    nodes, as opposed to the center of the nodes. To find this point, we first
    decompose the vector pointing from the center of the source to the center
    of the destination node into X and Y, and then normalize the components by
    dividing by the length of the vector. This gives us an X and Y unit delta
    that, when multiplied by the radius of the node (which is 10), gives us the
    offset that must be added to one point of the edge, and subtracted from the
    other.

    If the length of the vector is less than 20 (i.e., if two nodes overlap),
    then we fix the source and destination pointer at the center of the source
    node. In practise this case is very hard to reproduce manually, as the
    forces between the two nodes is then at its maximum.

    It's important to notice that we call
    \l{QGraphicsItem::prepareGeometryChange()}{prepareGeometryChange()} in this
    function. The reason is that the variables \c sourcePoint and \c destPoint
    are used directly when painting, and they are returned from the
    \l{QGraphicsItem::boundingRect()}{boundingRect()} reimplementation. We must
    always call
    \l{QGraphicsItem::prepareGeometryChange()}{prepareGeometryChange()} before
    changing what \l{QGraphicsItem::boundingRect()}{boundingRect()} returns,
    and before these variables can be used by
    \l{QGraphicsItem::paint()}{paint()}, to keep Graphics View's internal
    bookkeeping clean. It's safest to call this function once, immediately
    before any such variable is modified.

    \snippet examples/graphicsview/elasticnodes/edge.cpp 3

    The edge's bounding rectangle is defined as the smallest rectangle that
    includes both the start and the end point of the edge. Because we draw an
    arrow on each edge, we also need to compensate by adjusting with half the
    arrow size and half the pen width in all directions. The pen is used to
    draw the outline of the arrow, and we can assume that half of the outline
    can be drawn outside of the arrow's area, and half will be drawn inside.

    \snippet examples/graphicsview/elasticnodes/edge.cpp 4

    We start the reimplementation of \l{QGraphicsItem::paint()}{paint()} by
    checking a few preconditions. Firstly, if either the source or destination
    node is not set, then we return immediately; there is nothing to draw.

    At the same time, we check if the length of the edge is approximately 0,
    and if it is, then we also return.

    \snippet examples/graphicsview/elasticnodes/edge.cpp 5

    We draw the line using a pen that has round joins and caps. If you run the
    example, zoom in and study the edge in detail, you will see that there are
    no sharp/square edges.

    \snippet examples/graphicsview/elasticnodes/edge.cpp 6

    We proceed to drawing one arrow at each end of the edge. Each arrow is
    drawn as a polygon with a black fill. The coordinates for the arrow are
    determined using simple trigonometry.

    \section1 GraphWidget Class Definition

    \c GraphWidget is a subclass of QGraphicsView, which provides the main
    window with scrollbars.

    \snippet examples/graphicsview/elasticnodes/graphwidget.h 0

    The class provides a basic constructor that initializes the scene, an \c
    itemMoved() function to notify changes in the scene's node graph, a few
    event handlers, a reimplementation of
    \l{QGraphicsView::drawBackground()}{drawBackground()}, and a helper
    function for scaling the view by using the mouse wheel or keyboard.

    \snippet examples/graphicsview/elasticnodes/graphwidget.cpp 0

    \c GraphicsWidget's constructor creates the scene, and because most items
    move around most of the time, it sets QGraphicsScene::NoIndex. The scene
    then gets a fixed \l{QGraphicsScene::sceneRect}{scene rectangle}, and is
    assigned to the \c GraphWidget view.

    The view enables QGraphicsView::CacheBackground to cache rendering of its
    static, and somewhat complex, background. Because the graph renders a close
    collection of small items that all move around, it's unnecessary for
    Graphics View to waste time finding accurate update regions, so we set the
    QGraphicsView::BoundingRectViewportUpdate viewport update mode. The default
    would work fine, but this mode is noticably faster for this example.

    To improve rendering quality, we set QPainter::Antialiasing.

    The transformation anchor decides how the view should scroll when you
    transform the view, or in our case, when we zoom in or out. We have chosen
    QGraphicsView::AnchorUnderMouse, which centers the view on the point under
    the mouse cursor. This makes it easy to zoom towards a point in the scene
    by moving the mouse over it, and then rolling the mouse wheel.

    Finally we give the window a minimum size that matches the scene's default
    size, and set a suitable window title.

    \snippet examples/graphicsview/elasticnodes/graphwidget.cpp 1

    The last part of the constructor creates the grid of nodes and edges, and
    gives each node an initial position.

    \snippet examples/graphicsview/elasticnodes/graphwidget.cpp 2

    \c GraphWidget is notified of node movement through this \c itemMoved()
    function. Its job is simply to restart the main timer in case it's not
    running already. The timer is designed to stop when the graph stabilizes,
    and start once it's unstable again.

    \snippet examples/graphicsview/elasticnodes/graphwidget.cpp 3

    This is \c GraphWidget's key event handler. The arrow keys move the center
    node around, the '+' and '-' keys zoom in and out by calling \c
    scaleView(), and the enter and space keys randomize the positions of the
    nodes. All other key events (e.g., page up and page down) are handled by
    QGraphicsView's default implementation.

    \snippet examples/graphicsview/elasticnodes/graphwidget.cpp 4

    The timer event handler's job is to run the whole force calculation
    machinery as a smooth animation. Each time the timer is triggered, the
    handler will find all nodes in the scene, and call \c
    Node::calculateForces() on each node, one at a time. Then, in a final step
    it will call \c Node::advance() to move all nodes to their new positions.
    By checking the return value of \c advance(), we can decide if the grid
    stabilized (i.e., no nodes moved). If so, we can stop the timer.

    \snippet examples/graphicsview/elasticnodes/graphwidget.cpp 5

    In the wheel event handler, we convert the mouse wheel delta to a scale
    factor, and pass this factor to \c scaleView(). This approach takes into
    account the speed that the wheel is rolled. The faster you roll the mouse
    wheel, the faster the view will zoom.

    \snippet examples/graphicsview/elasticnodes/graphwidget.cpp 6

    The view's background is rendered in a reimplementation of
    QGraphicsView::drawBackground(). We draw a large rectangle filled with a
    linear gradient, add a drop shadow, and then render text on top. The text
    is rendered twice for a simple drop-shadow effect.

    This background rendering is quite expensive; this is why the view enables
    QGraphicsView::CacheBackground.

    \snippet examples/graphicsview/elasticnodes/graphwidget.cpp 7

    The \c scaleView() helper function checks that the scale factor stays
    within certain limits (i.e., you cannot zoom too far in nor too far out),
    and then applies this scale to the view.

    \section1 The main() Function

    In contrast to the complexity of the rest of this example, the \c main()
    function is very simple: We create a QApplication instance, seed the
    randomizer using qsrand(), and then create and show an instance of \c
    GraphWidget. Because all nodes in the grid are moved initially, the \c
    GraphWidget timer will start immediately after control has returned to the
    event loop.
*/