Loading...
pipeline

PB009: Lecture 2

Geometry Representations

This lecture discusses the requirements and types of data representations used in computer graphics.

The first part of lecture discusses types of representations in terms of represented topology and data definition (implicit, parametric, explicit). Subsequently individual types of representations are covered.

Requirements for different representations

In modern computer graphics, we need to represent various types of spatial data, encompassing a broad range of applications and formats. This includes records of real-world data, such as 3D scans and CT images, which capture the physical characteristics of objects and environments with high precision. These records are crucial e.g., in medicine or engineering, providing detailed insights into the structures being studied.

In addition to real-world data records, we often need to create models of real-world objects and phenomena that either cannot be directly recorded or do not yet exist. Examples include architectural models of buildings, construction templates, detailed representations of DNA structure, and molecular models used in chemistry and biology. These models help in visualizing and understanding complex systems, facilitating simulations, and aiding in the design and analysis processes.

Moreover, the representation of entirely virtual objects or scenes is essential, particularly in the realm of animated movies, computer games, and virtual reality environments. These virtual representations can range from simple objects to entire immersive worlds, enabling interactive and engaging user experiences.

There are also scenarios that lie between purely real-world data and entirely virtual constructs. An example of this is the virtual reconstruction of archaeological sites based on records of discovered ruins. This approach combines real data with virtual modeling to recreate historical sites, providing a means to explore and study these locations as they might have appeared in the past.

Overall, the diversity of spatial data highlights the importance of designing and choosing suitable methods to accurately represent the physical and virtual worlds, be it for the purpose of visualization, simulation, or scientific analysis. Based on the needs of different applications, we can define several properties that we may require the data representation to fulfill. Note that it is often unnecessary or even impossible to fulfill all of them completely. When choosing a suitable representation, we are often looking for balance based on the specific purpose of the representation. Different applications may prioritize different attributes, and achieving the right balance (e.g., level of detail vs. memory consumption) ensures that the representation effectively meets the intended use case requirements.

circle
circle
circle
circle
Examples of different data in computer graphics: comparison of two 3D facial scans, molecule model, game asset, archeological reconstruction (Ferdani et al., 2020)

Unambiguity: The representation should be clear and distinct, ensuring that it corresponds to a single, unique object without any confusion with other objects. It is clear which object is represented (e.g., it is clear that the character model shows Mario and not Luigi).

Uniqueness: Each object should have a single, unique representation that differentiates it from all other objects there are no multiple representations of the same object, e.g., there is only one Mario). This helps in preventing duplication.

Completeness: The representation should include all the required information about the object for the given task. For example, for rendering, we might need information about vertex positions, normals, and colors. Without all the data, the representation would be incomplete.

Precision: The representation must be accurate and exact, describing the object at a sufficient level of detail. Precision is essential for applications where exact measurements and detailed analysis are required (e.g., medical applications). On the other hand, this requirement might be relaxed for applications such as games or animated movies.

Compactness (memory efficiency): The representation should be efficient in terms of memory usage, minimizing the amount of storage required, ideally without sacrificing detail or accuracy. Compactness is important for optimizing performance and resource management, especially in systems with limited storage capacity.

Efficient algorithms: The representation should support the implementation and use of efficient algorithms, for example, for rendering or operations like searching (e.g., fast mesh traversal algorithms are needed when searching for the closest points on two compared 3D meshes).

Ease of use: The representation should be user-friendly and intuitive, allowing easy adoption without excessive technical support. This might include reasonable and intuitive data organization or accessible documentation.

Wide applicability: The representation should be versatile, and applicable across different domains and use cases, increasing its utility and relevance. In this aspect, modularity and extendability might be important, as opposed to fixed single-purpose features.

Error-proofness: The representation should be designed to minimize errors and be robust against common mistakes. Error-proofing helps in maintaining the integrity and reliability of the representation, reducing the likelihood of inaccuracies and misinterpretations.

Topology and geometry

Before we dive into different types of representations let us first discuss some important terminology.

Topology is the study of properties that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending, but not tearing or gluing. It focuses on the qualitative aspects of space, such as connectivity and continuity. The typical properties that are studied include connectedness (e.g., holes in the surface) or adjacency (how points are connected).

This differs from geometry, which is the study of the qualitative properties and measurements of shapes, sizes, and relative positions, including properties such as curvature, area, or distance between points. In other words, the topology of the object is not affected by (continuous) deformations, while geometry is. Take a look at the images below.

topology vs geometry
All of the illustrated surface have different geometry. Further, the two surfaces on the left have the same topology, as do the two on the right. But the sphere and the two-holed doughnut surface have different topologies: no matter how you try, you can never deform one to look like the other. (Source: Jeffrey Weeks, The Shape of Space).
topology vs geometry
Now try to identify yourself which of the surfaces have the same topology. (Answer, Source: Jeffrey Weeks, The Shape of Space).

In computer graphics we often discuss topology in terms of basic topological elements that describe the shape of the object:

Vertices - points in 3D space that define the corners or intersections of geometric shapes

Edges - lines that connect two vertices, they are typically straight lines (e.g., in polygonal meshes), but more generally can also be curves

Faces - surfaces bounded by edges, they are typically polygons, such as triangles or quadrilaterals, but more generally can be any mathematically defined surface

Solids - enclosed regions of 3D space (typically some kind of polyhedrons), they are usually defined using vertices, edges, and faces to describe their surface, which is watertight (there are no holes in the surface)


topological elements
Topological elements

The following images illustrate a case where the general surface topology of the object (a sphere) is the same, as is the geometry (positions) of vertices. However, the topology of the polygonal mesh forming sphere is different. The vertices are connected in a different manner - on the left, most vertices are of degree 4 (they are connected to 4 other vertices), while on the right, the average degree is 6. Along with the information about geometry and topology (connectedness, adjacency) of these topological elements, representations can also include additional information tied to these elements (color of vertices, normal of the faces, material, etc.).

topological comparison
Two objects with same vertex geometry but different topology of the mesh

Types of representations

Based on the type of topological elements included in the representations, we can split them into several categories:

Point representations - include only information associated with vertices, no connectivity.

Wireframes - pseudosurface representation, includes connectivity of vertices, but no information about how they form faces.

Surface (shell, boundary) representations -include information about outer surface of the objects.

Volumetric/Solid representations - include information about inner structure and content of the object

Besides topology, we can also look at how the geometry is defined (mathematically). Here we can differentiate between implicit, parametric, and explicit definitions.

Implicit representations

With implicit representations, we are not given any information about the positions of points/vertices of an object, but rather we are provided with the relationship the object and its surface/vertices fulfill. This is given by an implicit equation f(x,y,z) = 0 (for 3D space). The surface is then defined as zero contour of this function, since only points P(x,y,x) for which the function returns 0 are part of the surface. If the equality is not set to 0, but to a different value (level), we are talking about level sets, as the object is then formed by set of points corresponding to a certain "level" of the function. In case we are considering the zero contour or zero level set as the surface of the object, the function is often called signed distance function (SDF), since the sign of the returned value indicates, if the point P lies inside (SDF is negative), on the surface (SDF is 0), or outside (SDF is positive).

Example: The relationship that defines a circle is that its all points have the same distance from its center and that distance is the radius. Thus, a unit circle (r=1) in 2D centered at (0,0) can be defined by following function:

f(x,y) = x2+ y2 - 1 = 0

Now, using this definition, let's try completing two tasks:

T1: Find coordinates of 20 different points on the surface of the circle.

  • Using this definition, there is no straightforward solution! We can only guess coordinates and try if the equation is fulfilled.

T2: Find out if a point [3⁄4, 2⁄4] lies inside or outside of the circle.

  • Easy! We simply plug the coordinates into the equation: 9/16 + 4/16 - 1 = - 3/16. The result is negative, so we know, the point lies inside.

implicit

Conclusion: Implicit representations are bad for finding points (sampling), but they are good for determining if points lie in/out or on surface. We will later look at some techniques commonly used to render implicit surfaces.

Examples of commonly used implicit representations: implicit surfaces (using SDF), metaballs/blobby surfaces, constructive solid geometry (CSG)

Parametric representations

With parametric representations, the surface of the object is expressed as a function of one or more parameters. In addition to the definition of the function, we also need the information about the extent of the parameter(s). The parametric definition in 3D thus takes the following form:

parametric equation

where, fx(t), fy(t), fz(t) express the coordinates x,y,z of point P(t) of the defined object for a given t and a,b specify the interval for which the function is defined.

Example: We will again use the case of a unit circle in 2D centered at (0,0). A circle can be easily expressed as a function of an angle Θ which will be our parameter:

fx(Θ) = cos Θ
fy(Θ) = sin Θ
where 0 ≤ Θ < 360°

Now, using this definition, let's try completing the two tasks:

T1: Find coordinates of 20 different points on the surface of the circle.

  • Easy! Just pick 20 different values from interval 0 ≤ Θ < 360° and plug them into the defining equations. For example, let's pick 30°:
    x = cos 30° = 0.866; y = sin 30° = 0.5

T2: Find out if a point [2⁄5, 3⁄4] lies inside or outside of the circle.

  • There is no straightforward way to test it with this definition.

parametric

Conclusion: Parametric representations are bad for determining if points lie in/out or on surface but they are great for finding points (sampling). Because of this, parametric definitions form the basis of geometry modelling in computer graphics and we will see a lot of them in following lectures.

Explicit representations

With explicit representations, one coordinate of a surface point (dependent variable) is expressed as a function of other coordinate(s) (independent variable(s)). The parametric definition in 3D, where z coordinate is expressed as a function of x and y thus takes the form z = f (x,y), but in order for this definition to be useful, we need to specify the scope of x and y: a ≤ x ≤ b; c ≤ y ≤ d .

Example: We will again use the case of a unit circle in 2D centered at (0,0). We will express y as a function of x. In this case we have a bit of a problem, since for each x, there are two points on the circle, one with positive and one with negative y coordinate. We will use two separate functions, that will define two half circles:

explicit equation

Now, using this definition, let's try completing our two tasks:

T1: Find coordinates of 20 different points on the surface of the circle.

  • Easy! Just pick 20 different values for x from interval -1 ≤ x ≤ 1 and plug them into the defining equations. For example, for x = 0.5:
    y = √ 0.75 = 0.866; y' = - √ 0.75 = -0.866

T2: Find out if a point [2⁄5, 3⁄4] lies inside or outside of the circle.

  • There is no straightforward way to test it with this definition. But we can convert it to implicit form.

parametric

Conclusion: Explicit representations are bad for determining if points lie in/out or on the surface but they are great for finding points (sampling). Incidentally, this is a common way to procedurally generate a so-called heightfields or heightmaps for terrains (e.g., in games). The x and y coordinates are regularly sampled and a z value is generated by the function.

In some literature, you will find what we described here as parametric representations included under explicit definitions. That is also correct, since in essence they also explicitly describe the surface of the object. For the sake of completeness, we keep the two definitions separate.

Furthermore, in a broader sense of the word, explicit representations are representations that explicitly list all elements of geometry (coordinates are not given in functional form). These include for example point clouds, voxel grids, or polygonal meshes.

Point-based representations

Point-based representations contain only information related to isolated points in space (position, their color, possibly normals). They typically do not contain any information about the topology of the object. Such representations are called point clouds. A point cloud consists of a discrete set of unstructured or semi-structured points. They are the typical product of 3D scanning process, e.g., photogrammetry, which works by capturing multiple overlapping images of an object or area from different angles. Using image matching and triangulation, the positions of points in 3D space are then estimated (see image below).

Some technologies, such as laser scanning (LiDAR), produce more structured results. LiDAR scanners measure the time it takes for the emitted light beam to reflect back to the sensor to estimate distance. Since the scanning is performed in regular grid pattern, the resulting scan from one direction is essentially a 2D image encoding the distances of points from the scanner, resulting in 2.5D representations called range image. Here, the topology can be inferred thanks to regular grid arrangement of points. However, the scanning is typically performed from multiple directions, much like in photogrammetry, resulting in semi-structured 3D point cloud. There are numerous other techniques used for acquisition of 3D spatial point-based data, with wide spectrum of applications, such as digital archeology, gaming and movies (e.g., to create realistic models of real world objects), medicine and dentistry (e.g., for prosthetics construction), and extended reality (scanners are used to correctly estimate the position of user and their surroundings).

Photogrammetry
Point cloud of a statue captured by photogrammetry.
(Source: Rob Williams, Techgage.)
range image
Range image of a face.
(Source: Fabry, Smeets, and Vandermeulen, 2010).

Point-based representations can either be visualized directly or converted to surface representation. For direct visualization, point-based rendering techniques such as billboarding or surface splatting can be used. In billboarding, each point is replaced by a flat primitive patch (typically a circle or a square) facing the camera, effectively covering the gaps between points. Splatting works similarly, but the patches are oriented according to estimated surface normal at the given point, which allows correctly lighting the object. The patches are blended in order to create illusion of smooth surface. Since the rendering is performed on point-wise bases, it is easily parallelizable and thus can be efficiently performed on GPU.

Photogrammetry
Point cloud billboarding.
(Source: Schütz, Krösl, and Wimmer, 2019.)
range image
Point cloud splatting.
(Source: Kobbelt and Botsch, 2004).

However, in some cases, point-base rendering is not sufficient and it is necessary to reconstruct the topology and extract the surface for further analysis and processing. Here, triangulation-based techniques (e.g., Delaunay triangulation) such as alpha-shapes are used. In these technique the whole point cloud is triangulated, and the unsuitable edges are removed. Both point-based rendering and surface reconstruction techniques are covered in more details in followup courses (PV112, PA010).

Edge-based representations: wireframes

Wireframe is a pseudo-surface representation of a three-dimensional object containing vertices and edges connecting them, without information about the actual surfaces. It is essentially a "skeleton" of the 3D model. The representation does contain some topological information (vertex connectivity), but it is still incomplete and ambiguous. Take a look at the image bellow. If we wanted to add surface to the wireframe model on the left, it could be interpreted in numerous different ways. Wireframes are often used for the purpose of visualization in 3D modelling software, either as standalone representations or in combination with surfaces, to provide understanding of the basic shape, structure, and topology of the objects (e.g., polygonal meshes).

wireframe
Multiple interpretations of wireframe model (leftmost).

Surface representations

Polygon soup
The simplest representation that contains the information about surfaces is a so-called polygon soup. This representations consists of set of vertices, edges, and polygons formed by them. However, the set of polygons is unstructured - there is no information about adjacency of polygons or connectivity of vertices, hence the term "soup". It is often used for storing 3D models and several commonly used file formats, such as OBJ or STL, belong to this category. In many cases, such representation can be sufficient, as rendering is typically parallelized and each polygon is processed independently of its neighbors.

In cases were the adjacency and connectivity is necessary, it can typically be easily computed from the available data. For example, the Wavefront OBJ file consist of 4 lists. The first three list specify vertex coordinates, normals, and texture coordinates. The last list contains list of polygons (faces), which are defines by indices referring to the first three list (see example below). Adjacency can be inferred based on the faces sharing same vertices.
obj
Excerpt from exemplary OBJ file.
Polygon mesh
Perhaps the most common way of representing 3D objects in computer graphics is using polygonal mesh. Like polygon soup, this representations consists of geometry given by vertices, edges, and polygons formed by them. However, unlike polygon soup, we are also working with topology, described by connectivity adjacency relationships (e.g., which vertices are connected, which faces are adjacent to edge, etc.). These relationships are important, since since without them, we would have ambiguous representation (much like in case of wireframes).
change in topology
Two pairs of triangles with same vertex geometry but different topology.

There are several types of polygonal meshes used in computer graphics, that can be categorized by their topology:

Structured meshes - have regular connectivity, i.e., each vertex is connected to the same number of other vertices in regular pattern. As such, we do not need to store connectivity information since it is inherent. Furthermore, is also leads to efficient algorithms, such as neighborhood search.

The most commonly used type of structured meshes is quadrilateral mesh. It consists of interconnected four-sided polygons, known as quadrilaterals or quads. Becaus of their flowing geometry quad meshes are particularly suitable for modelling and animation. They naturally support the creation of edge and face loops, which are continuous loops of edges (or faces) useful for defining areas of articulation and for achieving smooth deformations (see image below). Furthermore, quad meshes also support regular subdivision, which enables increasing level of detail without unexpected results and is another technique commonly used in 3D modelling and animation (more on that in course PA010). Lastly, it is also very easy to triangulate quad mesh, since each quad can be diagonally split into 2 triangles.

edge loops
Edge loops on a facial model (Source: Isaac Damasceno).

Parametric surfaces
Implicit surfaces
Note: In recent years, implicit modelling and representations are gaining popularity as they are suitable for alternative rendering approaches (raycasting and raytracing vs. traditional rasterization which is optimized for triangles), as well as due to new methods for modelling and surface reconstruction (based on deep learning).

Volume/solid representations

Answers

Surfaces that have same topology: (a,c), (b,d), and (e,f,g,h). Surface h may look like it has 4 holes, but when you try to flatten it, you will see there are only 3. For surface g, you need to uncross the center piece.