Drawing styled text with Uniscribe

The last tutorial saw the completion of the UspAnalyze function, one of the main APIs of the new UspLib text-rendering engine. We will now switch our attention to the implementation of the UspTextOut function. Our goal is to divide up the glyph-lists we ceated in the last tutorial, and apply colour information prior to display with ScriptTextOut. The method we will use to identify which colour belongs to each glyph is the central theme of this tutorial.

Now, there is alot of very specific information in this tutorial related to Unscribe and you are only going to find it interesting if you have also been trying to understand how to draw styled text. So feel free to skip to the next tutorial if you want to see UspLib in action.

The image above shows another small utility I wrote whilst working with Uniscribe. The purpose of this app is to demonstrate (and test) the UspLib library. You can download the demo, and also the UspLib sourcecode, at the top of this article.

6. Drawing styled text

At this point we could quite simply call ScriptTextOut with a whole run of glyphs and be done with it. It would display correctly and we would have succeeded in our goal to display Unicode text. However the text would only be drawn in a single font and colour, and it would have been much simpler to use the ScriptString API instead! Remember, the entire reason we are looking at Uniscribe is because we need to apply font and colour information in a very fine-grained manner.

Back in part#10 of this series I proposed a new method for rendering text in Neatpad, using three separate passes. I have implemented this rendering scheme with the UspTextOut function:

void UspTextOut( USPDATA * uspData,
                 HDC hdc,
                 int xpos,
                 int ypos,
                 RECT * bounds
    )
{
    //
    // 1. Draw all background colours, including selection-highlights;
    // selected areas are added to the HDC clipping region which prevents
    // step#2 (below) from drawing over them
    //     
    PaintBackground(uspData, hdc, xpos, ypos, bounds);

    //
    // 2. Draw the text normally. Selected areas are left untouched
    // because of the clipping-region created in step#1
    //
    SetBkMode(hdc, TRANSPARENT);
    PaintForeground(uspData, hdc, xpos, ypos, bounds, FALSE);

    //
    // 3. Redraw the text using a single text-selection-colour (i.e. white)
    // in the same position, directly over the top of the text drawn in step#2
    // Before we do this, the HDC clipping-region is inverted,
    // so only selection areas are modified this time
    //
    PaintForegound(uspData, hdc, xpos, ypos, bounds, TRUE);
}

UspTextOut is quite similar to ScriptStringOut, in that it requires a string to be analyzed prior to display. It takes as input the USPDATA object that contains the information generated by UspAnalyze. Although there are three passes involved, there are only two functions that need to be implemented - DrawBackground, and DrawForeground which will be used to draw both regular (styled) as well as ‘selected’ text. We will take a look at the implementation of these functions a little further down.

Characters vs Glyphs vs Clusters

The major problem with Uniscribe is understanding how to decipher the results of the ScriptShape and ScriptPlace calls. There is just so much information returned about each run of text that it takes a fair amount of time and effort to understand it all. Hopefully by the end of this tutorial you will have a little more insight into how all of the Uniscribe functions hang together.

The key detail to understand about Uniscribe (and computer Typography in general) is the difference between characters and glyphs. Up until this point the main focus with Neatpad has been logical Unicode character sequences. However once Uniscribe has been involved the focus is very much on glyphs. The thing to understand here, is that there is no direct relationship between characters and glyphs.

For simple scripts such as English a font usually contains one glyph per Unicode character. However for more complex scripts this relationship can change. Sometimes a single Unicode character can result in more than one glyph. The opposite is also true - there can also be multiple Unicode characters resulting in just a single glyph. This behaviour various depending on what font is being used. This separation between characters and glyphs presents a problem because our attribute style-runs are all character based, and we somehow need to translate this styling information onto specific glyphs.

To make things even more complicated, the concept of glyph clusters must be understood. A cluster is basically a grouping of glyphs which must be treated as a single selectable unit. Whilst this is not a problem in itself, it does make rendering glyph sequences a little more complicated because cluster boundaries must be respected.

Understanding the Logical Cluster List

The logical-cluster list is key to establishing a relationship between characters and glyphs. This list is returned by ScriptShape in the pwLogClust[] array. It provides the mapping between logical character-positions and glyph-cluster positions. UspLib stores each run’s logical-cluster information inside the clusterList[] field of the USPDATA object.

To support this idea of character-to-glyph mapping, the logical-cluster list must represent two important concepts:

• Firstly, it identifies the cluster boundaries in the original Unicode string - that is, the offsets in logical character units (WCHARs) of each cluster. Each entry in the clusterList corresponds exactly to a single character in the original string - so clusterList is always the same length as the Unicode string we are processing.
• Secondly, this same array also identifies the offsets of each glyph-cluster, within the glyph-buffers generated by ScriptShape and ScriptPlace.

In other words, the individual element values (the content) of the clusterList defines the glyph-clusters, whilst the positions of the array elements represents the clusters in logical character terms.

As an example we will use the same Arabic string “يُساوِي” we were looking at previously. This string of seven Unicode characters results in the following logical cluster information being generated by ScriptShape. Note that the logical array-index positions are listed across the top of the table.

Whole clusters are identified by grouping together any identical numbers in the logical-cluster list. As you can see from the cluster-list in the table above, there are two 6’s and two 2’s (in addition to the other singlular numbers), resulting in a total of five whole clusters all together. The image below illustrates this grouping concept.

Notice that cluster-list is always stored in logical order, whilst the glyph-list is always in visual order. This means that for right-to-left scripts (such as the Arabic string above), the cluster-list elements will decrease when reading the array. As a result of this, the first glyph that must be drawn will be at the very end of the glyph-list. Bearing this in mind, the breakdown of the clusters is as follows:

• 1st cluster: two characters represented by two glyphs.
• 2nd cluster: one character represented by one glyph.
• 3rd cluster: one character represented by one glyph.
• 4th cluster: two characters represented by two glyphs.
• 5th cluster: one character represented by one glyph.

Hopefully it should be fairly obvious how the logical clusters were identified - with the number of WCHARs in each cluster calculated by the number of characters in each grouping. Calculating the number of glyphs in each cluster is less obvious. The key here is looking at the difference between the cluster values. This is how the identification of each cluster occurred:

1. The first two 6’s identify cluster#1, comprising two WCHARs (in character-positions 0 and 1). This value of 6 points to the end of the glyphList which contains the glyphs for this cluster. We know that this cluster is represented by two glyphs (#5 and #6) because:
2. The next value in the cluster-list (4) tells us two things. Obviously this cluster starts at glyph #4 in the glyph-list. However this also means that there were 2 (two) glyphs in the last cluster (6-4 = 2).
3. The third cluster is comprised of the single glyph#3, and a single WCHAR.
4. The fourth cluster is comprised of two WCHARs again, which are represented by glyphs #1 and #2.
5. The fifth and final cluster is again a single WCHAR, represented by glyph#0 in the glyph-list.

As you can see the key detail here is looking at the difference between glyph-indices in order to count the number of glyphs in each cluster. Special consideration must also be taken with right-to-left scripts because of the way that glyphs are stored in reverse order. The way I handled this was to advance the x-coordinate to the end of the run, call SetTextAlign(TA_RIGHT), and then move the output-location to the left each time, resulting in the glyphs being output in logical (right-to-left) order.

The important thing to understand is that we always follow the cluster-list in logical order, even for right-to-left scripts. We rely on the ordering of the element values to locate each glyph-cluster as it should be drawn.

Another example

The previous example was of couse a right-to-left script and highlighted the unique way in which these scripts are represented by Uniscribe. The example shown next is based on the example in MSDN under the ScriptShape documentation, and highlights how complex left-to-right text is represented by Uniscribe.

The string this time is from the Devanagari script. I have no idea what it means because I just strung a sequence of code-points together which happened to have the right “look”. If anyone can supply me with a Unicode phrase of 7 characters, which results in the glyph+cluster properties shown below, then please get in touch!

The key difference here is how the cluster-list elements increase when reading the array. For left-to-right runs, the glyphs are stored in the same order as the original Unicode characters. This is the ordering that many Western readers will find most natural.

The diagram hopefully again illustrates the relationship between logical characters and glyph-clusters, this time for a left-to-right run of text. This example is purely fictitious as I couldn’t find any phrase, font & script which satisfied the required glyph+cluster properties. Again, the number of glyphs per cluster is calculated by the difference between the cluster-list elements.

• 1st cluster: one character represented by one glyph (1-0=1)
• 2nd cluster: one character represented by three glyphs (4-1=3)
• 3rd cluster: three characters represented by one glyph (5-4=1)
• 4th cluster: two characters represented by three glyphs (8-5=3)

The number of glyphs for the last cluster was calculated because we knew how many glyphs (8 in total) were generated for this run by ScriptShape.

Interpolation is the key

The one thing to understand about Uniscribe is the separation between characters and glyphs. So looking now at another example, what happens when we have three characters comprising two glyphs? The problem we face is, how do we distribute the colour information for each character across the glyphs, and which glyph takes which colour?

For some scripts where the glyphs typically order horizontally you can almost infer the colour relationships. However when glyphs stack vertically on top of each other within a cluster, or when there is an unequal number of characters-to-glyphs, there is no easy way to associate a colour with a particular glyph.

With UspLib I solved this problem in two ways - using one method for drawing the background, and another when drawing the actual glyphs themselves (the foreground). Drawing the foreground was easy: I decided simply to paint all glyphs in a cluster as a single colour. Should there be multiple colour-attributes for the cluster, only the first is chosen and the rest are ignored. This is by far the easiest method and in reality you wouldn’t expect individual glyphs to have their own colours when in a cluster.

Painting the background is rather different, because the inversion-highlighting scheme must be taken into account. The strategy I have used here is to interpolate the colours across the width of each cluster, when drawing the background. This method is hinted at by Microsoft in the following quote from MSDN, in the section “notes on ScriptXtoCP and ScriptCPtoX”:

“Cluster information in the logical cluster array is used to share the width of a cluster of glyphs equally among the logical characters they represent.”

It took me a while to make the logical leap that this strategy could also be used for text-rendering, however after implementing it I realised it is the exact same method used by the ScriptString API.

The process is very simple. We know how many characters make up each cluster, and also how many glyphs make up each cluster. We therefore sum the width of these glyphs to calculate the total width of the cluster. We then divide the cluster-width by the number of characters in the cluster - this number tells us how wide each colour band should be.

advanceWidth = clusterWidth / charCount;

For some scripts, dividing the clusters this way makes alot of sense, especially for Arabic because the caret is conventially positioned at character boundaries rather than glyph-cluster boundaries. However for most scripts this would be viewed as incorrect. Rather than having a special-case just for Arabic, I have instead written UspTextOut so that it always interpolates over glyph-clusters, should any colour-attributes happen to be this fine-grained. We will rely on the fact that ScriptCPtoX will only allow the caret (and therefore selection-highlghts) to be placed in the middle of clusters when appropriate.

Lastly, using integer math for the cluster-division will be result in potential rounding errors. Whilst this is not a massive problem, we need to have the exact same results that ScriptCPtoX produces when it does its own presumed division-operations (otherwise we could be out by a pixel occasionally). Presumably ScriptCPtoX uses MulDiv in its calculations because this appears to give the correct results, and is what I have used for UspLib.

Drawing the background

As mentioned above, drawing the background is a little different because of the use of interpolation. We will start by looking at the PaintBackground routine:

void PaintBackground(USPDATA * uspData, HDC hdc, int xpos, int ypos, RECT * bounds)
{
    int i;
    ITEM_RUN * itemRun;

    // Process the item-runs in visual-order
    for(i = 0; i < uspData->itemRunCount; i++)
    {
        itemRun = GetItemRun(uspData, i);

        // paint the background of the specified item-run
        PaintItemRunBackground(uspData, itemRun, hdc, xpos, bounds);

        xpos += itemRun->width;
    }
}

As you can see this function is very simple. It merely processes the item-runs in visual-order and advances the x-coordinate by the item-width for each run. Each item-run background are rendered individually by the PaintItemRunBackground function.

void PaintItemRunBackground(USPDATA *uspData, ITEM_RUN *itemRun, HDC hdc, int xpos, int ypos)
{
    int i, lasti;

    // locate the item-run buffers
    WORD * clusterList = uspData->clusterList + itemRun->charPos;
    ATTR * attrList = uspData->attrList + itemRun->charPos;
    int * widthList = uspData->widthList + itemRun->glyphPos;

    for(lasti = 0, i = 0; i < itemRun->len; i++)
    {
        // search for a logical cluster boundary (or end of run)
        if(i == itemRun->len || clusterList[lasti] != clusterList[i])
        {
            << process cluster >>
        }
    }
}

The primary task is to identify the logical-cluster positions. The two loop-indices (lasti and i) represent these cluster positions in the original text-string. The number of WCHAR s in each cluster is therefore (i-lasti). Because we always iterate in logical order, this is true for both LTR and RTL texts.

<< process cluster >>
        int glyphIdx1, glyphIdx2;

        // locate glyph-positions for the cluster
        GetGlyphClusterIndices(itemRun, clusterList, i, lasti, &glyphIdx1, &glyphIdx2);

        // measure width of this group of glyphs
        for(runWidth = 0; glyphIdx1 <= glyphIdx2; )
            runWidth += widthList[glyphIdx1++];

        // divide the cluster-width by the number of code-points that cover it
        advanceWidth = MulDiv(runWidth, 1, i-lasti);

Once a cluster has been identified, GetGlyphClusterIndices is callled. This function inspects the clusterList and returns the corresponding glyph-index positions for i and lasti.

The width of the glyph-cluster is computed next, by simply iterating between glyphIdx1 and glyphIdx2, before dividing the cluster-width by the number of characters (WCHARs). We now know how far to advance each time we paint a bit of background.

for(a = lasti; a <= i; a++)
    {
        // look for change in attribute background
        if(a == itemRun->len ||
           attr.bg != attrList[a].bg || 
           attr.sel != attrList[a].sel )
        {
            PaintRectBG(uspData, itemRun, hdc, xpos, &rect, &attr);
            rect.left = rect.right;
        } 
    }

The final task is to interpolate the colour-attributes over the cluster. We only ever paint the background if we detect a change in colour, so most of the time an item-run background is painted with just one operation. Missing from the code listing above is the small detail of correcting for rounding errors in the (integer) division - however this is not necessary for understanding the code.

I won’t bother including the code for the PaintRectBG function - suffice to say it is not really very interesting, other than the fact that it calls ExcludeClipRect after drawing any selection-highlight background area.

void GetGlyphClusterIndices( USPDATA * uspData, 
                             ITEM_RUN * itemRun, 
                             int clusterIdx1, 
                             int clusterIdx2, 
                             int * glyphIdx1, 
                             int * glyphIdx2
                           )
{
    WORD *clusterList = uspData->clusterList + itemRun->charPos;

    // locate glyph-positions for the cluster
    if(itemRun->analysis.fRTL)
    {
        // RTL scripts
        *glyphIdx1 = clusterIdx1 < itemRun->len ? clusterList[clusterIdx1] + 1 : 0;
        *glyphIdx2 = clusterList[clusterIdx2];
    }
    else
    {
        // LTR scripts
        *glyphIdx1 = clusterList[clusterIdx2];
        *glyphIdx2 = clusterIdx1 < itemRun->len ? clusterList[clusterIdx1] - 1 : itemRun->glyphCount - 1;
    }
}

Above is the GetGlyphClusterIndices function. Note the two distinct cases for LTR and RTL scripts - this is required because the cluster-elements decrease when reading the cluster array (for RTL scripts), but increase for LTR scripts.

Drawing the Foreground

The process for drawing the text is so similar to that of the background that I won’t bother including too much code this time. We’ll jump straight in to the start of the DrawForegroundItemRun function:

// right-left runs can be drawn backwards for simplicity
if(itemRun->analysis.fRTL)
{     
     oldMode = SetTextAlign(hdc, TA_RIGHT);

     xpos += itemRun->width;
     runDir = -1;
}

The first thing we do is set the text-alignment to TA_RIGHT for any right-to-left string, and advance the x-coordinate to the end of the run. This will allow us to draw the text in logical order (as we walk the logical-cluster-list). This is important because apart from this one detail, it means we can maintain a single function for drawing both LTR and RTL texts.

// loop over all the logical character-positions
 for(lasti = 0, i = 0; i <= itemRun->len; i++)
 {
     // find a change in attribute
     if(i == itemRun->len || attrList[i].fg != attrList[lasti].fg )
     {
         // scan forward to locate end of cluster (we must always
         // handle whole-clusters because the attr[] might fall in the middle)
         for( ; i < itemRun->len; i++)
             if(clusterList[i - 1] != clusterList[i])
                 break;

        // locate glyph-positions for the cluster [i,lasti]
        GetGlyphClusterIndices(itemRun, clusterList, i, lasti, &glyphIdx1, &glyphIdx2);

        << display text >>
     }
 }

The next difference between foreground and background rendering is how we identify cluster-boundaries. This time we look for changes in colour first of all. Once a new colour is found we scan forward to locate the end of the cluster. This means we can paint the whole cluster in one colour and not worry about interpolation.

<< display text >>

    // measure the width (in pixels) of the run
    for(runWidth = 0, g = glyphIdx1; g <= glyphIdx2; g++)
        runWidth += widthList[g];

    // only need the text colour as we are drawing transparently
    SetTextColor(hdc, forcesel ? uspData->selFG : attrList[lasti].fg);

    //
    // Finally output the run of glyphs
    //
    hr = ScriptTextOut(
        hdc, 
        &uspFont->scriptCache,
        xpos,
        ypos,
        0,
        NULL,					
        &itemRun->analysis, 
        NULL,
        0,
        glyphList + glyphIdx1,
        glyphIdx2 - glyphIdx1 + 1,
        widthList + glyphIdx1,
        NULL,
        offsetList + glyphIdx1
    );

    // +ve/-ve depending on run direction
    xpos += runWidth * runDir;
    lasti = i;

Once the text-colour has been set, ScriptTextOut is called with the range of glyphs which fall within the cluster. Once again, we only output any text should there be a change in colour so usually there would only be one call to ScriptTextOut.

7. ScriptTextOut

For the sake of completeness here’s the prototype for ScriptTextOut :

HRESULT WINAPI ScriptTextOut(

   HDC hdc, 
   SCRIPT_CACHE * psc,
   int x, 
   int y, 
   UINT fuOptions,

   // ExtTextOut options
   RECT * rect,        
   SCRIPT_ANALYSIS * analysis, 
   WCHAR * pwcReserved, 
   int iReserved,
   WORD * pwGlyphs, // in - results of ScriptShape
   int cGlyphs, 
   int * piAdvance, // in - results of ScriptPlace
   int * piJustify,    
   GOFFSET * pGoffset // in - results of ScriptPlace
);

That’s a pretty intimidating function by anyone’s standards! The parameters of note are:

• fuOptions is can be one of ETO_CLIPPED, ETO_OPAQUE, or zero. These are the standard ExtTextOut flags. Because we have drawn the background ourselves there is no need to use these parameters. Note that if opaque was specified, whole clusters of glyphs must be passed to this function.
• pwGlyphs and cGlyphs identify the list of glyph values returned by ScriptShape.
• piAdvance and pGoffset point to the glyph-placement buffers returned by ScriptPlace.
• piJustify points to an optional array of justified advance values.

ScriptTextOut is basically a wrapper around ExtTextOut - however you will notice that there is no WCHAR* parameter to this function. This is because ScriptTextOut calls ExtTextOut with the ETO_GLYPH_INDEX option, and passes the buffer of glyphs we specifed.

ScriptTextOut may perform additional processing (such as glyph-reordering) before calling into GDI, so don’t be tempted to bypass ScriptTextOut by calling ExtTextOut directly.

Uniscribe Limitations

One of the drawbacks of Uniscribe is the very thing it does best - the breaking up of a string into individually shapable items. The problem is that some strings containing alot of whitespace or punctuation result in a large number of item-runs. Whilst this is not bad in itself, it does present a problem when it comes to rendering the line of text. The shear number of calls to ScriptTextOut has a performance penalty - in comparison to calling ExtTextOut with the same line of text.

For complex-scripts there is no alternative but to break up the string using ScriptItemize. However it would be nice if for non-complex (i.e. English) scripts we could somehow re-combine the item-runs and reduce the potential number of calls to ScriptTextOut. I haven’t ventured too far down this path yet, but it is certainly possible to identify if an item-run is complex or not by inspecting the SCRIPT_ANALYSIS::eScript field.

struct SCRIPT_ANALYSIS
{
    WORD eScript : 10; 
    WORD fRTL : 1;
    ...
};

Now, the eScript field is ‘opaque’ which means we shouldn’t make any assumptions about its value. However it can be used as an index into the “global script table”, which contains information about the specific script-shaping engines installed in a system.

HRESULT WINAPI ScriptGetProperties(SCRIPT_PROPERTIES ***ppSp, int *piNumScripts);

The ScriptGetProperties function returns a pointer to this global-script-table, and each entry in the table is a pointer to a SCRIPT_PROPERTIES structure:

struct SCRIPT_PROPERTIES
{
    DWORD langid;
    DWORD fNumeric;
    DWORD fComplex;
    ...
};

There are many information-fields in this structure, however the interesting one for us is the fComplex flag. Drawing all this together results in the following function, which returns a boolean indicating if an item-run is complex or not:

BOOL IsRunComplex(ITEM_RUN *itemRun)
{
    SCRIPT_PROPERTIES ** propList;
    int propCount;
    int scriptIndex; 

    // get pointer to the global script table
    ScriptGetProperties(&propList, &propCount);

    // the SCRIPT_ANALYSIS::eScript is an index to the global script table
    scriptIndex = itemRun->analysis.eScript;

    // locate the script from the script-index
    return propList[scriptIndex]->fComplex;
}

Any non-complex item-runs could theoretically be identified and then merged together into a single run, with the SCRIPT_ANALYSIS::eScript field set to SCRIPT_UNDEFINED. All this should happen before ScriptShape is called.

Coming up in Part 15

Every time I post a new tutorial I promise that there’ll be another update to Neatpad, and of course it hasn’t happened (again!). Uniscribe is just so damn complicated it has taken me far more time to document than I first anticpated. For now you can download the UspLib demo at the top of this tutorial, and next time we really will be seeing a new-and-improved Neatpad.

Downloads
uspdemo.zip