Implementing iBooks page curling using a conical deformation algorithm

One of iPad's most talked about apps is Apple's own iBooks e-reader. Perhaps its most eye-catching but completely superfluous feature is the beautiful, dynamic page curling effect that follows your finger naturally as you drag to turn pages. Unlike cheap implementations using simple masks and gradients, iBook's page curling is very realistic, with content that bleeds through and deforms accurately along the curve of the page. Shortly after the iPad announcement Steven Troughton-Smith discovered the page curl effect hiding inside a private API but it offers few cues to the actual implementation.

This article aims to demonstrate one technique that Apple may have used to implement their page curling behavior but doesn't assert that they did. Instead of a 3D approach through OpenGL it's quite possible that they may have simply used Core Image and some fancy math to implement everything entirely in 2D, something hinted at by the fact their page flattens out for large deformations rather than exhibiting a uniform curvature. Whether or not this is the same algorithm Apple uses, it's a simple, elegant solution that works well from all viewing angles, not just straight on.

Background

I was particularly intrigued when I first saw iBooks' dynamic page curling because several years ago I developed a system for kiosk-based virtual books. Using a touchscreen, users can browse a rare book by swiping with a finger while the priceless original remains protected in a climate-controlled case. During the initial stages of the project I experimented with various methods of handling the page turning. High visual quality followed by performance were the top criteria. Unfortunately realtime 3D didn't cut it on the hardware and software available at the time. While it would have been nice to have had dynamic page curling, in the end we opted to use pre-rendered bitmaps of each page turn for the sake of image quality. Needless to say, it was a lengthy and expensive process but yielded the best looking results by far.

Fast forward a few years into the future, and graphics hardware was advancing faster than computers in general. A new, high-performance 3D development tool called Unity had just been released and I was quite blown away by its capabilities. On a whim I decided to revisit dynamic page curling to see if then current technology could deliver acceptable results. I was pleasantly surprised with what I could accomplish in less than a day, and you can view the proof-of-concept online (installs Unity plugin if needed, no restart required), or as a stand-alone Mac application (11.8 MB). The interface isn't pretty, but it gets the job done.

The math behind page curling

Many people have tackled the job of modeling a page curl dynamically in 3D. Some early attempts treated a page as a soft body, utilizing a mass-springs system to calculate all the internal and external forces applied to each point in a mesh. While this gives realistic results for supple, cloth-like objects, paper is by nature stiff and rigid and normally bends in a predictable manner. In addition, mass-springs models are very computationally expensive and may exhibit compression or stretching, effects unwanted when modeling stiff paper. By thinking of a page curl as a geometric transformation, we can greatly simplify our calculations.

It turns out some clever scientists at Xerox PARC did in fact do this and released a research paper in 2004.^[1] Their brilliantly simple solution consists of thinking of a page curl as an imaginary cone of changing dimensions, around which the page wraps itself as the cone rolls across the surface of the book. It's probably easier to visualize once you've read the paper. Go ahead, it's only a single page PDF. Now grab a nearby book and curl a page yourself. Neat, isn't it?

The math presented in the research paper may seem daunting at first but it's actually just basic algebra and trigonometry. I won't attempt to explain it any better than the authors because they already do a pretty good job and I suck at math anyway. What's important is that they have come up with a set of functions that map any arbitrary 2D point P(x, y) on a flat page to its corresponding 3D point T(x, y, z) in space given cone parameters θ and A. Go review the math before reading on, if you haven't already.



θ represents the cone angle and can range from {0…π/2} (90° for those who prefer to think in degrees over radians). The smaller the value, the skinner the cone; at zero, the cone degenerates into a ray and makes the page virtually disappear. At the other extreme, the cone is infinitely wide, which maps to a perfectly flat page with no curl whatsoever.

A represents the cone apex. A value of zero puts the apex at the origin while larger and smaller values translate the apex farther away along the y axis (up and down the spine of the book). Very large values of A (approaching infinity) combined with small values of θ produce an extremely elongated cone, or essentially a cylinder. As θ becomes smaller, the page begins to wind in upon itself, which may be an interesting way of implementing a scroll-like effect.

The third and final parameter ρ represents the rotation of the page around the y axis, or the spine of the book. As mentioned in the paper, a complete page turn comprises both a deformation and rotation component. While we could combine both processes into one step, for illustrative purposes it's easier to keep them separate and apply ρ separately as a basic rotation transform.

Ok, enough with the math, let's see some…

Examples

If you don't have Xcode installed, take a look at this Grapher example. Grapher is a wonderful yet little-known graphing application lurking in the Applications/Utilities folder. This example includes only the page deformation equations. Rotation is omitted because Grapher does not support 4x4 matrices, which are needed for 3D affine transformations. (It's possible to implement through matrix expansion but I don't want to clutter up the math any more than necessary.)

The equations are taken pretty much straight from the PARC research paper, though I had to substitute d for r and h for θ since Grapher reserves r and θ for drawing in polar coordinates. Click on the little triangle next to t to play the page curl animation. The effect is very basic since θ and A are defined here as linear functions of t.

You can adjust the values of θ and A manually but it's a little tricky since Grapher allows only one parameter to be animated at a time. To do this, select t at the top of the equation list then click on the square stop button above the slider. Select either of the next two equations for θ or A and delete the t variable. Press return to confirm the edit then select Equation—>Animate Parameter from the menu. Click on the settings button to adjust the parameters to your liking. Go ahead and play around with it for a while before coming back here.

If you didn't already, you may want to check out my original proof-of-concept Unity demo. I've recreated a similar version for iPad using OpenGL ES 1.1 (1.3 MB Xcode project). After compiling and running the app, you should see a page continually flipping from right to left, with sliders that adjust for the current parameter values. Stop the animation by clicking on the Animate switch, or grabbing any one of the sliders (if you can!).



The Time slider automatically calculates appropriate values of rho, theta, and A for time t to generate a decent looking page flip animation. This is acceptable for an automatic, non-interactive page flip, say for when the user taps or swipes the page to quickly go to the next one. However, to generate a page curl that dynamically tracks the user's finger requires calculating appropriate values of rho, theta, and A from the touch location as a 2D coordinate. That requires a bit more complicated math and isn't included yet, but will hopefully be addressed in a future article.

While the animation is stopped, drag the rho, theta, and A sliders to see how they affect the geometry of the curl.

Code

The real meat of the code is in the CCPage class, specifically the -deform method which performs all the magic in a scant few lines of code, in fact just six lines for the actual deformation process! The method takes no arguments because rho, theta, and A are properties of CCPage. Just set them before calling -deform. Take a close look and feel free to step through it in the debugger. There's plenty of inline documentation to guide you through.

- (void)deform
{
  Vertex2f  vi;   // Current input vertex
  Vertex3f  v1;   // First stage of the deformation
  Vertex3f *vo;   // Pointer to the finished vertex
  CGFloat R, r, beta;
  for (ushort ii = 0; ii < numVertices_; ii++)
  {
    // Get the current input vertex.
    vi    = inputMesh_[ii];                       
    // Radius of the circle circumscribed by vertex (vi.x, vi.y) around A on the x-y plane
    R     = sqrt(vi.x * vi.x + pow(vi.y - A, 2)); 
    // Now get the radius of the cone cross section intersected by our vertex in 3D space.
    r     = R * sin(theta);                       
    // Angle subtended by arc |ST| on the cone cross section.
    beta  = asin(vi.x / R) / sin(theta);       
   
    // *** MAGIC!!! ***
    v1.x  = r * sin(beta);
    v1.y  = R + A - r * (1 - cos(beta)) * sin(theta); 
    v1.z  = r * (1 - cos(beta)) * cos(theta);
    // Apply a basic rotation transform around the y axis to rotate the curled page.
    // These two steps could be combined through simple substitution, but are left
    // separate to keep the math simple for debugging and illustrative purposes.
    vo    = &outputMesh_[ii];
    vo->x = (v1.x * cos(rho) - v1.z * sin(rho));
    vo->y =  v1.y;
    vo->z = (v1.x * sin(rho) + v1.z * cos(rho));
  }  
}

This algorithm simply iterates through each vertex in our input mesh, deforming it according to properties rho, theta, and A, and puts the result in our output mesh, which is fed to our OpenGL renderer for display. Since each vertex is completely independent of any other, this algorithm is a prime candidate for parallelization, such as with blocks or OpenGL ES 2.0 vertex shaders.

The rest of the project is mostly OpenGL and application infrastructure hacked together from Xcode templates and demos so don't look to it as a shining example of good application design, but feel free to poke around if you want.

Notes

The code is intentionally verbose for illustrative purposes and far from optimized. The intermediate variables may be handy when stepping through with the debugger. Look forward to future articles where I revisit parts of the code for cleanup, optimization, and adding additional features such as lighting and shadows, triangle strips, blocks, and OpenGL 2.0 support. (Triangle strip support added and enabled with USE_TRIANGLE_STRIPS in CCCommon.h.)

Turning a page in real life usually does not form perfect conical shapes as in this algorithm. They'll typically be elliptical cones or some other irregular shape, sometimes with two curves if the fingers are pinching the corner of the page. For most intents and purposes though this algorithm gives results that are Good Enough, with an almost trivial implementation.

Part of the reason this writeup took a while is that I abandoned my original algorithm that modeled a page as a solid 3D cuboid. This approach could account for the general but rare case where the thickness should be visibly noticeable, say when flipping a large chunk of pages at once in a telephone directory, but for most practical purposes this was highly unlikely. Therefore I decided to rewrite the code to model a page as two independent coplanar meshes to represent the front and back faces. This greatly simplifies the math and texture mapping but can only handle pages of zero thickness (which is perfectly fine for the vast majority of cases).

I'm still relatively new to OpenGL and Objective-C in general, so I welcome any tips, suggestions, or corrections. Thanks for taking the time to read my first blog post. Hope you enjoyed it!

References and acknowlegements

1. Hong, L., Card, S. K., & Chen, J. (2004). Deforming pages of 3D electronic books. Retrieved from Palo Alto Research Center, http://www2.parc.com/istl/groups/uir/publications/items/UIR-2004-10-Hong-DeformingPages.pdf

Thanks to Jeff LaMarche for his extensive and incredibly helpful OpenGL ES from the ground up tutorials.