Harri Siirtola
email: harri.siirtola@cs.uta.fi

Kari-Jouko Räihä
email: kari-jouko.raiha@cs.uta.fi

Using Gaze Data in Evaluating Interactive Visualizations

Evaluations have long been missing or imperfect in a publication presenting a new visualization technique, but proper evaluations are now becoming a standard. There are many reasons for the reluctance of evaluating visualization techniques, including the complexity of the task and the amount of work required. We propose a simple evaluation approach that consists of a set of tasks carried out in an experimental setting coupled with eye tracking to approximate the focus of the user's attention. In addition, we discuss three methods to visualize the gaze data to gain insight into the user's attention distribution, and show examples from a study where a parallel coordinate browser was evaluated.

Introduction

Evaluation of interactive visualizations is a challenging task. This is easy to verify by observing the attention it is given in the literature, and the number of workshops, panels, sessions, and keynote speeches dedicated to it. The complexity of evaluation comes from the large number of factors that affect how a particular technique performs. These factors include interplay of the user's internal models, perceptive processes, interpretations, and cultural elements [START_REF] Spence | Information Visualization -Design for Interaction[END_REF]. It is often difficult to cancel out even some of these factors which leads to hard-to-analyze experimental results.

The lack of evaluation is a serious problem in visualization research. Often the published ideas are visually or technologically interesting, but the lack of evaluation leaves it open if they are actually useful. Ellis and Dix [START_REF] Ellis | An explorative analysis of user evaluation studies in information visualisation[END_REF] did in 2006 a survey of 65 papers describing a new visualization application or technique, and found that only 12 of them had any kind of evaluation at all, and of those 12 evaluations only two were of any use! This is clearly a problem for the visualization community since development of visualization techniques should be based on experiences from prior work.

The proposed evaluation methods for interactive visualizations vary a great deal. In one end we have recommendations to perform longitudinal and extensive in-depth user studies, and in the other end there is an exasperated demand to "try it at least by yourself." Somewhere, between these two extremes, there must be an approach that is both practical and acceptable to the community.

In recent years the eye tracking technology has become affordable and is now considered as standard in usability testing [START_REF] Nielsen | Eyetracking Web Usability[END_REF]. When the early usability methods used video taping of the computer screen and test participant in analysis, it is now possible to overlay the screen recording with the test participant's gaze path. This is immensely useful in analyzing interactive visualization techniques as well, because when a person maintains her gaze on a single location for a certain period of time, it can be used as an approximation of the person's focus of attention [START_REF] Posner | Orienting of attention[END_REF]. Without this information it is really hard to say if the user's attention is drawn to the relevant, task-specific parts of the visualization.

The main hindrance in using eye trackers in evaluation is the sheer volume of data they produce. Unless the analyst is willing to watch all the gaze-overlaid videos and transcribe the events, the data must somehow be abstracted, summarized and visualized to allow the analysis. Analyses of usability tests often abstract the data into heatmaps that do reveal the highly useful overview of gaze behavior, but abstract away much of the gaze data. In the evaluation of interactive visualizations a bit more detail is often desired.

In this paper we consider a number of methods to abstract the gaze data for the analysis of interactive visualizations. The following approaches to represent the gaze data are explored:

-Heatmaps of fixations -Proportion of time spent on Areas-Of-Interest (AOIs) -Transitions between AOIs Each of these approaches provide a different view of how a visualization performs. In Section 4 we introduce a parallel coordinate browser and its evaluation data that is used as material in examples.

Related work

Saraiya et al. [START_REF] Saraiya | An insight-based methodology for evaluating bioinformatics visualizations[END_REF][START_REF] Saraiya | An insight-based longitudinal study of visual analytics[END_REF] discuss the limitations of using a short-term controlled experiment to study interactive visualizations and present an "insight-based longitudinal method" for evaluation. They argue that the evaluation should cover the entire analysis process from a raw data set to the insights sought from the data. In similar vein, Shneiderman and Plaisant [START_REF] Shneiderman | Strategies for evaluating information visualization tools: multi-dimensional in-depth long-term case studies[END_REF] propose a method titled "multidimensional in-depth long-term case study (MILC)" which is based on a vast array of methods applied in a longitudinal study.

Isenberg et al. [START_REF] Isenberg | Grounded evaluation of information visualizations[END_REF] propose a "grounded evaluation" method that uses qualitative data to "ground" the evaluation to the correct context of the intended use of the visualization technique. They advocate application of qualitative methods early on and through-out the entire development life cycle, and greater sensitivity to context.

In addition to the MILC approach, the other publications and position statements from the BELIV workshops ("Beyond time and errors: novel evaluation methods for information visualization") [START_REF] Bertini | Beliv'06: beyond time and errors; novel evaluation methods for information visualization[END_REF][START_REF] Bertini | Beliv'08: Beyond time and errors: novel evaluation methods for information visualization[END_REF] are relevant as well. Andrews [START_REF] Andrews | Evaluation comes in many guises. BELIV'08: BEyond time and errors: novel evaLuation methods for Information Visualization[END_REF] gives a clarification of different flavors of evaluation and discusses which method is applicable in which phase of the development cycle. O'Connell and Choong [START_REF] O'connell | BELIV'08: BEyond time and errors: novel evaLuation methods for Information Visualization[END_REF] stress that the evaluation should be based on large, realistic data sets and tasks, and advocate the user-centered approach to evaluation. Robertson [START_REF] Robertson | Beyond time and errors -position statement. BELIV'08: BEyond time and errors: novel evaLuation methods for Information Visualization[END_REF] stresses the importance of ecological validity, both in tasks and in the choice of participants.

Eye tracking has a long history in evaluating eye movements for a variety of visual inspection tasks [START_REF] Goldberg | Computer interface evaluation using eye movements: methods and constructs[END_REF]. The richness of the data brings with it an added challenge: which metrics to use for evaluating the data and the interaction with the application? Jacob and Karn [START_REF] Jacob | Eye tracking in human-computer interaction and usability research: Ready to deliver the promises[END_REF] list more than ten possibly useful metrics, each fit for and used in for various purposes in varying contexts. For a researcher mainly interested in the interactive visualization and not on the analysis tool, finding the right analysis metric can be a challenge. Systematic, standardized approaches would be desirable.

In keeping with the tradition of the visualization community, to make sense of the gaze data one should naturally try to find suitable visualizations of it. Ramloll et al. [START_REF] Ramloll | Gaze data visualization tools: Opportunities and challenges[END_REF] address the challenges and opportunities in designing gaze data visualization tools. Various tools have since been produced by eye tracker vendors and by researchers (e.g., [START_REF] Špakov | iComponent -Device-Independent Platform for Analyzing Eye Movement Data and Developing Eye-based Applications[END_REF]). This paper builds on the existing tools by proposing a method suitable for analyzing interactive visualizations.

Evaluation method

The proposed evaluation approach can be seen as an extension of what North [START_REF] North | Visualization Viewpoints: Toward measuring visualization insight[END_REF] suggested in his column about measuring "insight generation." Our approach has two elements:

1. Artificial tasks that simulate the true tasks; 2. Approximation of visual attention by eye tracking.

North suggested that (1) should include both simple benchmarking tasks and more complex, open-ended tasks. The former allow us to check the performance of low-level mechanics of the visualization, and the latter bring at least some ecological validity to the evaluation. The open-ended tasks are highly useful as post-test interview material as well. The "artificiality" of tasks means that they can be real tasks, if possible, but often we need to resort to something that is only mechanically close to the real ones.

The second element [START_REF] Ellis | An explorative analysis of user evaluation studies in information visualisation[END_REF] proposes that we use eye tracking data to inspect where the user is looking at while using a visualization. An eye tracking device captures participants' gaze data, especially their fixation targets and lengths. A fixation occurs when the person maintains his or her gaze on a single location for a certain period of time, and it can be used as an approximation of the person's focus of attention. The rapid transition between fixations is called a saccade, and no visual percepts accumulate during the saccades.

These elements are combined in a controlled experiment that provides both quantitative (task execution time, correctness, gaze distribution) and qualitative (observation, think-aloud protocol, interview) data about the visualization. While this data may often be quite noisy, it is highly useful when comparing two designs or when trying to understand why a certain visualization performs as it does.

We believe that the "light-weight" or "discount" evaluation method proposed here might be a good tradeoff which reveals enough about the evaluation target to draw informed conclusions. Depending on whether the main interest is in quantitative or qualitative information, the elements (such as think-aloud and eye tracking) may be combined in different ways [START_REF] Hyrskykari | Gaze path stimulation in retrospective think-aloud[END_REF], lending flexibility to the approach.

Evaluating Parallel Coordinate Explorer

Evaluation of Parallel Coordinate Explorer (PCE) [START_REF] Siirtola | Direct manipulation of parallel coordinates[END_REF][START_REF] Siirtola | Direct manipulation of parallel coordinates[END_REF] is used as an example to illustrate how gaze data helps in studying interactive visualizations. This particular implementation was chosen because there are several studies of it, its strengths and weaknesses are well known, and we recently redid one of the studies by adding gaze tracking to the experimental setup [START_REF] Siirtola | Visual perception of parallel coordinate visualizations[END_REF]. The implementation of PCE is available on the web [START_REF] Siirtola | Parallel Coordinate Explorer[END_REF] as well.

PCE is a parallel coordinate browser that allows users to interact with a parallel coordinate plot by creating and modifying persistent selections. These selections highlight the lines that fulfill the constraints that can be combined with logical connectives (AND, OR, XOR).

Figure 1 shows a typical interaction with PCE. Suppose the task is to find the most powerful four-cylinder car in the data set (i.e., its engine having the highest horsepower value). The four-cylinder cars have been highlighted (constraint on axis CYL), another constraint on axis HP focuses the selection on the cars with high engine horsepower, and one of the cars in the selected set has been drilled down (the values are displayed under the axis bottom labels in red). The end-points of an axis show normally the minimum and maximum values of the corresponding variable, but change to display in red the minimum and maximum of a constraint if there is exactly one range selection on the axis.

The details of the experimental setup and the results are presented in Siirtola et al. [START_REF] Siirtola | Visual perception of parallel coordinate visualizations[END_REF] and only the nine tasks are given here: 0. How many American cars are there in the data set? 1. How many cars have a four or six cylinder engine? 2. What is the average mileage for the six-cylinder cars? 3. How would you describe the cars that weigh over 4500 pounds? 4. What is the origin of the six-cylinder cars that were manufactured in 1971? 5. Which Japanese cars have the best acceleration? 6. What else is common to the most powerful, best accelerating, and heaviest cars in the data set? 7. How many non-American cars are there in the data set? 8. What is the most common number of cylinders for cars manufactured in 1973?

There are three distinct task types: simple selections, complex selections, and explorative tasks. All tasks except 3 and 6 had an unambiguous answer. Task 0 was always performed first as a practice task but the participants did not know about this.

Here we will focus on the approximation of visual attention by visualizing gaze data. The other elements of evaluation mentioned in Section 3 (task execution measurements, live observations, think-aloud, and interviews) are similar as in any usability test [START_REF] Nielsen | Usability Engineering[END_REF], and an example of applying them in the evaluation of an interactive visualization can be seen, e.g., in Siirtola et al. [START_REF] Siirtola | Interacting with parallel coordinates[END_REF].

The following sections will show what kind of observations about an interactive visualization tool can be made by abstracting and visualizing the fixations and saccades of evaluation participants. In the following, the gaze data is represented as heatmaps of fixations, as balloon plots of attention proportions, and as gaze transitions between areas of interest.

Heatmap-based observations

The most popular approach to visualize fixation data is to ignore the order of the fixations completely and to base the analysis on how long the gaze has been fixated on different areas of the screen. Here "long" can mean either number of fixations or total duration of fixations in the area. Long fixations are usually an indication of increased cognitive processing, and a high number of fixations suggests problems in the visual search. By smoothing the data appropriately and encoding it with different levels of gray or color, the interest or attention can be visualized in a style familiar from maps. Such visualizations have been called "attentional landscapes" [START_REF] Pomplun | Disambiguating complex visual information: Towards communication of personal views of a scene[END_REF] and "fixation maps" [START_REF] Wooding | Fixation maps: quantifying eye-movement traces[END_REF]. The most common term for this concept nowadays is "heatmaps" or even "attention heatmaps".

Figure 2 shows the heatmap of task 4 for a single participant where the objective was to find the origin of six-cylinder cars manufactured in 1971. Solving the task requires making a selection with two constraints, one on the CYL axis that selects the six-cylinder cars, and another on the YEAR axis that further prunes the selection to cars that were manufactured in 1971. With this selection it is easy to verify that those cars were manufactured in the U.S.A. In (the color version of) the figure the number of fixations is encoded ranging from green to red via yellow, green being the lowest number of fixations observed and red being the highest. There are two red "peaks" in this landscape in the bottom of axes YEAR and ORIGIN (appearing darker in grayscale). One might expect that there should be three peaks, one for each selection and one for reading the result. It appears that this particular participant had problems making the selection for year 1971 and also spent a relatively long time verifying the result. Making the selection from the YEAR axis is more difficult than making the selection from the CYL axis because of the higher number of items which translates into lesser space to mouse the selection.

Figure 3 shows the heatmap of task 4 for all participants. The overall situation appears more like expected -there are three distinct peaks for the task-critical areas, and the trickiest selection has received most of the attention. In addition, it seems that the participant of Figure 2 remembered the location of axes CYL and ORIGIN, but some of the participants had to scan the axes names to locate them (indicated by the light green color over the axis names).

Heatmaps are good for summarizing large quantities of data that would be next to impossible to gain insight into if presented numerically. Sometimes, as in the example above, heatmaps may give useful insight into the distribution of users' attention, especially if the task at hand is focused and simple enough.

Heatmaps are typically used in single-condition situations, or in multi-condition experiments without tests for statistical significance. Therefore heatmaps should primarily be used for data visualization instead of data analysis [START_REF] Bojko | Informative or misleading? Heatmaps deconstructed[END_REF]. In addition, the heatmaps often do not come with all the relevant metadata, and being unaware of it can lead into false interpretations. Another issue is the attractiveness and apparent intuitiveness of heatmaps which can lead into over-interpretation.

Proportion of time spent on Areas-of-Interest

The heatmap-based analysis of fixations can be made more detailed if we divide the underlying visualization into "Areas of Interest (AOI)", basically by naming the parts of the visualization that are of interest. In many visualizations we have at least some static elements in the interface that allow to track when the user's gaze is fixated into them. If the visualization does not have any static elements at all, it is still possible to compute the fixations for dynamic elements, but it will be a technical challenge. In PCE, the only dynamic parts of the visualization are the selection constraints, making it easy define the AOIs. Figure 4 shows the AOI definitions that were used in the experiment [START_REF] Siirtola | Visual perception of parallel coordinate visualizations[END_REF]. area is named in Figure 4 after the axis and divided into three parts: top of the axis (1), axis itself (2), and bottom of the axis (3). For instance, for the first vertical axis from the left (CAR), CAR.1 refers to the area enclosing axis label and the maximum value, CAR.2 to the axis itself, and CAR.3 to the mimimun value and the selected value, if one polyline is chosen. Figure 4 shows in addition a visual query where all the six-cylinder cars have been highlighted (triangles at the CYL axis) and the one with the smallest engine displacement has been selected (a Volvo diesel, values shown in red below the labels of the axes).

Dividing the user interface of PCE into AOIs allows to list the areas that must be attended to solve a task. For example, solving task 0 ("How many American cars are there in the data set?") requires looking into the areas TASK (to read the task), ORIGIN.2 and ORIGIN.3 (to find and select "American" cars), and MENU (to read the number of selected cars). This is the optimal course of events which is rare in a real first-use situation. However, the comparison makes it easier to evaluate the design and implementation of a visualization by revealing which proportion of fixations is spent on the areas that are relevant in carrying out the task.

Figure 5 shows two balloon plots of the fixation data (produced with the package gplots of statistical system R [START_REF] Development | R: A Language and Environment for Statistical Computing[END_REF]). In a balloon plot each cell contains a dot whose size reflects the relative magnitude of the corresponding component. The left-hand side plot shows the medians of fixations before entering an AOI, and the right-hand side plot shows the fixation duration means in an AOI. On the left, the grey background in a cell indicates an AOI that must be first attended to solve a task, and on the right the grey background shows all the cells that must be attended in a course of the task. Therefore, to approach the optimal solution, on the left a smaller value on grey background is "better" and on the right a bigger value on grey background is "better". In the experiment [START_REF] Siirtola | Visual perception of parallel coordinate visualizations[END_REF], the percentage of time spent on task-specific AOIs varied between 53% and 92%. The lowest percentages were observed on two open-ended tasks (3 and 6, 53% and 58%, respectively) and on the task with a complicated selection (task 4, 55%). The left balloon plot in Figure 5 shows the medians of fixations before entering the respective AOI and indicate that the important areas were found quickly (the balloons with grey background are small). The right side of Figure 5 plots the duration means in an AOI, and shows that the middle part of the axes drew longer fixations than either the top or bottom area. This is caused by the fact that the interactive part in the middle required more intense attention than the (mostly) static values at the ends.

Transitions between Areas-of-Interest

Both the heatmap and the AOI-based visualizations of fixation data ignore the order of fixations completely, which may leave important aspects of interaction unnoticed or even skew the observations. In this third method to visualize fixation data the focus is on the transitions between the Areas-of-Interest. This is a piecewise representation of gaze paths and does not show them as continuous objects as in a video overlay. Instead, the idea is that the relevant parts of the interaction should "pop out" as having more inter-area transitions, providing better insight to the course of events.

The following visualizations were produced by extracting the AOI transitions from eye tracker log files with an AWK [START_REF] Aho | The AWK programming language[END_REF] script that transformed the AOI data into a transition graph defined in the language DOT (part of the Graphviz project [START_REF]Graphviz: Graphviz -graph visualization software[END_REF]). The DOT compiler was then used to lay out and produce an image of the transition graph.

The initial, plain versions of the graphs were hard to read because of the automatic layout. It completely broke the resemblance to the user interface, trashing the mental model for the UI, and made it hard to interpret the transitions. To force the axis AOIs to stay together, they were placed in the same subgraph. Now the Graphviz layout engine may move the subgraphs around, but not the nodes inside them. Figure 6 shows a transition graph for the AOIs shown in Figure 4 with its static elements, without any transitions. As seen in Figure 6, the period in axis names is replaced by underscore to allow indexing of associative arrays with the AOI names. Another change related to the AOIs is that the gaps between the axis AOI's (as defined in Figure 4) were removed to prevent frequent transitions to and from the AOIs to areas that do not belong to any AOI.

To reduce visual clutter in the transition graphs two additional encodings were introduced. Repeated transitions between two AOIs are represented as a single connection line and the number of transitions is encoded into the line width. In addition, the overall fixation time of an AOI is encoded into the line width of a node symbol. A dashed line is used to indicate a single transition and an AOI without any fixations.

Figure 7 shows a single user's transition graph for task 4. The focal point of attention is in the middle part of the YEAR axis, YEAR 2, which has the highest duration of fixations as indicated by the bold border of the node. As noted previously, it is a challenge to select one of the twelve items from a crowded YEAR axis. A similar selection from the five-value CYL axis is easier, and this participant does not even bother to check the lower limit of selection at all (no fixations in CYL 3). The inter-AOI transitions are mainly between ORIGIN, YEAR, and TASK. This participant chose first the six-cylinder cars, then the year 1971, and finally read the selection from the ORIGIN axis. There are several confirmatory YEAR-ORIGIN and ORIGIN-TASK transitions. Overall, the attention is where it is supposed to be when solving this task.

Figure 8 shows a transition graph of task 4 for all participants. Overall, the selection problem on the YEAR axis receives the most of the attention, but beyond that the situation is quite even. However, it is clear that the axes CYL, YEAR, and ORIGIN are in the focus as the layout sets them next to each other.

Figure 9 shows a typical single participant's transition graph for an exploratory task, which is here task 3: "How would you describe the cars that weigh over 4500 pounds?" The strategy is to select the cars having WEIGHT over 4500 and then scan the other axes in search of patterns. AOIs WEIGHT and TASK receive most of the attention and transitions. The middle parts of the axes are then attended and occasional drill-down hits the lower part of the axes. No attention is devoted to the axis labels, indicating that this participant knows the variable positions by now.

Discussion

The proposed light-weight evaluation method is proposed as a trade-off between complex methods involving an array of qualitative and quantitative methods applied in a longitudinal study, and simple controlled experiments. The goal is to separate data collection and data interpretation as much as possible, and make the evaluation easier to repeat. When the AOIs are documented and the percentages are printed, the experiment is fairly easy to repeat and verify.

Instead of studying the participants' focus of attention by observation and interviewing, we advocate to use the eye tracking technology for it. What is really needed is "brain tracking", but eye tracking is a substitute while this technology matures. The problem with eye tracking is the amount of data collected even for a modest experimental setting. We discussed three approaches that avoid viewing all the video footage and provide useful visualizations of gaze data instead: heatmaps, AOI-based balloon plots, and AOI-based transition diagrams. These correspond roughly to three more general problem solving approaches: acquir-ing general overview, working top-down, and working bottom-up. Heatmaps are good for giving an overview of how an interface is really used, but on a high level only. The AOI-based balloon plots give a bit more fine-grained insight into how an interactive visualization is used, and the AOI-based transition graphs reveal the most common paths taken while using the visualization.

The proposed approach has the advantage that it is repeatable and, with some practice, can become a technique that is fast for a researcher to use. Eye tracking is, however, no panacea. There are caveats that a researcher should be aware of, such as the inherent inaccuracy of gaze data (the combined effect of tracker inaccuracy and the perceptual span of the human eye can yield offsets of up to 2 degrees of visual angle) and the sensitivity of the results on the algorithm used for estimating fixations [START_REF] Salvucci | Identifying fixations and saccades in eye-tracking protocols[END_REF]. The inaccuracy makes it difficult to apply eye tracking for visualizations that have densely packed information, such as those in Figure 5, though even there focusing on the areas of interest (the grey areas) can make the approach usable. And in many other cases the areas of interest are more sparsely located, such as in our example, or in many timeline visualization.

The proposed evaluation approach is simple and not a substitute to a longitudinal study with real users and tasks. However, we believe that the approximation of users' focus of attention with gaze data analysis is highly useful in revealing the issues that should certainly be addressed before a proposed visualization method is acceptable. The gaze data cannot prove that a certain method is a success, but it is impeccable in pointing out the major design flaws.

In this paper we have applied the proposed evaluation approach into one visualization method and repeated an earlier experiment. In the future, we plan to refine the evaluation method further, do additional experiments, and develop a software tool to streamline the gaze data visualization. In such a tool we could link the two gaze data visualizations which would allow rapid movement between the two views, i.e., spotting an interesting cell in a balloon plot would be a link into the corresponding transition graph and vice versa. One should be able to select and unselect included participants and tasks, and adjust thresholds for the diagrams. This clearly calls for a conventional multiple-view interface with dynamic controls and brushing.

Fig. 1 .

 1 Fig. 1. Interacting with Parallel Coordinate Explorer: finding the most powerful engine among the four-cylinder cars.

Fig. 2 .

 2 Fig. 2. Heatmap of fixation counts for task 4 for a single participant ("What is the origin of the six-cylinder cars that were manufactured in 1971?").

Fig. 3 .

 3 Fig. 3. Heatmap of fixation counts for task 4 over all users.

Fig. 4 .

 4 Fig. 4. Areas Of Interest (AOI) used in the analysis and their naming conventions.

Fig. 5 .

 5 Fig. 5. On the left: balloon plot for AOI by Task: Medians of fixations before entering an AOI. On the right: Balloon plot for AOI by Task: Fixation duration means in an AOI. The mandatory AOIs for a task have a grey background.

Fig. 6 .

 6 Fig.6. Area-of-Interest elements in a transition graph. The subgraph structure constrainsts the nodes inside an axis area to stay together and in the correct order.

Fig. 7 .

 7 Fig. 7. Transition graph for a single user's task 4, "What is the origin of the six-cylinder cars that were manufactured in 1971?"

Fig. 8 .Fig. 9 .

 89 Fig. 8. Transition graph for task 4 over all participants.

Acknowledgements

We thank Tuuli Laivo for collecting the gaze data that was used in our example visualizations. This work was supported by the Academy of Finland (project 1129300). The work of the second author was supported by the Academy of Finland grant 1130044. The paper was written while he was visiting the University of Canterbury in Christchurch, New Zealand.


Sebastian Thelen
email: sthelen@cs.uni-kl.de

Joerg Meyer
email: jmeyer@uci.edu

Achim Ebert
email: ebert@cs.uni-kl.de

Hans Hagen
email: hagen@cs.uni-kl.de

Giga-Scale Multiresolution Volume Rendering on Distributed Display Clusters

Keywords: High-Resolution Displays, Large-Scale Data Sets, Volume Rendering

Visualizing the enormous level of detail comprised in many of today's data sets is a challenging task and demands special processing techniques as well as a presentation on appropriate display devices. Desktop computers and laptops are often not suited for this task because data sets are simply too large and the limited screen size of these devices prevents users from perceiving the entire data set and severely restricts collaboration. Large high-resolution displays that combine the images of multiple smaller devices to form one large display area have proven to be an adequate solution to the ever-growing quantity of available data. The displays offer enough screen real estate to visualize such data sets entirely and facilitate collaboration, since multiple users are able to perceive the information at the same time. For an interactive visualization, the CPUs on the cluster driving the GPUs can be used to split up the computation of a scene into different areas, where each area is computed by a different rendering node.

In this paper we focus on volumetric data sets and introduce a dynamic subdivision scheme incorporating multi-resolution wavelet representation to visualize data sets with several gigabytes of voxel data interactively on distributed rendering clusters. The approach makes efficient use of the resources available on modern graphics cards which mainly limit the amount of data that can be visualized. The implementation was successfully tested on a tiled display comprised of 25 compute nodes driving 50 LCD panels.

Introduction

Many data sets that are acquired in today's applications exceed the computational capabilities of desktop PCs or workstations. The Visible Human Project [START_REF]The Visible Human Project[END_REF], for instance, provides 40GB of data for the female cadaver, thus asking for techniques to process an enormous amount of information. A lot of research has focused on developing methods for handling such large data sets. Solutions include the parallelization of the render process or the invention of level-of-detail or data compression techniques. The benefits of these methods are undeniable, however, one limitation remained for a long time: the visualization of large amounts of information and the advantage of having high-resolution data sets also require a large amount of screen real estate. The pixel count of regular computer monitors is usually too low to display complex data sets at their full level of resolution. For three-dimensional data sets, the gap between the amount of information contained in a partially transparent volume and the available screen space becomes even more obvious. Zooming+panning (e.g., Google Earth navigation) or focus+context (i.e., a highresolution focus view and a low-resolution context view) approaches offer ways to deal with this problem but for some data sets these methods are not appropriate. For instance, such data sets can only be fully perceived when they are displayed entirely. In the last couple of years tiled high-resolution displays have become more and more popular due to advances in display and hardware technology. Tiled high-resolution displays combine the resolution of multiple devices to form one large display area. Two basic approaches have emerged: projectorbased and monitor-based tiled displays. Multiple projectors can be combined to form a projector-based tiled display. The challenge is to calibrate the system, as projector images are usually distorted and non-uniform in terms of color and luminance. LCDs represent the most affordable way to build a large high-resolution display. LCD-based systems are easier to set up since they usually require less space, and problems like lens distortions or mismatches of color temperature and luminance are limited to a minimum. Further, the resolution of today's average LCDs is higher than the one of most projectors, so that it is relatively easy to build systems with a resolution of several hundred megapixels. In this paper we focus on the development of a volume rendering application for large scalar data sets on tiled displays. The display system we work with is a tiled wall consisting of fifty 30 inch LCDs arranged in a 10 × 5 grid. Instead of the traditional isosurfaces, i.e., regions representing a constant scalar value within the data set, we use a direct volume rendering approach based on 3D texture mapping for visualization. The size of data sets that can be visualized on a computer is mainly limited by the available amount of video RAM on the graphics card. Therefore, the main contribution of this paper is the description of a technique that fully exploits the resources of a render node in the display cluster. We combine octree-based out-of-core frustum clipping with a waveletbased multi-resolution representation of the data to increase the visual quality of the renderings. The rest of the paper is structured as follows: Section 2 gives a brief overview of current literature relevant to our work. Section 3 describes the data structure we employ, while section 4 deals with software-and hardware related aspects. In section 5, we introduce the actual method that allows us to visualize high-resolution data sets on large displays, followed by a description of implementational aspects in section 6. Section 7 discusses the results we achieve on our system that are more deeply analyzed in section 8. Section 9 compares our system to other dis-tributed rendering systems. The paper ends with a conclusion and an outlook on future work.

Related Work

In its simplest form, 3D texture mapping is limited by the fact that the original data has to fit entirely into the texture memory of the graphics card. To overcome this limitation, LaMar et al. [START_REF] Lamar | Multiresolution Techniques for Interactive Texture-Based Volume Visualization[END_REF] describe a multi-resolution approach that is based on octree subdivision. The leaves of the octree define the original data and the internal nodes define lower-resolution versions. Artifacts are minimized by blending between different resolution levels. Weiler et al. [START_REF] Weiler | Level-of-Detail Volume Rendering via 3D Textures[END_REF] extend this approach. Their hierarchical level-of-detail representation allows consistent interpolation between resolution levels. The described methods are relevant to our work since we also produce multi-resolution images of the data set. However, in our case multi-resolution refers to the detail levels of tiles within the display wall and not to regions of different resolution within the resulting picture. The techniques above are able to handle data sets that do not fit into the texture memory of the graphics hardware. Nonetheless, data still has to fit into the computer's main memory. The data structure we exploit in this paper has been described by Meyer et al. [START_REF] Meyer | Interactive Visualization of Medical and Biological Data Sets[END_REF]. The authors use a dynamic subdivision scheme that incorporates space-subdivision based on octrees and wavelet compression. It has been used to implement a network-based rendering application that is able to visualize data sets between 20MB and 76GB size by first transferring low-resolution versions of the data via network and then gradually refine them [START_REF] Meyer | Network-Based Rendering Techniques for Large-Scale Volume Data Sets[END_REF]. Plate et al. [START_REF] Plate | Octreemizer: a hierarchical approach for interactive roaming through very large volumes[END_REF] developed the Octreemizer, a hierarchical paging scheme that uses octrees to deal with data sets that exceed the size of RAM. The Octreemizer however only exploits the octree subdivision characteristics without incorporating any data compression scheme. Various attempts have been made to parallelize rendering on a cluster of computers by image-order [START_REF] Palmer | Ray Casting on Shared-Memory Architectures: Memory-Hierarchy Considerations in Volume Rendering[END_REF][START_REF] Amin | Fast volume rendering using an efficient, scalable parallel formulation of the shear-warp algorithm[END_REF][START_REF] Bajaj | Compression-Based Ray Casting of Very Large Volume Data in Distributed Environments[END_REF], object-order [START_REF] Elvins | Volume Rendering on a Distributed Memory Parallel Computer[END_REF][START_REF] Heirich | Scalable Distributed Visualization using off-the-shelf Components[END_REF] or hybrid approaches [START_REF] Garcia | An Interleaved Parallel Volume Renderer with PC-clusters[END_REF]. The aim of these methods is to achieve a speed-up in the rendering process by combining the computational power of a set of computers. Far less research though has focused on utilizing clusters to generate high-resolution results of volume rendered images on high-resolution displays. Vol-a-Tile [START_REF] Schwarz | Vol-a-Tile -A Tool for Interactive Exploration of Large Volumetric Data on Scalable Tiled Displays[END_REF] was able to visualize seismic data sets on the 5 × 3 GeoWall2 [START_REF]The Geowall2[END_REF] display grid at EVL. The authors present a master-slave prototype that uses an MPI-based rendering library and an OptiStore data streaming server. Application specific implementation details are not given. The TeraVoxel project [START_REF] Lombeyda | Scalable Interactive Volume Rendering using off-the-shelf Components[END_REF] founded at the California Institute for Technology was able to interactively render a 256 × 256 × 1024 data set on a 3840 × 2400 display using four VolumePro 1000 cards by employing pipelined associative blending operators in a sort-last configuration, contrary to our sort-first approach. Schwarz et al. [START_REF] Schwarz | Distributed Volume Rendering of Very Large Data on High-Resolution Scalable Displays[END_REF] describe an octree approach for frustum clipping to make better use of system resources without exploiting the power of a multi-resolution wavelet representation and give a comparison of various parallel image-and object-order as well as hybrid volume rendering techniques. QSplat [START_REF] Rusinkiewicz | Qsplat: a multiresolution point rendering system for large meshes[END_REF] is a multi-resolution rendering system for displaying isosurfaces out of point data sets. It also uses a progressive refinement technique but generates images using a splatting approach (see section 5.1). Despite the increasing popularity of high-resolution displays, until today the ultimate general purpose software solution for driving all different types and configurations of displays is still missing. Various commercial and non-commercial software solutions are available, differing mainly in the way they perform distributed rendering and the display configurations they can handle. Distributed rendering strategies were first analyzed and classified by Molnar et al. [START_REF] Molnar | A Sorting Classification of Parallel Rendering[END_REF]. The authors identified three classes of rendering algorithms, characterized by the stage in which geometry is distributed among the nodes (sort-first, sortmiddle and sort-last). Alternatively, distributed rendering can be classified by the execution mode of applications on the cluster [START_REF] Chen | Software Environments for Cluster-Based Display Systems[END_REF]. In master-slave mode, an instance of the application is executed on each node of the cluster, while in client-server mode a client node issues rendering tasks to the render servers via network. A good survey on distributed rendering software was given by Ni et al. [START_REF] Ni | A Survey of Large High-Resolution Display Technologies, Techniques, and Applications[END_REF] and Raffin et al. [START_REF] Raffin | PC Clusters for Virtual Reality[END_REF]. Some of the best known software packages include CAVELib [START_REF]CAVELib Application Programmer Interface[END_REF], VRjuggler [START_REF] Bierbaum | VR Juggler: A Virtual Platform for Virtual Reality Application Development[END_REF], Syzygy [START_REF] Schaeffer | Syzygy: Native PC Cluster VR[END_REF], AnyScreen [START_REF] Deller | A Highly Scalable Rendering Framework for Arbitrary Display and Display-in-Display Configurations[END_REF], OpenSG [START_REF] Reiners | OpenSG: A Scene Graph System for Flexible and Efficient Realtime Rendering for Virtual and Augmented Reality Applications[END_REF], Chromium [START_REF] Humphreys | Chromium: A Stream-Processing Framework for Interactive Rendering on Clusters[END_REF], NAVER [START_REF]IMRC Wiki: The NAVER Framework[END_REF], Jinx [START_REF] Soares | JINX: an X3D browser for VR immersive simulation based on clusters of commodity computers[END_REF] , and CGLX [START_REF] Doerr | [END_REF].

Data Structures

Rendering of large data sets in real time requires data reduction techniques and hierarchical subdivision of the data set. This chapter describes a spaceand time-efficient, combined space subdivision and multi-resolution technique for volumetric data [START_REF] Meyer | Network-Based Rendering Techniques for Large-Scale Volume Data Sets[END_REF].

Adaptive Octree

Large volumetric data sets, which are typically arranged in a regular Cartesian grid, are often too complex to be rendered in real time on today's hardware for cluster nodes and with current 3D texture-based rendering techniques. Therefore, they must be reduced to a reasonable size, so that each node can quickly access the appropriate section of the 3D volume and render this portion of the data almost instantaneously. The slice format in which volume data often comes is not suitable for this purpose, because too many files need to be opened in order to display a 3D volume from cross-sections. Opening large numbers of files has proven to be prohibitively slow. Therefore, an octree space subdivision algorithm is employed. Instead of using a database, the Unix file system and an efficient indexing scheme are used to access the right block of data instantly. The octree method is illustrated in Fig. 1. Three simple binary decisions (left or right, front or back, and top or bottom) are necessary at each level to determine the position of a voxel in an octree. Each decision corresponds to a two bit index, which can take on 2 3 = 8 states (0-7), i.e., the eight child nodes of the octree. The number represents the file name, and several numbers in a file name indicate an octree traversal path. With this fast indexing scheme, it is possible to traverse the tree almost instantaneously in order to get to the leave of the tree which carries the data. The main advantage of the octree data structure is the early termination of the traversal in branches that are empty. It works best for data sets where the object is located near the center of the data cube and has an empty or nearly empty background (e.g., for CT or MRI scans), but it also works for sparse data sets. The information is determined in a preprocessing step when creating the octree data structure. Empty areas are not stored, saving a significant amount of disk space and RAM. Several space subdivision algorithms have been implemented in order to compare their performance and scalability [START_REF] Meyer | Interactive Rendering -A Time-Based Approach[END_REF] with the octree approach. Binary Space Partition (BSP) trees, for example, are based on a binary subdivision of three-dimensional space. A root node is recursively subdivided in alternating directions, in a cycle of several subdivisions (one for each dimension). Empty regions are marked, so that they can be skipped in order to speed up the rendering procedure. A statistical analysis based on typical data sets (CT and MRI scans) has been conducted, and it was found that for the same data set size the octree technique consistently outperformed other techniques like the BSP tree both in terms of preprocessing time and, more importantly, traversal time during rendering [START_REF] Meyer | Interactive Visualization of Medical and Biological Data Sets[END_REF]. At this point, depending on the depth of the octree, the data block to be read from the octree may still be too large to fit into the texture buffer of a rendering node's graphics card. For this reason, the leaves are stored in a multi-resolution wavelet format, which is described in the next section.

3D Non-standard Haar Wavelet Decomposition

We use a 3D non-standard Haar wavelet decomposition method to store the leaves. The benefit of using this method is the fact that low-resolution information can be stored at the beginning of the file, and if more detail is desired, more data in the form of detail coefficients can be loaded in order to refine the image. Depending on the number of wavelet levels, a tremendous reduction of data can be accomplished with acceptable visual artifacts in the rendered image. On the first level, only 1/8th of the data needs to be rendered, on the second level 1/64th (less than 2% of the total data set), and so forth. This exponential reduction leads to a significant acceleration and memory savings. The volume pyramid can be compressed by removing small coefficients. A threshold determines whether a coefficient can be set to zero or not. Real numbers with fractions can be quantized, e.g., by removing the fraction part, and low-frequency coefficients could be stored at higher precision than high-frequency coefficients. However, one of the most important advantages of the wavelet approach is the fact that we can use the same amount of memory to store the hierarchy as to store the original volume. Typically, we would use float as the data type to store detail coefficients. We can replace this data type by integers with no loss of precision, and therefore we can make use of the fact that integer arithmetic is much faster than floating point arithmetic [START_REF] Calderbank | Wavelet transforms that map integers to integers[END_REF]. In our implementation, we use the following method: Volume data is represented as a three-dimensional array of scalar values. The resolution is 8 bits, which allows for 256 different gray levels. For the wavelet transformation, we use an unsigned integer (32 bits) to store coefficients, which is the same size as a float (4 bytes). Initially, our data is stored in bits 23. . . 30. The leftmost bit 31 is usually unused. Only when the algorithm computes the sum of two data items in order to determine the reduced pixel, i.e., their representation in the lower resolution image, the intermediate result can become temporarily larger than 255, which causes an overflow into this unused bit. For the computation of reduced pixel values and detail coefficients, a division by two is involved, which corresponds to a bit shift to the right, i.e., an underflow. Since we have three dimensions per cycle, we can have a 3 bit underflow. We have 22 bits available. This means that we can apply the algorithm 7 times before we run out of bits. This is sufficient, since the data set is then already reduced to (1/8) 7 = 4.77 × 10 -7 . This means, for instance, that a typical data set of 256 3 = 16, 777, 216 voxels is then already reduced to 8 voxels.

System Details

The following section discusses hard-and software related aspects of the display cluster used for the visualizations.

Cluster Display Wall

Our visualization cluster (see Fig. 3) consists of 25 PowerMac G5 computers, equipped with nVidia GeForce 6800 and nVidia Quadro FX4500 graphics cards. These 25 compute nodes drive fifty 30 inch Apple Cinema Displays that have been arranged in a 10 × 5 grid. Together they form a 200 megapixel tiled display wall which measures 23 × 9 ft. Each screen has a native resolution of 2560 × 1600 pixels. The wall can display scenes at a maximum resolution of 25, 600 × 8, 000 pixels. A designated front-end node processes user input and launches applications. The current operating system on the cluster is Mac OS X Tiger.

CGLX

As mentioned in section 2, there exists a variety of different distributed rendering libraries. Our implementation of the volume renderer is based on CGLX [START_REF] Doerr | [END_REF], a Cross-Platform Cluster Graphic Library. CGLX was developed at the California Institute for Telecommunications and Information Technology at UC San Diego and is a flexible and transparent OpenGL-based graphics framework for distributed visualization systems in a master-slave setup. Master-slave architectures run an instance of the application on each compute node of the cluster. Communication between nodes is realized through a light-weight, thread-based network communication protocol. Attempting to be as transparent as possible to the developer, CGLX offers a GLUT-like (OpenGL Utility Toolkit) interface, which allows the library to intercept and interpret OpenGL calls, providing a distributed large scale OpenGL context on tiled displays. Theoretically, existing applications can be ported to CGLX by just changing the includes from GL/glut.h to clgX.h and calling cglXOrtho, CGLX's equivalent to glOrtho. However, in practice things like synchronized access to global variables or shared resources (e.g., files) require some more tweaking.

System Design

When doing volume rendering of large-scale data sets on desktop computers, the limited resources of the system pose restrictions to the visualizations. Above all, the available amount of video RAM determines the size of data sets that can be visualized on a given system. The same restrictions apply when designing cluster applications, where each node computes the entire scene. The waste of system resources is enormous, since nodes allocate memory for the entire scene, but only display a small part of it. Often however, this approach is favored by distributed rendering libraries. Since libraries try to be transparent, programmers write code almost as if they are developing applications for desktop PCs. The library lets each node compute the entire scene and sets viewport and viewing frustum according to the location of its screens within the grid. While this is a clear advantage for the developer, it leads to a waste of system resources, which we try to avoid with algorithm described in the following section.

Rendering Algorithm

Different methods have been developed to visualize volumetric data sets by approximating the volume rendering equation [START_REF] Max | Optical Models for Direct Volume Rendering[END_REF]. As opposed to isosurface algorithms [START_REF] Lorensen | Marching cubes: A high resolution 3D surface construction algorithm[END_REF], these techniques simulate the propagation of light in a transparent light emitting and absorbing medium.

Raycasting [START_REF] Levoy | Efficient Ray Tracing of Volume Data[END_REF][START_REF] Kruger | Acceleration Techniques for GPU-based Volume Rendering[END_REF][START_REF] Roettger | Smart hardwareaccelerated Volume Rendering[END_REF] is an image-order method that casts rays through each pixel of the viewing plane into the volume and samples along the ray. The method is able to yield high-quality results but is computationally expensive. In order to be interactive, it requires sophisticated adaptive sampling schemes, empty space skipping, and early ray termination. Their implementation is partly supported by today's modern programmable GPUs. However, even though raycasting is able to produce the best optical results, it generally means having to trade speed for image quality. We decided that raycasting is not going to pay off when the goal is to achieve interactive framerates on a fifty tile display wall.

Splatting [START_REF] Westover | Footprint Evaluation for Volume Rendering[END_REF][START_REF] Westover | Interactive Volume Rendering[END_REF][START_REF] Rusinkiewicz | Qsplat: a multiresolution point rendering system for large meshes[END_REF]] is a rendering approach in which voxels of the volume are projected in back-to-front order onto the 2D viewing plane. Splat kernels, e.g., Gaussian kernels, are used to blend splats and generate smooth images. Splatting in general is faster than raycasting, but the implementation is tricky and results depend on the choice of the splat kernel. Therefore, splatting was not our first choice rendering algorithm.

Texture mapping [START_REF] Wilson | Direct Volume Rendering via 3D Textures[END_REF][START_REF] Cabral | Accelerated Volume Rendering and Tomographic Reconstruction using Texture Mapping Hardware[END_REF][START_REF] Rezk-Salama | Interactive volume on standard PC graphics hardware using multi-textures and multi-stage rasterization[END_REF] treats volumetric data as 3D textures that are mapped to sets of proxy geometry. The general approach is to map data sets to a stack of view-aligned planes via trilinear interpolation. Afterwards, blending of adjacent planes generates a continuous three-dimensional visualization of the volume. Texture mapping is very efficient on modern GPUs, since trilinear interpolation is hard-wired on today's graphics cards. Furthermore, the technique is easy to implement and produces good-quality results. Therefore, we decided to implement a rendering algorithm that is based on this approach.

It is worth pointing out that our prototype could theoretically be adapted to use any of the other rendering approaches. Most changes would concentrate on the main render loop and not on the data structure employed in our algorithm.

We want to make full use of the resources of each rendering node and determine which parts of a scene its monitors are going to display. The rendering node allocates resources only for a portion of the data set and uses the available video memory to display its subvolume at the highest possible quality. For doing so, we make use of the data structure described in section 3. The volume subdivision of the octree is well suited for being used in a frustum clipping step (see section 6.1). It allows rendering nodes to disregard parts of a scene that do not have to be displayed. These parts do not need to reside in RAM and do not need to occupy precious texture memory. The wavelet representation of the octree data allows rendering nodes to determine a compression level for the subvolumes, so that they still fit in their graphics card's texture memory and at the same time provide the highest possible level of detail.

As a result we end up with a scene in which each LCD of the grid displays a portion of the volume at an individual but maximal quality. For large-scale data sets this quality can differ by a factor of 8 -64 (which corresponds to 1 -2 wavelet levels) from the results that can be achieved on a desktop PC.

Progressive Refinement

When transforming the volume (by translation, rotation or scaling operations) frustum clipping has to be rerun because parts of the data set might fall into a different region of the display wall. Frustum clipping can slow the system down because it implicates time consuming file operations to load new data chunks from hard disk into main memory. Therefore, it is impossible to clip at interactive rates. Our solution to this bottleneck is a fallback texture. The fallback texture permanently resides in the graphics card's texture memory and contains the entire data set which is loaded only once at start-up time. Whenever the volume is transformed, i.e., when the user uses the mouse to change the current position or scaling factor of the volume, we switch from the individually computed subvolumes of a node to the fallback texture. The size of the fallback texture is chosen in a way that each rendering node maintains a predefined minimum frame rate. That way we keep the system responsive and guarantee that the volume is displayed at any given time in its current position. Because the fallback texture contains the entire data set and has to be stored once on each node, its detail level is usually lower than the ones that result from the clipping process.

When the mouse is released, i.e., when user interaction is paused, the system gradually increments a counter, which determines the detail level. As a consequence, the image is gradually refined up to the maximum level of detail each graphics card can display. Data sets can comprise several gigabytes and are stored in the octree-wavelet format. The size of the octree bricks is determined by the octree depth -a parameter that is specified by the user. The deeper an octree is, the more brick files there are and the smaller the brick files will be. However, loading the required information from these files in just one step may take too long. The data organization of the brick files allows a rendering node to load the content incrementally. The content of the files is organized in such a way that the data of the highest wavelet compression appears at the beginning of a file and is followed by the detail coefficients of lower wavelet levels (see section 3). Thus, it is possible to first load the lowest detail level and then gradually refine by sequentially loading detail coefficients for the reconstruction. In practice this means, that we start at a level i, display the data set at that resolution and then, triggered by a timer, switch to level i -1, i -2 and so forth. This way, after having interacted with the volume, the user is provided with instantaneous visual feedback. Progressive refinement including fallback textures keeps the system responsive and enables users to explore data sets interactively. For small movements through the volume, where only parts of a scene change, the user experience could in the future be improved by loading additional high-resolution data around a hull of the frustum. Synchronization between nodes is achieved through the render library's builtin synchronization mechanism. Before OpenGL render buffers are swapped, a barrier synchronization lets the system stall until all threads reach the barrier. While this means having to wait for the slowest node in the cluster, it gives us a way to switch synchronously between wavelet levels during progressive refinement and to reduce artifacts. Note, that within a tile the wavelet level is always constant, in contrast to the method that was presented by LaMar et al. [START_REF] Lamar | Multiresolution Techniques for Interactive Texture-Based Volume Visualization[END_REF].

Their algorithm generates regions of varying resolution within the final image.

Implementation

This section discusses implementation details of the frustum clipping and texture mapping stage.

Out-of-Core Frustum Clipping

During the clipping stage each rendering node determines for each of its monitors (i.e., two in our case) which parts of the data set they are going to display depending on the current view. This yields a subvolume for each screen for which the according files are loaded at the node. The subvolume is loaded at the maximum possible resolution, so that it still fits into a predefined portion of the texture memory. As a result, frustum clipping yields a partial copy of the entire data structure from hard disk in a node's main memory, ready to be visualized by 3D texture mapping.

To determine if an octree brick is going to be displayed by a monitor, we calculate where on the tiled display the eight corners of an octree brick are going to appear, i.e., we project them into 2D space and calculate their window coordinates. Determining the window coordinates (wx, wy) of a given point v = (ox, oy, oz, 1.0) in object space under a modelview matrix M , a projection matrix P and viewport V can be accomplished via OpenGL's gluProject method. gluProject

first computes v = P • M • v.
The actual window coordinates are obtained through

wx = V [0] + V [2] • (v [0] + 1)/2
(1)

wy = V [1] + V [3] • (v [1] + 1)/2. ( 2
)
wx and wy specify the window coordinates of point v. The viewport V of course is defined by the size of the tiled display, i.e., 25, 600 × 8, 000 in our case. The projection matrix P is the matrix that orthogonally projects the viewing frustum to the viewport V . Since we transform the volume by manipulating OpenGL's texture matrix T , we use its inverse T -1 as an input to gluProject instead of the modelview matrix M (inverse, because T manipulates texture coordinates and not the texture image).

Once the window coordinates of the eight brick points are known, their bounding box is tested for intersection with the area of each LCD in the grid. The intersections with the screen of a node define a rectangular subvolume whose content we load from hard disk. The wavelet representation of the octree bricks allows us to load the subvolume at a detail level, that will not exceed a predefined number of voxels n. The wavelet level for a subvolume of dimensions dx, dy, dz is calculated as follows: wavelet level = 0; cM od = 1; while (dx/cM od) • (dy/cM od) • (dz/cM od) > n do wavelet level + +; cM od = 2 • cM od; end while We limit textures to n = 16.7 × 10 6 voxels. A three-dimensional RGBA texture containing that many voxels has a size of 64MB. Notice, that we have to store three textures at each node: One high-resolution texture for each of the two monitors that are connected to a node and one common low-resolution fallback texture containing the entire data set.

Assembling the Volume

Now that we have buffers containing different regions of the data set at different levels of resolution, the next step is to render them using the texture mapping approach discussed in section 5.1. Therefore, data chunks have to be assembled to form the entire volume. Since buffers represent 3D textures, one can think of two approaches to assemble them: The first approach maps each subvolume to its own stack of view-aligned proxy geometry, whose size and position within object space depends on the particular subvolume. The second approach maps each subvolume to the same (full screen) stack of view-aligned proxy geometry but scales and translates each texture so that it appears at the right position when being mapped. We chose the second approach, because it can easily be realized with the meta information that comes with each buffer and is provided by the data structure that implements the wavelet-octree (see Fig. 4). The following facts are known about each subvolume: vx, vy and vz denote the buffer's axis dimensions. As explained above, vx • vy • vz ≤ 16.7 × 10 6 holds. Further, the rectangle's two diagonal points p = (px, py, pz) and q = (qx, qy, qz) are known. Their coordinates are normalized with respect to the full size of the data set, so (0, 0, 0) and (1, 1, 1) span the entire volume. p and q allow us to compute the actual portion of the data set, that is represented by all vx • vy • vz voxels through dx = qx -px, dy = qy -py and dz = qz -pz. Furthermore, p provides us the normalized offset within the entire volume with respect to the origin (0, 0, 0). Now, the calculation of appropriate scaling factors and translation vectors to place the texture at the right location in the volume is straight forward.

Results

Limiting the size of textures to 16.7×10 6 voxels, i.e., 64MB for an RGBA texture, does not seem logical considering the fact that each graphics cards is equipped with 256MB VRAM. However, each node maintains three textures, all with a maximum size of 64MB, resulting in a total of 192MB. Another 31.25MB are used for the framebuffer of each display supporting a resolution of 2560 × 1600 pixels. Thus, only 32.75MB remain for additional operations. The calculation shows that a limit of 64MB per texture results in an optimal use of the available video resources. In fact, even the main memory workload of a node is kept low. Theoretically, the application only needs to allocate main memory for all three texture buffers. In practice about twice the amount of memory is needed due to the internal management of data. If more physical memory was added to the graphics cards, these observations would scale accordingly, and the visual quality of the displayed image would further improve. A variety of factors influence the quality of visualizations:

-Data sets themselves influence quality in that their dimensions partly determine the level-of-detail. Data sets consisting of many slices and therefore having a large extension in z-direction will not be displayed at the same detail level as data sets with fewer slices. -The octree depth has a big influence on the final result. An octree of depth one partitions the entire volume into eight bricks, resulting in a rather coarse subdivision for the clipping process. An octree of depth two, however, produces 64 bricks and increases the quality since frustum clipping is able to extract smaller subvolumes that better represent the actual portion of data to be displayed. -Last but not least, the current view has a strong effect on the detail level.

Zooming-in maps fewer octree bricks to a tile and can therefore increase the level-of-detail. Rotations and translations have a similar influence.

Fig. 5(a) depicts a typical multi-resolution scene, where each monitor displays at its own tile-specific wavelet level. Note, that multi-resolution in this case refers to potentially different wavelet levels between tiles and that the level of detail within a tile is constant. The data that is visualized is a histology data set of a human cadaver brain. In order to illustrate the wavelet distribution within the wall, screens have been color coded in Fig. 5(b). Tiles marked red correspond to regions of wavelet level 2, meaning that these LCDs display the data set at 1/64 = 1.5% of the original resolution. Green tiles correspond to areas of wavelet level 1, i.e., they display 1/8 = 12.5% of the original structure. The close-up in Fig. 6 illustrates the difference between these two levels for a human mandible data set. In the upper picture each LCD displays at a wavelet level of 2, which corresponds to the detail level of the fallback texture. After refinement, the upper two LCDs switch to wavelet level 1, thereby increasing the level of detail by a factor of 8 and revealing more anatomical structures.

Analysis

The multi-resolution data structure is computed in a two-stage preprocessing step. In the first stage, a tool called VolCon computes the octree structure described in section 3.1, so that an input data set, consisting of a set of files storing slice information, is stored as a set of files storing octree bricks. In the second stage, another tool called Compress calculates the wavelet representation described in section 3.2 based on the results of stage one. Octree depth and maximum level of wavelet compression are passed as user-defined parameters. Generally, deeper octrees generate smaller brick files which lead to a crucially more accurate approximation of the subvolume of a tile. However, increased clipping accuracy comes cost of more file accesses. Table 1 illustrates the preprocessing time for various data sets with an octree depth of two and two levels of wavelet compression on a Core2Duo laptop machine with 2GB RAM.

We measured the time it takes each node to clip and render a scene (after interaction) using different octree depths for multiple data sets. Furthermore, we monitored the wavelet level at which each tile displays the scene. A fixed perspective was used during measurements, i.e., the orientation and zoom level remained unchanged. The results are depicted in Fig. 7. Fig. 7(a) shows that the average time it takes to clip and render a scene decreases with increasing octree depth and thereby increasing number of bricks, except one outlier for the brain data set. The overhead of loading unnecessary parts of the data set decreases because clipped subvolumes better match the data set portion, that a tile has to display. A possible explanation for the outlier is that there is a sweep point where the overhead caused by additional I/O operations overweighs the benefits of a better subvolume approximation. Fig. 7(b) shows that at the same time, with increasing octree depth, the average detail level of the display wall increases, i.e., the average wavelet level over all fifty tiles gets smaller, because the available texture memory is used more efficiently to store structural details of the volume. The detail level of the skull data set remains constant with increasing octree depth because the volume is small enough to fit entirely into the graphics card's texture memory. Note, that the real-valued wavelet levels in Fig. 7(b) result from averaging the discrete values for each tile. Though these compression levels cannot be achieved in practice, they give a good theoretical value describing the overall level of detail comprised in all fifty LCD panels. Further note, that the partly asymmetric variances depicted in Fig. 7(b) are due to the fact that the percentage of voxels scales non-linearly with the wavelet level, i.e., the level of detail comprised at level i is 1/8th of level i -1. In general, both the average rendering time and the level of detail are positively affected by a deeper octree. Our studies show that an octree depth of four in most cases is sufficient to guarantee almost interactive behavior when working with data sets.

In earlier experiments we investigated the data structure's capabilities when accessing volume data for a non-distributed application [START_REF] Nguyen | Large-scale Volume Rendering using Multi-resolution Wavelets, Subdivision, and Multi-dimensional Transfer Functions[END_REF]. Fig. 8 compares a system using the octree-wavelet data structure to a system that uses neither spatial subdivision nor a multi-resolution representation. The unoptimized system loads the entire data by directly accessing a set of files storing slice information, i.e., slices are loaded sequentially into main memory. Fig. 8(a) compares the time it takes to load the entire mandible data set slice-wise into RAM to the time it takes to load at different wavelet levels at a fixed octree depth of three. Though the time difference observed for the system using the octree-wavelet structure is marginal between wavelet levels, loading is less than 7% of the average time measured to load the entire cross-sectional data. Fig. 8(b) illustrates the influence of octree depth on the loading time for the skull data set. It can be observed that loading takes longer with increasing octree depth, which is due to the increased number of I/O operations that have to be performed and that are generally considered to be slow. This pattern also holds for various wavelet levels.

The results of Fig. 8(b) and Fig. 7(a) seem contradictory. Whereas a higher octree depth leads to a better approximation of subvolumes during frustum clipping and reduces the amount of data that has to be loaded, the increased number of file operations works against this effect. However, the benefits of having a smaller clipping volume overweigh the negative effect of additional I/O operations.

Discussion

According to Molnar's [START_REF] Molnar | A Sorting Classification of Parallel Rendering[END_REF] classification of distributed rendering algorithms the system presented in this paper implements a static sort-first algorithm. A general advantage of the sort-first strategy is the fact that communication overhead and network traffic are kept low. This is an important characteristic for the visualization of large-sized data sets because it prevents the network from being a performance bottleneck. The data structure employed in this paper including the multi-resolution approach resembles a scenegraph-based system [1]. Scenegraphs also perform frustum culling in order to reduce scene complexity and they implement LOD techniques that often estimate an object's level of detail based on its distance to the viewing plane. However, scenegraphs are generally oriented towards geometric data and not so much suited for managing volumetric data sets. To our knowledge, no scenegraph-based system running on a distributed display cluster exploits resources for direct volume rendering with the efficiency of the technique we presented in this paper. Note, that 3D texture mapping results in uniform sampling along the viewing ray. If one wants to sample adaptively, for example based on the distance to the eye point, this can be achieved by raycasting the volume (see section 5.1). The algorithm we presented scales with the processing power and size of the display system. The higher the number of tiles the more compute nodes are required. If the number of compute nodes increases the subvolumes get smaller, because the relative area covered by a monitor decreases. As a consequence, the quality of visualizations improves, since the same amount of resources is used to render smaller subvolumes. Likewise, if the amount of video memory increases, the buffer sizes can be adapted in order to store more detail information. Instead of allocating 64MB for texture objects, larger memory blocks would improve the average wavelet level of tiles and thus also the quality of renderings. So far, when talking about "increased quality" we refer to a higher resolution. However, visual quality also encompasses contrast, color, and shading. Thus far, these topics have been mostly untouched in our work. In the future it might be interesting to investigate how to incorporate them into our system. For instance, the human visual system is strongest in the center field of view. Objects in the periphery are perceived with less detail. In order to account for this, one could apply a focus+context technique to create areas of high contrast with complex shading in the center of the tiled display and fuzzy regions in the periphery, similar to what Baudisch et al. [START_REF] Baudisch | Focus plus context screens: combining display technology with visualization techniques[END_REF] did with the resolution of the focus+context screen. Our display wall is a monitor-based display cluster that combines the images of multiple LCD panels to form one large high-resolution display area. In contrast, projector-based tiled displays combine the images of a set of computer projectors [START_REF] Majumder | Practical Multi-projector Display Design[END_REF][START_REF] Li | A Survey of Multi-Projector Tiled Display Wall Construction[END_REF] and can easily exceed the dimensions of monitor-based systems. A major advantage of projector systems is their ability to form truly seamless displays [START_REF] Majumder | Achieving color uniformity across multi-projector displays[END_REF][START_REF] Majumder | Perceptual photometric seamlessness in projectionbased tiled displays[END_REF] while monitor-based systems inherently suffer from monitor bezels causing discontinuities in visualizations. At the moment our implementation does not cope with sharp transitions between adjacent tiles due to different resolution levels. We found that the benefit of perceiving finer details of the data set outweighs these slight optical confusions. A user study we conducted [START_REF] Ebert | Tiled++: An Enhanced Tiled Hi-Res Display Wall[END_REF] showed that sharp transitions between different levels of resolution on a tiled wall do not cause as much confusion as mismatches in brightness and color between screens. The problem of discontinuities caused by monitor bezels requires deeper investigation in the context of human-computer interaction. Software [START_REF] Mackinlay | Wideband displays: mitigating multiple monitor seams[END_REF] as well as hardware dependent solutions [START_REF] Ebert | Tiled++: An Enhanced Tiled Hi-Res Display Wall[END_REF] have already been proposed.

10

In this paper we presented a method to effectively visualize volumetric data sets on tiled displays. Our implementation is based on a spatial subdivision scheme using octrees and incorporates a multi-resolution wavelet representation of the data. We were able to show that our approach increases the quality of visualizations by individually exploiting the resources of each rendering node. The system is interactive and allows users to explore data sets nearly in a real-time fashion. Our implementation was tested on a fifty tile display that is driven by twenty-five rendering nodes. In the future, we plan to investigate modifications of our data structure and implement memory caching and prefetching strategies to minimize I/O latencies. Additionally, we want to exploit further features of current state-of-the-art GPUs.

Acknowledgements

This work was supported by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) as part of the International Graduate School (International Research Training Group, IRTG 1131) in Kaiserslautern, Germany. The

Fig. 1 .

 1 Fig. 1. Octant indexing scheme used to represent paths in the octree.

Fig. 2 .

 2 Fig. 2. Octree space subdivision uses multi-resolution wavelet representation for the leaves.

Fig. 3 .

 3 Fig. 3. 200 megapixel tiled display cluster measuring 23 × 9 ft.

Fig. 4 .

 4 Fig. 4. Mapping information.

Fig. 5 .Fig. 6 .

 56 Fig. 5. (a) Multi-resolution rendering of the Toga data set. (b) Wavelet level distribution. Red corresponds to tiles of level 2 (1/64 = 1.5% of original quality), green to level 1 (1/8 = 12.5% of original quality).

Fig. 7 .

 7 Fig. 7. (a) Average time it takes to perform frustum clipping and volume assembling. (b) Average percentage of original voxels being displayed (including average wavelet level).

Fig. 8 .

 8 Fig. 8. (a) Loading time vs. wavelet level. (b) Loading time vs. octree height.

Table 1 .

 1 Data set characteristics and preprocessing times for octree depth 2 (64 bricks) and two levels of wavelet compression.

	Data Set Dimensions (x × y × z) Size(MB) VolCon Compress
	Skull	256 × 256 × 113	28.25	0m 2.5s 0m 2.7s
	Mandible	1024 × 1024 × 374	1496	2m 17.2s 4m 2.5s
	Toga Brain	1024 × 1024 × 753	3012	5m 9.9s 9m 45.8s

authors would like to thank Stephen F. Jenks and Sung-Jin Kim (University of California, Irvine), Falko Kuester and Kai-Uwe Doerr (University of California, San Diego) and the National Science Foundation for their support.