Skip to content

Instantly share code, notes, and snippets.

@Pomax
Created November 15, 2015 14:32
Show Gist options
  • Save Pomax/426bfa1d8434a6ec4820 to your computer and use it in GitHub Desktop.
Save Pomax/426bfa1d8434a6ec4820 to your computer and use it in GitHub Desktop.
programming some geometry in Type2 Charstrings

Writing Type2 sin(x) and cos(x) functions

If we want to make a font in which the glyphs are turned some random amount, we'll need to make sure we have a rotate function available. Normally, this is something you do with a rotation matrix, but that rotation matrix depends on trigonometric functions, and Type2 charstring instructions don't come with a trig. library, so ... we need to write our own!

In fact, let's use Bhaskara I's method of "sort of kind of" approximating a sine wave -or rather half of one- by using a relatively simple expression:

                 4x(π-x)
sin(x) = 4 * ----------------
              5π^2 - 4x(π-x)

which is a tweaked version of the generic

                  x^2
parabolic(x) = ---------
                b + x^2
              

But how do we implement this in the fairly simple Type2 stack-based language? First, let's implement this function in JavaScript, because it's super easy to prototype in, and see what we might need.

function sin(x) {
  var top = 4 * x * (π - x);
  var bottom = 5 * π * π - top;
  return 4 * top/bottom;
}

Simple enough. But let's start pulling this apart so we can express it as simple operations:

function sin(x) {
  var p = 3.1415...;
  var e = p - x;
  var e2 = e * x;
  var top = 4 * e2;
  var psq = p * p;
  var fp = 5 * psq;
  var bottom = fp - top;
  var frac = top/bottom;
  var result = 4 * frac;
  return result;
}

Slightly less legible, but everything's simple arithmetic operations now. However, we don't need the precision that Math.PI has to offer: we can get away with a simplified version. We can replace "Math.PI" with "3.1415" (doing the same for other technically constant values) and hardcode that everywhere, so we don't need to capture as many variables:

function sin(x) {
  var a = 3.1415 - x;
  var b = x * a;
  var c = 4 * b;
  var d = 49.348 - c;
  var f = c/d;
  return 4 * f;
}

Short and sweet. So, how do we implement this in Type2 operations? First of all, we don't actually have variables in Type2, but we do have a "transient stack", so we can treat that as putting numbers in an array:

function sin(x) {
  // duplicate the top of the stack, so we get [x, x]
  dup

  // cache values to the transient stack:
  read top of stack ('x') and put it in transient stack[0]
  // add '3.1415' to the top of the stack and dupe it so we get [x, 3.1415, 3.1415]
  add 3.1415
  dup
  read top of stack ('3.1415') and put it in t. stack[1]

  // values we don't need to keep
  add 4, read top of stack, put in t. stack[2]
  add 49.348, read top of stack, put it in t.stack[3]

  // at this point the stack is [..., x, 3.1415] but we want (pi-x),
  // so we need to make sure we swap the top two stack elements:
  exch (replaces [...,a,b] with [...,b,a])

  // and now we can do our subtraction to form (pi-x):
  sub (replaces [...,a,b] with [...,a-b])


  // we then form x(pi-x):
  get stack[0]
  mul (replaces [...,a,b] with [...,a*b])

  // and then form 4x(pi-x):
  get stack[2]
  mul

  // at this point we have a value we want to cache because
  // we're going to need it again to compute that division:

  put <just computed> on transient stack[4]

  // again, a "put" does not actually change the main stack, so
  // we've left the value on the main stack: we'll use it very soon

  // first, form 49.348 - 4x(pi-x):
  get stack[3]
  get stack[4]
  sub

  // and then we use that 4x(pi-x) value that was still on the stack,
  // along with the 49.348 - 4x(pi-x) we just computed:
  div (replaces [...,a,b] with [...,a/b]

  // almost done: all we need to do now is form 4*(...) and we're done:
  get stack[2]
  mul

  // the top of the stack now contains sin(x) -approximately- instead of x
  return
}

So, tracing through the function, when this runs it replaces the value at the top of the stack, which was "x", will now contain the value of "sin(x)" instead, for doing something with. So, let's express this as Type2 instructions

[start of Type2 subroutine]
// add 'x' to the transient stack, without losing it from the main stack
01:  dup, 0, put
// add '3.1415' to the transient stack, without losing it from the main stack
02:  3.1415, dup, 1, put
// cache '4'
03:  4, 2, put
// cache pi squared
04:  49.348, 3, put
// form pi-x
05:  exch, sub
// form x(pi-x):
06:  0, get, mul
// form 4x(pi-x):
07:  2, get, mul
// cache the value:
08:  4, put
// form 49.348 - 4x(pi-x):
09:  3, get, 4, get, sub
// form division:
10:  div
// almost done: all we need to do now is form 4*(...) and we're done:
11:  2, get, mul
// return to previous control flow
12:  return

So, in proper Type2 control values:

01: 12 27, (0), 12 20
02: (3.1415), 12 27, (1), 12 20
03: (4), (2), 12 20
04: (49.348), (3), 12 20
05: 12 28, 12 11
06: (0), 12 21, 21 24
07: (2), 12 21, 21 24
08: (4), 12 20
09: (3), 12 21, (4), 12 21, 12 11
10: 12 12
11: (2), 12 21, 12 24
12: 11

Now, all those "actual numbers" (rather than instructions) still need encoding using the Type2 number encoding (explained in full in Adobe Tech Note 5177, section 3.2). For the simple numbers we're dealing with, any number "a" is encoded as the value "a + 139", so 0 becomes 139, 1 becomes 140, etc. For the decimal fractions, Type2 has a 16 bit + 16 bit encoding, starting with a byte set to 255, then 16 bits for the integer, and then 16 bits for the fraction's value, both encoded as 2's complement bit patterns. So, our "3.1415" is encoded as 16 bits for 3 (11), and 16 bits for the 1415 (10110000111), which in bytes is [255,0,3,5,135] and our "49.348" is 49 (110001) and 348 (101011100), which in bytes is [255,0,49,1,92]:

01: 12 27, 139, 12 20
02: 255 0 3 5 135, 12 27, 140, 12 20
03: 143, 141, 12 20
04: 255 0 49 1 92, 142, 12 20
05: 12 28, 12 11
06: 139, 12 21, 21 24
07: 141, 12 21, 21 24
08: 143, 12 20
09: 142, 12 21, 143, 12 21, 12 11
10: 12 12
11: 141, 12 21, 12 24
12: 11

And finally, compacted to a byte array:

12, 27, 139, 12, 20, 255, 5 3, 3 135, 12, 27, 140, 12, 20, 143, 141, 12, 20, 255, 5 49, 9 92, 142, 12, 20, 12, 28, 12, 21, 139, 12, 21, 21, 14, 141, 12, 21, 21, 14, 143, 12, 20, 142, 12, 21, 143, 12, 21, 12, 21, 12, 22, 141, 12, 21, 12, 24, 11

We can now store this as a Type2 subroutine, to replace values 'x' on top of the stack with values 'sin(x)' (or at least, a fairly decent approximation of it, based on an input from 0 to 1, rather than 0 to twice pi).

What about cos(x)?

Using some high school trigonometry, we know that cos(x) is the same as sin(x+pi/2), so the implementation of cos(x) is fairly simple:

add pi/2 to the top of the stack
add (turning [..., x, pi/2] into [..., x+pi/2])
call sin(x) subroutine with x+pi/2 at the top of the stack

So in instructions:

(1.57)
add
call subroutine: ... (where ... is a number pointing to our subroutine for sin(x), let's pretend it's 0 for now)
return to main control flow

And in bytes:

255 0 1 0 57, 12 10, 139, 29, 11 

Making sure that the 139 (which is decimal 0) gets changed to reflect whatever the subroutine number of our sin(x) is.

Cool. Can we do rotations?

We totally can. Let's implement a rotation/translation (so we can rotate over a specific origin) now that we have a sin(x) and cos(x) function available:

function rotate(angle, ox, oy, x, y) {
  var x' = x - ox,
      y' = y - oy,
      nx = x' * cos(angle) - y' * sin(angle),
      ny = x' * sin(angle) + y' * cos(angle);
  return { nx + ox, ny + oy};
}

Which of course requires a little more care in Type2:

function(angle, ox, oy, x, y) {
  cache all arguments to the transient stack
  
  restore angle
  form and cache cos(angle) to the transient stack

  restore angle
  form and cache sin(angle) to the transient stack

  restore x and ox
  form and cache x-ox to the transient stack

  restore y and oy
  form and cache y-oy to the transient stack
  
  retore x' = (x-ox) and y' = (y-oy) and form:
    nx = x' * cos(angle) + y' * -sin(angle) + ox
    ny = x' * sin(angle) + y' * cos(angle) + oy
  then cache nx and ny

  // make sure we preserve the angle and origin, with
  // [x,y] at the start replaced by [nx, ny] instead:

  restore angle, ox, oy, nx, ny

  return to previous control flow
}

So in instructions:

// stack contains: [..., angle, ox, oy, x, y],
// so put them onto the transient stack in argument order:
4 put, 3 put, 2 put, 1 put, 0 put

// we'll say routine 0 is sin(x), and routine 1 is cos(x)

0 get, 0 callsub, 5 put  // sin(angle)
0 get, 1 callsub, 6 put  // cos(angle)

3 get, 1 get, sub, 7 put  // (x - ox)
4 get, 2 get, sub, 8 put  // (y - oy)

7 get, 6 get, mul, 9 put  // (x-ox) * cos(angle)
8 get, 6 get, mul, 10 put // (y-oy) * sin(angle)

// nx = (x-ox) * cos(angle) + -((y-oy) * sin(angle)) + ox
3 get, 9 get, 10 get, neg, add, add, 11 put


7 get, 6 get, mul, 12 put // (x-ox) * sin(angle)
8 get, 5 get, mul, 13 put // (y-oy) * cos(angle)

// ny = (x-ox) * sin(angle) + (y-oy) * cos(angle) + oy
2 get, 12 get, 13 get, add, add, 14 put

// restore output to [angle, ox, oy, nx, ny]
get 0, get 1, get 2, get 13, get 14

return

Rotating glyphs

So, now we need to of course make a font that uses this, in a way that we can type a sequence of --for instance-- "AAAAAA" and have every 'A' be rotated a little differently. This means prepping a regular charstring so that it will call the rotate operation for each coordinate pair.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment