Swansea University crest

Research Reports for 2008

CSR 1-2008
The OKlibrary: A generative research platform for (generalised) SAT solving
Oliver Kullmann
abstract    PDF
CSR 2-2008
Programming experimental procedures for Newtonian kinematic machines
E J Beggs and J V Tucker
abstract    PDF
CSR 3-2008
The Data Type of Spatial Objects
K. Johnson and J V Tucker
abstract    PDF
CSR 4-2008
Row Tracing using Hierarchical Occlusion Maps
Ravi P. Kammaje and Benjamin Mora
abstract    PDF
CSR 5-2008
On the Lower Complexity of Coherent Renderings
Benjamin Mora, Ravi Kammaje and Mark W. Jones
abstract    PDF
CSR 6-2008
The Complexity of Coherent Rendering
Benjamin Mora, Ravi Kammaje and Mark W. Jones
abstract    PDF
CSR 7-2008
Fundaments of Branching Heuristics: Theory and Examples
Oliver Kullmann
abstract    PDF
CSR 8-2008
Present and future of practical SAT solving
Oliver Kullmann
abstract    PDF
CSR 9-2008
Studies on Contraction Flows and Pressure-Drops - Extensional Viscosity and Dissipative Stress Effects
H.R. Tamaddon-Jahromi, F.S Syed and M. F. Webster
abstract    PDF
CSR 10-2008
COMPUTATIONAL RHEOLGY
M.F. Webster, H.R. Tamaddon-Jahromi and F. Belblidia
abstract    PDF
CSR 11-2008
Numerical modeling of step-strain for stretched filaments
M.F. Webster, H. Matallah, K.S. Sujatha and M.J. Banaai
abstract    PDF
CSR 12-2008
Experimental and Computational Aspects of Some Contraction Flows of Highly Elastic Liquids and Their Impact on The Relevance of the Couette Correction in Extensional Rheology
K. Walters, M.F. Webster, H.R.Tamaddon-Jahromi
abstract    PDF
CSR 13-2008
The dynamics of compressible Herschel-Bulkley fluids in die-swell flows
F. Belblidia, T. Haroon and M. F. Webster
abstract    PDF
CSR 14-2008
Updating Objective-C
David Chisnall
abstract    PDF
CSR 15-2008
Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic
Arnold Beckmann and Samuel R. Buss
abstract    PDF
CSR 16-2008
Automatic Generation of 3D Computer Caricatures based on Artistic Deformation Styles
Lyndsey Clarke, Min Chen and Benjamin Mora
abstract    PDF

CSR 1-2008 The OKlibrary: A generative research platform for (generalised) SAT solving

Oliver Kullmann

The OKlibrary is introduced, an active library supporting research and
development in the area of generalised SAT-solving, available at http://www.
ok-sat-library.org. We discuss motivation and architecture of the library,
and outline its current extend. A key idea is the notion of “generalised satisfiability
problems” as a generalisation of SAT towards CSP, and we discuss
the basic ideas.
Report Titles

CSR 2-2008 Programming experimental procedures for Newtonian kinematic machines

E J Beggs and J V Tucker

By experimental computation we mean the idea of computing a function by experimenting with some physical equipment. To analyse the functions computable by experiment, we are developing a methodology that chooses a precise specification of a physical theory T and derives precise descriptions of the procedures and equipment the theory allows. As a case study, we choose a fragment T of Newtonian kinematics and describe a language EP(T), and some of its extensions, for expressing experimental procedures allowed by T. The languages for experimental procedures are similar to imperative programming languages that express algorithmic procedures. We show that EP(T) can define all functions on the rational numbers that are definable by algorithms.
Report Titles

CSR 3-2008 The Data Type of Spatial Objects machines

K. Johnson and J V Tucker

A spatial object consists of data assigned to points in a space. We develop an algebraic theory of spatial objects by modelling abstract data types of spatial objects as topological algebras of functions. One useful algebra is that of continuous functions, with operations lifted from operations on space and data, and equipped with the compact- open topology. We use terms as abstract syntax for de ning spatial objects and conditional equational specifications for reasoning. We pose a completeness problem: Given a selection of operations on spatial objects, do the terms approximate all the spatial objects to arbitrary accuracy? We give some general methods for solving the problem and consider their application to spatial objects with real number attributes.
Report Titles

CSR 4-2008 Row Tracing using Hierarchical Occlusion Maps

Ravi P. Kammaje and Benjamin Mora

A new rendering method that aims to achieve high speeds by incorporating the use of hierarchical occlusion maps and concepts from Ray Tracing and Scanline Rendering is presented. Instead of considering only the intersections between a single ray(or a packet of rays) and the scene as regular ray–tracing algorithms do, our technique investigates the use of an entire row of pixels. This moves some of the ray–tracing computations into a simplified 1D domain and appears to reduce the memory requirements considerably. When multi–threaded on a quad–core computer, the algorithm shows near perfect speedup. For each line, an occlusion map that represents parts of the image line that are occluded is maintained. This combination of using a spatial subdivision data structure and a hierarchical occlusion map results in highly reduced intersection and traversal steps thus reducing the time required for rendering.
Report Titles

CSR 5-2008 On the Lower Complexity of Coherent Renderings

Benjamin Mora, Ravi Kammaje and Mark W. Jones

This paper demonstrates the fundamental theoretical result that isosurface and 3D mesh rendering can often be achieved at an average O(1) complexity for first-hit rays when rendering can be made coherent. This is in comparison to O(Log(n)) complexity normally associated with ray-tracing. More specifically, complexity of coherent rendering must be expressed as an asymptotic function of two variables - the scene size and the number of rays considered. The new complexity results are achieved by combining image coherence and object coherence during the traversal of spatial subdivision structures.
Two variants of the same algorithm have been implemented and rigorous testing of their asymptotic behavior support our assertions. One implementation demonstrates that an n^2 isosurface image of an n^3 dataset can be rendered at O(n^2) complexity, and the second demonstrates that for sufficiently large image sizes, a 12 million triangle scene can be rendered at approximately the same speed as a single triangle scene.
Report Titles

CSR 6-2008 The Complexity of Coherent Rendering

Benjamin Mora, Ravi Kammaje and Mark W. Jones

This paper demonstrates the fundamental result that isosurface and 3D mesh rendering can be achieved at an average O(1) complexity per pixel with an appropriate implementation of coherent rendering, whereas traditional techniques like regular ray-tracing only achieve O(Log(n)) at best. This result is achieved by combining image and object coherence during the traversal of spatial subdivision structures.
To verify our assertion, two variants of the algorithm have been implemented. One demonstrates that a n3 dataset isosurface can be rendered in a n2 image at an O(n2) complexity, and the second demonstrates that a 12 million triangle scene can be rendered at approximately the same speed as a single triangle scene for sufficiently large images.
Report Titles

CSR 7-2008 Fundaments of Branching Heuristics: Theory and Examples

Oliver Kullmann

The foundations for the theory of heuristics for backtracking algorithms,
governing the choice of branchings, are developed in an abstract framework.
This work can be seen as a survey on underlying methods and ideas, unifying
three streams, namely ideas from worst-case analysis of algorithms, a method
by Donald E. Knuth to estimate tree sizes, and the essence of practical experience
gained in the last 40 years. But also for the first time these ideas
are put into a coherent framework, and new possibilities emerge regarding
the construction of optimised heuristics, important for practical applications.
Specialising on SAT algorithms, the basic heuristics are discussed. Also the
problem of the ordering of branchings is considered, and the basic approaches
are outlined.
Report Titles

CSR 8-2008 Present and future of practical SAT solving

Oliver Kullmann

We review current SAT solving, concentrating on the two paradigms of
conflict-driven and look-ahead solvers, and with a view towards the unification
of these two paradigms. A general “modern” scheme for DPLL algorithms is
presented, which allows natural representations for “modern” solvers of these
two types.
Report Titles

CSR 9-2008 Studies on Contraction Flows and Pressure-Drops - Extensional Viscosity and Dissipative Stress Effects

H.R. Tamaddon-Jahromi, F.S Syed and M. F. Webster

In this paper, we explore the ability of network-type models (Phan-Thien/Tanner PTT) to reflect enhanced pressure drops in contraction/expansion flows (ratio 4:1:4). Severe strain hardening is captured through suitable parametric control, whilst ensuring strong suppression of shear-thinning properties, to approximate those of typical solvent dominated Boger fluids. This advances upon our prior work with Oldroyd models. The position is further contrasted against that for dissipative stress models, where both inelastic and viscoelastic models are introduced with some interesting consequences. The numerical techniques adopted follow a hybrid finite element/volume algorithm of incremental pressure-correction time-stepping structure.
Report Titles

CSR 10-2008 COMPUTATIONAL RHEOLGY

M.F. Webster, H.R. Tamaddon-Jahromi and F. Belblidia

This chapter offers a general overview of the present state of the art in the field of computational rheology, emphasizing the various numerical challenges that have emerged through the material modeling and discretisation approaches adopted. There is brief coverage of the alternative levels of modeling involved, from macroscopic to mesoscopic, alongside the different discrete techniques utilized and the challenges posed by prescribed benchmark problems. Progress in the field is described historically through consideration of a particular benchmark problem, contraction flow, detailing advances in experimental, numerical and analytical developments, that illustrate the many branches of computational rheology. Several case studies are also presented that illustrate some selected applications, covering such interests areas as transient flow solutions, kinetic-based models, pressure drop analysis and compressible-viscoelastic computations.
Report Titles

CSR 11-2008 Numerical modeling of step-strain for stretched filaments

M.F. Webster, H. Matallah, K.S. Sujatha and M.J. Banaai

This article addresses the modelling of filament-stretching/step-strain deformation under viscoelastic capillary breakup configurations of the CaBER-type. Start-up, prior to step-strain, is conducted under constant stretch-rate synchronous plate-retraction with impulsive sessation of plate motion. The study encompasses variation in material rheology, appealing to Oldroyd, Geisekus and Phan-Thien/Tanner type models, which display differences in shear and extensional viscosity properties (shear-thinning/extension-hardening). Two different viscosity ratio settings are considered to reflect high and low-solvent viscosity constituent components; the former representing typical Boger fluids, the latter high polymer concentration fluids. We compare and contrast results for three alternative filament aspect-ratios at the onset of step-strain. Throughout the step-strain period, we have been able to successfully capture such physical features as drainage to the filament feet, necking at the filament centre, and periods with travelling waves through the axial filament length. In addition, we have identified the suppressive influence that larger capillary forces have upon radial fluctuations, and the minor impact that gravitational forces have upon the ensuing deformation. From this study, estimates for rheometrical data have been derived in terms of characteristic material relaxation time and apparent extensional viscosity. The computational techniques employed include a compressed-mesh (CM) procedure, an Arbitrary Lagrangian-Eulerian scheme (ALE) and a free-surface particle tracking technique. Spatial discretisation of the problem is accomplished through a hybrid finite element/finite volume algorithm implemented in the form of a time-stepping incremental pressure-correction formulation.
Report Titles

CSR 12-2008 Experimental and Computational Aspects of Some Contraction Flows of Highly Elastic Liquids and Their Impact on The Relevance of the Couette Correction in Extensional Rheology

K. Walters, M.F. Webster, H.R.Tamaddon-Jahromi

Existing experimental data on planar and axisymmetric contraction flows of constant-viscosity and shear-thinning elastic liquids have presented rheologists with some provocative challenges, which we hope to address in this lecture by carrying out numerical simulations for various constitutive models. Amongst the questions we hope to address are the following:

  1. Why do constant-viscosity Boger fluids behave so differently in planar and axisymmetric contractions, when the same is not true for shear-thinning fluids?
  1. Why do existing numerical simulations for the Oldroyd B model fail to predict the significant increases observed in the Couette correction for Boger fluids?
  1. What are the roles of ‘normal stress differences’ and ‘extensional viscosity’ in determining the Couette correction?
  1. What is the future for contraction-flow experiments in providing a measure of “resistance to stretch”?

In order to make headway, we shall concentrate on the contraction-expansion 4:1:4 geometry with rounded corners, which from a numerical standpoint is easier to handle than the more popular 4:1 contraction geometry with sharp corners. (There is sufficient evidence in the experimental literature to indicate that the expansion-contraction geometry shows many of the features found in the 4:1 contraction geometry).
Report Titles

CSR 13-2008 The dynamics of compressible Herschel-Bulkley fluids in die-swell flow

F. Belblidia, T. Haroon and M. F. Webster

In a variety of industrial applications, modelling compressible inelastic free-surface flows remains a numerical challenge. This is largely due to the physical phenomena involved and the computational cost associated with the simulations of such flows. In particular, the die-swell benchmark problem is characterised by specific features. These are related to the presence of a sharp separation point at the die-exit, the location and the shape of the free-surface, and additionally the consideration of fluid compressibility under various forms of material modelling.

In this article, a time-marching pressure-correction scheme is considered to solve both incompressible and compressible inelastic flows. This is achieved via a pressure-based approach within a finite element framework employing efficient high-order time-stepping schemes. A Tait-type model is utilised to express the equation of state that links density to pressure, so that pressure is retained as a primary variable.

Various material models are considered in this numerical study for the die-swell problem, where the material rheological characteristics have a direct impact upon the location and form of the free-surface. Initially, unyielded material is considered through Newtonian and power-law assumptions. Further complication is then introduced through the Bingham model, where fluid yield stress is taken into account. More general rheological modelling is constructed via the Herschel–Bulkley model, combining inelastic behaviour with yield stress presence. This is complimented by relaxing incompressible assumptions, allowing the effects of compressibility to enter the problem.

Results are presented for steady and transient flow scenarios and numerical solutions are validated against published data. There is Focus upon on the effect of variation in compressibility parameter setting, inertia level, power-law index and yield stress level, with regard to the evolving shape/location of the free-surface and the response in extrudate swell. Extrudate swell is observed to decline with decrease in power-law index. With increase in Reynolds number, extrudate swell decreases before finally reaching a plateau at high Reynolds number, in agreement with experimental results. Swelling also decreases with rise in yield stress levels. The combination of these parameters within the compressible Herschel–Bulkley model renders it difficult to predict, a priori, the outcome in terms of die-swell behaviour.
Report Titles

CSR 14-2008 Updating Objective-C

David Chisnall

The Objective-C language is over two decades old. Since its creation, numerous advances in the area of object oriented programming have been made. This report presents implementations of several of these ideas in Objective-C, including traits, mixins, futures and prototype-based object orientation. This serves to highlights how original design decisions in the language have allowed new concepts to be added and how others have limited the exibility of the language.
Report Titles

CSR 15-2008 Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic

Arnold Beckmann and Samuel R. Buss

The complexity class of Πpk-polynomial local search (PLS) problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1 ≤ i ≤ k + 1, the Σpi-definable functions of Tk+12 are characterized in terms of Πpk-PLS problems. These Πpk-PLS problems can be defined in a weak base theory such as S12, and proved to be total in Tk+12. Furthermore, the Πpk-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new ∀Σb1 (α)-principle that is conjectured to separate Tk2(α) and Tk+12(α).
Report Titles

CSR 16-2008 Automatic Generation of 3D Computer Caricatures based on Artistic Deformation Styles

Lyndsey Clarke, Min Chen and Benjamin Mora

Caricatures are a form of humorous visual art, usually created by skilled artists for the intention of amusement
and entertainment. In this paper, we present a novel approach for automatic generation of a computer caricature from a facial photograph, which captures artistic deformation styles from hand-drawn caricatures. In order to achieve this, we propose a pseudo stress-strain model to encode the parameters of an artistic deformation style using ‘virtual’ physical and material properties. We have also developed a software system for performing the caricaturistic deformation in 3D which eliminates the undesirable artefacts in 2D caricaturisation. We employed a Multi-level Free-Form Deformation (MFFD) technique to optimize a 3D head model reconstructed from an input facial photograph, and also for controlling the caricaturistic deformation. Our results demonstrated the effectiveness and usability of the proposed approach and the developed techniques, which allow everyday users to apply the captured and stored deformation styles to a variety of facial photographs.
Report Titles