Development/Improve handles of DrawingML shapes

    From The Document Foundation Wiki

    I have added methods to calculate the adjustment values from handle position for DrawingML preset shapes. The implementation is in EnhancedCustomShape2d::SetHandleControllerPosition(). This article gives some background information and is mainly addressed to developers.

    Problem

    Shapes in DrawingML can be defined in a way, that the outline of the shape is not fix, but can be vary depending on adjustment values. They have handles by which the user can alter the adjustment values.

    The attributes gdRefX, gdRefY, gdRefAng, and gdRefR of the handle element determine, which adjustment value is effective. The position of the handle is determined by a child element <pos x="foo" y="bar"/>. Allowed attribute values are not only simple numbers and names of adjustment guides but formula guide names too. The formulas then reference other formulas and adjustment values.

    In case you open a file and render the document, there is no problem. The adjustment values are contained in the document and you use them in the calculation of the formula results and finally of the handle position. Problems occur, if the user moves the handle and you have to calculate, which adjustment value is needed, so that the calculation will result in the new handle position. My changes solve this problem for preset shapes of DrawingML. They fail for user defined shapes. In case you know a general solution, please implement it.

    Specification

    The definition of the preset shapes are given in standard ISO/IEC 29500-1:2016 [1] in the part Electronic inserts[2]. But this document contains some errors. The LibreOffice repository has the file presetShapeDefinitions.xml [3] where some errors are already corrected. If you think something is wrong, missing or unclear in the standard, you can contact the Microsoft forum “Office XML, ODF, and Binary File Formats” [4].

    DrawingML uses own operators in the formulas of the shape. These operators are specified in section “20.1.9.11 gd” in the standard. In addition DrawinML uses some identifiers for special values, e.g. “ss” for the smaller one of height and width. These identifiers are specified in section “20.1.10.56 ST_ShapeType” in the standard.

    Some identifiers in my solution might look cryptic to you. I have often build them from the guide name or the special identifier in the specification, prefixed with character “f” to indicate the domain “double”.

    [1] https://standards.iso.org/ittf/PubliclyAvailableStandards/c071691_ISO_IEC_29500-1_2016.zip
    [2] https://standards.iso.org/ittf/PubliclyAvailableStandards/c071691_ISO_IEC_29500-1_2016_Electronic_inserts.zip
    [3] https://opengrok.libreoffice.org/xref/core/oox/source/drawingml/customshapes/presetShapeDefinitions.xml
    [4] https://social.msdn.microsoft.com/Forums/en-US/home?forum=os_binaryfile

    Test documents

    You might need test documents with preset shapes. You can use the script README [5] to generate such files. Caution, the script is not usable in Cygwin, you need a true Linux. The script does not only generate the file oox-drawingml-cs-presets [6], which is in the repository. It locally generates a folder “pptx”. This folder contains for each preset shape “foo” a file preset-cshape-foo.pptx and a file cshape-foo.pptx. The preset-cshape-foo.pptx file contains the shape using the <prstGeom> element. The file cshape-foo.pptx contains the shape using the <custGeom> element, which means, that the file itself contains the shape definition as specified in the presetShapeDefinitions.xml file. In addition the folder has the files cshape-all.pptx and preset-cshape-all.pptx with all shapes on one slide.

    The shapes are inserted with same width and height. Because some errors are only visible if width and height are different, you need to stretch the shapes manually. The shapes are inserted without adjustment values, that means, that the default adjustment values are used. Of cause, in case you have MS Office or SoftMaker on hand, you can use these apps to generate and manipulate test files. In addition you can work directly in the file.

    [5] https://opengrok.libreoffice.org/xref/core/oox/source/drawingml/customshapes/README
    [6] https://opengrok.libreoffice.org/xref/core/oox/source/drawingml/customshapes/oox-drawingml-cs-presets

    Basic idea

    The shape definition describes how to get the handle position using the adjustment value. The basic idea of my solution is, to perform this calculation backwards. The downside of this approach is, that it can only work, if you know the formulas beforehand. That is given for preset shapes, but not for arbitrary user defined shapes. DrawingML distinguishes them by using either the element <prstGeom> with a reference to the shape identifier or the element <custGeom>.

    The import detects the <prstGeom> element. In that case it sets for a shape identifier “foo” the Type attribute of the SdrCustomShapeGeometryItem property to “ooxml-foo”. In case of a <custGeom> element, the Type attribute is set to “ooxml-non-primitive”. Notice, that this attribute is an OUString and different from the member eSpType of class EnhancedCustomShape2d, which is a MSO_SPT enum value. My solution examines the Type attribute and performs the needed calculations depending on the found shape type.

    The general structure of a preset shape definition is this:

    <foo>
    <avLst …> … </avLst> List of adjustment guides. In the preset definitions it contains the default values. Those are not relevant here, but might be useful for test cases.
    <gdLst …> … </gdLst> List of formula guides.
    <ahLst …> … </ahLst> List of handle definitions.
    <cxnLst …> … </cxnLst> List of connections, which means “glue points”. They are not relevant here.
    <rect …/> Area for text. It is not relevant here.
    <pathLst…> … </pathLst> List of paths. In DrawingML subpaths are realized by sub-elements <path>.
    </foo>

    Example with XY handle

    The “rightArrow” shape has the following definitions for formula guides and handles:

    Screenshot of shape “rightArrow” in edit mode

    <gdLst >
    <gd name="maxAdj2" fmla="*/ 100000 w ss" />
    <gd name="a1" fmla="pin 0 adj1 100000" />
    <gd name="a2" fmla="pin 0 adj2 maxAdj2" />
    <gd name="dx1" fmla="*/ ss a2 100000" />
    <gd name="x1" fmla="+- r 0 dx1" />
    <gd name="dy1" fmla="*/ h a1 200000" />
    <gd name="y1" fmla="+- vc 0 dy1" />
    <gd name="y2" fmla="+- vc dy1 0" />
    <gd name="dx2" fmla="*/ y1 dx1 hd2" />
    <gd name="x2" fmla="+- x1 dx2 0" />
    </gdLst>

    <ahLst >
    <ahXY gdRefY="adj1" minY="0" maxY="100000"> <pos x="l" y="y1" /> </ahXY>
    <ahXY gdRefX="adj2" minX="0" maxX="maxAdj2"> <pos x="x1" y="t" /> </ahXY>
    </ahLst>

    First look at the list of handles. The shape has two XY handles. The first handle is at point (l|y1). “l” is the special value “left”. “y1” is the result of the formula with name “y1”. The attribute gdRefY binds the y-value of the handle position to the adjust value with name “adj1”. If the position of the handle changes, the adjustment adj1 will get a new value. The attributes minY="0" maxY="100000" restrict possible values of the adjustment to the range [0..100000]. This handle is at the left side of the shape and it is only vertical movable.

    The second handle is at point (x1|t). “t” is the special value “top”. “x1” is the result of the formula with name “x1”. The attribute gdRefX binds the x-value of the handle position to the adjust value with name “adj2”. The attributes minX="0" maxX="maxAdj2" restrict possible values to the range [0..maxAdj2] where “maxAdj2” is the result of the formula with name “maxAdj2”. This handle is at the top of the shape and it is only horizontal movable.

    XY-adjustment values are given relative to width and height of the shape. Thereby 100000 means 100%, and 50000 would mean 50%.

    Now look, how y1 is calculated

    DrawingML Meaning
    y="y1" y = y1
    <gd name="y1" fmla="+- vc 0 dy1" /> y1 = vc - dy1
    <gd name="dy1" fmla="*/ h a1 200000" /> dy1 = h * a1 / 200000
    <gd name="a1" fmla="pin 0 adj1 100000" /> a1 = clamp adj1 to range [0, 100000]

    The formulas of the preset shapes always repeat the restriction of the adjustment value in the handle element by using the “pin” operator. For backward calculation we can ignore the pin operator, because the method SetHandleControllerPosition() checks the range and clamps the initially calculated adjustment value to the specified range.

    Setting the parts together you get the equation
    y = vc - h * adj1 / 200000.

    Resolving in adj1 results in
    adj1 = (vc - y) / h * 200000

    So you find shape “ooxml-rightArrow” under pattern “(vc - y) / h * 200000” in the method lcl_getYAdjustmentValue().

    Some formulas can be simplified, because “top” and “left” is always zero for preset shapes. Therefore bottom=height, right= width, vertical center=height/2 and horizontal center=width/2 holds. This allows to put some shape types under the same pattern, although they calculation looks different at a first glance.

    Most of the XY handles follows such pattern. In most cases the handle can move either vertical or horizontal. All such shapes are collected in the unit test “testTdf115813_OOXML_XY_handle” of CustomshapesTest [7] in svx. A unit test for the other shapes is missing.

    [7] https://opengrok.libreoffice.org/xref/core/svx/qa/unit/customshapes.cxx

    Example with polar handle

    The shape “arc” has the (shortened) definition below. To shorten it, not only the connector list and the text rectangle was removed, but also formulas, which are only used for values in those elements. Formulas in DrawingML can only refer other formulas, if those are placed before them. That makes it easy to eliminate not needed formulas starting from the end. Looking at handle list and path list you see, that only x1, y1, x2, y2, stAng and swAng are needed here and of cause the helper values for to calculate them.

    Screenshot of shape "arc" in edit mode

    <gdLst>
    <gd name="stAng" fmla="pin 0 adj1 21599999" />
    <gd name="enAng" fmla="pin 0 adj2 21599999" />
    <gd name="sw11" fmla="+- enAng 0 stAng" />
    <gd name="sw12" fmla="+- sw11 21600000 0" />
    <gd name="swAng" fmla="?: sw11 sw11 sw12" />
    <gd name="wt1" fmla="sin wd2 stAng" />
    <gd name="ht1" fmla="cos hd2 stAng" />
    <gd name="dx1" fmla="cat2 wd2 ht1 wt1" />
    <gd name="dy1" fmla="sat2 hd2 ht1 wt1" />
    <gd name="wt2" fmla="sin wd2 enAng" />
    <gd name="ht2" fmla="cos hd2 enAng" />
    <gd name="dx2" fmla="cat2 wd2 ht2 wt2" />
    <gd name="dy2" fmla="sat2 hd2 ht2 wt2" />
    <gd name="x1" fmla="+- hc dx1 0" />
    <gd name="y1" fmla="+- vc dy1 0" />
    <gd name="x2" fmla="+- hc dx2 0" />
    <gd name="y2" fmla="+- vc dy2 0" />
    </gdLst>

    <ahLst>
    <ahPolar gdRefAng="adj1" minAng="0" maxAng="21599999"><pos x="x1" y="y1" /></ahPolar>
    <ahPolar gdRefAng="adj2" minAng="0" maxAng="21599999"><pos x="x2" y="y2" /></ahPolar>
    </ahLst>

    <pathLst>
    <path stroke="false" extrusionOk="false">
    <moveTo><pt x="x1" y="y1" /></moveTo>
    <arcTo wR="wd2" hR="hd2" stAng="stAng" swAng="swAng" />
    <lnTo><pt x="hc" y="vc" /></lnTo>
    <close />
    </path>
    <path fill="none">
    <moveTo> <pt x="x1" y="y1" /></moveTo>
    <arcTo wR="wd2" hR="hd2" stAng="stAng" swAng="swAng" />
    </path>
    </pathLst>

    Angles in DrawingML have the unit 1/60000 deg. If a formula has an operator with trigonometric function, then it uses this special unit directly. Therefore you often need to convert angle units in C++. For converting between rad and deg use basegfx::rad2deg and basegfx::deg2rad, respectively. For other conversions you should look whether a suitable conversion function already exists.

    We try again, to get the adjustment value from the handle position. We start with x = x1 and y = y1

    <gd name="x1" fmla="+- hc dx1 0" /> x1 = hc - dx1
    <gd name="y1" fmla="+- vc dy1 0" /> y1 = vc - dy1

    This gives dx1 = hc - x and dy1 = vc - y

    Further relevant formula guides are

    <gd name="stAng" fmla="pin 0 adj1 21599999" />
    <gd name="wt1" fmla="sin wd2 stAng" /> wt1 = wd2 * sin(stAng)
    <gd name="ht1" fmla="cos hd2 stAng" /> ht1 = hd2 * cos(stAng)
    <gd name="dx1" fmla="cat2 wd2 ht1 wt1" /> dx1 = wd2 * cos(atan2(wt1, ht1))
    <gd name="dy1" fmla="sat2 hd2 ht1 wt1" /> dy1 = hd2 * sin(atan2(wt1, ht1))

    Are you confused? For understanding the formulas, you need some knowledge about ellipses. Therefore here a quick side-trip to ellipses.

    Some Mathematics of Ellipses

    Consider an ellipse with coordinate origin in its center and ellipse axes on coordinate axis. A point of the ellipse can be determined by its distance r to the origin and the angle β to the x-axis. The ellipse is determined by its widths and height. Lets name the corresponding radii wR and hR here. So the question is, how to calculate the coordinates (xPos|yPos) of a point of the ellipse, if you know the angle β of the point and the radii wR and hR of the ellipse. One way is shown in the following image.

    Method with radius as intermediate step

    A second way uses the construction of an ellipse with two circles, one with the minor radius of the ellipse, the other with the major radius of the ellipse. If you draw an angle α, it will intersect these circles. Name the intersection point with the minor circle A and the intersection with the major circle B. Draw a straight line through point A parallel to the major axis of the ellipse and a straight line through point B parallel to the minor axis of the ellipse. The intersection of these lines is a point P of the ellipse.

    Construct an ellipse point using affine transformation

    So if you know the corresponding “circle” angle α of a point, you would be able to calculate the point coordinates. The following image shows the calculation of such “circle” angle from known angle β and radii wR and hR.

    Method with "circle" angle as intermediate step

    BTW, the <draw:enhanced-geometry> element uses angles in the meaning of angle β, but the primitive shape <draw:ellipse> uses angles in the meaning of angle α in ODF.

    Continue Example “arc”

    Comparing the general way with the formulas of the shape “arc” we can notice that the angle β corresponds to the angle stAng, the radii wR and hR correspond to wd2 and hd2, and the coordinates of point P correspond to (dx1 | dy1). So written with DrawingML operators cat2 and sat2, we would get

    <gd name="dx1" fmla="cat2 wd2 hd2*cos(stAng) wd2*sin(stAng) " />
    <gd name="dy1" fmla="sat2 hd2 hd2*cos(stAng) wd2*sin(stAng) " />

    But it is not possible to use complex expressions as parameter of DrawingML operators. They need to be calculated beforehand in help formulas. That is here

    <gd name="ht1" fmla="cos hd2 stAng" />, which means ht1 = hd2 * cos(stAng)
    <gd name="wt1" fmla="sin wd2 stAng" />, which means wt1 = wd2 * sin(stAng)

    These help formula results can then replace the complex expressions and you get
    <gd name="dx1" fmla="cat2 wd2 ht1 wt1 " />
    <gd name="dy1" fmla="sat2 hd2 ht1 wt1 " />

    You have seen, that the calculation of handle position from adjustment value is quite complex. Luckily, the here needed backward calculation is easy. You only need atan2.

    β = atan2(dy1, dx1).

    Of cause you have to keep in mind, that you need the angle in the special DrawingML angle unit. That is done in the local method lcl_getAngleInOOXMLUnit().

    I have shown these ellipse calculations here, because in shape definitions which use angles, you will find such group of formulas, that calculate point coordinates from angle in the first or the second way. For backward calculating you can take such entire group and resolve it by using a single atan2.

    Example “blockArc”

    The shape has two polar handles. The position of the first one determines an “angle” adjustment value adj1 for the start angle. The position of the second handle determines an “angle” adjustment value adj2 for the end angle and a “radius” adjustment values adj3. The “angle” adjustment values are calculated similar to the shape “arc”.

    The “radius” adjustment value adj3 is special. The relevant formula guides for backward calculating are these

    <gd name="istAng" fmla="pin 0 adj2 21599999" />
    <gd name="a3" fmla="pin 0 adj3 50000" />
    <gd name="dr" fmla="*/ ss a3 100000" />
    <gd name="iwd2" fmla="+- wd2 0 dr" />
    <gd name="ihd2" fmla="+- hd2 0 dr" />
    <gd name="wt2" fmla="sin iwd2 istAng" />
    <gd name="ht2" fmla="cos ihd2 istAng" />
    <gd name="dx2" fmla="cat2 iwd2 ht2 wt2" />
    <gd name="dy2" fmla="sat2 ihd2 ht2 wt2" />
    <gd name="x2" fmla="+- hc dx2 0" />
    <gd name="y2" fmla="+- vc dy2 0" />

    Screenshot with references to the formula guide names

    You notice a group of formulas in the middle, which belong to such ellipse calculations, which I have mentioned in the previous section. The peculiarity in this case is the fact, that the adjustment value does not determine a full radius, but only the part “dr”. The value of “dr” is such, that the handle position (x2|y2) is a point on the inner ellipse. Mathematically it means, that “dr” is a solution of the equation
    [math]\displaystyle{ \Big(\frac{hc - x2}{wd2 - dr}\Big)^2 + \Big(\frac{vc-y2}{hd2-dr}\Big)^2 = 1 }[/math]

    Writing this without fraction results in
    [math]\displaystyle{ \big({hc - x2}\big)^2 \cdot \big({hd2-dr}\big)^2+\big({wd2 - dr}\big)^2\cdot \big({vc-y2}\big)^2 = \big({wd2-dr}\big)^2 \cdot \big({hd2-dr}\big)^2 }[/math]

    You have to determine the roots of a fourth degree polynomial. In my solution this is done numerically in the method lcl_getRadiusDistance(), which uses Newton's method.

    Example “circularArrow”

    Some shape definitions are very complex. For such shapes I found it useful, to print the shape and enter all the points, angles and formula values which I could identify. The image shows a scan of such sheet.

    Scan of work in progress

    My investigation of the shape “circularArrow” results in some unexpected results and leaves some yet not solved problems, see ToDo comments in the code.

    • The end angle of the arc does not determine the tip of the arrow head, but it determines the point, where the middle-ellipse of the arc intersects the base line of the arrow head. That is point (xH|yH).
    • The end angle is given in the adjustment value adj3. But the point (xH|yH) has no handle. Instead the adjustment value adj3 is bound to the angle of the polar handle in point (xF|yF). That is the handle in the corner of the shaft of the arrow with the base line of the arrow head.
    • The tip of the arrow head has the coordinates (xA|yA). It is a polar handle, where the angle is bound to adjustment value adj2. But this angle is not a start or end angle as in the shape “arc”. It is the increment to the end angle adj3.
    • The base line of the arrow head is not perpendicular to the middle-ellipse of the arc, but it is parallel to a line from the tip of the arrow head to the center of the ellipse.
    • Point (xB|yB) at the end of the base line of the arrow head has a polar handle. The radius of this polar handle is bound to the adjustment value adj5. But it is not really a “radius”, but it determines the distance between point (xB|yB) and point (xH|yH) and thereby the ellipse axis differences between the outer ellipse given by the width and height of the shape and the middle-ellipse of the arrow.
    • The polar handle in point (xF|yF) does not only refer to an angle but to a radius too. This radius is bound to the adjustment value adj1. And again, it is not really a “radius”, but that adjustment value determines the thickness of the shaft of the arrow.
    • Only the polar handle at point (xE|yE) acts similar to the handles of the shape “arc”. It is bound to adjustment value adj4, which is the start angle of the shape “circularArrow”.

    My solutions contains two approximations for this shape type. The following images show the correct values compared to the approximated values.

    Difference between correct angle and approximated value for adj3
    Difference between correct and approximated value for adj5