A Procedural 3D Modelling and Animation System Based on Lua

Formation Lua, tutoriel & guide de travaux pratiques en pdf.

Fugu

The basis of modelling in Fugu is a Lua script that generates and manipu-lates 3D triangular meshes via discrete simulation. Lua is a powerful, e cient, lightweight scripting language, frequently used in computationally demanding real-time applications such as games and multimedia environments [11]. We chose Lua because of its simple syntax, extensible semantics and the ease with which it can be embedded in other software.
Lua scripts interface to a dynamic 3D runtime engine, written in C++, which handles the generation and display of geometry, along with the Fugu user interface (Section 2.1). Fugu scripts are single le Lua modules contain-ing module-scoped variables and two special callback functions, setup() and update() (Section 2.2). An array of functions and libraries (Section 2.3) are exposed to the scripting system to manipulate and control this runtime engine.

Interface

Fugu’s interactive, code-oriented interface consists primarily of a code pane (Figure 2, left) and a 3D view (Figure 2, right). The design will be familiar to anyone who has used other popular creative-coding systems such as Processing (see Sidebar: Script-based Modelling an Animation). Users can edit a script, press PLAY and see its e ect immediately. They can also interact with the generated model while the simulation is running.
The code pane supports standard code editing functionality including syntax highlighting, line numbering, and multi- le editing with tabs. The 3D view uses a trackball-style manipulation of the scene viewport, and viewing modes range from wireframe to ambient occlusion shaded and textured modes. Additionally the user can select smoothly subdivided versions of the geometry (using But-ter y subdivision [3]). A console window at the bottom of the screen presents script syntax and run-time errors.
Figure 2: A screenshot of Fugu showing the code pane with syntax colouring (left), 3D interactive view of the model the script generates (right) and the console window for syntax and runtime error reporting (bottom).

Script Format

A Fugu script is a single le of Lua code written in the form of a Lua module. When a script is loaded, Fugu looks for two special functions in the module: setup() and update().
The setup function is run once at the start of a simulation to specify initial conditions and create any initial meshes. For example, the setup function of Listing 1 creates a new spherical mesh, stores it in a module-scoped variable m, then adds the mesh to the Fugu universe (see Section 2.3).
The update function is called repeatedly and at regular intervals from the time the user presses the PLAY button. Updating continues until the PAUSE button is pressed. The update function receives a parameter specifying the time elapsed since the last update, dt. In Listing 1, the update function iterates over all the vertices in the mesh m and modi es their positions every time step.
Listing 1: An example Fugu script. The setup function creates a spherical mesh. During each update, all the vertices of this mesh are perturbed by a sine function that varies over time and local vertex position.
module (… , package . seeall )
local m
function setup ()
m = sphere ()
fgu : add ( meshnode ( m ))
end
function update ( dt )
for _ , v in ipairs ( v e r t e x l i s t ( m )) do
v . p = v . p + vec3 (0 ,0.01* sin ( v . p . x + fgu . t ) ,0)
end
end

Geometric Modelling Functionality

In addition to the standard Lua library, Fugu provides access to a range of func-tions and datatypes that support 3D mesh modelling. Fugu’s primary object is the 3D triangular mesh, composed of vertices, edges, and triangles. Fugu simpli es working with mesh geometry by facilitating mesh creation and ma-nipulation through an extensive set of functions and datatypes. A summary, classi ed according to type, is given below.
The universe is a simple scene graph for organising multiple mesh ob-jects and their display. The userdata universe object fgu, contains all the objects of the scene and provides two member functions add(n:node) and make child of(parent:node, child:node) which allow a script to add a node to the universe and to anchor a node’s position to another node respectively. There are two types of nodes: abstract nodes which can be used as invisible an-chors (e.g., as a pivot for an object), and mesh nodes, which transform meshes in the scene. Mesh objects must be wrapped in a meshnode datatype before they are added to the universe (Listing 1).
A ne transformations (stored as homogeneous matrices) transform nodes in the scene graph, or can be applied directly to a mesh to permanently trans-form its geometry. Fugu provides a shorthand for the standard geometric transformation matrices: T(t:vec3) translates a point by the given vector; S(s:vec3) scales by the vector s; R(rad:double, axis:vec3) rotates a point a number of radians around the speci ed axis; and, Rv(a:vec3,b:vec3) rotates vector a to align with vector b.
A number of mesh creation functions are provided. Standard primitives are created using cube(), sphere(), icosahedron(), etc. The iso(r:int, f:function) function generates an isosurface mesh by sampling the function f using the marching cubes algorithm within a 2x2x2 cube with resolution r. For instance, a sphere could be generated with the following statement:
iso (16 , function (x ,y , z )
return distance ( vec3 (x ,y , z ) , vec3 (0 ,0 ,0)) – 1 end )
This example also illustrates the use of Lua’s anonymous functions. Meshes can be loaded from les (in the popular .obj format), useful for applying functions to pre-built geometry (such as the Stanford Bunny in Figure 1 (b)).
The creation of generalised cylinders|geometric surfaces de ned by con-necting a series of cross-section curves distributed along a carrier curve [1]|is also supported. A triangular mesh approximating the surface is constructed from the generalised cylinder, using a novel curve-morphing technique [12].
Cylinders are de ned using a Logo-inspired turtle interface, in which a co-ordinate reference frame, the turtle, is created and transformed through space, tracing out cross-sections and carrier curves [8]. The turtle’s member functions change its position and orientation, these include move(d:double), roll(a:double), pitch(a:double) and yaw(a:double). Cross-section and carrier curves are modelled as piecewise cubic Bezier curves, the control points of which are added by the turtle as it moves through space, using add point(). After de ning the cylinder, the member function mesh() creates and returns a triangular mesh version of the cylinder, on which additional mesh-based oper-ations can then be performed. The example in Figure 7 illustrates a complex organic form created in Fugu with generalised cylinders.
(Sidebar) Mesh Implementation: Rather than design yet another mesh representation and manipulation library of our own, we used VCGLib to provide the mesh functionality required in Fugu. VCGLib is a comprehen-sive C++ template library that provides a exible framework for creat-ing and manipulating triangular meshes (http://vcg.sourceforge.net). Using VCGLib permitted rapid development, allowing us to focus on de-signing new geometric operators and manipulators, leaving VCGLib to take care of mesh representation and geometric integrity. Additionally, VCGLib provides many useful operations, such as Loop subdivision, and has been extensively used and tested in the popular program MeshLab (http: //meshlab.sourceforge.net/). Two alternative libraries, CGAL (http: //www.cgal.org) and OpenMesh (http://www.openmesh.org), provide similar functionality and were considered for our application. CGAL is oriented towards meshes with a xed topology and is more focused on guar-anteeing correctness of algorithms with its precise kernels, rather than being an e cient real-time format. OpenMesh is a polygonal mesh library based around a half-edge data structure and associated operations. In retrospect OpenMesh may have been a better choice due to its simpler API and more liberal license than VCGLib (LGPL vs GPL).
The lowest-level of mesh manipulation occurs on vertices and faces. Fol-lowing the design inherited from our mesh representation library, VCGLib (see sidebar Mesh Implementation), edges are manipulated implicitly by modi-fying vertices and faces. The vertexlist(m:mesh) function provides access to a mesh’s vertices as a Lua array. A vertex is a user-data object, and has a number of attributes including a position, p, colour, c, and normal, n. List-ing 1 illustrates one way a vertex position can be modi ed in a script. Should a script retain a reference to a vertex for some time, there is the possibility the reference may become invalid if the vertex is deleted by another part of the script. To protect against such issues, vertices (and faces) are modelled as proxies (see sidebar Proxies). Faces have a similar set of functions, for example facelist(m:mesh) returns a list of faces in the mesh, face.n returns the normal of a face, and face:v(i) returns the i’th vertex of the face.
Figure 3: Using a pos to navigate a mesh. This gure shows two faces of a mesh and four pos’es, drawn as triangles connecting the vertex, edge and face referenced by each pos. From the pos <v,0,f> (indicated in the gure), we can move to the vertex above it with flip v, the opposing edge within the face with flip e, or to the adjacent face with flip f. If the mesh is fully connected we can reach any position on the mesh using a sequence of these operations.
When modifying mesh geometry or vertex positions, normals may need to be recalculated to ensure correct shading and display. This is performed auto-matically between update calls or by calling mesh:sync() explicitly.
Fugu provides a simple mechanism for navigating around a mesh: the pos object, which models a cell-tuple [2]. A pos is a <vertex,edge,face> tuple, where vertex and face are the data structures introduced above, and edge is either 0 or 1 (referencing one of two possible edges). A pos uniquely identi es a position on a mesh and provides a set of member functions (flip v(), flip e(), and flip f()) for navigating it over the mesh (see Figure 3). Many of the functions in Fugu return a pos or a list of pos’es. Given a pos, p, the vertex or face it points to can be retrieved as p.v and p.f.
(Sidebar) Proxies: Fugu is designed to allow multiple scripts to run simul-taneously so that, for example, a physics script could simulate the e ects of soft-body dynamics on a developing ower, while a sprouting script could be sprouting orets from that ower’s surface. For simplicity we assume that scripts are not running truly concurrently, but rather that they have update() functions that are called sequentially. However, what happens when a script stores a reference to a vertex, and another script deletes that vertex? To safeguard against accessing an invalid object, vertices and faces are stored by proxy. This adds a safe layer of indirection, and o ers a valid() function to check if the element targeted for access still exists. VCGLib also shu es vertices and faces around in memory as elements are deleted, for space e ciency { another reason that necessitates this safety mechanism. The vertex and face proxies implemented in Fugu also ensure they are updated to point to valid memory locations.
A number of mesh operations for assisting with modelling are provided. Accessor functions return sets of elements: loopv(v:vertex), for example, returns an ordered list of vertices that loop around v, and nearbyv(v:vertex, n:int) returns a list of vertices that are n edges or less away from v. Other functions, such as mesh:smooth subdivide(levels:int) operate on an entire mesh. VCGLib provides a large number of these functions, several of which we expose as Lua functions.
Local operations, such as inset(v:vertex,s:double) (demonstrated in Section 3.1), insets the faces surrounding a vertex and scales them by a given amount, s. extrude(v:vertex, d:vec3, m:double) extrudes the faces sur-rounding a vertex v in direction d, by magnitude m. Given a list of vertices, vl, and a plane de ned with position p and normal n, flattenvl(m:mesh, vl:list, p:vec3, n:vec3) attens all the vertices in the list to lie on that plane.
Mathematics functions include trigonometric functions, linear algebra, Per-lin noise and a variety of interpolative functions. Datatypes for 3D vectors, ho-mogeneous matrices, and quaternions are available as the userdata types vec3, mat4, and quat respectively. Lua’s operator overloading features allow standard mathematical operators (addition, multiplication, etc.) to work on these new types (see Listing 1).
A set of geometric functions are available to assist with performing ge-ometric queries, collision tests, etc. For example, the function distribute points sphere(n:int) returns n equally distributed points on a sphere and perp(v:vec3) returns a normalised vector perpendicular to v.
A number of utility functions for manipulating Lua structures are provided, most of which are adopted from the Underscore.lua library (http://mirven. github.com/underscore.lua/). These functions provide a simpli ed syntax for iterating over Lua tables and performing functional programming. For exam-ple, the each(t:table, f:function) utility function applies f to each member of t.
Higher-level functions are implemented directly in Lua, while lower-level, CPU intensive functions are implemented in C++. The support library, Lu-abind, was invaluable in allowing easy binding between C++ datatypes and variables and Lua. Our goal is to eventually provide enough functionality so that most mesh operations can be coded purely on the Lua-side, allowing user-created libraries to be easily shared amongst the user community.
Having now described the basics of Fugu operation, along with its principal functions and datatypes, we will illustrate how these features can be used to model 3D form using a series of examples.

Example Applications

In this section we describe two applications that highlight the di erent mod-elling features available within Fugu. The rst example demonstrates a mesh operation for creating continuous animated extrusions. This compound extru-sion operation (implemented as a Lua function that combines several lower-level operations) is used to generate a variety of tubular organic structures over ex-isting meshes. The example also illustrates the general structure of a Fugu script and key mesh-level operations. The second example describes a timed L-system simulation, based on Calcispongiae development. Unlike previous L-system modelling tools, the geometry generated by the L-system’s development can be subject to further modi cation using Fugu’s mesh operations.

Extrusion

Extrusion is a fundamental operation in 3D mesh modelling that involves the translation of a group of triangles, typically along their normal, to generate a new form over the region that is swept out. A continuous extrusion can be used to animate the outward growth of a limb, spike, or thorn. This section illustrates how continuous extrusions are modelled and applied over arbitrary meshes in our system. By changing extrusion parameters a variety of di erent e ects can be achieved.
The extrude(v:vertex,dir:vec3,m:double) function extrudes a set of faces adjacent to a speci ed vertex, along a supplied direction by amount m. To e ectively model continuous growth, discontinuities in the surface geometry must be minimised as it undergoes extrusion. One method of achieving this is to use very small extrusion steps. However, in the model described below, we use the function, inset, which performs a zero-distance extrusion, followed by scaling of the end faces.
A continuous extrusion operator can be modelled with a move phase, during which the vertices of the extrusion are translated continuously in a speci ed direction; and an inset phase, where the faces at the end of the extrusion are inset, forming a new cap to translate. It is useful to consider growth as a single entity, so to model this in Lua we create a Lua object with an internal state and an update function that is responsible for performing the extrusion. This update function returns false when the extrusion is complete, and true otherwise. The internal logic is modelled using a state machine with three states: move, inset, and done. The script for this object is shown in Listing 2.
The inset state executes the inset function (Listing 3) and then returns the machine to the move state. This function doesn’t change self.v (the vertex currently being extruded), which always refers to the vertex at the end of the extrusion. Additionally, the inset function returns the cap: a fan of pos’es (cell-tuples) iterating over the faces located at the active end of the extrusion. This is used in the move state to access the vertices surrounding self.v.
While in the move state, the extrusion shifts self.v by a small amount in the normal direction, then moves the adjacent vertices extracted from self.cap using the function capov(cap:list), which, for a given pos-fan, returns the outer vertices as a Lua array. The vertices are rst moved in the extrusion direction, and then scaled from the center so that they shrink. The nal step calls flattenvl(m:mesh,vl:list,p:vec3,n:vec3), which attens the end cap vertices in the list vl, so they sit on the plane de ned by position p with normal n. If the vertices have been shifted more than SEG LENGTH, then the state is either changed to inset to generate a new segment, or to done if the required number of segments have been generated. Figure 4 illustrates these stages in Listing 2: This function creates a Lua object which, by repeatedly calling its update member function, will create an extrusion at the supplied vertex.
function n ew _s pi ke ( the_mesh , t h e _ v e r t e x )
— the possible states local states = {
move = 1 , inset = 2 , done = 3
}
— co ns ta nt s for the o pe ra ti on local SPEED = 4
local S E G _ L E N G T H = .1 local NUM_SEGS = 5 local SHRINK = .8
— create the object and its initial instance v ar ia bl es local obj = {
m = the_mesh ,
v = the_vertex ,
n = t h e _ v e r t e x .n ,
seg = 1 ,
distance = 0 ,
cap = nil ,
state = states . move
}
— define the actions local actions = {}
actions [ states . move ] = function ( self , dt ) … end actions [ states . inset ] = function ( self , dt ) … end
— the update function executes the action based on its state obj . update = function ( self , dt )
if self . state == states . done then return false
else
actions [ self . state ]( self , dt ) return true
end end
— return the new object
return obj
end
10
Listing 3: The two actions corresponding to the inset and move phases.
actions [ states . inset ] = function ( self , dt ) self . cap = inset ( self .m , self .v ,.99) self . state = states . move
self . distance = 0
end
actions [ states . move ] = function ( self , dt )
local dist = SPEED * dt
self . v . p = self . v . p + self . n * dist
if ( self . cap ) then
local outer = capov ( self . cap )
local center = vec3 (0 ,0 ,0)
for _ , ov in ipairs ( outer ) do
ov . p = ov . p + self . n * dist
center = center + ov . p
end
center = center /# outer
for _ , ov in ipairs ( outer ) do
ov . p = center + ( ov .p – center )* SHRINK
end
fl at te nv l ( self .m , outer , self . v .p , self . n )
end
self . distance = self . distance + dist
if ( self . distance > S E G _ L E N G T H ) then
self . seg = self . seg + 1
if ( self . seg <= NUM_SEGS ) then
self . state = states . inset
else
self . state = states . done
end
end
end
the extrusion process.
Useful modi cations to the continuous extrusion operation include rotating the end cap each segment, making the end cap more circular (to reduce the e ect of starting conditions), and creating heterogeneous forms by modifying the extrusion object parameters based on vertex height (see Figure 1 (a) and Figure 3.1 (a,b)). By extruding outwards and then inwards, we can create more interesting shapes, such as suckers (Figure 3.1 (c)). This extrusion operation is general enough to be performed on any smooth manifold mesh. Figure 1 (b) illustrates the operation on the Stanford Bunny, for example.