waashk/acm huggingface dataset:
vision in film and special effects computer vision techniques have become increasingly important in visual effects. when a digital artist inserts an effect into a live-action scene, the more information that they know about the scene, the better. in visual effects, we use vision techniques to calculate the location of the camera, construct a 3d model of the scene and follow objects as they move through the scene.think back to the 1980s, before computer graphics in special effects really took hold. in most of the films of that era, it was very easy to spot the "effects shot" in a film. the give-away was the sudden halting of a previously dynamic, moving camera. this was done because inserting a special effect character or object into a scene with a moving camera was very difficult. the camera move used in filming the live action part of the scene must be exactly reproduced by the camera on the effects set when the model or puppet is filmed. to accomplish this, one of two techniques were employed: 1) mechanical devices were used to encode the motion of the camera and then the encoded information was used to control the motion of the camera on the effects set, or 2) an experienced motion control engineer matched the move by eye. both of these techniques are terribly prone to error and were used only on high budget productions.in the 1990s with the advent of widespread computer generated effects and digital scanning of film, it became possible to apply computer vision techniques to extract information from the scene to aid the digital artist in blending an effect with the reality of the filmed image. doug roble
semantics of interactive rotations  we first outline an overall design philosophy for rigid geometric manipulations, then examine a manipulation's characteristics: nesting, scope, pivot constraints, and axis, constraints. we show how a mnemonic notation helps us explain how a simple matrix operation can make manipulations (both rotations and translations) nested within rotations easy to control. finally, we mention some practical considerations to increase calculation speed and control numerical error. an appendix collects formulas useful for working with rotations.  michael e. pique
integrating solid image capability into a general purpose calligraphic graphics package  raster scanned graphics terminals provide several features not found in standard line drawing displays. among them are area fill and an extensive color palette. hardware support for such functions is becoming cost effective and available in a variety of forms. what is now needed is high level, device independent software that assists in the generation of and interaction with these terminals. to accomplish this, a project has been undertaken jointly by sandia laboratories, purdue university, and megatek corporation to integrate solid image capabilities into the graphics compatibility system, gcs. gcs is a widely used, general purpose calligraphic graphics package. due to the similarity of the gcs model to that of the gspc core system, gcs provides a timely test bed for solid image extensions to a line drawing package. this paper will summarize the capabilities being implemented, the method and motivation behind each function, and suggestions for further work.  the heart of the extensions is a hidden surface algorithm similar to myers' approach which combines the simplicity of a z buffer with the efficiency of a watkin's algorithm. facilities will be provided for hidden line removal as well as hidden surface processing in order to satisfy the basic gcs design goal of device independence. in this way, random vector terminals as well as raster devices will benefit.  if a user does not require hidden object processing then very little additional overhead will remain in those routines which have been called. hidden surface processing may also be intermixed with wire frame drawings and text.  two remaining issues are the user interface for 3d object definition and the specification of lighting models. since the myers algorithm requires n sided polygons as input, a basic call has been provided for such definitions. higher level constructs, called "shells" and "faces", which facilitate creation of complex 3d bodies, have been implemented.  the specification of lighting models is an area of considerable debate. it has been concluded that a choice of a few common models will be made available to the user. these include interpolated and noninterpolated shading (smooth and flat). objects may be color-shaded or black-and-white. a hook is provided for user definition of more exotic lighting models.  g. laib r. puk g. stowell
automation of simulation model generation from system specifications  major advances in simulation techniques have in the past resulted from refinement of our understanding of the modeling process itself. the encapsulation of frequently used functions into standard packages gave rise to the original simulation languages. the recognition of frequently used concepts gave rise to current model-based simulation systems. the separation of the model frame from the experimental frame is just beginning to see implementation in commercially available decision support systems. we believe the next major advance will come from a better understanding of the relationship between the representation (or description) of the system itself and the models/experiments which are performed to satisfy a particular goal. we are currently working towards a modeling paradigm in which a system specification frame and a goal specification frame are formally recognized as distinct from the simulation modeling, experimental, and implementation frames.  richard j. mayer robert e. young
example-based hinting of true type fonts  hinting in truetype is a time-consuming manual process in which a typographer creates a sequence of instructions for better fitting the characters of a font to a grid of pixels. in this paper, we propose a new method for automatically hinting truetype fonts by transferring hints of one font to another. given a hinted source font and a target font without hints, our method matches the outlines of corresponding glyphs in each font, and then translates all of the individual hints for each glyph from the source to the target font. it also translates the control value table (cvt) entries, which are used to unify feature sizes across a font. the resulting hinted font already provides a great improvement over the unhinted version. more importantly, the translated hints, which preserve the sound, hand-designed hinting structure of the original font, provide a very good starting point for a professional typographer to complete and fine-tune, saving time and increasing productivity. we demonstrate our approach with examples of automatically hinted fonts at typical display sizes and screen resolutions. we also provide estimates of the time saved by a professional typographer in hinting new fonts using this semi-automatic approach.  douglas e. zongker geraldine wade david h. salesin
compositing digital images  most computer graphics pictures have been computed all at once, so that the rendering program takes care of all computations relating to the overlap of objects. there are several applications, however, where elements must be rendered separately, relying on compositing techniques for the anti-aliased accumulation of the full image. this paper presents the case for four-channel pictures, demonstrating that a matte component can be computed similarly to the color channels. the paper discusses guidelines for the generation of elements and the arithmetic for their arbitrary compositing.  thomas porter tom duff
interactive three-dimensional holographic displays: seeing the future in depth computer graphics is confined chiefly to flat images. images may look three- dimensional (3d), and sometimes create the illusion of 3d when displayed, for example, on a stereoscopic display [16, 13, 12]. nevertheless, when viewing an image on most display systems, the human visual system (hvs) sees a flat plane of pixels. volumetric displays can create a 3d computer graphics image, but fail to provide many visual depth cues (e.g. shading texture gradients) and cannot provide the powerful depth cue of overlap (occlusion). discrete parallax displays (such as lenticular displays) promise to create 3d images with all of the depth cues, but are limited by achievable resolution. only a real-time electronic holographic ("holovideo") display [11, 6, 8, 7, 9, 21, 22, 20, 2] can create a truly 3d computer graphics image with all of the depth cues (motion parallax, ocular accommodation, occlusion, etc.) and resolution sufficient to provide extreme realism [13]. holovideo displays promise to enhance numerous applications in the creation and manipulation of information, including telepresence, education, medical imaging, interactive design and scientific visualization.the technology of electronic interactive three- dimensional holographic displays is in its first decade. though fancied in popular science fiction, only recently have researchers created the first real holovideo systems by confronting the two basic requirements of electronic holography: computational speed and high-bandwidth modulation of visible light. this article describes the approaches used to address these problems, as well as emerging technologies and techniques that provide firm footing for the development of practical holovideo. mark lucente
color image quantization by minimizing the maximum intercluster distance  one of the numerical criteria for color image quantization is to minimize the maximum discrepancy between original pixel colors and the corresponding quantized colors. this is typically carried out by first grouping color points into tight clusters and then finding a representative for each cluster. in this article we show that getting the smallest clusters under a formal notion of minimizing the maximum intercluster distance does not guarantee an optimal solution for the quantization criterion. nevertheless our use of an efficient clustering algorithm by teofilo f. gonzalez, which is optimal with respect to the approximation bound of the clustering problem, has resulted in a fast and effective quantizer. this new quantizer is highly competitive and excels when quantization errors need to be well capped and when the performance of other quantizers may be hindered by such factors as low number of quantized colors or unfavorable pixel population distribution. both computer-synthesized and photographic images are used in experimental comparison with several existing quantization methods.  zhigang xiang
a user interface management system  the design and construction of the user interface to interactive systems is receiving increased attention. this paper describes a user interface management system that allows a designer/developer to focus on the logical functionality of an application without the usual bookkeeping associated with a conventional programming language. the user interface management system contains two components: a special purpose, application independent dialogue specification language and a run-time interpreter that provides a number of interaction extensions not possible with procedure libraries.  david j. kasik
rasterizing curves of constant width  this paper gives a fast, linear- time algorithm for generating high-quality pixel representations of curved lines. the results are similar to what is achieved by selecting a circle whose diameter is the desired line width, and turning on all pixels covered by the circle as it moves along the desired curve. however, the circle is replaced by a carefully chosen polygon whose deviations from the circle represent subpixel corrections designed to improve the aesthetic qualities of the rasterized curve. for nonsquare pixels, equally good results are obtained when an ellipse is used in place of the circle. the class of polygons involved is introduced, an algorithm for generating them is given, and how to construct the set of pixels covered when such a polygon moves along a curve is shown. the results are analyzed in terms of a mathematical model for the uniformity and accuracy of line width in the rasterized image.  john d. hobby
provably correct theories of action  we investigate logical formalization of the effects of actions in the situation calculus. we propose a formal criterion against which to evaluate theories of deterministic actions. we show how the criterion provides us a formal foundation upon which to tackle the frame problem, as well as its variant in the context of concurrent actions. our main technical contributions are in formulating a wide class of monotonic causal theories that satisfy the criterion, and showing that each such theory can be reformulated succinctly in circumscription.  fangzhen lin yoav shoham
chess on a hypercube  we report our progress on computer chess last described at the second conference on hypercubes. our program follows the strategy of currently successful sequential chess programs: searching of an alpha-beta pruned game tree, iterative deepening, transposition and history tables, specialized endgame evaluators, and so on. the search tree is decomposed onto the hypercube (an ncube) using a recursive version of the principal-variation- splitting algorithm. roughly speaking, subtrees are searched by teams of processors in a self-scheduled manner.  a crucial feature of the program is the global hashtable. hashtables are important in the sequential case, but are even more central for a parallel chess algorithm. the table not only stores knowledge but also makes the decision at each node of the chess tree whether to stay sequential or to split up the work in parallel. in the language of knuth and moore, the transposition table decides whether each node of the chess tree is a type 2 or a type 3 node and acts accordingly. for this data structure the hypercube is used as a shared-memory machine. multiple writes to the same location are resolved using a priority system which decides which entry is of more value to the program. the hashtable is implemented as "smart" shared memory.  search times for related subtrees vary widely (up to a factor of 100) so dynamic reconfiguration of processors is necessary to concentrate on such "hot spots" in the tree. a first version of the program with dynamic load balancing has recently been completed and out-performs the non-load-balancing program by a factor of three. the current speedup of the program is 101 out of a possible 256 processors.  the program has played in several tournaments, facing both computers and people. most recently it scored 2-2 in the acm north american computer chess championship.  e. w. felten s. w. otto
towards a standard upper ontology the suggested upper merged ontology (sumo) is an upper levelontology that has been proposed as a starter document for thestandard upper ontology working group, an ieee-sanctioned workinggroup of collaborators from the fields of engineering, philosophy,and information science. the sumo provides definitions forgeneral-purpose terms and acts as a foundation for more specificdomain ontologies. in this paper we outline the strategy used tocreate the current version of the sumo, discuss some of thechallenges that we faced in constructing the ontology, and describein detail its most general concepts and the relations between them. ian niles adam pease
decomposable negation normal form knowledge compilation has been emerging recently as a new direction of research for dealing with the computational intractability of general propositional reasoning. according to this approach, the reasoning process is split into two phases: an off-line compilation phase and an on-line query-answering phase. in the off-line phase, the propositional theory is compiled into some target language, which is typically a tractable one. in the on-line phase, the compiled target is used to efficiently answer a (potentially) exponential number of queries. the main motivation behind knowledge compilation is to push as much of the computational overhead as possible into the off-line phase, in order to amortize that overhead over all on-line queries. another motivation behind compilation is to produce very simple on-line reasoning systems, which can be embedded cost-effectively into primitive computational platforms, such as those found in consumer electronics.one of the key aspects of any compilation approach is the target language into which the propositional theory is compiled. previous target languages included horn theories, prime implicates/implicants and ordered binary decision diagrams (obdds). we propose in this paper a new target compilation language, known as decomposable negation normal form (dnnf), and present a number of its properties that make it of interest to the broad community. specifically, we show that dnnf is universal; supports a rich set of polynomial--time logical operations; is more space-efficient than obdds; and is very simple as far as its structure and algorithms are concerned. moreover, we present an algorithm for converting any propositional theory in clausal form into a dnnf and show that if the clausal form has a bounded treewidth, then its dnnf compilation has a linear size and can be computed in linear time (treewidth is a graph-theoretic parameter that measures the connectivity of the clausal form). we also propose two techniques for approximating the dnnf compilation of a theory when the size of such compilation is too large to be practical. one of the techniques generates a sound but incomplete compilation, while the other generates a complete but unsound compilation. together, these approximations bound the exact compilation from below and above in terms of their ability to answer clausal entailment queries. finally, we show that the class of polynomial--time dnnf operations is rich enough to support relatively complex ai applications, by proposing a specific framework for compiling model-based diagnosis systems. adnan darwiche
hierarchical agent control: a framework for defining agent behavior  the hierarchical agent control architecture (hac) is a general toolkit for specifying an agent's behavior. hac supports action abstraction, resource management, sensor integration, and is well suited to controlling large numbers of agents in dynamic environments. it relies on three hierarchies: action, sensor, and context. the action hierarchy controls the agent's behavior. it is organized around tasks to be accomplished, not the agents themselves. this facilitates the integration of multi-agent actions and planning into the architecture. the sensor hierarchy provides a principled means for structuring the complexity of reading and transforming sensor information. each level of the hierarchy integrates the data coming in from the environment into conceptual chunks appropriate for use by actions at this level. actions and sensors are written using the same formalism. the context hierarchy is a hierarchy of goals. in addition to their primary goals, most actions are operating within a set of implicit assumptions. these assumptions are made explicit through the context hierarchy. we have developed a planner, grasp, implemented within hac, which is capable of resolving multiple goals in real time.  hac was intended to have wide applicability. it has been used to control agents in commercial computer games and physical robots. our primary application domain is a simulator of land-based military engagements called "capture the flag." hac's simulation substrate models physics at an abstract level. hac supports any domain in which behaviors can be reduced to a small set of primitive effectors such as {\sc move} and {\sc apply-force}. at this time defining agent behavior requires lisp programming skills; we are moving towards more graphical programming languages.  marc s. atkin gary w. king david l. westbrook brent heeringa paul r. cohen
frame-to-frame coherence and the hidden surface computation: constraints for a convex world  frame-to-frame coherence is the highly structured relationship that exists between successive frames of certain animation sequences. from the point of view of the hidden surface computation, this implies that parts of the scene will become visible or invisible in a predictable fashion. in this paper the frame-to-frame coherence constraints are identified and characterized for static scenes restricted to stationary, closed, convex, nonintersecting polyhedra. the animation derives from a continuous movement of the viewer. the mathematical analysis of the constraints is geometric, and leads to a characterization of the self- occlusion relationship over a single polyhedron; and to a characterization of the occlusion or change of occlusion relationship over two polyhedra. based on these constraints, an algorithm is presented which generates successive frames in an animation sequence.  harold hubschman steven w. zucker
the software process and software environments (panel session)  this panel discussion springs from a three-day workshop on the software process and software environments that was held in march 1985. our intention is to convey some of what was discussed at that workshop and to precipitate discussion of some of the issues that arose during the workshop deliberations. in this paper we briefly summarize the workshop, then list some of the issues that might become foci of the panel discussion.  jack c. wileden mark dowson
watertight tessellation using forward differencing  in this paper we describe an algorithm and hardware for the tessellation of polynomial surfaces. while conventional forward difference-based tessellation is subject to round off error and cracking, our algorithm produces a bit-for- bit consistent triangle mesh across multiple independently tessellated patches. we present tessellation patterns that exploit the efficiency of iterative evaluation techniques while delivering a defect free adaptive tessellation with continuous level-of-detail. we also report the rendering performance of the resulting physical hardware implementation.  henry moreton
error-bounded antialiased rendering of complex environments  in previous work, we presented an algorithm to accelerate z-buffer rendering of enormously complex scenes. here, we extend the approach to antialiased rendering with an algorithm that guarantees that each pixel of the output image is within a user-specified error tolerance of the filtered underlying continuous image. as before, we use an object-space octree to cull hidden geometry rapidly. however, instead of using an image-space depth pyramid to test visibility of collections of pixel samples, we use a quadtree data structure to test visibility throughout image-space regions. when regions are too complex, we use quadtree subdivision to simplify the geometry as in warnock's algorithm. subdivison stops when the algorithm can either analytically filter the required region or bound the convolution integral appropriately with interval methods. to the best of our knowledge, this is the first algorithm to antialias with guaranteed accuracy scenes consisting of hundreds of millions of polygons.  ned greene michael kass