The procedural method is cutting edge in gaming and virtual cities generation. This paper presents a novel technique for procedural real-time scene generation using a truncated icosidodecahedron as basic element and a custom physics system. This can generate a virtual museum in an interactive-way. For doing this, we have created a simple interface that enables creating a procedural scenario regarding the user-speci ed patterns, like number of pieces, connection mode, seed and constraints into the path. The scene is generated around three dimensional edges meaning a new point of view of hypermuseums. It has its own physics system to adapt the movement through the three dimensions of the scene. As a result, it allows the user to create a procedural scene in almost real-time where a user character can go over the 3D scene using a simple interactive interface.
Nowadays, the generation of virtual procedural scenes is growing importance in video games and virtual reality. The procedural generation is used in many areas, such as generating volumetric re [FKM+07], creating textures [RTB+92] or piles of rock for building [PGGM09]. In fact, the building information modeling is a popular research area, e.g. with some works from Muller et al. [MWH+06] and Patow [Pat12].
On the other hand, physical museums are trying to bring the art and history to the general public. The concept of hypermuseum [Sch04] was born to virtually recreate the interior of a museum. Thus, a hypermuseum is usually understood as an identical recreation of a physical museum. They are subject to the physics laws and have a typical path structure. This work presents a new point of view for hypermuseums unleashing the imagination. The idea is creating a hypermuseum regardless of the physical laws, following the Escher's picture \Relativity" or \Inception" movie. We use a truncated icosidodecahedron (TI) to create the virtual path rotating and connecting its di erent faces.
The procedural process generation is not used to be in real time because the idea is creating and saving something to be used later, but in this case, the hypermuseum is procedurally generated at the same time that it is gone over. Thus, this paper presents an almost real-time approach for procedural generation using a space voxelization.
The rest of the manuscript is organized as follows. In Section 2, several works related to our proposal are described. Section 3 presents the TI and explains the mathematics that have been used in the polyhedron and Sec. 4 shows the general idea of creating an hypermuseum with these pieces. Section 5 shows the process to generate a TI into the scene. Section 6 explains the path generation and the custom physics system. Section 7 explains the space division used for data storage and accelerating the generation process. Section 8 shows the evaluation of our proposal. Finally, Section 9 analyzes the conclusions and states the open issues of this work. 2
Some researches have previously created hypermuseums. For instance, [Sch98] generates an accurate representation of a museum using a WWW database. [WWWC04] generates virtual content in which visitors can interact on a display or via web. William Swartout et al. propose to create virtual guides using a natural language and human aspects [STA+10].
Nevertheless, as far as we know, this proposal means the rst time that a procedural process is being used to generate a hypermuseum. In any case, there are some works with similar procedural approaches. [STBB14] presents a complete survey with di erent procedural methods useful to generate features of virtual worlds, including buildings and entire cities that can be viewed as similar to hypermuseums. Di erent methods employ a combination of computational geometry algorithms similar to our proposal. Stefan Greuter et al. [GPSL03] describe a \pseudo in nite" city where several kinds of buildings are procedurally generated with di erent parameters. Julian Togelius et al. [TPY10] generate a map using a multi-objective evolutionary algorithm. [LSWW11] creates paths in a similar way to this work where a user can walk trough them. Finally, [CwCZ11] creates procedural elements using voxels as basic elements. Against these alternatives, this paper presents a novel technique towards real-time procedural scene generation. 3
This section presents the gure used for generating the scene and explain the required mathematical basis to create it.
An icosidodecahedron is a Platonic polyhedron with twenty triangular and twelve pentagonal faces (see Fig. 1, rst element). Every Platonic solid has a dual. The dual solid is the polyhedral element whose vertices are positioned in the center of each face of the rst solid. The Platonic solid can be vertextruncated by its dual when the ratios ddodecahedron=dicosahedron (being d the radius between the faces and the center of polyhedron) get appropriate values. Their intersection gives Archimedean solids. In this case, an icosahedron and a dodecahedron are combined to obtain the icosidodecahedron.
Our gure called TI, presents a more complex geometry than an icosidodecahedron. We use the vertex truncation between an icosidodecahedron and a rhomb-triacontahedron. Figure 1 shows the obtained truncation. A complex polyhedra is used for connecting the faces by means of a connecting bridge allowing a user character to walk trough the faces. The face transitive duals of the series of the vertex-transitive polyhedra go from the rhomb-triacontahedron to the deltoid-hexecontahedron, passing through a continuous series of intermediate hexakis-icosahedra (also called disdyakis-triacontahedra). The following parameters are used for truncation: ddodecahedron = 1=p1 + (1= 2)
p dicosahedron = = 3 1=(1 + 1= 2) drt 1 (1) (2) (3) where
is the golden ratio and drt is the radius of a rhomb-triacontahedron.
Each triangular face of the TI is enumerated as follows. First, a face is randomly selected to be numbered with number one. For each face, three connected faces can be accessed numbering them in clockwise. Then, we get the second face and repeat this process. Finally, all local positions and rotations of the faces from the center of the icosidodecahedron are saved. For each face, there is another face with the same rotation and opposite position requiring only four data values in space position to position a face. 4
The Truncated Icosidodecahedron Museum (TIM) consists on successively joining custom platforms using the geometry of the triangular faces of the TI. Only two custom platforms have been de ned: i) looking outside of the TI and, ii) looking inside it. The platforms are built based on the icosidodecahedron's geometry, i.e. it generates a TI if twenty platforms were chosen. The user can select a series of parameters, such as the number of faces, the seed, connection mode between them and if the pattern can use less faces than the given. Introducing the same pattern and the same seed creates the same scene. A scene, where the user character has the capability for walking through it, is interactively generated.
Each platform of the TIM has three connection bridges as joints between neighbor faces of a TI. The faces neighbor to a face are called border faces. The connection between faces are used as paths. Some faces have not connected all their connecting bridges. These faces are called limit faces whereas all the used faces are called useful faces. We use the limit faces to generate new TIs from there to enlarge the TIM scenario. Figure 2 shows the di erences between kinds of face. This section explains the building of a TI and the problem found during its creation. Subsection 5.1 presents the method to get the useful faces. Subsection 5.2 explains the di erent kinds of face selection. Subsection 5.3 de nes the generation of the TI into the virtual scene. 1. All faces. This list contains useful faces. 2. Available faces. This list contains the faces to get more faces, i.e. it stores the limit faces until the date. It requires a rst face, named inception face, to generate the TI given in the constructor. 3. Inaccessible faces. This list contains the faces which we cannot use.
Firstly, the inception face is added in \available faces" . Immediately a face is got from \available faces" as limit face. Then get the border faces to the limit face. If any of these border faces has already been used or it is contained on \inaccessible faces", it is refused. Then, get one of the accessible border faces and add it to \all faces" and \available faces". The process checks then the bu er of \available faces" removing all completed faces. This process is repeated until the size of \all faces" bu er is the same as the number of provided faces. If any face collides, the face is added into \inaccessible faces" bu er before the rebuilt process. 5.2
There are three di erent modes to connect a face with its border faces. All modes repeat the same process but the condition to select the next face to connect di ers between them.
{ Random mode. This mode takes a random face from the bu er of \available faces\. This face is used as limit face. Then get a random face from the border faces of this limit face. At the end, this face is checked and added to the bu ers \all faces" and \available faces". { Full mode. This mode takes the rst face of \available faces" as limit face.
Then get the rst face of its border faces. Once this face is checked, it is added to the bu ers of \all faces" and \available faces". After the clean process, if all border face of this limit face was added, this limit face was erased from \available faces" and take the rst face of \available faces"as limit face. If the new limit face has not got border faces, the algorithm takes a random face of \ available faces" as limit face. { Linear mode. At rst, this mode randomly takes a face from \available faces". Then get one border face. It is checked and added to \all faces" and \available faces". Finally, instead of taking a face from \available faces", take the last face added as limit face, and repeat the process. If this border face has not got border faces, the algorithm take one as limit face from \available faces".
In every mode, the bu er of \available faces" is cleaned at the end of each iteration. This process consist on removing the completed faces. 5.3
This section shows the generation of a TI in the virtual space. First of all, the algorithm requires the following parameters: { Inception face. First platform to generate a TI. A platform is the representation of a face. In the rst TI the algorithm gets a random number for selecting an inception face and zero to border face. { Blocked face. Platform that cannot be used. { Bu er of \all faces". { Face mode. Our proposal presents two di erent alternatives (see Figure 4).
The rst one (outside face) is used for walking outside the TI. In the other hand (inside face) is used for traveling inside the TI.
The process to generate a TI is represented in Algorithm 1. A platform is understood as the representation of a face.
Algorithm 1 Generation of TI faces in virtual space. 1: procedure PutFaces(pathList) 2: for all f aces do 3: if f aceM ode = 0 then 4: Create face with platform "FaceOutside" 5: else 6: Create face with platform "FaceInside" 7: end if 8: Add plattform to TI 9: ChangeLocalP osition(idF ace; platf orm) 10: ChangeLocalRotation(idF ace; platf orm) 11: end for 12: end procedure
The algorithm instantiates the custom platform given the face mode and this process is repeated for each face from \all faces" bu er. Each platform requires the local position and rotation to place itself in the right position. These parameters are pre-calculated to make the process faster.
To generate a path in the museum, rstly a TI is created regarding the user patterns as shown above. This is added into the \available TIs" bu er. Then, the algorithm follows the next steps: i) generating all possible TIs, ii) checking the new TI generated, iii) rebuilding the collided objects, and iv) repairing inaccessible paths. The algorithm stops when the \available TIs" bu er is empty. The sequence of creation a path from a TI is explained in next subsections. The number of platforms varies depending on the user patterns. Some of these platforms have not connections with others. We use the limit platforms to generate new TIs and connect them. The parameters required to generate a new TI child are the number of faces of the new object, the connection mode and the condition if the path generated can be lower than the number of faces. First of all, the faces in available faces from TI are used as limit face to generate new unions. For each face from this bu er, its border faces are calculated. The border faces are needed for two reasons. First, the border face of the TI father is the dual face of the border face of the inception face from the new TI. It means that the border face of the new TI uses the connecting bridge to join both TIs. For this reason, this border face is removed from the border faces to avoid a collision. Second, the border faces are needed to know the where the connecting bridge is to position the new TI.
Next, the algorithm calculates the center position for the new object. The midpoint method is used for calculating the new center. As we explained in
Section 3, every face has an opposite symmetrical face. Thus, the algorithm uses the connecting bridge position between the two objects as the middle point. The algorithm applies the following equation to get the new center:
Centerchild = P ositionbridge 2
Centerfather (4)
The new generated object is added into the TI list to check the bu er. Then, if all unions of the TI have been generated, the object is saved into the \full TI" bu er. If some of the unions cannot generate a new object (Section 7 explains the reason), the object is added to the border list. This process is repeated for each TI into the \available TIs" bu er. 6.3
We use a convex mesh around the platform (see Fig. 6) to avoid platform intersection. A ghost layer component is created for each platform. When a collision is detected, this component evaluates the latest created platform and selects which one has to be destroyed. At the end, if the platform is not destroyed, its ghost layer component is deleted. The algorithm has the following steps: 1. The collider detects a collision. If the collided platform has not a ghost layer component and it is not part of the TI father, it is marked to be destroyed. 2. If the collided platform has a ghost layer component, it is evaluated if its identi er is higher. If its identi er is lower, it is added to the collision list. 3. Before destroying the platform, the collision list is checked it. If there is any platform in the list, it is destroyed. If not, the platform remains without destroying.
The collision detection process automatically starts when a platform is instantiated. If the platform has to be destroyed, a message is sent to the kernel process. This message contains the collided TI and the destroyed face. This face is saved into the \inaccessible faces" bu er and a new TI is rebuilt with this constraint.
This process is run when a platform of a TI is destroyed. Then, the algorithm creates another TI avoiding the face corresponding to the platform taking into account the number of useful faces enabled by the user patterns. Nevertheless, if the inception face has collided, this TI is destroyed. 6.5
The repair of a TI is required when some unions can not be generated, due to a TI destruction. This process consists on replacing the connecting bridge with a wall. When the platform is repaired, the collider is replaced with another one, which best matches into the mesh taking into account the connecting bridges destroyed. 6.6
A TI can be technically understood as a simpli cation of a sphere. This idea is used to generate an adaptable physics system. While the user walks trough the TI, the force is calculated using the Newton's universal gravitational constant (see Fig. 7). When the user walks outside the object, the force pulls the user to the center of the object, allowing to the user walks over the sphere surface. If the user walks inside, the force pushes the user from the center. The player system detects the mode and changes the direction of the force when it is necessary. The representation space has been voxelized. Each voxel has the size of a TI storing the data that represents it. When the user character is moved, the cubes ot TIs, which have not to be represented, are saved with all its content to provide persistence. A map, where the key is the center of the voxel and the content is a list with all TI data, is used to accelerate the process.
In addition, the voxelization has other uses, like limiting the generation of TIs. The cube, where a TI is represented, is divided in three parts in all axis (see Fig. 8). Each one of the subcubes is a voxel to get faster memory accesses. When the user character walks and passes to other voxel, the system accesses memory only using the following nine cubes (instead of accessing the whole memory). This division also places the user in the center of the voxel seeing the existing objects in every direction. We test our proposal using a Intel i7-3630QM CPU laptop with a Nvida 660GTXM and 16Gb DDR3 RAM. The application has been developed by using the game engine Unity3D v4.6.2f1[3] to enable running it in any platform, like Windows, Mac, Linux, mobile or web. The user can walk over the scene speci ed regarding its own patterns by using the custom physics and sound steps, like if the user is inside of a museum. Figures 10 and 11 show examples of the scene created at the same time that is gone over. This work can be downloaded and tested in https://dl.dropboxusercontent.com/u/697729/TIM/Index.html.
To evaluate its performance, we have created a custom pattern and a speci c tour to allow us to replicate the scene. We run the same testbed 7 times obtaining the Fig. 12.
Figure 12 is divided in six columns, which correspond to di erent steps of path generation. As we can see, the standard deviation is low, ensuring a similar behavior in di erent runnings. Regarding performance, the collision detection phase requires most of the time. This is due to the Unity's collision system requires three internal loops to evaluate collision and destruction. Finally, we test the GPU vs CPU performance. We test di erent scenes, but the time using GPU is very similar to use CPU. 9
This paper presents a novel technique to procedurally generate a hypermuseum from a TI. It could be adapted to generate any kind of scene. The user walks into an in nite procedural 3D scene created at the same time that it is gone over. This kind of generation presents a new point of view to understand hypermuseums. Additionally, we have created a panel to make user access easy to speci c rooms. Thus, the user can select the room which would like to visit to teleport there.
As future work, we are planning to improve the collision detection system or create a custom one. Furthermore, we plan to adapt other kinds of gures to work, making more complex scenes and better adapted to the user needs, e.g to add the possibility of using for game scenarios. Finally, we plan to integrate procedural artworks.
Acknowledgments Thanks to Hector Zapata, CEO of Tetravol S.L., to propose this as work as a Master's Thesis and TI platforms.
Unity 3D. Unity 3d engine. http://unity3d.com/.