Popup: Automatic Paper Architectures from 3D Models

Pop up: Automatic Paper Architecture Frkm 3X Models
A CGM project by Stav Shapiro
Supervised by Dmitry Rudoy

Introduction

3D paper architecures are models created by cutting and folding 2D sheets of paper. A subgroup of these paper architectures are popup paper architecures, which are created by folding and cutting sheets of papers in such a way that when the paper is folded along a central line, the 3D model pops out. e.g:

Planning, and constructing such models is incredibly difficult and requires practice and skill.

In this project I have implemented a method suggested in the paper Popup:Automatic Paper Architecture from 3D Models to automatically construct a cut and fold layout for an A4 paper, from a 3D input model.

The suggested method constructs a model which satisfies the necessary conditions of a foldable paper architecture and also 'wraps around' the input model in such a way that the output model resembles the input.

The Theory

To understand the sufficient conditions a paper architecture, we first need to learn the langauge and definitions to describe:

PLS

Piecewise Linear Surface, or PLS is a collection of planar, non intersecting and non overlapping patches which are interconnected via shared straight edges.

PLPA

Planar layout for Paper Architecture, or PLPA T is defined as

1. A PLS whose patches are co planar
2. T forms a rectangular domain with possible holes and there are patches called backdrop and ground that touch the boundary of the rectangular domain and share a straight edge along the mid line of the rectangle. The foldability

for example:

In order for the output model to be a paper architecture, it has to satisfy 2 conditions:

1.Foldability - The PLS is said to be foldable if it can be folded continously from a a sheet of paper
2.Realizability - is said to be realizable if The continous transformation mentioned above is unique.


What does this actually mean?

The foldability condition merely says that the model has to be made out of pieces of paper that existed in the original sheet of paper in first place.

The Realizability condition says that the final product has to be stable, e.g it has to hold itself together without extra support.

The Implementation

The algorithm works on a 3D model dened by a triangular mesh, then it takes the following steps:

1. Computing a parallel PLS approximation of the input model, this initial PLS is referred to as the visible PLS. This visible PLS ensures the foldability conditions in Theorem 1.131

2. Modifying the visible PLS to meet the realizability condition in Theorem

Step 1 - Finding the Visible PLS

The input to the program is a triangular mesh describing the 3D surface, and a user defined backdrop and ground. In step 1 we build a model that approximates the 3D input model by voxelizing it's surface, I do this by constructing an N by N by N cartesian mesh grid and removing the cubes that are not intersected by the triangular mesh, and then defining the cube faces that have normals in the Z or Y directions as model faces.
To accomplish this, I have used a voxelization software , which was very easy to use, but also had many drawbacks, since the voxelization was incosistent. To fulfill the requirements of theorem 1.131, we need only check that the PLS created by these model faces is indeed a parallel PLS. The paper's approach to this is taking all the model faces that are visible when looking from the outside, meaning the model faces that first intersect a ray in the direction of . Those faces are called the visible faces.

Obviously, the visible faces grid fulfills the requirements theorem 1.131

My approach to this was so:

I have defined a 3 dimensional mesh grid, and indeed used a voxelization tool to find all the cubes that intersect the triangular mesh.

Next, I have defined a structure of model faces each containing a simplex of the size ns*4 which defines the connections of each model face, as an array with the center of each model face.

Finally, i went through all the model faces and traced a ray through each of their corners, if that model face was the first to be traced for all 4 corners, it remaind as visible face. Obviously, the visible faces grid fulfills the requirements theorem 1.131 My approach to this was so:
I have defined a 3 dimensional mesh grid, and indeed used a voxelization tool to find all the cubes that intersect the triangular mesh. Next, I have defined a structure of model faces each containing a simplex of the size ns * 4 which defines the connections of each model face, as an array with the center of each model face.
Finally, i went through all the model faces and traced a ray through each of their corners, if that model face was the First to be traced for all 4 corners, it remaind as visible face.

Step 2 - Finding the Closest Pop-up Realizable Surface

Now we move on to ensure realizability.

Definition 2.2.2 Candidate face, is the grid face the projects onto b along

An Error measure between such candidate face and the visible PLS alone the view direction is defined as



Where B is the set of all base faces, S is the realizable PLS face and is a parallel PLS face, and the error metric is the Eucleadean distnace between the centers of the faces.

In order to get to minimize this error while still maintain the realizability condition, the following algorithm is suggeseted: Call our Realizable approximation S and the original visible PLS
1. First include in our S the visible base faces that are connected to the outermost ring, like so

2. We then work on each slice of the PLS for different values of x , for each strip we either add patches that exist in the original visible PLS, or we add new patches that are connected to existing patches in one of the ways allowed in theorem 1.132

Definition 2.2.3 A base face is Visited if b has a candidate face in S and unvisited otherwise

A candidate face can be added to S in the following ways:

2.1 will be added to to S if it is adjacent to a Visited face (it shares an edge with it), is Parallel to it and is a grid face of the original Visiblw PPLS

2.2A patch will be added to S if it is a part of a path of base face a along a strip of base faces for which x is a constant, where the beggining and the end faces are visited faces. That path is either

Between two non parallel faces

Between two parallel faces

And the path cannot be between end faces whose angle between their centers is between 180 to 270 degrees

and for which is minimal.

Results

I have written a program in Matlab that implemenets the suggested algorithm, and had the following results:
All of the following 3D models are realizable surfaces, meaning: they can be folded from a 2D sheet of paper by following the Planar Layout cutting and folding instructions.

The Lincoln memorial



The result of their algorithm was similar, but a little different



The main difference can be seen in the planar layout of my result:



The most prominent flaw in this layout is the lack of symmetry. This lack of symmetry stems from the uneven voxelization from before.

Here is a cool result of my impelementation: The Cerrito Church, notice how the algorithm deals well with curved surfaces:



This last result is not even of a building plan, the original model was a bunny


And the realizable PLS result from the algorithm was

Downloads and Resources

Book Poster Code

References

The Theory and the algorithm was based on the following papers In my implementation I have used the following toolboxes