Computer Graphics & Geometry
Y. Takai
Hokkaido University Computing Center
Sapporo 060-0811, Japan
H. Arata
Fujitsu Hokkaido Communication Systems Limited
Sapporo 004-8550, Japan
N.K. Takai
Faculty of Business Administration and Information, Hokkaido Information University
Ebetsu 069-8585, Japan
T. Saito
Graduate School of Engineering, Hokkaido University
Sapporo 060-8628, Japan
Key words: free-form shape modeling; virtual clay; plastic deformation; Margolus cellular automata.
Free-form shape modeling techniques are getting more and more important in interactive 3D computer graphics. Users who have knowledge of geometry can build up a solid model using strict geometrical operations. But, in order to apply such geometrical operations to free-form objects, users must have enough mathematical knowledge and flexibility of spatial recognition.Problems on free-form shape modeling above can be solved by regarding the objects as clay which shows well-known plastic deformation. If users can deal with objects in the same way as real clay works, handling of free-form objects becomes easy and user-friendly.
So far, many researches on deformation using strict physical laws have been presented, such as a finite element method[1], a method based on elasticity theory[2], and an application of particle systems[3]. But all these methods need considerable computation time for deformation, and are not suitable for interactive applications.
Using a lot of parametric patches to represent the surface of deformable objects is one of the efficient and applicable methods[4,5,6], but novice users cannot deform objects intuitively, and get some difficulties if they can. [7] is a numerical method in which mathematical functions are embedded on the surface of the objects. This method has realized deformations regardless topology, but its interactivity is not clear.
There are some researches on volume sculpting and volume morphing in a 3D virtual space. [8] has realized virtual sculpting by updating binary voxel values, empty or full. But each voxel works as simple memory, its idea is just the same as pixmap. [9] has realized smoother and faster morphing in a 3D space. This work deals with morphing between two volume objects. The objects cannot be directly deformed by the user's operations.
In this paper we propose the virtual clay model for interactive free-form shape modeling. We make use of a 3D cellular automaton with Margolus neighborhood, and try to apply it to plastic deformation within a 3D voxel space. Each voxel is allocated a finite state automaton which is given the distribution rules of virtual clay. Each automaton repeats state transition according to the conditions of its Margolus neighbor voxels.
We have some researches which apply a cellular automaton to modeling, such as a texture generation model[10], a plant growth model[11], an application to parallel particle systems[12], and a constraint-based picture drawing model[13]. But there have been no researches try to apply a cellular automaton to 3D free-form shape modeling.
The free-form shape modeling proposed in this paper is based on simple distribution rules of virtual clay, not based on complicated physical laws. Hence the computation time for plastic deformation is much less than that of other methods based on strict physical simulation. In addition to that, deformation process looks so natural that the virtual clay reminds us the behavior of real clay. We demonstrate the effectiveness of our approach by some free-form examples of virtual clay modeling.
We consider plastic free-form deformation as a physical process of equalizing density distribution of the virtual clay in a 3D space. When the density of virtual clay is under a certain threshold everywhere, the virtual clay object keeps its own shape. Deformation of the object is caused by clay transportation from high density potion to low density portion. Of course, the total mass of virtual clay within the object must be conserved.Let us think of above approach within a 3D voxel space, where a voxel value corresponds to the mass of virtual clay included in the voxel. A threshold is defined in the voxel space, and voxel value is updated when the value becomes over the threshold. This model can be implemented by using a cellular automaton which has 3D Margolus neighborhood. From here, we refer to a voxel merely as a cell.
Fig.1. 2D Margolus neighborhood.
Fig.1 shows an example of 2D Margolus neighborhood for simplicity. In 2D Margolus neighborhood, the nearest 4 cells make one block, transitions of all cells within a block are performed in one step[14]. We can think of the neighborhood of each cell as the block including the cell itself. In addition, the boundaries of blocks are changed step by step as shown in Fig.1. Hence each cell alternates its neighborhood in every transition step.
Fig.2. 2D block patterns and state transition rules.
Fig.2 illustrates the state transition rules for 2D space. Each cell has a binary state depending on whether the mass of virtual clay is over the threshold or not. Hence, we have 4 different block patterns according to cell's state. Let m1 through m4 be the mass of virtual clay at each cell. The transition rule of the case 0 in Fig.2, for example, is as follows:dm <= m1 * alpha,
m1 <= m1 - dm,
mk <= mk + (dm / 3), for k = 2,3,4.
In this formula, alpha is a rate constant for distribution (0 < alpha < 1), and usually alpha nearly equals 0.3. The notation of <= means value assignment to the left.
In this way, the transition rule for virtual clay distribution is very simple. As a result of one transition within a block, cells provided with some virtual clay might become over the threshold in the block. This situation will cause the next state transition within the other neighborhood (block). Virtual clay in cells over the threshold is distributed around in a manner of multidimensional bucket brigade. The transportation of virtual clay will stop when all cells become under the threshold.
In 3D Margolus neighborhood, the nearest 8 cells make one block as shown in Fig.3. As the same manner as 2D neighborhood discussed above, each cell belongs to different blocks in odd and even steps. In total, we have 21 different patterns according to the cell's binary state which depends on whether a cell includes more virtual clay than the threshold. Fig.4 illustrates all the block patterns in the 3D Margolus neighborhood.
Fig.3. 3D Margolus neighborhood.
Fig.4. 3D block patterns.
The state transition rule for virtual clay distribution is very simple. Let the state of a cell be 1 if its virtual clay is over the threshold. Otherwise, let the state be 0.[Step 1] For each cell k of which state is 1,
dmk <= mk * alpha, and then mk <= mk - dmk,
where mk is the mass of virtual clay of cell k, and alpha is a rate constant for distribution (0 < alpha < 1).
[Step 2] For each cell j of which state is 0,
mj <= mj + ((dm1 + dm2 + ... + dmr) / n),
where n is the number of the cells of which state is 0, and r is the number of the cells of which state is 1.
In 3D Margolus neighborhood, at most 14 operations of floating point addition and at most 7 operations of floating point multiplication are performed in a block at each transition step. It is obvious that total mass of virtual clay within a block is conserved in course of the state transitions. For each block, no transitions happen in either (1) all cells in the block are state 1, or (2) all cells in the block are state 0.
Note that it's possible to deal with obstacles in the voxel space. The obstacles are implemented as special cells to which virtual clay cannot be distributed.
In our model, all plastic deformation of a virtual clay object is based on a simple push operation by using a moving plate. The push operation is realized by transferring all virtual clay in a cell into the adjacent cells along the direction of pushing. The surface of a virtual clay object can be pushed at most one cell in depth per step. This kind of distribution caused by quasi-force is prior to the state transition rule.
Fig.5. Push operation by a moving plate.
Fig.5 shows an example of the push operation by a moving plate. This plate is implemented in a cell space as a set of the special cells to which virtual clay cannot be distributed. When some cells become over threshold as the result of pushing, virtual clay is distributed around according to the transition rule. The state transitions are repeated until we have no cells over threshold, which results in overall plastic deformation of the virtual clay object.If all cells are under the threshold, such a situation of the cell space is referred to as a stable state. The number of steps passed until the stable state depends on total mass of virtual clay, threshold of cell, and the parameter alpha.
Virtual clay with only 1 degree of freedom is found inside a very narrow tube made of obstacles. Distribution of such virtual clay takes place just along the direction of the tube, and transportation inside the tube is not attenuated. Hence, if the both ends of the tube are closed by obstacles, we have an oscillation of traveling virtual clay inside the tube. If the degree of freedom for virtual clay distribution is more than or equal to 2, the cell space is sure to converge to a stable state.
Note that there is no upper limitation for the amount of virtual clay which each cell can contain. Hence, it's possible that we push again the virtual clay object before the object reaches a stable state. This freedom in a way of pushing does not influence the convergence property of virtual clay.
3. Experiments and Virtual Clay Works
At first we show preliminary results of virtual clay's plastic deformation. A virtual clay simulator has been implemented on SGI Indigo2 IMPACT10000. This simulator carries out the state transitions in a 3D cell space given. We use AVS for visualizing isosurfaces of the virtual clay object. The size of the voxel space is 128 * 128 * 128. The parameter alpha is 0.3, initial value of each cell which constructs an initial shape is 20.0, and threshold is 21.0.Fig.6 shows a virtual clay column (diameter 32 cells, height 64 cells) which is pressed by a large plate. Fig.7 shows a virtual clay cube (height 64 cells) partially pressed by a small plate. Fig.8 shows a virtual clay board (18 cells thick) cut by a thin plate. In all cases the moving plates are not rendered.
Fig.6. Deformation of virtual clay (1).
Fig.7. Deformation of virtual clay (2).
Fig.8. Deformation of virtual clay (3).
As shown in these results, the virtual clay well simulates the plastic deformation of real clay. Behavior of the virtual clay is very similar to our intuition in real clay works. Computation time necessary for deformation is 21.5 seconds for 1000 steps in Fig.6, and 26.4 seconds for 400 steps in Fig.7. These times do not include the processing time for isosurface rendering by AVS. Our method is much faster than conventional physically-based modeling such as particle systems.We are now constructing a prototype system for interactive virtual clay works. Fig.9 shows the system control panel. To visualize a shape-forming process in virtual clay works, we employ an isosurface rendering technique based on the marching cubes. Initial shape of a virtual clay object can be selected from predefined objects such as sphere, cube, column, etc. Plastic deformation is carryed out by the push operation with a moving plate. Pushing direction and position are arbitrary.
Fig.9. User interface for virtual clay works.
Fig.10 shows the results made by using the virtual clay work prototype system. Every initial shape of those is a simple cube. Just with pushing the surface of the virtual clay by a flat plate, we can easily obtain clay-like shape with softly curved surfaces. Fig.11 shows an example of surface decoration on a virtual clay object. A Chinese character on the cup is formed by swelling the virtual clay. Small swell on the surface is easily made by decreasing the cell's threshold locally and temporarily.
Fig.10. Examples of virtual clay works. (A chair, a cup, and an ashtray)
Fig.11. Another example of virtual clay works. (A Japanese tea cup)
In this paper we have proposed interactive free-form shape modeling by using the virtual clay. Behavior of the virtual clay in a voxel space is well simulated by a cellular automaton with 3D Margolus neighborhood. The state transition rule for deforming virtual clay is very simple, and requires a short computation time. Total mass of a virtual clay object is conserved in course of its plastic deformation. Through some experiments we demonstrated realistic and intuitive behavior of the virtual clay.An interactive deforming operation for the virtual clay is still limited. In real clay works, a stretch operation is also very common. It is our future work to enhance the virtual clay model to deal with both pushing and stretching operations.
1. A.Pentland and J.Williams, 'Good vibrations: Modal dynamics for graphics and animation', Computer Graphics, 23(3), 215-222, (1989).
2. D.Terzopoulos and K.Fleischer, 'Deformable models', The Visual Computer, 4(6), 306-331, (1988).
3. W.T.Reeves, 'Particle systems -- a technique for modeling a class of fuzzy objects', Computer Graphics, 17(3), 359-376, (1983).
4. G.Wyvill, D.McRobie, and M.Gigante, 'Modeling with features', IEEE Computer Graphics and Applications, 17(5), 40-46, (1997).
5. W.Welch and A.Witkin, 'Variational surface modeling', Computer Graphics, 26(2), 157-166, (1992).
6. W.M.Hsu, J.F.Hughes, and H.Kaufman, 'Direct manipulation of free-form deformation', Computer Graphics, 26(2), 177-184, (1992).
7. R.T.Whitaker and D.E.Breen, 'Level-set models for the deformation of solid objects', Proc. of 1998 Workshop on Implicit Surfaces, (1998).
8. T.A.Galyean and J.F.Hughes, 'Sculpting: An interactive volumetric modeling technique', Computer Graphics, 25(4), 267-274, (1991).
9. A.Lerios, C.D.Garfinkle, and M.Levoy, 'Feature based volume metamorphosis', Proc. of Computer Graphics, 449-456, (1995).
10. R.Fisch, 'Cyclic cellular automata and related process', Physica, 45D, 19-25, (1990).
11. N.Greene, 'Voxel space automata: modeling with stochastic growth processes in voxel space', Computer Graphics, 23(3), 175-184, (1989).
12. Y.Takai, K.Ecchu, and N.K.Takai, 'A cellular automaton model of particle motions and its applications', The Visual Computer, 11(5), 240-252, (1995).
13. H.Arata, Y.Takai, N.K.Takai, and T.Yamamoto, 'A declarative picture drawing model based on cellular automata', Trans. of Institute of Electronics, Information and Communication Engineers, J81-D-II(6), 1278-1284, (1998).
14. N.Margolus, 'Physics-like models of computation', Physica, 10D, 81-95, (1984).
Computer Graphics & Geometry