Hi Fidelity Visualisation and Simulation

Chris Thorne

December 2007
dragonmagi at gmail.com

View my page on Association of Virtual Worlds

Key words: Simulation, floating point, precision, spatial jitter, positional, rendering, physics, fidelity, truth, center, accuracy, 3D graphics, computation, scalability, design, architecture, software, coordinate, origin.

Raising the simulation fidelity bar

This document and my PhD are part of my efforts to raise the world of modelling, visualisation and simulation to a new level of fidelity: improving scalability, the quality and fidelity of motion, interaction and rendering; and the accuracy and the repeatability of physics. These benefits are offered at little or no performance cost but with the potential for improved performance. A rare win-win situation. For simplicity, hereafter I will refer to modelling, visualisation and simulation as just simulation.

The problem: limited and inconsistent fidelity, quality and scalability

The truth is not as true as it could be

When looking at a result from a computer we are making an observation: observing a simulation viewed from a particular perspective as video output, or perhaps the evaluation of an equation as a printed numerical value. Often the results are not as accurate as the underlying computer system is capable of producing. This poorer fidelity is due to designers' inadequate understanding of fundamental properties of floating point positional spaces, a scarcity of good guidance on what to do about problems such as spatial jitter and the lack of a holistic approach to minimising error throughout the simulation pipeline. In many cases such error goes unnoticed because there is no obvious visible sign of something wrong, but in some cases the error can be seen in the form of jittery motion and other effects described below.

Symptoms: jitter, rendering artifacts, poor scalability and inconsistent physics

Jittery motion and rendering artifacts, such as tearing or flashing, are often observed when large scale spaces are employed, e.g. as a full scale model of the Earth. These effects occur when objects or viewpoints have large coordinate values, that is, at large distances from the origin. Many experiments were conducted to investigate these effects and develop an understanding of the underlying causes. Descriptions and programs are included here to show some of these effects: motion spatial jitter, positional jitter, break-up of models and z buffer order, rendering artifacts, and physics. The following describes the key causes of these effects.

Causes

Execution environment: the precision funnel

Simulations execute in a pipeline of successive processing stages with progressively decreasing floating point precision: a precision funnel. The hardware of the final graphical output stage has at most 32bit precision (single precision) for coordinates and sometimes as little as 24 or 16 bit. Early stages of the pipeline are executed on a general purpose client CPU and possibly also on a server. The client and server CPUs afford higher precision, such as double precision.

The literature review revealed a common assumption that insufficient precision is the sole cause of jitter and related problems. Consequently, solutions were designed to address these problems by using higher precision variables. However, the precision funnel cannot be avoided using this approach because the final stage hardware remains low precision. Therefore just using higher precision in earlier stages yields limited benefit.

Another important part of the problem equation is a poorly understood or often overlooked property of simulation space: its nonuniform resolution.

Simulation space resolution is not uniform

Figure 1: The sfumato painting technique, used by Leonardo da Vinci on the Mona Lisa, increases in `smokiness' outwards from the center. Similarly, simulation exhibits a degradation in the quality of rendering as the viewpoint moves outwards from the origin. This is because simulation space is defined by a floating point coordinate system. Floating point numbers have a decreasing resolution of representable values with increasing distance from the origin, as shown in Figure 2 below.

decreasing resolution of floating point with distance

Figure 2: The nonuniform resolution of floating point numbers leads to an increase in error, degrading quality outwards from the origin. The resolution induced error, or spatial error, can be a more significant cause of rendering artifacts than limited precision in large scale systems. In addition to affecting rendering, spatial error causes jittery motion and interaction and can introduce unacceptable error into physics and other calculations.

Time error

As with spatial position, if time values are represented in floating point are large then a simulation can show perceivable changes and inconsistent behaviour. The physics experiments show an example of this effect. In fact, computation using any positional floating point number are sensitive to the positional error induced problems discussed here.

Relative spatial error and propagation

Relative error in calculation is traditionally determined using the rules of numerical error math. E.g. e_{x+y} = e_x + e_y and for multiplication: e_{xy} = ye_x * xe_y. However, such methods do not take into account the error inherent in the simulation space itself, the spatial component of which is calculated using Pythagoras' Theorem. Figure 3 below illustrates how coordinates are quantised to discrete locations in simulation space. A region of space showing two boxes delineating machine representable positions for coordinates (the nearest red spheres). The corners of both boxes are the only representable coordinate values for the real valued coordinates (x,y,z) and (x',y',z'). In a computer, (x,y,z) and (x',y',z') will be quantised to (or 'moved' to) one of the surrounding 8 representable coordinates that each can have (the nearest red spheres). The maximum positional error for point (x,y,z) is if it moves along the diagonal AC to either A or C. This error is therefore equal to half the distance between A and C and calculated by Pythagoras' Theorem.

Geometric property of relative spatial error

To estimate the maximum contribution of spatial error to error in a simulation, one must consider the relative spatial error between two points, because a simulation involves more than one object's location. Even when there is just one object, the viewpoint also has a position and hence there are at least two locations. When each location moves in opposite directions, this is a pathological case of diversion. The largest diversion occurs when they diverge along the diagonals of the cubes and this error is represented by half of the (AC+AB) distances. Alternatively, a pathological conversion to point A could occur if each point was closer to the sphere common to both cubes. This is potentially worse as calculations that divide by the distance between (x,y,z) and (x',y',z') will produce a divide by 0 error. As distance from the origin increases, the gap between representable points increases and so therefore does the relative spatial error.

Although relative spatial error is itself calculated differently, when used in a scalar result such as a distance computation, it can be incorporated into normal relative error estimation of algebraic equations using the usual rules of relative error calculation, described above. The maximum relative error for a simulation propagates exponentially with the number of operations performed. This exponential propagation is must also be taken into account in any estimation of maximum simulation error.

Figure 3: A region of space showing two boxes delineating machine representable positions for coordinates (the nearest red spheres).

Core solution to minimising simulation error: a continuous floating origin

"The engines don't move the ship at all!
The ship stays where it is and the
engines move the universe around it!"
Cubert Farnsworth, in A Clone of my Own, Futurama, Season 2, Episode 5

Since decreasing resolution with distance from the origin is a major cause of positional error and the fidelity of simulation space is highest around the origin, the solution begins with keeping the viewpoint at the origin and moving objects in the other direction instead of the conventional approach of moving the viewpoint through space. This is called a continuous floating origin because the origin "floats" with you as you navigate a continuous space. In this approach navigation does not move one through the virtual universe in a similar way the Planet Express ship does not move Cubert through the Futurama universe. Yet in both cases one can visit all parts of the universe!

The floating origin method leads to useful improvements in fidelity, rendering quality and scalability. This link shows a video of navigation from space to face, illustrating how the approach enhances scalability. The video is of a full scale planet earth modelled in one continuous single precision coordinate space. Without shifting the origin it is not possible to navigate an avatar at ground level after zooming in from space, given present day graphics hardware.

As Cubert Farnsworth found, one has to think about things differently to fully comprehend the solution. Think about moving objects around you, not moving through the environment; about resolution not precision; and about algorithms that exploit efficiencies resulting form keeping the observer at the center of space and time. The core floating origin idea spawns a suite of origin-centric techniques, process guidelines and a new simulation architecture, which together improve the fidelity and even performance of simulation.

Summary

"Men should not travel, Brutha.
At the center there is truth.
As you travel, so error creeps in."
Small Gods by Terry Pratchett

Computers are generally incapable of providing the exact truth, but an origin centric system provides greater truth due to its greater accuracy. We can rephrase the advice to Brutha by saying, for computer simulation: there is greater truth at the center.

The thesis presents techniques, analytical tools, architecture and process guidelines that holistically address the problem domain with a new origin-centric paradigm for positional computing. Along with the required change in thinking about the problem and solution, his new positional computing paradigm yields many benefits in the form of a continuous rendering space, increased accuracy, smoother motion, higher fidelity rendering and interaction, greater scalability and, in some cases, better performance.

References/links of interest

This document:
Thorne, C. G., 2007. Hi Fidelity Visualisation and Simulation, http://floatingorigin.com/

PhD thesis:
THORNE, C. 2007. Origin-centric techniques for optimising scalability and the fidelity of motion, interaction and rendering, PhD Thesis, University of Western Australia. School of Computer Science and Software Engineering, http://theses.library.uwa.edu.au/adt-WU2008.0177, see also http://floatingorigin.com/ThorneThesis.pdf

A geospatial recommendation to the Web3D Consortium:
Thorne, C. G., 2005. Next Steps for X3D Geospatial Specification,
http://www.web3d.org/x3d-earth/meetings/2007November/NextStepsForGeospatial.pdf
some of which which has tentatively been adopted (2009):
http://www.web3d.org/images/uploads/news/X3D-EarthMeetingingMBARI_5-6March2009_(2).pdf

Further references can be found in publications arising and the bibliography mirror.

Additional Information

Some additional information is provided in this appendix.

--
updated April 2009