¸ois Franc

Valérie Lehericey
email: francois.lehericey@irisa.fr

Bruno Gouranton

Arnaldi

GPU Ray-Traced Collision Detection: Fine Pipeline Reorganization

Keywords: Collision Detection, Narrow-Phase, GPU Computing

Ray-tracing algorithms can be used to render a virtual scene and to detect collisions between objects. Numerous ray-tracing algorithms have been proposed which use data structures optimized for specific cases (rigid objects, deformable objects, etc.). Some solutions try to optimize performance by combining several algorithms to use the most efficient algorithm for each ray. This paper presents a ray-traced collision detection pipeline that improves the performance on a graphicd processing unit (GPU) when several ray-tracing algorithms are used. When combining several ray-tracing algorithms on a GPU, a well-known drawback is thread divergence among work-groups that can cause loss of performance by causing idle threads. In this paper we avoid branch divergence by dividing the ray tracing into three steps with append buffers in between. We also show that prediction can be used to avoid unnecessary synchronizations between the CPU and GPU. Applied to a narrow-phase collision detection algorithm, results show an improvement of performance up to 2.7 times.

INTRODUCTION

Collision detection (CD) is an important task in virtual reality (VR). From a set of objects, we need to know those which collide. Nowadays collision is one of the main bottlenecks in VR applications due to the complexity of environments we want to simulate and the real-time constraint required by VR. We need to simulate large environments that can count millions of objects. And we want to include complex objects that can be deformable, undergo topology changes or be fluids.

To handle such a work load, collision is generally divided into two phases: broad-phase and narrowphase. The broad-phase takes the whole set of objects from the environment and provides a set of pairs of objects that might collide. The narrow-phase takes these pairs and outputs the ones that actually collide. This paper focuses on the narrow-phase which is nowadays the most time-consuming phase.

Recent approaches use GPGPU (general-purpose computing on graphics processing units) to take advantage of the high computational power of recent GPUs. Parallel implementation of the broad-phase sweep and prune algorithm on GPUs improve performance by orders of magnitude [START_REF] Liu | Realtime collision culling of a million bodies on graphics processing units[END_REF]. The narrow-phase can also be implemented on a GPU [START_REF] Pabst | Fast and scalable cpu/gpu collision detection for rigid and deformable surfaces[END_REF].

In the literature four categories of narrow-phase algorithms are studied, including image-based algorithms that uses rendering techniques to detect collisions. As GPUs are designed especially for rendering, image-based methods are well suited for GPGPU implementations. In particular ray-tracing algorithms can be used and several ones can be combined to improve performance (Lehericey et al., 2013a). When implementing several ray-tracing algorithms on GPUs, high branch divergence in the execution can lead to underuse of the GPU and reduced performance.

Main contributions: we present a new pipeline organization of the narrow-phase for ray-traced collision detection. The goal of our pipeline is to minimize thread divergence on GPUs to improve performance. Our pipeline is designed to be able to integrate several ray-tracing algorithms without causing overhead. We then present a prediction method to avoid CPU-GPU synchronization between steps of the pipeline to further improve performance. This paper is arranged as follows. The following section provides a reviex of the relevant literature. Section 3 presents our ray-traced collision pipeline. Section 4 shows how prediction can be used to avoid unnecessary synchronization between the CPU and GPU. Implementation and results are discussed in Section 5. Section 6 concludes this paper. This section focuses on the literature on CD which is most pertinent to our work, in particular imagebased algorithms for the narrow-phase. For an exhaustive overview on CD, readers should refer to surveys such as [START_REF] Teschner | Collision detection for deformable objects[END_REF][START_REF] Kockara | Collision detection: A survey[END_REF].

Image-based Collision Detection

Image-based algorithms use rendering techniques to detect collisions. These methods are often adapted for GPUs, which are processors designed for rendering. Image-based methods can be used to perform collision detection on rigid and deformable bodies. These techniques usually do not require any pre-processing steps which makes them suitable for dynamically deforming objects. Image-based algorithms can either use rasterization or ray-tracing techniques.

Rasterization can be used to compute a layered depth image (LDI) which can be post-processed to detect collisions [START_REF] Allard | Volume contact constraints at arbitrary resolution[END_REF]. The CInDeR algorithm [START_REF] Knott | Cinder: Collision and interference detection in real-time using graphics hardware[END_REF] uses rasterization to implicitly cast rays from the edges of an object and counts how many object faces the ray passes through. If the result is odd then there is collision; otherwise there is no collision. [START_REF] Heidelberger | Real-time volumetric intersections of deforming objects[END_REF][START_REF] Heidelberger | Detection of collisions and self-collisions using imagespace techniques[END_REF]) take three-dimensional closed objects and output the intersection volume without the needs of any data structures making it suitable for deformable objects. The main drawback of these techniques is the discretization of the space through rendering that induces approximations and may lead to the omission of small objects.

Ray-tracing algorithms can be used to overcome these approximations. [START_REF] Wang | Adaptive imagebased intersection volume[END_REF] show that ray tracing can be used to compute a LDI with a higher resolution around small objects by increasing the density or rays locally to increase the precision. [START_REF] Hermann | Ray-traced collision detection for deformable bodies[END_REF] detect collisions by casting rays from each vertex of the objects. Rays are cast in the inward direction; the ones that hit another object before leaving the source object detect a collision. Before casting a ray, the ones that are outside the intersection of the bonding volumes are dropped since they cannot collide.

Based on Hermann et al.'s algorithm, (Lehericey et al., 2013a;[START_REF] Lehericey | Ray-traced collision detection: Interpenetration control and multi-gpu performance[END_REF] introduced an iterative ray-traced collision detection algorithm (IRTCD). This method combines two different raytracing algorithms; a full and an iterative algorithm that are respectively used for high and small displacements between objects. The full algorithm can be any existing ray-tracing algorithm. The iterative algorithm is a fast ray-tracing algorithm that exploits spatial and temporal coherency by updating the previous time-step. These algorithms can be used on GPUs for improved performance.

GPU Computing

Several methods consider the GPU as a streaming processor. As GPUs are massively parallel processors, computations should be arranged to be made parallel [START_REF] Nickolls | The gpu computing era[END_REF].

When code runs on a GPU, the same function (called kernel) is called by multiple threads (called work-item) on different data. Work-items do not run independently but in a group (called work-group); in a work-group, work-items run in a single instruction, multiple data way. On a conditional branch, if the work-items diverge among a work-group, each branch runs serially. This phenomena is called thread divergence and reduces performance [START_REF] Zhang | Streamlining gpu applications on the fly: thread divergence elimination through runtime thread-data remapping[END_REF].

One case of thread divergence is having a sparse input, in which case some work-items have nothing to do and are idle in a work-group while the other workitems finish. Collision-streams [START_REF] Tang | Collision-streams: fast gpu-based collision detection for deformable models[END_REF] use stream compaction to avoid kernel execution on sparse inputs. Collision detection is divided into several steps and streaming compaction is used between steps to ensure dense input for each kernel.

Synthesis

Ray-traced collision detection can be used on GPUs to achieve high performance on complex scenes. In a simple scenario only one ray-tracing algorithm can be used to resolve collisions. But in complex scenes with objects of different nature we can employ several ray-tracing algorithms to optimize each nature of object. With rigid objects we can use algorithms with complex data structures. With deformable objects we need data structures that can be updated at each timestep. In the case of topology changes we need to reconstruct the ray-tracing data structures occasionally. Iterative ray-tracing can be used to accelerate all of these algorithms.

In complex scenes where all these properties are represented, combining several ray-tracing algorithms improves performance. In such situations, the need of a narrow-phase that can easily manage diverse ray-tracing algorithms without losing performance emerges.

RAY-TRACED CD PIPELINE

To perform our ray-traced CD method there are several ray-tracing algorithms available in the literature. We selected three algorithms. We qualify the two first ones as 'full' ray-tracing algorithms; these algorithms can be used at any time. The third algorithm, called iterative, requires specific conditions.

The first full algorithm is a stackless bounding volume hierarchy (BVH) traversal. This algorithm uses an accelerative structure and can be used for rigid objects. The second full algorithm is basic raytracing. This algorithm does not use any additional accelerative structures and can be used for deformable objects. If we used the stack-less BVH traversal algorithm or deformable objects, we would need to update the accelerative structure at each time-step.

The third ray-tracing algorithm which we do not qualify as 'full' is the iterative ray-tracing algorithm. This algorithm is incremental and updates the previous time-step. This algorithm cannot be used at any time because it needs an extra input to work; this extra input is the reference of the last hit triangle in the previous time-step (called temporal data in the remainder of this document). The iterative algorithm needs a full ray-tracing algorithm to first create temporal data and then it can be used to replace the full algorithm in the following steps. We can use the iterative algorithm as long as relative displacement between the ray and target of the ray remain small. When temporal data is available, the iterative algorithm is faster than the two previous ones and should be preferred.

Before executing the ray-tracing we can perform simple culling tests to reduce the total number of rays to cast. If the origin of the ray is outside the bounding volume of the target, we can remove that ray because it cannot be inside the target. For rays using the iterative algorithm, we test if temporal data is available from the last step. If no temporal data is available we can drop the vertex because the iterative algorithm requires temporal data. The absence of temporal data indicates that at the previous time-step no collision was detected for this vertex and no prediction indicated a possible future collision.

When combining several ray-tracing algorithms on GPUs, the naive implementation consists of executing one large kernel that implements all the raytracing algorithms with a switch to select which algorithm to use for each vertex. This naive implementation will cause thread divergence for two reasons. First, all the ray-tracing algorithms are executed by the same kernel; this adds a branch divergence on the execution of each ray trace. Each work-group that executes more than one algorithm will execute them se-quentially. Second, in a context where we can safely cull some vertices to reduce the amount of computation, this naive implementation will initiate workitems that finish immediately. These work-items will then be idle while the other work-items of the workgroup finish.

This section presents our pipeline distribution of tasks to improve the performance of ray-traced collision detection on GPUs. Subsection 3.1 gives an overview of the pipeline and the three steps. Subsection 3.2, 3.3 and 3.4 detail the three steps: per-pair, per-vertex and per-ray steps.

Pipeline Organization

To achieve collision detection our narrow-phase pipeline must perform several tasks: Apply a measurement of displacement on the pair of objects to decide if we use a full or the iterative ray-tracing algorithm. Cull vertices with simple criteria to avoid unnecessary ray-tracing. Execute the ray-tracing from the remaining vertices; the algorithm depends on the nature of the object or if we decided to use the iterative algorithm.

The displacement measurement can be applied globally on a pair of rigid objects and needs to be applied per vertex when a deformable object is present to take into account internal deformations. Pairs (or vertices) classified with small displacement will use the iterative ray-tracing algorithm.

Vertex culling uses a drop criterion to remove vertices that do not need to be tested with ray-tracing because a simple test can discard collision. For the vertices classified as evidencing displacement, we check if the vertex is inside the intersection of the bounding volumes of the two objects of the pair. For the vertices classified as showing small displacement we test the presence of temporal data.

Ray-tracing is executed for each of the remaining vertices. We use the iterative algorithm when selected; otherwise, we use an algorithm that depends on the nature of the target of the ray-tracing.

These tasks show that the narrow-phase must process data at three different levels of granularity: perpair, per-vertex and per-ray granularity. The goal of this decomposition is to avoid branch divergence and ensures a dense input at each step. Figure 1 gives an overview of the pipeline organization.

Append buffers are used between each step to store data. The kernel preceding the append buffer fills it. Each entry of the buffer generates threads in the following kernel. The main purpose is to guarantee a dense input to the following kernel and avoid idle threads. Figure 1: Pipeline organization of the narrow-phase. The narrow-phase starts from the list of pairs of objects detected by the broad-phase. The first step is applied on the pair and we separate them into three categories: rigid pairs with small displacement, rigid pairs with high displacement and deformable pairs. The second step is applied on the vertices of the objects of the pairs; we select which ray-tracing algorithm to use depending on the nature of the objects and the result of the displacement measurement. The last step is applied on the rays and is the execution of the ray-tracing algorithms.

In the following subsections (3.2, 3.3 and 3.4) we detail the content of the three steps.

Per-Pair Step

The per-pair step starts from the list of pairs of objects provided by the broad phase. In this step one thread corresponds to one pair.

First we split the pairs into two categories: those which contain only rigid objects and those which contain deformable objects. This separation is applied because the criterion to decide if we use a full or the iterative algorithm is different.

For the pairs with only rigid objects we apply at this stage a displacement criterion to separate those with high displacement that will use a full ray-tracing algorithm and the ones with small displacement that will use the iterative algorithm. We cannot apply a displacement criterion on the pairs that contain at least one deformable object in this stage. In such cases displacement needs to be measured locally to take into account internal deformations.

Per-Vertex Step

The per-vertex step starts from each list of pairs constructed in the per-vertex step. In this step one thread is executed for each vertex of each object of each pair.

For the pair containing deformable objects, we can now apply a displacement measurement on the vertices to separate the ones with small displacement that will use the iterative algorithm and the others that will use a full algorithm.

Then we apply a drop criterion on the vertices to cull the ones that can be safely discarded. The criterion is different for vertices using a full algorithm and vertices using the iterative algorithm. For the vertices that use a full algorithm, we check if the vertex is in-side the intersection of the bounding volumes of the two object of the pair. If not, we can drop this vertex as it cannot collide. For the vertices that use the iterative algorithm, we test if temporal data is available from the preceding step. If no temporal data is available we can drop the vertex.

After applying the drop criterion, each remaining vertex generates a ray that will be cast on the other object of the pair; the parameters needed to cast these rays are stored in three buffers. Vertices using the iterative algorithm fill the list of rays for the iterative ray-tracing algorithm. Rays generated from vertices using a full algorithm need to be separated into two categories: rays cast to a rigid object use a stackless BVH ray-tracing algorithm; rays cast to a deformable object use the basic ray-tracing algorithm.

Per-Ray Step

The per-ray step starts from each list of rays and executes the ray-tracing. Each thread casts one ray.

The BVH ray list uses the stackless BVH traversal algorithm. This algorithm uses a BVH as an accelerative ray-tracing structure [START_REF] Wald | Ray tracing deformable scenes using dynamic bounding volume hierarchies[END_REF] with a stackless traversal adapted for GPUs [START_REF] Popov | Stackless kd-tree traversal for high performance gpu ray tracing[END_REF]. The basic ray list uses the basic ray-tracing algorithm. This algorithm does not use any accelerative structure; for each ray we iterate through each triangle. This method has high complexity but does not necessitate any accelerative structures that would need to be updated after each deformation. The iterative ray list uses the iterative ray-tracing algorithm (Lehericey et al., 2013a). This algorithm can be used on both rigid and deformable objects.

Each ray-tracing algorithm is implemented and executed in a separate kernel to avoid branch divergence in the GPU. The ray-tracing algorithms output contact points for the physics response. Figure 2: Comparison of the timeline of events between "exact workload" and "workload prediction". In this a task, A, fills an append buffer and two tasks, B 1 and B 2 , use it. On the top part we execute the 1 and B 2 tasks with the optimal work size but the GPU spends time in idle due to a synchronization. On the bottom part we use a prediction of the completion to schedule tasks at the cost of some empty work-items.

BUFFER COMPLETION PREDICTION

Along the narrow-phase we need to know the number of elements contained in append buffer (which we will to as completion in the rest of this section). For each append buffer we need to know a priori the completion to sufficient space and a posteriori to know how many threads must be launched in the following kernels. But these completion values are unavailable a priori and stored in the GPU memory a posteriori. To avoid extra computations or synchronizations that would lower the performance, we can rely on predictions.

In this section we will first explain, in subsection 4.1, our general prediction scheme and then we will apply this prediction scheme to the append buffer sizes and on the workload in subsection 4.2 and 4.3.

Generic Prediction

Let N t be the number of elements contained in an append buffer at the current time-step, and N t-1 at the previous time-step. p(N t ) is the predicted value at the time-step t.

We have access to N t-1 , i.e. the exact count that should have been used in the previous time-step. This value can be retrieved asynchronously with no extra cost. predict the evolution of the value, we rely on the evolution of the number of pairs issued by the broad-phase which gives an indication on the evolution of the global workload. Let nbPairs t (and nbPairs t-1 ) be the number of pairs detected by the broad-phase at the time-step t (and t -1).

Equation 1 gives a prediction value p(N t ). We take as input the real value at the previous time-step, N t-1 . We weight the value with the evolution of the number of pairs that give us an indication of the evolution of the workload. And we multiply the result with a confidence level of at least 1 to take into account variability.

p(N t ) = N t-1 × nbPairs t nbPairs t-1 × con f idence (1)
At the end of the time-step we can asynchronously retrieve the real value N t and compare it with the prediction p(N t ) to check if the prediction was high enough. If the prediction was too low we have two strategies. The simplest one is to ignore the error and continue the simulation. This solution will cause errors in the simulation but will be suitable for real-time applications. The second solution is to backtrack the simulation and use the real values. This will achieve a correct simulation and will be preferred for offline simulations.

Buffer Size Prediction

Before we launch a kernel that will fill an append buffer we need to know a priori the number of elements that will be inserted to allocate sufficient space.

To get this number we could execute the kernel twice: once to get the number of outputs and once to fill the append buffer.

We can use prediction to the first execution. We apply the prediction equation to evaluate the size of the append buffer. We can use a large value of confidence in these predictions as it does not affect computation size but does affect buffer size.

Workload Prediction

To be able to a kernel that takes as input an append buffer we need to know completion of the buffer to know how many threads to launch. This completion value is in the GPU memory and the nel execution is scheduled by the CPU. We have two solutions to manage this data dependency:

The first solution, called exact workload, consists of reading back the completion from the GPU to the CPU. Then we can the next kernels with the exact number of threads. The upper of Figure 2 shows the timeline of the events on the CPU and GPU. The major drawback of this method is the synchronization between the CPU and GPU; the GPU is idle while waiting for the next kernel's execution.

The second solution, called workload prediction, does not to rely on the exact completion, but predicts it. To predict the completion we can apply the prediction equation with a large value of confidence to minimize the risk of missing some rays. If we run too many threads, they will immediately exit after checking if their index exceed the completion value stored in the GPU. The drawback of this method is that large prediction will lead to empty threads in the GPU, but these empty work-items will be all grouped in the last work-groups and thus will not provoke branch divergence. The advantage of this solution is that it does not trigger any synchronization between the CPU and GPU as shown in the bottom part of Figure 2.

PERFORMANCE EVALUATION

This section presents our experimental environment and our performance results. First, in 5.1 we present our experimental setup. Then in subsection 5.2 we show the performance improvement when using our ray-traced pipeline method. In subsection 5.3 we show the performance gain obtained by using prediction. Finally in 5.4 we measure the quantity of errors introduced by the predictions.

Experimental Setup

To measure the performance improvements of our ray-traced narrow-phase we measured the GPU computation time of 10 second simulations executed at 60 Hz on two different experimental scenes: 'rigid objects' and 'rigid and deformable objects'. In the scene 'rigid objects' (see Figure 4) 1,000 rigid non-convex objects fall on an irregular ground. Four different objects presented in Figure 3 are used in equal quantities. Up to 10,000 pairs of objects are tested in the narrow-phase. In the scene 'rigid and deformable objects' (see Figure 5) 216 rigid non-convex objects fall on an irregular ground and 36 deformable sheets fall on the top of them. The rigid objects are the same as in the first scene. The deformable sheets are square shaped and composed of 8,192 triangles. Up to 860 pairs of rigid objects and 600 pairs of rigid/deformable objects are tested in the narrow-phase. Our experimental scenes were developed with bullet physics 3.x1 using a GPU. Our narrow phase were implemented for GPU with OpenCL. All scenes were executed using an AMD HD 7990.

Pipeline Performance

To measure the speedup obtained with our narrowphase pipeline, we compared the GPU computation time of the narrow-phase while using our pipeline reorganization and without it. In the scene 'rigid objects' we measured the performance of our pipeline reorganization when using only the full ray-tracing algorithm (BVH ray traversal) and when using both full and iterative ray-tracing algorithms. Result are shown in Figure 6.

The first result is the speedup obtained when using our pipeline method with only the full ray-tracing algorithm. We get an average speedup of 1.31 times when using our pipeline ray-tracing method. This speedup can be explained by the per-vertex step that guarantees that the ray-tracing step is executed on dense data even if the input of the per-vertex step is sparse.

The second result is the speedup when using our pipeline method with the combination of full and iterative ray-tracing algorithms. The average speedup when using our pipeline ray-tracing method is 2.73 times. The extra speedup compared to the previous case come from the execution of each ray-tracing algorithm in a different kernel in the per-ray step which reduces branch divergence in the GPU.

In the scene 'rigid and deformable objects' we measured the performance of our pipeline reorganization when three ray-tracing algorithms are used. Result are shown in Figure 7. In this scene we get an average speedup of 1.84 times when using our pipeline ray-tracing method.

Workload Prediction

To show the performance improvement when using our workload prediction strategy, we compared the GPU computation time of simulation using the workload prediction and the exact workload strategies. 1: Average GPU performance gain between the exact and prediction strategies for the workload. The workload prediction strategy is up to 2.84 ms faster per time-step than the exact workload strategy.

Table 1 gives the average gain when using the workload prediction against the exact workload strategy. We measured the gain on both 'rigid object' and 'rigid and deformable objects' scenes. For the 'rigid object' scene we measured the gain when using only the full ray-tracing algorithm and when using both full and iterative ray-tracing algorithms. The results show that the workload prediction strategy is between 2.0 and 2.8 ms faster per time-step than the exact workload strategy in both cases. This gain comes from elimination of CPU/GPU synchronizations between steps that eliminate the fixed cost (the cost of a CPU/GPU synchronization does not depend on the quantity of work). This reduction is not negligible in a real-time context where we only have a few ms to compute collisions.

Prediction Error Evaluation

To evaluate the efficiency of our generic prediction equation (Eq. 1), we measured the percentage of missed rays caused by underestimation of the predictions. We compared this percentage of missed rays with a simple prediction equation (Eq. 2) that does not take into account the evolution of the number of pairs detected by the broad phase. In both cases we used a 2% variability confidence (con f idence = 1.02). bu f f er t = bu f f er t-1 × con f idence

(2)

Scenario

Error reduction 'Rigid objects' 79% Full and iterative ray-tracing 'Rigid and deformable objects' 28% Full and iterative ray-tracing Table 2: Measurement of the reduction of the number of missed rays. Taking into account the evolution of the number of pairs detected by the broad-phase reduces the number of missed rays by up to 79%.

Table 2 shows the reduction of the errors when using our prediction method against the simple one. We did not include the scene 'rigid objects' with only the full ray-tracing algorithm because with only one algorithm the percentage of error is too small to be significant (less than 0.1%). Results show that taking into account the evolution of the number of pairs reduce the percentage of errors by 28 and 79%.

CONCLUSIONS AND FUTURE WORK

We have presented a pipeline reorganization to improve the performance of ray-traced collision detection using a GPU. Our method enables the integration of different ray-tracing algorithms in our narrowphase to efficiently handle objects of different nature. By dividing the narrow-phase into three steps, we were able to maintain a dense input throughout the whole pipeline to maximize the GPU cores usage. Our implementation shows an average speedup up to 2.73 times.

In future work we want to extend our narrowphase to objects of other nature such as topology changes and fluids. We also want to improve performance by generalizing our pipeline to multi-GPU and hybrid CPU/GPU architectures.

Figure 3 :

 3 Figure 3: The four rigid objects used in the simulation respectively composed of 902, 2,130, 3,264 and 3,458 triangles.

Figure 4 :

 4 Figure 4: 'Rigid object' scene: 1,000 concave objects fall on an irregular ground.

Figure 5 :

 5 Figure 5: 'Rigid and deformable object' scene: 216 concave objects fall on an irregular ground and 36 deformable sheets fall over them.

Figure 6 :

 6 Figure6: Performance comparison of GPU collision detection with and without our pipeline reorganization in the scene 'rigid objects'. With only a full ray-tracing algorithm our method gives an average speedup of 1.31 times and with the combination of a full and iterative ray-tracing algorithms our methods gives an average speedup of 2.73 times.

Table

		without pipeline
		with pipeline
	Time in simulation (s)
	Figure 7: Performance comparison of GPU collision de-
	tection with and without our pipeline reorganization in the
	scene 'rigid and deformable objects'. Our method gives an
	average speedup of 1.84 times.
	Scenario	Average gain
	'Rigid objects' Only full ray-tracing	2.84 ms
	'Rigid objects' Full and iterative ray-tracing	1.97 ms
	'Rigid and deformable objects' Full and iterative ray-tracing	2.05 ms

http://bulletphysics.org/


Guillaume Claude
email: guillaume.claude@irisa.fr

Valérie Gouranton

Bruno Arnaldi
email: bruno.arnaldi@irisa.fr

Valerie Gouranton
email: valerie.gouranton@irisa.fr

Versatile Scenario Guidance for Collaborative Virtual Environments

Keywords: Virtual Reality, Scenarios, Collaboration

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

In virtual reality, the scenario depicts all the possible sequencing of events allowed in the virtual environment. This description can be more or less rigid depending on its model and the requirements of the simulation. In some cases, the actions are defined step by step. The actor, a character driven by either a user or an autonomous agent system, has limited choices and must follow the scenario step by step. It is generally the case of VR applications dedicated to the training to industrial or surgical procedures. The scenario can also be depicted as a set of rules that describes how the actors have to behave, without much more guidance. This case is widely spread in storytelling where the focus is made more on the characters than on the sequencing of the events. Once defined, the scenario is loaded in a component of the virtual reality system: the scenario engine. The engine uses the scenario to modify the virtual environment and to adapt its inner state to the obtained reactions.

In the context of the development of a virtual reality application framework, we need a model that fits in any simulation where the scenario is a key point. Thus, we do not make any assumption about the purpose of the simulation or its application domain. Furthermore, the events occurring in it are not defined either. The purpose of the simulation also defines the level of guidance provided by the scenario. As an example, if the simulation focuses on the training to a procedure, the scenario may guide the user step by step in his or her actions. It could also wait for the environment to reach specific state to notify the achieve-ment of a goal. Two different scenarios can be applied to a unique virtual environment to provide a version of the simulation with guidance to train the user and a second version without guidance to test his or her training. Finally, the simulation could involve more than one actor. To provide a more accurate model of multi-actor social situations, especially collaboration, we decided to base our work on the role theory [START_REF] Biddle | Role theory: concepts and research[END_REF].

Based on these needs, we have addressed a list of features our ideal scenario model must provide:

• No specific types of events

RELATED WORK

In this section, we present existing work on scenarios for virtual environments. The first two parts are focused on an overview of this work. We then study some of them through the criteria proposed in section 1. In the remainder, we call 'actor' an avatar interacting in the VE and controlled by either a user or an artificial intelligence.

Emerging Scenarios

Emerging scenario models aim at leaving more freedom to the actors. They define a set of rules, to constraints actors behaviour, that can evolve with time depending on the actors actions and on the state of In VRaptor [START_REF] Shawver | Virtual actors and avatars in a flexible user-determined-scenario environment[END_REF], the scenario emerges from the behaviour of the virtual humans and from the actions (not constrained) of the user. In Facade [START_REF] Mateas | A behavior language for story-based believable agents[END_REF], story elements (beats) describe the behaviour of the agents and are designed to respond to the user behaviour in an appropriate manner. [START_REF] Cavazza | Madame bovary on the holodeck: Immersive interactive storytelling[END_REF] proposed a system where the behaviour of the agents is driven by their feelings. The actions of the actors have a set of preconditions and a set of effects on these parameters.

In the remainder, we will not focus more on this kind of scenario engine as we want to focus on the sequencing of the event and on the scenario itself.

Predefined Scenarios

Predefined scenario engines depict all the possible sequencing of events that may occur in the simulation. Some of them could be limited to a unique execution. In EMSAVE [START_REF] Vidani | Using a task modeling formalism in the design of serious games for emergency medical procedures[END_REF], the actor has several choices during the simulation, but only one is actually able to unfold it. More complex engines describe several possible sequencing of the events that can occur during the simulation. LORA++ [START_REF] Gerbaud | Virtual environments for training: From individual learning to collaboration with humanoids[END_REF], the StoryNets of MRE [START_REF] Swartout | Toward the holodeck: Integrating graphics, sound, character and story[END_REF], or HAVE [START_REF] Chevaillier | Semantic modeling of virtual environments using mascaret[END_REF] are based on automata and are able to express intricate sequencing of the events.

Predefined scenario engines are generally used for scenarios with a small amount of alternatives. They are reliable when the main concern is to guide the actors through a specific task or story but they generally reach their limits when they are used in a VR system that needs more freedom.

Modelling of events

To be able to adapt itself to the evolution of the simulation, the scenario engine must be able to perceive the changes occurring in the environment. In many environments, the more common events are the actions of the actors. LORA++ relies on the model STORM [START_REF] Mollet | Storm: a generic interaction and behavioral model for 3d objects and humanoids in a virtual environment[END_REF], able to model collaborative actions. HAVE, a language extended from the UML activity diagram, relies VEHA [START_REF] Chevaillier | Semantic modeling of virtual environments using mascaret[END_REF] (also an extension of UML) describing the behaviour of the objects in the environment. Other ways to model events can be found in the literature, even if they are not directly connected to scenario models. The work of [START_REF] Willans | Verifying the behaviour of virtual environment world objects[END_REF] proposes to model the behaviour of the objects in the VE using Petri nets. [START_REF] Lugrin | Making sense of virtual environments: action representation, grounding and common sense[END_REF] propose an interaction model based low level physical events sequences recognition.

Guidance Level

The guidance level of the scenario defines how free is the actor to act at a specific point of the simulation. As stated before, in EMSAVE the actor can only perform only one action. Even if the system offers multiple choices, only one of them will truly affect the virtual environment. Others will simply provide knowledge to the user about why they are not the good option. As they are based on automata, LORA++, HAVE and StoryNets give more freedom to the user. However, LORA++ is specialised in procedural training and the actors are not supposed to do nothing but following the procedure. HAVE proposes an ideal scenario with goals to reach but the actors are free to act as they wish, even not following the scenario. StoryNets offer nodes where the actor is free to act. These nodes are linked together with scripted phases (as in video games cut-scenes). The choice of one link before another depends on what has append during the free phases. However, the user can not intervene in the cut-scenes.

Role Modelling

The role theory [START_REF] Biddle | Role theory: concepts and research[END_REF] defines the role of a person as what he or she can do, and what he or she has to achieve in regard of a situation and in a specific social context. This definition helps to describe multi-actor organisations such as team work.

In virtual reality, this definition fits well to collaborative virtual environments. The "can do" part of the theory defines the actions an actor can execute in regard of the simulation state. The "has to achieve" part matches to the goals the actors have to reach (alone or collectively).

LORA++ uses roles to define the actions an actor can execute in the virtual environment. This expression of role matches partially with the role theory but lacks dynamic evolution at runtime and goal definition. HAVE defines roles as classes where the possible actions are depicted as well as the goals. These roles are then used as regular UML activity diagram's partitions. The roles are given to users. However, the roles do not seem to evolve during the simulation.

Synthesis

In the literature, we have not found a scenario model that fits with all of our criteria (see table 1):

• Types of events: Each model is tightly related to another model used to express interaction (LORA++ and STORM) or behaviour (HAVE and VEHA) or to specific kinds of actions (speech recognition for StoryNets or "Go forward" command for EMSAVE).

• Level of guidance: Each of them has a specific level of guidance (from very limited (EMSAVE) to totally free (HAVE)). But none of them is able to adapt itself, making them restricted to specific simulations.

• Role theory: The role theory is not applied or only partially (LORA++ and HAVE) In this section, we present our scenario model for virtual reality applications. Its main concerns are:

MODEL OVERVIEW

• Intricate event sequencing,

• Adaptability to any kind of virtual environment regardless of the event model,

• Complete expression of roles,

• Consistency between the parameters in a sequence of events

We aim at providing a solution to problems common to scenarized virtual environments. However, problems raised by technical or applicative contexts are handled by a set of tools used by our model. If needed, new tools can be defined by the user.

Model Basis: Sequencing and Adaptability

The event sequencing is handled by using safe Petri nets [START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF]) as a base model. We have decided to use Petri nets above state machines because the latter lacks in expressiveness for parallelism. It can be an issue to model partial ordering in the events. Furthermore, Petri nets have been widely studied and extended in the literature. Using Petri nets in Virtual Reality systems is not new. As an example, Smith and Duke [START_REF] Smith | The hybrid world of virtual environments[END_REF] have applied them to interaction.

The transitions, modelling the events in Petri nets, are completed using two entities, the sensor and the effector (see figure 1). Sensors are the input part of the model. Their job is to wait for specific conditions to be reached. As an example, this condition can be that a specific action has been executed or that a variable in the environment reaches a value. When the condition is met, the transition related to the sensor is triggered. Effectors are the output counterpart. They run a defined behaviour when the related transition is triggered. As an example, a specific type of effectors can be used to modify the roles of the actors in the environment or to start the execution of a script. The sensor and the effector offer to extend the model to be able to adapt it to any kind of event modelling. As an example, a specific type of sensor can be defined to detect low level physical events modelling of actions as proposed by Cavazza et al. [START_REF] Lugrin | Making sense of virtual environments: action representation, grounding and common sense[END_REF] and an other can be created to match with STORM [START_REF] Mollet | Storm: a generic interaction and behavioral model for 3d objects and humanoids in a virtual environment[END_REF].

Roles description

In order to fit with role theory, we have embedded in our model the ability to give a fine-grained description of the actions related to roles. Furthermore, these descriptions of roles can be changed dynamically. The role of the actors is expressed by using an element called the attribution. Each transition of the scenario can be labelled by any number of attributions. Each actor possesses a subset of the attributions used in the scenario. An actor is only able to see the transitions of the scenario labelled by its own set of attributions. Using this feature, the role of an actor is defined by it own set of attributions. More complex conditions can be expressed by this feature. It is possible to allow an actor to view a transition only if he or she has an expected combination of attributions. For example, a transition can only be seen by an actor if he or she has the attribution a and b but not c.

Our model expresses goals by a specific subset of the places, called final places, which needs to hold a token all at once. This set defines a subset of the markings state that, if one of them is reached, the scenario is considered as a success. Another subset of the places, called initial places, defines the initial marking of the scenario. We have also defined that a place can contain a scenario. When a place containing a scenario receives a token, the inner scenario receives a token on all of its initial places. When a final marking is reached, the place is considered as holding a token by the downtream transitions. Using this feature, it becomes possible to express intermediate goals.

Activity Consistency

As multiple users can have access to the same subnet, one issue left is to maintain the consistency of the parameters in a specific sequence of events. It is achieved by giving transitions the ability to manipulate data stored in the tokens of the Petri net. These data are then used by the sensors when they check that a transition can be triggered or not.

In the remainder of this paper, we call "Activity Continuum" a subnet in which parameters of the events are consistent. For example, if the author of the scenario needs to restrict a sequence of action to the user that started it, the first transition has to store the identity of the actor on the token. The sensors in the continuum then check the identity of the actor and refuse to any other the triggering of a transition. Other use of this feature can be applied to multiple parameters.

Deadlocks

Deadlocks are a common problem in many systems. In our case they mean that, given the current marking, it does not exist a sequence of events that leads to a final marking. This reachability problem is widely treated, and solved, for Petri nets in the literature [START_REF] Mayr | An algorithm for the general petri net reachability problem[END_REF]. Once the deadlock is detected, solutions can be to prevent the activation of transitions leading to the deadlock or reloading the environment and the scenario to a previous state if a deadlock is reached.

Comparison with a standard: UML Activity Diagrams

UML Activity Diagrams (UAD) may be seen as sufficient to express Collaborative Virtual Environment scenarios. They are inspired by Petri nets, model concurrency or dispatch the activity between the different stakeholders of a process [START_REF] Fowler | UML distilled: a brief guide to the standard object modeling language[END_REF].

As they are not a scenario model, many of the problems may need a specific solution instead of using generic and reusable components. An example will be the use of a tool. In our model we can express the ability given by a tool to its wielder using assignments. UAD will require to manipulate a specific data structure and to test it each time an action requires this ability. The modelling of several stakeholders is also limited. It will be difficult to distinguish the actors from their roles. Furthermore, UAD do not provide any built-in means to express dynamic changes on the attributions of the roles.

MODEL FEATURES

In this section, we detail three features of our scenario engine with different cases:

• Different usage of roles: case of the access to actions

• Expressing constraints on the parameters of a sequence of events: case of the identity of the actors

• Using assignments to model an ability: case of the usage of tools We have integrated our model in a CVE for the training to a procedure. Our objective is to demonstrate that, with only small changes in the scenario, we can easily affect the behaviour of the actors and the unfolding of the simulation. These changes could consist to add or remove a transition at a specific point of the scenario, changing the initial attribution of the roles of the actors or adding an activity continuum on a sub-scenario. • Take/Install the new wheel Furthermore, the procedure implies some constraints:

Use Case

• The screws can be removed in any order

• The screws must be screwed crosswise based on the first screw but without constraints on the choice of this screw • The only way to act upon screws is to possess a screwdriver. In the following sections we add constraints based on the goals of the simulation. It will impact the scenario without changing the unfolding of the procedure.

We mainly use one type of effector and one type of sensor in our application. The type of the sensors is "Action sensor". They aim at triggering the attached transition when a specific action is executed by an actor. The type of the effectors is "Actor Assignments Modifier". They add or remove assignments to an actor that triggers the related transition. The roles of the actor is defined using a set of assignments described in Figure 3.

Role modelling

In our scenario, we have defined three roles: "Screws manager", "Old-wheel manager" and "New-wheel manager". In addition, we have used the assignments to express the fact that a user must have the hand free to take an object (the screwdriver or one of the wheels). It is consistent with the role theory as, if an actor has his or her hand free, one can expect him or her to execute specific actions.

Our first use case uses one specific scenario but with two different sets of default roles (see figure 4): • In the first set, a unique role is assigned to all users. Each user is able to execute any steps of the procedure. • The second set specifies three different roles (old wheel responsible, new wheel responsible and screwer). Each role is necessary to achieve the scenario. The second set constrains users to have more specific activities during the simulation. It implies that the simulation must be executed with at least three actors (one for each specific role). The first set allows the scenario to be executed with one actor. Obviously, one can define others sets of roles (e.g. "screwer" and "wheels responsible"). Changing this configuration has no impact on the writing of the scenario itself. It is achieved by changing on the initial attributions of the actors. Thanks to our model, we can achieve several different simulations using the same scenario. A video showing an execution of this case can be found at https://vimeo.com/109443535

Activity Continuum

In the real world, stopping an on-going activity and leaving someone else dealing with it is possible most of the time. However, it is generally not the most efficient way to handle things. Usually, the person that starts the activity drives it to its term. It is mainly due to a desire of saving time or energy. While writing a scenario for a CVE, the author may want to express one case or another. In this section we propose the two ways to express a unique scenario.

The first scenario is dedicated to freedom of action. Any actor with the correct assignment combination is able to execute an action. The second scenario, using the activity continuum feature, aims at being closer to the more efficient way to execute the procedure. When an actor execute the first action of the sequence, he or she becomes the only actor able to trigger the downstream transitions up to the last action of the sequence.These two scenarios are opposed in their objectives. Using our model, there is only little changes between the two. In Figure 5 the activity continuum is modelled by the the grey area that links all of the transitions. A video showing an execution of this case can be found at https://vimeo.com/109446234

Tool Usage

In this use case, we focus on how to model the necessity to use a tool in the scenario. We consider the tool as an element giving a specific ability to its owner. In our case, possessing the screwdriver allows an actor to act upon the screws. In this section, we confront two different solutions, among others, to solve this problem. In one of our solution (see Figure 6), the actions to take or put back the tool are integrated as, respectively, first and last steps of the activity. These two actions are fully synchronized with the main part of the activity. Our second solution uses two Petri nets: one is used to express that an actor can take or put back the tool and the other is the activity itself. In this second case (see Figure 7), the actor can take or put back the tool at any time and any actor holding a screwdriver can continue the activity. This solution decorrelates the actions on the tool and the actions on the screws.

The two solutions have a different level of guidance and realism. The first solution restricts more the actions of the actor, focusing on a specific sequencing. The second solution offers more freedom to the actor. He or she can take or release the screwdriver at any moment of the activity. However, without the tool the actor is not able to perform any screwing ac-

Open scenario

Finally, our model can be used to only express constraints on the environment, such as the old wheel must be removed to put the new one, without guiding the actors in the sequencing of their actions. In our previous examples, the scenario guides the actors through the procedure. Here, the scenario defines constraints between the actions and the goal to reach (via the final places). The Figure 8 shows a part of this scenario. This approach is more suited to specific cases such as the evaluation of the users after being trained using one of the previous scenarios. It can also fit to model the interaction constraints in an open world (or sandbox) virtual reality application. We can notice that this scenario is really close to those providing more guidance. In fact, we have reused many of the components.

Combining the two approaches is also possible, thanks to the flexibility of our model. As an example, one can write scenarios with multiple levels of guidance depending on the steps of the simulation.

Synthesis

Our model allows a scenario to be reused to match changes on criteria such as the purpose of the simulation or the degree of expertise of the a user. Furthermore, It can be achieved thanks to small alterations on the scenario. An other example of the use of our model can be found in [START_REF] Claude | Short Paper: #SEVEN, a Sensor Effector Based Scenarios Model for Driving Collaborative Virtual Environment[END_REF].

CONCLUSION AND FUTURE WORK

In this paper we have depicted the features of our scenario engine model:

• Its ability to be connected to any type of events or virtual environments • The possibility to express intricate scenarios

• The freedom given to the author to define the guidance level • The expressiveness of the dynamic role modelling based on the role theory • Its ability to maintain consistency in the parameters of sequences of events However, our expression of the role theory is not yet complete. Currently, the expression of goals is limited to common goals (intermediate or not). Currently, our model misses the ability to express role related goals. An other main issue left is to detect deadlocks even in parametrized events. Even if the scenario allows to trigger an event, it is possible that the related condition is never be reached in the environment.

AKNOLEDGMENTS

This publication is supported by the S3PM project of the CominLabs Excellence Center. The prototype has been developed with the help of Thomas Boggini, Julian Joseph and Rozenn Bouville-Berthelot.

Figure 1 :

 1 Figure 1: Use of Petri nets to interact with the virtual environment.

Figure 2 :

 2 Figure 2: Our Virtual Reality Application

Figure 3 :

 3 Figure 3: Assignments are a fine grain elements composing roles. Our VR application aims to train the users to change the wheel of a car. The procedure, and our scenario, is defined by four steps: • Unscrewing the four screws • Removing the old wheel • Installing the new wheel • Screwing back the screws To achieve this procedure, we propose eight actions to the actors in our Virtual Environment: • take/release a screwdriver • Screw/Unscrew a screw • Remove/Release the old wheel

Figure 4 :

 4 Figure 4: In the first set, each user has the same role. In the second set, specific roles have been created for each task of the procedure.

Figure 6 :

 6 Figure6: In this scenario, the actor must take the tool just before using it.

Figure 7 :

 7 Figure 7: In this scenario the actor must have the right tool to execute specific actions, but there is no constraint on how he has acquired it.

Figure 5 :

 5 Figure 5: Using the activity continuum (grey area) feature, only the actor that has started the activity is able to finish it.

Figure 8 :

 8 Figure 8: A part of the non-guided version of the scenario.

Table 1 :

 1 Synthesis of several Scenario model features

		Events	Guidance	Role
	Emergent models	actions of actors	none	Movie like
	EMSAVE	"Go forward" notification	static	none
	LORA++	STORM only	specified paths	static, describe actions
	HAVE	VEHA only	goals to reach	static, actions and goals
	StoryNets	Predefined events	static story elements	none
	the virtual environment. The sequencing of the events
	is a consequence, not controlled by the author.