SUMMARY We present a novel approach to combined textual and visual programming by allowing visual, interactive objects to be embedded within textual source code and segments of source code to be further embedded within those objects. We retain the strengths of text‐based source code, while enabling visual programming where it is beneficial. Additionally, embedded objects and code provide a simple object‐oriented approach to adding a visual form of LISP‐style macros to a language. The ability to freely combine source code and visual, interactive objects with one another allows for the construction of interactive programming tools and experimentation with novel programming language extensions. Our visual programming system is supported by a type coercion‐based presentation protocol that displays normal Java and Python objects in a visual, interactive form. We have implemented our system within a prototype interactive programming environment called ‘The Larch Environment’. Copyright © 2013 John Wiley & Sons, Ltd.

A discrete collision detection algorithm to detect self-collisions between deformable objects is presented, this is built up using a bounding volume hierarchy (BVH) and a Feature-based method. The deformations are represented by the features of the mesh, which are within the bounding volumes and consequently the updating time for the BVH is reduced. The algorithm compares the minimum bounded geometry, the 1-ring, with the other spheres of the hierarchy in order to cull away bounding volumes (BV) that are far apart. The 3D objects utilised are surface-based and are deformed by warping, control points of splines, and a mass-spring model.

Abstract We present a method to accelerate the visualization of large crowds of animated characters. Linear‐blend skinning remains the dominant approach for animating a crowd but its efficiency can be improved by utilizing the temporal and intra‐crowd coherencies that are inherent within a populated scene. Our work adopts a caching system that enables a skinned key‐pose to be re‐used by multi‐pass rendering, between multiple agents and across multiple frames. We investigate two different methods; an intermittent caching scheme (whereby each member of a crowd is animated using only its nearest key‐pose) and an interpolative approach that enables key‐pose blending to be supported. For the latter case, we show that finding the optimal set of key‐poses to store is an NP‐hard problem and present a greedy algorithm suitable for real‐time applications. Both variants deliver a worthwhile performance improvement in comparison to using linear‐blend skinning alone.

An algorithm to detect collisions between both rigid and deformable objects is presented. The approach exploits benefits of a bounding volume hierarchy (BVH) and a feature-based method. The BVH decomposes the three dimensional polygonal objects into a hierarchy of spheres. The lowest level of the hierarchy is formed utilising spheres which bound 1-rings surrounding each vertex of the original mesh. Spatial coherence is exploited during construction to ensure that adjacent 1-rings are joined first. This promotes tighter bounding volumes as the objects deform. Experiments were carried out to analyse the performance of the method when varying the BVH construction to consider octrees and binary trees. To illustrate the enhancement the approach provides it has been compared against standard Sphere and Axis-aligned Bounding Volume Hierarchies.

Real-time crowds significantly improve the realism of virtual environments, therefore their use has increased considerably over the last few years in a variety of applications, including real-time games and virtual tourism. However, due to current hardware limitations, crowd variety tends to be sacrificed in order for the crowd simulation to execute in real-time, which decreases the quality and realism of the crowd. Currently the little variety that is incorporated in real-time crowds tends to be applied by modulating each avatar with random colours, which has a detrimental effect on the texture quality. Furthermore, the existing crowd variety is often hard to define and control. To overcome these problems a set of techniques are presented, which defines and controls crowd variety, to further improve on current variety and quality of crowds. These techniques permit variety to be introduced: by changing the body mass via the application of a displacement map onto the mesh; by scaling the skeleton of the avatar; by applying HSV colour shifts to different parts of the avatar; and by transferring textures between avatar models. The appearance of the avatars under animation is also improved via the use of muscle displacement within the mesh. With the new techniques, the visual quality of the crowd is improved due to the increase in diversity.

Abstract Creating an interactive simulation of a large urban environment populated with virtual humans poses a number of interesting challenges, ranging from how to initialise the virtual humans in the correct locations to maintaining a real‐time simulation. When considering a large environment it is beneficial to investigate automatic techniques that create and simulate virtual humans using the available computing resources effectively. In this paper, two contributions towards the population of a large environment are described. The first presents two methods that use an automatic analysis of the urban environment to determine the required population densities throughout the scene. These methods ensure that the virtual humans are distributed such that main high streets consistently exhibit a higher number of virtual humans than other areas. The methods presented here achieve above 90% correlation to the predicted population densities for the environment, which outperforms the state of the art. The second contribution concerns the optimisation of the two methods to facilitate their applicability to large environments. The methods presented are modified to insert virtual humans dynamically into the behaviour system when required. The approach limits the required computing resources whilst achieving above 75% correlation to the predicted population values. Copyright © 2008 John Wiley & Sons, Ltd.

Distributing a collection of virtual humans throughout a large urban environment, where limited semantic information is available, poses a problem when attempting to create a visually realistic real time environment. Randomly positioning agents within an urban environment will not cover the environment with virtual humans in a plausible way. For example, areas of the urban space that are more frequently used should have a higher population density both at the start and during the simulation. It is infeasible to manually identify areas in the urban environment which should be crowded or sparsely populated when considering a scalable method, suitable for large environments. Consequently, this paper combines and extends techniques from spatial analysis and virtual agent behaviour simulations to develop a system capable of automatically distributing pedestrians in an urban environment. In particular, it extends the pointbased space syntax technique to enable the automatic analysis of a large urban environment in the presence of limited contextual information. This analysis specifies a set of population densities for areas in the environment and these values are used to initialise the locations of all the virtual humans in the environment. In addition to the initialisation stage the population densities in each area are consulted to ensure that the correct distribution of virtual humans is maintained throughout the simulation. The system is tested on an arbitrary section of a real city and comparisons of the characteristic parts of the test environment are correlated with the pedestrian movements.

Abstract Computer Graphics technologies have developed considerably over the past decades. Realistic virtual environments can be produced incorporating complex geometry for graphical objects and utilising hardware acceleration for per pixel effects. To enhance these environments, in terms of the immersive experience perceived by users, the human's sense of touch, or haptic system, can be exploited. To this end haptic feedback devices capable of exerting forces on the user are incorporated. The process of determining a reaction force for a given position of the haptic device is known as haptic rendering. For over a decade users have been able to interact with a virtual environment with a haptic device. This paper focuses on the haptic rendering algorithms which have been developed to compute forces as users manipulate the haptic device in the virtual environment.

Abstract In recent years, the availability of off‐the‐shelf geometric data for an urban environment has increased. During rendering, ground level images are mapped onto the façades of the buildings to improve the visual quality of the scene. This paper focuses on a technique that enables ground level images to be automatically integrated into an existing coarse three‐dimensional environment. The approach utilises the planar nature of architectural scenes to enable the automatic extraction of a building façade from an image and its registration into the virtual environment.

Abstract Real‐time rendering of photo‐realistic humans is considerably outside the scope of current consumer‐level computer hardware. There are many techniques, which attempt to bridge the gap between what is desired and what is possible. This paper aims to give an overview of the techniques designed to alter the complexity of the model's geometry (level of detail), or replace it with a flat image (visual impostor) and to improve the lighting model (lighting and shadows). Recent years have shown a boom in the power and availability of consumer‐level programmable graphics processors, thus techniques that make use of these features are coming to the forefront.

There are strict time constraints with regard to the update rates for applications incorporating the sense of touch. Therefore, it is essential to employ efficient algorithms for haptic rendering to ensure stable and realistic force feedback is perceived. A major part in any haptic rendering algorithm is the collision detection between the virtual representation of the haptic interface and the objects in the scene. The first part of this paper describes an efficient collision detection algorithm, which is derived from spatial partitioning and bounding volume hierarchy approaches. The pair of closest points is obtained between two polygonal models which may be nonconvex. The second part of the paper describes a haptic rendering algorithm that allows three-dimensional polygonal objects to represent deformable tools in the virtual environment

Many methods exist for automatically generating three dimensional models of urban environments at various levels of detail. To improve the realism of these models texture maps are applied to the building facades. This paper focuses on techniques which progress towards the automatic application of textural detail to building facades. In particular attention is paid to residential scenes where buildings are occluded by many objects such as vegetation and fences. The approach undertaken uses a set of images for each building being textured. From this set a single building image is created by identifying the building and removing occluding objects using a depth map. Further processing of the building image is undertaken to generate two texture maps, the wall map and the object map. The wall map contains a repeatable wall pattern extracted automatically from the building facade. The object map contains the spatial arrangement of features on a transparent background. The features are objects on the building facade such as windows and doors. These two texture maps are combined on the graphics card to permit the final textural detail of the building to be visualised

Abstract The aim of the rapid world modeling project is to implement a system to visualize the topography of the entire world on consumer‐level hardware. This presents a significant problem in terms of both storage requirements and rendering speed. This paper presents the ‘Tiled Quad Tree’, a technique and format for the storage of digital terrain models, to work as part of an integrated system for the visualization of global terrain data. We show how this format efficiently stores and compresses elevation data, in a way that allows the data to be read very rapidly from hard disk or similar storage medium, to facilitate real‐time rendering. The results of compressing several distinct data sets are presented.

The economic production and the interactive rendering of complete reconstructions of populated urban environments are technically difficult tasks. Specialized modelling tools, which exploit knowledge of the types of object being modelled by working in the application domain, can be used to create appealing virtual reconstructions quickly. At the same time, the structural information from the modeller gives valuable hints to the renderer to determine efficient interactive display strategies through the use of level-of-detail and culling techniques. Thus a modeller that knows the operator is creating houses can use this information to simplify the user interaction, guide the operator, and to create models that build in optimisations when attempting real-time rendering. In this paper we discuss the way in which polygonal and multi-resolution surface techniques can complement one another in the modelling of urban environments. We also draw more general conclusions which apply to other software systems that share the same objective.

Abstract Over recent years a variety of haptic feedback devices have been developed and are being used in a number of important applications. They range from joysticks used in the entertainment industry to specialised devices used in medical applications. This paper will describe the recent developments of these devices and show how they have been applied. It also examines how haptic feedback has been combined with visual display devices, such as virtual reality walls and workbenches, in order to improve the immersive experience. ACM CSS: H.5.2 Information Interfaces and Presentation—Haptic I/O; I.3.8 Computer Graphics—Applications; I.6 Simulation and Modelling—Applications

Over recent years a wide variety of interaction devices involving haptic feedback have been brought to the market, but they vary widely in terms of input measures recorded. These range from one dimensional input on a haptic feedback steering wheel to a six degree of freedom position and orientation device and further, to assemblies of such devices. On the surface most of the variations can be accommodated logically with standardized input models combining existing logical input devices and haptic feedback processes as acknowledgement/echos. However it is very uncertain whether such a model can adequately model the system requirements for effective haptic feedback. In this paper we review the input models that have developed over the past 20 years and ask “Is it the end of the road for the conceptual model of input incorporated into the early graphics standards and elaborated over the years?” In addition, to highlight the problems of implementation with haptic interaction, we describe a typical application, the simulation of a collision with a virtual wall.

This paper describes the use of virtual environments in endodontics. The problems associated with capturing the virtual environment by defining and manipulating the geometric shapes of teeth are illustrated. Dentists require ways of interacting with the virtual environment which closely mirror the conditions under which they work. Touch is very important when working in the close confines of the mouth and using instruments within dental cavities. Therefore, the paper reports on experimentation with novel interactive techniques designed to work with the available geometric representations of teeth. These techniques involve combining surface descriptions with force feedback and collision detection, to give the dentist realistic sensations in simulating treatment procedures. Some early experiments with distributed environments are described, with potential for collaboration in mentored training.

The Binary Space Partitioning (BSP) tree achieves fast hidden surface removal for most practical applications where an observer can move through a scene of static objects. However, the BSP algorithm generally increases the number of polygons in a scene due to its splitting stage resulting in a detrimental effect on the priority ordering and more significantly, the display calculations (shading, lighting, shadows, etc.) of the rendering pipeline. We present the Conflict Neutralization algorithm which attempts to reduce the number of splits more effectively than existing techniques whilst maintaining the ‘standard’ model of a BSP tree. Our idea is similar to Conflict Minimization proposed by Fuchs; the significant difference is that our algorithm recognizes that a polygon suitable for selection in the Minimization criterion may subsequently stop the remainder of polygons achieving some reductions in cuts—with Conflict Neutralization, such a polygon is demoted. We compare the results of Conflict Neutralization against Conflict Minimization, the Least‐crossed with Most‐crossed tie‐breaking criterion and our own, enhanced implementation of Conflict Minimization. We show how these techniques fall into different ‘depths of analysis’.

A number of related factors determine whether the ideal offered by parallel processing of a linear increase in performance with an increased number of processors is approached. It is vital to understand the nature of the application being ‘parallelised’ so that each factor can be considered for that application to determine if it is suitable for parallelisation. This paper demonstrates the value of analysing a serial implementation as part of understanding the application's nature. It also describes a parallel implementation of a divide-and-conquer parallel algorithm for determining the convex hull of a set of 2D points, following an earlier serial implementation. It is compared with an earlier parallelisation of the serial divide-and-conquer Preparata–Hong algorithm. It analyses the algorithms and determines the factors affecting their parallelisation. © 1998 John Wiley & Sons, Ltd.

Abstract Two parallel implementations of a 3D convex hull algorithm are reported. The paper considers a MIMD distributed memory architecture and the implementations are carried out on the Meiko Computing Surface using T800 transputers and the programming languages Occam and C. The first method uses a simple parallel geometric decomposition strategy and produces encouraging results. With the second approach a parallel generic Divide‐and‐Conquer kernel is incorporated. This is an example of the algorithmic skeleton approach to parallel programming and involves run‐time, dynamic allocation of work to processors. The resulting performances for both methods are measured and compared.

Abstract Recent studies have shown a connection between seasonal phytoplankton activity and generation of atmospheric sulphur products known to contribute towards acid rain [1]. Although anthropogenic sources of sulphur dioxide and sulphate dominate in acid &position on land surfaces, for some less industrialised areas of Europe, during the summer, there may be a significant contribution from natural marine sources. This paper describes briefly the nature of the marine processes thought to be taking place and survey cruises in the Southern North Sea used to collect data. Such field studies pose peculiar difficulties in both collection and processing of data. A critique on the nature of data generated under such conditions is included and some implications drawn for visualisation and interpretation techniques. Some initial results, with basic interpolation and approximation techniques, are compared. The paper concludes with suggestions on the way in which the research projects described are intended to befurther developed.

Abstract This paper discusses the problem of geometric degeneracies and outlines possible solutions when converting geometric algorithms into practice. It concentrates on the application of one of the suggested solutions, a perturbation technique, to a 2D convex hull program. An outline of the relevant theory and its conversion into practice is given. Experimental results are presented and discussed.

A detailed description of the implementation of a three-dimensional convex hull algorithm is given. The problems experienced in the production and testing of a correct and robust implementation of a geometric algorithm are discussed. Attention is paid to those issues that are often brushed over in the theoretical descriptions but cause errors in a real computation. These include degeneracies such as coplanar points, floating-point errors, and other special, but not necessarily degenerate, cases.

Abstract Sequential and parallel planar convex hull algorithms, their applications and some of the problems encountered on implementations are described. Details of Pascal implementations are given for three of the sequential algorithms: Graham's, Floyd‐Eddy and the Approximation method. The programs are compared experimentally.