GVC Area - Modeling

Geometry processing: design, representation, rendering, analysis, transmission, and animation of shapes

Scope

All GVC students who select Modeling as one of the two specialization sub-areas for the second part of their qualifier are expected to be familiar with the main concepts, major results, common mathematical foundations, and algorithmic techniques used for representing, constructing, processing, transmitting, and rendering digital models of shapes. These include for example the data structure and algorithms for constructing and processing popular representation techniques for curves, surfaces, and solids. Furthermore, students in this area are also expected to understand the various acceleration techniques (simplification, compression, occlusion, space partition) for processing, rendering, animating, or transmitting shapes and basic Computational Geometry results and techniques for dealing efficiently with very large models. Typical problems in Modeling include:

  • Interactive design and editing of curves, surfaces, and solids
  • Construction of a valid (water-tight, oriented) triangle mesh from a large polygon soup
  • Smoothing, sharpening, refining, resampling, and simplifying triangle meshes
  • Compression, progressive transmission, and streaming of large triangle meshes
  • Level-of-Detail, occlusion culling, streamable meshes, and other acceleration techniques for very large meshes
  • Shape analysis, segmentation, matching, comparison, mapping and morphing
  • Hardware-assist for collision detection, Boolean operations
References

Students should be comfortable with the majority of problems and solutions discussed in the following texts and are encouraged to explore other relevant material directly referenced in these texts or pertaining to these problems.

In addition to these references, students should select 6 different modeling problems and be able to demonstrate familiarity with an important recent paper on each one of the selected problems. Preferably, the papers should be chosen from different venues, such as the proceedings of the ACM SIGGRAPH, Eurographics, Symposium on Solid and Physical Modeling, Symposium on Geometry Processing, or Shape Modeling International conferencs (some are posted online), or the main journals that publish modeling content, such as the ACM Transactions on Graphics, the IEEE Transactions on Visualization and Computer Graphics, Computer-Aided Design, Graphical Models, the Visual Computer, Computer Graphics Forum, and Shape Modeling.

For previous notes and papers, go here: Geometry, Topology, Curves, Meshes, Solids, Hausdorff, Motions, Compression, Tightening, Bending, Occlusion

Courses
  • CS 6491: Foundations of Computer Graphics (Rossignac)
Sample Questions
  • TOPOLOGY OF POLYHEDRA: Provide a precise topological definition of a polyhedral solid and of its natural vertices, edges, edge-loops and faces. Define and illustrate the terms of connected components, handles, and holes in such polyhedral solids. When is such a solid a manifold? Why is it important to support non-manifold models and why is it more difficult?
  • CONVEX HULL: Provide a precise definition of the convex hull of a point set S in the plane. Show why the following definition is wrong: The convex hull of a set S is the union of all line segments tA+(1-t)B such that A and B belong to S and t lies in [0..1]. Outline the simplest algorithm and also the most efficient algorithm for computing the convex hull of a set of V points in 2D. What is the complexity of these algorithms?
  • DATA-STRUCTURE FOR TRIANGLE MESHES: Describe in details the Corner Table data-structure for storing triangle meshes. What properties must be verified by a data set represented this way for it to correspond to the boundary of a polyhedral solid? What further restrictions are imposed if the polyhedron is manifold. Describe a few simple operators for traversing such a data structure and explain how they should be used to walk from one triangle to a neighboring one and for visiting all triangles incident upon a vertex. Explain how many bits would be required to store a triangle mesh with T triangles using this data-structure? Provide a precise formula and explain in details your assumptions and the meaning of each factor.
  • CURVED SURFACES AND THEIR TESSELATIONS: Explain the trade-off between representing the boundary of 3D shapes with curved surfaces and representing them with triangles. What is the difference between parametric and implicit surfaces and what are their respective advantages? How would you construct a good triangular approximation for each? Inversely, how would you fit an implicit and a parametric surface to a triangle mesh?
  • BUILDING AND ACCESSING LARGE MODELS: Suppose that you are responsible for building a 3D model of an entire city, so as to support interactive walkthrough of a high visual quality for users connected through the Internet to your server. Suggest a representation scheme and an effective process of acquiring or constructing it. Discuss the various techniques that you would use to accelerate the download of the models and the local rendering.
  • MORPHING Given two models of 3D objects, A and B, each represented by a very different triangle mesh, we want to show an animation of a smooth 3D morphing from A to B. Discuss three or more automatic techniques for computing and animating such morphs. For each technique, explain what are the situations where the morphing would not yield satisfactory results?
  • DIFFERENCE AND DISTANCE BETWEEN POLYHEDRA: Let A and B be two sets. Provide precise definitions for the minimum distance between them, for the Hausdorff distance between them, and for the volume of their symmetric difference. Illustrate the differences between these measures on 2D examples. Especially show examples of drastically different sets with a small Hausdorff distance and a large difference and also of sets with a small volume difference and a large Hausdorff distance. Provide efficient algorithms for computing them when A and B are two convex polyhedra, each represented by a triangle mesh.
  • SUBDIVISION SURFACES: Define what are subdivision surfaces. Describe in details two subdivision schemes for triangle meshes. Discuss their drawbacks. How would you convert a manifold triangulated surface into an approximating subdivision surface. How could you use such a multi-resolution model to edit large features of a 3D shape while preserving small details.
  • SKELETON. A basic notion in modeling is that of a skeleton: a minimalist representation of an object's geometry and/or topology. Describe several methods that can be used to extract or represent an object's skeleton.
  • MORPHOLOGY: Mathematical morphology is an elegant way to cast the problem of representing shape in a set-theoretical framework. Describe its basic concepts and operations (closing, opening, erosion, dilation, structuring elements, etc.) Illustrate them on 2D examples.
  • SIMPLIFICATION: A long-standing problem concerns the reduction in the number of polygons to reduce overall model complexity. Describe some of the well known methods to accomplish this, contrasting their respective advantages and disadvantages.
  • CURVES AND SURFACES: What is a B-spline curve? How do you subdivide a control polyline in 3D so that in the limit you obtain a cubic Bspline? How do you convert a control polyline of a cubic Bspline curve into a series of Bezier control polygons that represent segments of the original Bspline curve.
  • PRIMITIVE SHAPES. Formulate the parametric and implicit representations for a circular cone and a torus. Explain how these should be used for testing point-containment and for computing intersections with rays and the normal at these intersections.
  • DIGITIZATION: It is often desirable to digitize a 3D object and then create a model of the object for subsequent analysis or visualization. A number of 3D digitization approaches exist: Describe these, pointing out their relative advantages/disadvantages, and discuss how a surface representation (either polygonal or parametric, for instance) can be built up from the collected data.
  • DELAUNAY AND VORONOI: Explain what is a Delaunay triangulation of a set of points in the plane and what is their Voronoi diagram. Describe precisely the relation between these two and how one may be derived from the other. Provide a simple yet reasonably efficient algorithm for computing the Voronoi diagram of V points in 2D. What is the asymptotic complexity of this algorithm?
  • PLAN PARTITION: The difference between a plane P and the union of L lines in P in general position is a set of R maximally connected regions. Define the properties of these regions and express L precisely as a function of R (prove your formula). Each region may be identified by L bits. Each bit indicating whether the region lies on the left or on the right of the corresponding line. How many possible regions could be defined by all the combinations of values for these bits? Provide an efficient algorithm that would discover which of these combinations correspond to non empty regions. What is the complexity of this algorithm?
  • ALPHA-SHAPES: Given a set of P points in the plane, describe in details an algorithm that would interpolate these points by a well chosen set of triangles and lines. Your interpolation should produce a good approximation to the original set from which the points were obtained by uniformly distributed, although irregular, random sampling. Analyze the complexity of your algorithm.
  • TRIANGULATING A POLYGON: Provide the simplest algorithm for triangulating a multiply connected polygon. What is the complexity of your algorithm? Suggest more complex algorithms with a lower complexity.
  • DETECTING INTERSECTIONS OF POLYHEDRA: Consider two solids A and B, each represented by a triangle mesh. Describe in details an efficient algorithm for detecting whether they intersect. What is the cost complexity of your algorithm? Propose auxiliary datastructures that will reduce the expected cost.
  • NUMERIC ACCURACY: Explain why integers are more effective than floats for representing the coordinates of the vertices of a polyhedral 3D model. Outline a process of computing the most accurate k-bit integer representation for each vertex coordinate. What should be the minimum k for locating cities on a map of the US? What should be k for modeling a car engine with 1mm accuracy? Explain why fixed precision computations may lead to drastic errors in the computation of the intersection between two polyhedra. Discuss epsilon-based and exact techniques to overcome this problem.
  • MINKOWSKI OPERATIONS: Define the Minkowski sum between two sets and illustrate it in 2D. Provide a simple and efficient algorithm for computing it for two convex polygons in 2D. Explain precisely how such operations may be used to reduce a translational path planning of an object amongst obstacles to the search of a trajectory of a point in free space. Explain how combinations of Minkowski operations may be used to eliminate details and noise and to round corners.
  • OCCLUSION: Given a set of 3D objects and a rectilinear cell C, provide an efficient algorithm for computing precisely which objects are visible from at least one point in C. Illustrate your algorithm in 2D.
  • COMPRESSION: Suggest ways of modifying the connectivity of a triangle mesh by edge-flips, so that the resulting connectivity graph can be better compressed using Edgebreaker.
  • LOD AND COMPRESSION TECHNIQUES: Define the following terms for 3D models: lossy-compression, loss-less compression, simplification, progressive refinement, and adaptive resolution. Discuss how they relate to each other and their use for interactive a 3D navigation and internet access. Provide a high level description of the algorithmic processes involved in each one of these technologies and point out the interesting research avenues.

  • CONSTRICTION: You are given a manifold triangle mesh M in 3D that has two bounding loops, A and B, where the vertices are arranged along a regular circle of radius r. M is represented using the Corner Table or some equivalent data structure, so that you can use corner operators: c.v, c.t, c.n, c.s. M is an irregular triangulation of a long, winding tube. Explain how you would compute the key constriction: the place where the area of the cross-section of the tube passes by a global minimum. The problem is that the term ‘constriction’ is not well defined.  Please do your best to define it.

  • STEADY PATTERN: You are given two edges E(A0,B0) and E(An,Bn) in 3D.  Explain how you would compute a steady pattern of n-1 intermediate edges that starts with edge E(A0,B0) and finishes with edge E(An,Bn). (A pattern is steady if there exists a transformation T such that E(Ai+1,Bi+1) = T(E(Ai,Bi)). Explain your overall approach and provide some guidance (not necessarily all the details) about how to compute it. Is the motion we define unique?

  • ROOMS: M is a triangle mesh with T triangles, E edges, and V vertices. M is connected. Each edge bounds at least 2 triangles. No vertex is a junction (i.e., removing any single vertex will not change the genus or number of components). M (i.e., the closure of the union of its triangles) decomposes three-space into a set of rooms (connected components of the complement of M), including one external, infinite room. Provide an outline and enough details to guide an implementation of an algorithm that computes the number n of rooms. Explain what data structure and operators you would like to have to support your algorithm.

  • BENT CAPLET: Consider three disjoint balls with centers A, B, C and with respective radii a, b, c. Explain how they may be used to define a bent caplet: A solid bounded by a smooth surface that contains a portion of Sph(A,a) and Sph(C,c) and is hugging (tangential contact) Sph(B,b) along the way. Provide first a high-level outline and then enough detail to guide an implementation of an algorithm that would render the bent caplet. Explain why the solution of using Neville’s algorithm in 4 space (3 coordinates and radius) may fail to produce a smooth surface and how your solution fixes the problem.

 

Last updated 8/9/18

Dean's Messages

GT Computing Helping Stories