Fast Ray Tracing of Arbitrary Implicit Surfaces with Interval and Affine Arithmetic

Existing techniques for rendering arbitrary-form implicit surfaces are limited, either in performance, correctness or flexibility. Ray tracing algorithms employing interval arithmetic (IA) or affine arithmetic (AA) for root-funding are robust and general in the class of surfaces they support, but traditionally slow. Nonetheless, implemented efficiently using a stack-driven iterative algorithm and SIMD vector instructions, these methods can achieve interactive performance for common algebraic surfaces on the CPU. A similar algorithm can also be implemented stacklessly, allowing for efficient ray tracing on the GPU. This paper presents these algorithms, as well as an inclusion-preserving reduced affine arithmetic (RAA) for faster ray-surface intersection. Shader metaprogramming allows for immediate and automatic generation of symbolic expressions and their interval or affine extensions. Moreover, we are able to render even complex forms robustly, in real-time at high resolution .     

Propagation algorithms for lexicographic ordering constraints

Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O(n) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq.     

Algorithm transformations for the data broadcast elimination method

VLSI technology has had tremendous success in revolutionizing computer design with processor arrays. Local communication and interconnection is a constraint that dictates the design of processor arrays. The shared bus and global access to memory are now no longer used, since they lower the speed. Consequently, parallel algorithms must be designed according to these constraints.

One of the problems that must be resolved for the above mentioned constraints is data broadcast elimination. Algorithms must be transformed into a form that uses data propagation instead of data broadcast.

Here systems of affine recurrence equations are analyzed and data broadcast is denned in context of the definition of data dependence and affine recurrence equations. A method for data broadcast elimination is introduced in [1] and expands the system of affine recurrence equations into new recurrence equations, that define data propagation and eliminates the data dependences where data broadcast occurs.

Parallel algorithms are usually given as a set of similar tasks repetitively performed on different data. The iteration form of presenting the algorithms is most common. Several techniques are introduced to transform the algorithm to a single assignment form of recurrence equations.

Some improvements of these techniques are presented to make the application of the data broadcast elimination method easier and more straight forward. The presented techniques are classified as the transformation of iterative algorithms to a recurrence form, the transformation of recurrence form to a single assignment form, and fulfilling the index forms of the algorithms.

A system of affine recurrence equations with the data broadcast property is always obtained by applying these procedures. The method of data broadcast elimination successfully transforms this system of affine recurrence equations into a system of uniform recurrence equations which can be used for parallel implementation on VLSI processor arrays.     

An Analysis of Arithmetic Constraints on Integer Intervals

Arithmetic constraints on integer intervals are supported in many constraint programming systems. We study here a number of approaches to implement constraint propagation for these constraints. To describe them we introduce integer interval arithmetic. Each approach is explained using appropriate proof rules that reduce the variable domains. We compare these approaches using a set of benchmarks. For the most promising approach we provide results that characterize the effect of constraint propagation. The work of the second author was supported by NWO, The Netherlands Organization for Scientific Research, under project number 612.069.003.     

Bounded error moving horizon state estimator for non-linear continuous-time systems: application to a bioprocess system

This paper investigates moving horizon state estimation (MHSE) within a bounded-error context for continuous-time systems. Verified integration of the non-linear ordinary differential equations used as system equation is achieved with interval Taylor expansions. In addition, interval constraint propagation techniques are used in order to reduce the pessimism due to interval arithmetic. The new MHSE method is illustrated with a bio-process system, for several lengths of the time horizon.     

An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint

Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we present an efficient algorithm for bounds consistency propagation of the generalized cardinality constraint (gcc). Using a variety of benchmark and random problems, we show that on some problems our bounds consistency algorithm can dramatically outperform existing state-of-the-art commercial implementations of constraint propagators for the gcc. We also present a new algorithm for domain consistency propagation of the gcc which improves on the worst-case performance of the best previous algorithm for problems that occur often in applications.     

An incremental algorithm for DLO quantifier elimination via constraint propagation

The first-order logical theory of dense linear order has long been known to admit quantifier elimination. This paper develops an explicit algorithm that yields an equivalent quantifier free form of its input formula. This algorithm performs existential quantifier elimination via constraint propagation. The result is computed incrementally using functional programming techniques. This approach may be of interest in implementing query languages for constraint databases.     

Effective strategic programming for Java developers

In object programming languages, the Visitor design pattern allows separation of algorithms and data structures. When applying this pattern to tree‐like structures, programmers are always confronted with the difficulty of making their code evolve. One reason is that the code implementing the algorithm is interwound with the code implementing the traversal inside the visitor. When implementing algorithms such as data analyses or transformations, encoding the traversal directly into the algorithm turns out to be cumbersome as this type of algorithm only focuses on a small part of the data‐structure model (e.g., program optimization). Unfortunately, typed programming languages like Java do not offer simple solutions for expressing generic traversals. Rewrite‐based languages like ELAN or Stratego have introduced the notion of strategies to express both generic traversal and rule application control in a declarative way. Starting from this approach, our goal was to make the notion of strategic programming available in a widely used language such as Java and thus to offer generic traversals in typed Java structures. In this paper, we present the strategy language SL that provides programming support for strategies in Java. Copyright © 2012 John Wiley & Sons, Ltd.     

Explaining circuit propagation

The circuit constraint is used to constrain a graph represented by a successor for each node, such that the resulting edges form a circuit. Circuit and its variants are important for various kinds of tour-finding, path-finding and graph problems. In this paper we examine how to integrate the circuit constraint, and its variants, into a lazy clause generation solver. To do so we must extend the constraint to explain its propagation. We consider various propagation algorithms for circuit and examine how best to explain each of them. We compare the effectiveness of each propagation algorithm once we use explanation, since adding explanation changes the trade-off between propagation complexity and power. Simpler propagators, although less powerful, may produce more reusable explanations. Even though the most powerful propagator considered for circuit and variants creates huge explanations, we find that explanation is highly advantageous for solving problems involving this kind of constraint.     

Application of Relational Interval Arithmetic to Computer Performance Analysis: a Survey

This paper presents a survey of the existing work in the area of interval-based performance analysis of computing systems. Intervals in performance analysis is required when uncertainties or variabilities exist in the workload parameters for the performance model of the system. Intervals are also useful for computing upper and lower bounds on system performance. Most conventional analytic models accept a set of single valued parameters and produce a single valued model output. Adaptation of these existing models to handle interval parameters require new techniques that use interval arithmetic. Experiences with relational interval arithmetic provided by a constraint logic programming language in solving a number of performance analysis problems in conventional multiprogrammed computers as well as distributed processing systems are described.     

Interval Methods for Accelerated Global Search in the Microsoft Excel Solver

This paper describes advanced interval methods for finding a global optimum and finding all solutions of a system of nonlinear equations, as implemented in the Premium Solver Platform, an extension of the Solver bundled with Microsoft Excel. It also describes the underlying tools that allow Excel spreadsheets to be evaluated over real and interval numbers, with fast computation of real gradients and interval gradients. The advanced interval methods described include mean value (MV) and generalized interval (GI) representations for functions, constraint propagation for both the MV and GI forms, and a linear programming test for the GI form, in the context of an overall interval branch and bound algorithm. Numerical results for a set of sample problems demonstrate a significant speed advantage for the GI techniques, compared to alternative methods.     

Solving Various Weighted Matching Problems with Constraints

This paper studies the resolution of (augmented) weighted matching problems within a constraint programming (CP) framework. The first contribution of the paper is a set of techniques that improves substantially the performance of branch-and-bound algorithms based on constraint propagation and the second contribution is the introduction of weighted matching as a global constraint ( WeightedMatching), that can be propagated using specialized incremental algorithms from Operations Research. We first compare programming techniques that use constraint propagation with specialized algorithms from Operations Research, such as the Busaker and Gowen flow algorithm or the Hungarian method. Although CP is shown not to be competitive with specialized polynomial algorithms for pure matching problems, the situation is different as soon as the problems are modified with additional constraints. Using the previously mentioned set of techniques, a simpler branch-and-bound algorithm based on constraint propagation can outperform a complex specialized algorithm. These techniques have been applied with success to the Traveling Salesman Problems [5], which can be seen as an augmented matching problem. We also show that an incremental version of the Hungarian method can be used to propagate a WeightedMatching constraint. This is an extension to the weighted case of the work of Régin [19], which we show to bring significant improvements on a timetabling example.     

Efficient Interval Linear Equality Solving in Constraint Logic Programming

Existing interval constraint logic programming languages, such as BNR Prolog, work under the framework of interval narrowing and are deficient in solving systems of linear constraints over real numbers, which constitute an important class of problems in engineering and other applications. In this paper, we suggest to separate linear equality constraint solving from inequality and non-linear constraint solving. The implementation of an efficient interval linear constraint solver, which is based on the preconditioned interval Gauss-Seidel method, is proposed. We show how the solver can be adapted to incremental execution and incorporated into a constraint logic programming language already equipped with a non-linear solver based on interval narrowing. The two solvers share common interval variables, interact and cooperate in a round-robin fashion during computation, resulting in an efficient interval constraint arithmetic language CIAL. The CIAL prototypes, based on CLP(R), are constructed and compared favorably against several major interval constraint logic programming languages.     

Implementing logical connectives in constraint programming

Combining constraints using logical connectives such as disjunction is ubiquitous in constraint programming, because it adds considerable expressive power to a constraint language. We explore the solver architecture needed to propagate such combinations of constraints efficiently. In particular we describe two new features named satisfying sets and constraint trees. We also make use of movable triggers (Gent et al., 2006) [1], and with these three complementary features we are able to make considerable efficiency gains.A key reason for the success of Boolean Satisfiability (SAT) solvers is their ability to propagate Or constraints efficiently, making use of movable triggers. We successfully generalise this approach to an Or of an arbitrary set of constraints, maintaining the crucial property that at most two constraints are active at any time, and no computation at all is done on the others. We also give an And propagator within our framework, which may be embedded within the Or. Using this approach, we demonstrate speedups of over 10,000 times in some cases, compared to traditional constraint programming approaches. We also prove that the Or algorithm enforces generalised arc consistency (GAC) when all its child constraints have a GAC propagator, and no variables are shared between children. By extending the Or propagator, we present a propagator for AtLeastK, which expresses that at least k of its child constraints are satisfied in any solution.Some logical expressions (e.g. exclusive-or) cannot be compactly expressed using And, Or and AtLeastK. Therefore we investigate reification of constraints. We present a fast generic algorithm for reification using satisfying sets and movable triggers.     

Robust design based on constraint networks

This paper describes a robust design method using constraint networks. As opposed to the traditional statistical robust methodology, the proposed method gives a valid model to analyze parameter uncertainties so as to predict conflicts in concurrent design. The mathematical model, which reflects the requirements of robust design, is given in the paper. A general consistency algorithm is designed using interval arithmetic to refine the intervals. This paper also proves that the consistency algorithm is arc consistent if the constraint network is integrated. The constraint network uses the consistency algorithm to verify the design process early in the process and to assist the designers in determining design variables to reduce the multidisciplinary iterations in concurrent design. The quantitative effect of downstream constraints can be analyzed before determining design parameters and potential conflicts can be predicted. A layout design example shows the validity of the method.     

Constrained global optimization for wine blending

Assemblage consists in blending base wines in order to create target wines. Recent developments in aroma analysis allow us to measure chemical compounds impacting the taste of wines. This chemical analysis makes it possible to design a decision tool for the following problem: given a set of target wines, determine which volumes must be extracted from each base wine to produce wines that satisfy constraints on aroma concentration, volumes, alcohol contents and price. This paper describes the modeling of wine assemblage as a mixed constrained optimization problem, where the main goal is to minimize the gap to the desired concentrations for every aromatic criterion. The deterministic branch and bound solvers Couenne and IbexOpt behave well on the wine blending problem thanks to their interval constraint propagation/programming and polyhedral relaxation methods. We also study the performance of other optimization goals that could be embedded in a configuration tool, where the different possible interactions amount to solving the same constraints with different objective functions. We finally show on a recent generic wine blending instance that the proposed optimization process scales up well with the number of base wines.     

A Comparison of verified distance computation between implicit objects using different arithmetics for range enclosure

This paper describes a new algorithm for computing verified bounds on the distance between two arbitrary fat implicit objects. The algorithm dissects the objects into axis-aligned boxes by constructing an adaptive hierarchical decomposition during runtime. Actual distance computation is performed on the cubes independently of the original object’s complexity. As the whole decomposition process and the distance computation are carried out using verified techniques like interval arithmetic, the calculated bounds are rigorous. In the second part of the paper, we test our algorithm using 18 different test cases, split up into 5 groups. Each group represents a different level of complexity, ranging from simple surfaces like the sphere to more complex surfaces like the Kleins bottle. The algorithm is independent of the actual technique for range bounding, which allows us to compare different verified arithmetics. Using our newly developed uniform framework for verified computations, we perform tests with interval arithmetic, centered forms, affine arithmetic and Taylor models. Finally, we compare them based on the time needed for deriving verified bounds with a user defined accuracy.     

Interval propagation to reason about sets: Definition and implementation of a practical language

Local consistency techniques have been introduced in logic programming in order to extend the application domain of logic programming languages. The existing languages based on these techniques consider arithmetic constraints applied to variables ranging over finite integer domains. This makes difficult a natural and concise modelling as well as an efficient solving of a class of NP-complete combinatorial search problems dealing with sets. To overcome these problems, we propose a solution which consists in extending the notion of integer domains to that of set domains (sets of sets). We specify a set domain by an interval whose lower and upper bounds are known sets, ordered by set inclusion. We define the formal and practical framework of a new constraint logic programming language over set domains, called Conjunto. Conjunto comprises the usual set operation symbols (, , \), and the set inclusion relation (% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeaacaGaaiaabeqaamaabaabaaGcbaGaeyOHI0maaa!37EA!\[ \subseteq \]). Set expressions built using the operation symbols are interpreted as relations (s s ₁ = s ₂, ...). In addition, Conjunto provides us with a set of constraints called graduated constraints (e.g. the set cardinality) which map sets onto arithmetic terms. This allows us to handle optimization problems by applying a cost function to the quantifiable, i.e., arithmetic, terms which are associated to set terms. The constraint solving in Conjunto is based on local consistency techniques using interval reasoning which are extended to handle set constraints. The main contribution of this paper concerns the formal definition of the language and its design and implementation as a practical language.     

The design of the Boost interval arithmetic library

We present the design of the Boost interval arithmetic library, a C++$++$ library designed to handle mathematical intervals efficiently and in a generic way. Interval computations are an essential tool for reliable computing. Increasingly a number of mathematical proofs have relied on global optimization problems solved using branch-and-bound algorithms with interval computations; it is therefore extremely important to have a mathematically correct implementation of interval arithmetic. Various implementations exist with diverse semantics. Our design is unique in that it uses policies to specify three independent variable behaviors: rounding, checking, and comparisons. As a result, with the proper policies, our interval library is able to emulate almost any of the specialized libraries available for interval arithmetic, without any loss of performance nor sacrificing the ease of use. This library is openly available at www.boost.org.