Home/Magazine Archive/September 2009 (Vol. 52, No. 9)/Constructive Function-Based Modeling in Multilevel.../Full Text

Virtual extension
# Constructive Function-Based Modeling in Multilevel Education

It is a digital age, especially for children and students who can be called the world's first truly digital generation. Accordingly a new generation education technology with a particular emphasis on visual thinking and specific computer-based notions and means is emerging. This is a new challenge for computer graphics which is a wide discipline dealing with creating visual images and devising their underlying models.

There have been two major paradigms in computer graphics, and shape modeling as its part, for a certain period of time: namely, approximation and discretization. Their purpose is to simplify ideal complex shapes to make it possible to deal with them using limited capabilities of hardware and software. The approximation paradigm includes 2D vector graphics, 3D polygonal meshes, and later approximations by free-form curves and surfaces. The discretization paradigm originated raster graphics, then volume graphics based on 3D grid samples, and recently point-based graphics employing clouds of scanned or otherwise generated surface points. The problems of the both paradigms are obvious: loss of precise shape and visual property definitions, growing memory consumption, limited complexity, and others. Surface and volumetric meshes, lying in the foundation of modern industrial computer graphics systems, are so cumbersome that it is difficult to create, handle, and even understand them.

The need in compact precise models with unlimited complexity has lead to the newly emerging paradigm of procedural modeling and rendering. One of the possibilities to represent an object procedurally is to evaluate a real function representing the shape and other real functions representing object properties at the given point. Our research group proposed in a constructive approach^{9} to creation of such function evaluation procedures for geometric shapes and in^{10} extended the approach to the case of point attribute functions representing object properties. The main idea of this approach is the creation of complex models from simple ones using operations similar to a model assembly from elementary pieces in LEGO.

In terms of educational technology, such an approach is very much in the spirit of a constructionism theory by Seimur Papert.^{8} The main principle of this theory is active learning when learners gain knowledge actively constructing artifacts external to themselves. Applications of this theory coupled with modern computer technologies are emerging although a relationship with educational practice is not always easy.^{3} It is known that constructive thinking lying in the heart of LEGO games enable children to learn notions that were previously considered as too complex for them. There was research at the MIT Media Laboratory that led to the LEGO MindStorms robotics kits allowing children build their own robots using "programmable bricks" with electronics embedded inside. We have been developing not physical but virtual modeling and graphics tools that make it possible to use an extensible suite of "bricks" (see illustration in Figure 1) with a possibility to deform and modify them on the fly.

Such an approach assumes mastering the basic mathematical concepts, initial programming in a simple language with subsequent creating an underlying model, generating its images and finally fabricating a real object of that model. We believe it is of interest as an educational technology for not only children and students but also for researchers, artists, and designers. It is important that learners interacting with a created virtual world acquire knowledge not just about mathematics and programming but also about structures and processes of the real world.

We found soon after the introduction of our approach to modeling in the mid-90s that none of existing modeling systems or languages support this paradigm. Another necessity was to start preparation of qualified students to be involved in the R&D process. This was the initial motivation for the project and its applications in education that we would like to present in this paper.

One of the most rapidly developing types of shape models in computer graphics are probably implicit surfaces^{4} and the more general *function representation* (FRep).^{9} One of the advantages of these models is their procedural nature and possibility to introduce a new primitive or operation via a concise analytical expression or a short function evaluation procedure. In FRep, a 3D object is represented by a continuous function of point coordinates as F(x,y,z)0. Time-dependent and other multidimensional objects are defined by a similar inequality. In an FRep modeling system, an object is represented by a tree data structure reflecting the logic of the object construction, where leaves are primitives and nodes are operations (Figure 1 left). The function F is evaluated at a given point by a FRep tree traversal procedure. A more general constructive hypervolume model^{10} allows for modeling multidimensional point sets with attributes, where an attribute is a mathematical model of an object property of an arbitrary nature (material, photometric, physical, and so on). Publications on various FRep related research subjects are presented at the FRep Web page.^{11}

There are several projects adopting the FRep modeling paradigm: general procedural modeling system HyperFun,^{6} skeleton-based implicit surface modeling system BlobTree,^{12} and FVRML/FX3D,^{7} which is a function-based extension of VRML and X3D formats. HyperFun is an international free and open source software project on FRep modeling, visualization and animation. The authors of this article are members of the HyperFun team, which is a freely associated group of researchers and students from different countries. The educational applications presented in this paper have been developed within the HyperFun project.

HyperFun^{1, 6} is in fact a name of a minimalist programming language supporting all the notions of FRep. This language was designed to be simple enough in order to allow nonspecialist users to create models of complex geometric shapes. A model in HyperFun (see an example in Figure 2) is constructed using assignment statements, conditional selection statements and iterative statements. Functional expressions are composed using arithmetic and relational operators. It is possible to use standard mathematical functions, special built-in operators for set-theoretic operations, and special library functions.

The "FRep library" contains the most common primitives and transformations of quite a broad spectrum and is easily extensible. There are functions implementing conventional modeling primitives (such as, block, sphere, cylinder, cone, and torus) and popular implicits (blobby objects, soft objects, metaballs). More advanced primitives include convolution objects with skeletons of different types, pseudorandom solid noise primitives, and objects defined by parametric functions (cubic spline and Bézier objects). The typical transformations are available, such as rotation, scaling, translation, twisting, stretching, tapering, blending as well as some more general operations such as non-linear deformations driven by arbitrary control points.

In principle, the language is selfcontained and allows users to build objects from scratch using only mathematical expressions, without the use of any predefined primitives, transformations, and control structures. This is the way users define object geometry in the mentioned above FVRML/FX3D extension, however it results in increasing code size and eventually diminishes the language expressive power. In addition, some objects (such as the fractal shape in Figure 3) can only be described by procedural definitions using structural programming statements.

Let us briefly describe the following software tools that are freely available and can be downloaded from the HyperFun Project Web site.^{6}

- The
*HyperFun Polygonizer*. This program imports an object from a HyperFun file, approximates it with a polygonal mesh, and displays the mesh using OpenGL. The program also makes it possible to output the results in VRML and STL formats. - The
*HyperFun for POVRay*is a plugin to a well-known ray-tracer POVRay (www.povray.org) which makes it possible to generate high quality photorealistic images and animations. - The
*HyperFun for Windows*is an interactive system allowing the user to easily master the FRep modeling concepts using the HyperFun language while working in a conventional MS Windows environment. This program allows the user to specify an FRep model in HyperFun, to compose complex scenes with multiple objects, and to specify visual parameters for subsequent rendering (from simple 2D plots to animated 3D isosurfaces). Figure 2 shows a system screenshot with a sample HyperFun model, which is usually used for tools testing.

Special attention is paid to the development of Web-based modeling tools such as the HyperFun Java applet and the interactive system EmpiricalHyperFun based on the empirical modeling principles.^{5} Such tools are available on-line through a Web browser on any platform supporting Java and Java 3D.

Function-based modeling, HyperFun language and software tools have been taught on several levels of education starting from elementary schools to doctoral thesis research. The primary target is mathematical education at schools and universities combined with practical experience in modeling, computer graphics, animation, and visualization. As HyperFun is quite a simple language it can also be used in teaching the basics of computer programming. At the introductory level, all the mathematical and geometrical concepts can be hidden. At a higher level, the underlying mathematical and geometric concepts can be introduced in the courses of linear algebra, analytical geometry, computer graphics, and other specialist disciplines. Finally, at the highest level, the HyperFun language can be used for modeling shapes with complex mathematical definitions by graduate and post-graduate students in different research areas.

Let us briefly present some educational experience in the context of the HyperFun project and then provide more specific details of teaching methods and practices.

Summer Camps for both junior high school and high school students are organized at the University of Aizu (Japan). Starting from year 2000, the camp program includes three days of HyperFun exercises and a small free-form modeling project by each participant. In average, 70 schoolchildren from all over Japan attend this event. The first day of the camp is devoted to teaching the modeling language; original models are designed by pupils during the second day, and scene composing and rendering constitutes the last day. Another example is a weekend school organized by Linux Café at Chiyoda district of Tokyo. Children looked happy to play with their virtual toys because in contrast to common computer games they could create and modify their models themselves. Examples of models by school pupils are shown in Figure 3 (top row).

Modeling in HyperFun along with models fabrication is among the topics of the workshop series held at the MITFabLab Norway. The Fab Lab program (http://fab.cba.mit.edu) aims at providing possibilities for ordinary people to master design and desktop fabrication of usable tangible objects. The participants of the workshops are instructors and researchers of Fab Labs around the world and they learned the basics of HyperFun in just one day.

More than a thousand university students in Japan, Russia, United Kingdom, France, Slovakia, Czech Republic, Austria, Sweden, Singapore, Albania, and United Arab Emirates, from the first year to the PhD level, studied FRep modeling using The HyperFun language in the following courses and exercises: computer graphics, shape modeling, visualization, computer animation, and compiler design. Examples of shape models created by users of different ages and qualifications are shown in Figure 3. More examples can be found in the gallery at the HyperFun Web site.

The resources used in the education process include Web sites presenting FRep research^{11} and HyperFun software development,^{6} special compact disks (for example, HyperFun CD distributed at the educational exhibition ACM: Beyond Cyberspace held in 2001, in San Jose, California), printed and electronic tutorials, on-line lecture notes, and repositories of student works.

There are several types of on-line tutorials for HyperFun. One is a traditional set of HTML pages available (currently in English and Japanese) at the project Web site. This tutorial provides information for relatively passive learning the basics with some included exercises. Another type of tutorial for more active learning is a Web-based multimedia tutorial for mastering the HyperFun applet (available at http://www.cgpl.org/HF/). It is a sequence of nine Macromedia Flash animations showing various aspects of practical work with the applet accompanied by an audio explanation.

Teaching at the university level can be organized in a number of ways. Let us consider, for example, the curriculum for computer graphics and animation oriented students at the Hosei University (Tokyo) in years 20062007. At the undergraduate school, the following elective courses based on FRep and HyperFun were given:

- First year project course includes introductory lectures, a set of exercises with modeling tools, and a free-form modeling project on creation and rendering of static 3D objects using the basic algebraic primitives and set-the-oretic operations;
- Second year project course includes a set of exercises on time-dependent modeling and production of a short animation exploiting more complex primitives and transformations such as convolution surfaces and metamorphosis;
- Third year: the Visualization course with interactive exercises using HyperFun for Windows for scientific visualization of analytically defined multidimensional objects, and the Computer Animation course including material on time-dependent FRep shape modeling;
- Fourth year: graduation research projects include development of mathematical models of new types of primitives and operations, processing algorithms, and implementation of software tools for HyperFun.

At the graduate school, two related lecture courses were given on "Function-based shape modeling" and "Volumetric and multidimensional modeling and visualization". Both courses include modeling projects by students. Topics of master theses include FRep related research and software development. Some of the projects of year 2006 resulted in academic conference and journal publications.

Augmented Sculpture project^{2} can serve as an example of a more complex and creative multilevel activity within our framework. In this project, we investigate an original approach to computer-based sculpting which can be exploited not only by computer graphics professionals but also by art student and artists. An interactive computer-based means for representing sculptures can lead to the production of artifacts with a new aesthetics. Consequently, viewers experiencing interaction with these shapes within a virtual space can also benefit from this technology. Starting with a physical sculpture, one can create its computer model and then manipulate this model to generate new shapes that can eventually be manufactured to produce a new physical sculpture. We call this approach "augmented sculpting" as it extends the existence of physical artifacts to a virtual computer world and then closes the loop bringing newly created computer models into physical existence. There is an Augmented Sculpture Web Page: http://www.hyperfun.org/AppASP/FASP.html which contains all the information about the project.

The creation of the geometric models of the preexisting sculptures by Russian artist Igor Seleznev was undertaken as an exercise by students of the Moscow Engineering Physics Institute attending the computer graphics course, which included nine hours of lectures and 20 hours of practicals on FRep shape modeling. Initially, photographs of the sculptures were made available to the students via the Web. The students were encouraged to write collaboratively and share the HyperFun code to create rough prototype geometric models. They then formed groups of two or three students to combine their efforts in building more accurate models. The physical sculptures were made available to them at this stage, and the artist himself took part in assessing and discussing the intermediate results with the students. Finally, the students constructed geometric models of the sculptures in the form of HyperFun programs. Note that the sculptures have quite complex shapes with subtle non-regular features, and students could see benefits from using such advanced primitives as convolution surfaces.

Model building and editing was carried out using the HyperFun for Windows toolkit, and the students generated the final ray-traced renderings using the HyperFun for POVRay. For example, students P. Yablochkin and N. Varivoda, starting from a real bronze statuette "Gymnast" (Figure 4 top left), created its model in The HyperFun language (its ray-traced image is shown in Figure 4 top right). Then, another student A. Ogarko has modified that model to make it time-dependent that allowed him to generate an animation (frames shown in Figure 4 middle row).

Having created models of a few sculptures one can implement a metamorphosis between them thus generating quite interesting sculpting artifacts. Traditionally, metamorphosis is a complex problem that requires the animator to establish a correspondence between the initial and final key shapes. In the FRep framework, metamorphosis is performed almost trivially by a non-specialist user and can generate intermediate shapes by interpolating between more than two key ones. Having created such artifacts one can then produce their physical incarnations using rapid prototyping machinery and the process called '3D printing'. Figure 4 (bottom left) shows three original sculpture models ("Gymnast", "Naked" and "Walking Androgynous") produced by students of the Hosei University in Tokyo using a SLA3500 rapid prototyping (RP) machine. The fabricated result of the metamorphosis is shown in Figure 4 (bottom right). Note that the students in Tokyo used so-called "triangle metamorphosis" between the models of three sculptures created by Moscow students!

The next stage is using an interactive modeling system where the artist can navigate interactively through a so-called 'FRep Sculpture Garden', which is a time-dependent scene composed of multiple objects. So, the artist experiences an immersion into a virtual space where he or she can generate new shapes using metamorphosis between the modeled sculptures. Editing the shapes on the fly by adding or removal material is also possible. This is a base for an interactive art installation in which physical and virtual artifacts are combined and overlaid.^{2} Such a project allows professionals, artists and students to mix and work together thus encouraging them for exchange ideas and skills.

At the first glance, function-based geometric modeling is a highly mathematical specialist subject interesting only for professionals. Our experience shows that it can be mastered and appreciated by people of different ages, qualifications and occupations as a useful and engaging activity. It is worth to mention in the conclusion some technical, methodological and social aspects of our long-term project.

In technical terms, existing interactive shape modeling systems in CAD and animation typically provide sophisticated multilevel graphical user interfaces (GUI). The ease of using menus and buttons creates the illusion of the easiness of modeling itself. However, the use of GUI leads to alienation of the user from the model being constructed. As the result, the learners concentrate on the details and specifics of GUI instead of the specific characteristics of the model.

Another level of creating shape models is the development of application programs based on so-called application program interfaces (API) such as ACIS (Spatial Technology), Parasolid (UGS), or SvLis (Bath University). APIs provide complete access to all components of the shape model, but require extensive knowledge in the underlying mathematical models and data structures.

What we actually advocate is the educational applications of a general approach to modeling geometric shapes, whose complexity is concealed by its constructive nature and rather elementary mathematics of primitive bricks (at least at the introductory steps). It has appeared to be simple enough to be mastered by a non-qualified user with minimal preparation time. In contrast to the existing interactive modeling systems, the HyperFun model is the text of the script the student is directly editing and redefining. This approach would only benefit from adding some GUIs while keeping the script generated automatically or edited by the user. Note also that directly using mathematical expressions for constructing shapes encourages students to deeper understanding of the underlying theory. At the same time, the mathematical theory, when hidden in the library primitives and operations, does not prevent non-specialist users, including school-children and artists, from exploiting benefits of modern and sophisticated computer graphics methods.

In a more social context of educational technology, we emphasize an active, creative and collaborative character of the learning process described here. Indeed, the building of object models starts from rather abstract mathematical expressions, utilizes ready made bricks in the form of library functions, goes all the way through modeling in the virtual world, and results in the fabrication of the created virtual objects. In the end, the learner gets tangible instances of those initial objects that might have had real prototypes. This is in the wake of the modern constructionism idea that learning is most effective when the learner creates a meaningful product actively using visual thinking and an advanced computer technology.

1. Adzhiev, V., Cartwright, R., Fausett, E., Ossipov, A., Pasko, A., Savchenko, V. HyperFun project: A framework for collaborative multidimensional FRep modeling, In *Proceedings of Implicit Surfaces '99, Eurographics/ACM SIGGRAPH Workshop* (June 1999), 5969.

2. Adzhiev, V., Comninos, P. and Pasko, A. Augmented sculpture: Computer ghosts of physical artifacts, *Leonardo 36*, 3 (May 2003), 211219.

3. Beynon, M., Roe, C. Computer support for constructionism in context. In *Proceedings of IEEE International Conference on Advanced Learning Technologies 2004* (Aug. 2004), 216220.

4. Bloomenthal, J., et al., Eds. *Introduction to Implicit Surfaces*, Morgan-Kaufman, 1997.

5. Cartwright, R., Adzhiev, V., Pasko, A., Goto, Y. and Kunii, T. Web-based shape modeling with HyperFun, *IEEE Computer Graphics and Applications 25*, 2 (March 2005), 6069.

6. HyperFun Project. Language and Software Tools for F-rep Geometric Modeling; www.hyperfun.org

7. Liu, Q. and Sourin, A. Function-defined shape metamorphoses in visual cyberworlds. *The Visual Computer 22*, 12 (Dec. 2006), 977990.

8. Papert, S. and Harel, I. Situating constructionism. In *Constructionism: Research Reports and Essays*, Ablex Publishing 1991, 111.

9. Pasko, A., Adzhiev, V. Sourin, A. and Savchenko V. Function representation in geometric modeling: concepts, implementation and applications. *The Visual Computer 11*, 8, (Aug. 1995), 429446.

10. Pasko, A., Adzhiev, V., Schmitt, B. and Schlick, C. Constructive hypervolume modeling. *Graphical Models 63*, 6 (Dec. 2001), 413442.

11. Shape Modeling and Computer Graphics with Real Functions; www.hyperfun.org/F-rep.html

12. Wyvill, B., Galin, E. and Guy, A. Extending the CSG Tree. Warping, blending and Boolean operations in an implicit surface modeling system, *Computer Graphics Forum 18*, 2, (Mar. 1999), 149158.

Figure 1. A constructive tree reflecting the logic of a function-based object assembly (left), simple building blocks-primitives (top right), and a LEGO model assembled from primitives (bottom right).

Figure 2. A sample HyperFun program and a corresponding image of the model in the HyperFun for Windows modeling environment.

Figure 3. HyperFun models by a junior-high school pupil (top left), by a group of four highschool pupils (top right), by undergraduate university students (middle row), by a graduate student (low left), and by an experienced mathematician (low right).

Figure 4. The Augmented Sculpture Project: real sculpture (top left); its HyperFun model (top right); frames of the gymnast animation (middle row); models of three sculptures produced by a RP machine(bottom left); RP model of the "triangle metamorphosis" (bottom right).

**©2009 ACM 0001-0782/09/0900 $10.00**

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.

No entries found