waashk/acm huggingface dataset:
scanning physical interaction behavior of 3d objects  we describe a system for constructing computer models of several aspects of physical interaction behavior, by scanning the response of real objects. the behaviors we can successfully scan and model include deformation response, contact textures for interaction with force-feedback, and contact sounds. the system we describe uses a highly automated robotic facility that can scan behavior models of whole objects. we provide a comprehensive view of the modeling process, including selection of model structure, measurement, estimation, and rendering at interactive rates. the results are demonstrated with two examples: a soft stuffed toy which has significant deformation behavior, and a hard clay pot which has significant contact textures and sounds. the results described here make it possible to quickly construct physical interaction models of objects for applications in games, animation, and e-commerce.
algorithmic aspects in speech recognition: an introduction  speech recognition is an area with a considerable literature, but there is little discussion of the topic within the computer science algorithms literature. many computer scientists, however, are interested in the computational problems of speech recognition. this paper presents the field of speech recognition and describes some of its major open problems from an algorithmic viewpoint. our goal is to stimulate the interest of algorithm designers and experimenters to investigate the algorithmic problems of effective automatic speech recognition.  adam l. buchsbaum raffaele giancarlo
fast computation of shadow boundaries using spatial coherence and backprojections  this paper describes a fast, practical algorithm to compute the shadow boundaries in a polyhedral scene illuminated by a polygonal light source. the shadow boundaries divide the faces of the scene into regions such that the structure or "aspect" of the visible area of the light source is constant within each region. the paper also describes a fast, practical algorithm to compute the structure of the visible light source in each region. both algorithms exploit spatial coherence and are the most efficient yet developed.  given the structure of the visible light source in a region, queries of the form "what specific areas of the light source are visible?" can be answered almost instantly from any point in the region. this speeds up by several orders of magnitude the accurate computation of first level diffuse reflections due to an area light source. furthermore, the shadow boundaries form a good initial decomposition of the scene for global illumination computations.  a. james stewart sherif ghali
elastic time  we introduce a new class of synchronization protocols for parallel discrete event simulation, those based on near- perfect state information (npsi). npsi protocols are adaptive dynamically controlling the rate at which processes constituting a parallel simulation proceed with the goal of completing a simulation efficiently. we show by analysis that a class of adaptive protocols (that includes npsi and several others) can both arbitrarily outperform and be arbitrarily outperformed by the time warp synchronization protocol. this mixed result both substantiates the promising results we and other adaptive protocol designers have observed, and cautions those who might assume that any adaptive protocol will always be better than any nonadaptive one. we establish in an experimental study that a particular npsi protocol, the elastic time algorithm, outperforms time warp, both temporally and spatially on every workload tested. although significant options remain with respect to the design of eta, the work presented here establishes the class of npsi protocols as a very promising approach.  sudhir srinivasan paul f. reynolds
visibility-ordering meshed polyhedra  a visibility-ordering of a set of objects from some viewpoint is an ordering such that if object a obstructs object b, then b precedes a in the ordering. an algorithm is presented that generates a visibility-ordering of an acyclic convex set of meshed convex polyhedra. this algorithm takes time linear in the size of the mesh. modifications to this algorithm and/or preprocessing techniques are described that permit nonconvex cells nonconvex meshes (meshes with cavities and/or voids), meshes with cycles, and sets of disconnected meshes to be ordered. visibility-ordering of polyhedra is applicable to scientific visualization, particularly direct volume rendering. it is shown how the ordering algorithms can be used for domain decomposition of finite element meshes for parallel processing, and how the data structures used by these algorithms can be used to solve the spatial point location problem. the effects of cyclically obstructing polyhedra are discussed and methods for their elimination are described, including the use of the delaunay triangulation. methods for converting nonconvex meshes into convex meshes are described.  peter l. williams
dynamic arguments in a case law domain  in this paper we describe an approach to reasoning with cases which takes into account the view that case law evolves through a _series_ of decisions. this is in contrast to approaches which take as a starting point a set of decided cases, with no account taken of the order in which they were decided. the model of legal reasoning we follow is based on levi's account which shows how decided cases often need to be reinterpreted in the light of subsequent decisions, so that features of cases wax and wane in importance. our aim is to reproduce the arguments that could have been used in a given case, rather than to apply a retrospective understanding of the law to them. a second novel feature is that we use a general purpose ontology to describe the cases, rather than one developed specifically to model the pertinent cases. the paper describes a prototype implementation, and uses an example to illustrate how our approach works. after this case by case description we make some remarks on the insights gained, and draw some conclusions.  john henderson trevor bench-capon
curve-drawing algorithms for raster displays  the midpoint method for deriving efficient scan- conversion algorithms to draw geometric curves on raster displays in described. the method is general and is used to transform the nonparametric equation f(x,y) = 0, which describes the curve, into an algorithms that draws the curve. floating point arithmetic and time- consuming operations such as multiplies are avoided. the maximum error of the digital approximation produced by the algorithm is one-half the distance between two adjacent pixels on the display grid. the midpoint method is compared with the two-point method used by bresenham, and is seen to be more accurate (in terms of the linear error) in the general case, without increasing the amount of computation required. the use of the midpoint method is illustrated with examples of lines, circles, and ellipses. the considerzations involved in using the method to derive algorithms for drawing more general classes of curves are discussed.  jerry van aken mark novak
domain knowledge and the design process  during the past 10 or 12 years, artificial intelligence researchers have explored techniques for bringing large amounts of domain knowledge to bear in solving ill-structured problems. several programs that make use of these knowledge-based techniques are currently being developed to assist in various design tasks. this paper introduces one technique---rule-based programming--- and illustrates its use with two programs, r1 and xsel, which are used by digital equipment corporation in the design of computer system configurations.  john mcdermott
r-buffer: a pointerless a-buffer hardware architecture  we present a graphics hardware architecture that implements carpenter's a-buffer. the a-buffer is a software renderer that uses pointer based linked lists. our pointerless approach computes order independent transparency for any number of layers with minimal hardware complexity. statistics are shown for a variety of different scenes using a trace based methodology, with an instrumented mesa opengl implementation. the architecture is shown to require from 2.1 to 3.6 times more memory than traditional z-buffering. a detailed hardware design is provided. order independent transparency is computed without application sorting and without artifacts. the architecture can also be used for antialiasing, and an example of carpenter's classical a-buffer antialiasing is shown.  craig m. wittenbrink
cyc: toward programs with common sense  cyc is a bold attempt to assemble a massive knowledge base (on the order of 108 axioms) spanning human consensus knowledge. this article examines the need for such an undertaking and reviews the authos' efforts over the past five years to begin its construction. the methodology and history of the project are briefly discussed, followed by a more developed treatment of the current state of the representation language used (epistemological level), techniques for efficient inferencing and default reasoning (heuristic level), and the content and organization of the knowledge base.  douglas b. lenat r. v. guha karen pittman dexter pratt mary shepherd
new quadric metric for simplifiying meshes with appearance attributes  complex triangle meshes arise naturally in many areas of computer graphics and visualization. previous work has shown that a quadric error metric allows fast and accurate geometric simplification of meshes. this quadric approach was recently generalized to handle meshes with appearance attributes. in this paper we present an improved quadric error metric for simplifying meshes with attributes. the new metric, based on geometric correspondence in 3d, requires less storage, evaluates more quickly, and results in more accurate simplified meshes.  meshes often have attribute discontinuities, such as surface creases and material boundaries, which require multiple attribute vectors per vertex. we show that a wedge-based mesh data structure captures such discontinuities efficiently and permits simultaneous optimization of these multiple attribute vectors. in addition to the new quadric metric, we experiment with two techniques proposed in geometric simplification, memoryless simplification and volume preservation, and show that both of these are beneficial within the quadric framework. the new scheme is demonstrated on a variety of meshes with colors and normals.  hugues hoppe
issue spotting in a system for searching interpretation spaces  a method for spotting issues is described which uses a system we are developing for searching interpretations spaces and constructing legal arguments. the system is compatible with the legal philosophy known as legal positivism, but does not depend on its notion of clear cases. ai methods applied in the system include an atms reason maintenance system, poole's framework for default reasoning, and an interactive natural deduction theorem prover with a programmable control component for including domain-dependent heuristic knowledge. our issue spotting method is compared with gardner's program for identifying the hard and easy issues raised by offer and acceptance law school examination questions.  t. f. gordon
expressive expression mapping with ratio images  facial expressions exhibit not only facial feature motions, but also subtle changes in illumination and appearance (e.g., facial creases and wrinkles). these details are important visual cues, but they are difficult to synthesize. traditional expression mapping techniques consider feature motions while the details in illumination changes are ignored. in this paper, we present a novel technique for facial expression mapping. we capture the illumination change of one person's expression in what we call an _expression ratio image_ (eri). together with geometric warping, we map an eri to any other person's face image to generate more expressive facial expressions.  zicheng liu ying shan zhengyou zhang
a signal-processing framework for inverse rendering  realism in computer-generated images requires accurate input models for lighting, textures and brdfs. one of the best ways of obtaining high-quality data is through measurements of scene attributes from real photographs by _inverse rendering_. however, inverse rendering methods have been largely limited to settings with highly controlled lighting. one of the reasons for this is the lack of a coherent mathematical framework for inverse rendering under general illumination conditions. our main contribution is the introduction of a signal-processing framework which describes the reflected light field as a convolution of the lighting and brdf, and expresses it mathematically as a product of spherical harmonic coefficients of the brdf and the lighting. inverse rendering can then be viewed as deconvolution. we apply this theory to a variety of problems in inverse rendering, explaining a number of previous empirical results. we will show why certain problems are ill-posed or numerically ill-conditioned, and why other problems are more amenable to solution. the theory developed here also leads to new practical representations and algorithms. for instance, we present a method to _factor_ the lighting and brdf from a small number of views, i.e. to estimate both simultaneously when neither is known.
accessible animation and customizable graphics via simplicial configuration modeling  o ur goal is to em bed free-form constraints into a graphical m odel. w ith such constraints a graphic can m aintain its visual integrity--- and break rules tastefully--- while being m anipulated by a casualuser. a typicalparam eterized graphic does notm eet these needs because its configuration space contains nonsense im ages in m uch higher proportion than desirable im ages, and the casual user is apt to ruin the graphic on any attem pt to m odify oranim ate it.  w e therefore m odel the sm all subset of a given graphic's configuration space that m aps to desirable im ages. in our solution, the basic building block is a sim plicial complex--- the m ost practical data structure able to accom m odate the variety of topologies that can arise. the configuration- space m odel can be built from a cross productofsuch com plexes. w e describe how to define the m apping from this space to the im age space. w e show how to invert that m apping, allow ing the user to m anipulate the im age without understanding the structure of the configuration-space m odel. w e also show how to extend the m apping when the originalparam eterization contains hierarchy, coordinate transform ations,and other non linearities.  o ur software im plem entation applies sim plicial configuration m odeling to 2d vector graphics.  tom ngo doug cutrell jenny dana bruce donald lorie loeb shunhui zhu
parallel thinning with two-subiteration algorithms  two parallel thinning algorithms are presented and evaluated in this article. the two algorithms use two-subiteration approaches: (1) alternatively deleting north and east and then south and west boundary pixels and (2) alternately applying a thinning operator to one of two subfields. image connectivities are proven to be preserved and the algorithms' speed and medial curve thinness are compared to other two-subiteration approaches and a fully parallel approach. both approaches produce very thin medial curves and the second achieves the fastest overall parallel thinning.  zicheng guo richard w. hall
incremental execution of guarded theories  when it comes to building controllers for robots or agents, high level programming languages like golog and congolog offer a useful compromise between planning-based approaches and low-level robot programming. however, two serious problems typically emerge in practical implementations of these languages: how to evaluate test in a program efficiently enough in an open- world setting, and how to make appropiate nondeterministic choices while avoiding full lookahead. recent proposals in the literature suggest that one could tackle the first problem by exploiting sensing information, and tackle the second by specifying the amount of lookahead allowed explicitly in the program. in this paper, we combine these two ideas and demonstrate their power by presenting an interpreter, written in prolog, for a variant of golog that is suitable for efficiently operating in open-world setting by exploiting sensing and bounded lookahead.
diagnosing and correcting student's misconceptions in an educational computer algebra system  using powerful computer algebra programs for mathematics education has been steadily gaining popularity, regardless of inherent user-unfriendliness exhibited by such systems. algebrator [4, 5] is a cas specifically designed to teach high-school algebra. despite its limited domain (or may be because of it), it has proven to be useful to students requiring mastery of basic algebra skills. algebrator's ca engine is but a small part of the whole system; larger portion of it deals with the way in which the system as an electronic tutor engages the student in the learning process. in this paper we will focus on algebrator's error diagnostic capability and teacher-directed generation of appropriate remedial tutoring sessions.  neven jurkovic
business information analysis and interaction technique (biait): finding the big payoff areas  while growth of the computer industry and the computing profession have been phenomenal, this growth has not been accompanied by improved communication between top executives in user organizations and their dp managers about effective use of the new computer- based information technologies. there remains a critical need for ways to demonstrate the impact of computer applications on management's ability to get the best results out of the resources under their control.  one candidate for solving this communication and evaluation problem is the business information analysis and integration technique (biait). it has grown out of some ibm research and is being developed within ibm and by others. the current range of uses covers application development planning and implementation, marketing planning, and organization analysis; other uses are visualized for the future.  the application development planning approach receiving major attention is called business information control study (bics). based upon the biait principles, the bics approach produces prompt identification of problem areas having high management visibility and big potential for payoff from use of computers.  walter m. carlson
design automation research at the university of wisconsin - madison  the university of wisconsin---madison has a large design automation research program with activities in many da and cad areas. the primary thrusts are in testing, high- and low-level synthesis, ai-based cad, rapid implementation of cad tools, design methodologies, and cad system issues. this document describes recent and current da projects. the reader is encouraged to contact the investigators for more information about specific projects.  j. beetem d. dietmeyer y. hu r. jain c. kime p. ramanathan k. saluja
regulatory element detection using correlation with expression (abstract only)  we present a new computational method for discovering _cis-_ regulatory elements which circumvents the need to cluster genes based on their expression profiles. based on a model in which upstream motifs contribute additively to the expression level of a gene, it requires a single genome-wide set of expression ratios and the upstream sequence for each gene, and outputs statistically significant motifs. analysis of publicly available expression data for _sac charomyes cerevisiae_ reveals several new putative regulatory elements, some of which plausibly control the early, transient induction of genes during sporulation. known motifs generally have high statistical significance.  harmen j. bussemaker hao li eric d. siggia
publishing a university computing service newsletter  the university computing services newsletter is the most effective, efficient and consistent way to reach the largest number of computer users. it can also be more than a way to disseminate technical information and news to computer users. the newsletter is tangible evidence of the activities of computing services staff both for end-users and university administrators. it serves as a record of the progress of the computing services, provides incentive for staff to complete projects in a timely manner and signifies a commitment by the computing services to a stable end-user environment.  in 1986, tulane computing services (tcs) went from intermittent production of a newsletter which received little attention from users to a six-times yearly, professional quality publication which has attracted the attention of the university computing community, university administrators and computing services and libraries at other universities. there were eight key factors involved in this transition: (1) management commitment (financial, technical and personnel) to a professional quality newsletter; (2) access to state-of- the-art desktop publishing technology; (3) increased staff commitment to the publication; (4) cooperation with the administrative department responsible for all university publications; (5) development of a consistent newsletter format compatible with that used for all tcs publications; (6) dedication to providing a stable end-user environment; (7) increased access to information from computing services administrators, systems programmers and operations staff; and (8) the hiring of an individual with graphics design and computer expertise who was primarily responsible for all desktop publishing done within the computing services.  alison hartman j. e. diem
the role of computational chemistry in translating genomic information into bioactive small molecules (abstract only)  although genomic information provides many potential targets for drug discovery, the challenge is to convert this information into drugs that cure human disease. workers in computer assisted molecular design and chemometrics have developed a number of techniques to aid this process. examples include selecting diverse compounds for high throughput screening, designing universal or targeted combinatorial libraries, and using a variety of computational techniques to forecast binding affinitiy and bioavailability of compounds. this lecture will summarize recent advances in these areas.  yvonne martin
chemical reaction dynamics: integration of coupled sets of ordinary differential equations on the caltech hypercube  use of the caltech/jpl hypercube multicomputer to solve problems in chemical dynamics is the subject of this paper. the specific application is quantum mechanical atom diatomic molecule reactive scattering. one methodology for solving this dynamics problem on a sequential computer is based on symmetrized hyperspherical coordinates. we will discuss our strategy for implementing the hyperspherical coordinate methodology on the hypercube. in particular, the performance of a parallel integrator for the special system of ordinary differential equations which arises in this application is discussed.  p. g. hipes t. mattson y-s. wu a. kuppermann