Although numerous pre-filtering and area sampling antialiasing techniques have been devised, few are capable of rendering complex, self-intersecting polygons. This paper presents a new antialiasing method capable of handling such polygons, according to any fill rule. The method is based on area sampling and is hence free from the visual aliasing artifacts of super sampling associated with near horizontal edges. It works by decomposing the coverage area of a polygon within each pixel into separate constituent regions, which are simple regions whose areas can be easily computed. The decomposition step does not attempt to generate non-overlapping regions, unlike that employed by existing methods, and hence operates very efficiently. This, together with other novel approximation techniques in the recombination stage allow pixel coverage areas to estimated with an efficiency approaching that of super sampling.

Although much research in machine learning has been carried out on acquiring knowledge for problem-solving in many problem domains, little effort has been focused on learning search-control knowledge for solving optimization problems. This paper reports on the development of SHAPES, a system that learns heuristic search guidance for solving optimization problems in intractable, under-constrained domains based on the Explanation-Based Learning (EBL) framework. The system embodies two new and novel approaches to machine learning. First, it makes use of explanations of varying levels of approximation as a mean for verifying heuristic-based decisions, allowing heuristic estimates to be revised and corrected during problem-solving. The provision of such a revision mechanism is particularly important when working in intractable and under-constrained domains, where heuristics tend to be highly over-generalized, and hence at times will give rise to incorrect results. Second, it employs a new linear and quadratic programming-based weight-assignment algorithm formulated to direct search toward optimal solutions under best-first search. The algorithm offers a direct method for assigning rule strengths and, in so doing, avoids the need to address the credit-assignment problem faced by other iterative weight-adjustment methods.