Thanh-Hai Trinh
email: trinh@enib.fr

Ronan Querrec

Pierre De Loor
email: deloor@enib.fr

Pierre Chevaillier
email: chevaillier@enib.fr

Ensuring Semantic Spatial Constraints in Virtual Environments Using UML/OCL

Keywords: CR Categories: H.5.1 [Information Interfaces and Presentation]: Multimedia Information Systems -Artificial, augmented, and virtual realities, Evaluation/methodology spatial constraints, spatial languages, semantic virtual environments, domain knowledge visualization

Spatial objects and relationships between them, compose a spatial model that is the backbone of virtual environments (VEs). However, due to the natural complexity of both spatial objects and spatial information, the modeling of such spatial relationships is still a difficult task. This paper presents a novel approach for representing semantic spatial relations in VEs using the Unified Modeling Language (UML) and the Object Constraint Language (OCL). Our approach first uses the UML class model as a conceptual model for VEs. We then propose a spatial extension of OCL named VRX-OCL as a high-level and flexible language to cover multidimensional, manifold, and reference frame-dependent spatial constraints. We mainly focus on two important classes of spatial relations, namely, topological and projective relations that allow nonmetric representation of space. The applicability of our approach is demonstrated in the Virtual Physics Laboratory, a VE for learning physics. Based on the constraints satisfaction, the system is able to visualize abstract spatial information and thus provides educational assistance to the learners.

Introduction

Spatial relationships between objects provide crucial knowledge about virtual environments (VEs). Particularly, in VEs dedicated to enhancing spatial behaviors such as exploring a space or searching an item in the space, an explicit representation of spatial knowledge is a need [START_REF] Durlach | Virtual environments and the enhancement of spatial behavior: Towards a comprehensive research agenda[END_REF]]. Spatial expressions found in such applications could be "let's move to the statue in front of the picture", "the cube is on the bench". However, spatial objects populating virtual world are often described in a low-level way within 3D scenes built upon standard formats (e.g., VRML, X3D). As a consequence, spatial relations are implicit and hard to define.

To overcome these issues, it becomes clear that a high-level representation of spatial objects and notably an explicit description of spatial relationships between them is required. Recent work has focused on defining a semantic model for VEs [START_REF] Latoschik | Semantic modelling for virtual worlds a novel paradigm for realtime interactive systems?[END_REF]. The main idea is to represent spatial objects not only as animatable 3D shapes but also with their functions, roles, and the relationships between them [START_REF] Gutierrez | Semantics-based representation of virtual environments[END_REF]]. However, there still lacks a conceptual base and a common language to precisely specify spatial relations and to support the ability to query the spatial knowledge. Difficulties increase when spatial relationships form a constraints network that must be satisfied when users interact with VEs. The problem is not only to express constraints but also to decide whether these objectives are achieved or not. For example, how to compute that a user is near the statue, and consequently, in front of the picture? How to ensure that the user has put the cube on the bench? Especially, spatial constraints can be used as a condition for spatial interactions (e.g., "Before activating the laser, verify that the cube is between the lens and the mirror"). To do so, an indepth formalization of both semantics and computational methods of spatial constraints is needed. This paper presents a general approach for ensuring semantic spatial constraints in VEs. The novelty relies on the use of the Unified Modeling Language (UML) for the conceptual modeling of VEs and the Object Constraint Language (OCL) for representing spatial constraints. Our motive is that UML is a relevant basis for metamodeling, recognized by both industrial domain and the scientific community. However, this language has not been fully exploited for modeling semantics of VEs. Being an integral part of UML, OCL is a textual language to express and query constraints that diagrams can not cover by themselves [START_REF] Omg | Unified Modeling Language 2.0 Object Constraint Language Specification[END_REF]]. Because of the necessity to manage not only logical constraints in the conceptual model but also spatial constraints specialized to 3D dynamic environments, we propose VRX-OCL, a Virtual Reality eXtension of OCL. Our extension aims at ensuring different semantic constraints in VEs: (1) internal properties of spatial object (e.g., type, value of attributes), (2) spatial relationships among a set of spatial objects, and (3) semantics of spatial object interactions (e.g., pre-and post-condition of spatial tasks). In addition, when associated with adequate spatial reasoning techniques, such a constraint language could be used within an inference system to deduce automatically new knowledge from given one. For example, given "the statue is in front of the picture" and "the table is in front of the statue", one can conclude that "the table is in front of the picture".

By coupling 3D scenes representation with a semantic model, using UML/OCL, our approach gives a novel perspective to define spatial relations between objects that should be satisfied during users's manipulations and to make domain specific knowledge visible to users. Especially, this knowledge can be directly interpreted as instructions displayed textually or graphically, e.g., by visualizing the acceptance areas for the localization of manipulated objects in the 3D environment. VEs for training, learning, or spatial assistance systems are typical use cases that can benefit from our approach.

In the next section, we briefly discuss open problems in the modeling of spatial constraints in VEs and related researches. We focus on two important classes of spatial relationships, namely, topological and projective constraints that allow nonmetric representation of space. We raise the need for a spatial language to model these constraints through examples borrowed from the Virtual Physics Laboratory, a VE for learning physics. Section 3 gives an overview of our approach. Sections 4 and 5 respectively detail how nonmetric spatial constraints are modeled in VRX-OCL. We present both formalization and computational model of topological and projective relations. Section 6 draws our conclusions and outlines future work.

Modeling Spatial Constraints in VE -Examples from the Virtual Physics Laboratory

Related researches on modeling spatial constraints in VEs were rare and incomplete. [START_REF] Pellens | Intuitively specifying object dynamics in virtual environments using VR-WISE[END_REF]] and [START_REF] Irawati | Spatial ontology for semantic integration in 3D multimodal interaction framework[END_REF]] used spatial ontology to store information about spatial objects and spatial relationships between them. Alternatively, [START_REF] Kalogerakis | Coupling ontologies with graphics content for knowledge driven visualization[END_REF]] mapped node elements in 3D standards (like VRML, X3D) onto ontology's concepts, relations such as "whole-part" were handled, but not spatial constraints. [START_REF] Smith | Integration of constraints into a VR environment[END_REF] represented spatial objects using scene graph in which each object was constrained to other ones by means of "offer area" and "binding area". [START_REF] Park | A framework for VR application based on spatial, temporal and semantic relationship[END_REF]] integrated both spatial ontology and scene graph into a framework called NAVER for representing temporal and spatial relations. The main drawback of these approaches is that constraints are directly defined in hierarchical structures, whereas objects populating virtual world are dynamic and often manipulated by users. Smith and Stuerzlinger's model allows constraints to be broken and then re-constrained but they are defined in an ad-hoc manner. Also, only some specific types of constraint are handled.

As stated in [START_REF] Cohn | Qualitative spatial representation and reasoning: An overview[END_REF], the most important aspects of space are topology, direction, and distance. Moreover, spatial expressions in natural language are usually described in a qualitative (symbolic) manner (such as "disjoint", "meet", "inside", etc. for topology; "left", "north of" for direction/orientation; "far", "near" for distance). In 3D space, the challenge is that spatial relations are multidimensional (among 3D entities built upon complex shapes), ambiguous (in immersive and multi-user VEs, different points of view might yield different observations of the same relation), and manifold. As pointed out in [START_REF] Renz | Qualitative spatial reasoning using constraint calculi[END_REF], spatial relations are often given in the form of constraints that can be unary ("the length of the bench is 2 metres"), binary ("the cube should be placed on the bench"), ternary ("the cube should be placed between the lens and the mirror"), or n-ary in general. Spatial constraints may relate to metric (distance, angle) or nonmetric information (topology, projection). The later is the subject of this research.

Figure 1(a) illustrates the Virtual Physics Laboratory (VPLab), a VE for learning dedicated to lab work in physics, particularly in optics. One of the exercises learners have to perform is to measure the light speed in different mediums: air, resin, and water. Below is an example of an instruction given to the learner, corresponding to an expected result of a step in the procedure s/he has to follow.

Constraint 1 To measure the speed of light in resin materials, put the cube of resin on the bench, between the lens and the mirror.

No metric information (e.g., angle, distance) was used in this example. Such a relation as "on" (meet) stays invariant under topological transformations (i.e., translation, rotation, scaling), so called topological relations. One can also note that the latter constraint is based on the alignment between objects and can be alternatively formulated as "put the cube on the bench such that the mirror is after the lens and the cube". Such constraints as "between", "after" are called projective constraints because they are preserved under projective operations that maintain the collinearity of a point set.

Within the VPLab, it is possible to provide some assistance to the learners. For example, it is possible to represent that the velocity of light depends on the material it passes through. This abstract knowledge can be reified by graphically representing light as virtual photons moving at a speed which depends on the object wherein they are located. This assistance is called Slow motion (Fig. 1(b)).

Constraint 2 When Slow motion assistance is active, if a virtual photon is inside an object, its speed is proportional to the refractive index of the material of this object, else its speed is proportional to the refractive index of air.

In this case, it is necessary to handle in the same expression both object properties and spatial relations. We will see later that the former can be expressed using standard OCL, not the latter. Moreover, user-system interactions in VEs can be carried out either in immersive mode or in desktop mode (see Fig. 1(c)). In the latter case, the user has only a projective view of the 3D scene. Even in immersive mode, sometimes it is useful to give to the user a global view of the environment (e.g, a navigation map in a large-scale environment). These needs are satisfied by means of orthographic views of the environment (i.e., front, top, or side views). The scene in Fig. 1(a) gives an example of such an orthographic projective constraint.

Constraint 3 From a top view of the work surface, the water tube shall be on the right side of the lens and the mirror.

In this example, the relative position of the water tube to the lens and the mirror is inverted (leftside instead of rightside) under the opposite view (the bottom-view in this case). Thus, it is necessary for spatial languages to be able to disambiguate spatial constraints.

3 The Proposed Approach

Building Conceptual Model Using UML

To model spatial objects, we use the UML class model in which every class corresponds to a specific type of spatial objects. via associations and composition links between classes. Interestingly enough, in our conceptual model, even abstract concepts such as light may be modeled by a spatial class, named Light, whose instances are considered as photons. We define also some special classes that contain system information (e.g., different camera positions are stored in the Camera class).

Thanks to object-oriented approach, a spatial object can inherit attributes, operations, and associations from the parent class. For example, some primitives coming from the underlying 3D library are common between spatial objects, such as rotation, scaling, translation, etc. Furthermore, the modeling of domain-oriented concepts in UML is facilitated by means of stereotype, i.e., a new modeling primitive derived from existing ones. In our conceptual model, spatial objects are defined using a new stereotype called <<Entity>> that contains the following basic information about spatial object: -Unique name: is an (string) attribute that uniquely identifies a spatial object. For example, 'transmitterLens' and 'receiverLens' are the names of two lenses in the VPLab; 'photon1', 'photon2', etc. uniquely identify the instances of the Light class.

-Position: is a vector representing the coordinates of an object in 3D space. In large-scale environments such as VEs, the position of the object is often defined as its centre of gravity.

-Shapes: refer to the geometric structures of the spatial object. We thus separate conceptual and graphical representations of objects.

Since spatial objects are complex and thus not relevant to manipulate or calculate at the conceptual level, they are often approximated using simpler structures. We hence use in the conceptual model two levels of approximation.

-Semantic points: every spatial object is associated with one referential point. Other points may be involved if necessary, e.g., the position, the interaction points, or the markers that facilitate the navigation between objects in VE.

-Convex bounding volume: a spatial object is described by its axisaligned bounding box (AABB). The use of AABB in the conceptual model makes spatial objects easy to compute, cheap to store (only two points are needed for their representation), and fast to test for intersection. Furthermore, this primitive structure provides a convex approximation that is detailed enough to deal with non-metric information such as topology and projection. Although algorithms in the rest of this paper for computing topological and projective models are detailed using AABB, further implementations can be similarly derived for other levels of approximation based on bounding volumes.

As stressed in [Ibáñez and Delgado-Mata 2006], most of this basic information can be automatically annotated. Compared to previous work using ontology as a underlying semantic layer of VE, UML is more expressive and flexible thanks to the concept of stereotype. A further advantage of UML relies on the ability to model operational semantics that is still limited in ontology.

Extending OCL for Ensuring Spatial Constraints

OCL is a declarative language to specify constraints and expressions on any elements in a UML diagram. It is both a constraint and a query language: an OCL expression returns a value or an object within the system, but the evaluation of expressions does not change the state of the system. Using the UML class model presented in Fig. 2, the following examples illustrate the expressiveness of OCL.

Example 1 The constraint "the length of the bench must be inferior to 2 metres" is formally specified as follows. Example 3 To express complex constraints with multi-classes, OCL allows the navigation between classes using associations. Such a cardinality constraint as "a work surface has only one bench but several mediums" is expressed as follows.

c o n t e x t W o r k s u r f a c e i n v : s e l f . bench->s i z e ( ) = 1 and s e l f . medium->s i z e ()>=1

In this example, the expression self.bench returns a collection of all benches associated to a work surface, while the function size() counts the number of elements in a collection.

Example 4 OCL expressions can be used to form a pre-or postcondition of an operation. For instance, the prototype of the constraint "Before activating the laser, verify that the cube is between the lens and the mirror" is as follows.

c o n t e x t T r a n s m i t t e r R e c e i v e r : : a c t i v a t e L a s e r ( ) : Boolean p r e : <a s p a t i a l c o n s t r a i n t e x p r e s s i o n > Thus, whenever the operation activateLaser on the TransmitterReceiver is launched by the user, the pre expression is verified to enable/disable this interaction.

Through the above examples, we can see that OCL facilitates the specification of constraints in a formal way. However, invariants in the original OCL are usually local and unary, whereas spatial constraints might be binary, ternary, or n-ary in general. Further, as discussed in Sect. 2, in Constraint 3, opposite orthographic viewpoints may yield uncommon observations about the relative position of the water tube (called primary object) to the mirror and the lens (called reference objects). This is due to the fact that most spatial relations must be given with respect to an implicit or explicit frame of reference (FoR) that can be: intrinsic (the relation is given by inner properties of the reference object), extrinsic (the relation is imposed by external factors on the reference object), and deictic (the relation is given by the point of view from which the reference object is seen) [Hernández 1994]. The benefits of this third-person perspective in VEs are also reported in [START_REF] Salamin | The benefits of third-person perspective in virtual and augmented reality?[END_REF]].

Addressing these issues, we propose VRX-OCL as a spatial extension of OCL. We distinguish two types of spatial expressions: those which are independent of FoR (such as topological constraints, or projective constraints in immersive mode), and those which depend on FoR (projective constraints in orthographic view mode, directional constraints, etc). Thus, generally speaking the syntax of spatial expression in VRX-OCL is described as below.

SpatialExp::=SpatialExpWithOutFoR|SpatialExpWithFoR SpatialExpWithOutFoR ::= po '.' rel name '(' ro (',' ro) * (',' arg)? ')' SpatialExpWithFoR ::= SpatialExpWithOutFoR '@' 'viewpoint' '(' obs ')'

In this syntax, po is the primary object that can be associated with one or more reference objects noted as ro. Together with the @viewpoint keyword, obs is a spatial object that plays the role of an observer from which the relationship is seen. When a spatial expression is associated with an FoR, the constraint evaluation depends on the spatial operator involved to decide whether the direction/position of the observer, the inner properties (e.g., size, internal orientation) or the external factors (e.g., movement direction if the object is being moved) of reference objects must be taken into account. In the case of nonmetric constraints, it is the position of the observer that will be used to unambiguously specify projective constraints under different orthographic views. arg is a list of arguments (e.g., projection plane, approximation level, etc.). Finally, rel name stands for the name of the spatial constraint.

Modeling Topological Constraints

The two well-known models of topological relation are RCC-8 [START_REF] Randell | A spatial logic based on regions and connection[END_REF]] and 9-intersection [START_REF] Egenhofer | Point-set topological spatial relations[END_REF]. However, the main issue of these models, if applied to VEs, is that they are based on an exact computation of the intersections between objects with sharp boundary (cf. Fig. 3). Meanwhile, in VEs, users manipulate objects using interface devices (cf. Fig. 1(c)) which is a procedure lacking in precision. That makes such a manipulation as "put the cube meeting the bench" become difficult if objects involved must have common sharp boundaries. To overcome this issue, we propose that spatial objects are represented by AABB whose surfaces have a thickness ε > 0. Considering large-scale VEs, we also suppose that spatial objects are large enough so that every dimension of their AABB is larger than 2ε, so called thick boundary objects (TBO). For example, Fig. 4 illustrates the cube whose thick boundary is the buffer zone inside the object, between the red and the blue parts. Similar to the 9-intersection model, we denote the exterior (the set of points not contained in AABB), the boundary (the set of points contained in the thick surfaces), and the interior (the set of points contained in AABB but not in the thick surfaces) of a TBO A by A -, A ε , and A o respectively. Topological relations between the two TBO A and B are defined by a 3x3 matrix representing the nine intersections between their six parts.

A disjoint B A meet B A overlap B A covers B A inside B A equal B A coveredBy B A B A B B A A B A B B A A contains B B A B A
IT BO (A, B) = A o ∩ B o A o ∩ B ε A o ∩ B - A ε ∩ B o A ε ∩ B ε A ε ∩ B - A -∩ B o A -∩ B ε A -∩ B - (1)
If one makes an orthographic projection of these TBO to one of the three planes of the Cartesian coordinate system, the result is two rectangles with broad boundary (BBR) A Oth , B Oth as defined in [START_REF] Clementini | Approximate topological relations[END_REF] BBR is easily defined, called IBBR(A, B).

IBBR(A, B) = A o Oth ∩ B o Oth A o Oth ∩ B ε Oth A o Oth ∩ B - Oth A ε Oth ∩ B o Oth A ε Oth ∩ B ε Oth A ε Oth ∩ B - Oth A - Oth ∩ B o Oth A - Oth ∩ B ε Oth A - Oth ∩ B - Oth (2)
Based on the properties of orthographic projections and AABB (two projection rectangles enable the reconstruction of a unique AABB), the following theorem identifies the number of topological relations between two TBO.

Theorem 1 The number of topological relations between TBO described by the matrix IT BO equals the number of topological relations between BBR described by the matrix IBBR.

Proof Taking an arbitrary point p ∈ A -, we have p ∈ B -iff p ∈ B - Oth in two orthographic projections (easily given by the characteristic of orthographic projection). Thus, A -∩B -= ∅ (sharing a common point) iff A - Oth ∩ B - Oth = ∅ in two orthographic projections. If we perform the same operation with the other elements in the IT BO (A, B) matrix, it is obvious that each IT BO (A, B) matrix corresponds exactly to an IBBR(A, B) matrix. In other words, the number of topological relations between TBO equals the number of topological relations between BBR.

Let us now consider topological relations between BBR. [Clementini and Di Felice 1997] defined 44 possible relations for regions with broad boundary. However, the drawback is that the topological relations of this model are not symmetric, i.e., A.meet(B) does not yield B.meet(A). To us, the thickness ε is chosen by application designers as a global parameter depending on the accuracy of interface devices. The symmetry of the relations is consequently conserved. Since the rectangle is a special case of a region, we apply the following restrictions (the details are left to the readers).

A - Oth ∩ B ε Oth = ∅ A ε Oth ∩ B ε Oth = ∅ A o Oth ∩ B ε Oth = ∅ ⇒ B - Oth ∩ B ε Oth = ∅ B o Oth ∩ B ε Oth = ∅ (3) A - Oth ∩ B ε Oth = ∅ A ε Oth ∩ B - Oth = ∅ ⇔ A ε Oth ∩ B o Oth = ∅ A o Oth ∩ B ε Oth = ∅ (4)
Note that these conditions are symmetric with A Oth and B Oth . Such restrictions exclude 27 cases, keeping 17. We further gather them in 8 basic clusters as illustrated in Fig. 5. We however still keep the same numbering and the name of relations as defined in [START_REF] Clementini | Approximate topological relations[END_REF] for compatibility and comparison with previous work. As the intersection matrix between the TBO is similar to the BBR, it makes calculating topological relations between TBO in VE a trivial task.

Some further remarks can be made regarding the TBO. For simplicity, we have defined above the thick surfaces as a buffer zone inside a spatial object. They however may be outside, or both inside/outside the object. These cases are applied to simulate other phenomena (e.g., magnetic effects in the VPLab: an object is considered as meeting an other object when they are in proximity). In particular, as spatial entities are often large, it seems relevant to suppose that the interior is always bigger than the thickness ε. This restriction eliminates all the configurations in which A o is inside A ε (relations numbered 14, 10, and 12), keeping 14 relations.

To sum up, binary topological operators in VRX-OCL take the form of po.rel name(ro), where po, ro are respectively the primary and reference objects. rel name is one of the eight basic topological relations: disjoint, meet, overlap, inside, coveredBy, contains, covers, equal. Using the UML class diagram shown in Fig. 2, the following examples illustrate how topological constraints are described in the VPLab.

Example 5 The part "the resin cube should be placed on the bench" in Constraint 1 is expressed in VRX-OCL below.

c o n t e x t W o r k s u r f a c e i n v : l e t r e s i n C u b e : Medium = s e l f . medium ( ) ->s e l e c t ( name= ' r e s i n C u b e ' ) , b e n c h : Bench = s e l f . b e n c h ( ) ->s e l e c t ( name= ' b e n c h ' ) i n r e s i n C u b e ->m e e t ( b e n c h )

In this example, the let expression allows one to define a variable that can be used in the constraint, while the select function is used to specify a subset of the collection.

Example 6 The Constraint 2 is expressed as follows. ->s e l e c t ( name= ' w a t e r T u b e ' ) i n i f s e l f . i n s i d e ( r ) t h e n r e s u l t = 1 . 5 e l s e i f s e l f . i n s i d e (w) t h e n r e s u l t = 1 . 3 e l s e r e s u l t = 1 e n d i f e n d i f getRefractiveIndex() is a query operation of the Light class to get the refractive index of the material in which a photon (self) travels. The result indicated in the body expression is based on topological relations between self and the materials.

Modeling Projective Constraints

Ternary Projective Relations

Orthographic View Mode. In order to specify spatial constraints under orthographic views such as Constraint 3, we propose to refine and integrate into VRX-OCL the 5-intersection model [START_REF] Clementini | Modeling and computing ternary projective relations between regions[END_REF] whose aim is to describe the collinearity among regions. Given three spatial objects represented by their AABB, an orthographic view (i.e., top view, front view, or side view) of a 3D scene results in three rectangles respectively noted as A Oth (primary object), and B Oth , C Oth (reference objects). In the case that the reference objects are disjoint, based on the 5-intersection model, the relative position of A Oth to B Oth and C Oth is described thanks to the intersections between the external tangent lines (see Fig. 6(a)) and the internal tangent lines (see Fig. 6(b)) which constitute five areas (see Fig. 6(c)). The central area is called betweenOnPlane corresponding to the convex hull of B Oth and C Oth . Based on this area, four other areas are defined that allow one to decide whether the primary object is left/right of or before/after the reference objects. Nevertheless, as discussed in Sect. 2, different orthographic views may yield different observations of a concrete relation. Thus, we propose that such a spatial relationship must be formalized in the context of a frame of reference as follows. po.rel name(ro1,ro2,plane,collinearity level) @viewpoint(obs) where: po, ro1, ro2 are respectively three spatial objects, rel name is the name of the relationship. The five basic relations are beforeOnPlane, betweenOnPlane, afterOnPlane, rightsideOnPlane, leftsideOnPlane, plane is the projection plane that is one of the three planes: XY, YZ, or XZ. Each plane corresponds to an orthographic view, collinearity level represents different intersection levels between the primary object A Oth and the area indicated by rel name, involving: 1 -A Oth intersects with the acceptance area; 2 -there exists at least one of the semantic points of the primary object A Oth that is in the acceptance area, obs stands for the viewer from which the relationship is seen. Among the five basic relations described above, only leftsideOnPlane and rightsideOnPlane relations need a viewer as an explicit frame of reference to disambiguate the relation of A Oth to B Oth and C Oth under different orthographic views.

Let us now consider the semantic of ternary projective operators. Although algorithms for computing ternary projective relations between regions have been discussed in [START_REF] Clementini | Modeling and computing ternary projective relations between regions[END_REF]], they however did not allow one to lift ambiguities occurred under different orthographic views. Moreover, since the results of the orthographic projection of AABB are rectangles instead of regions, we decide to build a customized algorithm, which is also used later to compute ternary projective relations in immersive mode.

Algorithm 1 Computing a ternary projective constraint under an orthographic view. 1. Find the internal tangent lines (noted as In1, In2) and the external tangent lines (noted as Ex1, Ex2) of B Oth and C Oth . 2. Divide the projection plane into five acceptance areas. 3. Based on the position of the observer, decide whether A Oth (or one of its semantic points) intersects with a particular area from the viewpoint of the observer.

The Step 1 is carried out based on an observation that the external tangent lines connect two vertices of B Oth and C Oth such that all the remaining vertices are in the same half-plane. The internal tangent lines are those that connect two vertices of B Oth and C Oth such that all the remaining vertices B Oth and C Oth are in different half-planes. In Step 2, it is essential to define the convex hull of B Oth and C Oth . We denote p, q, s, t as the intersection points between the external tangent lines Ex1, Ex2 and the internal tangent lines In1, In2; k and m are the intersection points of the external tangent lines with B Oth and C Oth . It is obvious that the convex hull of B Oth and C Oth is the union of B Oth , C Oth , and the quadrangle made by k, q, m, s. In Step 3, for the sake of presentation, we only present in this paper the algorithms conceived to decide whether a point belongs to an area. Not lost generality, suppose that the situation in Fig. 6(c) is obtained from a top view projection. In this case, our algorithms are detailed as follows.

Algorithm 2 Point v belongs to the area betweenOnPlane if one of the following conditions holds: (i) v is contained in B Oth or C Oth . (ii) v is contained in the quadrangle made by k, q, m, s. The evaluations for other areas can be derived similarly. In Algorithm 3, if the observer yields a bottom-view of the environment, the result is inverted: the point v that belongs to the area leftsideOnPlane from a top-view is in the rightsideOnPlane area from a bottom-view, and vice versa. This mechanism obviously enables unambiguous distinction of ternary projective relations observed under orthographic views. Our algorithms are in constant time, compared to that mentioned in [START_REF] Clementini | Modeling and computing ternary projective relations between regions[END_REF]] which runs in O(nlog n).

Example 7 Using VRX-OCL, the Constraint 3 is expressed as below. For conciseness, only the constraint between the water tube and the transmitter lens and the mirror is illustrated. A similar constraint can be applied to the receiver lens and the mirror. In this example, we assume that the top-view resulted from the projection of the scene onto the XY plane. The evaluation of the constraint depends on TOP CAMERA, an instance of the Camera class that contains information about the top-view.

Immersive View Mode. To realize or perceive such spatial operations as Constraints 1 and 2, it is required to embed users into VE in immersive mode. Using haptic devices, this mode enables a more realistic manipulation of spatial entities than desktop mode. To express such constraints in VRX-OCL, we are based on the projective model between bodies defined in [START_REF] Billen | Projective relations in a 3D environment[END_REF].

Given two disjoint reference objects B and C, the localization of the primary object A can be retrieved from the intersections between the external tangent planes (see Fig. As ternary projective constraints in immersive perceiving mode are inherently independent of the reference frame, we subsequently integrate these relations into VRX-OCL as new spatial operators that take the form as follows: po.rel name(ro1, ro2, collinearity level) where:

po, ro1, ro2 are respectively three spatial objects, rel name is one of the followings: before, between, after, aside, collinearity level corresponds to the two representation levels of objects in the conceptual model: 1 -the AABB of A intersects with the acceptance sub-space referred by rel name; 2there exists at least one of the semantic points of A that is in the acceptance sub-space referred by rel name.

Let us now detail our method to compute ternary projective relations in 3D space that is presently lacking in previous models. The This algorithm is similarly expanded to other sub-spaces. It is obvious that the 3D reconstitution of ternary projective relations from orthographic views is in constant time.

Example 8 In the VPLab, the latter part of Constraint 1 "put the cube between the lens and the mirror" is expressed as follows. A similar constraint can be applied to the receiver lens and the mirror. Within the VPLab, based on the constraints satisfaction, it is possible to visualize abstract spatial relations and thus to help the learners in precisely manipulating spatial objects (see Fig. 8).

Quaternary Projective Relations

While ternary projective relations are based on the collinearity between three spatial entities, quaternary projective relations deal with the coplanarity among four spatial objects. Given three disjoint reference objects B, C, and D, the intersections between the external tangent planes (see Fig. 9(a)) and the internal tangent planes (see Fig. 9(b)) result in four sub-spaces named above, below, inside, outside (see Fig. 9(c), in which full AABBs are not showed). These relations are formalized in VRX-OCL as follows. po.rel name(ro1, ro2, ro3,coplanarity level) where: po and ro1, ro2, ro3 are respectively the primary and three reference objects, rel name is one of the following: inside, outside, above, below, coplanarity level defines different coplanarity levels between spatial objects: 1 -the AABB of A intersects with the sub-space corresponding to rel name; 2 -there exists at least one of the semantic points of the primary object A that is in the sub-space corresponding to rel name.

In order to compute quaternary projection relations, the first requirement consists of finding internal and external tangent planes. In the context of AABB, we argue that there are two external tangent planes (noted as Ex1 and Ex2) and six internal tangent planes (respectively noted as In1,..,In6). Figures 9(a) and 9(b) intuitively show that the external tangent planes connect three vertices from the reference objects such that all the remaining vertices are on the same half-space. In contrast, the internal tangent planes connect three vertices from the reference objects but gather two objects in a same half-space whereas the last one is in another half-space. In addition to the definition of tangent planes, it is needed to define the convex hull of the three reference objects. Let p, q, r and s, t, u be the vertices that respectively make up the two external tangent planes Ex1 and Ex2, Fig. 9(c) shows that the convex hull is built from the union of B, C, D, Ex1, Ex2, and three planes, termed as complementary tangent planes. Informally, an example of a complementary tangent plane is the one made up from p, q, s, and t that connects vertices from two of three reference objects such that all remaining vertices are in the same half-space. Let us now consider the algorithm to test whether a point belongs to a specific sub-space. Due to space limitations, we only present the method for checking the above relation which is detailed below.

Algorithm 5 Point v is above the reference objects B, C, and D if all of the following conditions hold: (i) v is not inside the convex hull of three reference objects.

(ii) v and s, u, t are in different half-spaces divided by Ex1.

(iii) v and s (respectively t, u) are in different half-spaces made by In1 (respectively In2, In3).

(iv) v and p (respectively q, r) are in different half-spaces made by In4 (respectively In5, In6).

The integration of these algorithms into VRX-OCL as new spatial operators allows one to express and query constraints related to the

Conclusions and Future Work

In this paper, we presented a general approach to ensure semantic spatial constraints in VEs. Our first finding was concerned with the use of UML to conceptualize 3D space, thus provided an abstract, implementation independent, and semantic representation of VEs.

We then defined VRX-OCL, a spatial extension of OCL to formally specify spatial constraints that are inherently manifold and dependent on frames of reference. We presented an in-depth definition of the semantics of nonmetric spatial constraints, i.e., topological and projective constraints. In order to tackle the lack of precision when manipulating 3D objects within VEs, we introduced the concept of thick boundary objects and then defined 17 topological relations between them. Our method for formalizing and computing projective relations allowed one to define semantic constraints between three objects (i.e., "before", "between", "after", "leftside", "rightside") and four objects (i.e., "above", "below", "coplanar"), both in orthographic and immersive views. Through the VPLab, we argued that the combination of these two families of spatial constraint offered the ability to define complex constraints without any metric information.

Metric spatial constraints, namely, distance and directional relations will be our future focus. We are particularly interested in qualitative approaches that abstract from metrical details of the physical world and thus provide a spatial representation closer to mental model of humans [START_REF] Cohn | Qualitative spatial representation and reasoning: An overview[END_REF]. Further, we plan to define and incorporate into our model suitable reasoning techniques. The main goal is to enable virtual agents to find out new relationships from existing ones. This research forms part of our project that aims at defining UML/OCL as the basis for a generic language dedicated to the semantic modeling of VEs. As semantic model intensively requires the reification and introspection of the conceptual model, we have been investigating our efforts on the design of a UML-based meta-model that might be used as a semantic reflection layer for VEs.

  (a) The work surface in VPLab (labels were added for explanation). (b) The effect Slow motion is simulated based on spatial constraints.(c) A user manipulates objects using 6DOF space mouse in desktop mode.

Figure 1 :

 1 Figure 1: The Virtual Physics Laboratory (VPLab) for practising physics lab work.

Figure 2 :

 2 Figure 2: The simplified UML class diagram representing the work surface of the VPLab.

Figure 3 :

 3 Figure 3: Illustration in 2D of eight topological relations according to RCC-8 and 9-intersection models.

Figure 4 :

 4 Figure 4: Visualization of an object without (left figure) and with (right figure) thick boundary.

Figure 5 :

 5 Figure 5: Illustration in 2D of 17 topological relations between AABB with thick boundary.

  c o n t e x t L i g h t : : g e t R e f r a c t i v e I n d e x ( ) : : R e a l body : l e t r : Medium = Medium . a l l I n s t a n c e s ( )->s e l e c t ( name= ' r e s i n C u b e ' ) , w: Medium = Medium . a l l I n s t a n c e s ( )

Figure 6 :

 6 Figure 6: Ternary projective relations in plan (orthographic) view.

Algorithm 3

 3 Point v belongs to the area leftsideOnPlane if all the following conditions hold: (i) v does not belong to the area betweenOnPlane. This test is carried out thanks to Algorithm 2. (ii) v and s are in different half-planes divided by In1. (iii) v and t are in different half-planes divided by In2. (iv) v and s (resp. t) are in different half-planes divided by Ex1.

  c o n t e x t W o r k s u r f a c e i n v : l e t w a t e r T u b e : Medium = s e l f . medium ( )->s e l e c t ( name = ' w a t e r T u b e ' ) , m i r r o r : M i r r o r = s e l f . m i r r o r ()->s e l e c t name = ' m i r r o r ' ) , t L e n s : L e n s = s e l f . l e n s ( )->s e l e c t ( name = ' t r a n s m i t t e r L e n s ' ) i n w a t e r T u b e . r i g h t s i d e O n P l a n e ( t L e n s , m i r r o r , 'XY ' , 1 ) @ v i e w p o i n t ( Camera . a l l I n s t a n c e s ( ) ->s e l e c t ( name= 'TOP CAMERA ' ) )

  7(a)) and the internal tangent planes (seeFig. 7(b)). However, unlike the formal model in which the number of tangent planes are undefined, the use of AABB as a convex approximation of object allows us to argue that there are exactly four external tangent planes and four internal tangent planes of reference objects. Figure7(c)shows the four acceptance subspaces defined from the intersections between these planes. (a) Two of four external tangent planes. (b) Two of four internal tangent planes.(c) Four sub-spaces made up from the tangent planes.

Figure 7 :

 7 Figure 7: Ternary projective relations in immersive view.

  (a) The zone before the lens and the mirror. (b) The zone between the lens and the mirror.(c) The zone after the lens and the mirror.

Figure 8 :

 8 Figure 8: Visualization of the acceptance sub-spaces between the transmitter lens and the mirror in the VPLab.

  c o n t e x t W o r k s u r f a c e i n v : l e t r e s i n C u b e : Medium = s e l f . medium ( ) ->s e l e c t ( name= ' r e s i n C u b e ' ) , t L e n s : L e n s = s e l f . l e n s ( ) ->s e l e c t ( name= ' t r a n s m i t t e r L e n s ' ) , m i r r o r : M i r r o r = s e l f . m i r r o r ( ) ->s e l e c t ( name= ' m i r r o r ' ) i n r e s i n C u b e . b e t w e e n ( t L e n s , m i r r o r , 1 )

  Four sub-spaces made up from tangent planes.

Figure 9 :

 9 Figure 9: Projective relations between four objects.

  (a) The external tangent planes. (b) The zone above.

Figure 10 :

 10 Figure 10: Visualization of the acceptance sub-spaces between the transmitter lens, the mirror, and the cube.

  This constraint is defined in the context of the Bench class, self represents any instance of this class. It is an invariant that specifies a static property of the attribute length of the contextual class.Example 2 In OCL, the allInstances() function returns the collection of all the instances of a class. Universal and existential quantifiers are denoted as forAll and exists. Logical relations and implication are also supported using logical operators such as and, or, xor, and implies. The following expression exemplifies that "different lenses must have different positions".

	c o n t e x t Bench i n v :
	s e l f . l e n g t h < 2
	c o n t e x t L e n s i n v :
	L e n s . a l l I n s t a n c e s ()-> f o r A l l ( l 1 , l 2 |
	l 1< >l 2 i m p l i e s l 1 . p o s i t i o n < >l 2 . p o s i t i o n )

  . Their interiors, boundaries and exteriors are respectively noted as A o

Oth , A ε Oth , A - Oth and B o Oth , B ε

Oth , B - Oth . Consequently, the intersection matrix between two

Acknowledgments. We thank the three anonymous reviewers for their fruitful suggestions, and Christine Baissac for her helpful editing. This work was supported by La Région Bretagne, France.


Pierre De Loor

Kristen Manac'h
email: manach@enib.fralexandra.fronville@univ-brest.fr

Alexandra Fronville

Simulation of abstract autopoietic machine

Keywords: autopoiesis, simulation, (M, R) System

come

According to [START_REF] Maturana | Autopoiesis and Cognition: The realization of the living[END_REF], autopoiesis is at the basis of autonomy and cognition. Consequently, some artificial life works aimed at simulating artificial autopoiesis [START_REF] Beer | R Autopoiesis and Cognition in the Game of[END_REF][START_REF] Mcmullin | Thirty Years of Computational Autopoiesis: A Review[END_REF]. Generally, the purpose is to maintain a topological organization of automata. At the opposite, we consider that simulation can override topological aspects because topology has no significance in the computational domain. More important is to preserve self-regeneration and resistance to disturbances of an Abstract Autopoietic Machine (AAM). The long term goal of our work is to address the elucidation of the Rosen conjecture -i.e. that a model of life defined as closure under efficient cause cannot be instantiated by a computer simulation -which is called into question by [Stewart and Miosso 2007] -which say that closure under efficient causation does not represent a theoretical problem for calculability - [START_REF] Letelier | Autopoietic and (M,R) systems[END_REF]] showed that autopoiesis is less general but very close to (M,R) System. Nevertheless, we can't claim that we simulate (M,R) systems because our model lack on a full loop allowing the use of produced data as an executive code.

Formally, an AAM is a tuple {E,F} : ─ E is a multiset (N,m) of abstract particles defined by an integer.

ܰ ؿ Գ.is the underlying set of E. It is representative of the self of the AAM ݉: ܰ ՜ Գ ஹଵ .is the multiplicity function, i.e the number of occurrence of x in E is m(x).

─ ܨ ൌ ሼ݂|݂: ܧ ൈ ܧ ՜ ܧ ଶ ሽ is a set of interaction functions. Each interaction function transforms a couple of abstract particles to another couple of abstract particle.

The dynamic of an AAM is executed into another multiset Env=(Nenv,menv) representative of an abstract environment. It is defined by these principles:

─ Env is initialized with E (Env=E) ─ ݂ ݅݊ ܨare chosen randomly and applied indefinitely to couples of elements of Env which are also chosen randomly. The result is introduced in Env. If Nenv⊂N during this evolution, the AAM machine is stable and closed. Else, the AAM is unstable and elements of N∩New are its nonself.

─ A perturbation consists in introducing some elements in Env. The reaction of the AAM is the dynamic of the evolution of the set N∩New.

The presentation will show results of these simulations. More precisely:

─ The influence of E and F on the resistance to different perturbations. ─ The regularities on reactions coming from disturbances.

Acknowledgements: This work is supported financially by the Conseil Régional de Bretagne.