Thank you Professor ???.

Today, I'll talk about a virtual folding simulator.

It realizes virtual space manipulation of paper folding 
including curved surfaces.
 Recently, it has been drawing attention 
to interact with a virtual object in a computer.

Using real-time computer graphics, 
we can manipulate virtual objects on a graphic screen,
 as if they were real ones.

So, real-time interaction brings us natural user interface 
and enables direct manipulation of virtual objects.

Therefore, virtual manipulation technology has 
great potential in various application fields, 
such as design, entertainment, training and so on.
 Many studies on virtual space manipulation 
have been reported in recent years.

Some of them are shown in this table.

Since they are mainly concerned with hardware 
or systems including input devices, 
virtual objects should be limited to simple ones such as rigid body. 

However, for more actual applications, 
we must develop some software to manipulate more complex materials, 
paper or cloth, for instance.

We chose here paper folding.  

Because it is familiar as a traditional folk art in Japan, 
and includes a lot of technical problems 
to interact with paper as non-rigid objects.
 Our virtual folding simulator has the following functions.

First of all, combining 4 kinds of basic folding, you can transform a sheet of virtual paper into a 3D figure made by both flat and curved polygonal faces.

To execute these folding operations, you should only pick and move 
one of the corner vertices of the paper with a mouse.

Second, you can fold the paper from arbitrary viewing direction and distance 
manipulating eight buttons. 

Third, you can also change color and texture on the paper 
at any time with pop-up menu on the screen.

Several actual traditional textures are scanned and stored into the simulator 
as ordinal RGB format images.

And finally, you can arrange several folded paper works on a computer screen.

We believe that this simulator can be used
 for new paper folding art or as educational tools.
 Today's my presentation consists of the following three parts.

The first is the manipulation algorithm.

This algorithm should realize general operations used in actual paper folding.

The second is the data structure.

Our interactive simulator should 
permit "re-do" and "undo" operations in real-time.  

Finally, the representation of curved faces is 
an effective way for natural looking of the paper.

We must consider physical nature of real paper for this purpose.

 Since the most simple and friendly interface device is a mouse, 
we used here the 2D mouse device to manipulate the virtual paper.  

Of course, 2D mouse has restriction to specify 3D objects.  

Therefore, we developed a scheme to interact 3D objects 
by manipulating the vertices with the mouse.  

So I will show you how to realize 
our paper folding manipulations from now on.

 We prepared three kinds of folding operations 
and a curving operation as the individual operation.  

We use Folding up operation to rotate all moving faces right by 180 degrees.  

Bending operation rotates the faces by under 180 degrees, 
say 90 degrees in this case.  

Tucking in operation is shown here.  

Curving operation produces natural round shapes of paper faces.

We can make this round shapes based on a simple mechanics model 
simulating the balance of inner elastic force of the paper.

I will explain it later.

Combining these basic folding we can make more complex folding.
 These figures show two stages in folding a paper crane.  

As you see,  such complex folding processes in real paper folding 
is realized by combining tucking in and folding up.

 Now, I will show you how to make these folding operations with a mouse.  

First, move the mouse cursor to the vertex you want to pick.  

When you push the middle button of the mouse, 
the nearest vertex from the cursor is picked for the manipulation.

The vertex position and the folding line change continuously 
according to the movement of the mouse until you release the button.  

At the moment you release the button, the picked vertex is fixed 
and a folding process has finished.

 In the Bending operation, 3D pointing is indispensable.  

Since the mouse cursor defines only 2D coordinates on the screen, 

we should control the depth from the screen 
by using right and left buttons of the mouse.  

That is when the right button is being pushed, 
the picked vertex is coming closer to the viewer, 
and when the left button is pushed, it is going away.
 For real-time interaction, the state of manipulated object 
should be renewed as quickly as possible.

We will manage complex folded paper structure as three level layers.  

They are Face Layer, Edge Layer and Vertex Layer as shown here.  

Now, let's see how the face layer works in folding process.
 Here, we can see an example of a bending operation after a folding up.  

As a face is separated into two faces in a folding operation, 
face separation can be represented with a binary tree.  

These two cells F and F3 are generated from their parent cell F in this process. 

Successive bending operation generate 
two cells F1 and F2 from their parent cell F.  

All faces are classified into groups in the Facecell Lookup Table.  

In this example, faces F2 and F3 make a group 
since they are on the same plane.  

On the other hand, F1 makes another group by itself.  

We deal with edge and vertex Layers in the similar way.

I'd like to skip the explanation of these layers for time limitation.  
Please refer to the proceeding.
 When we move a face, some other faces might be moved together.

In this folding up case, the lower face is also moved with the upper face 
because these two faces are connected with this folding line.  

In the right case, since these two faces overlap in this area, 
the upper face is moved with the lower one.  

Using these connectivity or overlap relation, 
all moved faces can be searched automatically.

In these searching procedure, 
unexpected overlapping may be detected as shown here. 

 To avoid this problem, 
the located position of the picked vertex is corrected in these four cases.  

The first case is to put a vertex just onto the nearest one.  

The second case is to put an edge onto another one.  

The third case is that the folding line is just as one of diagonal lines.  

And the last one is bending with specific angle such as 90 degrees.  

We have developed an automatic correction function to cope with these cases.

This function works really usefully in interactive paper folding.
 I will explain the last part of today's talk, 
namely representation of curved face.
When we curve a sheet of paper on the floor, the paper face consists of two part, that is flat part onto the floor and round part away the floor.
In order to represent the round part of the paper, a set of ribbon-like polygons are useful.

The shape of round part  is determined by its cross sectional shape represented by a set of bend line on the 2D plane as shown here.

In the balance of inner elastic force, the bend line might have equal between vertices and equiangle at the vertex.  The energy  function has the minimum value for the most stable state.
To decrease energy, these vertices are moved to the arrow direction.


Now I will show you how our system is working on VTR.  
Would you start video tape, please.

At first, four kinds of basic folding are shown.  
We just fold up.  
You can see each of these operations twice.  
Now a bending is done after folding up.  
We can change the view point.  
Then, you can see a tucking in process, after folding up.  
Using these operations, we can make several paper folding 
such as plane, crane, cicada and so on. 
This is an example of folding plane. 
This is an example of folding crane. 
Thank you for the VTR.  
Now I will go to the conclusions.

We implemented the system
on a graphics workstation Silicon Graphics IRIS Crimson with Reality Engine as about 5000 steps of C program and used standard GL Library.

We developed a paper folding simulator in a virtual space.  
We recognize that this is an experiment of human-machine interface 
using real-time computer graphics.  
Since this is a proto-type system, we still have many future studies.  
Dynamic motion behavior should be taken into account 
for more realistic virtual paper manipulation.  
New interaciton functions such as cutting will expand the ability 
of the system to create interesting paper folding arts.  
Thank you!

Some researches/ on computer processing/ of ORIGAMI/ 
have been repo^rted/ as shown here.
This paper describes/ how to generate animation/
 of folding process/ based on/ key frame images.  
This paper shows/ how to estimate/ folding process/ 
based on/ unfolded state/ of folded paper.  
However,/ they did not deal with/ 
any interactive manipulation.  
On the other hand,/ 
this is an interactive simulation system/ 
developped by our group though,/ it does not realize/ 
real-time manipulation.  
For this purpose,/ we think that/ new type of interface/ 
and data structure/ 
different from these systems/ must be developped.

As we fold a paper,/ the folding line/ and the rotation angle/ must be decided.
As you see here,/ we can take the folding line/ 
as intersection/ of the holizontal paper plane/ and equidistantplane/ 
between pre- and post- moved positions/ of the picked vertex.  
Rotation angle is twice/ as big as the angle/ between the two planes.
Since/ new folding stage/ of the paper/ is displayed/ as soon as/ 
the mouse is moved, we can feel/ like picking up/ a real paper.

Edge separation is also/ represented with binary trees.  

However,/ since edges are/ not only separated/ but also generated/ 
by the folding line,/ the number of edgecell trees/ are increased.

This is an example of list renewal/ in separation of a triangle face.  
This facecell represents that/ face F0 is constructed by three edges,/ 
E1,E2 and E3.  
In separation of F0,/ two faces F1 and F2/ are generated/ and edges/ 
belonging to them/ are decided.  
This edgecell represents that/ edge E1 is constructed/ 
by two vertices V1 and V2,/ and belongs to face F0.  
In this example,/ only E1 is separated into two edges such as E11 and E12.  
A new vertex V4/ and a new edge E4 are generated.  
Edgecell E4/ is a root of/ new edgecell tree/ from now on.

This face is se^parated/ into two faces/ with the folding line,/ 
but this face is not separated.  
Lists are renewed/ only for/ such separated faces.

The position of a vertex changes/ following folding operations.  
History of vertex position is represented with a liner list of vertexcells.  
When a vertex moves, the corresponding list is renewed.  
Vertexcell Lookup Table picks up the newest cell 
correspond to vertex No.  quickly.