• Calendar

January 25, Monday
14:00 – 16:00

In this talk I will present several problems I have been working on in geometric modeling, computational geometry and computer graphics. The first problem is the construction, under the exact computation paradigm, of arrangements of Bezier curves. The second is the computation of Voronoi cells of free-form curves and the third is the visualization of solid models using the graphics processing unit (GPU). The common theme in these problems is that they contain geometric constructions, which either cannot be represented using their standard geometric representation or computing them is too expensive. Previous methods for attacking these problems typically use approximations, either of the input or of the problematic geometric constructions. Our methods, on the other hand, use procedural representations, which enable to answer a set of queries that are sufficient for solving the problem at hand. In arrangements of Bezier curves, we represent intersection vertices with references to intersecting curves, and to bounding polygons. This enables us to avoid the prohibitive running times incurred by exact algebraic arithmetic. In the computation of Voronoi cells of free-form curves, the bisector curves cannot be represented in standard (Bezier or B-spline) form. Instead we use a representation based on an implicit function in the curves parametric domain combined with a mapping to the Euclidean plane. Using this representation we can answer the queries required to compute the lower envelope of the bisector distance functions and thus compute the boundary of the Voronoi cell. When rendering solid models using the GPU, a common problem is the appearance of cracks between faces in the model visualization. These are a result of the non-exact representation of trimming curves in the model. Using a representation that stores references to intersecting surfaces we are able to avoid these cracks and render a smooth water tight model. This work is part of an ongoing project. In my talk, I will present the different problems and how applying procedural representations helps in their computation. I will also present other problems for which I believe applying such representations can be useful. The work described in this talk was done in collaboration with Gershon Elber, Ron Wein, Kirk Haller and others.