Wednesday, May 5, 2010

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.

Unity example

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.

Cone_illustration.png

θ 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

Grapher example

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!).

Simulator_example.png

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.

33 comments:

  1. Awesome post man!!
    Can you add the Grapher file to the post? Or share it in any other form. It would greatly help my learning on this subject. Thanks again!

    ReplyDelete
  2. Thanks! There's a link to the Grapher file right underneath its screenshot, though it might not be obvious. Here it is again: Curl.gcx.zip, 106 KB.

    ReplyDelete
  3. This is great information, thanks a lot. I'm having trouble downloading your iPad OpenGL ES 1.1 demo project, can you verify that is still up there?

    Thanks!

    ReplyDelete
  4. Sorry about that. It should be working now. The files are mirrored here in case that happens again:

    Grapher file: Curl.gcx.zip
    Xcode project: ConeCurl.zip
    Mac Unity application: PbP_Demo.zip

    ReplyDelete
  5. Great code. how would i get this to roll up/down?

    ReplyDelete
  6. Hi,

    thanks for this post. Any hints how to use it for animating a UIView and show the view behind?

    I'm not really good in OpenGL. I looked through the code but don't understand it very well.

    Matthias

    ReplyDelete
  7. could you please build the app it in iphone os 3.1.3 . I donot have snowleopard to update to 3.2.

    ReplyDelete
  8. @Adnan: I created the project using Xcode's OpenGL ES template for iPad, which requires 3.2. However, there's no reason it shouldn't run on 3.1.3 with a few modifications, such as iPhone xib files.

    @Matthias: To show a page underneath the curling page, you can simply draw a two-triangle quad textured with the image of the underlying page.

    @Scott Andrew: Thanks! Curling up/down is just a matter of swapping the x and y axes, or rotating 90º around the z axis.

    I'll try to flesh out the project a bit more and integrate in some of your comments after WWDC.

    ReplyDelete
  9. Great stuff!
    Any chance you can post the Unity project files??

    ReplyDelete
  10. For some reason I can't find the original Unity source files or otherwise I would have posted them. It was just hacked together in a few hours as a Unity learning experiment anyway, so it's probably for the better. The salient bits were ported almost verbatim into the Xcode project.

    ReplyDelete
  11. Great subject. Thank you very much, wdnuon.
    I waiting for some updates. :)

    ReplyDelete
  12. Great great work! I am trying to add "thickness" to each page but I am new to OpenGL and I am kind of lost. I have been experimenting with CreateMesh() inside CCPage.m but unsuccessfully. Any help (small or big) would be very very appreciated.

    ReplyDelete
  13. WOW!
    Building a framework, or a 3rd party library for a page flip, by adding touch detection and handling - will probably become one of the most wanted libraries out there.
    I must say it looks beautiful, I never worked with OGL ES and I'm having a hard time understanding the code. But I must say - this is beautiful.

    ReplyDelete
  14. Hi,

    first of all GREAT POSTING! I need to implement this page curl now with all extras (shadows, page follows dynamically your tap, etc). So my question is if you made some more progress in integrating these features and can help me with that? I need to make the input parameters be a function of the (x,y) position of my current tap.

    cheers
    stefan

    ReplyDelete
  15. Excellent! I am trying to implement a full book approach (multiple pages drawn). Could you point to some key elements in your code that need to change so that I can more than one CCPage ?

    ReplyDelete
  16. Massively impressed by this. I think you are doing yourself a disservice by saying you don't know OpenGL or Obj C very well.

    Is there any news on the future articles you mentioned…I'm looking into adapting your original code to handle touch movements up and down (and thus affecting the page curl accordingly - you mentioned this)…but sadly my OpenGL is almost non existent so it's quite a struggle!

    ReplyDelete
  17. First thanks for the great info and sample. Can someone help me how to change the iPad sample to render the page image in full screen and move the book middle on the left side?

    ReplyDelete
  18. Hey great job! Can someone help me what I must to do if I want to change che size of the images? I want to have fullscreen page.

    ReplyDelete
  19. Wonderful post! Thanks for sharing

    ReplyDelete
  20. Does anyone know whether using this algorithm is safe from an appstore perspective ? I'm afraid it would go against apple rules, as this effect is probably covered by an apple patent.
    I guess they didn't release their original effect in the SDK for a reason, probably to keep it for their own apple products, eg iBook.

    ReplyDelete
  21. Hi ,

    would you please sent me the initial value of A, R, r, theta and beta. As I am not able to find these detail in the PbP_Demo.zip file,
    I working on windows, it is not opening most the files in this zip.

    I have used A = -15 and rho = 0.0 and theta = 90.0, but I am not getting correct results.

    would anyone please send me A, R, r, theta and beta values. I would greatly appriciate your reply.

    Regards
    Muthuvel.P

    ReplyDelete
  22. Readers of this post may appreciate http://blog.flirble.org/2010/10/08/the-anatomy-of-a-page-curl/ (by me) that took this most useful work and extended it a bit further... including some discussion on tracking touches.

    ReplyDelete
  23. are we allowed to use your code in our product? or is there a license requirement?

    ReplyDelete
  24. Wow, Im simply astonished by this, I have been looking a resources like this for months.

    I see you did some stuff in unity, Im about to buy the license, and a page turn its a MUST for my requirements, but I want to make the turn effect when changing scenes. As I can tell you are expert unity user :D, maybe you can help me out here, can I achieve this effect when changing scenes in unity?, is it difficult to do it?, I mean, Im gonna use unity not to do Gears of wars, or something, but simple interactive apps, in 2D and 3D.

    Thanks for great post.
    I guess my decision on buying it will depend much in what you let me know.

    ReplyDelete
  25. @GustavPicora: you'll probably need render-to-texture for that, render the current scene to a texture then put that in the page mesh, then let it animate. You'll need the Pro license to access render-to-texture feature

    ReplyDelete
  26. @W. Dana Nuon: I took the liberty of extracting the source files from the Unity Mac App binary file that you gave and got two scripts, PageBlock and PageCurl. I hope you don't mind that I shared it to the community: http://forum.unity3d.com/threads/65639-Page-Flipping-Behaviour-Effect?p=419976&viewfull=1#post419976

    ReplyDelete
  27. Any chance to get back the Unity source files ? I'd really love to study the source code there... Would be a very nice Xmas present !

    ReplyDelete
  28. Would you be willing to translate this to Android? ;) I assume you'd use BitmapMesh.
    http://developer.android.com/resources/samples/ApiDemos/src/com/example/android/apis/graphics/BitmapMesh.html

    ReplyDelete
  29. Same here, would also be quite interested in the Android implementation! Anybody got something on this as a starting point?

    ReplyDelete
  30. Very nice! I changed two lines in the Xcode project to get the revealed page (back) to not be reversed.

    ES1Renderer.m line 109-110:

    CGContextTranslateCTM (bitmapContext, width, height); // added width
    CGContextScaleCTM (bitmapContext, -1.0, -1.0); // flipped x also

    Thanks for sharing your excellent results!

    ReplyDelete
  31. Hi W. Dana Nuon,

    Thanks for a great article. It really gave some inspiration and motivation for doing something similar, on Android though, and using a bit different, more simple, approach. At first I went with what you describe here but frankly speaking, didn't have much idea where to continue once I had implemented what you present here. Namely, I was more interested in following pointer movement than rendering a best possible visual experience using time for interpolating between page start and end position. Also having fixed point viewpoint from the top gave a reason to stick with something which really looks ugly if looked from arbitrary angle.

    If you still find the topic interesting, here's what I ended up with. Commentary is not as good compared to what you provide us here but am hoping it described the idea somewhat well.

    http://github.com/harism/android_page_curl/

    Thanks in any case,
    H

    ReplyDelete
  32. I created a Page Curl like filter using OpenGL and CoreGraphics. Speaking about math, shadow casting, shader etc. was a nightmare :-) but it's realistic and it's very close to the iBooks one.

    http://api.mutado.com/mobile/paperstack/

    I'm working on an easy-to-use API to integrate the GLView and other classes in a common project (like a PDF viewer).

    To resume, the logic behind is based on a conical page deformation but to be realistic like iBooks, the math is a bit different from your conical deformation. The filter is done, I hope to complete the API it in a couple of weeks then I'll publish it on github.

    Cheers,
    @lomanf

    ReplyDelete
  33. My cousin recommended this blog and she was totally right keep up the fantastic work!
    Flip Books Software

    ReplyDelete