waashk/acm huggingface dataset:
line drawings of octree-represented objects  the octree structure represents the space occupied by an object as a juxtaposition of cubes, where the sizes and position coordinates of the cubes are integer powers of 2 and are defined by a recursive decomposition of three- dimensional space. this makes the octree structure highly sensitive to object location and orientation, and the three-dimensional shape of the represented object obscure. it is helpful to be able to see the actual object represented by an octree, especially for visual performance evaluation of octree algorithms. presented in this paper is a display algorithm that helps visualize the three- dimensional space represented by the octree. given an octree, the algorithm produces a line drawing of the objects represented by the octree, using parallel projection, from any specified viewpoint with hidden lines removed. the order in which the algorithm traverses the octree has the property that if node x occludes node y, then node x is visited before node y. the algorithm produces a set of long, straight visible edge segments corresponding to the visible surface of the polyhedral object represented by the octree. examples of some line drawing produced by the algorithm are given. the complexity of the algorithm is also discussed.  jack veenstra narendra ahuja
parallel proximity detection and the distribution list algorithm  generalized proximity detection for moving objects in a logically correct parallel discrete-event simulation is an interesting and fundamentally challenging problem. determining who can see whom in a manner that is fully scalable in terms of cpu usage, number of messages, and memory requirements is highly non-trivial.  a new scalable approach has been developed to solve this problem. this algorithm, called the distribution list, has been designed and tested using the object-oriented synchronous parallel environment for emulation and discrete-event simulation (speedes) operating system. preliminary results show that the distribution list algorithm achieves excellent parallel performance.  jeff s. steinman frederick wieland
compatability and interaction style in computer graphics recent trends in human computer interaction have focused on representations based on physical reality [4, 5, 6, 8]. the idea is to provide richer, more intuitive handles for control and manipulation compared to traditional graphical user interfaces (guis) using a mouse. this trend underscores the need to examine the concept of manipulation and to further understand what we _want_ to manipulate versus what we _can_ easily manipulate. implicit in this is the notion that the bias of the ui is often incompatible with user needs.the main goal of ui design is to reduce complexity while augmenting the ability of users to get their work done. a fundamental belief underlying our research is that complexity lies not only in what is purchased from the software and hardware manufacturers, but also in what the user creates with it. it is not just a question of making buttons and menus easier to learn and more efficient to use. it is also a question of "given that i've created this surface in this way, how can it now be modified to achieve my current design objective?" (the observation is that how the user created the surface in the first place will affect the answer to the question.) our thesis is that appropriate design of the system can minimize both kinds of complexity: that inherent in accessing the functionality provided by the vendor, _and_ that created by the user. the literature focuses on the former. in what follows, we investigate some of the issues in achieving the latter. in so doing, we structure our discussion around questions of _compatibility._ george w. fitzmaurice bill buxton
induction of models under uncertainty  this paper outlines a procedure for performing induction under uncertainty. this procedure uses a probabilitic representation and uses bayes' theorem to decide between alternative hypotheses (theories). this procedure is illustrated by a robot with no prior world experience performing induction on data it has gathered about the world. the particular inductive problem is the formation class descriptions both for the tutored and untutored cases. the resulting class definitions are inherenty probabilistic and so do not have any sharply defined membership criterion. this robot example raises some fundamental problems about induction--- particularly it is shown that inductively formed theories are not the best way of making predictions. another difficulty is the need to provide prior probabilities for the set of possible theories. the main criterion for such priors is a proagmatic one aimed at keeping the theory structure as simple as possible, while still reflecting any structure discovered in the data.  p cheeseman
constraint-based termination analysis of logic programs  current norm- based automatic termination analysis techniques for logic programs can be split up into different components: inference of mode or type information, derivation of models, generation of well-founded orders, and verification of the termination conditions themselves. although providing high-precision results, these techniques suffer from an efficiency point of view, as several of these analyses are often performed through abstract interpretation. we present a new termination analysis which integrates the various components and produces a set of constraints that, when solvable, identifies successful termination proofs. the proposed method is both efficient and precise. the use of constraint sets enables the propagation on information over all different phases while the need for multiple analyses is considerably reduced.  stefaan decorte danny de schreye henk vandecasteele
quasi-linear depth buffers with variable resolution  in this paper we present new class of variable-resolution depth buffers, providing a flexible trade-off between depth precision in the distant areas of the view volume and performance. these depth buffers can be implemented using linear or quasi- linear mapping function of the distance to the camera to the depth in the screen space. in particular, the complementary z buffer algorithm combines simplicity of implementation with significant bandwidth savings.  a variable-resolution depth buffer saves bandwidth by changing size of the per-pixel depth access from 24 bits to 16 bits when distance to the pixel from the camera becomes larger than a given threshold. this distance is selected in order to keep the resulting resolution equal or larger than the resolution of the 24-bit screen z buffer. for dynamic ratios of the distances between far and near planes 500 and above, bandwidth savings may exceed 20%.  quasi-linear depth floating-point depth buffers are best at high dynamic ratios; 3d hardware should support per-frame setting of the optimal depth buffer type and format. per-frame adjustment of the resolution switch distance allows balancing performance with depth precision and should be exposed in the graphics api.  eugene lapidous guofang jiao jianbo zhang timothy wilson
checking regulation consistency by using sol-resolution  this paper addresses the problem of regulation consistency checking. regulations are sets of rules which express what is obligatory, permitted, forbidden and under which conditions. we first define a first order language to model regulations. then we introduce a definition of regulation consistency. we show that checking the consistency of a regulation comes to generate some particular consequences of some first order formulas. then, we show that we can apply inoue's inference rule, sol-resolution, which is complete for generating, from some clauses, their consequences which satisfy a given condition.  laurence cholvy
jagged edges: when is filtering needed?  depiction of oblique edges by discrete pixels usually results in visible stair steps, often called jaggies. a variety of filtering approaches exists to minimize this visual artifact, but none has been applied selectively only to those edges that would otherwise appear jagged. a recent series of experiments has led to a model of the visibility of jagged edges. here, we demonstrate how these data can be used efficiently to determine when filtering of edges is needed to eliminate the jaggies and when it is unnecessary. this work also provides a template for how the results of psychophysical experiments can be applied in computer graphics to address image-quality questions.  avi c. naiman
text processing - where do we go from here?  most universities have sort of "backed into" the word-processing/text- processing business. as large computers become more sophisticated and small word- processing micros become more readily affordable, large numbers of students, faculty, and staff have discovered the joys of online text editing and formatting and have demanded access to these types of systems. this can, and at times does, lead to uncontrolled growth and even pandemonium as users vie for time on the terminals and machines and demand specialized assistance from user services personnel. since there was no "master plan," the process of inputting, editing, formatting, previewing, and outputting text is currently done very much piecemeal using whatever hardware and software is available at the time. this worked fine with the small numbers of knowledgeable users who first got interested in computerized text processing as an outgrowth of their other computer-related activities. however, with more and more "lay" users appearing every day with new text- processing applications there has developed a real need to organize and give a direction to this previously uncontrolled field.  this paper will discuss what is being done at clemson university to provide these controls and will touch on the concept of a fully integrated text processing system, which is the topic of a white paper recently started by the document composition project of ibm's share user group.  sandra piazza
energy preserving non-linear filters  monte carlo techniques for image synthesis are simple and powerful, but they are prone to noise from inadequate sampling. this paper describes a class of non-linear filters that remove sampling noise in synthetic images without removing salient features. this is achieved by spreading real input sample values into the output image via variable-width filter kernels, rather than gathering samples into each output pixel via a constant-width kernel. the technique is nonlinear because kernel widths are based on sample magnitudes, and this local redistribution of values cannot generally be mapped to a linear function. nevertheless, the technique preserves energy because the kernels are normalized, and all input samples have the same average influence on the output. to demonstrate its effectiveness, the new filtering method is applied to two rendering techniques. the first is a monte carlo path tracing technique with the conflicting goals of keeping pixel variance below a specified limit and finishing in a finite amount of time; this application shows how the filter may be used to "clean up" areas where it is not practical to sample adequately. the second is a hybrid deterministic and monte carlo ray-tracing program; this application shows how the filter can be effective even when the pixel variance is not known.  holly e. rushmeier gregory j. ward
pic - a language for typesetting graphics  pic is a language for specifying pictures so that they can be typeset as an integral part of a document preparation system.  the basic objects in pic are boxes, lines, arrows, circles, ellipses, arcs and splines, which may be placed anywhere and labeled with arbitrary text. most of the effort in designing pic has gone into making it possible to specify the sizes and positions of objects with minimal use of absolute coordinates.  this paper describes pic, with primary emphasis on those aspects of the language that make it easy to use.  brian w. kernighan
gap - a gpss/fortran package  the gap package has been developed to permit the linking of standard gpss models to a series of fortran subprograms. since the gap subprograms are transparent to the user, knowledge of the fortran language is not needed. gap provides an easy mechanism to obtain, among other things, values from a number of standard statistical distributions, permits the loading of msavevalues and other snas using data cards and provides statistical analysis of the gpss model output.  robert j. wimmert
creating polyhedral stellations  a process for creating and displaying stellations of a given polyhedral solid is described. a stellation is one of many star-like polyhedra which can be derived from a single solid by extending its existing faces. a program has been implemented which performs the stellation process on an input object and generates a 3-dimensional image of the stellated object on a computer graphics display screen. pictures of icosahedron and rhombictriacontahedron stellations generated by the program are included in the paper.  kathleen r. mckeown norman i. badler
cooperative acceleration: robust conservative distributed discrete event simulation  robustness of the simulation mechanism is a requirement for acceptability of distributed simulation environments. we consider complex and erratic distributed conservative simulations, using colliding pucks as a guiding example. a new mechanism is introduced which allows logical processes to cooperate locally and advance. advance is made through the collective selection of the next event in a group of logical processes. the algorithm demonstrates scalability through the locality of its determination. a description and proof of correctness is given. the effectiveness of the cooperative acceleration mechanism is illustrated with measurements on road traffic and colliding pucks simulations.  t. d. blanchard t. w. lake s. j. turner
unstructured lumigraph rendering  we describe an image based rendering approach that generalizes many current image based rendering algorithms, including light field rendering and view- dependent texture mapping. in particular, it allows for lumigraph-style rendering from a set of input cameras in arbitrary configurations (i.e., not restricted to a plane or to any specific manifold). in the case of regular and planar input camera positions, our algorithm reduces to a typical lumigraph approach. when presented with fewer cameras and good approximate geometry, our algorithm behaves like view- dependent texture mapping. the algorithm achieves this flexibility because it is designed to meet a set of specific goals that we describe. we demonstrate this flexibility with a variety of examples.  chris buehler michael bosse leonard mcmillan steven gortler michael cohen
direct ascent, deep space intercept model  a stochastic computer model was developed to analyze a direct ascent, deep space intercept system. there are two error sources within the system: the deep space tracking system and the launch vehicle guidance system. the errors are modeled based on equipment performance data and analytical results. to compensate for the system errors, the requirements for a maneuverable intercept vehicle are developed. the requirements are described in terms of sensor acquisition distance and vehicle velocity change. analyses of error sources and tradeoffs amongst maneuver factors are discussed.  mark m. mekaru richard c. barclay
modelling styles and their support in the casm environment  much effort is currently being expended in the design and implementation of integrated software support environments for discrete event simulation modelling. what are the considerations underlying the development of such environments and how are efforts being directed? this paper discusses aspects of the background to current developments and relates this discussion to the context of one such environment namely that of the computer aided simulation modelling (casm) group at the london school of economics.  david w. balmer
a fast, low-space algorithm for multiplying dense multivariate polynomials  this paper presents an improved adaptive hybrid algorithm for multiplying dense multivariate polynomials that is both time and space efficient. the hybrid algorithm makes use of two families of univariate algorithms, one karatsuba based and the other dft based, which are applied recursively to solve the multivariate problem. the hybrid algorithm is adaptive in that particular univariate algorithms are selected at run time to minimize the time complexity; an order-of-magnitude speedup with respect to classical multiplication is achieved over the entire practical range except for very small problems. empirical investigation shows that most of the theoretical superiority is maintained in actual implementation. the largest contribution to the space requirements of the total algorithm is determined by the univariate algorithm used for the outermost variable; except for quite small problems, selecting univariate algorithms to minimize run time almost always leads to situations where the space requirements of the total algorithm are extremely close to the space required merely to store the result.  vangalur s. alagar david k. probst
a development methodology applied to a radar system simulation  as systems to be simulated grow larger and more complex and the cost of software escalates the need for cost and time efficient development methodologies become critical. this paper describes such a methodology. the methodology is based on standard modern software practices such as top-down design and structured programming. this development methodology has been applied to a radar system simulation which will eventually grow into an air defense simulation employing a surveillance net, and deployed weapons. the objective of the simulation is to provide a computer design tool to aid in the synthesis and parameterization of modern air defense systems.  the simulation embodies computational algorithms as well as the contentions for resources among the various elements of the system.  the radar system simulation is implemented in the simscript simulation program language. it is documented in the software design and documentation language (sddl) which is a machine processed and machine reproducible pseudo code.  jane harmon jay landreth donald lausch padman nagenthiram henry ramirez
evaluation of a metric inventory system using simulation  traditional measures obtained from the application of theoretical inventory models do not provide detailed information on the ability of multi-echelon, reparable item inventory systems to maintain their supported machines in an operational status. monte carlo simulation techniques are applied to obtain estimates of the operational status actually attained. an advantage of the simulation techniques is that they do not require all the strict assumptions of the theoretical models. the slam simulation language developed by pritsker and pegden is used for this analysis.  james r. coakley charles g. carpenter
a network interface unit simulation using micro passim  this paper describes how micro passim, a gpss based simulation system, was transported from the apple ii to the hp 9836. the problems associated with moving a large program form one ucsd pascal system to another are discussed. micro passim was transported to the hp system so that an ethernet to hpib interface board could be modeled. the model is described and the results obtained from the simulation are discussed. a discussion of the advantages and disadvantages of using micro passim rather than a standard language, such as gpss, is also included.  tom p. vayda larry l. wear
efficient identification of important factors in large scale simulations  large, complex computer simulation models can require prohibitively costly and time-consuming experimental programs to study their behavior. therefore we may want to concentrate the analysis on the set of "most important" factors (i.e., input variables). factor screening experiments, which attempt to identify the more important variables, can be extremely useful in the study of such models. the number of computer runs available for screening, however, is usually severely limited. in fact, the number of factors often exceeds the number of available runs. in this paper we present a survey of supersaturated designs for use in factor screening experiments. the designs considered are: random balance, systematic supersaturated, group screening, modified group screening, t-optimal, r-optimal, and search designs. we discuss in general terms the basic technique, advantages, and disadvantages of each procedure surveyed.  carl a. mauro
comparison of simulation results of dissimilar models  analytical and simulation models for the same idealised but realistic computer system are considered. the results for cpu utilisation and cpu queue length from the models compare very favourably, suggesting that the technique could be used to confirm the accuracy of a simulation model. increasingly dissimilar models are also systematically investigated. it is found that the degree of dissimilarity of the models can be surprisingly large before the method of comparison can be considered as having broken down.  c lazos
special purpose automatic programming for hidden surface elimination  in many applications of three dimensional computer graphics, the appearance of the same scene must be computed repeatedly for many different positions of the viewer. this paper concerns a scheme for exploiting this property of an application for the purpose of improving the efficiency of the hidden surface computation. the scheme involves a kind of automatic programming: for each scene to be considered, a different special purpose program is automatically constructed. the special purpose program then takes the position of the viewer as input, and generates a suitable description of the scene with hidden surfaces removed as output. since the special purpose program has a very limited task to perform - it is adapted to handling just one scene - it can be much faster than any general purpose algorithm would be for the same scene. the paper describes a method by which special purpose programs for hidden surface elimination can be constructed in a fully automatic manner. the method has been implemented, and results of experiments are given.  chris goad
simplifying the modeling of multiple activities, multiple queuing, and interruptions: a new low-level data structure  most conventional discrete-event simulation software assumes a simple progression of entities through queues and activities. such software cannot cope easily with modeling systems where entities can be present in more than one queue, can be involved in more than one activity (i.e., scheduled for more than one event), or can be interrupted while queuing or taking part in an activity in order to join another queue or take part in a different activity. low-level data structures to address these problems have been implemented in pascal by extending an existing suite of pascal procedures, call pascal_sim. the problems and their solutions are discussed in the context of machine breakdown in a production system. comparisons between the use of the new structures and the existing ones showed some gain in computational efficiency and considerable improvement in ease of modeling. the generality of the data structure is considered.  ruth m. davies robert m. o'keefe huw t. o. davies