August 2013
Volume 28 Number 8
DirectX - Real-Time, Realistic Page Curling with DirectX, C++ and XAML
By Eric Brumer | August 2013
During the development of Windows 8 and Visual Studio 2012, the Microsoft C++ team created some open source apps to showcase the various C++ technologies available to software developers. One of these apps is Project “Austin,” a digital note-taking app written in C++, using DirectX and XAML on the Windows Runtime (WinRT).
In this app, a user can create a notebook and jot down some notes or scribble diagrams. There’s support for adding and deleting pages, different ink colors, and adding image files from a PC or from SkyDrive. Figure 1 shows some screenshots of the app in action.
.png "Project “Austin”")
Figure 1 Project “Austin”
Users can view their notebooks in three ways: a single row of pages (as in Figure 1), a grid of pages or as if the pages were stacked on top of one another. In this stacked view, the user can flip through pages by swiping his finger across the page, as if he were flipping through pages in a real book. The digital pages are curled in real time based on the position of the user’s finger as he flips the page. Figure 2 shows the page curling in action.
.png "Page Curling")
Figure 2 Page Curling
The page-curling feature also handles page uncurling. When the user lets go of a page while curling, the page acts like a real piece of paper: if the page is below a certain threshold, it uncurls back to a lay-flat position; if the page is above the threshold, it uncurls but finishes turning.
This article describes in depth the geometry, technologies and code used to perform real-time page curling and uncurling.
The Geometry of Page Curling
Before exploring the overall design, I’ll get the geometry and math out of the way. This information is largely taken from my MSDN blog post, “Project Austin Part 2 of 6: Page Curling” (bit.ly/THF40f).
The 2006 paper, “Turning Pages of 3D Electronic Books” (L. Hong, S.K. Card and J. Chen), describes how page curling can be simulated by deforming the paper around an imaginary cone, as shown in Figure 3. By changing the shape and position of the cone you can simulate more (or less) curling.
.png "Flat Paper (Black) Curling Around a Cone (Green) to Become the Curled Paper (Red)")
Figure 3 Flat Paper (Black) Curling Around a Cone (Green) to Become the Curled Paper (Red)
Similarly, page curling can also be simulated by deforming the paper around an imaginary cylinder, as shown in Figure 4.
.png "Flat Paper (Black) Curling Around a Cylinder (Green) to Become the Curled Paper (Red)")
Figure 4 Flat Paper (Black) Curling Around a Cylinder (Green) to Become the Curled Paper (Red)
My method for page curling is as follows:
- If the user is curling from the top-right of the page, deform the page around a cone with angle θ and apex at coordinates (0, Ay, 0).
- If the user is curling from the center-right of the page, deform the page around a cylinder with radius r.
- If the user is curling from the bottom-right of the page, deform the page around an inverted cone.
- If the user is curling anywhere in between, deform the page around the linear combination of a cone and a cylinder, based on the y-coordinate of the input.
- After deforming, rotate the paper around the y axis.
Here are the details to transform a page around a cylinder. (The Hong article describes similar geometry to transform a page around a cone.) Given the point Pflat with coordinates {x1, y1, z1 = 0} of a flat page, the goal is to transform it into Pcurl with coordinates {x2, y2, z2}, the point on a cylinder with radius r that’s lying on the “spine” of the book. Now take a look at Figure 5, which shows the end of the cylinder. You can see the x and z axes (the y axis runs in and out of the page). Note that I’m representing the flat paper and the cylinder using the same colors as in the previous figures.
.png "Transforming Pflat to Pcurl")
Figure 5 Transforming Pflat to Pcurl
The key insight is that the distance from the origin to Pflat(x1) is the same as the arc distance from the origin to Pcurl along the cylinder. So, from simple geometry, I can say that the angle β = x1/r. Now, to get Pcurl, I take the origin, move it down by r on the z axis, rotate around β, then move it up by r on the z axis. The curlPage method in Figure 6 shows the code to deform the vertex buffer for a page. The vertex buffer and page coordinate information are abstracted away.
Figure 6 Deforming the Vertex Buffer
void page_curl::curlPage(curl_parameters curlParams)
{
float theta = curlParams.theta;
float Ay = curlParams.ay;
float alpha = curlParams.alpha;
float conicContribution = curlParams.conicContribution;
// As the user grabs toward the middle-right of the page, curl the
// paper by deforming it on to a cylinder. The cylinder radius is taken
// as the endpoint of the cone parameters: for example,
// cylRadius = R*sin(theta) distance to where R is the the rightmost
// point on the page, all the way up.
float cylR = sqrt( _vertexCountX * _vertexCountX
+ (_vertexCountY /2 - Ay)*( _vertexCountY /2 - Ay));
float cylRadius = cylR * sin(theta);
// Flipping from top corner or bottom corner?
float posNegOne;
if (conicContribution > 0)
{
// Top corner
posNegOne = 1.0f;
}
else
{
// Bottom corner
posNegOne = -1.0f;
Ay = -Ay + _vertexCountY;
}
conicContribution = abs(conicContribution);
for (int j = 0; j < _vertexCountY; j++)
{
for (int i = 0; i < _vertexCountX; i++)
{
float x = (float)i;
float y = (float)j;
float z = 0;
float coneX = x;
float coneY = y;
float coneZ = z;
{
// Compute conical parameters and deform
float R = sqrt(x * x + (y - Ay)*(y - Ay));
float r = R * sin(theta);
float beta = asin(x / R) / sin(theta);
coneX = r * sin(beta);
coneY = R + posNegOne * Ay - r * (1 - cos(beta)) * sin(theta);
coneZ = r * (1 - cos(beta)) * cos(theta);
// Then rotate by alpha about the y axis
coneX = coneX * cos(alpha) - coneZ * sin(alpha);
coneZ = coneX * sin(alpha) + coneZ * cos(alpha);
}
float cylX = x;
float cylY = y;
float cylZ = z;
{
float beta = cylX / cylRadius;
// Rotate (0,0,0) by beta around line given by x = 0, z = cylRadius
// aka Rotate (0,0,-cylRadius) by beta, then add cylRadius back
// to z coordinate
cylZ = -cylRadius;
cylX = -cylZ * sin(beta);
cylZ = cylZ * cos(beta);
cylZ += cylRadius;
// Then rotate by alpha about the y axis
cylX = cylX * cos(alpha) - cylZ * sin(alpha);
cylZ = cylX * sin(alpha) + cylZ * cos(alpha);
}
// Combine cone & cylinder results
x = conicContribution * coneX + (1-conicContribution) * cylX;
y = conicContribution * coneY + (1-conicContribution) * cylY;
z = conicContribution * coneZ + (1-conicContribution) * cylZ;
_vertexBuffer[j * _vertexCountX + i].position.x = x;
_vertexBuffer[j * _vertexCountX + i].position.y = y;
_vertexBuffer[j * _vertexCountX + i].position.z = z;
}
}
}
The variable conicContribution, ranging from -1 to +1, captures the position on the y axis the user has touched. A value of -1 represents the user touching the bottom of the page, and +1 represents the top of the page.
The complete set of deformation parameters is captured in curl_parameters:
struct curl_parameters
{
curl_parameters() {}
curl_parameters(float t, float a, float ang, float c) :
theta(t), ay(a), angle(ang), conicContribution(c) {}
float theta; // Angle of right-cone
float ay; // Location on y axis of cone apex
float alpha; // Rotation about y axis
float conicContribution; // South tip cone == -1, cylinder == 0,
north tip cone == 1
};
Note that the cylinder radius is missing from this struct; I’m taking a shortcut by computing it based on the cone parameters, as in Figure 6.
Architecture
With the geometry out of the way, I can focus on the design and page-curling architecture. The goal of the design is to allow for realistic page curling and uncurling without losing fluidity. For instance, the user should be able to partially curl a page, let go so the page uncurls somewhat, then continue curling the page, while the animation remains fluid and realistic.
The Project Austin page-curling architecture is implemented in the page_curl class, shown in Figure 7.
Figure 7 The page_curl Class
class page_curl
{
public:
void attachPage(const std::shared_ptr<paper_sheet_node> &pageNode);
void startUserCurl(float x, float y);
void startAutoCurl();
void onRender();
private:
struct curl_parameters
{
curl_parameters() {}
curl_parameters(float t, float a, float ang, float c) :
theta(t), ay(a), angle(ang), conicContribution(c) {}
float theta; // Angle of right cone
float ay; // Location on y axis of cone apex
float alpha; // Rotation about y axis
float conicContribution;
// South tip cone == -1, cylinder == 0, north tip cone == 1
};
void continueAutoCurl();
page_curl::curl_parameters computeCurlParameters(float x, float y);
void page_curl::curlPage(page_curl::curl_parameters curlParams);
... Other helpers that will be discussed later ...
std::shared_ptr<paper_sheet_node> _pageNode; // Page abstraction
bool _userCurl; // True if the user is curling the page
bool _autoCurl; // True if the page is uncurling
float _autoCurlStartTime; // The time the user let go to start uncurling
// Allows for smooth animations
curl_parameters _currentCone;
curl_parameters _nextCone;
};
Here are the methods that matter:
void page_curl::attachPage(const std::shared_ptr<paper_sheet_node> &pageNode) is called by the Project Austin code whenever a page is curled. The paper_sheet_node data structure captures all the pertinent information about the page coordinate system, as well as the DirectX vertex buffer used to render this particular page. The implementation isn’t discussed in this article.
void page_curl::startUserCurl(float x, float y) is called by the Project Austin user input handler code to indicate the user has pressed his finger down and is curling at the location (x, y). This code does the following:
- sets the _userCurl state bit to indicate the user is curling the page
- unsets the _autoCurl state bit to stop any uncurling if it’s in progress
- sets _nextCurlParams to the deformation parameters based on the user’s position (x, y)
void page_curl::startAutoCurl is called by the Project Austin user input handler to indicate the user has let go of the screen. This code does the following:
- unsets the _userCurl state bit to indicate the user is no longer curling the page
- sets the _autoCurl state bit to indicate an uncurl is in progress, with a time stamp of when the uncurl started
void page_curl::onRender is called by the Project Austin render loop for each frame. Note that this is the only function that actually deforms the vertex buffer. This code works as follows:
- If _userCurl or _autoCurl is set, the code deforms the vertex buffer to the parameters computed from _nextCurlParams and _currentCurlParams. Using both ensures smooth curling, as discussed later in this article.
- If _autoCurl is set, the code calls continueAutoCurl
- Sets _currentCurlParams to _nextCurlParams
void page_curl::continueAutoCurl is called by page_curl::onRender if the page is uncurling. This code:
- computes _nextCurlParams based on when the uncurl started
- unsets _autoCurl if the page has completed curling
page_curl::curl_parameters page_curl::computeCurlParameters(float x, float y) computes the curl parameters (theta, Ay, alpha, conicContribution) based on the user input.
Now that you’ve seen the overall architecture, I’ll fill in each of the public and private methods. I chose the overall design to make it easy to ensure smooth animation. The key is splitting up startUserCurl and onRender, and maintaining the state between the two.
I’ll now discuss some of these methods, providing either motivation or background regarding the design decisions.
Smooth Animation
Given the functions described previously, it might seem appropriate for startUserCurl to simply read the position of the user’s finger, and for onRender to simply deform the page to those parameters.
Unfortunately, this particular animation can look ugly if the user moves her finger very fast. If onRender draws the deformed page at 60 frames per second (fps), it’s possible that between two frames the user moved her finger halfway across the screen. On one frame, the page is deformed to a nearly flat state. If, on the very next frame, the page is deformed to a fully curled state, the fluidity of the animation is lost and ... well, it looks ugly.
To get around this, I keep track of not only _nextCurlParams (the desired location where the curl should go based on either user input or the formulas for uncurling), but also the current state of the curl in _currentCurlParams. If the desired curl location is too far from the existing curl location, then I should instead be curling to an intermediate value that ensures the animation is smooth.
The term “too far” is open to interpretation. Because there are four elements in the cone_parameters structure, and each one is a floating-point number, I treat _currentCurlParams and _nextCurlParams as points in four-dimensional space. The distance between the two curl parameters is then just the distance between two points.
Similarly, the term “intermediate value” is also open to interpretation. If the _nextCurlParams is too far from _currentCurlParams, I choose an intermediate point that’s closer to _nextCurlParams proportional to the distance between the two points. So, if the user starts with a flat page and curls it extremely quickly, the page appears initially to spring forward quickly, but then slows down the closer it gets to the desired location. Because this happens at 60 fps, the overall effect is very minor, but from a usability standpoint the results look great.
Figure 8 shows the full rendering code.
Figure 8 The Rendering Code
void page_curl::onRender()
{
// Read state under a lock
curl_parameters nextCurlParams;
curl_parameters currentCurlParams;
bool userCurl;
bool autoCurl;
LOCK(_mutex)
{
nextCurlParams = _nextCurlParams;
currentCurlParams = _currentCurlParams;
userCurl = _userCurl;
autoCurl = _autoCurl;
}
// Smooth going from currentCurlParams to nextCurlParams
curl_parameters curl;
float dt = nextCurlParams.theta - currentCurlParams.theta;
float da = nextCurlParams.ay - currentCurlParams.ay;
float dr = nextCurlParams.alpha - currentCurlParams.alpha;
float dc = nextCurlParams.conicContribution -
currentCurlParams.conicContribution;
float distance = sqrt(dt * dt + da * da + dr * dr + dc * dc);
if (distance < constants::general::maxCurlDistance())
{
curl = nextCurlParams;
}
else
{
float scale = maxDistance / distance;
curl.theta = currentCurlParams.theta + scale * dt;
curl.ay = currentCurlParams.ay + scale * da;
curl.alpha = currentCurlParams.alpha + scale * dr;
curl.conicContribution =
currentCurlParams.conicContribution + scale * dc;
}
// Deform the vertex buffer
if (userCurl || autoCurl)
{
LOCK(_mutex)
{
_currentCurlParams = curl;
}
this->curlPage(curl);
}
// Continue (or stop) uncurling
if (autoCurl)
{
this->continueAutoCurl();
}
}
Handling User Input (and Lack Thereof)
Project Austin, being a C++ DirectX XAML app, makes use of the WinRT APIs. Gesture recognition is handled by the OS—specifically by Windows::UI::Input::GestureRecognizer.
Hooking up the onManipulationUpdated event to call startUserCurl(x, y) when the user is curling the page is straightforward. The code for startUserCurl is then:
// x is scaled to (0, 1) and y is scaled to (-1, 1)
void page_curl::startUserCurl(float x, float y)
{
curl_parameters curl = this->computeCurlParameters(x, y);
LOCK(_mutex)
{
// Set curl state, to be consumed by onRender()
_nextCurlParams = curl;
_userCurl = true;
_autoCurl = false;
}
}
Similarly, it’s straightforward to hook up the onManipulationCompleted event to call startAutoCurl when the user lets go of the page. Figure 9 shows the code for startAutoCurl.
Figure 9 The startAutoCurl Method
void page_curl::startAutoCurl()
{
LOCK(_mutex)
{
// It's possible the user let go, but the page is
// already fully curled or uncurled
bool shouldAutoCurl = !this->doneAutoCurling(curl);
_userCurl = false;
_autoCurl = shouldAutoCurl;
if (shouldAutoCurl)
{
_autoCurlStartTime = constants::general::currentTime();
}
}
}
The more interesting code is for handling auto-uncurling when the user lets go of the page; the page will continue to uncurl until it’s completely flat or until it has completely curled forward. I base this transformation on the current curl parameters and the elapsed time (squared) since uncurling started. This way, the page starts to uncurl slowly but as time passes it uncurls faster and faster. This is a cheap way to attempt to simulate gravity. Figure 10 shows the code.
Figure 10 Handling Auto-Uncurling
void page_curl::continueAutoCurl()
{
LOCK(_mutex)
{
if (this->doneAutoCurling(curl))
{
_autoCurl = false;
}
else
{
float time = constants::general::currentTime() -
_autoCurlStartTime;
_nextCurlParams = this->nextAutoCurlParams(
_currentCurlParams,
time * time);
}
}
}
Tuning the Curling for Realism
Absent from the previous sections is the code for computeCurlParameters, doneAutoCurling and nextAutoCurlParams. These are tunable functions that involve constants, formulas and heuristics that are the result of hours of painstaking trial and error.
For example, I spent many, many hours trying to achieve reasonable results for computeCurlParameters. Figure 11 shows two versions of the code—one that simulates the curling of a thick piece of paper (the pages inside a book), and a second that simulates a plastic cover (the cover of a softcover book, for example).
Figure 11 Curling Two Kinds of Pages
// Helper macro for a straight line F(x) that passes through {x1, y1} and {x2, y2}.
// This can't be a template function (C++ doesn't let you have float literals
// as template parameters).
#define STRAIGHT_LINE(x1, y1, x2, y2, x)
(((y2 - y1) / (x2 - x1)) * (x - x1) + y1)
page_curl::curl_parameters page_curl::paperParams(float x, float y)
{
float theta, ay, alpha;
if (x > 0.95f)
{
theta = STRAIGHT_LINE(1.0f, 90.0f, 0.95f, 60.0f, x);
ay = STRAIGHT_LINE(1.0f, -20.0f, 0.95f, -5.0f, x);
alpha = 0.0;
}
else if (x > 0.8333f)
{
theta = STRAIGHT_LINE(0.95f, 60.0f, 0.8333f, 55.0f, x);
ay = STRAIGHT_LINE(0.95f, -5.0f, 0.8333f, -4.0f, x);
alpha = STRAIGHT_LINE(0.95f, 0.0f, 0.8333f, 13.0f, x);
}
else if (x > 0.3333f)
{
theta = STRAIGHT_LINE(0.8333f, 55.0f, 0.3333f, 45.0f, x);
ay = STRAIGHT_LINE(0.8333f, -4.0f, 0.3333f, -10.0f, x);
alpha = STRAIGHT_LINE(0.8333f, 13.0f, 0.3333f, 35.0f, x);
}
else if (x > 0.1666f)
{
theta = STRAIGHT_LINE(0.3333f, 45.0f, 0.1666f, 25.0f, x);
ay = STRAIGHT_LINE(0.3333f, -10.0f, 0.1666f, -30.0f, x);
alpha = STRAIGHT_LINE(0.3333f, 35.0f, 0.1666f, 60.0f, x);
}
else
{
theta = STRAIGHT_LINE(0.1666f, 25.0f, 0.0f, 20.0f, x);
ay = STRAIGHT_LINE(0.1666f, -30.0f, 0.0f, -40.0f, x);
alpha = STRAIGHT_LINE(0.1666f, 60.0f, 0.0f, 95.0f, x);
}
page_curl::curl_parameters cp(theta, ay, alpha, y);
return cp;
}
page_curl::curl_parameters page_curl::plasticParams(float x, float y)
{
float theta, ay, alpha;
if (x > 0.95f)
{
theta = STRAIGHT_LINE(1.0f, 90.0f, 0.9f, 40.0f, x);
ay = STRAIGHT_LINE(1.0f, -30.0f, 0.9f, -20.0f, x);
alpha = 0.0;
}
else
{
theta = STRAIGHT_LINE(0.95f, 40.0f, 0.0f, 35.0f, x);
ay = STRAIGHT_LINE(0.95f, -20.0f, 0.0f, -25.0f, x);
alpha = STRAIGHT_LINE(0.95f, 0.0f, 0.0f, 95.0f, x);
}
page_curl::curl_parameters cp(theta, ay, angle, y);
return cp;
}
The code for knowing when curling is complete merely involves checking whether the page is completely flat or is completely curled:
bool page_curl::doneAutoCurling(curl_parameters curl)
{
bool doneCurlBackwards = (curl.theta > 89.999f)
&& (curl.ay < -69.999f)
&& (curl.alpha < 0.001f)
&& (abs(curl.conicContribution) > 0.999f);
bool doneCurlForwards = (curl.alpha > 99.999f);
return doneCurlBackwards || doneCurlForwards;
}
And last, my version of auto-curl, shown in Figure 12, relies on the current curl position and the square of the elapsed time since the curl started. Instead of uncurling a page in the same way it’s curled, I simply have the curl parameters linearly approach the parameters for a flat page, but let the page fall backward (if the user let go when the page was only slightly curled) or forward (if the user let go when the page was mostly curled). Using this technique and the square of the elapsed time, the page has a nice bounce to it when you let go. I really like how it looks.
Figure 12 My Version of Auto-Curling
page_curl::curl_parameters page_curl::nextAutoCurlParams(
curl_parameters curl, float time)
{
curl_parameters nextCurl;
if (curl.alpha > 40)
{
nextCurl.theta = min(curl.theta + time/800000.0f, 50.0f);
nextCurl.ay = curl.ay;
nextCurl.alpha = min(curl.alpha + time/200000.0f, 100.0f);
}
else
{
nextCurl.theta = min(curl.theta + time/100000.0f, 90.0f);
nextCurl.ay = max(curl.ay - time/200000.0f, -70.0f);
nextCurl.alpha = max(curl.alpha - time/300000.0f, 0.0f);
}
if (curl.conicContribution > 0.0)
{
nextCurl.conicContribution =
min(curl.conicContribution + time/100000.0f, 1.0f);
}
else
{
nextCurl.conicContribution =
max(curl.conicContribution - time/100000.0f, -1.0f);
}
return nextCurl;
}
One thing I wish I had implemented is page inertia when uncurling. Users should be able to fling the page. When they let go, the page should continue curling in the same direction it was flung, until drag forces it to stop and lay back flat. This could be implemented by adding history to onRender, keeping track of the last few positions of the user’s finger, and making use of this in the formulas in nextAutoCurlParams.
Performance
The curlPage method has to do quite a bit of math to curl a single page. By my count, there are nine calls to the sin function, eight to cos, one to arcsin, one to sqrt, and around two dozen multiplies, plus additions and subtractions—for each vertex in the paper model—for each frame that’s being rendered!
Project Austin aims for 60 fps; thus, processing each frame can take no more than 15 ms, lest the app feel sluggish.
The necessary performance is achieved by ensuring that the innermost loop is vectorized, where the Visual Studio C++ compiler generates Streaming SIMD Extensions 2 (SSE2) instructions to take advantage of CPU vector units. The compiler is able to vectorize all of the transcendental functions in the math.h header file.
In this case, the inner loop calculates the curled position for four vertices at a time. The performance boost frees up the CPU for other rendering tasks, such as applying shadows to the curled page.
Read more about the auto-vectorizer on MSDN and on the Parallel Programming in Native Code blog (bit.ly/bWfC5Y).
Wrapping Up
I’d like to thank the great people who worked on Project Austin, in particular Jorge Pereira, George Mileka and Alan Chan. By the time I started working on the project they already had a great app, and I feel fortunate to have spent some time adding a little realism to it. It helped me understand beauty in simplicity, and how tough it can be to make things simple!
You can find more information about the app, including some videos, on the MSDN blogs by searching for Project Austin. And you’ll find code at austin.codeplex.com.
Eric Brumer is a software development engineer at Microsoft, working on the Visual C++ compiler optimizer team. Reach him at ericbr@microsoft.com.
THANKS to the following technical expert for reviewing this article: George Mileka (Microsoft)
George Mileka is a software development engineer at Microsoft, working on the Visual C++ Libraries team. Reach him at gmileka@microsoft.com.