7656106
Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time
We study algorithmic aspects in the management of geometric scenes in interactive walkthrough animations. We consider arbitrarily large scenes consisting of unit size balls. For a smooth navigation in the scene we have to fulfill hard real time requirements. Therefore, we need algorithms whose running time is independent of the total number of objects in the scene and that use as small space as possible. In this work we focus on one of the basic operations in our walkthrough system: reporting the objects around the visitor within a certain distance. 
 
Previously a randomized data structure was presented that supports reporting the balls around the visitor in an output sensitive time and allows insertion and deletion of objects nearly as fast as searching. These results were achieved by exploiting the fact that the visitor moves "slowly" through the scene. A serious disadvantage of the aforementioned data structure is a big space overhead and the use of randomization. 
 
Our first result is a construction of weak spanners that leads to an improvement of the space requirement of the previously known data structures. Then we develop a deterministic data structure for the searching problem in which insertion of objects are allowed. Our incremental data structure supports O(1+k) reporting time, where k is a certain quantity close to the number of reported objects. The insertion time is similar to the reporting time and the space is linear to the total number of objects.
14681345
The randomized sample tree: a data structure for interactive walkthroughs in externally stored virtual environments
We present a new data structure for rendering highly complex virtual environments of arbitrary topology. The special feature of our approach is that it allows an interactive navigation in very large scenes (30 GB/400 million polygons in our benchmark scenes) that cannot be stored in main memory, but only on a local or remote hard disk. Furthermore, it allows interactive rendering of substantially more complex scenes by instantiating objects.For the computation of an approximate image of the scene, a sampling technique is used. In the preprocessing, a so-called sample tree is built whose nodes contain randomly selected polygons from the scene. This tree only uses space that is linear in the number of polygons. In order to produce an image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk.We implemented our algorithm in a prototypical walkthrough system. Analysis and experiments show that the quality of our images is comparable to images computed by the conventional z-buffer algorithm regardless of the scene topology.
14377391
A Network Based Approach for Realtime Walkthrough of Massive Models
New dynamic search data structures developed recently guarantee constant execution time per search and update, i.e., they fulll the real-time requirements necessary for interactive walk-through in large geometric scenes. Yet, superiority or even applicability of these new methods in practice was still an open question. Their prototypical implementation presented in this work uses common libraries on standard workstations and thus represents a rst strut to bridge this gap. Indeed our experimental results give an indication on the actual performance of these theoretical ideas on real machines and possible bottlenecks in future developments. By special algorithmic enhancements, we can even avoid the otherwise essential preprocessing step.
29746533
Guidance of Users in Interactive 3D-Visualisations of Material Flow Simulations
15975823
The randomized z-buffer algorithm: interactive rendering of highly complex scenes
We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of an arbitrary three-dimensional scene consisting of triangular primitives by reconstruction from a dynamically chosen set of random surface sample points. This approach is independent of mesh connectivity and topology. The resulting rendering time grows only logarithmically with the numbers of triangles in the scene. We were able to render walkthroughs of scenes of up to 1014 triangles at interactive frame rates. Automatic identification of low detail scene components ensures that the rendering speed of the randomized z-buffer cannot drop below that of conventional z-buffer rendering. Experimental and analytical evidence is given that the image quality is comparable to that of common approaches like z-buffer rendering. The precomputed data structures employed by the randomized z-buffer allow for interactive dynamic updates of the scene. Their memory requirements grow only linearly with the number of triangles and allow for a scene graph based instantiation scheme to further reduce memory consumption.
1039321
A Support Tool for Writing Multilingual Instructions
Multilingual instructions generation has been the object of many studies recently, motivated by the increased need to produce multilingual manuals coupled with the cost of technical writing and translating. These studies concentrate on the automatic generation of instructions, leaving technical writers out of the loop. In many cases, however it is not possible to dispense with human intervention entirely, for at least two reasons. First, the system must be provided with a semantic knowledge base from which the instructions can be generated. Second, it is the technical writers who have the expertise necessary for producing instructions appropriate for a specific product or company, and it is not necessarily an easy task to make this expertise available to a system. The results of a requirement analysis study confirm the view that the most useful tool is not a stand-alone writing tool but rather one that supports technical writers in their task. In this paper, we describe such a support tool, which we developed based on the results of our user requirement analysis.
15568865
Appraising two decades of distributed computing theory research
Abstract.The field of distributed computing started around 1970 when people began to imagine a future world of multiple interconnected computers operating collectively. The theoretical challenge was to define what a computational problem would be in such a setting and to explore what could and could not be accomplished in a realistic setting in which the different computers fell under different administrative structures, operated at different speeds under the control of uncoordinated clocks, and sometimes failed in unpredictable ways. Meanwhile, the practical problem was to turn the vision into reality by building networks and networking equipment, communication protocols, and useful distributed applications. The theory of distributed computing became recognized as a distinct discipline with the holding of the first ACM Principles of Distributed Computing conference in 1982. This paper reviews some of the accomplishments of the theoretical community during the past two decades, notes an apparent disconnect between theoretical and practical concerns, and speculates on future synergy between the two.
1648746
Experience in early and late software engineering project courses
We report on the experience we gained in different software engineering project courses at our department. A student who is specialized in software engineering has to complete, besides lectures on software engineering and related fields, two project courses: an "early" basic project course, and a "late" complex project course. For both of them we developed leveled teaching approaches considering the different knowledge and skills of beginners and "advanced" students, respectively. The paper describes, discusses and evaluates these approaches.
201632
CULTURE AND INDIGENOUS KNOWLEDGE SYSTEMS: EMERGENT ORDER AND THE INTERNAL REGULATION OF SHARED SYMBOLIC SYSTEMS
ABSTRACT I explore the relationship between culture, knowledge and behaviour in a context of change, comparing scientific with cultural knowledge. I argue that applications (or instantiations) of scientific knowledge are not the same as science, and undergo a process that has properties not unlike those described by Ellen and Harris for ‘Indigenous Knowledge’ (IK). This process uses knowledge that is not derived from the system represented, but nevertheless is necessary for the system to operate in a contingent world even though this knowledge was not in the original subset of knowledge being applied. This consideration of knowledge about what contexts must be instantiated to enable domain knowledge to be instantiated builds on Ellen's concept of prehension, which in part includes the anticipatory knowledge a subject brings to a situation. I suggest the operative principles in IK have similar properties.