Computer Graphics & Geometry
G. Pasko
IT Institute, Kanazawa Institute of Technology, Japan
email:
A. Pasko
Department of Digital Media, Hosei University, Japan
email:
C. Vilbrandt
Computer Arts Laboratory, University of Aizu, Japan
email:
T. Ikedo
Department of Digital Media, Hosei University, Japan
email:
Contents
Issues of digital preservation of shapes and internal structures of culturally valuable objects are discussed. An overview of existing approaches to digital shape preservation as well as corresponding problems is given. Our approach is based on using constructive modeling, which reflects the logical structure of the shapes. We examine and select those mathematical representations of shapes that fit the purposes of longterm digital preservation. Constructive Solid Geometry (CSG) is applied in modeling a Japanese temple Sazaedo with a unique internal structure. Traditional Japanese lacquer ware called shikki is modelled using the function representation (FRep). We describe the Virtual Shikki project aimed to present the virtual shapes and textures of lacquer ware on the Web.
1. Digital preservation of cultural heritage
Using computers for preservation of cultural heritage in digital form is one of the recently popular topics in computer graphics, geometric modeling, and virtual reality communities. There are several directions in this research activity [1]:
In this paper, we would like to share a general view on digital preservation of shapes and practical experience in using computers to model a Japanese temple Sazaedo with a unique internal structure and lacquer ware items called shikki. In the next section, we discuss different paradigms of digital preservation of culturally valuable shapes. Section 3 provides information on the selection of the basic mathematical model and tools. Modeling Sazaedo using CSG is presented in Section 4. The Virtual Shikki project based on FRep is described in Section 5. Section 6 summarizes the paper.
2. Paradigms of digital shape preservation
In this section, we discuss and compare different approaches to computeraided preservation of culturally valuable shapes. A shape can be considered a point set in a multidimensional space in the general case. 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.
2.1 Measurements and drafting
Taking measurements and 2D drafting is the traditional way of documenting existing shapes. It is supported by computeraided drafting systems and has logical continuation in the �measurements and modeling� paradigm.
2.2 Scanning
There exist several welldeveloped technologies for automatic noncontact acquiring 3D point coordinates on the visible surfaces of objects. These technologies are based on lasers, structured light, sound, and stereo imagery. Although archiving of rough data is preferable in any case, it can be the best way of actually representing the surface as it was shown in the Digital Michelangelo project [9]. 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 that �if one only wants to view a 3D model, and not perform geometric operations on it, then it need not be represented polygonally.�
2.3 Scanning and meshing
Traditionally a polygonal mesh is generated on the base of the rough data. This can be necessary especially if the measurement equipment does not provide point coordinates directly. For example, in the Pieta Project [9] the scanner consisted of six blackandwhite cameras capturing images of a striped pattern projected on an object. Accompanying software computed a triangle mesh from the captured images using principles of stereo computer vision.
2.4 Measurements and modeling
This is the next step from the traditional 2D drafting approach. It is especially important in the situation when the real object is lost, destroyed or damaged, with the only source of information in previous measurements and drawings. The goals are to create as full as possible 3D model of the object, its internal structure, design logic and history of the shape construction, timedependent aspects and other parametric dependencies. De facto standard industrial modeling tools are usually based on the socalled boundary representation (BRep) of 3D objects. In particular, BRep can be based on a polygonal mesh approximation of the object surface. This modeling scheme can be only partly appropriate for achieving the mentioned above goals of modeling. BRep data structures do not reflect the internal object structures (e.g., material distribution) or the design logic. Parameterization of BRep models is quite limited. Only simple timedependent parametrization of Brep is allowed, which does not change the object topology. A constructive modeling approach can be an alternative. It is based on the construction of complex objects using simple primitive elements and combining and transformation operations. This approach is supported by the Constructive Solid Geometry (CSG) and the function representation (FRep) discussed in the next section.
2.5 Scanning and modeling
Scanning can provide a set of reference control points for manual modeling or the full point cloud can be used for the (semi)automatic model generation. An example of the latter case is the voxel model generation from the set of range images [11]. The potential of the automatic search of the simple model structure and parameters fitting of an implicit surface model on the base of range data was illustrated in [10]. In the case of the unknown initial estimation of the model structure, genetic evolving of shapes can be applied similarly to the reported experiments with CSG [13] and analytically defined implicit surfaces [5]. Here, the overall distance of 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 optimization of shape parameters and further genetic evolving of shape structures.
3. Selection of a shape representation and modeling tools
The basic mathematical representation in digital preservation should serve for several purposes: to reflect the logic of the object construction, to support modeling of parametric families of shapes, to support specific modeling operations with possibility to extend them, to serve for generation of polygonal, other surface models, and voxelization for visualization, animation and virtual objects presentation on the Web, and to serve for direct control of rapid prototyping machines with arbitrarily high precision for reproduction of the modeled objects. The boundary representation (BRep) and Constructive Solid Geometry (CSG) are the most well known models of 3D solids [6]. However, both schemes have limitations from the point of view of the above mentioned criteria.
The most problematic are operations on BRep solids. Settheoretic (Boolean) operations often result in nonvalid solids with cracked boundaries. Deformations of BRep solids can cause selfintersections of boundaries. Shape transformations (metamorphosis) are applicable to only to Brep solids of the same topological genus.
To design a shape one can select simple shapes (primitives), specify their parameters and position in space, and construct a more complex shape of them by applying union, intersection, or subtraction set operations. This modeling paradigm and the corresponding representation is called CSG. A CSG solid is represented as a binary tree (or a CSG tree) with operations at the internal nodes and primitives at the leaves. The point membership classification algorithm defines whether a given point is inside, outside, or on the boundary of the solid. This algorithm recursively traverses the CSG tree starting from the root. In the nodes with linear transformations, the inverse of the transformation is applied to the current point coordinates. When the recursion reaches the leaves, the point is tested against the corresponding primitives. Then, the classification results are combined in the internal nodes with settheoretic operations.
CSG tree provides both the construction history and the logical structure of the solid. This allows for editing the primitives or other sublevel objects of constructed solids. CSG suffers from asymmetric treatment of primitives and complex solids. Although modern CSG systems such as SvLiS [4] can adopt arbitrary primitives and operations to define them, the set of operations allowed in the nodes of the CSG tree is still very limited, thus restricting the representational power of this model. Though it performs well for the mechanical or architectural objects, it can hardly be used for organic shapes and sculptures. Deformations and metamorphosis are not applicable to CSG solids.
Proprietary binary file formats for BRep and CSG make difficult to translate or provide interoperability or migration across platforms, thus forcing the life span of the data to be limited. There are open file standards for geometric data exchange, such as IGES and STEP. 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 (ISO 10303 standard) supports CSG, but this part of the protocol is quite rarely used nowadays.
We propose to use the socalled function representation (FRep) as the basic mathematical model [12]. FRep is a generalization of traditional implicit surfaces [3] and CSG. It represents an object by a continuous function of three variables. A point belongs to the object if the function is positive at the point. The function is zero on the entire 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.
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. Many modeling operations are closed on the representation, i.e., generate as a result another continuous function defining the transformed object. They are settheoretic operations, blending, offsetting, nonlinear deformations, metamorphosis, projection and others. However, the set of operations needs to be extended to support such operations as bounded blending (see Section 5.2) useful in modeling lacquer ware.
The HyperFun language [7, 8] was introduced for teaching and practical use of FRep modeling. It is a minimalist programming language supporting all notions of FRep. HyperFun was also designed to serve as a lightweight protocol for exchanging FRep models between people, software systems, and networked computers. Average size of HyperFun files is 5K. This allows for efficient implementation of a clientserver modeling system where a client can run a simple interface tasks and generate a HyperFun protocol to be sent to the server. The server site can be a powerful parallel computer or a computer cluster to perform timeconsuming tasks such as raytracing, polygonization, voxelization and others.
The open and simple textual format of HyperFun, its clearly defined mathematical basis, support of constructive, parameterized and multidimensional models, its support by free modeling and visualization software, and ease of use make HyperFun a good candidate as a tool for digital preservation and archiving of culturally valuable shapes.

Figure 1. CSG models of the Sazaedo roof and canopy.
Figure 2. The rendered model of Sazaedo showing helical structure. 
Figure 3. Fully rendered view of Sazaedo. 
4. Modeling Sazaedo
The scan and polygonal mesh approach in computer modeling of an object produces a visual image, but does not contain the level of consistent and accurate detail needed for the digital preservation of cultural and historical objects. The authors propose a constructive preservation paradigm that reflects the logical structures of objects reproduced. Furthermore, this paradigm requires the use of freely available, open source hardware and software and a data structure that is transparent, independent, robust, multidimensional and based on rigorously proven mathematical processes to enable a true digital preservation environment.
The need for such a constructive paradigm is demonstrated by one author�s experience with a model of historic temple in the Aizu region of Japan. Archaeological data and onsite measurements yielded not only surface data, but also necessary preservation information on the relationship of materials, structures and procedures. Constructive Solid Geometry was chosen as the most likely data format for modeling historical architecture with any possibility of archival quality. All parts of the historical building Sazaedou [14] were created whenever possible with only CSG based entities. However, because CSG is limited in its range of shape representation and the overall size of the models was extremely large the double helix ramp inside Sazaedou had to be represented unsatisfactorily by a polygonal mesh.
The models of Sazaedou (Figs.13) illustrate that these are virtual constructions using virtual lumber cut, positioned and joined according to the specifications of the miya daiku, temple carpenter. This empirically shows the value of digital preservation of cultural heritage using constructive modeling. However, constructive modeling is time consuming and depends on a great deal of computer knowledge, 3D visualization skills, as well as a good understanding of materials, material processes and engineering knowledge. Thus, it is presently limited to few highly skilled persons. Furthermore, the above approach relies on hardware and proprietary software that may conceivably become obsolete and unusable even before the modeled objects themselves are destroyed.
In using CSG, computational requirements dictated that sections of the model be developed in many separate files on four different PC based systems. There were significant problems in data creation and manipulation of sections of the buildings across separate files on different computers as the coordination was all manually done. When combining the files into one file, it is needless to say that this data overwhelmed even the fastest single system on several different platforms. Five years later, the entire model of Sazaedou cannot be handled easily at one time in present day animation and rendering systems. The efforts the author experienced using CSG in commercial products on single computer systems with the hope of creating digital archival data seems wasted. It is doubtful that even this CSG constructed data will live through the next several decades because of the proprietary nature of the commercial software and the unknown quality of the CSG database. It may take as much or more effort to extract the CSG data structure embedded in these proprietary programs as it would to reconstruct the buildings from original data. We can conclude from this experience that the use of open data structures and archival formats is vitally important for digital shape preservation of cultural heritage.
5. Virtual Shikki project
Historical heritage of traditional crafts such as pottery, embroidery or lacquer ware has specific features from the computerbased preservation point of view. First of all, any craft is a living tradition, not a fixed set of inherited items. It includes masters with their knowledge of the essential craft technology, which is often not presented in written form. This gives opportunity to preserve the technology or even enhance it using computers. On the other hand, it brings up psychological and economical problems, when computerbased technology is considered as not support, but a rival to traditional crafts. The necessity of computerbased preservation is validated by decreasing number of masters, fading technologies, and crafts loosing economical grounds.
Parts of a shikki item are produced manually using thin pieces of wood, then they are assembled, painted in different colors, and covered by natural lacquer called �urushi�. There is 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 in their topology, geometry, and texture. In this work, we apply the function representation supported by HyperFun software to model shikki objects.
5.1. Project content
The purposes of the Virtual Shikki project are reflected in the following directions of research and development activity:
5.2. Implementation issues
In this paper, we describe the part of the project dealing with modeling shapes and presenting virtual models of existing items. In this section we describe specific modeling operations, design of typical shikki objects and the devoted Web site.
5.2.1. Specific modeling operations
A blending operation generates a smooth transition between two given surfaces. Blending operations for FRep were formulated in [12] for all set operations (union, intersection, difference) between two solids. However, the formulation of blending as a Gaussiantype displacement from the standard set operations 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 a bounded blending operation, illustrated in Fig. 4. A sake pot is shown in Fig. 4a with the circled area of the resulting bounded blending. Fig. 4b shows union of the initial pot spout and ellipsoidal shape (left bottom part of the pot body) to be blended. The cylindrical bounding solid is shown in Fig. 4c. The blending shape resulting from the bounded blending operation should completely reside inside this solid. The resulting blend satisfying this requirement is shown in Fig. 4d.
The HyperFun definition (see syntax description in the paper [7] and online at [8]) of the proposed procedural formulation of the bounded blending union is shown in Fig. 5. Here, arguments of the operation are transferred as a parameter array a[5]. Then, it is unfolded to the following variables: functions f1 and f2 define the original shapes (pot spout and ellipsoidal left bottom part of the pot body), function f3 defines the bounding cylindrical solid, and parameters b0 and b1 control the shape of the blend. The difference between this formulation and one given in [12] is that the standard union operation between f1 and f2 (symbol ��) is displaced using function disp, which is guaranteed to be zero outside the bounding solid f3. The proposed bounded blending was extensively used in modeling shapes of lacquer ware in this project.
a  b 
c  d 
Figure 4. Bounded blending operation: a) sake pot with the circled area of blending; b) initial pot shape without blending; c) pot and cylindrical bounding solid; d) resulting pot shape with bounded blending.
BlendUniB(x[3],a[5]){
 blending union of objects
 f1 and f2
 bounded by object f3
 displacement with parameters
 b0 and b1
f1 = a[1]; f2 = a[2]; f3 = a[3];
b0 = a[4]; b1 = a[5];
Uni = f1  f2;
w1 = f1^2 + f2^2;
if (f3 > 0) then w2 = f3^2;
else w2 = 0;
endif;
disp = b0*(1  w1/(w1+b1*w2));
BlendUniB = Uni + disp;
}
Figure 5. Bounded blending union operation defined in HyperFun.
5.2.2. Virtual objects presentation
The implementation of the three first stages of the project, namely modeling shapes, digitizing textures, and presentation of virtual objects, includes the following:
1) Creation of several 3D computer models of traditional Japanese lacquer ware items. The basic modeling tool was HyperFun language and software [7, 8].
2) Generation of polygonal models using HyperFun Polygonizer [8] and export to VRML (Virtual Reality Modeling Language) format.
3) Decimation of polygonal shapes using different software tools to achieve as low as possible size of VRML models.
4) Scanning color textures directly from lacquer ware objects with planar surfaces and from photographs. Texturing polygonal models using traditional tools like 3D Studio Max.
5) Generation of images and creation of the Web site [15] (Fig. 6). A HyperFun model is available for each object of the Web site. Each image is also hyperlinked to the corresponding VRML model, which can be downloaded and visualized using any VRML viewer such as CosmoPlayer. See an example of the sake set VRML model in Fig. 7.
The average size of VRML file is 100500 Kb. However, the size of the sake set file (Fig. 6) is 4.5 Mb. On the other hand, HyperFun models for all lacquer ware items did not exceed 5 Kb. In this sense, we can conclude that HyperFun provides a high level of compression and should be considered as a lightweight network protocol in future. We found that VRML files are too memory expensive, especially in the case of complex shapes and sets. Other and more compact Web3D formats should be considered in future. More 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.
Modeling specific shapes required a large amount of routine labor on measuring control points and manual fitting model parameters. Semiautomatic methods should be introduced on the base of 3D scanning of real objects for getting control points and nonlinear optimization for automatic parameters fitting.
6. Conclusion
We proposed an approach to digital shape preservation based on using constructive modeling. We examined and selected Constructive Solid Geometry and the function representation as mathematical models of shapes that fit the purposes of longterm digital preservation. Constructive Solid Geometry (CSG) was used in modeling a Japanese temple Sazaedo with a unique internal structure. Traditional Japanese lacquer ware was modelled using FRep.
a  b 
c 
Figure 6. Snapshots of the �Virtual Shikki� Web site with images hyperlinked to VRML models of corresponding lacquer ware items.
Figure 7. VRML model of the sake set examined using CosmoPlayer software. 
The approach to digital shape preservation taken here seems to suggest too much hard work, if compared with automatic surface scanning and almost automatic polygonal mesh generation. The decision on which way to go in a particular project depends on the final purposes. If only a visualization animation from a distant viewpoint is needed, then polygonal mesh or other BRep models can be satisfactory. Constructive modeling helps reveal knowledge about the shape logical macrostructure. Representation of threedimensional surface microstructure (bumps, cracks, roughness) is also out of the range of BRep abilities, but it is still possible to model it using FRep. Open and simple textual format of the FRep geometric protocol is quite important for longterm digital preservation and model exchange between systems and people. The burden of manual labor can be reduced gradually by introducing semiautomatic methods based on 3D scanning of real objects with acquisition of control points and nonlinear optimization for automatic parameters fitting of the constructive objects. Automation of the logical structure extraction will be investigated in our future work. Future development of this project will also include development of interactive modeling tools specialized for lacquer ware and utilizing rapid prototyping machines for the production of test or even final products.
Acknowledgements
The work was supported by the grant of the Fukushima Prefecture government. We would like to thank Takase family for sharing information on the shikki production process and needs, Eric Fausett for texturing VRML models, and Jody Vilbrandt for her help with preparation of this document.
References
[1] A. Addison, Emerging trends in virtual heritage, IEEE Multimedia, Special Issue on Virtual Heritage, vol. 7, No. 2, 2000, pp. 2225.
[2] J. Abouaf, The Florentine Pieta: can visualization solve the 450yearold mystery?, IEEE Computer Graphics and Applications, vol. 19, No. 1, 1999, pp. 610. http://www.research.ibm.com/pieta
[3] J. Bloomenthal et al., Introduction to Implicit Surfaces, Morgan Kaufmann, 1997.
[4] A. Bowyer, Svlis: Introduction and User Manual, Information Geometers, Winchester, UK, 1995.
[5] E. Bedwell, D. Ebert, Artificial evolution of implicit surfaces, Eurographics/ACM SIGGRAPH Workshop Implicit surfaces '99, ENSERB, France, 1999, pp.8188.
[6] C. Hoffmann, Geometric and Solid Modeling. An Introduction, Morgan Kaufmann Publishers, San Mateo, USA, 1989.
[7] V. Adzhiev, R. Cartwright, E. Fausett, A. Ossipov, A. Pasko, V. Savchenko, HyperFun project: a framework for collaborative multidimensional FRep modeling, Implicit Surfaces '99, Eurographics/ACM SIGGRAPH Workshop (Universite Bordeaux 1, France, September 1315 1999), J. Hughes and C. Schlick (Eds.), pp. 5969.
[8] HyperFun Project: Language and Software for Frep Modeling, URL: http://www.hyperfun.org
[9] M. Levoy et al., The Digital Michelangelo project: 3D scanning of large statues, SIGGRAPH 2000 Proceedings, ACM, 2000, pp. 131144.
[10] S. Muraki, Volumetric shape description of range data using "Blobby Model", Computer Graphics, Proceedings of SIGGRAPH 91, 25 (4), 1991, pp. 227235.
[11] P.J. Neugebauer, Geometrical cloning of 3D objects via simultaneous registration of multiple range images, Proceedings of the 1997 International Conference on Shape Modeling and Applications (SMI '97), IEEE Computer Society, 1997.
[12] A. Pasko, V. Adzhiev, A. Sourin,
V. Savchenko, Function representation in geometric modeling: concepts, implementation and applications, The Visual Computer, vol.11, No.8, 1995, pp.429446.
[13] S. Todd, W. Latham, Evolutionary Art and Computers, Academic Press, 1992.
[14] C.W. Vilbrandt, J.M. Goodwin, and J.R. Goodwin, Computer models of historical sites: Sazaedou  from the Aizu History Project, Proceedings 1999 EBTI, ECAI, SEER & PNC Joint Meeting (Taipei: Academia Sinica), pp. 489502.
[15] Virtual Shikki Web site, URL: http://www.k.hosei.ac.jp/~pasko/Shikki/Shikki.html
Computer Graphics & Geometry