Cultural Heritage Preservation Using Constructive Shape Modelin

C. Vilbrandt ^(a), G. Pasko ^(b), A. Pasko ^(c,b), P.-A. Fayolle^(a), T. Vilbrandt^(f), J. R. Goodwin ^(d),

^(a) University of Aizu, Department of Computer Software., Aizu-Wakamatsu, Japan

^(e) University of California Los Angeles, Department of Computer Science, Los Angeles (CA), USA

Issues of digital preservation of shapes and internal structures of historical cultural objects are discussed. An overview of existing approaches to digital preservation related to shape modeling is presented and corresponding problems are considered. We propose a new digital preservation paradigm based on both constructive modeling reflecting the logical structure of the objects and open standards and procedures. Constructive Solid Geometry (CSG) and Function Representation (FRep) are examined and practically applied as mathematical representations producing compressed yet precise data structures, thus providing inter-operability between current and future computer platforms crucial to archiving. Examples of CSG reconstruction of historical temples and FRep modeling of traditional lacquer ware are given. We examine the application of fitting of a parameterized FRep model to a cloud of data points as a step towards automation of the modeling process. Virtual venues for public access to cultural heritage objects including real time interactive simulation of cultural heritage sites over the Web are discussed and illustrated.

Categories and Subject Descriptors (according ACM CSS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling, Boundary representations, Constructive solid geometry (CSG)**, Curve, surface, solid, and object representations, Function representation, Modeling packages; I.3.6 [Computer Graphics]: Methodology and Techniques, Graphics data structures and data types, Languages, Standards; I.3.8 [Computer Graphics]: Applications � simulation, digital preservation of cultural heritage

The preservation of cultural heritage objects through the use of computer modeling techniques has attracted considerable attention in computer graphics, geometric modeling, and virtual reality communities [Add00]. This is a particularly important issue in the realm of cultural heritage, since objects may be easily demolished, as the recent destruction of the Buddha images in Afghanistan has powerfully demonstrated. The archiving of digital data or digital models is possible, in part, because digital models can be digitally reproduced any number of times without degradation at very little cost. This allows for any number of exact digital duplicates of digitally modeled objects to be stored in various locations, thus providing both public access and security; such is not possible with physical objects. We review the application of computer technology and its advantages for cultural heritage preservation.

By digital preservation we mean not only archiving digital models of the surface shapes, internal structures (revealing the logic of construction), color, texture, and other attributes representing mixed materials, but also the process of reverse engineering or digital reconstruction of existing objects and objects that have been lost. Such digital processing allows for the physical reconstruction and conservation of objects lost due to unexpected events such as the Buddha images mentioned above. We review, discuss and compare different approaches to computer-aided preservation of cultural heritage objects.

�Rapid changes in the means of recording information, in the formats for storage, and in the technologies for use threaten to render the life of information in the digital age as, � �nasty, brutish and short� � [GW96]. Much of the current digital modeling, visualization and animation of cultural heritage objects will become unusable before the existing heritage objects themselves are destroyed or lost. Thus, we discuss the technical problems concerning digital persistence as related to the creation of system independent digital data structures. We also argue the use of open standards and procedures as critical to the archiving of data.

More than ten years ago, concerned with digital persistence, the authors used Constructive Solid Geometry (CSG), a set of commonly known and understood procedures, for modeling culturally valuable shapes. The authors, aware of the pending obsolescence of the system supporting the CSG modeling, planned for the lossless migration of the CSG cultural heritage modeling to a more abstract, robust and independent system of representation as described in this paper.

Accordingly, we discuss the development of a new paradigm for cultural heritage preservation that is aimed at avoiding the pitfalls of obsolescence and inoperability - a paradigm that includes constructive modeling and extensibility which will allow for future digital modeling of all of the measurable, physical attributes of a cultural object. In general, the central theme to the paradigm proposed is the concept of constructive modeling that reflects the logical structure of the object modeled [Ena02] [HBC*02]. We demonstrate the constructive modeling paradigm with CSG based models of ancient Japanese temples from both archaeological data and on-site measurements that reveal how the actual objects were constructed.

A major step in the development of our approach to the preservation of cultural heritage objects was the adoption of function representation (FRep) as a replacement to CSG representation and the creation of HyperFun, a special geometric modeling language supporting FRep modeling. We illustrate the use of FRep and HyperFun in modeling of traditional Japanese lacquer ware.

The constructive modeling of cultural objects takes skill and a great deal of time. Therefore, we examine the application of fitting of a parameterized FRep model to a cloud of data points as a step towards automation of the modeling process. Finally, we discuss and illustrate the next major component of our digital preservation system for cultural heritage - virtual venues for public access to cultural heritage objects including real time interactive simulation over the Web.

Digital archiving is at once alternative and supplementary to the physical archiving of cultural heritage objects, if the synthetic digital objects created from sampled analogue objects defining a culture are precisely detailed yet compressed for optimal storage. In this section, we discuss digital cultural heritage preservation advantages, applications, and approaches. We raise with diligence several significant problems and solutions critical to the implementation of digital archiving technologies and give specific implementation details.

The preservation of cultural objects of importance by means of digital processes is not only theoretically possible but highly desirable for the following reasons: since each digital reproduction copy is a perfect copy, digital reproduction has the potential to allow secure archiving of data into the distant future; in very small amounts of physical space, large amounts of data can be stored, making it feasible to have many copies in many locations, thus assuring against loss due to unforeseen events; much historical data and many cultural objects can not be accessed publicly (because of the cost and overhead of display, exotic locations, etc.), whereas digital data can be publicly accessed on demand globally; transparent learning through constant interaction with cultural objects in real time simulations, both locally and globally, is perhaps one of the most promising benefits from evolving digital modeling technologies.

Given the advantages of computer applications for digital preservation above, we list the following ways computers may be used to preserve cultural heritage:

Let us discuss and compare different approaches to computer-aided preservation of culturally valued objects. In the general case, a shape can be considered a point set in a multi-dimensional space. Thus, not only external boundaries, but also internal structures of objects as well as their time and other parametric dependencies can be subjects of digital preservation.

Measurements and drafting. Some existing objects are historically documented by measurement and 2D drafting representation. The results are paper drawings with a limited number of dimensions, not computer models of an object. Computer-aided drafting methods may be used and logically extended in the "measurements and modeling" paradigm described below.

Measurements and modeling. The goal of this approach is to use all available documents and measurements for creation of a 3D model of the object that is as complete as possible, and to represent its internal structure, design logic (showing how components are interconnected or layered), and history of the shape construction, as well as time-dependent aspects and other parametric dependencies. The modeling/design approach is especially valuable if the real object has been lost, destroyed or damaged. So, the model can be used to repair or replace the object. This approach can be based on using different shape representations discussed in later sections.

Surface scanning. There exist several well-developed technologies for automatic non-contact acquisition of 3D point coordinates on the visible surfaces of objects. These technologies are based on lasers, structured light, sound, and stereo imagery. Archiving of the raw data (the measured point locations) is preferable in any case to archiving shapes inferred from this data. Moreover, the raw data itself can be the best way of actually representing the surface, as was shown in the Digital Michelangelo project [LPC*00]. The authors� dataset of range images obtained with laser rangefinders provided 18:1 storage savings with no loss in information, if compared with the equivalent polygonal mesh. A special viewer based on range images was developed. The project authors claim, �If one only wants to view a 3D model, and not perform geometric operations on it, then it need not be represented polygonally.�

Surface scanning and meshing. Traditionally a polygonal mesh is generated on the basis of the raw data, as in the 3D Scanning of the Minerva of Arezzo [RCM*01]. This can be necessary especially if the measurement equipment does not provide point coordinates directly. For example, in the Piet� Project [Abo99], the scanner consisted of six black-and-white cameras capturing images of a striped pattern projected on the object. Accompanying software computed a triangle mesh from the captured images using principles of stereo computer vision.

Surface scanning and modeling. Scanning can provide a set of reference control points for manual modeling or the full point cloud can be used for (semi-) automatic model generation. An example of the latter case is voxel model generation from a set of range images [Neu97]. The potential of an automatic search of a simple model structure and parameters fitting of an implicit surface model on the base of range data was illustrated in the work of S. Muraki [Mur91]. In the case of unknown initial estimation of the model structure, evolution of shapes using techniques such as genetic algorithms can be applied, in the manner of the reported experiments with CSG [TL92] and analytically defined implicit surfaces [BE99]. Here, the overall distance from the shape surface to the scanned points can serve as an optimization criterion. In this work, we use measurements and constructive modeling of parameterized shapes oriented towards automatic estimation of shape parameters and further genetic evolution of shape structures.

Volumetric scanning and modeling. There exist well-developed technologies for automatic non-contact acquisition of 3D point coordinates along with physical attributes of an entire volumetric object: Magnetic Resonance Imaging (MRI), ultra sound, Computed Tomography (CT) imaging, also known as "CAT scanning" (Computed Axial Tomography). Recently, gigahertz and terahertz (THz), very short wave lengths of black body radiation, have been harnessed for very sensitive deep penetration, high resolution volumetric scanning called Tray spectroscopy [Pos03]. Currently, Trays are being used at the York Archaeological Trust to scan historical objects such as pages in books (with out turning the pages), paintings and ceramics providing volumetric molecular information on the creation of the artefact and the technologies used by its maker [Rep02]. Volumetric scanning tools could sample the physical attributes objects to be archived in compressed mathematical models. Volume modeling or heterogeneous object modeling techniques can be applied to create such models.

The exponential growth in digital technologies allows for the development of new and better applications and associated processes every year. However, such advancements also create critical hardware and software inoperability and data vitality considerations between older and newer systems. Reports by The Research Libraries Group [GW96] and more recently the National Science Foundation / Library of Congress [HBC*02] emphasize the magnitude of challenges surrounding digital persistence and preservation. Some of the problems and potential solutions are discussed below.

Obsolescence problem. The yearly advances of hardware and software render most computer systems obsolete within three to five years. Because of incompatibility issues with newer systems, older systems must be replaced. Hardware and software within seven years become so obsolete that they can no longer be purchased, supported or serviced. The incompatibility becomes so great with each passing year that eventually the data created by older systems becomes unusable because of data dependencies. �Despite awareness of the digital archiving problem, market forces alone have proven inadequate to develop and provide solutions� [HBC*02].

Dependency problem. Data migration cannot be addressed without legal access to the data file formats and the source code of the software used in the data creation; the other option is hardware and software emulation that is expensive and has been made illegal recently by the Digital Millennium Copyright Act [Sim00] [FF00]. Thus, it makes little sense to create models of cultural heritage objects in data formats and processes which are proprietary and become obsolete in a relatively short time. It should be self-evident that concealed and unverifiable procedures are unacceptable for archiving important cultural heritage data.

Solutions. The solution is the development of a preservation system using a highly abstracted form of proven mathematical representation in the form of an open standard, which is less likely to become obsolete and where the source code is open for public inspection, can be freely modified, recompiled and tested, and where all procedures are made public and transparent. The development and use of open standards and procedures is a critical element of the proposed approach to digital preservation. Open public development and inspection by many people assures the accuracy of the data and the processes, at the same time allowing for migration of the data across platforms and to advanced systems of the future.

In the following sections, we discuss three shape representations, Boundary Representation (BRep), Constructive Solid Geometry (CSG), and Function Representation (FRep). Mainly, these representations are discussed from the practical modeling point of view. Formal definitions and more details on solids and solid representations can be found elsewhere [Hof89] [Req80]. Following a brief survey, we are proposing to use a hybrid shape model for a new digital preservation paradigm based on empirical knowledge stemming from the extensive modeling experience and shape modeling research of the authors.

To represent a solid by its boundary, one needs to introduce points (vertices), curves (edges), and surface patches (faces), and stitch them together. BRep has two parts: topological information on the connectivity of vertices, edges, and faces, and geometric information embedding these boundary elements in three-dimensional space. Topological information specifies incidences and adjacencies of boundary elements. Geometric information specifies coordinates of vertices or the equations of the surfaces containing the faces. A subset of BRep, namely vertices, edges, and some additional curves constitute a so-called wire frame model, which is useful for generation of the visual shape representation while interacting with it. A polygonal mesh is a particular case of BRep with only planar faces.

Mono-directional. Currently, commercial modeling systems use BRep not only for visualization but also for mathematical definition of objects. The so called solid model cannot be directly edited, because there is no CSG type tree or any other history of operations in BRep itself. We call this mono-directional modeling in that without a history embedded in the model the user cannot move backward and inspect or change intermediate results for verification of operations.

�Mathematical cracks� The BRep based modeling systems are exceedingly complex and prone to error. Cracks (or gaps) between faces, inappropriate intersections, incorrect normals, and internal walls are typical errors in BRep models. These models lack volumetric modeling capabilities and any other way of recording the physical properties of an object that would recommend it to use for digital preservation of cultural objects. The authors' empirical knowledge gained by intensive modeling and application experience confirms the "mathematical cracks" which appear in various forms. For example, in importing BRep polygonal meshes from CAD to animation software, the "mathematical cracks" take the form of randomly reversed normals, which consume a great many hours of manual labor to correct in large models. Other more critical operations included a reversed normal of a polygon used to generate tool paths for Computer Numerical Controlled (CNC) machines causing several hundred thousand dollars worth of scrap metal and production time lost. The list of instances where the "mathematical cracks" in industrial applications have appeared is very long and beyond the scope of this paper.

A constructive modeling approach can be an alternative to modeling using polygonal meshes and other BRep models. It is based on the construction of complex objects using primitive elements and operations. With Constructive Solid Geometry or CSG representation, one can begin by selecting simple shapes (primitives), specifying their parameters and positions in space, and then using them to construct more complex objects by applying combinative and transformation operations.

Bi-directional. When a complex object is created with CSG, its constructive primitives and the order in which they were processed can be accessed; CSG modeling can be called bi-directional. Bi-directional is a critical concept for preservation modeling for several reasons. Bi-directional means that we can move up and down the CSG binary tree of primitives and operations examining intermediary results and allowing modification and thus verification. Furthermore, CSG allows for efficient surface calculations of area and mass calculations of weight, volume, and centricity.

CSG inter-operability standards. Inter-operability between current systems and future systems relies on data exchange standards. Therefore we present the standards related to CSG. IGES (Initial Graphics Exchange Standard) is the U.S. national standard for exchange of data between dissimilar CAD systems. Over the last twenty years, IGES has failed to include in its standards support for the translation and exchange of CSG data. On the other hand, STEP protocol (International Standard for the Exchange of Product Model Data, ISO 10303 standard) does support CSG, but this part of the protocol is rarely used nowadays. A suitable protocol should at least support CSG.

CSG modeling for cultural heritage preservation. More than ten years ago, the authors practically applied CSG. However, critical to the successful application of CSG in our long-term project were the �open architecture� of AutoCAD and the Advanced Modeling Extensions (AME) that allowed access and manipulation of the CSG data directly. It should be noted that open architecture is not the same as open source code. Due to the speed of the 386 and 486 computers available at that time, the authors had to develop modeling operations that used up to four computers at one time to accomplish the task of modeling ancient Japanese temples in CSG. At the time that we finished the basic CSG modeling of Enichiji and Sazaed� (see Section 4.2), interactive modeling of one entire temple model on a single computer was not possible. The authors were aware that the rapid evolution of computing technology would solve such computational problems. Entire models with real time rotation are now easily handled on current machines. The use of CSG modeling which had open architecture was arduous, but the migration to future systems was more important than the short-term convenience of BRep.

The disadvantage of CSG representation for cultural preservation is in its geometric domain; it is not suitable for producing organic shapes. Thus, although it performs well in its representation of most architectural and mechanical objects, it would not do for sculpture. We did not attempt to model any of the sculpture in the temples, until we could find or develop a representation that was inclusive of the CSG paradigm and beyond.

The basic mathematical representation in digital preservation should serve several purposes. It should reflect the logic of the object's construction, support modeling of parametric families of shapes, support specific and extensible modeling operations, generate polygonal and other surface models, as well as voxel models, for visualization, animation and virtual objects presentation on the Web, and serve for direct control of rapid prototyping machines with the precision needed to reproduce the modeled objects. We propose to use so-called function representation (FRep) as our basic mathematical model [PAS*95]. FRep is a generalization of traditional implicit surfaces [Blo*97] and CSG. It represents a 3D object by a continuous function of point coordinates as F(x,y,z)  0. A point belongs to the object if the function is positive at the point. The function is zero on the entire surface (called usually an implicit surface) of the object and is negative at any point outside the object. The function can be easily parameterized to support modeling of a parametric family.

History of operations. In FRep, an object is represented by a tree structure reflecting the logical structure of the object construction, where leaves are arbitrary "black box" primitives and nodes are arbitrary operations. Function evaluation procedures traverse the tree and evaluate the function value at any given point. Algebraic surfaces, skeleton-based implicit surfaces, convolution surfaces, procedural objects (such as solid noise), swept objects, and volumetric (voxel) objects can be used as primitives (leaves of the construction tree).

General representation. In FRep, there is no difference in processing soft objects, CSG solids, or volumetric objects. This allowed researchers to solve such long standing problems as metamorphosis between objects of different topology, sweeping by a moving solid, controlled blending for all types of set-theoretic operations, collision detection and hyper-texturing for arbitrary solids, and direct modeling of space-time and multidimensional objects.

The HyperFun language [ACF*99] [HF03] was introduced for teaching and practical use of FRep modeling. It is a minimalist programming language supporting all notions of FRep. The following tools are available for processing HyperFun models: a polygonizer that generates a polygonal mesh on the surface of the object and exports it in the VRML format; and a plug-in for the POV-Ray ray-tracer that helps to generate high-quality photorealistic images. Application software deals with HyperFun models through an interpreter, which evaluates the defining function at any given point.

Unlimited dimensional modeling. HyperFun also naturally supports 4D (space-time) and multidimensional FRep modeling using functions of several variables. Recently FRep has been applied to represent not only point set geometry, but also material distribution and other properties of arbitrary nature (optical, physical, statistical, etc.) [PAS*01]. We are investigating approaches and tools for further utilization of multidimensional models. The main idea is to provide a mapping of such objects to a multimedia space with such coordinates as 2D/3D world space coordinates, time, color, textures and other photometric coordinates, and sounds. Deeper connections between multimedia space and geometric multidimensional spaces should be investigated in the context of computer animation, computer art, and cultural heritage preservation applications.

Lightweight protocol. It should be noted that function representations of complex geometric objects offer better than two to three orders of magnitude compression in comparison to boundary representations (polygonal meshes) of the same objects. The nature of FRep in comparison to BRep is a concise primitive definition of a BRep surface yet to be unfolded. Typically, the average size of HyperFun files is 5K or less for complex geometric shapes; a sample comparison of an FRep based HF file and BRep based VRML file is shown in Fig. 1 (see more examples at http://www.hyperfun.org).

	HF file: 1.19 Kb VRML file: 1.4 Mb

Easy to learn. It is quite easy to learn and use HyperFun on the beginner's level. It does not require deep mathematical knowledge. High-school level geometry and common sense in constructing and using building blocks are enough to start modeling. The authors have had the experience of teaching HyperFun to first year university, high school and even junior high school students.

Archival quality. The open and simple textual format of HyperFun, its clearly defined mathematical basis, its support of constructive, parameterized and multidimensional models, its support by free modeling and visualization software, and its ease of use make it a good candidate as a tool for the digital preservation of cultural heritage objects.

The aim of this work is development of open data structures and procedures for a digital preservation system that not only allows for interoperability between platforms, but also solves the problem of digital persistence. The intended scope of a digital preservation system may be perceived as mathematical modeling of shape and any number of static or time-dependent physical properties of an object or site. Such a digital preservation system for cultural heritage should allow for:

Hybrid System. We propose from the practical modeling point of view that BRep, wire frame, and polygonal mesh visualizations are needed by the user for the dynamic interactive modeling of CSG or FRep defined objects. BRep operations, which are known for their speed, could be used for the relatively inaccurate local tweaking operations such as moving a vertex, edge, or face and using Euler operators, which include adding and removing vertices, edges and faces, as an intermediate stage of more precise modeling operations for CSG or FRep objects, which are known to be computationally more intense and slow. In the practice of modeling with CAD systems, wire frame is convenient for finding the center of arcs and circles and thus indispensable to the creation and editing of entities, and polygonal meshes are necessary for fast rendering the entities for verification of construction. Hybrid systems using BRep based interaction and visualization together with mathematically rigorous representations are needed for quintessential digital modeling of cultural heritage objects.

Our prototype implementation of a hybrid system includes the AutoCAD rel 12 with AME supporting CSG, a special module in AutoLisp providing export of CSG models in the HyperFun format, and a set of HyperFun modeling and rendering tools. We are currently working on a full scale modeler with an interactive and immersive real time 3D environment user interface similar in concept to our history game simulation described in Section 4.3. Gradually we will introduce semi-automatic methods based on 3D scanning of real objects with acquisition of control points and non-linear fitting of the parameters of the constructive objects as illustrated in Section 4.5.

In the following examples of Japanese temples and traditional lacquer ware, we illustrate constructive modeling with the application of CSG and FRep to practical problems of cultural heritage preservation.

Our work on two Buddhist temples in the Aizu region of Japan illustrates application of CSG based constructive modeling. All parts of the two historical buildings from the Aizu History Project [Goo*03], the Golden Hall at Enchiji and Sazaed�, were created whenever possible with only CSG based entities. However, because CSG is limited in its range of shape representation, the thatch roof of the Golden Hall and the double helix ramp inside Sazaed� is represented by a polygonal mesh.

Golden Hall at Enichiji. The first structure that we modeled using CSG was the Golden Hall at Enichiji, a temple located at the foot of Mt. Bandai. Although Enichiji was the religious center of the region throughout much of the Heian period (794-1185), no buildings or images from that period are extant today. In order to produce a model of the Heian Golden Hall, the structure that housed the temple's most important Buddha-images, the authors relied on data introduced in archaeological site reports [BMK*94].

Figure 3: Interior tower: (L) colorized; (M) diagram of the interior tower�s location; (R) wood texture.

The 3D CAD model can be used to display components separately, so that the construction may be seen and understood. Even an actual visit to the site does not enable such views. The interior tower (Fig. 3) is housed in an exterior tower (Fig. 4), with a separate support structure for each connected by a double-helical walkway.

Figure 4: Exterior tower and double-helical interior walkway: (L) colorized; (M) diagram of the exterior tower�s location. (R) rendered wooden texture;

The tower exterior shows helical overhangs (Fig. 5) protecting the windows from direct sunlight, rain and snow.

Figure 6 shows an engineering drawing of the roof from below. By using measurements from this drawing and supplementing them with measurements taken on site, a 3D CAD model was constructed, and is displayed in the wire frame view (Fig. 6) and rendered views (Fig. 7).

The entrance and its canopy are structures that can be better understood from the models in (Figs. 8 and 9) than from a photograph or a visit to the actual site, since they are complex objects, and access and sightlines are restricted.

Figure 5: Exterior tower's double-helical exterior overhangs and interior walkway with exterior walls removed

Figure 7: Roof viewed from below: (L) false color CAD model; (R) rendered 3D CAD model wood grain; (M) Max file with textures taken from the temple.

Figure 8: Entrance canopy: (L) photograph; (m) photograph and Max model; (R) Max model. The shape of the top of the entrance canopy is a problem.

It is possible to select only one section from the single CAD model of the entire structure and display it from multiple viewpoints and with various levels of detail (Fig. 10).

Figure 10: Base: (L) wire frame; (M) colorized; (R) details of the canopy supports.

Figure 11: Rendered model: fully rendered external view with the external walls made transparent

Because of the constructive approach, any part may be rendered without displaying the other components and an external shell may be fully rendered (Fig. 11).

The models illustrated are virtual constructions using virtual lumber cutting, positioning and joining according to the specifications of the miya daiku based on empirical knowledge of the past. By virtual lumber cutting, positioning and joining, we mean that each piece of the temple is created from virtual parts that represent the shape of each piece of lumber in the same order that would have been used by the miya daiku. These virtual lumber operations show the value of digital preservation of cultural heritage using constructive modeling. The 3D model has recently been used to produce high quality renderings of the interior of Sazaed�, as would be seen by a person walking through the structure, and to produce animations [Bri01] of the journey through the temple (see http://ggpl.org/saza2001).

Data migration. The currently used CSG modeling tools (AutoCAD rel 12 AME) will cease to run on future systems, resulting in the CSG models being inaccessible. It will take as much or more effort to extract the currently used CSG data structure as it would to reconstruct the buildings from original data. However, the migration of the CSG models to FRep is research that empirically demonstrates what is needed for data migration to future platforms.

The miya daiku or shrine carpenter uses parts of the tree or piece of timber in a specific place or way to create what the miya daiku understands as a "living" harmonious structure. A simple example of this specific use of timber by the miya daiku is the fabrication of the main columns of the temple, which are cut from trees growing on four sides of a mountain. The orientation of these trees to the earth and to each other on the mountain is maintained as the columns in the temple structure. With the use of the constructive hypervolume model,²² we can reach beyond the virtual surfaces and model the actual material structure of a wooden object. In the future, with records of weather and growth rings of trees, we can synthetically grow a tree using volume modeling and fabricate synthetic pieces of timber, using the same type of traditional miya daiku procedures, to create a synthetic representation of such ancient temple structures. Synthetic simulations of the miya daiku procedures in constructing traditional temples would not only archive the historical objects themselves but also allow us a deeper understanding of the miya daiku craft.

In our research, we are exploring the use of optimized real time game engines as a method of viewing 3D cultural heritage content. These applications provide built in logic to handle basic world properties like gravity and collision detection. In addition, 3D games provide highly intuitive and efficient user interfaces, advanced network code for multi-user distributed environments, and an open coding environment allowing unlimited customization.

In real time simulation using gaming methods, a user can interact with the program, as well as with other users, in an immersive and entertaining environment. However, the restrictions imposed on a real time environment are significant. Even at relatively slow frame rate of ten frames per second (barely adequate for games), all computation for each frame must be finished within 100 milliseconds. On the most powerful gaming systems, this hardly allows for the level of complexity we might want in a historical simulation model. Such desired levels can be precalculated or calculated on demand by computational grids and presented as visualizations in various formats inside the real time game environment, transparent to the user.

Currently, at the University of Aizu Computer Arts Lab, we have modeled such a system using Quake [Car*03] as the front end client and the POV-Ray ray-tracer as the backend server. Our test case is a model of the Enichiji temple. In order to provide an immersive environment, we have created a model of this temple that runs in Quake and allows the user to climb the stairs, inspect the internal architecture, and move under, over, through or around the temple in full real time. At any location in the Quake environment, the user may choose a detailed POV-Ray rendered visualization (Fig. 12).

Figure 12: Inside the Enichiji temple model: (L) is a view of the real time Quake model in low detail; (R) is a detailed raytracing delivered to the client in seconds after a view is selected.

We are working to incorporate the HyperFun geometric modeling language into the Quake game engine and Web technologies.

Digital preservation of crafts heritage. As subjects of computer-based preservation efforts, traditional crafts such as pottery, embroidery or lacquer ware require special treatment. First of all, any craft is a living tradition, not a fixed set of inherited items. At the center of the tradition are masters with knowledge of essential craft technology, which is often not presented in written form. While computers may be used to preserve this technology or even to enhance it, computer-based technology is sometimes considered not to support, but rather to rival traditional crafts, giving rise to psychological and economic conflicts. However, the decreasing number of masters, fading technologies, and economic difficulties for crafts and their practitioners validate the necessity of computer-based preservation. The production of traditional Japanese lacquer ware or shikki suffers from the problems mentioned above, as well as from additional economic pressure due to cheap production of plastic look-alikes. In this section, we demonstrate how computers can help to preserve traditional crafts such as shikki manufacture, using a practical example of FRep modeling, conversion to polygonal BRep, and Web presentation of shikki items.

Virtual Shikki. When making actual shikki, parts of an item are produced manually using thin pieces of wood, which are then assembled, painted in different colors, and covered by natural lacquer or urushi. There is a great variety of shikki items: boxes, small drawers, stands, cups, bowls, sake pots, chopsticks, notebooks, and even ball pens and pencils. These items are quite different from one another in their topology, geometry, and texture.

The �Virtual Shikki� project includes the following research and development activities:

Implementation issues. The process of modeling shikki shapes included the selection of representative items, the measurement of the coordinates of control points, the introduction of the basic logical structure of the model (primitives and operations), the description of the parameterized constructive model using the HyperFun language, visualization using ray-tracing and polygonization, comparison of the obtained shape and control points with those of the original, modification of the construction, and selection of parameters of the model.

Some additional specific operations - for example, bounded blending - were required for adequate modeling of shikki shapes. A blending operation generates a smooth transition between two given surfaces. Blending operations for FRep were formulated by Pasko et al. [PAS*95] for all set operations (union, intersection, difference) between two solids. However, this formulation of blending suffers from the resulting surfaces being offset (expanded or contracted) everywhere in the space. This is not acceptable in modeling lacquer ware shapes, because blending should not affect original surfaces outside the specified area of influence. To satisfy this requirement, we proposed and implemented bounded blending operations [PPI*02], illustrated in Fig. 15. A sake pot is shown in Fig. 15a with the circle showing the region of bounded blending. Fig. 15b shows the union of the initial pot spout and the ellipsoidal shape (the left bottom part of the pot body) which are to be blended. The cylindrical bounding solid is shown in Fig. 15c. The blended shape resulting from the bounded blending operation should completely reside inside this solid. The resulting blend satisfying this requirement is shown in Fig. 15d.

Web presentation. The �Virtual Shikki� project is presented at the special website[PP00] (several snapshots are shown in Fig. 16). Each image at the site is hyperlinked to the corresponding HyperFun model and the VRML model, which can be downloaded and visualized using any VRML viewer such as the CosmoPlayer. See an example of the sake set VRML model in Fig. 17.

VRML is often selected for Web presentation of 3D virtual objects. However, VRML has well-known drawbacks such as huge data files and long downloading time. The size of the sake set VRML file (Fig. 17) is 4.5 Mb (uncompressed ASCII version). Other and more compact Web3D formats should be considered in the future. On the other hand, no HyperFun models for any lacquer ware item exceeded 5 Kb. Thus we can conclude that HyperFun provides a high level of compression and should be considered as a lightweight geometric network protocol. A radical solution would be to transfer small HyperFun models to the user�s computer and provide a browser able to unfold a polygonal or other representation suitable for interactive visualization.

Creating specific models of real world objects requires a large amount of routine labor in measuring control points and fitting model parameters. Semi-automatic methods based on using 3D scanned points as control points and non-linear optimization for automatic fitting of parameters can be used to make the work of the modeler easier.

Some of the most useful methods for solving the problem of nonlinear optimization for fitting parameterized models in the least square sense are briefly discussed here and then applied to the concrete example of the parameterized FRep sake pot model presented above in the �Virtual Shikki� case study.

Nonlinear least square approach. Given a parameterized FRep model that describes the global shape of the object, and a set of 3D points on or near the surface of this object, the task is to recover the best set of parameters so that the parameterized FRep model closely fits the data points. The 3D points, typically obtained by a scanner, serve as control points for the final shape of the object. The vector of parameters from the FRep model control the final shape, and the best fitted parameters should give the closest possible model according to the information provided by the control points.

For estimation of general distance of the point cloud to the surface with the current vector of parameters, a fitness function is needed. The FRep model itself can serve for defining such an algebraic distance. The least square error, or error of fit, for the model is the sum of the square of the defining function values at all points. Techniques of function minimization can be used with the least square error function. FRep models are essentially nonlinear, and so is the least square error. Therefore, local and global nonlinear minimization techniques are considered below.

Local methods for nonlinear minimization. The most traditional methods for solving problems of nonlinear least square fitting are Levenberg-Marquardt or Newton type methods [Den*81] [Mor78] [FPT*92]. Such methods rely on a local quadratic approximation of the function being minimized; this quadratic approximation is obtained by a Taylor series expansion of the function in the vicinity of the current vector of parameters. The algorithms of Levenberg Marquardt and Newton methods search iteratively for a privileged direction to go in the parameter space and a step length in that direction based on the information given by the gradient and the Hessian matrix of the function. For some parameter spaces with multiple local minima, such methods are likely to be trapped into a local minimum. Good initial parameters are very important, because they determine to which minimum the algorithm may converge.

Global methods avoiding local minima. In contrast to local methods for nonlinear minimization, global methods are intended to find the best possible solution to the optimization problem. The choice of the starting point in parameter space should cause fewer problems for these methods. Simulated annealing is one of these methods, which has received a lot of attention for solving optimization problems both in discrete and continuous spaces [Gof*94] [Kir*83] [Met*53]. When trying to minimize a function usually only downhill steps are accepted, but in simulated annealing uphill steps can be accepted with a probability, initially close to 1 and decreasing to 0 with the temperature of the system. Methods based on simulated annealing may be a good alternative to classical direct methods in a global optimum search among many local optima, but they face some major problems of efficiency: the objective function needs to be sampled a huge number of times before reaching convergence.

Hybrid methods for nonlinear minimization. In order to overcome problems of both methods presented in the previous sections, a two stage algorithm of nonlinear FRep fitting is proposed. At the beginning, a global method like simulated annealing is used to identify the vicinity of the global minimum, then a local, faster method, is applied, to extract the parameters that closely fit the 3D point set. Switching to a local method occurs when the error is below some threshold or when the parameterized model looks close enough to the data set. The result of this two stage process is a method faster than a purely global method, and it can also avoid the local minimum.

Experiments. The two stage process has been applied to the fitting of the parameterized FRep model of a sake pot in the �Virtual Shikki� project. The initial set of control points includes 27048 3D points on or near the surface of the object (Fig. 13).

The parameterized FRep model has several parameters to be estimated: the position of the object in the space, the radius of the main body, and the last one controlling the shape of the handle. It took 347 seconds on a Pentium IV processor laptop for the two stage algorithm to converge to the global minimum. Most of the time is spent in the global minimization procedure (341 seconds).

Figure 14: Evolution of the shape of the sake pot during the fitting process.

We proposed a new paradigm to digital preservation of cultural heritage based on constructive shape modeling using CSG and FRep, and on open data structure and procedures. As a case study, CSG was used in modeling the Japanese temples Enichiji and Sazaed� with its unique internal structure. Traditional Japanese lacquer ware was modeled using FRep. Constructive modeling usually requires high levels of 3D modeling skill and is labor-intensive. Accordingly, we demonstrated the possibility of automation by the use of fitting of a parameterized FRep model to a cloud of surface points. Automation of the logical structure extraction will be investigated in our future work.

We are in the process of migrating the CSG based objects from a set of proprietary and now obsolete but open architecture CAD tools to FRep based HyperFun models that fit the purposes of both digital preservation and long term secure archiving. We are developing real time environments for both modeling and public access to historical models

The proposed paradigm has several distinct advantages: constructive modeling helps to reveal knowledge about an object's logical macrostructure; the representation of three-dimensional surface microstructure (bumps, cracks, roughness) is possible to model using FRep; the open and simple textual format of the geometric protocol makes it highly suitable for long-term digital preservation and for the exchange of models among systems and people. FRep's major disadvantage which has restricted its wide spread use in industrial applications has been processing speed. However, such problems are being resolved with the rapid evolution of computer technology, namely parallel and distributive processing, and specialized hardware development.

[Abo99] ABOUAF J.: The Florentine Piet�: can visualization solve the 450-year-old mystery? IEEE Computer Graphics and Applications, vol. 19, No. 1 (1999), pp. 6-10.

[ACF*99] ADZHIEV V., CARTWRIGHT R., FAUSETT E., OSSIPOV A., et al.: HyperFun project: a framework for collaborative multidimensional FRep modeling. In Proc. Implicit Surfaces '99 (1999), pp. 59-69. (Eurographics/ACM SIGGRAPH Workshop).

[Add00] ADDISON A.: Emerging trends in virtual heritage. IEEE Multimedia, Special Issue on Virtual Heritage 7, 2 (April 2000), pp. 22-25.

[BE99] BEDWELL E., EBERT D.: Artificial evolution of implicit surfaces. In Proc. Eurographics/ACM SIGGRAPH Workshop Implicit surfaces '99 (1999), pp. 81-88.

[Blo*97] BLOOMENTHAL J. (Editor), et al.: Introduction to Implicit Surfaces. Morgan Kaufmann, 1997.

[BMK*94] Bandai Machi Ky�iku Iinkai (ed. and pub.): Shiseki Enichiji Ato IX, 1994.

[Den*81] DENIS J. E., et al.: An adaptive nonlinear least-squares algorithm. ACM Transaction on Mathematical Software 7 (1981), pp. 348-368.

[Ena02] The ENAME Charter, International Guidelines for Authenticity, Intellectual Integrity, and Sustainable Development in the Public Presentation of Archaeological and Historical Sites and Landscapes, Draft 2 (October 2002), Scientific and Professional Guidelines (B, C), Articles 18 and 20. National Park Service Symposium on the ENAME Charter (2002). URL:http://www.heritage.umd.edu/CHRSWeb /Belgium/Proposed%20Charter.htm

[FF00] FLEISCHHAUER C., FRANCIS D.: Comment on Circumvention (Feb. 2000). Library of Congress (National Digital Library Program, and the Motion Picture, Broadcasting and Recorded Sound Division). URL : http://lcweb.loc.gov/copyright/1201/comments/175.pdf

[FPT*92] FLANNERY B., PRESS W., TEUKOLSKY S., VETTERING W.: Numerical Recipes in C � the Art of Scientific Computing. Cambridge University Press, 1992.

[Gof*94] GOFFE W., et al.: Global optimization of statistical functions with simulated annealing. Journal of Econometric 60 (1994), pp. 66-95.

[GW96] GARRET J., WATERS D.: Preserving Digital Information: Report of the Task Force on Archiving of Digital Information. The Commission on Preservation and Access and The Research Libraries Group, Inc. (May 1996). URL: http://www.rlg.org/ArchTF/

[HBC*02] HEDSTROM M., BRANDT L., CAMPBELL L., et al.: It�s About Time: Research Challenges in Digital Archiving and Long-Term Preservation. In Library of Congress (October 2002), Preserving Our Digital Heritage: Plan for the National Digital Information Infrastructure and Preservation Program, Washington, D.C.: Library of Congress: 205-220. (Sponsored by the National Science Foundation, Digital Government Program and Digital Libraries Program, Directorate for Computing and Information Sciences and Engineering, and the Library of Congress, National Digital Information Infrastructure and Preservation Program). URL:http://www.digitalpreservation.gov/repor /NSF_LC_ Final_Report.pdf

[Hof89] HOFFMAN C.: Geometric and Solid Modeling. An Introduction. Morgan Kaufmann, 1989.

[Kir*83] KIRKPATRICK S., et al.: Optimization by simulated annealing. Science 220 (1983), pp. 671.

[LPC*00] LEVOY M., PULLI K., CURLESS B., et al.: The Digital Michelangelo Project: 3D Scanning of Large Statues. In Proc. SIGGRAPH 2000, pp. 131-144.

[Met*53] METROPOLIS N., et al.: Equations of state calculations by fast computing machine. J. Chem. Phys. 21 (1953), pp. 1097.

[Mor78] MORE J.: The Levenberg-Marquardt algorithm implementation and theory. Lecture Notes in Mathematics No. 630 Numerical Analysis (1978), vol. 630, pp. 105-116.

[Mur91] MURAKI S.: Volumetric shape description of range data using �Blobby Model�. Computer Graphics 25, 4 (1991), pp. 227-235. (Proc. SIGGRAPH �91).

[Neu97] NEUGEBAUER P. J.: Geometrical cloning of 3D objects via simultaneous registration of multiple range images. In Proc. 1997 International Conference on Shape Modeling and Applications (SMI '97), IEEE Computer Society (1997), pp. 130-139.

[PAS*95] PASKO A., ADZHIEV V., SOURIN A., SAVCHENKO V.: Function representation in geometric modeling: concepts, implementation and applications. The Visual Computer 11, 8 (1995), pp.429-446. URL: http://wwwcis.k.hosei.ac.jp/~F-rep/

[PAS*01] PASKO A., ADZHIEV V., SCHMITT B., SCHLICK C.: Constructive hypervolume modeling. Graphical Models, special issue on Volume Modeling 63, 6 (2001), pp. 413-442.

[PPI*02] PASKO G., PASKO A., IKEDA M., KUNII T.: Bounded blending operations. In Proc. Shape Modeling International 2002 (May 2002), pp. 95-103. (IEEE Computer Society).

[RCM*01] ROCCHINI C., CIGNONI P., MONTANI C., et al.: 3D Scanning the Minerva of Arezzo. In Proc. ichim01 (2001), vol. 2, pp. 265-272.

[Req80] REQUICHA A.: Representations of rigid solids: theory, methods, and systems. Computing Surveys 12, 4 (1980), pp. 437-465.

[Sim00] SIMONS B.: Exemption to Prohibition on Circumvention of Copyright Protection Systems for Access Control Technologies. Comments to the Copyright Office of the Library of Commerce (Feb. 2000). Association for Computing Machinery. URL:http://lcweb.loc.gov/copyright/1201/ comments/171.pdf

[TL92] TODD S., LATHAM W.: Evolutionary Art and Computers. Academic Press, 1992.

[VGG99] VILBRANDT C., GOODWIN J. M., GOODWIN J. R.: Computer Models of Historical Sites: Sazaed� - From the Aizu History Project. In Proc. 1999 EBTI, ECAI, SEER & PNC Joint Meeting (1999), pp. 489-502. (Academia Sinica).

Figure 15: Bounded blending operation: a) sake pot with the region of blending circled; b) initial pot shape without blending; c) pot and cylindrical bounding solid; d) resulting pot shape with bounded blending.

Figure 16: Snapshots of the �Virtual Shikki� Web site with images hyperlinked to the HyperFun and VRML models of corresponding lacquer ware items.

Figure 17: VRML model of the sake set examined using the CosmoPlayer software.