Most methods for computing offsets and bisectors of parametric curves are based on a local formulation of the distance to a curve. As a consequence, the computed objects may contain spurious parts and components, and have to be trimmed. We approach these problems as global optimization problems, and solve them using interval arithmetic, thus generating robust approximations that need not be trimmed. [ps]
We prove that the Jouanolou foliation of degree k<5 admits no nontrivial minimal sets. The proof uses reliable computations based on interval arithmetic. [ps]
We present an algorithm for intersecting finite-element meshes defined on parametric surface patches. The intersection curves are modeled precisely and both meshes are adjusted to the newly formed borders, without unwanted reparametrizations. The algorithm is part of an interactive shell modeling program that has been used in the design of large offshore oil structures. To achieve good interactive response, we represent meshes with a topological data structure that stores its entities in spatial indexing trees instead of linear lists. These trees speed up the intersection computations required to determine points of the trimming curves; moreover, when combined with the topological information, they allow remeshing using only local queries. [ps]
In this paper we present a method for applying 2D textures onto composite and articulated objects defined by implicit functions. The method generates a particle system associated with the gradient vector field of an implicit function which acquires texture coordinates at a support surface. By extending this method to composite objects, an implicit surface may change its shape in time, while maintaining texture consistency. This approach prevents the appearance of undesirable effects such as ghosting and artifacts at the blending parts of an implicit object. [ps]
We present an algorithm for intersecting finite-element meshes defined on parametric surface patches. The intersection curves are modeled precisely and both meshes are adjusted to the newly formed borders. The algorithm is part of an interactive shell modeling program, which has been used in the design of large offshore oil structures. We avoid unacceptable interaction delays by using a variant of the DCEL data structure that stores topological entities in spatial indexing trees instead of linked lists. These trees speed up the intersection computations required to determine points of the trimming curves, and also allows mesh reconstruction using only local queries. [ps]
We discuss the control possibilities of texture mapping for a new method to apply 2D textures onto implicit surfaces. The method uses a particle system associated with the gradient vector field of an implicit function to acquire texture coordinates at a support surface. It introduces geometric, parametric and temporal concepts to solve the problem of texture mapping, elements from which we create tools for local and global control. [ps]
This monograph is a set of course notes written for the 21st Brazilian Mathematics Colloquium held at IMPA in July 1997. It gives an overview of the field of self-validated numerics-computation models in which approximate results are automatically provided with guaranteed error bounds. We focus, in particular, on two such models: interval arithmetic and affine arithmetic.
Interval arithmetic (IA) was developed in the 1960's by Ramon E. Moore. IA is the simplest and most efficient of all validated numerics models, and, not surprisingly, the most widely known and used. After two decades of relative neglect, IA has been enjoying a strong and steady resurgence, driven largely by its successful use in all kinds of practical applications. We are confident that many readers of this monograph will find IA to be a useful tool in their own work as well.
Affine arithmetic (AA) is a more complex and expensive computation model, designed to give tighter and more informative bounds than IA in certain situations where the latter is known to perform poorly. The AA model was proposed and developed recently by the authors, although a similar model had been developed in 1975 by E. R. Hansen. Apart from its usefulness for certain special applications, AA is being presented here as an example of the many topics for research that are still unexplored in the field of self-validated numerical methods. [ps]
This paper introduces a new refinement method for computing triangle sequences of a mesh. We apply the method to construct a single generalized triangle strip that completely covers a parametric or implicit surface. A remarkable feature of this application is that, our method generates the triangulation and the triangle strip simultaneously, using a mesh refinement scheme. As a consequence, we are able to produce a hierarchy of triangle strips defined at each refinement level. This data structure has many applications in geometry compression and rendering. [ps]
We show that faster solutions to unconstrained global optimization problems can be obtained by combining previous accelerations techniques for interval branch-and-bound methods with affine arithmetic, a recent alternative to interval arithmetic that often provides tighter estimates. We support this claim by solving a few well-known problems. [ps]
This paper introduces a unified and general polygonization algorithm for parametric and implicit surfaces. The algorithm produces a hierarchical mesh that is adapted to the surface geometry and has a multiresolution progressive structure. This representation can be exploited with advantages in several applications. [ps]
We discuss the problem of adaptive polygonization of regular surfaces of the euclidean 3D space, and present effective algorithms for computing optimal polygonizations of surfaces described in parametric or implicit form. [ps]
Lua is a language specifically designed to be tailored for specific domains. In this sense, Lua can be regarded as a language framework. This paper describes our experience using Lua for building different Domain-Specific Languages. These domains include bibliographic databases, user-interfaces, graphical metafiles, and finite element analysis. [ps]
We present a new method for adaptive polygonization of parametric surfaces. The method combines recursive simplicial subdivision of the domain and point sampling along curves on the surface. We avoid cracks in the polygonal mesh by determining the optimal sampling rate along the edges of a cell before subdividing it. The method is suitable for surfaces with low variations, such as bicubic patches, as well as for surfaces with high variations, such as height fields. [ps]
Design patterns capture object-oriented software design experience, and allow this practical knowledge to be shared among members of the software development community. Thus, designers can publish their patterns on the Web and make them broadly accessible. Web-based tools to apply these design patterns to objects would be a significant further step in making design experience more accessible. Designers could access the best patterns for their design, and possibly experiment before making final design commitments. This paper describes the prototype of a designer's assistant which implements many of these ideas. The structure and operation of the tool are described as well as the underlying formalisms needed to make the construction of the tool feasible. [html]
We present a new method for applying texture onto implicit surfaces. The method tracks particles associated with the gradient vector field of the implicit function. Unlike others methods, this approach gives effective tools for controlling the placement of the applied texture. [project home page]
We introduce HPS, a new topological data structure that efficiently represents hierarchies of planar subdivisions, thus providing direct and efficient support for GIS concepts such as abstract generalizations and multi-scale partitions. Unlike previous ad hoc solutions, HPS provides efficient access to adjacency information for each level and across levels, while storing the complete hierarchy in a single data structure, without duplications. HPS also provides topological operators that ensure global consistency. Like all topological data structures, HPS can be used as a framework onto which geometric and attribute information is placed: HPS explicitly handles attributes consistently with modeling, and naturally supports both topological and geometrical multi-resolution representations. We also discuss how some typical applications in GIS, Digital Cartography, and Finite Element mesh generation can be improved with HPS. [ps]
We prove that the visibility graph of a set of line segments lying in disjoint vertical strips contains a monotone circumscribing Hamiltonian cycle. This provides some evidence for a conjecture of Mirzaian, as refined by O'Rourke and Rippel. [ps]
We describe a variant of a domain decomposition method proposed by Gleicher and Kass for intersecting and trimming parametric surfaces. Instead of using interval arithmetic to guide the decomposition, the variant described here uses affine arithmetic, a tool recently proposed for range analysis. Affine arithmetic is similar to standard interval arithmetic, but takes into account correlations between operands and sub-formulas, generally providing much tighter bounds for the computed quantities. As a consequence, the quadtree domain decompositions are much smaller and the intersection algorithm runs faster. [ps]
After reviewing three classical sampling methods for implicit objects, we describe a new sampling method that is not based on scanning the ambient space. In this method, samples are ``randomly'' generated using physically-based particle systems. [ps]
Minimizing the amount of code that must be written and maintained is particularly critical in the development of the user interface for a highly interactive system, since the code for the user interface represents a substantial part of the application. This is especially important where the interactive system is available on a number of distinct platforms. Providing a single user interface abstraction requiring only one set of source code that can be mapped automatically into specific interface systems appears to be the preferred approach; but the underlying model must be designed carefully in order to keep the system relatively simple, easy to use and maintain, and allow ease of experimentation as user interfaces are produced. We describe the design and implementation of IUP/LED, a portable user interface toolkit that we believe has these properties. The toolkit is designed for rapid prototyping and modification, to provide a look-and-feel appropriate to a specific computing environment, is easily expanded to support new interface developments, and supports an abstract layout model. We also present a summary of the experiences in using the toolkit to indicate that it does support the original design objectives. [ps]
This paper describes Lua, a language for extending applications. Lua combines procedural features with powerful data description facilities, by using a simple, yet powerful, mechanism of tables. This mechanism implements the concepts of records, arrays, and recursive data types (pointers), and adds some object-oriented facilities, such as methods with dynamic dispatching. Lua presents a mechanism of fallbacks that allows programmers to extend the semantics of the language in some unconventional ways. As a noteworthy example, fallbacks allow the user to add different kinds of inheritance to the language. Currently, Lua is being extensively used in production for several tasks, including user configuration, general-purpose data-entry, description of user interfaces, storage of structured graphical metafiles, and generic attribute configuration for finite element meshes. [ps | html]
We prove that Euclidean minimal spanning trees correctly reconstruct differentiable arcs from sufficiently dense samples. The proof is based on a combinatorial characterization of minimal spanning paths and on a description of the local geometry of arcs inside tubular neighbourhoods. We also present simple heuristics for reconstructing more general curves. [ps]
This gem presents an adaptive method for sampling the domain with respect to local curvature. Samples concentration is in proportion to this curvature, resulting in a more efficient approximation; in the limit, a flat curve is approximated by merely two endpoints. Applications of this sampling strategy, including rasterization and arc length parametrization, are also discussed. [ps]
We discuss adaptive enumeration and rendering methods for implicit surfaces, using octrees computed with affine arithmetic, a new tool for range analysis. Affine arithmetic is similar to standard interval arithmetic, but takes into account correlations between operands and sub-formulas, generally providing much tighter bounds for the computed quantities. The resulting octrees are accordingly much smaller, and the rendering faster. We also describe applications of affine arithmetic to intersection and ray tracing of implicit surfaces. [ps]
We describe a tool for developing highly abstract, interactive graphical applications. Simple, high level programmable access is provided to both conventional interface objects and active graphical objects that are specific to the application domain. This allows occasional programmers to quickly develop their own sophisticated interactive tools, such as front-ends to legacy batch programs.
We describe the design and implementation of Lua, a simple, yet powerful, language for extending applications. Although Lua is a procedural language, it has data description facilities, and has been extensively used in production for several tasks including user configuration, general purpose data-entry, description of user interfaces, description of application objects, and storage of structured graphical metafiles. [ps]
We present discrete physically-based methods for generating polygonal approximations of implicit surfaces. These methods not only generate a combinatorial manifold approximating the surface, but also produce a structure that is well suited to numerical simulations in physically-based modeling and animation systems. [ps]
We divide the computation of polygonal approximations of implicit objects into two phases: sampling and structuring. Unlike classical treatments, we study each phase separately. Classical sampling methods are reviewed, and a new sampling method is proposed; this method uses physically-based particle systems, and is more robust than classical enumeration and continuation methods. We describe a broad taxonomy of structuring problems. According to this taxonomy, the presence of an independent structuring phase casts the modeling problem as a problem in non-parametric scattered data interpolation, which we propose to solve using computational morphology. The use of global structuring is described in detail for curves: we prove that minimal spanning trees are good morphological tools for arcs. A couple of methods are also suggested for surfaces. [ps]
The necessity of specialized database management systems for the efficient handling of load information in finite element structural analysis/design is discussed. A new system with a simple interface and low overheads is proposed. Both the user interface and the technical details of the implementation are presented. An evaluation of the performance of the system is also given. The FORTRAN listing of a model implementation is included in the Appendix.
bs is a simple programmable button shell for X that I wrote some years ago but only recently posted to the net. Despite being a powerful tool, supporting user defined dialog layout, bs is actually a very simple and short program. The source code of bs is fully explained in this article. This explanation provides brief introduction to Xt, widgets, callbacks and callback data. I also show how easy it is to use Motif widgets instead of Athena widgets, for which bs was originally developed. [html]