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.
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.
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.
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.
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)
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.).
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.
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.
T2: Find out if a point [3⁄4, 2⁄4] lies inside or outside of the circle.
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)
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:
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.
T2: Find out if a point [2⁄5, 3⁄4] lies inside or outside of the circle.
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.
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:
Now, using this definition, let's try completing our two tasks:
T1: Find coordinates of 20 different points on the surface of the circle.
T2: Find out if a point [2⁄5, 3⁄4] lies inside or outside of the circle.
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 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).
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).
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.
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.