Yukiko Kenmochi

Lilian Buzer

Akihiro Sugimoto

Ikuko Shimizu

Discrete plane segmentation and estimation from a point cloud using local geometric patterns

Keywords: Image segmentation, discrete geometry, planar surface

This paper presents a method for segmenting a 3D point cloud into planar surfaces using recently obtained discretegeometry results. In discrete geometry, a discrete plane is defined as a set of grid points lying between two parallel planes with a small distance, called thickness. Contrarily to the continuous case, there exist a finite number of local geometric patterns (LGPs) appearing on discrete planes. Moreover, such a LGP does not possess the unique normal vector but a set of normal vectors. By using those LGP properties, we first reject non-linear points from a point cloud, and then classify non-rejected points whose LGPs can have common normal vectors into a planar-surface-point set. From each segmented point set, we also estimate parameters of a discrete plane by minimizing its thickness.

Introduction

Recent progress of computer vision technologies allows us to easily acquire a 3D point cloud of an object [1] . Let us consider a simple case where our interesting object is polyhedral. Then, reconstructing the whole 3D shape using several 3D point clouds taken from different viewpoints requires extracting at least three common planar patches from every 3D point cloud [START_REF] Shum | Principal component analysis with missing data and its application to polyhedral object modeling[END_REF] . This extraction is known as surface segmentation.

Conventional approaches for the surface segmentation problem of a 3D point cloud are classified into the following three categories: region-based, edge-based, and hybrid approaches. The first one merges points that have similar region properties calculated from their neighboring points such as normal vectors [START_REF] Papaioannou | Segmentation and surface characterization of arbitrary 3D meshes for object reconstruction and recognition[END_REF][START_REF] Taylor | Robust range data segmentation using geometric primitives for robotics applications[END_REF] , curvatures [START_REF] Besl | Segmentation through variable-order surface fitting[END_REF] parameters of fitted planes [START_REF] Faugeras | Segmentation of range data into planar and quadric patches[END_REF][START_REF] Cohen-Steiner | Variational shape approximation[END_REF][START_REF] Hoover | An experimental comparison of range image segmentation algorithms[END_REF] or quadratic surfaces [START_REF] Faugeras | Segmentation of range data into planar and quadric patches[END_REF][START_REF] Marshall | Robust segmentation of primitives from range data in the presence of gemetric degeneracy[END_REF] , and other indices corresponding to local surface shapes [START_REF] Chen | 3D free-form object recognition in range images using local surface patches[END_REF] . As calculated properties are very sensitive to noise and quantization errors, they cause over segmentation results [START_REF] Haris | Hybrid image segmentation using watersheds and fast region merging[END_REF] . Thus, an additional procedure for merging regions is needed after the initial segmentation [START_REF] Haris | Hybrid image segmentation using watersheds and fast region merging[END_REF][START_REF] Köster | MIR: an approach to robust clustering -application to range image segmentation[END_REF] . In the second approach, edges are searched such that they separate regions by using depth discontinuities [START_REF] Zhao | Range-data-based object surface segmentation via edges and critical points[END_REF] . As edges are not always extracted as connected curves, they cause under segmentation, contrary to the first one. Thus, in this case, an additional procedure for splitting regions is needed after the initial segmentation. The third approach is hybrid between the above two approaches, namely, combinations of region-based and edge-based approaches [START_REF] Haris | Hybrid image segmentation using watersheds and fast region merging[END_REF][START_REF] Stamos | 3D model construction using range and image data[END_REF][START_REF] Yokoya | Range image segmentation based on differential geometry: a hybrid approach[END_REF] . One of interesting ideas for planar cases in the third approach can be found in [START_REF] Stamos | 3D model construction using range and image data[END_REF] ; the notion of locally planar points are proposed for a planar segmentation method. Locally planar points are used *Corresponding author. E-mail address: y.kenmochi@esiee.fr; Address: Laboratoire A2SI, ESIEE, Cité Descartes, BP 99, 93162 Noisyle-Grand Cedex, France; Fax: +33.1.45.92.66.99 for detecting not only planar regions but also edges, because points that are not locally planar are considered to be potentially edge points.

The above three approaches possess the common problem of using surface primitives or geometric features for the surface segmentation. In order to approximate/select surface primitives and calculate geometric features from 3D discrete points, we are obligated to set parameters from the practical point of view. Such parameter setting/adaptation is not simple work, because it depends on the discreteness of a given 3D point cloud, such as data resolution and noise. For example, we need to define a set of neighboring points for calculating geometric features for each 3D point. Note that, in this paper, a set of neighboring points in a 3D point cloud is also called a locally geometric pattern, abbreviated to an LGP. The sizes and patterns of LGPs implicitly give influences to other parameter values in the post-process of region merging/splitting, because calculated geometric features generally have some errors due to various patterns of LGPs. However, in most cases, such parameter adaption is realized experimentally or statistically with some statistical hypothesis. In this paper, simplifying the surface segmentation problem by focusing only on planar cases, we present a new method for planar surface segmentation of a 3D point cloud using recently obtained discrete-geometry results [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF] . The discrete geometry enables us to eliminate many unnecessary parameters and to simplify the planar surface segmentation algorithm.

We present a discrete version of the hybrid method, in this paper, by using fixed-size LGPs in a discrete space. As a consequence, once we fix the size, it automatically decides other parameter values thanks to the theory of discrete geometry [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF] . In discrete geometry, a discrete plane is defined as a set of grid points lying between two parallel planes with a small distance, called a thickness [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF] . Contrarily to the continuous case, there exist a finite number of local geomet-ric patterns, LGPs, appearing on discrete planes, called linear LGP [START_REF] Kenmochi | Digital planar surface detection using local geometric patterns. submitted to Processings of Discrete Geometry for Computer Imagery[END_REF] . In fact, points whose LGPs are linear can be considered to be discrete version of locally planar points [START_REF] Stamos | 3D model construction using range and image data[END_REF] . In addition, each linear LGP does not possess the unique normal vector but a set of normal vectors [START_REF] Coeurjolly | On digital plane preimage structure[END_REF] . By using those LGP properties, we present a segmentation method following the two steps: first reject non-linear points from a point cloud (edge-based part), and then merge non-rejected points whose LGPs have common normal vectors (regionbased part). It thus uses only precalculated look-up tables with respect to LGPs, and does not require any parameter setting. Furthermore, our method is less sensitive to noise as well as quantization errors. Indeed linear LGPs already take into account quantization errors for their generation. We show the effectiveness by applying our algorithm to 3D point clouds such as range images. In order to evaluate our segmentation results, we apply a method for estimating discrete plane parameters from each segmented planar surface by minimizing its thickness. This problem is solved by a linear programming method. As the thickness indicates the segmentation inaccuracy, we consider that the thinner the thickness, the better the segmentation result.

2 Non-linear point rejection using LGP

Discrete planes

Let R be the set of real numbers. A plane P in the 3D Euclidean space R 3 is defined by the following expression:

P = {(p, q, r) ∈ R 3 : αp + βq + γr + δ = 0}
where α, β, γ, δ ∈ R. Let Z 3 be the set of grid points whose coordinates are integers in R 3 . A discrete plane, which is a digitization of P, is then defined such that

D(P) = {(p, q, r) ∈ Z 3 : 0 ≤ αp + βq + γr + δ < ω} (1)
where ω = max (|α|, |β|, |γ|), called the thickness [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF] .

Linear LGP on discrete planes

We consider a cubical grid-point set Q(x) whose edge length is 2 around a point x ∈ Z 3 such that

Q(x) = {y ∈ Z 3 : x -y ∞ ≤ 1}. (2)
Let us assume that each point in Z 3 has a binary value such as either 1 or 0. Such a pattern of binary points in Q(x) is called local geometric patterns, abbreviated to LGP. There are 2 26 different LGP for Q(x) providing that the central point x always has the fixed value 1. This indicates that

x is considered not to be a background point but to be a surface point. Among those different LGPs, we investigated which LGP can appear on discrete planes [START_REF] Kenmochi | Digital planar surface detection using local geometric patterns. submitted to Processings of Discrete Geometry for Computer Imagery[END_REF] . This problem is mathematically written as follows. Let F be a set of points whose binary values are 1 in Q(x). If there is a plane P such that

F = D(P) ∩ Q(x) = {(p, q, r) ∈ Q(x) : 0 ≤ αp + βq + γr + δ < ω}, (3)
we say that F forms a discrete plane in Q(x). Therefore, our problem is solved by looking for all possible F, namely LGPs, satisfying (3). Such LGPs are called linear LGPs.

Since this problem is considered to be the feasibility of the inequalities of (3) for all (p, q, r) ∈ F, we need to check if there are feasible solutions α, β, γ, δ for each different LGP of Q(x). If they exist, such LGP can appear on discrete planes and become linear LGP. However, [START_REF] Kenmochi | Digital planar surface detection using local geometric patterns. submitted to Processings of Discrete Geometry for Computer Imagery[END_REF] shows that we can avoid computing the feasibility test for all 2 26 LGPs of Q(x), by taking an approach based on arithmetic planes [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF][START_REF] Reveillès | Combinatorial pieces in digital lines and planes[END_REF] , which are related to discrete planes. An algorithm is then proposed to generate all linear LGPs, and it is found that there exist only 34 LGPs that appear on discrete planes, called linear LGPs, up to translations, rotations and symmetries, as shown in Fig. 1. Note that they are generated with the constraints

0 ≤ α ≤ β ≤ 1, γ = 1. ( 4
)
In order to visualize the shapes of linear LGPs in Fig. 1, we add polyhedral meshes generated for planar surface points by applying a discrete-marching-cube-like method for the 18-neighborhood system [START_REF] Kenmochi | Combinatorial boundary of a 3D lattice point set[END_REF] to a digitized half space. Interior points of planar surfaces are designated as black points in the figures.

Locally linear and non-linear points

Experimentally, those linear LGPs can be seen not only on discrete planes but also on discrete smooth surfaces. Intuitively, this is not difficult to understand, since any local surface patch on a smooth surface can be approximated to a planar surface when the size of the patch becomes small. In the discrete space, even if a point has a linear LGP, we are uncertain whether such a point appears on a planar surface or a non-planar surface. Contrarily, if a point has a non-linear LGP, it never appears on a planar surface. From this reason, if a point has a linear LGP, it is called a locally linear point, otherwise, simply called a non-linear point.

From a point cloud to a grid point set

Before executing the non-linear point rejection to a gridpoint set, we explain how to transform a 3D point cloud into a grid-point set. Our input in this paper is a range image represented by a 2D digital image each of whose pixel (x, y) ∈ [X1, X2] × [Y1, Y2] of Z 2 has a depth information d(x, y) from a 3D scanner to an object surface. We transform such a range image into a 3D triple-valued image by re-quantizing a depth d(x, y) as follows: for each point (x, y, z) in a finite subset

X = [X1, X2] × [Y1, Y2] × [Z1, Z2] of Z 3 , we define a triple-valued function such that t(x, y, z) =      2, if z = ⌊ d(x,y) r + 1 2 ⌋, 1, if z > ⌊ d(x,y) r + 1 2 ⌋, 0, otherwise, ( 5
)
where r is a sampling interval for depths.

Grid points whose values are 2 are closest to input points (x, y, d(x, y)) so that they are considered to be discrete surface points and to be visible from a 3D scanner. Thus, we call them visible surface points and define a set of visible surface points such that

V = {(x, y, z) ∈ X : t(x, y, z) = 2}. (6)
Concerning grid points whose values are 1, they are invisible from a 3D scanner so that we do not know whether they are surface points or not. Therefore, we simply call them invisible points. Since the rest of grid points whose values are 0 are visible and background points, a set of potential points for an object is defined as a union of visible surface points and invisible points such that

W = {(x, y, z) ∈ X : t(x, y, z) = 0}.
Thus, a set of surface points is obtained as a border point set of W such that

∂W = {x ∈ X : N6(x) ∩ W = ∅} (7)
where

N6(x) = {y ∈ Z 3 x -y 1 ≤ 1}
and W is the complement of W. Note that V ⊆ ∂W and the equality does not always hold. A visible surface point set V can be considered to be a digitization of a point cloud, while a surface point set ∂W is necessary for making binary patterns of LGPs; the binary value of a point x is set to be 1 if x ∈ ∂W; otherwise, set to be 0. This is why we also need ∂W as well as V.

Non-linear point rejection

By simply checking the LGP linearity, we can therefore reject non-linear points from a grid-point set, since we know that non-linear points never appear on any discrete plane. In other words, the linear LGPs play an important role in filtering linear points. Note that it is realized by looking up the binary table of LGPs (linear or not).

For the experiment, we use a 3D point cloud taken by a 3D scanner Konica-Minolta VIVID 910 with a resolution 320 × 240. We first re-quantized the z-coordinates with a similar interval r to those of the x-and y-coordinates from (5), and obtained two finite grid-point sets, namely, a visible surface point set V and a surface point set ∂W, from ( 6) and (7). Note that the LGP linearity is checked for every point in V even if binary patterns for LGPs are made from ∂W.

Figure 2 shows an example of locally linear and non-linear points, colored in light green and black respectively, in a 3D point cloud taken by a 3D scanner Konica-Minolta VIVID 910 with a resolution 320 × 240. We see in the figure that points appearing around polyhedral-face edges are rejected as well as isolated points that are considered to be noise. However, we also observe that some points around edges are not rejected, because they are considered to be locally linear even if they are not linear in a larger region than their

LGPs. This fact implies that a simple post-processing, such as the connected component labeling [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF] of a non-rejected point set, does not always give satisfactory results for planar surface segmentation.

In fact, we can generalize the definition of a cubical gridpoint set Q(x) with an infinity norm that is not more than k, instead of 1, in (2) [START_REF] Kenmochi | Digital planar surface detection using local geometric patterns. submitted to Processings of Discrete Geometry for Computer Imagery[END_REF] . If k = 2, for example, we obtain 1574 linear LGPs. However, larger LGPs are not so useful for the non-linear point rejection. First, they are more sensitive to noise because each point need more neighboring points to be locally linear. Therefore, we generally obtain more black points in Fig. 2 if we use larger LGPs. Secondly, from the practical point of view, we lose a privilege to use a binary look-up table for checking the LGP linearity, because of the size of all binary patterns of LGPs. In the cases where k is more than 1, we need to use another data structure such as a tree to store all linear LGPs and to check the linearity of a given LGP. Because of these reasons, we use LGPs for k = 1 in this paper.

Planar surface segmentation of locally linear points

In order to solve our segmentation problem, we propose a method using not only the point connectedness but normal vectors derived from LGPs.

Feasible normal vectors of linear LGPs

A linear LGP is a discrete plane patch of D(P) in a bounded space Q(x), denoted by D Q(x) (P). Given a D Q(x) (P), we can find a set of Euclidean planes P such that the digitization of each of those planes in Q(x) is equal to D Q(x) (P). The set of all such Euclidean planes is called the preimage and it is known that the correspondence between discrete plane patches and Euclidean planes is not one-toone but one-to-many [START_REF] Coeurjolly | On digital plane preimage structure[END_REF] . Because of the one-to-many correspondence, the preimage of D Q(x) (P) is represented by a set of parameters α, β, γ, δ. More precisely, the preimage is obtained as a feasible solution set of the inequality set of (3) for all points (p, q, r) ∈ D Q(x) (P). It means that the preimage is given by a convex polytope in the parameter space [START_REF] Coeurjolly | On digital plane preimage structure[END_REF] .

As all interesting parameters in this paper are translation-invariant, we focus on the three parameters α, β, γ indicating the normal vector of P, distinguished from the intercept δ of P. We thus apply the Fourier-Motzkin elimination [START_REF] Ziegler | Lectures on Polytopes[END_REF] to the inequality set of (3) for all (p, q, r) ∈ D Q(x) (P), so that a set of feasible normal vectors is calculated from each linear LGP. Remark that all calculations are done by using only integers, i.e., they cause no rounding errors; the details are found in [START_REF] Kenmochi | Digital planar surface detection using local geometric patterns. submitted to Processings of Discrete Geometry for Computer Imagery[END_REF] .

The results are derived in the space (α, β) from linear LGP with the constraints (4), since we use the 34 linear LGPs in Fig. 1. The feasible region for each linear LGP is obtained as a convex polygon in the triangle region whose vertices are (0, 0), (0, 1) and (1, 1) of the space (α, β) because of (4). Each line in the triangle region in Fig. 3 corresponds to a half plane represented by each inequality of (3) for every (p, q, r) ∈ D Q(x) (P) for every linear LGP. We see in Fig. 3 that the inequality set divides the trian- LGP is given as a set of normal cells that constitutes a convex polygon in the space (α, β). Table 1 shows the set of normal cells whose union corresponds to the convex polygon representing the set of feasible normal vectors for each linear LGP depicted in Fig. 1. Remark that there are some pairs of linear LGPs both of which have the identical set of normal cells. In addition, a normal cell corresponds not only to a simple linear LGP but to several linear LGPs. Thus, the correspondence between linear LGPs and normal cells is many-to-many.

Discrete Gaussian sphere

The 26 normal cells in Fig. 3 are generated with the constraints (4). We embed these normal cells into the 3D space (α, β, γ) with γ = 1, as illustrated in Fig. 4. The triangle surrounded by thick lines in Fig. 4 corresponds to the triangular region that is the union of normal cells in Fig. 3. Once the normal cells are embedded into the space (α, β, γ), we make the congruous ones by applying to them 48 transformations of rotations and symmetries of a cube of edge length 2, centered at the origin of the 3D space. We see, in Fig. 4, that there are the 48 triangles on the cube, so that the whole cube contains 1248 normal cells. Such a cube is called the cubical Gaussian sphere.

We now project normal cells tiled on the cubical Gaussian sphere onto a unit sphere centered at the origin, as illustrated in Fig. 5. The unit sphere separated by projected normal cells is called the discrete Gaussian sphere,

because the size of normal cells indicates the resolution of digitized normal vectors calculated from linear

LGPs. The triangle surrounded by red lines in Fig. 5 corresponds to the triangle surrounded by thick lines in Fig. 4 that corresponds to the union of normal cells in Fig. 3. In the remainder, we denote G the set of all normal cells on the discrete Gaussian sphere. Remark that we use only integer or rational numbers to calculate all normal cells, which are related to the cubical Gaussian sphere.

Unified discrete Gaussian image

By using the discrete Gaussian sphere, we give a discrete version of extended Gaussian images that are useful for representing surface shapes [START_REF] Horn | Extended Gaussian images[END_REF] , called unified discrete Gaussian images. Let us first consider a discrete version of the Gaussian image that is the mapping from an object surface point to its normal vector on the Gaussian sphere. Let V ′ be a locally linear point set in Z 3 . For a point x ∈ V ′ , we define a discrete Gaussian image I(x) as the set of normal cells corresponding to the linear LGP of x. Choosing a normal cell c ∈ G, we now consider a point subset of

V ′ such that R(c) = {x ∈ V ′ : c ∈ I(x)}. (8)
We then obtain the number of points in R(c) for every c ∈ G, called the unified discrete Gaussian image, such that

u(c) = |R(c)|. (9)
Note that u(c) and R(c) are generated by simply looking up a table such as Table 1. The concept of unified discrete Gaussian images is similar to that of extended Gaussian images [START_REF] Horn | Extended Gaussian images[END_REF] . The differences from extended Gaussian images are the followings: the function ( 9) is defined with respect to a normal cell c on the discrete Gaussian sphere G, instead of a point n on the Gaussian sphere; the value of ( 9) is the number of grid points x such that I(x) includes c, instead of the area of the surface whose normal vector is n. From the definition, we see that our unified discrete Gaussian image represents a distribution of normal cells of a digital object surface. Figure 6 shows an example of the unified discrete Gaussian images for a digitized box. Concerning cell colors on the discrete Gaussian sphere in Fig. 6 (bottom), the darker the blue cell, the larger the value of u(c), and the red cell has the maximum value. The length of the pale blue needle for each cell c also corresponds to the value of u(c). On a digitized box in Fig. 6 (top), red and blue points are locally linear, while green points are non-linear. Note that red points correspond to the red cell in Fig. 6 (bottom). Figure 6 shows that we can extract a set of grid points that belong to a digital plane D(P) by choosing a "correct" normal cell, for example, a red one. This is based on the following fact;

Algorithm

By using the unified discrete Gaussian image u(c) and the point sets R(c), we present our algorithm for planar surface segmentation from a locally linear point set V ′ . Our problem is formulated as follows; each point x ∈ V ′ is assigned into one of sets Si for i = 1, 2, . . . such that the points in each Si constitutes a connected planar-surface set. From the previous discussions, our method is founded on the following hypothesis: if there is a connected point subset S ⊆ V ′ such that they have a common normal cell for all x ∈ S, S may constitute a discrete plane.

Based on this hypothesis, we present Algorithm 1. we look for the largest connected grid-point set Si, whose points having a common normal cell by using u(c) and R(c).

As each point has several normal cells, our method cannot be processed in parallel with respect to normal cells. It must be a repeated procedure; once we obtain Si, we remove all points of Si from every R(c), modify u(c), and repeat this procedure after the increment of i. Practically, we would like to avoid obtaining a very small surface patch, so that we set a parameter s that is the minimum size for Si.

Algorithm 1 is thus a loop procedure of seeking planar surfaces Si. Each Si is a maximally connected point set, whose points have a common normal cell. Once we find Si, we check the size of Si in Step 11, and if |Si| ≥ s, we remove all points of Si from every R(c) and also modify u(c) in Step 13. After such modification and incrementing i, we seek a new Si. For finding each Si, we look for the maximum connected component C of each R(c), and then set Si to be the maximum among all C. In order to reduce the frequency of calculation of connected components, which is a global operation, we make a priority queue D k of normal cells with u(c) in Step 4. We then repeat dequeue of a normal cell h from D k to obtain the maximum connected component C of R(h) in Step 8. Comparing the size of C with the maximum among those of other normal cells that are already dequeued from D k , we finally obtain the currently maximum point set S l in Step 9. Note that this loop is repeated until the size of R(h) is less than s or more than the size of S l as described in Step 7. For calculating the maximum connected component of R(h), we apply a simple method based on a depth-first strategy by using a queue [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF] . The time complexity is linear with respect to the size of R(h).

Experimental results

For the experiment, we used six range images of the same blocks, which are taken by a 3D scanner Konica-Minolta VIVID 910 from two different viewpoints with three different resolutions. The range images were transformed into grid-point sets by following the explanation in Subsection 2.4. First, we rejected all non-linear points, as described in Section 2, and then applied Algorithm 1. The results are illustrated in Figs. 7 and8. In the cases of Fig. 7, the numbers of valid (measured) points are 207459 for (a), 51739 for (b) and 12859 for (c). Among those valid points, we have 184682 locally linear points for (a), 47093 for (b), and 11346 for (c), respectively. Similarly, in the cases of Fig. 8, the numbers of valid (measured) points are 195768 for (d), 48797 for (e) and 12139 for (f). Among those valid points, we have 176697 locally linear points for (d), 44266 for (e), and 10676 for (f), respectively. Tables 2 and3 show the number of locally linear points that are assigned to each segmented planar surface, and their corresponding color in Figs. 7 and8. We see that 13, 12 and 13 planar surfaces are found in Fig. 7 (a), (b) and (c), and 13, 10 and 13 planar surfaces are found in Fig. 8 (d), (e) and (f), respectively.

We see in Figs. 7 and8 that non-linear points, colored in light green, appear around edges of block faces, and sometimes appear in faces because of small bumps in faces or noise in the range images. As we set the minimum surface size s, there are locally linear points that construct no planar surface whose size is not less than s around the points, colored in black in the figures. Note that we use 2D connected component labeling in Algorithm 1, instead of 3D connected component labeling, because locally linear points are sparsely distributed in the 3D space, but not in the 2D space.

There are physically 12 visible planar surfaces in Fig. 7 and 10 in Fig. 8; there are actually 11 planes in Fig. 7 because a table face is separated into two parts with a right cube. Figures 7 and8 and Tables 2 and3 show that all planar surfaces are segmented by our simple algorithm, which require neither complicated parameter setting nor parameter estimation. We should mention that it may bring us rather over-segmentation results when the resolution of an input image is high. For example, the orange and cream points in Fig. 7 (a) (resp. the pale blue and violet points in Fig. 8 (d)) should be considered to be in the same region, even if they are separately segmented. We also see that our method is less sensitive to image noise in lower image resolutions; for example, in Fig. 7 (a), there do not exist many linear points on the left cubic face colored in moss green, while more olive and turquoise points are found in Figs.

(b) and (c).

As we discussed in Subsection 2.5, we can use largersize LGPs for the planar surface segmentation. If we use lager-size LGPs, then we will have more normal cells on the discrete Gaussian sphere [START_REF] Kenmochi | Digital planar surface detection using local geometric patterns. submitted to Processings of Discrete Geometry for Computer Imagery[END_REF] . This means that each normal cell becomes relatively small so that we can see smaller differences between normal vectors for their distinction. However, we may have a risk of obtaining over-segmentation results. Furthermore, as mentioned before, there are other problems such as obtaining less locally linear points because larger LGPs are more sensitive to noise, and finding a good data structure.

Estimation of discrete plane parameters

Formulation

From each segmented planar-surface set Si, we estimate its discrete-plane parameters. In this paper, we treat the problem as an linear programming problem. The similar method for the recognition of blurred discrete plane patches can be found in [START_REF] Provot | Recognition of blurred pieces of discrete planes[END_REF] .

In order to simplify our problem, we first consider the case that ω = |γ|. From (1), we obtain a linear inequality set such that, for all (x, y, z) ∈ Si,

0 ≤ α ′ x + β ′ y + z + δ ′ ≤ ǫ (10)
where

α ′ = α ω , β ′ = β ω , δ ′ = δ ω .
Note that we derive the constraints

-1 ≤ α ′ ≤ 1, -1 ≤ β ′ ≤ 1
from these substitutes. We have another constraint ǫ ≥ 0; if ǫ < 1, the above inequalities are the same as (1). A solution set (α ′ , β ′ , δ ′ ) is then obtained by minimizing ǫ under the above constraints. In this framework, if we find a minimum where ǫ < 1, Si is recognized as a discrete plane patch exactly; otherwise, Si is recognized as a set of gridpoints between two parallel planes whose distance is wider than the thickness of a discrete plane. Geometrically, our method looks for two parallel planes such that the z-axial distance between them becomes minimum.

For all the other cases such that ω = |β|, |α|, we simply need to modify (10), so that the following inequalities are obtained respectively

0 ≤ α ′ x + y + γ ′ z + δ ′ ≤ ǫ, 0 ≤ x + β ′ y + γ ′ z + δ ′ ≤ ǫ where γ ′ = γ ω .
From this substitute, we also derive -1 ≤ γ ′ ≤ 1.

Practically, we simultaneously use the above 3 types of inequality sets to find a parameter set by minimizing ǫ.

Experimental results

We used a free linear programming solver, lp_solve [24] , for our experiments. Tables 4 and5 show the estimation results for segmented planar surfaces obtained in the previous section, as illustrated in Figs. 7 and8. Note that we set ω = 1, so that we have α = α ′ , β = β ′ , and γ = γ ′ .

We first see that the parameter values of α, β and γ that are obtained for the corresponding planar surfaces, segmented from the range images with different resolutions, are very similar. For example, the first (resp. second) planes in Table 4 From Tables 4 and5, we also see that it is rare that ǫ becomes less than 1, specially when the image resolution is high. In other words, our segmented planar surfaces can be exactly discrete planes, when the resolution becomes lower. The tables show that the higher the image resolution, the larger the value ǫ. Since each segmented planar surface contains many grid points when the image resolution is high, as seen in Table 2, it can generate a thicker discrete plane. Figure 9 illustrates the estimated discrete plane with a minimum thickness, namely, the two parallel planes with a minimum distance, for each segmented point set in Fig. 7. In Fig. 9, we see that there is no isolated point in any segmented point set, thanks to the non-linear point rejection and the connected component labeling in Algorithm 1. Therefore, the thickness may be related to the surface curvedness of a segmented point set, as well as the shape and the size. It might be interesting to study how we can reduce the thickness ǫ by changing the image resolution, for the aim of inventing a multiscale method for range image registration by using planar surfaces, for example.

Conclusion

In this paper, we present a discrete version of the hybrid method for planar surface segmentation from a 3D gridpoint set. Our method simply requires two types of look-up tables, such as the binary LGP table (linear or non-linear) and the normal cell list with respect to each linear LGP, and does not require any parameter setting/estimation. The experimental results in Figs. 7 and8 show us that our method is useful for planar surface segmentation from a point cloud, because it takes into account not only quantization errors but also noise. We also present a method for estimating discrete-plane parameters, which is also based on discrete geometry. Theoretically, exact discrete planes must be obtained if input is an ideal image, i.e., it does not contain noise, but contains only quantization errors. However, our estimation results in Tables 4 and5 show us that exact discrete planes are rarely obtained for practical images. This is because input images contain noise as well as quantization errors. Therefore, we need to eliminate such noise, for example, by reducing image resolutions, before applying our method based on discrete geometry. As our method is fully discrete and such discreteness may help us to build up a multiscale approach, we will reorient our future work to inventing a multiscale method for range image registration by using discrete planes, for example. We expect that our approach will provide a rough registration result with less computation.

Figure 1

 1 Figure 1 The 34 linear LGPs.

Figure 2

 2 Figure 2 An experimental example of non-linear point rejection.

Figure 3

 3 Figure 3 Normal cells on the αβ-plane with constraint (4).

Figure 4 Figure 5

 45 Figure 4 The cubical Gaussian sphere.

Figure 6 A

 6 Figure 6 A synthetic 3D image of a box (top) and its unified discrete Gaussian image (bottom).

Algorithm 1 : 14 return

 114 Planar surface segmentation input : a unified discrete Gaussian image u(c), point sets R(c), and a minimum surface size s output: planar-surface point sets Si for i = 1, 2, 3, . . . begin 1 initialize a label such that l = 0; 2 repeat 3 make a queue D k of normal cells with priorities 4 of values u(c); increment l and initialize S l = ∅; 5 set h to be the highest priority cell in D k and 6 remove it from D k ; while |R(h)| > max(s -1, |S l |) do 7 set C to be the maximum connected 8 component of R(h); if |C| > |S l | then set S l = C; 9 reset h to be the highest priority normal 10 cell in D k and remove it from D k ; if |S l | ≥ s then 11 forall c such that u(c) = 0 and 12 R(c) ∩ S l = ∅ do reset R(c) = R(c) \ S l and 13 u(c) = |R(c)|; until |S l | < s; Si for i = 1, 2, . . . , l -1; 15 end 16 if (α, β, γ) is a normal vector of D(P), (α, β, γ) is included in the common normal cell(s) of I(x) for all x ∈ D(P).

Figure 7

 7 Figure 7 Planar surface segmentation results from range images of blocks, which are taken from the same viewpoint, with different resolutions: the image sizes are 640 × 480 (a), 320 × 240 (b), and 640 × 480 (c). The minimum surfaces sizes s are set to be 1000 (a), 500 (b), and 100 (c), respectively.

Figure 8

 8 Figure 8 Planar surface segmentation results from range images of blocks, which are taken from a different viewpoint from that in Fig. 7, with different resolutions: the image sizes are 640 × 480 (d), 320 × 240 (e), 160 × 120 (f). The minimum surfaces sizes s are set to be 1000 (d), 500 (e), and 100 (f), respectively.

  (a), (b) and (c), colored in blue (resp. yellow) in Fig. 4, have similar values of α, β and γ. Concerning to the parameter δ, the values in Tables 4 (a) and 5 (d) (resp. Tables 4 (b) and 5 (e)) are almost four times (resp. twice) as large as those in Tables 4 (c) and 5 (f), respectively. The reason is that the grid space of Figs. 7 (a) and 8 (d) (resp. Figs. 7 (b) and 8 (e)) is four times (resp. twice) as large as that of Figs. 7 (c) and 8 (f), because of their image resolutions. Note that we set the grid interval to be 1 for the parameter estimation.

Figure 9

 9 Figure 9 Estimated two parallel planes with a minimum thickness for each segmented point set in Fig. 7.

Table 1

 1 Linear LGPs and their normal cells.

	linear LGP	normal cells
	1	0 25
	2	1 9 11 12
	3	4 5 7 10 23
	4,5	0 1 16 17 18 24
	6,17	2 3 4 5 7 8
	7	2 3 5 8
	8,9	6 9 10 11 14 15 21 23
	10,12	8 19 20 25
	11	8 17 18 19 20
	13,28	2 3 4 5 6 7 9 10 11 12 13 14 15 21 22 23
	14	2 3 6 13 14 15 16 21 22 24
	15	2 3 6 11 12 13 14 22
	16	4 5 7 10 23
	18,19	0 18 19 25
	20,23	0 1 3 8 12 13 16 17 18 19 20 22 24 25
	21,22	3 8 16 17 20 22
	24,25	1 9 11 12 13 14 15 24
	26,34	2 4 5 6 7 10 21 23
	27	2 5 6 7 21 23
	29,30	0 17 18 19 20 25
	31,32	1 12 13 16 22 24
	33	6 9 11 14 15 21

gle region into triangular or quadrilateral polygons in the space (α, β), called normal cells. The feasible region of each linear

Table 2

 2 Point colors and numbers of segmented planar surfaces in Fig.7.

	color	(a)	(b)	(c)
	1 blue	24649 6755 1770
	2 yellow	19865 6194 1578
	3 pink	17656 5540 1523
	4 pale blue	12724 4655 1191
	5 orange	12092 3097	699
	6 green	10246 2512	573
	7 brown	8974 2253	545
	8 turquoise	4734 1629	536
	9 olive	3787 1517	440
	10 purple	3567	985	248
	11 violet	3484	979	232
	12 moss green	1948	937	223
	13 cream	1734		101

Table 3

 3 Point colors and numbers of segmented planar surfaces in Fig.8.

	color	(d)	(e)	(f)
	1 blue	28053 6814 1850
	2 yellow	21931 6738 1583
	3 pink	15074 4315 1182
	4 pale blue	13414 4245 1161
	5 orange	9981 2994	787
	6 green	9153 2547	604
	7 brown	8905 2409	589
	8 turquoise	8525 2222	542
	9 olive	3689 1139	281
	10 purple	3470	943	218
	11 violet	1852		119
	12 moss green	1386		114
	13 cream	1145		112


Patrice Bouvier
email: bouvier@univ-mlv.fr

François De Sorbier

Pascal Chaudeyrac

Cross benefits between virtual reality and games

Keywords: virtual reality, gaming experience, cross-benefits, immersion, interaction

In one hand, video games are dedicated to entertainment. In recent years, the emerging of consumers hardware dedicated to games induced great progress for realism and gameplay. Graphics rendering and physical engines, digital surround sound and new interaction interfaces are examples of areas which have benefited of these last improvements and widely contribute to the gaming experience.

In another hand, virtual reality focus on user's presence which is its indubitable feeling of belonging to the virtual environment. As this goal is very hard to reach, studies have to focus on human through several research directions like immersion (3D vision, sound spatialization, haptic devices) and interaction which has to be as natural and non intrusive as possible. Recent researches on intersensoriality possibilities, metaphorical interactions or brain computer interfaces are examples of what would be achieved in immersion and interaction.

At this point, we can argue that virtual reality can be a provider of new methods and resources for games. Unfortunately virtual reality room are expensive and difficult to deploy, what is probably the main reasons why virtual reality is still a laboratory experiment or confined to industrial simulator. Here is our double contribution : to combine video games and virtual reality through two different virtual reality game solutions and to design them with consumer grade components. This paper first presents a survey of both current video game evolutions and virtual reality researches.

We will also give some examples of cross-benefits between video games and virtual reality. To illustrate this last point we will describe two virtual reality applications created by our research team and dedicated to gaming. Finally, as a prospective talk we will deal with three points : some recent virtual reality systems supposedly applicable to home gaming, some good points from DG that VR developers should incorporate in VR systems and last point, some lines of enquiry so that the union between VR and DG be at last consummate.

Introduction

Virtual reality (VR) and digital games (DG) are two area which share many similar characteristics among which the three most important are as follows. Both of them have to focus on Human to succeed (feeling of presence for VR, entertainment for DG). VR and DG exploit the technological breakthroughs of several fields like image synthesis, electronics etc. Finally, they both act sometimes in a virtual realistic world like flight simulator or therapy environment [START_REF] Krijn | Virtual reality exposure therapy of anxiety disorders: A review[END_REF]. Other times they allow to operate in a fantasy world which does not necessarily respect usual physical laws.

Similarly, the pitfall to avoid is in common i.e. the race for more and more visual realism. But, firstly it does not guarantee the success of a DG and secondly realism is not the key point for a virtual environment where credibility is sufficient to arouse a feeling of presence. This strong symmetry between VR and DG is the reason why general public is prone to confuse them; though we will see later that the frontier is still here. Moreover, during the eighty's and the ninety's some books (Neuromancer from William Gibson), movies like Tron, Lawnmower and eXistenZ and certain papers or reporting of scientific translation make believe that in the early 2000's it will be very common to wear a HMD and a tactile suit to play DG. In 2008 this expectation is still here. Even if during last decades there was a lot of exchange between VR and DG it's still not possible to play at home to a virtual reality game.

Our contribution, in this paper, is twofold, a presentation of two virtual reality games and some reflections on virtual reality games. We will first propose a rapid historic review on DG and a brief state of the art on VR. Then we will outline some examples of cross-benefits between VR and DG. In a third part we will describe virtual reality applications created by our research team and dedicated to gaming. Finally, as a prospective talk we will deal with three points : some recent virtual reality systems supposedly applicable to home gaming, some good points from DG that VR developers should incorporate in VR systems and last point, some lines of enquiry so that the union between VR and DG be at last consummate.

State of the art

The goal of this section is not to present a complete historical overview on the virtual reality and digital games, which would be out of the scope of this paper, but only the main steps and evolutions.

Digital games

First digital games appeared in the 60s with games like Oxo or Tennis for two [START_REF]The first video game[END_REF]. This latest worked with an oscilloscope and was playable via analogical computers. The first game console produced by Magnavox and called Magnavox Odyssey was created in 1972 for home entertainment. At the same period the Atari company was founded and was at the origin of the world famous game Pong [3].

Since the beginning, games were designed to be played by two people using two paddle controllers or using interfaces like the light gun that enriched the gaming experience. First created for one single game, home game consoles quickly evolved to accept multiple games induced by the coming of several companies like Nintendo or SEGA. They proposed their own consoles with dedicated games.

Once again, Atari innovated, in 1977 with his Atari 2600, by replacing the simple beep by a real sound based on two mono channel.

The first video game with three-dimensional content appeared in the early 80s and was called battlezone. During the following years, games did not stopped their development proposing better graphical content and scenario. For example, games like Super Mario Bros, Final Fantasy, Dune II or Wolfenstein 3D offered new kinds of gameplay.

Examples of 3D stereoscopic games have been released in 1995 and were playable with the Nintendo's Virtual Boy portable console. However most of the players were sick and the console was not very successful.

With the arrival of the Internet in 90s, a new gaming experience is proposed to the players who can play against human distant players into persistent virtual universes. An example of such a game is Ultima online created in 1997.

Gaming interfaces evolved at the same time than the video games' democratization. It exists two categories of interfaces : some dedicated to home gaming and others dedicated to arcade.

Coin-operated entertainment machines have been very popular when they appeared in the middle of the 70s. Their main advantage is that they are dedicated for one-single game. It means that games have better graphical content, and interfaces are related to the gaming context (the player can use a wheel, a weapon,...) and sometimes the machine environment is adapted for a better immersion (decor, vibrations,...).

The first home gaming interfaces were very simple like a small box with a single push button and/or a knurl to decrease the manufacturing cost. Quickly the mouse (1972) and the joystick (1980s) have appeared and became popular because of the better interaction with games. Latter, interfaces that could only be found when playing with coin-operated entertainment machines were available for home gaming (guns, wheels, pad). Currently the tendency is to provide less and less intrusive interfaces in order to increase the gaming experience like the EyeToy [START_REF]Eye Toy[END_REF] (Sony), the Wiimote [START_REF] Ikeda | Game system and storage medium having game program stored thereon[END_REF] (Nintendo), the Gaming amBX [START_REF]Philips amBX PC gaming peripherals[END_REF](Phillips).

Virtual reality

Virtual reality, like digital game takes advantage of several other scientific areas like cognitive science, computer graphics, electronics etc. A reality system aims at immersing one or more users in an artificial environment where he will be able to feel and interact in real-time thanks to sensory-motor interfaces. The experience will have to be credible enough to gull user's senses in order to create, as an ultimate goal, a feeling of presence of the virtual objects, but also a feeling of his self-presence in the virtual environment. This feeling of presence can be achieved relying on five pillar which are immersion, interaction, real-time, emotions and cognitive science. It may be interesting to make clear the function of each pillar. The immersion is the sensory stimulation which permit the perception of the virtual environment and then its comprehension. The interaction enable the user to not remain spectator of the experiment but to act on it. By real-time we mean we have to maintain the coherence of the perception-action loop. The emotions bring by the experience help the user to accept the experiment by distracting his attention from real world environment including the interaction devices and from the shortcomings of the application. The last pillar is the cognitive science which enable to understand (amongst other things) how Human apprehend their environment, that's a very useful point in order to improve the immersion and interaction efficiency.

The application scope of VR are numerous : simulator for the army and the industry, tool for the treatment of phobias, education and culture with the reconstitution of antic site, art etc.

The first VR installation date from 1956, Morton Heiling created the Sensorama [START_REF] Heilig | Sensorama Simulator[END_REF] which enable to live a multi-modal experiment. In 1966 Sutherland presents The sword of Damocles [START_REF] Sutherland | The ultimate display[END_REF] an installation which combine head tracking and Head Mountain Display (HMD) to render a point of view dependant wireframe virtual environment. In 1975, Myron Krueger proposed an installation named Videoplace where the user can use his avatar to interact with a simple virtual environment thanks to a camera. In the middle of the eighty's, Jaron Lanier found VPL the first company which commercialize some equipment dedicated to virtual reality like data gloves and HMDs. The Cave Automatic Virtual Environment [START_REF] Cruz-Nera | The CAVE: audio visual experience automatic virtual environment[END_REF], created in 1992 is composed of a small room of about five square meters where each wall and the ground are screens displaying synchronised images. Then it offers an almost complete visual immersion. At the end of the last century appeared the first autostereoscopic displays which enable a true stereoscopic vision without the use of special glasses.

The virtual reality games

In this section we will try to answer the question "what is the difference between virtual reality game (VRG) and classical digital game ?" Both virtual reality and digital games can work on the five pillars introduced in the 2.2 section but each pillar can be used at different level. For example in VR, immersion level is very high but the emotion level is quite low whereas it's quite the contrary in DG.

As example of VRG we can notice DisneyQuest open in 1998 which was an indoor interactive theme park which contains several VR attractions like Aladdin's Magic Carpet Ride. It's interesting to notice that, all over the world, all that kind of parks have closed due to low attendance. We can also notice that most of VRG only appeared in theme park like Disney or Futuroscope in France. There is also some few examples in game center with arcade video game like Alpine Racer or Aqua Jet which try to bring more realism thanks to more natural interaction devices but, for example, none of them propose stereoscopic vision. In conclusion we can argue that digital game with a high level of immersion and interaction is very uncommon and home VRG is completely missing. Also, we must make mention of serious game which is a VR research study and use DG statecraft but the aim in that case is not entertainment but for example to provide a safe virtual environment dedicated to training, teaching etc. You can find a good overview about serious game here [START_REF] Susi | Serious games -an overview[END_REF].

Cross-benefits

In this section we present some examples of cross-benefits between virtual reality and digital games.

Benefits from virtual reality to games

There are numerous benefits from virtual reality to games essentially because virtual reality is a gathering of multiple scientific domain instead of a single one. These various research area are improved by needs of VR applications. Part of these enhancements generally transit into mass market once the developing cost is reasonable.

For example, computer graphics have beneficed from expectations of simulator applications. Indeed, they need a realistic and real time rendering. This has induced developments of physically-based engine that have been progressively transited in DG (Far Cry, Half-Life 2). Similarly, we can cite, in sound rendering, this research [START_REF] Moeck | Progressive Perceptual Audio Rendering of Complex Scenes, I3D[END_REF] on perceptual audio rendering technology which has been adopted by the game company Infogrames/Atari to improve their game audio engine.

Virtual reality focused research on telepresence [START_REF] Negroponte | Augmentation of human ressources in command and control through multiple media man-machine interaction[END_REF] with applications dedicated to collaborative and distant work quite sooner than the success of massively multiplayer online games. In medical domain, transmission of hight amount of data in short time like video flow is very important.

As Virtual reality is requiring immersive interactivity between the user and the virtual environment, many haptic devices have been developed. Hence, several tools have been designed for DG including vibrating or feedback elements [START_REF] Schmult | Application Areas for a Force-Feedback Joystick[END_REF].

Benefits from games to virtual reality

First VR should thank DG to be at the initiative of numerous improvement in real-time computing. As described in the last section, a digital game is a good provider of emotions (fear, happiness, curiosity...) needed by the fourth pillar. The player has to surpass oneself in order to take up the challenges against himself or other people and, as a consequence, the player motivation and involvement increase.

Currently, games benefit from a good popularity thanks to the young population enthusiasm for entertainment. This popularity has stimulated the creation of cheaper and lighter virtual reality systems that spread out labs. Moreover, now that people are interested in virtual reality, it provides a community that can validate in vivo through the different concepts and interfaces selected for a VR application. At last, the democratization of digital games have led to the creation of various open source libraries like Ogre 3D [START_REF]Ogre3D : open source graphics engine[END_REF] that can facilitate the creation of virtual reality applications also VR libraries are available [START_REF]FreeVR: Virtual Reality Integration Library[END_REF].

Hardware is continuously improved by DG: equipments become quickly highly capable and cheap. At the beginning virtual reality installations were made with specific hardwares like a dedicated graphic card or an expensive video projection systems. Now a virtual reality room can be created using consumer grade components. Many hardware developments designed for games have been reused in research areas because of its simplicity and low cost. For example some virtual reality installations use a the Nintendo Wiimote for interactivity [START_REF] Schou | A Wii Remote, a Game Engine, Five Sensor Bars and a virtual reality theatre[END_REF] or several Sony Playstation 3 to provide a computational cluster [START_REF] Buttari | SCOP3 A Rough Guide to Scientific Computing On the PlayStation[END_REF].

Our two virtual reality games

In this section we present 2 examples of VRG. We made some assumptions about the conception, for example, a low cost immersive system. We will also discuss our belief about these choices.

JIM3D

Jim 3D [START_REF] Bouvier | Immersive visual and audio world in 3D[END_REF] (Interactive game using 3D mosaic) is a classical point and click game inspired from the famous game MYST3 wherein the player can move from scene to scene and in each scene the user have a free 360° rotation viewpoint. To increase the feeling of presence of the player we added some new development.

Using a rendering algorithm based on three cylinders, we are able to create stereoscopic pairs to increase the immersion of the player. The cylinders, which are set on the vertices of an equilateral triangle, represent the scene from slightly different viewpoints. The user is virtually placed at the center of this triangle and two cylinders are selected according to his view direction and associated to his eyes (one image for left eye, the other for the right eye). Besides the visual system, we use a 8speakers-based sound system that surrounds the player which is placed at its center. The playable sounds are either environmental sounds to define the ambiance of the game or spatialized sounds to help the user to localize an object in the scene.

The scenario of the game consists in a series of riddles that the player must resolve to go forward in the game. Thus, interaction metaphors have been designed to help the user to easily interact with the different parts of game. The interactive tools is made of two LEDs that can be placed on one finger of the player : he can use it to rotate the viewpoint using a gesture similar to a catch & drop, and he can activate an action by pointing an object of the scene.

ISSI

The goal of the project ISSI [START_REF] De Sorbier | Conference on Human System Interaction[END_REF] is to create a virtual reality installation similar to a CAVE system. It is composed of several interfaces build with grade consummer components: the display system is made of 4 transparent screens (made with tracing paper), a sensitive carpet to detect the position of the user, a compass placed on the head of the user to detect his orientation and headphone to diffuse a spatialized sound.

In the actual scenario you are playing the role of a prisoner who want to evade from his cell. The choice of a cell for the interactive context has been decided to have a virtual environment that match the size of the installation. Thus, each screen of the installation is nearly a wall of the cell. Moreover, the user's feeling of presence is increased by the situation: a breakout involves stress as the goal is to quickly escape. Then, his attention is completely focuses on the virtual environment rather than the installation or external disturbing information.

To increase presence, visual effects relative to the virtual body, have been added. The first one is an interactive image of the user's personage reflected by a mirror. Thus the user can have an overview of what he looks like according to his position. The second effect is the shadow of the prisoner that moves according to the position of the user. In addition to the increase of the realism of the scene, the user's feeling of presence will be more important as virtual elements interacts with his actions even if they does not help to progress in the scenario.

Critical analysis

The different interactive tools created for these previous VR games have been designed to be the less intrusive as possible. Thus the player is just wearing and using light elements like stereoscopic glasses, sensitive rug, LEDs etc.

Our system have been made with consumer grade components and with home made devices. The main reason is that we are able to control each step of the virtual reality game and propose a low cost (less than 5000€) solution. However we are aware that our installation need some improvement to be used outside of the research domain but, as detailed in the following part, we try to suggest new ways to develop virtual reality games.

Discussion

In this chapter we will present some recent interesting innovations in VR with which we should pretend that's what people will use in virtual reality games in 2015... The second part deals with some futures cross-benefits between VR and DG. Then we will give some lines of enquiry which seem significant to succeed in offering some virtual reality games.

5.1 Some virtual reality innovations that you will not play with... but your children or grandchildren maybe will... The aim of this section is not to denigrate all theses researches which are all very interesting but to point the fact that it could be easy to make people dream by pretending they will soon be able to play with... As example we could notice some research about one of the most important point in VR : how to reproduce the feeling of self-motion ? Here is three interesting solutions among others which enable to physically move in a large space : the VirtuSphere [START_REF] Latypov | The virtusphere[END_REF] which is a sphere which rotates through the motion of the user, CirculaFloor [START_REF] Iwata | CirculaFloor[END_REF] which uses a set of movable tiles and Powered Shoes [START_REF] Iwata | Powered shoes[END_REF] which is a motor-driven roller skates.

Other interesting research concerned the area of the brain machine interface, we can cited the brain computer interface [START_REF] Dornhege | Toward Brain-Computer Interfacing[END_REF] which enable to establish a direct communication between the brain and the virtual environment.

The best practices in DG to apply to VR

DG companies practice some studies to know their public in order to be able to adapt their products.

VR is a bit too attached to physic and should follow the example of DG and sometimes forget physical law to produce some more fanciful and aesthetic environments. In the same way it should be interesting to give more freedom to the user to interact with his environment. Is the height on interaction would not be to allowed the user to interact with the VR application itself like the player community of a game do when they create add-ons or new maps for their favorite game ? To introduce players in one game universe, DG create an ambiance through a narrative cinematic introduction movie and maintain it with the help of dedicated interlude like replay scene. We think ambiance is an interesting means to improve the feeling of presence in a VR experiment.

Lines of enquiry for virtual reality games

We have seen in the last section that researches on movement restitution in virtual reality have been very active during the past years. The benefit of these researches is dual: firstly, it focuses on the immersion quality letting users to achieve a natural movement. As consequence user self-motion perception agrees with the proprioceptive feedback. Secondly, it can reduce the feeling of head spin and queasiness due to motion sickness. It is a crucial point because players use to play several hours consecutively but immersive systems are well-known [START_REF] Pausch | A Literature Survey for Virtual Environments: Military Flight Simulator Visual Systems and Simulator Sickness[END_REF] to cause headaches and feeling of sickness.

To reproduce the self motion feeling following a low cost way, it seems interesting to think about the role of the multimodality. Hence, the movement impression could be given with visual and audio stimuli [START_REF] Väljamäe | Travelling without moving: Auditory scene cues for translational self-motion[END_REF].

About immersive installations we suggest to develop low cost multisensorial systems (visual, audio, tactil...) to achieve an immersion level with enough credibility. Nevertheless lot of studies have to be done to define the minimal immersion level required to create a virtual reality experience.

The future of visual interfaces that will be used in home virtual reality gaming is definitely interlinked with autostereoscopic screens. First, player have the habit of playing games on computer or television screens, next, projective systems and Head Mounted Displays are very intrusive and at the origin of discomfort. Autostereoscopic screens are still expensive but cost will decrease like the LCD screens have done.

Virtual reality interaction tools have to be simpler and cheaper for future games. For example interaction could be done using only webcams to detect and interpret the gesture of the player or detect player's emotions and intention with eye tracking algorithms. Of course this is not an easy task as it requires more research to achieve such a level of complexity and robustness but it could allow to use any objects of everyday life to interact with a game.

Finally it is evident that future virtual reality game system must be offered as plug and play system to be easy to use.

Conclusion

Our contribution is twofold, we propose some reflections and lines of enquiry about virtual reality games that we applied in two virtual reality games workshop. We definitely think that virtual reality games is a wonderful area of research on itself and can benefit to both VR and DG.

In the future, we want to go further in our reflections initiate in the section five, open these reflections to augmented reality and mixed reality games and finally to put them into practice through games.